基于隨機松弛優(yōu)選策略的網(wǎng)絡(luò)脆弱性彌補算法

趙光勝，程慶豐，孫永林

(1. 解放軍外國語學(xué)院 語言工程系，河南 洛陽 471003； 2. 國防科技大學(xué) 計算機學(xué)院，湖南 長沙 410073)

1 引言

計算機網(wǎng)絡(luò)技術(shù)的飛速發(fā)展深刻影響著人類的生產(chǎn)生活方式。然而在享受互聯(lián)互通和信息共享帶來的便捷與效益的同時，網(wǎng)絡(luò)技術(shù)發(fā)展過程中對安全性的忽視，導(dǎo)致了網(wǎng)絡(luò)環(huán)境中存在各式各樣的安全隱患，嚴重威脅著網(wǎng)絡(luò)運營及合法用戶的信息安全。從根本上講，敵手通常利用網(wǎng)絡(luò)中存在的脆弱性逐步滲透并控制若干網(wǎng)絡(luò)節(jié)點，達到惡意目的。因此，尋找并彌補威脅網(wǎng)絡(luò)關(guān)鍵資源的關(guān)鍵脆弱性，是提高網(wǎng)絡(luò)安全性的一種有效方法。網(wǎng)絡(luò)脆弱性彌補分析(MCNHA， minimum-cost network hardening analysis)以尋找并彌補威脅關(guān)鍵目標的代價最小的網(wǎng)絡(luò)脆弱性為目標，是一個NPC問題，目前尚無足夠有效的算法應(yīng)對大規(guī)模復(fù)雜網(wǎng)絡(luò)[1～10]。

MCNHA涉及的問題包括：如何確定彌補方案空間，如何判定彌補方案有效，如何確定彌補方案代價，最重要也是最困難的是如何求解代價最小并且有效的彌補方案。確定彌補方案空間的關(guān)鍵在于確定可能會對關(guān)鍵目標構(gòu)成威脅的全部脆弱性，一種有效的方法是使用攻擊圖[1～10]確定可能威脅到關(guān)鍵目標的全部脆弱性，它能充分反映給定網(wǎng)絡(luò)環(huán)境中的脆弱性之間的利用依賴，攻擊圖也可以確定彌補方案的有效性判定法則。彌補方案的代價取決于彌補方案的實施難度，以及相關(guān)脆弱性彌補后對網(wǎng)絡(luò)環(huán)境的影響的評估。求解代價最小并且有效的彌補方案在于如何快速地從2O(n)規(guī)模的彌補方案空間中選出代價最小的有效的方案，這是一個 NPC問題。因此，設(shè)計高效的策略，在有限的計算資源下快速尋找代價盡可能小的有效彌補方案，是MCNHA應(yīng)對大規(guī)模復(fù)雜網(wǎng)絡(luò)的唯一出路。

基于以上分析，與MCNHA相關(guān)的研究工作主要涉及攻擊圖構(gòu)建與分析和代價最小化彌補 2方面，下面分別介紹這2方面的研究現(xiàn)狀。

攻擊圖構(gòu)建與分析技術(shù)是MCNHA的基礎(chǔ)[1～10]，攻擊圖作為一種網(wǎng)絡(luò)防御分析的工具，其基本思想已提出10多年。具體地，Swiler[11]于1998年最早提出了攻擊圖模型，使用攻擊模型來描述一致的攻擊行為，并通過手工方式從目標狀態(tài)反向的生成攻擊圖。文獻[12～14]引入了自動分析技術(shù)，提高了攻擊圖的構(gòu)建效率。Lippmann[15，16]總結(jié)了過去的攻擊圖分析技術(shù)，并提出了基于攻擊圖的網(wǎng)絡(luò)安全評估與彌補方法。Ou[17，18]提出了單目標攻擊圖構(gòu)建算法，并發(fā)現(xiàn)了含圈攻擊路徑現(xiàn)象。陳峰[7，8，19，20]提出了一種生成多目標攻擊圖的算法，并從威脅概率的角度分析攻擊路徑，得出了長攻擊路徑在實際網(wǎng)絡(luò)攻擊中通常不會發(fā)生的結(jié)論。苘大鵬[21]以評估網(wǎng)絡(luò)整體安全性為目標，提出了通過限定攻擊步數(shù)和狀態(tài)節(jié)點可達性的策略，降低攻擊圖的復(fù)雜度，進一步提高攻擊圖的生成效率。此外，研究者們還提出了多種方法來增強攻擊圖的可理解性和可視化效果[22～24]。攻擊圖的構(gòu)建與分析經(jīng)歷了從手工到自動分析，從簡單到復(fù)雜的過程，現(xiàn)有的技術(shù)雖然在構(gòu)建效率、可理解性和可視化等方面仍存在不足，但基本滿足MCNHA的需求。

在代價最小化彌補方面，Jha[1]基于狀態(tài)攻擊圖尋找保障目標網(wǎng)絡(luò)關(guān)鍵信息資產(chǎn)安全的最小安全措施集。Noel S等[2]提出了基于屬性攻擊圖的最小成本安全彌補措施集，但是該方法不能應(yīng)用大型的具有含圈攻擊路徑的攻擊圖。Wang[3]解決了攻擊圖的含圈問題，但不能應(yīng)用于大規(guī)模攻擊圖。Homer[4]提出了一種基于邏輯攻擊圖的自動化網(wǎng)絡(luò)配置管理方法，但在攻擊圖規(guī)模較大時應(yīng)用情況仍然不佳。司加全[5]提出了一種可操作性較強的基于安全損失關(guān)鍵度最大優(yōu)先原則的網(wǎng)絡(luò)安全增強策略，但沒有分析在大規(guī)模復(fù)雜網(wǎng)絡(luò)環(huán)境中的應(yīng)用情況。陳峰[6～8]提出了基于二叉決策圖的最優(yōu)彌補集精確計算方法和基于貪婪策略的近似計算方法，前者較Wang的方法有較大性能提升，但仍只能應(yīng)用于小規(guī)模網(wǎng)絡(luò)環(huán)境；后者引入了n-有效路徑的概念，是一種可應(yīng)用于大規(guī)模網(wǎng)絡(luò)的計算方法，但適用范圍仍有較大限制。Albanese[9]提出了一種時間效能近似最小的方案，可以獲得較高的近似比率，但沒有考慮求解所用的計算資源和求解精度問題。

針對MCNHA，本文提出了一種基于隨機松弛優(yōu)選策略的網(wǎng)絡(luò)脆弱性彌補分析算法(MCNHASLOS， minimum- cost network hardening algorithm based on stochastic loose optimize strategy)，依據(jù)概率論的思想，在彌補方案空間的一系列隨機松弛子空間中迭代求解代價最小的彌補方案，并依據(jù)其有效性判定結(jié)果更新近似最優(yōu)彌補方案，使其逐步逼近最優(yōu)彌補方案。算法具有求解速度快、耗費/收益比高、精度可控等優(yōu)點，適合在大規(guī)模網(wǎng)絡(luò)環(huán)境中應(yīng)用。

2 基本概念和前提假設(shè)

為了突出網(wǎng)絡(luò)脆弱性彌補分析的重點和難點，且方便后文敘述，本節(jié)明確若干基本概念、前提假設(shè)和符號約定。

彌補方案空間。由所有可能的彌補方案組成的集合，記為Plan-Space。假定目標網(wǎng)絡(luò)中可能威脅到關(guān)鍵目標的脆弱性總數(shù)為n，分別用{1， 2， …，n}標記這n個脆弱性，則可用n位二進制數(shù)來表示Plan-Space，這樣每個彌補方案Plan對應(yīng)一個n位二進制數(shù)，為“1”的位置表示對應(yīng)的脆弱性需要彌補，即(0)2≤(Plan)2≤(2n-1)2，其中，(0)2是平凡無效彌補方案，對任何彌補目標都無效，而(2n-1)2則是平凡有效彌補方案，對任何彌補目標都有效，同時彌補代價也最高。

最優(yōu)彌補方案。彌補方案空間中代價最小的有效彌補方案，記為Opt-Plan。

近似最優(yōu)彌補方案。近似最優(yōu)方法求解得到的有效彌補方案，記為Approx-Opt-Plan。

彌補方案代價計算函數(shù)。計算彌補方案代價的函數(shù)，記為Cost()。

彌補方案有效判定函數(shù)。判定彌補措施是否有效的函數(shù)，記為Valid()。

彌補方案松弛子空間。從Plan-Space中隨機選取若干項構(gòu)成的子空間，記為Sparse-Space。

優(yōu)勢彌補方案空間和優(yōu)勢比率。依據(jù)Cost()和優(yōu)勢比率Psuperior可將彌補方案空間Plan-Space劃分成 2部分，低代價部分稱為優(yōu)勢空間，記為Superior-Space。Superior-Space中的彌補方案至少比Plan-Space中|Plan-Space|(1-Psuperior)個彌補方案的代價低，Psuperior體現(xiàn)了用戶對近似最優(yōu)彌補方案Approx-Opt-Plan的代價最優(yōu)性期望，Psuperior越小，用戶對Approx-Opt-Plan的代價最優(yōu)性期望越高。

有效彌補方案空間和有效比率。依據(jù)Valid()可將彌補方案空間Plan-Space劃分成有效彌補方案空間和無效彌補方案空間，將前者記為Valid-Space，|Valid-Space|與|Plan-Space|之比稱為有效比率，記為PValid。反映了關(guān)鍵目標受威脅程度，PValid越高關(guān)鍵目標越容易受到攻擊。

目標空間。優(yōu)勢空間和有效空間相交的部分，記為Goal-Space。Goal-Space中的彌補方案既滿足優(yōu)勢比率的要求，又滿足有效性的要求，體現(xiàn)了用戶對Approx-Opt-Plan期望的可滿足性，Goal-Space的規(guī)模愈小，用戶的期望愈難滿足，當Goal-Space為空時，表明用戶的期望無法滿足。

目標達成概率。Approx-Opt-Plan落入Goal-Space中的概率。

前提假設(shè)1。彌補方案空間Plan-Space已知。對于給定的網(wǎng)絡(luò)環(huán)境和關(guān)鍵目標，通過攻擊圖自動生成算法可以生成各種形式的攻擊圖，依據(jù)攻擊圖可以確定關(guān)鍵目標的彌補方案空間。如果將攻擊圖中存在攻擊路徑到達關(guān)鍵目標的脆弱性組成的集合稱為相關(guān)脆弱性集合，那么相關(guān)脆弱性集的冪集即為彌補方案空間。為了突出網(wǎng)絡(luò)脆弱性彌補分析的重點和技術(shù)難點。從大規(guī)模的Plan-Space中尋找落入Goal-Space中的Plan，約定Plan-Space已知。

前提假設(shè)2。彌補方案有效性判定函數(shù)Valid()已知。如果將能夠到達關(guān)鍵目標的每條攻擊路徑表示成脆弱性的析取子句，那么所有析取子句的合取即構(gòu)成關(guān)鍵目標的彌補方案有效性判定邏輯表達式Valid()，對于一個給定的Plan，Valid(Plan)=1就表示Plan有效。為了突出重點和技術(shù)難點，約定Valid()已知。

符號約定。為了敘述方便，約定文中出現(xiàn)的符號及其含義，如表1所示。

表1 符號約定

3 隨機松弛優(yōu)選原理

網(wǎng)絡(luò)脆弱性彌補分析的重點和技術(shù)難點在于如何從大規(guī)模的Plan-Space中快速尋找到落入Goal-Space中的Plan，實際上這是一個狀態(tài)空間搜索問題。對于大規(guī)模的復(fù)雜網(wǎng)絡(luò)環(huán)境，Plan-Space可能很大，為了加速收斂，提出了一種隨機松弛優(yōu)選策略 (SLOS， stochastic loose optimize strategy)，并提出了一種基于SLOS的網(wǎng)絡(luò)脆弱性彌補分析算法 (MCNHA-SLOS， minimum-cost network hardening algorithm based on stochastic loose optimize strategy)。SLOS的基本原理稱為隨機松弛優(yōu)選原理(SLOP， stochastic loose optimize principal)，首先描述并證明SLOP。

隨機松弛優(yōu)選原理：將一個集合Universe劃分成 2個子集Low和High，Low中元素的個數(shù)與Universe中元素的個數(shù)之比為PL；從Universe中隨機選取一個元素，則該元素屬于集合Low的概率為PL，屬于集合High的概率為1-PL；從Universe中隨機選取N個元素，則其中包含Low中元素的概率為1-(1-PL)N。因此無論集合Universe有多少元素，也無論PL有多小，只要取一個適當大小的數(shù)N，就可以保證 1-(1-PL)N≈1，也就是從Universe中隨機選取N個元素，其中至少有一個元素存在于集合Low中的概率幾乎為1。

隨機松弛優(yōu)選原理的證明非常簡單，如圖 1所示。

圖1 隨機松弛優(yōu)選原理證明

4 網(wǎng)絡(luò)脆弱性彌補分析算法

4.1 算法思想

MCNHA-SLOS思想：為了同時滿足代價最小和有效彌補2項指標，MCNHA-SLOS迭代地應(yīng)用SLOP，每次迭代都從Plan-Space的一個NSparse規(guī)模的Sparse-Space中選取代價最小的彌補方案Min-Plan，并依據(jù)Valid(Min-Plan)更新近似最優(yōu)方案Approx-Opt-Plan，通過Niterate次迭代使Approx-Opt-Plan落入Goal-Space的概率PGoal幾乎為1。

對于給定的優(yōu)勢比率Psuperior，通過Niterate次NSparse規(guī)模的Sparse-Space迭代，目標達成概率PGoal為可以證明無論PSuperior和PValid有多小，都可以選取適當?shù)腘iterate和NSparse使PGoal幾乎為1。

MCNHA-SLOS巧妙地運用了隨機松弛優(yōu)選策略，將全空間的優(yōu)化問題轉(zhuǎn)化為階段性的松弛子空間的優(yōu)化問題，將NP難度的求解問題轉(zhuǎn)化為精度可控的、可快速求解的迭代運算。

4.2 算法描述

MCNHA-SLOS的偽代碼如圖2所示。首先，將2n-1賦予近似最優(yōu)彌補方案Approx-Opt-Plan，表示所有的脆弱性都需要彌補，這必然是有效的，并且具有最大的彌補代價。接下來進行Niterate輪迭代，在每輪迭代中，首先將Approx-Opt-Plan賦予臨時的代價最小方案Min-Plan；再利用GeneratePlan()產(chǎn)生NSparse個隨機方案Plan，每產(chǎn)生一個Plan，計算其代價Cost(Plan)，并與Min-Plan的代價Cost(Min-Plan)進行比較，若Cost(Plan)＜Cost(Min-Plan)，則將Min-Plan更新為Plan；NSparse次迭代結(jié)束后，判定Min-Plan的有效性，若Valid(Min-Plan)為真，則將Approx-Opt-Plan更新為Min-Plan。Niterate輪迭代結(jié)束后，輸出近似最優(yōu)彌補方案Approx-Opt-Plan，算法結(jié)束。

2)應(yīng)能在少量參考數(shù)據(jù)的基礎(chǔ)上，保證較大的預(yù)測準確性。豎井掘進機在實際工作條件下，每掘進一個進程即得到一次有效的偏斜測量數(shù)據(jù)，測量數(shù)據(jù)離散不連續(xù)，且只有最近幾個進程的偏移對實際預(yù)測有指導(dǎo)意義。這要求預(yù)測系統(tǒng)能夠在較少的數(shù)據(jù)基礎(chǔ)上，達到準確的預(yù)測效果。

圖2 MCNHA-SLOS算法偽代碼

4.3 算法分析

精確求解MCNH問題是在Plan-Space中尋找Opt-Plan，其理論搜索量為2n次，在馮·諾依曼計算結(jié)構(gòu)下，當n較大時該問題是不可解的。而MCNHA-SLOS算法則是通過NiterateNSparse次搜索以很高的概率得到落入Goal-Space的Approx-Opt-Plan。具體地，PGoal、PSuperior、PValid、NSparse、Niterate之間關(guān)系滿足式(1)。

從式(1)可以看出，在網(wǎng)絡(luò)環(huán)境和關(guān)鍵目標給定的情況下，PValid是固定的；在目標空間Goal-Space確定的情況下，PSuperior也是固定的。因此無論PSuperior和PValid有多小，總可以選取適當?shù)腘Sparse和Niterate，使PGoal幾乎為1，也就是使Approx-Opt-Plan幾乎必定落入Goal-Space，達到用戶的期望。

通俗地講，MCNHA-SLOS算法將2n量級的精確求解問題，轉(zhuǎn)化成了NiterateNSparse量級的近似求解問題，將不可能在有效時間內(nèi)求得最優(yōu)解的問題轉(zhuǎn)化為可以在有效時間內(nèi)獲得滿意的近似最優(yōu)解問題，并且可以依據(jù)擁有的計算資源和可容忍的時間控制求解精度，非常適合在大規(guī)模網(wǎng)絡(luò)環(huán)境下應(yīng)用。

5 實例分析

本節(jié)通過一個簡單的實例演示 MCNHA-SLOS算法的計算流程，如圖3所示。

圖3 網(wǎng)絡(luò)脆弱性彌補分析實例

圖3中有V1～V5共5個脆弱性可能威脅到關(guān)鍵目標 Target，彌補這 5 個脆弱性的代價分別為(2， 2， 3，3， 1)，有效性判定函數(shù)Valid(Plan)=(V1||V4) &&(V2||V4) && (V3||V5)。簡化攻擊圖下方是一串隨機數(shù)，可以轉(zhuǎn)化為隨機生成的彌補方案。不難看出代價最小彌補方案為(00011)2，即彌補脆弱性V4和V5可以有效防護關(guān)鍵目標Target，且彌補代價最小，有效比率PValid=15/32≈0.47，Plan-Space中的方案按彌補代價排序后的結(jié)果如表2所示，其中加粗顯示的為有效彌補方案。

在本實例的計算過程中，將NSparse取為2，并且將GeneratePlan()取為 Rand()%25，MCNHASLOS的具體演算過程如圖4所示。

圖4 MCNHA-SLOS算法示例演算

在實例中，如果令PSuperior= 0.5，則Goal-Space={(00011)2， (11001)2}，PGoal= (1-(1-0.5)2)×(1-(1-0.47)5)≈ 0.72，而實際的計算結(jié)果Approx-Opt-Plan= (00011)2∈Goal-Space，實際上已經(jīng)找到了最優(yōu)方案，而搜索量是5×2 = 10，較32的全空間搜索量要少很多。

6 實驗分析

表2 依代價排序的彌補方案空間

為了便于分析攻擊圖技術(shù)的相關(guān)算法，設(shè)計實現(xiàn)了目標網(wǎng)絡(luò)建模演示系統(tǒng)(Net-MD， network modeling and demonstrating system)和網(wǎng)絡(luò)脆弱性綜合分析系統(tǒng)(Net-VA， network vulnerability analyzing system)。Net-MD可用于快速構(gòu)建各種規(guī)模的模擬網(wǎng)絡(luò)環(huán)境，并將網(wǎng)絡(luò)環(huán)境信息存儲在數(shù)據(jù)庫中；Net-VA可獲取數(shù)據(jù)庫中的網(wǎng)絡(luò)環(huán)境數(shù)據(jù)，應(yīng)用不同的算法生成目標網(wǎng)絡(luò)的攻擊圖，并將攻擊圖存儲在數(shù)據(jù)庫中。

實驗分為2組，第一組為MCNHA-SLOS的參數(shù)分析，通過觀察在不同參數(shù)設(shè)置下的實驗結(jié)果，明確各參數(shù)在算法中所起的作用，制定合理的參數(shù)設(shè)定策略；第二組在合理的參數(shù)設(shè)定策略基礎(chǔ)上對比MCNHA-SLOS算法與其他算法的性能差異?？紤]到MCNHA-SLOS算法的統(tǒng)計特性，采取多次實驗取平均數(shù)據(jù)的方法。為了討論方便，在實驗中假定所有脆弱性的彌補代價相同，都取為1，因此彌補方案的代價只取決于包含的脆弱性數(shù)量。

6.1 參數(shù)分析

利用Net-MD構(gòu)建了200個網(wǎng)絡(luò)節(jié)點規(guī)模的模擬網(wǎng)絡(luò)環(huán)境，并以粗線框的4個服務(wù)器為關(guān)鍵目標，如圖5所示。利用Net-VA生成了30個脆弱性規(guī)模的攻擊圖，如圖 6所示。并基于此圖對 MCNHASLOS進行參數(shù)分析。

6.1.1NSparse和Niterate分析

針對以上網(wǎng)絡(luò)環(huán)境和攻擊圖，首先觀察在NSparse和Niterate取不同值時 MCNHA-SLOS的計算結(jié)果，并分析NSparse和Niterate的最佳取值原則，為此將GeneratePlan()固定為Rand()%230。

首先，固定NSparse為16，隨著Niterate的增加，觀察Approx-Opt-Plan的彌補代價變化情況。如圖7所示，左邊部分代表Approx-Opt-Plan的平均代價，右邊部分代表花費的時間，可以看出，隨著Niterate的增加，計算時間的消耗逐漸增長，而Approx-Opt-Plan的平均代價則穩(wěn)步降低。說明算法迭代的次數(shù)越多獲得的平均代價就越低，越能接近最低代價。

圖5 模擬網(wǎng)絡(luò)環(huán)境

圖6 攻擊圖

圖7 MCNHA-SLOS算法耗費收益對比

從表3所列詳細實驗結(jié)果可以看出，當Niterate為32時，有多達17次平凡有效彌補方案出現(xiàn)，同時也有代價低至10的彌補方案出現(xiàn)；而當Niterate增加到8192時，Approx-Opt-Plan的彌補代價基本穩(wěn)定在 8和9。這充分體現(xiàn)了MCNHA-SLOS的統(tǒng)計特性，即使計算投入量很小，也有可能獲得較好的有效彌補方案，隨著計算資源投入的增加，所獲得的有效彌補方案的彌補代價在統(tǒng)計意義上穩(wěn)步下降。

接下來，觀察不同的NSparse取值對Approx-Opt-Plan平均代價的影響，以確定NSparse的取值原則。如圖8所示，當Niterate較小時(如32， 128)，NSparse的取值越小，Approx-Opt-Plan的平均代價越??；當Niterate較大時(如 2 048， 8 192)，NSparse的取值越大，Approx-Opt-Plan的平均代價越小，但差別并不顯著。結(jié)合表4所示的詳細數(shù)據(jù)，其中“()”中表示的是平均計算時間(s)，可以看出，當Niterate較大時，Approx-Opt-Plan的平均代價隨著NSparse的增加而降低，而計算時間在增加，總體上Approx- Opt-Plan的平均代價隨著計算時間投入(NiterateNSparse)的增加而穩(wěn)步下降，NSparse的取值對算法的影響不大。綜合考慮，認為NSparse應(yīng)當盡量取小一點。

圖8 不同NSparse的比較

6.1.2GeneratePlan()分析

在上文中都將GeneratePlan()取為Rand()%2n，實際上這并不是一個好的策略，從第5節(jié)的實例分析中可以看出，彌補方案空間低代價區(qū)的有效方案只有2個，而Rand()%2n所產(chǎn)生的Plan均勻分布于Plan-Space。每輪迭代通過在NSparse個Plan中選取代價最低的Min-Plan，它為有效方案的概率會很低，這將導(dǎo)致Approx-Opt-Plan很長時間才能得到更新。相反，如果彌補方案空間低代價區(qū)的有效方案較多，Min-Plan為有效方案的概率就會較高，這樣Approx-Opt-Plan就會經(jīng)常更新。如果能夠依據(jù)Plan-Space中有效彌補方案的比率PValid，改變由GeneratePlan()控制生成的Plan的分布范圍，就能夠提高MCNHA-SLOS的效率。

在Plan的定長二進制表示下，(Plan)2包含的“1”越多，則Plan有效的概率就越高，用Density(Plan)表示(Plan)2中“1”的個數(shù)與(Plan)2長度的比值，稱其為方案 1密度； 并為GeneratePlan()引入?yún)?shù)density來控制其所產(chǎn)生方案的1密度。新的GeneratePlan()定義為

表3 MCNHA-SLOS實驗結(jié)果

其中，如果Rand()%10 ＜density× 1 0，則xi=1，如果Rand()%10 ≥density×10，則xi=0。而GeneratePlan()=Rand()%2n實際上是當density=0.5時式(2)的退化形式。本節(jié)固定NSparse為5，觀察density的不同取值對Approx-Opt-Plan平均代價的影響。

對于圖 5所示的網(wǎng)絡(luò)環(huán)境和圖 6所示的攻擊圖，實驗結(jié)果如圖9所示。當density取0.3時，由GeneratePlan()產(chǎn)生的Plan有效的概率較低，Approx-Opt-Plan難以更新，因此當Niterate較小時，Approx-Opt-Plan的平均代價維持在較高的水平(包含較多的平凡有效彌補方案)，但當Niterate=8192時，Approx-Opt-Plan的平均代價迅速下降至較低的水平；當density取0.7時，由GeneratePlan()產(chǎn)生的Plan有效的概率較高，Approx-Opt-Plan比較容易更新，因此當Niterate較小時，Approx-Opt-Plan的平均代價就達到了較低的水平，但由于density較大，由GeneratePlan()產(chǎn)生的Plan的代價始終維持在較高的水平，當Approx-Opt-Plan的平均代價降至一定程度后，就很難再有明顯下降；當density取0.5和0.45時，由GeneratePlan()產(chǎn)生的Plan有效的概率比較合理，使Approx-Opt-Plan的平均代價隨著Niterate的增加能夠迅速下降，并且當Niterate較大時也能維持比較明顯的下降趨勢，相比較而言，density取0.45較0.5具有更好的效果。

圖9 不同density的比較

合理地選取density，實際上取決于網(wǎng)絡(luò)環(huán)境和攻擊圖本身，當攻擊圖中到達關(guān)鍵目標的路徑較密集時，關(guān)鍵目標就越容易遭受攻擊，同時也越難彌補，這種情況下density就應(yīng)該選取較大的值；而當?shù)竭_關(guān)鍵目標的路徑較稀疏時，則應(yīng)選取較小的density。

6.2 算法對比

目前為止，已有不少針對MCNH問題的求解方法，但真正能夠應(yīng)用于大規(guī)模復(fù)雜網(wǎng)絡(luò)的卻很少，其中陳峰提出的近似求解算法weighted-Greedy[7，8]具有較好的效果。因此將 MCNHA-SLOS與 weighted-Greedy進行對比。為公平起見，在相同的軟硬件環(huán)境(Intel Core Duo T7500 2.2 GHz CPU， 2 GB RAM，Windows XP)中運行2種算法。Weighted-Greedy算法通過|C|×|L|來控制算法的復(fù)雜度，其中C表示脆弱性利用的所有初始前提屬性，為方便討論，假定每個脆弱性只有唯一的前提初始屬性，而L代表所有的n-有效攻擊路徑。為了對比2種算法在不同問題難度下的性能，利用Net-MD構(gòu)建了5個不同的網(wǎng)絡(luò)環(huán)境：Net1，200個網(wǎng)絡(luò)節(jié)點，10個脆弱性；Net2，200個網(wǎng)絡(luò)節(jié)點，20個脆弱性；Net3，200個網(wǎng)絡(luò)節(jié)點，30個脆弱性；Net4，200個網(wǎng)絡(luò)節(jié)點，40個脆弱性；Net5，200個網(wǎng)絡(luò)節(jié)點，50個脆弱性。利用Net-VA構(gòu)建了相應(yīng)的攻擊圖，并統(tǒng)計出相應(yīng)的n-有效攻擊路徑的個數(shù)分別為：16、116、244、975和2 297。

實驗中，為MCNHA-SLOS選擇適當?shù)膁ensity，將NSparse取為5，并依據(jù)|C|×|L|來設(shè)定相應(yīng)的Niterate，使2個算法具有相近的計算量，在此基礎(chǔ)上對比2個算法求得Approx-Opt-Plan的平均代價。如圖10所示，當網(wǎng)絡(luò)環(huán)境和攻擊圖的復(fù)雜程度較低時，weighted-Greedy較 MCNHA-SLOS有更好的計算結(jié)果，但隨著問題復(fù)雜程度的增加，MCNHA-SLOS的優(yōu)勢逐漸顯現(xiàn)，在Net4和Net5下，MCNHA-SLOS得到的Approx-Opt-Plan的平均代價明顯低于weighted-Greedy，并且這種趨勢隨著問題復(fù)雜程度的增加越來越明顯。通過對比實驗，MCNHA-SLOS能夠適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)環(huán)境下的MCNH問題求解。

圖10 MCNHA-SLOS和weighted-Greedy算法比較

7 結(jié)束語

MCNH一直受到研究者的關(guān)注，目前針對它的研究工作主要集中2個方面：一方面是如何構(gòu)建高效攻擊圖，包括智能化、可視化等；另一方面是在現(xiàn)有的攻擊圖技術(shù)的基礎(chǔ)上，如何使用其他輔助手段進行高效的、低代價的彌補分析。隨著網(wǎng)絡(luò)安全問題的日益凸顯以及網(wǎng)絡(luò)規(guī)模和復(fù)雜性的擴大，對這些問題的研究還會更加深入和復(fù)雜，也一定會受到持續(xù)關(guān)注。

本文討論了 MCNH問題涉及的基本問題，并針對其NP難解性，提出了一種近似最優(yōu)求解算法MCNHA-SLOS，運用隨機松弛優(yōu)選策略，將全空間的優(yōu)化問題轉(zhuǎn)化為階段性的松弛子空間的優(yōu)化問題，將NP難度的問題求解轉(zhuǎn)化為精度可控的、可快速求解的迭代運算。網(wǎng)絡(luò)維護者可依據(jù)現(xiàn)有計算資源，選擇適當?shù)膮?shù)，利用 MCNHA-SLOS算法獲得滿意的近似最優(yōu)彌補方案。實驗表明，MCNHA-SLOS較現(xiàn)有算法在求解復(fù)雜MCNH問題時具有顯著優(yōu)勢，能夠適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)環(huán)境。MCNHA-SLOS雖然能夠適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)環(huán)境，但仍有需要深入研究的地方，下一步的研究工作主要是：1）NSparse和Niterate之間的關(guān)系；2）如何對density進行合理取值使算法具有更好的性能；3）在可實現(xiàn)規(guī)模的真實環(huán)境中測試。

[1] JHA S， SHEYNER O， WING J M. Two formal analyses of attack graphs[A]. Proceedings of 15th IEEE Computer Security Foundations Workshop[C]. 2002.

[2] NOEL S， JAJODIA S， O'BERRY B， JACOBS M，et al. Efficient minimum-cost network hardening via exploit dependency graphs[A].Proceedings of 19th Annual Computer Security Applications Conference[C]. 2003.86-95.

[3] WANG L Y， NOEL S， JAJODIA S. Minimum-cost network hardening using attack graphs[J]. Computer Communications， 2006，29(18)：3812-3824.

[4] HOMER J，et al. From Attack Graphs to Automated Configuration Management-An Iterative Approach[R]. Kansas State University Technical Report， 2008.

[5] SI J Q， ZHANG B， MAN D P，et al. Approach to making strategies for network security enhancement based on attack graphs[J]. Journal on Commurtications， 2009，30(2)：123-128.

[6] CHEN F， WANG L Y， SU J S. An efficient approach to minimum-cost network hardening using attack graphs[A]. Proceedings of the 4th International Conference on Information Assurance and Security[C].2008.209-212.

[7] CHEN F， ZHANG Y， SU J S，et al. Two formal analyses of attack graphs[J]. Journal of Software， 2010，21(4)： 838-848.

[8] CHEN F. A Hierarchical Network Security Risk Evaluation Approach Based on Multi-goal Attack Graph[D]. National University of Defense Technology， 2008.

[9] ALBANESE M， JAJODIA S， NOEL S. Time-efficient and cost- effective network hardening using attack graphs[A]. Proceedings of the 42nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)[C]. 2012.1-12.

[10] DIAMAH A， MOHAMMADIA M， BALACHANDRAN B. Network security evaluation method via attack graphs and fuzzy cognitive maps[J]. Intelligent Decision Technologies. 2012， 16： 433-440.

[11] SWILER L P， PHILLIPS C， ELLIS D，et al. Computer-attack graph generation tool[A]. Proceedings of DARPA Information Survivability Conference &Exposition II[C]. 2001.307-321.

[12] SHEYNER O， HAINES J， JHA S，et al. Automated generation and analysis of attack graphes[A]. Proceedings of IEEE Symposium on Security and Privacy[C]. 2002.273-284.

[13] SHEYNER O. Scenario Graphs and Attack Graphs[D]. Carnegie Mellon University， 2004.

[14] AMMANN P， WIJESEKERA D， KAUSHIK S. Scalable， graph-based network vulnerability analysis[A]. Proceedings of the 9th ACM Conference on Computer and Communications Security[C]. 2002.217-224.

[15] LIPPMANN R P，et al. An Annotated Review of Past Papers on Attack Graphs[R]. MIT Lincoln Laboratory， 2005.

[16] LIPPMANN R P， INGOLS K W， SCOTT C，et al. Evaluating and Strengthening Enterprise Network Security Using Attack Graphs[R].ESC-TR-2005-064， MIT Lincoln Laboratory， 2005.

[17] OU X M， GOVINDAVAJHALA S， APPEL A W. MulVAL： a logic-based network security analyzer[A]. Proceedings of 14th USENIX Security Symposium[C]. 2005.8.

[18] OU X M， BOYER W F， MCQUEEN M A. A scalable approach to attack graph generation[A]. Proceedings of 13th ACM conference on Computer and Communications Security[C]. 2006.336-345.

[19] CHEN F， TU R， ZHANG Y，et al. Two scalable approaches to analyzing network security using compact attack graphs[A]. Proceedings of International Symposium on Information Engineering and Electronic Commerce[C]. 2009.90-94.

[20] CHEN F， SUN J S， HAN W B. AI planning-based approach of attack graph generation[J]. Journal of PLA University of Science and Technology， 2008，9(5)：460-465.

[21] MAN D P， ZHOU Y， YANG W，et al. Method to generate attack graphs for assessing the overall security of networks[J]. Journal on Commurtications， 2009，30(3)：1-5.

[22] HOMER J， VARIKUTI A， OU XM，et al. Improving attack graph visualization through data reduction and attack grouping[A]. Proceedings of 5th International Workshop on Visualization for Cyber Security[C]. 2008.68-79.

[23] HARBORT Z， LOUTHAN G， HALE J. Techniques for attack graph visualization and interaction[A]. Proceedings of the Seventh Annual Workshop on Cyber Security and Information Intelligence Research[C]. 2011.

[24] ALHOMIDI M A， REED M J. Attack graphs representations[A].Proceedings of 4th Computer Science and Electronic Engineering Conference (CEEC)[C]. 2012. 83-88.