@article { author = {Abadi, M. and Jalili, S.}, title = {A particle swarm optimization algorithm for minimization analysis of cost-sensitive attack graphs}, journal = {The ISC International Journal of Information Security}, volume = {2}, number = {1}, pages = {13-32}, year = {2010}, publisher = {Iranian Society of Cryptology}, issn = {2008-2045}, eissn = {2008-3076}, doi = {10.22042/isecure.2015.2.1.3}, abstract = {To prevent an exploit, the security analyst must implement a suitable countermeasure. 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. There may be multiple countermeasures with different weights for preventing a single exploit. Also, a single countermeasure may prevent multiple exploits. We present a binary particle swarm optimization algorithm with a time-varying velocity clamping, called SwarmCAG-TVVC, for minimization analysis of cost-sensitive attack graphs. The aim is to find 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 problem is in fact a constrained optimization problem. A repair method is used to convert the constrained optimization problem into an unconstrained one. A local search heuristic is used to improve the overall performance of the algorithm. We compare the performance of SwarmCAG-TVVC with a greedy algorithm GreedyCAG 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 is 6.15 percent less than the weight of a critical set of countermeasures found by GreedyCAG. Also, SwarmCAG-TVVC performs better than GenNAG in terms of convergence speed and accuracy. The results of the experiments show that SwarmCAG-TVVC can be successfully used for minimization analysis of large-scale cost-sensitive attack graphs.}, keywords = {Particle Swarm Optimization,Attack Scenario,Countermeasure,Cost-Sensitive Attack Graph,Minimization Analysis}, url = {https://www.isecure-journal.com/article_39174.html}, eprint = {https://www.isecure-journal.com/article_39174_46dabfb15e3074fa1a9201bf15ccbbd6.pdf} }