Mahdi Abadi - Department of Computer Engineering Tarbiat Modares University
Saeed Jalili - Department of Computer Engineering Tarbiat Modares University

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.

Network Attack Graph, Attack Scenario, Genetic Algorithm, Minimization Analysis