Analyzing Weighted Attack Graphs Using Genetic Algorithms

Each attack graph represents a collection of possible attack scenarios in a computer network. In this paper, we use weighted attack graphs (WAGs) for vulnerability assessment of computer networks. In these directed graphs, a weight is assigned to each exploit by the security analyst. The weight of an exploit is proportionate to the cost required to prevent that exploit. The aim of analyzing a weighted attack graph is to find a critical set of exploits such that the sum of their weights is minimum and by preventing them no attack scenario is possible. In this paper, we propose a greedy algorithm, a genetic algorithm with a greedy mutation operator, and a genetic algorithm with a dynamic fitness function for analyzing the weighted attack graphs. The proposed algorithms are used to analyze a sample weighted attack graph and several randomly generated large-scale weighted attack graphs. The results of experiments show that the proposed genetic algorithms outperform the greedy algorithm and find a critical set of exploits with less total weight. Finally, we compare the performance of the second genetic algorithm with an approximation algorithm for analyzing several randomly generated large-scale simple attack graphs. The results of experiments show that our proposed genetic algorithm has better performance than the approximation algorithm and finds a critical set of exploits with less cardinality.