Analyzing Weighted Attack Graphs Using Genetic Algorithms
Subject Areas : electrical and computer engineeringKeywords: Weighted attack graphattack scenarioexploitnetwork vulnerability assessmentgenetic algorithms,
Abstract :
Each attack graph represents a collection of possible attack scenarios in a computer network. In this paper, we use weighted attack graphs (WAGs) for vulnerability assessment of computer networks. In these directed graphs, a weight is assigned to each exploit by the security analyst. The weight of an exploit is proportionate to the cost required to prevent that exploit. The aim of analyzing a weighted attack graph is to find a critical set of exploits such that the sum of their weights is minimum and by preventing them no attack scenario is possible. In this paper, we propose a greedy algorithm, a genetic algorithm with a greedy mutation operator, and a genetic algorithm with a dynamic fitness function for analyzing the weighted attack graphs. The proposed algorithms are used to analyze a sample weighted attack graph and several randomly generated large-scale weighted attack graphs. The results of experiments show that the proposed genetic algorithms outperform the greedy algorithm and find a critical set of exploits with less total weight. Finally, we compare the performance of the second genetic algorithm with an approximation algorithm for analyzing several randomly generated large-scale simple attack graphs. The results of experiments show that our proposed genetic algorithm has better performance than the approximation algorithm and finds a critical set of exploits with less cardinality.
[1] م. آبادي و س. جليلي، "کشف سناريوهاي نفوذ به شبکههاي کامپيوتري با استفاده از بررسيکننده مدل SPIN،" مجموعه مقالات سومين كنفرانس رمز ايران، دانشگاه صنعتي اصفهان، صص. 305-294، شهريور ماه 138۴.
[2] C. Ramakrishnan and R. Sekar, "Model-based vulnerability analysis of computer systems," in Proc. 2nd Int. Workshop on Verification, Model Checking and Abstract Interpretation, pp. 1-8, Sep. 1998.
[3] C. A. Phillips and L. P. Swiler, "A graph-based system for network vulnerability analysis," in Proc. 1998 New Security Paradigms Workshop, pp. 71-79, Charlottesville, US, Sep. 1998.
[4] O. Sheyner, Scenario Graphs and Attack Graphs, Ph.D. Thesis, Carnegie Mellon University, Apr. 2004.
[5] P. Ammann, D. Wijesekera, and S. Kaushik, "Scalable, graph-based network vulnerability analysis," in Proc. 9th ACM Conf. on Computer and Communications Security, pp. 217-224, Washington DC, US, Nov. 2002.
[6] O. Sheyner, J. Haines, S. Jha, R. Lippmann, and J. M. Wing, "Automated generation and analysis of attack graphs," in Proc. IEEE Symposium on Security and Privacy, pp. 273-284, Oakland, US, May 2002.
[7] NuSMV: A New Symbolic Model Checker. http://nusmv.irst.itc.it/.
[8] S. Noel and S. Jajodia, "Managing attack graph complexity through visual hierarchical aggregation," in Proc. ACM CCS Workshop on Visualization and Data Mining for Computer Security, pp. 109-118, Washington DC, US, Oct. 2004.
[9] S. Noel, M. Jacobs, P. Kalapa, and S. Jajodia, "Multiple coordinated views for network attack graphs," in Proc. IEEE Workshop on Visualization for Computer Security, pp. 99-106, Minneapolis, US, Oct. 2005.
[10] S. Jha, O. Sheyner, and J. M. Wing, "Two formal analyses of attack graphs," in Proc. 15th IEEE Computer Security Foundations Workshop, pp. 49-63, Nova Scotia, Canada, Jun. 2002.
[11] M. Abadi and S. Jalili, "Applying genetic algorithms for minimization analysis of network attack graphs," in Proc. 11th Int. CSI Computer Conf., pp. 133-139, Tehran, Jan. 2006.
[12] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley, Reading, MA, 1989.
[13] K. A. De Jong, Evolutionary Computation: A Unified Approach, MIT Press, Cambridge, MA, 2006.
[14] M. Mitchell, An Introduction to Genetic Algorithms, MIT Press, Cambridge, MA, 1999.
[15] R. Deraison, Nessus Scanner. http://www.nessus.org.
[16] Common Vulnerabilities and Exposures. http://www.cve.mitre.org.
[17] P. Ammann, J. Pamula, R. Ritchey, and J. Street, "A host-based approach to network attack chaining analysis," in Proc. Annual Computer Security Applications Conf., pp. 72-84, Tucson, US, Dec. 2005.