面向大規(guī)模網(wǎng)絡安全加固的攻擊圖分析方法*

趙 超，王慧強+，林俊宇，呂宏武，韓冀中

1.哈爾濱工程大學 計算機科學與技術學院，哈爾濱 150001

2.中國科學院 信息工程研究所，北京 100000

1 引言

計算機網(wǎng)絡已成為當今社會不可或缺的組成部分，然而隨著網(wǎng)絡技術快速發(fā)展，大量的安全漏洞暴露出來。安全漏洞是各類網(wǎng)絡安全事件層出不窮的主要原因[1]。理論上，為確保網(wǎng)絡安全，應該掃描并修復網(wǎng)絡中的全部漏洞，但由于網(wǎng)絡的實際情況、安全與業(yè)務架構(gòu)之間的矛盾、加固代價、漏洞修復的滯后性等問題，修復全部漏洞實際上通常無法做到。因此，如何針對網(wǎng)絡的整體安全狀況，選擇合適的安全加固措施，既保障網(wǎng)絡的安全，同時盡可能減小對業(yè)務的影響，降低所選加固措施的總代價，成為網(wǎng)絡安全管理員面臨的一大難題。

針對這一問題，研究人員提出了一系列網(wǎng)絡安全分析模型，如故障樹（fault tree）、攻擊樹（attack tree）、攻擊圖（attack graph）等。故障樹最早用于裝備工程領域，用來分析設備故障原因，提高維修效率，后由Helmer等人[2]引入網(wǎng)絡安全領域，但故障樹的規(guī)模會隨邏輯門和基本事件數(shù)目的增加呈指數(shù)級增長，因此不適合大規(guī)模網(wǎng)絡的攻擊建模。攻擊樹模型由Schneier[3]提出，以葉子節(jié)點表示攻擊方法，根節(jié)點表示最終目標，能夠清晰地表示可能的攻擊方式，但隨著問題規(guī)模的擴大，樹形結(jié)構(gòu)的建模會導致模型中存在大量冗余，使得模型結(jié)構(gòu)非常龐大。在此基礎上，Phillips和Swiler[4]提出攻擊圖模型。隨著學者對攻擊圖模型的不斷研究，提出了屬性攻擊圖，較好地解決了狀態(tài)攻擊圖存在的空間爆炸問題。文獻[5]首次提出了攻擊者能力的“單調(diào)性假設”，將攻擊圖生成算法的復雜度由指數(shù)級降為多項式級，隨后又提出了很多方法用以生成攻擊圖[6-8]，開發(fā)了一系列的攻擊圖自動生成軟件[9-10]，進一步降低攻擊圖生成的時間復雜度。

要利用攻擊圖獲得網(wǎng)絡安全加固策略，需要對其做進一步的分析，相比于攻擊圖的生成，對攻擊圖分析方法的研究還存在很多問題。文獻[11]首先提出最小原子攻擊修復集問題，認為可以通過修復原子攻擊阻斷攻擊路徑，并用貪婪算法求解，但該方法沒有考慮修復代價。文獻[12-13]研究了最優(yōu)初始條件修復集問題，通過修復某些初始屬性以阻斷攻擊路徑，同時以最少的修復措施保障關鍵節(jié)點的安全，但精確的攻擊路徑搜索算法具有指數(shù)級時間復雜度，無法應用于大規(guī)模網(wǎng)絡中。文獻[14]提出了n-有效攻擊路徑生成算法，通過限制迭代次數(shù)降低算法時間復雜度，但僅以路徑長度作為攻擊風險的評判標準，沒有考慮不同漏洞在攻擊難度和造成后果等方面的差異，并且算法同樣沒有解決局部最優(yōu)問題。文獻[15]提出用基于網(wǎng)絡流的攻擊圖分析方法，解決最優(yōu)原子攻擊修復集和最優(yōu)初始屬性修復集問題，算法效率較高，但是忽略了屬性攻擊圖節(jié)點間的邏輯關系，因此生成的修復策略修復代價過高。文獻[16]基于依賴攻擊圖，同時考慮攻擊威脅和修復成本，直接計算關鍵狀態(tài)，但在實際應用中，修復成本對于攻擊者的攻擊行為并無影響，不宜作為風險評估的依據(jù)。

針對目前研究的不足，基于屬性攻擊圖，以現(xiàn)有的攻擊圖構(gòu)建方法為研究基礎，對攻擊圖的分析方法展開研究，提出了一種適用于大規(guī)模網(wǎng)絡安全加固的攻擊圖分析方法。首先，提出攻擊路徑的風險評估方法，并采用啟發(fā)式算法搜索攻擊圖中風險系數(shù)最高的攻擊路徑；然后，以此為度量基礎，根據(jù)網(wǎng)絡的實際情況，設置危險閾值，搜索出全部危險系數(shù)大于閾值的潛在攻擊；最后，選擇能夠阻斷這些高危險潛在攻擊的屬性，生成低代價的網(wǎng)絡安全加固策略。

2 攻擊路徑危險系數(shù)度量方法

網(wǎng)絡中普遍存在著安全漏洞，并且每天都有大量的新漏洞被發(fā)現(xiàn)，但對全部漏洞進行修復往往是不切實際的。攻擊圖能夠很好地展現(xiàn)漏洞之間的關聯(lián)，通過對攻擊圖的分析，選擇危險性較高、修復難度較低的漏洞進行修復，盡可能地使網(wǎng)絡具有相對較高的安全程度是一個更加實際的辦法。要判斷不同攻擊方式的威脅程度，需要有具體的評判方法，在闡述具體方法之前，首先給出一些基本定義。

2.1 基本定義

屬性攻擊圖能夠展示出攻擊者利用網(wǎng)絡中的各種安全漏洞進行攻擊的所有可能方式，它的形式化定義如下。

定義1（屬性攻擊圖）屬性攻擊圖AG定義為一個三元組D=＜V,A,E＞。其中，V表示屬性節(jié)點集合，V0表示初始屬性節(jié)點集合，Vd表示非初始屬性節(jié)點集合，則V0與Vd共同構(gòu)成屬性節(jié)點集合V，即V=V0?Vd；A表示原子攻擊集合；E表示有向邊集合，是有序積集((V0?Vd)×A)?(A×Vd)的一個子集。

同時，屬性攻擊圖需滿足以下規(guī)則：

（1）當原子攻擊a的所有前提屬性均得到滿足的情況下，原子攻擊a才能被執(zhí)行。

（2）屬性v的任意一個前提原子攻擊被執(zhí)行，都可以使攻擊者獲得屬性v。

在屬性攻擊圖中，通常用文字表示屬性節(jié)點，用圓或橢圓表示原子攻擊節(jié)點，用箭頭表示有向邊，如圖1所示。

Fig.1 An example of attack graph圖1 攻擊圖實例

定義2（可達）在一個攻擊圖中，對于屬性集Va∈V，若攻擊者從Va出發(fā)，經(jīng)過一系列攻擊行為，可以獲得屬性v，則稱Va可達v，記作Va?v；反之，若攻擊者從Va出發(fā)，不足以獲得屬性v，則稱Va不可達v，記作Vav。

定義3（初始可達集）若Va?v，且Va?V0，則稱Va是v的初始可達集。

定義4（最小初始可達集）若Va是v的初始可達集，且對 ?v′∈Va，Va-v′v，則稱Va是v的最小可達初始屬性集，簡稱最小初始集。

也就是說，對于攻擊者的一次攻擊行為，若要獲得關鍵屬性，對應的最小初始集中的所有屬性都是必要的。

定義5（攻擊路徑）攻擊者利用一個最小初始集，經(jīng)過一步或多步攻擊，最后獲得目標屬性的過程，稱為一次攻擊過程，將這個過程中發(fā)生的所有原子攻擊按先后順序構(gòu)成一個序列，稱為一個攻擊路徑，表示形式為ai→aj→…→ak。

對于一個關鍵屬性v，可能存在多個最小初始集，并且不同的最小初始集中可能存在相同的初始屬性。例如，在圖1所示的攻擊圖中，攻擊者可以通過初始屬性v0、v3，經(jīng)由攻擊路徑a1→a3獲得屬性v5；也可以通過屬性v1、v2、v3，經(jīng)由攻擊路徑a2→a3獲得屬性v5。因此，屬性v5存在兩個最小初始集，分別為{v0,v3}和{v1,v2,v3}。

2.2 攻擊路徑危險系數(shù)

為了得到網(wǎng)絡安全加固策略，首先需要知道攻擊者有哪些可能的攻擊路徑。在攻擊圖中，搜索全部攻擊路徑的算法具有無法避免的指數(shù)級時間復雜度，無法適用于大規(guī)模網(wǎng)絡。一個更具實際意義的方法是：通過評估攻擊路徑的風險，搜索被攻擊可能性較高的攻擊路徑，并提前阻斷，保障網(wǎng)絡的相對安全。

為了度量不同攻擊路徑被攻擊者利用可能性的高低，需要對攻擊路徑上全部漏洞的嚴重程度進行評估。給出一種基于CVSS（common vulnerability scoring system）的攻擊路徑危險系數(shù)的計算方法。CVSS是NVD（national vulnerability database）提出的一套公開標準，被用于評價安全漏洞的嚴重程度。對于每一個已知漏洞，CVSS會給出一個基礎分數(shù)（base score），該分數(shù)通過AccessVecto（r接入方式）、Access-Complexity（攻擊復雜度）、Authentication（身份驗證）、ConfImpact（機密性影響）、IntegImpac（t完整性影響）、AvailImpac（t有效性影響）等指標計算得出，漏洞的危險程度越高，分數(shù)就越高，取值范圍是[0,10]?？梢钥闯?，作為一種通用的漏洞評分標準，CVSS基礎分數(shù)綜合考慮了攻擊難度和造成后果的嚴重程度，能較好地反映出攻擊者對于不同漏洞實施攻擊的意愿的高低。因此，本文采用CVSS基礎評分作為參考，并以此說明攻擊路徑危險系數(shù)的計算方法。

攻擊者對網(wǎng)絡進行多步攻擊的過程中，每一步攻擊對應著一個安全漏洞，對于任意的原子攻擊a，令r(a)為原子攻擊a的危險系數(shù)，則：

對于任意攻擊路徑l，r(l)為攻擊路徑l的危險系數(shù)，定義為l上全部利用的漏洞危險系數(shù)的乘積，則：

攻擊路徑的危險系數(shù)反映了路徑被攻擊者選擇的意愿大小的相對程度，為攻擊路徑的威脅程度評判提供了依據(jù)。

3 最小初始集生成方法

上文提到，搜索全部攻擊路徑的算法具有無法避免的指數(shù)級時間復雜度，無法適用于大規(guī)模網(wǎng)絡。在實際應用中，由于網(wǎng)絡性質(zhì)的不同，不同的組織、機構(gòu)對于自身網(wǎng)絡安全程度的要求并不相同。例如，大型商業(yè)公司和一些政府部門對網(wǎng)絡安全性的要求通常較高，在網(wǎng)絡安全方面的投入也較大；而對于一般的辦公網(wǎng)絡，只要保證網(wǎng)絡的正常使用即可，安全要求相對較低，通常也無法承受過高的安全加固代價。針對這種情況，設計方法采用以下步驟：（1）搜索網(wǎng)絡中危險系數(shù)最高的攻擊路徑，作為初步判斷網(wǎng)絡安全狀況的基礎；（2）根據(jù)步驟（1）的結(jié)果，結(jié)合網(wǎng)絡的安全需求情況和專業(yè)人員的經(jīng)驗，設定一個危險閾值；（3）搜索出全部危險系數(shù)大于閾值（潛在風險較高）的攻擊路徑對應的最小初始集，所得的最小初始集將作為本文第4部分的輸入，為最終生成網(wǎng)絡安全加固策略提供基礎。

3.1 最大危險系數(shù)計算

最大危險系數(shù)攻擊路徑的精確搜索算法同樣具有指數(shù)級的時間復雜度，因此可采用啟發(fā)式算法求解攻擊圖中的最大危險系數(shù)。在一個攻擊圖中，對攻擊路徑的搜索通常采用自底向上的方式，由關鍵屬性出發(fā)，逆向構(gòu)造攻擊路徑，這個過程與螞蟻選路的過程非常相似，因此選用蟻群算法求解攻擊圖中最大危險系數(shù)問題。對蟻群優(yōu)化算法中的ASrank模型進行適當?shù)男薷?，提出攻擊圖最大危險系數(shù)計算方法。

定義6（攻擊路徑運算符“+”）設l1、l2為兩個攻擊路徑，將l2連接在l1后面，構(gòu)成一個新的攻擊路徑，稱為l1、l2的“+”運算，記作l1+l2。

給定攻擊圖AG和目標屬性vk，所有螞蟻從vk出發(fā)，采用深度優(yōu)先的迭代搜索方式構(gòu)建危險系數(shù)最高的路徑lmax。由于屬性攻擊圖中節(jié)點間存在邏輯關系，針對屬性攻擊圖中的兩種節(jié)點，算法遵循以下規(guī)則：

（1）當螞蟻位于屬性節(jié)點v∈Vd時，螞蟻在v的前提原子攻擊節(jié)點中選擇一個加入lmax中并移動到該節(jié)點上。

（2）當螞蟻位于原子攻擊節(jié)點a∈A時，依次對a的每一個前提屬性節(jié)點構(gòu)建攻擊路徑，將結(jié)果與該螞蟻已生成的路徑進行“+”運算。

規(guī)則（1）中，螞蟻選擇原子攻擊節(jié)點并不是盲目的，而是傾向于選擇信息素濃度和收益更高的節(jié)點，這里的收益更高指的是原子攻擊節(jié)點的危險系數(shù)r(a)更大。因此，螞蟻位于屬性節(jié)點v時，選擇原子攻擊節(jié)點i的概率可以表示為：

其中，參數(shù)α，β＞0；τi是節(jié)點i的信息素濃度；ηi是節(jié)點i的啟發(fā)式信息，ηi=r(i)。

構(gòu)造的路徑危險系數(shù)r(l)初始值設為1，當K只螞蟻完成構(gòu)建后，按照構(gòu)建的解路徑危險系數(shù)的大小排序，只有排列在最前的ω-1只螞蟻和生成了至今最優(yōu)解的螞蟻才允許釋放信息素。構(gòu)建的解路徑危險系數(shù)r(l)越大的螞蟻，留下的信息素就越多。信息素更新準則為：螞蟻在它選擇的原子攻擊節(jié)點上留下的信息素量為Q×Rk，這里Q是一個常數(shù)，Rk是螞蟻k構(gòu)造解路徑的危險系數(shù)。同時，信息素會隨著時間的流逝而揮發(fā)，信息素更新公式如下：

其中，t是迭代次數(shù)；ρ∈[0,1]是控制信息素τi揮發(fā)的參數(shù)；Δτi是節(jié)點i上信息素的總增量；是螞蟻k在節(jié)點i上留下的信息素量。在信息素更新之后，進行第t+1次迭代。算法經(jīng)過T次迭代后，得到最終結(jié)果。

為避免螞蟻生成無效的含圈攻擊路徑或重復計入屬性節(jié)點導致的危險系數(shù)計算錯誤，引入了兩個屬性節(jié)點集Vselected和Vvisited，分別存放當前節(jié)點的祖先節(jié)點和兄弟節(jié)點。在深度優(yōu)先迭代之前，若節(jié)點已在Vselected中，說明產(chǎn)生無效的含圈攻擊路徑，若節(jié)點已在Vvisited中，說明該節(jié)點之前已經(jīng)搜索過，不必再次搜索。下面給出每只螞蟻構(gòu)造高危險系數(shù)攻擊路徑時的算法ant_path_search的偽代碼。

算法1 ant_path_search算法

算法第4行若構(gòu)造的攻擊路徑含圈，屬無效攻擊路徑，螞蟻重新搜索；第7行屬性v是已搜索過的分支，無需重新搜索；第11行螞蟻根據(jù)式（3）中的概率選擇下一步原子攻擊節(jié)點；第16行對所有下一步屬性節(jié)點的攻擊路徑做“+”運算，迭代構(gòu)造完整的攻擊路徑。

依照此方法，螞蟻可以構(gòu)造一條攻擊路徑并計算出危險系數(shù)，循環(huán)運行算法K次，可以得到K條攻擊路徑，然后根據(jù)式（4）更新各個節(jié)點的信息素，更新搜索到的最大危險系數(shù)，重復此過程T次，得到最后結(jié)果。

假設攻擊圖AG中含有N個節(jié)點，每只螞蟻最多對N個節(jié)點遍歷一次，共有K只螞蟻，迭代T輪，則該蟻群算法的時間復雜度為O(T×K×N)。

3.2 最小初始集生成

通過蟻群算法可以得到攻擊路徑中最高的危險系數(shù)，在此基礎上，可以根據(jù)網(wǎng)絡對安全的要求程度、網(wǎng)絡規(guī)模和可承受代價多少的不同，設定一個容忍系數(shù)μ，危險閾值rth=rmax×μ，認為危險系數(shù)r＞rth的攻擊路徑具有較高危險性，應該予以阻斷。同時，研究發(fā)現(xiàn)真實的攻擊路徑長度往往較短[10]，并且過長的攻擊路徑會降低攻擊者的攻擊意愿，因此設定一個攻擊者攻擊意愿的衰減系數(shù)γ，當攻擊路徑l長度大于lmax時，危險系數(shù)隨攻擊路徑步數(shù)的增長而衰減。此外，考慮到一個網(wǎng)絡中可能包括多個關鍵節(jié)點，不同的節(jié)點重要程度不同，因此為每個目標屬性v設置一個參數(shù)λv反映目標節(jié)點的重要程度。當修復資源有限的情況下，該參數(shù)可以幫助管理員將更多的資源投入到更重要的節(jié)點上。因此攻擊路徑的危險系數(shù)公式更新為：

其中，m為路徑l的步數(shù)；m′為lmax的步數(shù)。

容忍系數(shù)μ需要根據(jù)網(wǎng)絡對安全的要求、網(wǎng)絡規(guī)模和可承受代價的情況綜合設置。對網(wǎng)絡安全的要求越高，網(wǎng)絡規(guī)模越小，可承受代價越大，μ應越小，危險閾值rth越小，滿足危險系數(shù)r＞rth的攻擊路徑就越多，反之亦然。衰減系數(shù)γ則通過降低超長攻擊路徑的危險系數(shù)限制被選擇的攻擊路徑數(shù)量，γ越小，超長路徑的危險系數(shù)r越小，滿足條件r＞rth的路徑數(shù)量就越少，γ越大，則滿足條件的路徑數(shù)量就越多。參數(shù)λ需要根據(jù)目標節(jié)點的重要程度設置，越重要的節(jié)點λ應越大，對應該屬性的攻擊路徑危險系數(shù)就越高，滿足條件r＞rth的路徑數(shù)量就越多。容忍系數(shù)μ、衰減系數(shù)γ和參數(shù)λ需要專業(yè)人員依據(jù)經(jīng)驗，并結(jié)合上述情況綜合設置。

在后續(xù)分析中需要使用攻擊路徑對應的最小初始集，因此提出最小初始集生成算法（minimum initial reachable attribute sets，MIRAS），搜索全部危險系數(shù)r＞rth的攻擊路徑對應的最小初始集。首先給出一個新的集合運算符。

定義7（集合運算符“×”）設A、B為兩個元素為集合的集合，從A中任取一個元素A′，B中任取一個元素B′，把它們的并集作為一個元素，所有這樣的元素構(gòu)成一個集合，稱為集合A與B的“×”運算，記作A×B，即A×B={A′?B′|A′∈A,B′∈B}。

MIRAS算法從給定的關鍵屬性節(jié)點v出發(fā)，采用深度優(yōu)先搜索，并用危險閾值rth限制搜索過程，迭代地搜索出節(jié)點v的全部高危險系數(shù)最小初始集M(v)。在向前搜索過程中，若v是可達屬性節(jié)點，則v的全部最小初始集M(v)就是v的父節(jié)點的最小初始集的并集；若v是原子攻擊節(jié)點，則M(v)就是v的父節(jié)點的最小初始集的“×”運算。在搜索的同時計算當前攻擊路徑的危險系數(shù)，當一條攻擊路徑含圈，或危險系數(shù)小于閾值rth時，返回空集?。這樣就可以迭代地搜索出全部危險系數(shù)大于閾值rth的攻擊路徑對應的最小初始集。由于篇幅的原因，這里不再詳述MIRAS算法的偽代碼。

下面分析MIRAS算法的時間復雜度。設最高危險系數(shù)攻擊路徑的步數(shù)為m′，對于容忍系數(shù)μ、衰減系數(shù)γ和參數(shù)λ，存在正整數(shù)m使得λγm+1＜μ＜λγm，因此算法搜索的攻擊路徑長度不大于m′+m。設攻擊圖中節(jié)點個數(shù)為N，節(jié)點的最大入度為d，則當v為屬性節(jié)點時，最多調(diào)用MIRAS(ai,r,m)算法d次，當v為原子攻擊節(jié)點時，最多調(diào)用MIRAS(vi,r,m+1)算法d次，因為搜索的路徑長度不大于m′+m，算法最多迭代2(m′+m)次，所以MIRAS算法的時間復雜度為O(d2(m′+m)×N)。由于m′+m為正整數(shù)，算法具有多項式級時間復雜度。

MIRAS算法給出了對于單一關鍵屬性v的全部最小初始集的計算方法。若攻擊圖中存在多個關鍵屬性，只需為每一個關鍵屬性vi′增加一個虛擬的下一步原子攻擊ai′，將這些原子攻擊的危險系數(shù)分別設為λi′，再為這些原子攻擊增加一個共同的虛擬結(jié)果屬性vk′，即可把求關鍵屬性集Vk的全部高危險系數(shù)最小初始集問題轉(zhuǎn)化為求關鍵屬性vk′的高危險系數(shù)最小初始集問題。

4 最優(yōu)修復集生成方法

通過上文的方法可以獲得攻擊圖中全部危險系數(shù)大于閾值的攻擊路徑對應的最小初始集，需要對這些最小初始集進行進一步的分析、計算，最終得到最優(yōu)修復集，即網(wǎng)絡安全加固策略。

4.1 最優(yōu)修復集問題

關鍵屬性vk的每一個最小初始集代表著一條可能的攻擊路徑，因此可以采取消除其中某些初始屬性的方法來阻斷該路徑，這些措施包括為系統(tǒng)漏洞打補丁，修改系統(tǒng)設置，禁用服務，加裝防火墻或修改防火墻設置，改變網(wǎng)絡拓撲等。

定義8（待修復集）在一個最小初始集中，所有可以被相應的安全彌補措施消除的屬性構(gòu)成的集合，稱為待修復集。

5.動詞不定式復合結(jié)構(gòu)做后置定語，它和動詞不定式短語一樣，均只能放在被修飾成分的后面，做后置定語。例如：

定理1消除待修復集中的任意一個屬性，均可阻斷對應的攻擊路徑。

證明對于關鍵屬性vk，Va是vk的一個最小初始集，Vr是Va對應的待修復集，顯然Vr?Va，?v′∈Vr有v′∈Va，根據(jù)最小初始集定義可知，Va-v′?vk。 □

為了保障關鍵屬性的安全，需對其全部高危險系數(shù)攻擊路徑對應的待修復集進行修復。根據(jù)定理1，在對單個待修復集進行修復時，只需選擇其中的一個屬性，并采取相應措施將其消除即可。同時，通過圖1的例子可以發(fā)現(xiàn)，不同的最小初始集中可能含有共同的初始屬性，因此消除一個屬性可能同時修復多個待修復集。而每種阻斷措施都需要付出一定的代價，例如修改系統(tǒng)設置或防火墻設置可能以降低系統(tǒng)易用性甚至犧牲某些業(yè)務功能為代價，系統(tǒng)升級可能以服務斷開時間為代價等。因此，如何選取屬性進行消除，使總代價最低就成為網(wǎng)絡安全加固策略生成研究的關鍵問題。本文稱該問題為最優(yōu)修復集問題，該問題的數(shù)學描述如下。

在攻擊圖AG中，設vk為關鍵屬性，為vk的全部待修復集，，設變量yj，若vj被選中，則yj=1，否則yj=0，cj為vj的代價。要使最優(yōu)修復集總代價最小，就是要求：

該問題等價于帶權重的集合覆蓋問題，是NP完全問題，精確求解算法時間復雜度為指數(shù)級，對于大規(guī)模網(wǎng)絡，顯然不具有實際應用價值。貪婪算法[14]是解決該問題的一個方法，效率很高，但極易陷入局部最優(yōu)，因此得到的加固策略代價較高。生成網(wǎng)絡安全加固策略的目的是為網(wǎng)絡安全管理員提供參考，在資源有限的情況下如何保障網(wǎng)絡具有更高的安全性。因此，對于大規(guī)模網(wǎng)絡的安全加固來說，相比于快速給出一個代價較高的加固策略，在可接受的時間范圍內(nèi)計算出代價更低的加固策略顯然更具實用價值?；诖顺霭l(fā)點，提出基于蟻群算法的網(wǎng)絡安全加固策略生成算法AS-NSH，求解最優(yōu)修復集。

4.2 網(wǎng)絡安全加固策略生成

首先對問題進行預處理，步驟如下：

AS-NSH算法描述如下：

首先構(gòu)建一個完全圖，節(jié)點集合由Vr中的全部屬性和一個啞元節(jié)點構(gòu)成，每個節(jié)點都具有信息素，每輪投放K只螞蟻。開始時，所有螞蟻都從啞元節(jié)點開始構(gòu)解，每只螞蟻根據(jù)式（11）給出的概率選擇下一步節(jié)點，螞蟻每訪問一個節(jié)點，就將該節(jié)點加入已選節(jié)點集，同時，已覆蓋的集合也可能發(fā)生變化，因此，在螞蟻每一步行動之后，都需要重新計算剩余節(jié)點的選擇概率。

其中，Vallowed是沒有被選擇的節(jié)點集合；參數(shù)α,β＞0；τi是節(jié)點i的信息素濃度；是螞蟻k選擇節(jié)點i的收益代價比，可以表示為：

其中，Seti表示節(jié)點i能夠覆蓋的待修復集的集合；表示螞蟻k當前已經(jīng)覆蓋的待修復集的集合；wi是節(jié)點i對應的代價。

其中，Q是一個常數(shù)；Wk是螞蟻k構(gòu)造解的代價；t是迭代次數(shù)；ρ∈[1,0]是控制信息素τi揮發(fā)的參數(shù)；Δτi是節(jié)點i上信息素的總增量；是螞蟻k在節(jié)點i上留下的信息素量。在信息素更新之后，進行第t+1次迭代。算法經(jīng)過T輪迭代后，得到最終結(jié)果。

下面分析AS-NSH算法的時間復雜度。設待修復集個數(shù)為m，節(jié)點數(shù)即屬性個數(shù)為n，一只螞蟻每次選擇下一步節(jié)點前都要計算所有剩余節(jié)點的選擇概率，螞蟻最多選擇n個節(jié)點，每輪有K只螞蟻，迭代T輪，因此AS-NSH算法的時間復雜度為O(T×K×n2)。

通過AS-NSH算法能夠計算出目標網(wǎng)絡的最優(yōu)修復集，即獲得了該網(wǎng)絡的安全加固策略，即對最優(yōu)修復集中的每個屬性，采取相應的網(wǎng)絡安全加固措施進行消除，保障目標網(wǎng)絡安全。

5 仿真實驗與評價

設計兩組仿真實驗分別驗證本文提出的最小初始集生成方法和最優(yōu)修復集生成方法的性能。仿真實驗的主機環(huán)境為Intel CoreTM2 Quad CPU 2.67 GHz，4.0 GB RAM，Windows 7操作系統(tǒng)，采用Java編程實現(xiàn)。

5.1 最小初始集生成方法性能分析

實驗模擬生成5個不同規(guī)模的攻擊圖，屬性節(jié)點的最大入度和出度均為4，原子攻擊節(jié)點的最大入度為3，出度為1，原子攻擊的危險系數(shù)為0到1之間的隨機值。攻擊圖的規(guī)模特征如表1所示，對提出的ant_path_search+MIRAS（APSM）算法、Obtain-Path（OP）算法[14]和精確求解的Network-Hardening（NH）算法[13]的時間性能進行對比。APSM算法中，MIRAS算法的λ均設為1，蟻群算法的迭代計算次數(shù)T=100，螞蟻數(shù)量，其他參數(shù)設置如表2所示。

Table 1 Scale characteristics of simulated attack graphs表1 模擬攻擊圖的規(guī)模特征

圖2給出了NH算法、不同參數(shù)的OP算法和不同參數(shù)的APSM算法在5組攻擊圖上的時間性能情況，縱坐標以指數(shù)形式表示。其中，OP1的有效路徑長度n=10；OP2的有效路徑長度n=15；APSM1的容忍系數(shù)μ=0.2，衰減系數(shù)γ=0.6；APSM2的容忍系數(shù)μ=0.1，衰減系數(shù)γ=0.8。其中，在后兩個實驗攻擊圖上，NH算法在104s內(nèi)沒有給出結(jié)果?？梢钥闯觯琋H算法的運行時間隨攻擊圖規(guī)模擴大而急劇增長，可擴展性較差，難以實際應用。APSM算法和OP算法的運行時間增長較慢，均具有良好的可擴展性，計算時間復雜度方面均優(yōu)于NH算法。

Table 2 Parameters of ant_path_search algorithm表2 蟻群算法的參數(shù)設置

Fig.2 CPU time of algorithms in different scales of attack graphs圖2 不同規(guī)模攻擊圖下各算法的CPU運行時間

同時可以看出，OP算法和APSM算法的運行時間受參數(shù)設置的影響明顯。對比OP1與OP2可知，OP算法的運行時間隨有效路徑長度n的增大而增長。對比APSM1與APSM2可知，容忍系數(shù)μ越小，哀減系數(shù)γ越大，則算法運行時間越長，反之則運行時間越短。

整體上APSM算法的運行時間稍長于OP算法，這是因為APSM算法為了更準確地對攻擊圖進行風險評估，首先需要對攻擊圖中的最高危險系數(shù)進行計算，需要消耗少量時間，APSM算法在搜索時還需要不斷計算已生成路徑的危險系數(shù)，同樣需要消耗時間。雖然OP算法在時間性能上略優(yōu)于APSM算法，但OP算法生成的攻擊路徑還需要進一步計算生成最小初始集，并且OP算法僅以路徑長度作為風險評判的依據(jù)，需要在算法運行前對網(wǎng)絡狀況缺乏一定了解的情況下確定有效路徑長度n。而APSM算法綜合了攻擊實施難度、后果嚴重程度、攻擊路徑長度和目標節(jié)點的重要程度來判斷攻擊路徑的危險程度，并且可以在對網(wǎng)絡的安全狀況有一定了解的情況下設置參數(shù)，結(jié)果更符合真實情況。因此，APSM算法在運算結(jié)果的合理性上優(yōu)于OP算法。

5.2 最優(yōu)修復集生成方法性能分析

實驗使用10組數(shù)據(jù)對比AS-NSH算法和Weighted-Greedy（WG）算法[14]的性能，該數(shù)據(jù)集由布魯內(nèi)爾大學的Beasley教授在文獻[17]中提出，是一組求解集合覆蓋問題的實例數(shù)據(jù)，提供公開下載。每組數(shù)據(jù)包括集合數(shù)m、元素數(shù)n、每個元素的代價Wi、每個集合包含的元素和每組問題的最優(yōu)解，最優(yōu)解即能夠覆蓋全部集合的最低總代價。對10組數(shù)據(jù)分別用WG算法和AS-NSH算法進行求解，AS-NSH算法參數(shù)設置如下：迭代次數(shù)T設為100次，α為1，β為2，ρ為0.5，Q為1，K設為20，τ0設為K/Wg。實驗結(jié)果如表3所示。

Table 3 Experimental results of two algorithms on different data sets表3 兩種算法在各實驗數(shù)據(jù)集上的運行結(jié)果

表3展示了各組數(shù)據(jù)的規(guī)模特征和兩種算法的運行結(jié)果。算法下面的兩列數(shù)據(jù)分別為所生成的解C和生成解與最優(yōu)解相差的百分比S，其中AS-NSH算法的結(jié)果為20次運算的平均值。對比實驗結(jié)果可知，AS-NSH算法生成的解均明顯小于WG算法。AS-NSH算法的平均結(jié)果比最優(yōu)解高3.36%，而WG算法平均比最優(yōu)解高11.69%。相比于WG算法，ASNSH算法將生成策略與最優(yōu)策略的差距降低了71.3%。圖3展示了WG算法、AS-NSH算法在10組數(shù)據(jù)上運行結(jié)果與最優(yōu)解的對比，其中橫坐標為數(shù)據(jù)集編號，縱坐標為各算法的解。

Fig.3 Results of two algorithms and optimum圖3 兩種算法的結(jié)果與最優(yōu)解的對比

Fig.4 CPU time of two algorithms圖4 兩種算法的CPU時間

圖4展示了兩種算法在各組數(shù)據(jù)上運行的平均時間。WG算法所需時間均小于1 s，明顯少于ASNSH算法。AS-NSH算法的運行時間雖然較多，但依然在合理的范圍內(nèi)，而結(jié)合之前的實驗結(jié)果，WG算法計算出的結(jié)果并不理想。在實際應用中，WG算法給出的加固策略會給用戶造成更大的修復代價，而AS-NSH算法的結(jié)果更接近最優(yōu)解，能夠有效地降低所需的安全加固代價，在資源有限的情況下獲得更優(yōu)的加固策略和更好的安全保障。對于一個實際的網(wǎng)絡，生成安全加固策略需要的時間只要在合理的范圍內(nèi)即可，能夠計算出更好的解，盡可能地為用戶節(jié)約修復代價顯然更具實際意義。因此對于大規(guī)模網(wǎng)絡的安全加固，AS-NSH算法具有更大的實際應用價值。

6 結(jié)束語

本文提出了一種面向大規(guī)模網(wǎng)絡安全加固的攻擊圖分析方法。首先提出了綜合考慮攻擊難度、攻擊后果嚴重程度、路徑長度和目標節(jié)點重要程度的風險評估方法，并通過啟發(fā)式算法計算最大風險系數(shù)的攻擊路徑，避免了精確搜索攻擊路徑的指數(shù)級時間復雜度問題；然后結(jié)合最大風險系數(shù)、網(wǎng)絡規(guī)模、網(wǎng)絡性質(zhì)和實際需求設置危險閾值，搜索高風險的最小初始集；最后提出啟發(fā)式算法求解最優(yōu)修復集問題，計算低代價的網(wǎng)絡安全加固策略，避免精確求解的指數(shù)級時間復雜度問題。實驗結(jié)果表明，本文方法具有良好的可擴展性，可應用于大規(guī)模網(wǎng)絡中，與現(xiàn)有方法相比，能夠在可接受的時間內(nèi)，有效地獲得更符合真實威脅情況的攻擊路徑。在本次選取的實驗數(shù)據(jù)集上，相比于貪婪算法，本文方法將生成策略與最優(yōu)策略的差距減小了71.3%。綜上所述，本文方法具有更強的實際應用價值。在后續(xù)的研究工作中，將進一步完善攻擊路徑的風險評估方法，使之更加符合真實情況，同時對提出的各算法進行優(yōu)化，進一步降低網(wǎng)絡安全加固策略的代價。

[1]Zang Yuqing,Li Xiaoyu,Zheng Chen,et al.2010 security vulnerability analysis and prospect[J].Netinfo Security,2011(2):69-72.

[2]Helmer G,Wong J,Slagell M,et al.Asoftware fault tree approach to requirements analysis of an intrusion detection system[J].Requirements Engineering,2002,7(4):207-220.

[3]Schneier B.Attack trees[J].Dr Dobb's Journal,1999,24(12):21-29.

[4]Phillips C,Swiler L P.A graph-based system for networkvulnerability analysis[C]//Proceedings of the 1998 Workshop on New Security Paradigms,Charlottsville,Sep 22-25,1998.New York:ACM,1998:71-79.

[5]Ammann P,Wijesekera D,Kaushik S.Scalable,graph-based network vulnerability analysis[C]//Proceedings of the 9th ACM Conference on Computer and Communications Security,Washington,Nov 18-22,2002.New York:ACM,2002:217-224.

[6]Ingols K,Lippmann R,Piwowarski K.Practical attack graph generation for network defense[C]//Proceedings of the 22nd Annual Computer Security Applications Conference,Dec 11-15,2006.Washington:IEEE Computer Society,2006:121-130.

[7]Ou Xinming,Boyer W F,McQueen M A.A scalable approach to attack graph generation[C]//Proceedings of the 13th ACM Conference on Computer and Communications Security,Alexandria,Oct 30-Nov 3,2006.NewYork:ACM,2006:336-345.

[8]Ye Yun,Xu Xishan,Qi Zhichang,et al.Attack graph generation algorithm for large-scale network system[J].Journal of Computer Research and Development,2013,50(10):2133-2139.

[9]Ou Xinming,Govindavajhala S,AppelAW.MulVAL:a logicbased network security analyzer[C]//Proceedings of the 14th USENIX Security Symposium,Baltimore,Jul 31-Aug 5,2005.Berkeley:USENIXAssociation,2005,14:8.

[10]Jajodia S,Noel S.Topological vulnerability analysis:a powerful new approach for network attack prevention,detection,and response[J].Algorithms,Architectures,and Information Systems Security,2007,3:285-305.

[11]Jha S,Sheyner O,Wing J.Two formal analyses of attack graphs[C]//Proceedings of the 15th IEEE Computer Security Foundations Workshop,Cape Breton,Jun 24-26,2002.Washington:IEEE Computer Society,2002:49-63.

[12]Noel S,Jajodia S,O'Berry B,et al.Efficient minimum-cost network hardening via exploit dependency graphs[C]//Proceedings of the 19th Annual Computer Security Applications Conference,Las Vegas,Dec 8-12,2003.Washington:IEEE Computer Society,2003:86-95.

[13]Wang Lingyu,Noel S,Jajodia S.Minimum-cost network hardening using attack graphs[J].Computer Communications,2006,29(18):3812-3824.

[14]Chen Feng,Zhang Yi,Su Jinshu,et al.Two formal analyses of attack graphs[J].Journal of Software,2010,21(4):838-848.

[15]Wu Jinyu,Jin Shuyuan,Yang Zhi.Analysis of attack graphs based on network flow method[J].Journal of Computer Research and Development,2011,48(8):1497-1505.

[16]Wang Shuzhen,Zhang Zonghua,Kadobayash Y.Exploring attack graph for cost-benefit security hardening:a probabilistic approach[J].Computers&Security,2013,32(1):158-169.

[17]Beasley J E.An algorithm for set covering problem[J].European Journal of Operational Research,1987,31(1):85-93.

附中文參考文獻：

[1]張玉清,李瀟宇,鄭晨,等.2010年安全漏洞態(tài)勢分析與展望[J].信息網(wǎng)絡安全,2011(1):69-72.

[8]葉云,徐錫山,齊治昌,等.大規(guī)模網(wǎng)絡中攻擊圖自動構(gòu)建算法研究[J].計算機研究與發(fā)展,2013,50(10):2133-2139.

[14]陳鋒,張怡,蘇金樹,等.攻擊圖的兩種形式化分析[J].軟件學報,2010,21(4):838-848.

[15]吳金宇,金舒原,楊智.基于網(wǎng)絡流的攻擊圖分析方法[J].計算機研究與發(fā)展,2011,48(8):1497-1505.