A Particle Swarm Optimization Algorithm For Minimization Analysis of Cost-Sensitiveattack Graphs

To prevent an exploit, the security analyst must implement a suitablecountermeasure. in this paper, we consider cost-sensitive attack graphs (cags)for network vulnerability analysis. in these attack graphs, a weight is assigned to each countermeasure to represent the cost of its implementation. theremay be multiple countermeasures with different weights for preventing a singleexploit. also, a single countermeasure may prevent multiple exploits. wepresent a binary particle swarm optimization algorithm with a time-varyingvelocity clamping, called swarm cag-tvvc, for minimization analysis of cost-sensitive attack graphs. the aim is to nd a critical set of countermeasures with minimum weight whose implementation causes the initial nodes and the goal nodes of the graph to be completely disconnected. this problemis in fact a constrained optimization problem. a repair method is used toconvert the constrained optimization problem into an unconstrained one.a local search heuristic is used to improve the overall performance of thealgorithm. we compare the performance of swarmcag-tvvc with a greedy algorithm greedy cag and a genetic algorithm gennag for minimization analysis of several large-scale cost-sensitive attack graphs. on average, the weight of a critical set of countermeasures found by swarmcag-tvvc is6:15 percent less than the weight of a critical set of countermeasures foundby greedy cag. also, swarmcag-tvvc performs better than gennag interms of convergence speed and accuracy. the results of the experiments showth at swarm cag-tvvc can be successfully used for minimization analysis of large-scale cost-sensitive attack graphs.