A Genetic Algorithm Approach for the Most Likely Attack Path Problem

Security attack path analysis has become attractive as a security risk assessment technique that represents vulnerabilities in a network. This paper presents a genetic algorithm approach to find the most likely attack paths in attack graphs. We provide an effective approach to network administrators by showing the paths and steps that attackers will most probably exploit to achieve a specific target. The use of a genetic algorithm is particularly appropriate as it offers a straight-forward approach and, most importantly, a range of solutions. This latter point differs from other approaches which concentrate on a singly most likely path and may ignore other important attack vectors. The paper shows how a genetic algorithm can be developed such that feasible individuals are maintained at each stage by selecting certain attack graph vertices to be the crossover and mutation sites.