Encounters of the Third Kind between Pen Testing and Automated Planning

Encounters of the Third Kind between Pen Testing and Automated Planning

Sunday, July 22, 2012
Carlos Sarraute, Ken Pickering
Workshop on Problem Solving using Classical Planners (CP4PS) at AAAI 2012 Conference.

Penetration Testing (in short pen testing) is a methodology for assessing network security, by generating and executing possible hacking attacks. As pentesting tools have evolved and have become more complex, covering new attack vectors, and shipping an increasing number of exploits, the problem of controlling the pentesting solution successfully became an important question. A computer-generated plan for an attack would isolate the user from the complexity of selecting suitable exploits for the hosts in the target network. Additionally, the possibility of incorporating an attack planning phase to the tool would allow for optimizations based on exploit running time, reliability, or impact on Intrusion Detection Systems.

In this talk, we will discuss the difficulties of solving this attack planning problem, and present the first industrial-scale solution that we obtained by integrating our pentesting tool with a classical planner. The basic idea was to model the actions available in the pentesting tool (namely exploits) and the information about the target network (machines, connectivity, operating systems, and running applications) in the PDDL language. This PDDL model allowed us to evaluate different planners until we decided to use Metric-FF (developed by Jörg Hoffman), based on its performance. As a result, we were able to obtain plans that minimize the average runtime of the attacks in real-world scenarios.

This integration raised interesting issues from an engineering perspective, such as: (i) optimizations to deal with increasingly larger problem sets with more criteria; (ii) "replanning": having a planner able to reshape graphs on the fly as data is updated, without complete regeneration; and (iii) expanding security metrics and threat modeling to account for new attack vectors.

We will also present two research directions that arose from this work: (i) add information about the exploits' probability of success, and develop a custom probabilistic planner for this problem; and (ii) model pentesting under uncertainty in terms of POMDPs, thus grounding penetration testing in a well-researched formalism. By using off-the-shelf POMDP solvers and a decomposition algorithm that exploits the network structure, we obtained a solution that scales while improving the expressivity of the model and the quality of the plans.