Decomposing the Network to perform Attack Planning under Uncertainty presented at Hackito Ergo Sum 2012

by Carlos Sarraute,

Tags: Formal Methods Attack Planning


Summary : As penetration testing tools have evolved and have become more complex, the problem of controlling these tools successfully has become 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, and contribute to making the assessment of network security more accessible to non-expert users. This issue can be addressed as an attack planning problem. In this talk, I will discuss some ideas to deal with the uncertainty regarding the target machines about the details of their operating system and running applications, which have a direct influence on the results of the exploits. Planning under uncertainty is more complex, since decisions must be taken based on beliefs about the target machines (and the belief space is infinite!) So there is naturally a tension between two directions: (i) to improve the realism and expressivity of the model and (ii) to improve the performance of the planner and make something actually useful in practice. I will present results obtained in both directions, some of them in collaboration with INRIA (Nancy, France). We have developed new algorithms that exploit the network structure: we decompose the network connectivity graph into logical components, and we approximate the attacks on these components by combining attacks on individual machines. The attacks on individual machines are modeled and solved as partially observable Markov decision processes (POMDP). This new method allows us to retain the expressivity of the POMDP model while making the solution scale to real-life networks.