評估單目標的攻擊圖自動構建方法SGA-AGC

◆張漢卿

（河北外國語職業學院 河北 066311）

評估單目標的攻擊圖自動構建方法SGA-AGC

◆張漢卿

（河北外國語職業學院 河北 066311）

本文提出了評估單目標的攻擊圖自動構建方法SGA-AGC（Single Goal Assessment-Attack Graph Construction）。實驗結果表明：搜索深度最大值對算法的影響最大，然后依次是目標網絡系統中主機數量、每臺主機最多擁有的脆弱性數量和原子攻擊數量，本文算法的性能優于文獻[4]和文獻[5]中的算法。

計算機網絡；單目標；攻擊圖

0 引言

通過分析現有構建方法的不足，根據現實應用的安全需求，本文給出了一種自動構建攻擊圖的方法：評估單目標的攻擊圖自動構建方法SGA-AGC。SGA-AGC方法將正向攻擊圖生成算法和反向攻擊圖生成算法結合起來，采用多線程的方法，同時從攻擊者的初始位置和攻擊者的攻擊目標出發進行分析，即正向搜索和反向搜索同時進行，大大提高了搜索的速度，從而減小了算法的時間復雜度。

1 問題的提出

定義1：資產。目標網絡系統中具有價值的資源，包括數據庫、文檔信息、軟件服務等，是網絡安全管理者保護的對象。

定義2：關鍵資產。由于不同的資產對全局目標網絡系統所起的作用是不同的，因此資產的重要程度是不同的，本文將重要程度高的資產稱為關鍵資產。

在現實的應用中，重要程度低的資產盡管也存在著脆弱性，但其對全局目標網絡系統的安全性的影響微乎其微，相反，若關鍵資產的脆弱性被攻擊者利用，其對全局目標網絡系統的影響將是巨大的、致命的[1]。因此，有的網絡安全管理者將脆弱性評估的重點放在對目標網絡系統的安全運行起著舉足輕重的關鍵資產上[5]，基于此，本文提出了一種基于正反雙向搜索策略的、評估單目標的攻擊圖自動構建方法SGA-AGC。

2 SGA-AGC算法及其優化策略

定義3：攻擊對隊列。只有當前提屬性集合中的屬性都滿足時，原子攻擊才能被攻擊者實施，從而獲得后果屬性。其中，前提屬性集合中的權限屬性反映了攻擊者擁有的權限，包括Root、User和None；后果屬性反映了攻擊者實施攻擊后，所獲得的新屬性，包括RunCode、DOS等。為了準確地描述具體的攻擊過程，本文定義了攻擊對隊列，該隊列中元素的格式為（權限屬性：后果屬性）。

定義 4：攻擊屬性對隊列。為了使用Graphviz工具繪制攻擊圖，本文定義了攻擊屬性對隊列，該隊列反映了原子攻擊的前提屬性集合和后果屬性集合，隊列中元素的格式為（權限屬性：后果屬性：攻擊屬性集）[2]。其中權限屬性與后果屬性同定義3，攻擊屬性集合包含了原子攻擊前提屬性集合中除權限屬性外的其它屬性，如主機可達性關系和存在的脆弱性等。

定義5：間隔元素。在攻擊對隊列中，為了將不同搜索深度的攻擊對間隔開，本文定義了形式為（c：c）的間隔元素，其中c為任意符號。

定義6：在攻擊對隊列中，若元素（1c：2c）滿足2c為最終攻擊目標，則稱鈣元素為終端元素。

SGA-AGC算法的基本思想：首先將正向攻擊圖生成算法和反向攻擊圖生成算法集合起來，采用雙線程的方法，同時從起始攻擊點和攻擊目標出發進行分析，即使正向搜索和反向搜索同時進行[3]；然后利用間隔元素和終端元素生成攻擊路徑；最后結合攻擊路徑，利用繪圖軟件（Graphviz、Visio）生成攻擊圖。SGA-AGC算法流程圖如圖1所示。

圖1 SGA-AGC算法流程圖

SGA-AGC算法的優化策略：一方面，攻擊者不會采用很復雜的攻擊手段，即攻擊者不會以太多的主機為跳板進行攻擊；另一方面，在正向搜索過程中，有的攻擊路徑不會出現攻擊目標，或者在反向搜索過程中，有的攻擊路徑不會出現起始攻擊點，對這樣的攻擊路徑進行更深層次的搜索是沒有意義的。因此，SGA-AGC算法采用限制搜索深度的優化策略，在具體的實現過程中，用戶可以設定搜索深度的最大值。

3 實驗結果與分析

為了驗證SGA-AGC算法的可行性、有效性和可擴展性，本文從不同的角度進行實驗分析。實驗環境如下：服務器PowerEdge R710，操作系統RetHat v5.4，內存32G，CPU 2.26GHz。

由SGA-AGC算法性能分析可知，該算法性能與目標網絡系統中主機數量H、搜索深度最大值N、每臺主機最多擁有的脆弱性數量Nvul、原子攻擊數量Nexploit等參數有關[4]。為了驗證不同網絡環境下這些參數對算法性能的影響，分別設計了如下四組實驗。

第一組實驗驗證網絡系統中主機數量對算法性能的影響。令每臺主機最多擁有的脆弱性數量為1，原子攻擊數量為1，搜索深度最大值為5，當目標網絡系統中主機數量不同時。算法CPU消耗時間隨著H的增加呈多項式增加趨勢。

第二組實驗驗證搜索深度最大值對算法性能的影響。令每臺主機最多擁有的脆弱性數量為1，原子攻擊數量為1，主機數量為300，當搜索深度最大值不同時，算法CPU消耗時間隨著N的增加呈指數增加趨勢。

第三組實驗驗證每臺主機最多擁有的脆弱性數量對算法性能的影響。令主機數量為300，搜索深度最大值為5，原子攻擊數量為1，當主機最多擁有的脆弱性數量不同時，算法CPU消耗時間隨著Nvul的增加呈線性增加趨勢。

第四組實驗驗證原子數量對算法性能的影響。令主機數量為300，搜索深度最大值為5，原子攻擊數量為1，當原子數量不同時，算法CPU消耗時間隨著Nexploit的增加呈線性增加趨勢。

由上述四組實驗結果可知，在SGA-AGC算法中，搜索深度最大值N對算法性能的影響最大，然后依次是目標網絡系統中主機數量H、每臺主機最多擁有的脆弱性數量Nvul和原子攻擊數量Nexploit，該實驗結果與算法性能分析結果一致。

目前，與SGA-AGC算法比較相近并且做了類似實驗分析的主要有文獻[4]和文獻[5]。其中，文獻[4]所提算法（算法1）是一種迭代算法，從攻擊圖出發，采用深度優先的搜索策略，反向搜索攻擊路徑；文獻[5]提出了DFAGG算法（算法2），從初始狀態出發，采用深度優先的搜索策略搜索能夠到達攻擊目標的攻擊路徑。

4 結論

本文通過深入分析現有攻擊圖構建方法的不足，針對評估單目標安全性的需求，提出了評估單目標的攻擊圖自動構建方法SGA-AGC。SGA-AGC算法采用正反雙向的搜索策略，首先將正向攻擊圖生成算法和反向攻擊圖生成算法結合起來；然后利用間隔元素和終端元素生成只與攻擊目標有關的攻擊路徑；最后結合攻擊路徑，利用Graphviz、Visio軟件生成攻擊圖。為了驗證算法的可行性、有效性和可擴展性，從不同的分析角度做了驗證實驗，實驗表明本文算法大大減小了時間復雜度，從而顯著提高了其性能。

[1]張海霞, 連一峰, 蘇璞睿等.基于安全狀態域的網絡評估模型[J].軟件學報, 2009.

[2]VARDI Y, ZHANG Cunhui. Measures of network vulnerability[J]. IEEE Signal Processing Letters, 2007.

[3]陳峰.基于多口標攻擊圖的層次化網絡安全風險評估方法研究[M].長沙: 國防科技大學出版社, 2009.

[4]MELL P. The common vulnerability scoring system (CVSS)and its applicability to federal agency systems[R]. NIST Interagency Report 7435, 2007.

[5]Xinming Ou. A logic-programming approach to network security analysis[D]. Princeton: Princeton University, 2005.