  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.
