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 present 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 a French research institute, and also discuss open problems that stem from this research.