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.