New Algorithms for Attack Planning

New Algorithms for Attack Planning

Monday, September 7, 2009
Carlos Sarraute
FRHACK Conference

We have presented the advances of our research in automating multi-step attacks against computer networks. Planning in the probabilistic setting is far more difficult than in the deterministic one, and it is the specific problem that we tackled in this presentation. We presented fast algorithms designed for probabilistic planning of multi-step attacks, in order to minimize an attack parameter (e.g. the expected execution time). Our solution is suited for an interesting (and significant) part of the scenarios that need to be solved in a real world attack. The computational complexity of our solution is O(n log n), where n is the total number of actions in the graph. This means that planning can be solved in scenarios with, for example, 512 hosts distributed in different networks, and 840 exploits in the attacker's toolbox.

The proposed algorithms were presented gradually, starting with scenarios with one target and multiple exploits, and moving on to scenarios made of arbitrary attack trees. Proofs that the algorithms provide an optimal attack plan were sketched in each case.

Related information

Attack Planning | Attack Simulation

Building Computer Network Attacks | A Penetration Testing Learning Kit | Advances in Automated Attack Planning