Document Type : Research Article

**Authors**

**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**

*Managing Cyber Threats: Issues, Approaches, and Challenges,*pages 247-266. Springer, New York, NY, USA, 2005.

*International Journal of Computers and Their Applications (IJCA),*15(4):263-273, 2008.

*Proceedings of the IEEE International Joint Conference on Neural Networks,*pages 1942- 1948, Perth, Australia, 1995.

*Proceedings of the New Security Paradigms Workshop,*pages 71-79, Charlottesville, VA, USA, 1998.

*Proceedings of the ACM Symposium on Information, Computer and Communications Security,*page 14, Taipei, Taiwan, 2006.

*Proceedings of the IEEE Symposium on Security and Privacy,*pages 273-284, Berkeley, CA, USA, 2002.

*Proceedings of the 9th ACM Conference on Computer and Communications Security,*pages 217-224, Washington, DC, USA, 2002.

*Proceedings of the IEEE Workshop on Visualization for Computer Security (VizSEC 2005),*pages 99-106, Minneapolis, MN, USA, 2005.

*Proceedings of the 9th International Symposium on Recent Advances in Intrusion Detection (RAID 2006),*pages 127-144, Hamburg, Germany, 2006.

*Proceedings of the 19th Annual Computer Security Applications Conference,*pages 86-95, Las Vegas, NV, USA, 2003.

*Computer Communications,*29(18):3812-3824, 2006.

*Proceedings of the 13*pages 336-345, Alexandria, VA, USA, 2006.

^{th}ACM Conference on Computer and Communications Security (CCS 2006),*Proceedings of the 14th Conference on USENIX Security Symposium,*page 8, Baltimore, MD, USA, 2005.

*Proceedings of the 15*pages 49-63, Cape Breton, Nova Scotia, Canada, 2002.

^{th}IEEE Computer Security Foundations Workshop,*Journal of Scientia Iranica,*15(6):605-619, 2008.

*Swarm Intelligence*. Morgan Kaufmann, San Mateo, CA, USA, 2001.

*Computational Intelligence*

*PC Tools.*Academic Press Professional, San Diego, CA, USA, 1996.

*. IEEE Connections,*2(1):8-13, 2004.

*Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics,*pages 4104-4109, Orlando, FL, USA, 1997.

*Fundamentals of Computational Swarm Intelligence. John Wiley & Sons,*Hoboken, NJ, USA, 2005.

*Proceedings of the IEEE Congress on Evolutionary Computation,*pages 1945-1950, Washington, DC, USA, 1999.

*Proceedings of the Inaugural Workshop on Artificial Life,*pages 15-25, Adelaide, Australia, 2001.

*Proceedings of the 15*pages 190-199, Cairns, Australia, 2002.

^{th}International Conference on Industrial and Engineering, Applications of Artificial Intelligence and Expert Systems,*Introduction to Evolutionary Computing.*Springer-Verlag, Berlin, Germany, 2003.

*Metaheuristic Procedures for Training Neural Networks,*pages 225-248. Springer-Verlag, Berlin, Germany, 2006.

*Proceedings of the Annual Computer Security Applications Conference (AC-SAC05),*pages 72-84, Tucson, AZ, USA, 2005.