Using Binary Particle Swarm Optimization for Minimization Analysis of Large-Scale Network Attack Graphs


Department of Computer Engineering,Tarbiat Modares University


The aim of the minimization analysis of network attack graphs (NAGs) is to nd a minimum
critical set of exploits so that by preventing them an intruder cannot reach his goal using
any attack scenario. This problem is, in fact, a constrained optimization problem. In this
paper, a binary particle swarm optimization algorithm, called SwarmNAG, is presented for the
minimization analysis of large-scale network attack graphs. A penalty function method with a
time-varying penalty coecient is used to convert the constrained optimization problem into
an unconstrained problem. Also, a time-varying velocity clamping, a greedy mutation operator
and a local search heuristic are used to improve the overall performance of the algorithm. The
performance of the SwarmNAG is compared with that of an approximation algorithm for the
minimization analysis of several large-scale network attack graphs. The results of the experiments
show that the SwarmNAG outperforms the approximation algorithm and nds a critical set of
exploits with less cardinality.