The ISC International Journal of Information Security ISSN: 2008-3076 (Online Edition)         2008-2045 (Paper Edition) Content Log In Register Description Editorial Board Review Process Author Guide Call For Paper Contact Info Poster PDF Link: Article-ISeCure-09-052.pdf Title: A Particle Swarm Optimization Algorithm for Minimization Analysis of Cost-Sensitive Attack Graphs   Author(s): Mahdi Abadi, Saeed Jalili (Faculty of Electrical and Computer Engineering, Tarbiat Modares University, Tehran, Iran)   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   Bibtex @article{ ISeCure-09-052, Author = {Mahdi Abadi, Saeed Jalili}, Title = {A Particle Swarm Optimization Algorithm for Minimization Analysis of Cost-Sensitive Attack Graphs}, Journal = {ISeCure, The ISC International Journal of Information Security}, Volume = {2}, Number = {1}, Pages = {13--32}, Year = {2010} }   Copyright 2007-2010 © ISC. All Rights Reserved