  Penetration Testing is a methodology for assessing network security, by
generating and executing possible attacks. Doing so automatically allows for
regular and systematic testing without a prohibitive amount of human labor. A
key question then is how to generate the attacks. This is naturally formulated
as a planning problem. Previous work (Lucangeli et al. 2010) used classical
planning and hence ignores all the incomplete knowledge that characterizes
hacking. More recent work (Sarraute et al. 2011) makes strong independence
assumptions for the sake of scaling, and lacks a clear formal concept of what
the attack planning problem actually is. Herein, we model that problem in terms
of partially observable Markov decision processes (POMDP). This grounds
penetration testing in a well-researched formalism, highlighting important
aspects of this problem's nature. POMDPs allow to model information gathering
as an integral part of the problem, thus providing for the first time a means
to intelligently mix scanning actions with actual exploits.
