مرکز منطقه ای اطلاع رسانی علوم و فناوری فصلنامه مهندسی برق و مهندسی کامپيوتر ايران 16823745 5 4 2007 12 21 Analyzing Weighted Attack Graphs Using Genetic Algorithms تحليل گراف‌هاي حمله وزن‌دار با استفاده از الگوريتم‌هاي ژنتيك 189 202 fa مهدی آبادی سعيد جليلي 2006 5 9 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. هر گراف‌ حمله مجموعه‌اي از سناريوهاي نفوذ به يک شبکه کامپيوتري را نمايش مي‌دهد. در اين مقاله، از گراف‌هاي حمله وزن‌دار براي تحليل آسيب‌پذيري شبكه‌هاي كامپيوتري استفاده مي‌شود. در اين گراف‌هاي حمله به هر سوءاستفاده توسط تحليل‌گر وزني نسبت داده مي‌شود. وزن نسبت داده شده به هر سوءاستفاده متناسب با هزينه لازم براي جلوگيري از آن سوءاستفاده است. هدف از تحليل گراف‌هاي حمله وزن‌دار يافتن يك مجموعه بحراني از سوءاستفاده‌ها است که مجموع وزن‌هاي آنها کمترين مقدار ممکن باشد و با جلوگيري از آنها هيچ سناريوي نفوذي امکان‌پذير نباشد. در اين مقاله، يك الگوريتم حريصانه، يك الگوريتم ژنتيك با عملگر جهش حريصانه و يك الگوريتم ژنتيك با تابع برازندگي پويا براي تحليل گراف‌هاي حمله وزن‌دار پيشنهاد مي‌شود. از الگوريتم‌هاي پيشنهادي براي تحليل گراف حمله وزن‌دار يك شبکه مثالي و چندين گراف حمله وزن‌دار مقياس بزرگ استفاده مي‌شود. نتايج بدست آمده از آزمایش‌ها، عملكرد بهتر الگوريتم‌هاي ژنتيك پيشنهادي را نسبت به الگوريتم حريصانه نشان مي‌دهند به گونه‌اي كه الگوريتم‌هاي ژنتيك فوق قادر هستند مجموعه‌هاي بحراني از سوءاستفاده‌ها با مجموع وزن‌هاي كمتر را پيدا كنند. همچنين، از الگوريتم ژنتيك با تابع برازندگي پويا براي تحليل چندين گراف‌ حمله ساده مقياس بزرگ استفاده مي‌شود و عملكرد آن با يك الگوريتم تقريبي براي تحليل گراف‌هاي حمله ساده مقايسه مي‌شود. http://ijece.org/ar/Article/Download/27883