# POMDPs Make Better Hackers: Accounting for Uncertainty in Penetration Testing

arXiv: https://arxiv.org/abs/1307.8182 · HTML: https://mlsanity.com/paper/1307.8182/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2013.

## Built on by (most cited first, 14 of 14)

- [PentestAgent: Incorporating LLM Agents to Automated Penetration Testing](https://mlsanity.com/paper/2411.05185/) (2024)
- [A Temporal-Pattern Backdoor Attack to Deep Reinforcement Learning](https://mlsanity.com/paper/2205.02589/) (2022)
- [Automated Penetration Testing with LLM Agents and Classical Planning](https://mlsanity.com/paper/2512.11143/) (2025)
- [Don't Watch Me: A Spatio-Temporal Trojan Attack on Deep-Reinforcement-Learning-Augment Autonomous Driving](https://mlsanity.com/paper/2211.14440/) (2022)
- [Deep Reinforcement Learning for Cyber System Defense under Dynamic Adversarial Uncertainties](https://mlsanity.com/paper/2302.01595/) (2023)
- [Using Constraint Programming and Graph Representation Learning for Generating Interpretable Cloud Security Policies](https://mlsanity.com/paper/2205.01240/) (2022)
- [A Unified Modeling Framework for Automated Penetration Testing](https://mlsanity.com/paper/2502.11588/) (2025)
- [GAIL-PT: A Generic Intelligent Penetration Testing Framework with Generative Adversarial Imitation Learning](https://mlsanity.com/paper/2204.01975/) (2022)
- [Tutorial on Course-of-Action (COA) Attack Search Methods in Computer Networks](https://mlsanity.com/paper/2205.13763/) (2022)
- [Planning with Dynamically Estimated Action Costs](https://mlsanity.com/paper/2206.04166/) (2022)
- [CloudLens: Modeling and Detecting Cloud Security Vulnerabilities](https://mlsanity.com/paper/2402.10985/) (2024)
- [Modeling Behavioral Preferences of Cyber Adversaries Using Inverse Reinforcement Learning](https://mlsanity.com/paper/2505.03817/) (2025)
- [NASimJax: A GPU-Accelerated Policy Learning Framework for Penetration Testing](https://mlsanity.com/paper/2603.19864/) (2026)
- [Staying on the Attack Path: Structured State for Long-Horizon Automated Penetration Testing](https://mlsanity.com/paper/2609.07344/) (2026)

## Abstract (arXiv)

Penetration Testing is a methodology for assessing network security, by generating and executing possible hacking attacks. Doing so automatically allows for regular and systematic testing. A key question is how to generate the attacks. This is naturally formulated as planning under uncertainty, i.e., under incomplete knowledge about the network configuration. Previous work uses classical planning, and requires costly pre-processes reducing this uncertainty by extensive application of scanning methods. By contrast, we herein model the attack planning problem in terms of partially observable Markov decision processes (POMDP). This allows to reason about the knowledge available, and to intelligently employ scanning actions as part of the attack. As one would expect, this accurate solution does not scale. We devise a method that relies on POMDPs to find good attacks on individual machines, which are then composed into an attack on the network as a whole. This decomposition exploits network structure to the extent possible, making targeted approximations (only) where needed. Evaluating this method on a suitably adapted industrial test suite, we demonstrate its effectiveness in both runtime and solution quality.