An algorithm to find optimal attack paths in nondeterministic scenarios

As penetration testing frameworks have evolved and have become more complex, the problem of controlling automati-cally the pentesting tool has become an important question. This can be naturally addressed as an attack planning prob-lem. Previous approaches to this problem were based on modeling the actions and assets in the PDDL language, and using off-the-shelf AI tools to generate attack plans. These approaches however are limited. In particular, the plan-ning is classical (the actions are deterministic) and thus not able to handle the uncertainty involved in this form of at-tack planning. We herein contribute a planning model that does capture the uncertainty about the results of the ac-tions, which is modeled as a probability of success of each action. We present efficient planning algorithms, specifically designed for this problem, that achieve industrial-scale run-time performance (able to solve scenarios with several hun-dred hosts and exploits). 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 traffic generated). We thus show that probabilistic attack planning can be solved efficiently for the scenarios that arise when assessing the security of large networks. Two “prim-itives ” are presented, which are used as building blocks in a framework separating the overall problem into two levels of abstraction. We also present the experimental results ob-tained with our implementation, and conclude with some ideas for further work