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

The aim of the minimization analysis of network attack graphs (nags) is to find a minimumcritical set of exploits so that by preventing them an intruder cannot reach his goal usingany attack scenario. this problem is, in fact, a constrained optimization problem. in thispaper, a binary particle swarm optimization algorithm, called swarmnag, is presented for theminimization analysis of large-scale network attack graphs. a penalty function method with atime-varying penalty coefficient is used to convert the constrained optimization problem intoan unconstrained problem. also, a time-varying velocity clamping, a greedy mutation operatorand a local search heuristic are used to improve the overall performance of the algorithm. theperformance of the swarmnag is compared with that of an approximation algorithm for theminimization analysis of several large-scale network attack graphs. the results of the experimentsshow that the swarmnag outperforms the approximation algorithm and finds a critical set ofexploits with less cardinality.