Abadi, M., Jalili, S. (2010). A particle swarm optimization algorithm for minimization analysis of cost-sensitive attack graphs. The ISC International Journal of Information Security, 2(1), 13-32. doi: 10.22042/isecure.2015.2.1.3

M. Abadi; S. Jalili. "A particle swarm optimization algorithm for minimization analysis of cost-sensitive attack graphs". The ISC International Journal of Information Security, 2, 1, 2010, 13-32. doi: 10.22042/isecure.2015.2.1.3

Abadi, M., Jalili, S. (2010). 'A particle swarm optimization algorithm for minimization analysis of cost-sensitive attack graphs', The ISC International Journal of Information Security, 2(1), pp. 13-32. doi: 10.22042/isecure.2015.2.1.3

Abadi, M., Jalili, S. A particle swarm optimization algorithm for minimization analysis of cost-sensitive attack graphs. The ISC International Journal of Information Security, 2010; 2(1): 13-32. doi: 10.22042/isecure.2015.2.1.3

A particle swarm optimization algorithm for minimization analysis of cost-sensitive attack graphs

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.

[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 IntelligencePC 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.