趙光勝，程慶豐，孫永林

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

彌補(bǔ)方案代價(jià)計(jì)算函數(shù)。計(jì)算彌補(bǔ)方案代價(jià)的函數(shù)，記為Cost()。

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

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

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

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

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

目標(biāo)達(dá)成概率。Approx-Opt-Plan落入Goal-Space中的概率。

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

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

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

表1 符號約定

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

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

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

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

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

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

4.1 算法思想

MCNHA-SLOS思想：為了同時(shí)滿足代價(jià)最小和有效彌補(bǔ)2項(xiàng)指標(biāo)，MCNHA-SLOS迭代地應(yīng)用SLOP，每次迭代都從Plan-Space的一個(gè)NSparse規(guī)模的Sparse-Space中選取代價(jià)最小的彌補(bǔ)方案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迭代，目標(biāo)達(dá)成概率PGoal為可以證明無論P(yáng)Superior和PValid有多小，都可以選取適當(dāng)?shù)腘iterate和NSparse使PGoal幾乎為1。

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

4.2 算法描述

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

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

圖2 MCNHA-SLOS算法偽代碼

4.3 算法分析

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

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

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

5 實(shí)例分析

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

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

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

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

圖4 MCNHA-SLOS算法示例演算

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

6 實(shí)驗(yàn)分析

表2 依代價(jià)排序的彌補(bǔ)方案空間

為了便于分析攻擊圖技術(shù)的相關(guān)算法，設(shè)計(jì)實(shí)現(xiàn)了目標(biāo)網(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)用不同的算法生成目標(biāo)網(wǎng)絡(luò)的攻擊圖，并將攻擊圖存儲在數(shù)據(jù)庫中。

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

6.1 參數(shù)分析

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

6.1.1NSparse和Niterate分析

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

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

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

圖6 攻擊圖

圖7 MCNHA-SLOS算法耗費(fèi)收益對比

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

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

圖8 不同NSparse的比較

6.1.2GeneratePlan()分析

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

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

表3 MCNHA-SLOS實(shí)驗(yàn)結(jié)果

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

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

圖9 不同density的比較

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

6.2 算法對比

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

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

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

7 結(jié)束語

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

本文討論了 MCNH問題涉及的基本問題，并針對其NP難解性，提出了一種近似最優(yōu)求解算法MCNHA-SLOS，運(yùn)用隨機(jī)松弛優(yōu)選策略，將全空間的優(yōu)化問題轉(zhuǎn)化為階段性的松弛子空間的優(yōu)化問題，將NP難度的問題求解轉(zhuǎn)化為精度可控的、可快速求解的迭代運(yùn)算。網(wǎng)絡(luò)維護(hù)者可依據(jù)現(xiàn)有計(jì)算資源，選擇適當(dāng)?shù)膮?shù)，利用 MCNHA-SLOS算法獲得滿意的近似最優(yōu)彌補(bǔ)方案。實(shí)驗(yàn)表明，MCNHA-SLOS較現(xiàn)有算法在求解復(fù)雜MCNH問題時(shí)具有顯著優(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進(jìn)行合理取值使算法具有更好的性能；3）在可實(shí)現(xiàn)規(guī)模的真實(shí)環(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.