Applying Genetic Algorithms for Minimization Analysis of Network Attack Graphs

Each attack scenario is a sequence of exploits launched by an intruder for a particular goal such as access to a database, service disruption, and so on. The collection of possible attack scenarios in a computer network can be represented by a directed graph, which is called network attack graph. In this directed graph, each path from an initial node to a goal node corresponds to an attack scenario. The aim of minimization analysis of network attack graphs is to find a minimum critical set of exploits that must be prevented to guarantee no attack scenario is possible. In this paper, we propose a genetic algorithm for minimization analysis of network attack graphs. A special dynamic fitness function has been used to improve the overall performance of the proposed genetic algorithm. We also report the results of applying this genetic algorithm for minimization analysis of a sample network attack graph consisting of 164 attack scenarios. The results of experiments show that our proposed genetic algorithm can be successfully used for minimization analysis of network attack graphs.