The ISC International Journal of Information Security

Current Issue

By Issue

By Author

By Subject

Author Index

Keyword Index

About Journal

Aims and Scope

Editorial Board

Editorial Staff

Publication Ethics and Malpractice Statement

Indexing and Abstracting

Related Links

FAQ

Peer Review Process

News

Sponsors

Journal Metrics

Reviewers

Review Guide in Publons

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

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

Optional file type 1
[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 13th 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 15th 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 15th 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.
The ISC International Journal of Information Security
Volume 2, Issue 1 - Serial Number 1
15
January 2010
Pages 13-32
Files
Share
How to cite
Statistics