Finding the minimum cut set in attack graphs using genetic algorithms

Abstract

Attack graphs are useful tools to both display possible attack vectors in simple systems and as an analysis tool for more complex systems. This paper considers the latter case and how an attack graph can be used to minimize the cost of deploying countermeasures. Specifically we develop an approach to find the minimum cut set in dependency attack graphs using a genetic algorithm (GA). The minimum cut set is a natural graph representation describing a set of security countermeasures that prevent attackers reaching their targets. The work shows that the problem maps naturally to a binary encoded GA and gives satisfactory results without the need to deploy problem specific GA operators.