Automated attack planning

"Penetration Testing (short pentesting) is a methodology for assessing network security, by generating and executing possible attacks exploiting known vulnerabilities of operating systems and applications. Doing so automatically allows for regular and systematic testing without a prohibitive amount of human labor, and makes pentesting more accessible to non-experts. A key question then is how to automatically generate the attacks. A natural way to address this issue is as an attack planning problem. In this thesis, we are concerned with the specific context of regular automated pentesting, and use the term \attack planning" in that sense. The following three research directions are investigated. First, we introduce a conceptual model of computer network attacks, based on an analysis of the penetration testing practices. We study how this attack model can be represented in the PDDL language. Then we describe an implementation that integrates a classical planner with a penetration testing tool. This allows us to automatically generate attack paths for pentesting scenarios, and to validate these attacks by executing the corresponding actions -including exploits- against the real target network. We also present another tool that we developed in order to effectively test the output of the planner: a simulation platform created to design and simulate cyber-attacks against large arbitrary target scenarios. Secondly, we present a custom probabilistic planner. In this part, we contribute a planning model that captures the uncertainty about the results of the actions, which is modeled as a probability of success of each action. We present efficient planning algorithms, specifically designed for this problem, that achieve industrialscale runtime performance (able to solve scenarios with several hundred hosts and exploits). Proofs are given that the solutions obtained are optimal under certain assumptions. These algorithms take into account the probability of success of the actions and their expected cost (for example in terms of execution time, or network track generated). Finally, we take a different direction: instead of trying to improve the efficiency of the solutions developed, we focus on improving the model of the attacker. We model the attack planning 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 the modelling of 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." Tesis Ingeniería Informática (doctorado) - Instituto Tecnológico de Buenos Aires, Buenos Aires, 2012