تحليل گراف‌هاي حمله وزن‌دار با استفاده از الگوريتم‌هاي ژنتيك
محورهای موضوعی : مهندسی برق و کامپیوتر
1 - دانشگاه تربيت مدرس
2 - دانشگاه تربيت مدرس
کلید واژه: الگوريتم ژنتيکتحليل آسيب‌پذيري شبكهسناريوي نفوذسوءاستفادهگراف حمله وزن‌دار,
چکیده مقاله :
هر گراف حمله مجموعه‌اي از سناريوهاي نفوذ به يک شبکه کامپيوتري را نمايش مي‌دهد. در اين مقاله، از گراف‌هاي حمله وزن‌دار براي تحليل آسيب‌پذيري شبكه‌هاي كامپيوتري استفاده مي‌شود. در اين گراف‌هاي حمله به هر سوءاستفاده توسط تحليل‌گر وزني نسبت داده مي‌شود. وزن نسبت داده شده به هر سوءاستفاده متناسب با هزينه لازم براي جلوگيري از آن سوءاستفاده است. هدف از تحليل گراف‌هاي حمله وزن‌دار يافتن يك مجموعه بحراني از سوءاستفاده‌ها است که مجموع وزن‌هاي آنها کمترين مقدار ممکن باشد و با جلوگيري از آنها هيچ سناريوي نفوذي امکان‌پذير نباشد. در اين مقاله، يك الگوريتم حريصانه، يك الگوريتم ژنتيك با عملگر جهش حريصانه و يك الگوريتم ژنتيك با تابع برازندگي پويا براي تحليل گراف‌هاي حمله وزن‌دار پيشنهاد مي‌شود. از الگوريتم‌هاي پيشنهادي براي تحليل گراف حمله وزن‌دار يك شبکه مثالي و چندين گراف حمله وزن‌دار مقياس بزرگ استفاده مي‌شود. نتايج بدست آمده از آزمایش‌ها، عملكرد بهتر الگوريتم‌هاي ژنتيك پيشنهادي را نسبت به الگوريتم حريصانه نشان مي‌دهند به گونه‌اي كه الگوريتم‌هاي ژنتيك فوق قادر هستند مجموعه‌هاي بحراني از سوءاستفاده‌ها با مجموع وزن‌هاي كمتر را پيدا كنند. همچنين، از الگوريتم ژنتيك با تابع برازندگي پويا براي تحليل چندين گراف حمله ساده مقياس بزرگ استفاده مي‌شود و عملكرد آن با يك الگوريتم تقريبي براي تحليل گراف‌هاي حمله ساده مقايسه مي‌شود.
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.