Document Type: ORIGINAL RESEARCH PAPER

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

[1] S. Jajodia, S. Noel, and B. O'Berry. Topological Analysis of Network Attack Vulnerability. In V. Kumar, J. Srivastava, and A. Lazarevic, editors, *Managing Cyber Threats: Issues, Approaches, and Challenges,* pages 247-266. Springer, New York, NY, USA, 2005.

[2] M. Abadi and S. Jalili. Minimization Analysis of Network Attack Graphs Using Genetic Algorithms. *International Journal of Computers and Their Applications (IJCA),* 15(4):263-273, 2008.

[3] J. Kennedy and R. C. Eberhart. Particle Swarm Optimization. In *Proceedings of the IEEE International Joint Conference on Neural Networks, *pages 1942- 1948, Perth, Australia, 1995.

[4] C. Phillips and L. P. Swiler. A Graph-based System for Network-Vulnerability Analysis. In *Proceedings of the New Security Paradigms Workshop,* pages 71-79, Charlottesville, VA, USA, 1998.

[5] J. M. Wing. Attack Graph Generation and Analysis. In *Proceedings of the ACM Symposium on Information, Computer and Communications Security,* page 14, Taipei, Taiwan, 2006.

[6] O. Sheyner, J. W. Haines, S. Jha, R. Lippmann, and J. M. Wing. Automated Generation and Analysis of Attack Graphs. In *Proceedings of the IEEE Symposium on Security and Privacy,* pages 273-284, Berkeley, CA, USA, 2002.

[7] NuSMV. NuSMV: A New Symbolic Model Checker. http://afrodite.itc.it:1024/~nusmv.

[8] P. Ammann, D. Wijesekera, Kaushik, and S. Scalable, Graph-based Network Vulnerability Analysis. In *Proceedings of the 9th ACM Conference on Computer and Communications Security,* pages 217-224, Washington, DC, USA, 2002.

[9] S. Noel, M. Jacobs, P. Kalapa, and S. Jajodia. Multiple Coordinated Views for Network Attack Graphs. In *Proceedings of the IEEE Workshop on Visualization for Computer Security (VizSEC 2005),* pages 99-106, Minneapolis, MN, USA, 2005.

[10] V. Mehta, C. Bartzis, H. Zhu, E. M. Clarke, and J. M. Wing. Ranking Attack Graphs. In *Proceedings of the 9th International Symposium on Recent Advances in Intrusion Detection (RAID 2006),* pages 127-144, Hamburg, Germany, 2006.

[11] S. Noel, S. Jajodia, B. O'Berry, and M. Jacobs. Efficient Minimum-Cost Network Hardening via Exploit Dependency Graphs. In *Proceedings of the 19th Annual Computer Security Applications Conference,* pages 86-95, Las Vegas, NV, USA, 2003.

[12] L. Wang, S. Noel, and S. Jajodia. Minimum-Cost Network Hardening Uusing Attack Graphs. *Computer Communications,* 29(18):3812-3824, 2006.

[13] X. Ou, W. F. Boyer, and M. A. McQueen. A Scalable Approach to Attack Graph Generation. In *Proceedings of the 13 ^{th} ACM Conference on Computer and Communications Security (CCS 2006),* pages 336-345, Alexandria, VA, USA, 2006.

[14] X. Ou, S. Govindavajhala, and A. W. Appel. MulVAL: A Logic-based Network Security Analyzer. In *Proceedings of the 14th Conference on USENIX Security Symposium, *page 8, Baltimore, MD, USA, 2005.

[15] S. Jha, O. Sheyner, and J. Wing. Minimization and Reliability Analysis of Attack Graphs. Technical report, CMU-CS-02-109, School of Computer Science, Carnegie Mellon University, 2002.

[16] S. Jha, O. Sheyner, and J. M. Wing. Two Formal Analyses of Attack Graphs. In *Proceedings of the 15 ^{th} IEEE Computer Security Foundations Workshop, *pages 49-63, Cape Breton, Nova Scotia, Canada, 2002.

[17] M. Abadi and S. Jalili. Using Binary Particle Swarm Optimization for Minimization Analysis of Large-Scale Network Attack Graphs. *Journal of Scientia Iranica, *15(6):605-619, 2008.

[18] J. Kennedy, R. C. Eberhart, and Y. Shi. *Swarm Intelligence*. Morgan Kaufmann, San Mateo, CA, USA, 2001.

[19] R. C. Eberhart, P. Simpson, and R. Dobbins. *Computational Intelligence* *PC Tools.* Academic Press Professional, San Diego, CA, USA, 1996.

[20] Y. Shi. Particle Swarm Optimization*. IEEE Connections,* 2(1):8-13, 2004.

[21] J. Kennedy and R. C. Eberhart. A Discrete Binary Version of the Particle Swarm Algorithm. In *Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics,* pages 4104-4109, Orlando, FL, USA, 1997.

[22] A. P. Engelbrecht. *Fundamentals of Computational Swarm Intelligence. John Wiley & Sons,* Hoboken, NJ, USA, 2005.

[23] R. Deraison. Nessus Scanner. http://www.nessus.org.

[24] Y. Shi and R. C. Eberhart. Empirical Study of Particle Swarm Optimization. In *Proceedings of the IEEE Congress on Evolutionary Computation, *pages 1945-1950, Washington, DC, USA, 1999.

[25] T. Hendtlass and M. Randall. A Survey of Ant Colony and Particle Swarm Meta-Heuristics and Their Application to Discrete Optimization Problems. In *Proceedings of the Inaugural Workshop on Artificial Life,* pages 15-25, Adelaide, Australia, 2001.

[26] D. Braendler and T. Hendtlass. The Suitability of Particle Swarm Optimisation for Training Neural Hardware. In *Proceedings of the 15 ^{th} International Conference on Industrial and Engineering, Applications of Artificial Intelligence and Expert Systems,* pages 190-199, Cairns, Australia, 2002.

[27] A. E. Eiben and J. E. Smith. *Introduction to Evolutionary Computing. *Springer-Verlag, Berlin, Germany, 2003.

[28] N. Krasnogor, A. Aragon, and J. Pacheco. Memetic Algorithms. In E. Alba and R. Mart, editors, *Metaheuristic Procedures for Training Neural Networks,* pages 225-248. Springer-Verlag, Berlin, Germany, 2006.

[29] NVD: National Vulnerability Database. http://nvd.nist.gov/.

[30] P. Ammann, J. Pamula, R. Ritchey, and J. Street. A Host-Based Approach to Network Attack Chaining Analysis. In *Proceedings of the Annual Computer Security Applications Conference (AC-SAC05),* pages 72-84, Tucson, AZ, USA, 2005.