李遠(yuǎn)敏（廈門理工學(xué)院計算機(jī)與信息工程學(xué)院，福建廈門361024）

層次化分類淘汰法的網(wǎng)絡(luò)最優(yōu)彌補(bǔ)模型

李遠(yuǎn)敏
（廈門理工學(xué)院計算機(jī)與信息工程學(xué)院，福建廈門361024）

針對求解最優(yōu)彌補(bǔ)的特點和需求，利用層次化分類淘汰，提出一種基于層次化分類淘汰法的最優(yōu)彌補(bǔ)模型（HSE－ONHM），得到最優(yōu)彌補(bǔ)的精確解.為了驗證HSE－ONHM的可行性和有效性，分別采取窮舉法和層次化淘汰算法求解同一目標(biāo)網(wǎng)絡(luò)環(huán)境的最優(yōu)彌補(bǔ).實驗結(jié)果表明：無論是淘汰次數(shù)還是CPU消耗時間，層次化分類淘汰法比窮舉法優(yōu)越；層次化分類淘汰法的計算時間隨著初始屬性節(jié)點數(shù)量呈指數(shù)增加，該實驗結(jié)果與算法性能分析結(jié)果一致.

最優(yōu)彌補(bǔ)模型；層次化淘汰算法；窮舉法；網(wǎng)絡(luò)安全

網(wǎng)絡(luò)脆弱性評估的目的之一是為網(wǎng)絡(luò)管理者及用戶提供最優(yōu)彌補(bǔ)，提高目標(biāo)網(wǎng)絡(luò)系統(tǒng)的安全性［1－6］.由于采取不同的安全彌補(bǔ)措施需要花費(fèi)不同的成本代價，最優(yōu)彌補(bǔ)即在有限資源的前提下，以最小的成本代價保證目標(biāo)網(wǎng)絡(luò)系統(tǒng)正常、安全運(yùn)行.Phillips等［7］首次提出了最優(yōu)彌補(bǔ)建議的分析方法，但該方法由于分析過于簡單，其準(zhǔn)確性有待進(jìn)一步考察.Sheyner等［8－9］提出了一種攻擊圖自動生成方法，并基于攻擊圖對最優(yōu)彌補(bǔ)建議進(jìn)行了理論分析.Homer等［10］認(rèn)為安全彌補(bǔ)措施提高目標(biāo)網(wǎng)絡(luò)系統(tǒng)的安全性的同時，會受到多種條件的約束，基于此，利用邏輯攻擊圖提出了一種自動化網(wǎng)絡(luò)配置管理方法.該方法通過多次迭代分析，最終會給出權(quán)衡了各種約束的網(wǎng)絡(luò)配置方案.本文提出了一種基于層次化分類淘汰法的網(wǎng)絡(luò)最優(yōu)彌補(bǔ)模型（HSE－ONHM），能得到最優(yōu)彌補(bǔ)的精確解.

1 網(wǎng)絡(luò)最優(yōu)彌補(bǔ)模型

求解最優(yōu)彌補(bǔ)時，若只彌補(bǔ)一個初始屬性節(jié)點能保證目標(biāo)網(wǎng)絡(luò)系統(tǒng)正常、安全運(yùn)行，且需耗費(fèi)的成本代價為a，則其他所有的除彌補(bǔ)該初始屬性節(jié)點外，仍彌補(bǔ)其他初始屬性節(jié)點的彌補(bǔ)策略，需耗費(fèi)的成本代價必須大于a.根據(jù)代價最小原則，應(yīng)將這些策略淘汰.

基于此，為了得到目標(biāo)網(wǎng)絡(luò)系統(tǒng)最優(yōu)彌補(bǔ)的精確解，對精確搜索方法進(jìn)行了改進(jìn)，提出一種基于層次化分類淘汰法的最優(yōu)彌補(bǔ)模型（HSE－ONHM）.該模型首先根據(jù)攻擊圖中的初始屬性節(jié)點進(jìn)行分類；然后，對彌補(bǔ)策略進(jìn)行層次化淘汰，依據(jù)代價最小原則，淘汰成本代價相對比較大的彌補(bǔ)策略，直至分類中的所有彌補(bǔ)策略都被淘汰，與此同時，得到最優(yōu)彌補(bǔ).

在具體的實現(xiàn)過程中，該方法主要分為兩個步驟.

步驟1 將彌補(bǔ)策略進(jìn)行分類.

步驟2 將淘汰成本代價大的彌補(bǔ)策略.

若彌補(bǔ)初始屬性節(jié)點c1能保證目標(biāo)網(wǎng)絡(luò)系統(tǒng)正常、安全運(yùn)行，即g（｛10…0｝）＝0，根據(jù)代價最小原則，則除彌補(bǔ)c1外，仍彌補(bǔ)其他初始屬性節(jié)點的彌補(bǔ)策略都應(yīng)被淘汰.設(shè)1－彌補(bǔ)｛cN＝1｝，使g（x）＝0，其中，N為初始屬性節(jié)點的編號.具體的淘汰規(guī)則為

淘汰2－彌補(bǔ)中的彌補(bǔ)策略：2i＋2j，0≤i≤n－1，i≠N，j＝N；

淘汰3－彌補(bǔ)中的彌補(bǔ)策略：2i＋2j＋2k，0≤i≤j≤n－1，i，j≠N，k＝N；

淘汰n－彌補(bǔ)中的彌補(bǔ)策略：2i＋2j＋…＋2m，0≤i＜j＜…＜s≤n－1，i，j，…，s≠N，m＝N.

具體有以下4個淘汰步驟.

步驟1 依次判斷1－彌補(bǔ)｛ci＝1｝中的彌補(bǔ)策略.

步驟2 若g（x）≠0，將該策略從1－彌補(bǔ)中淘汰.

步驟3 若g（x）＝0，令N＝i，并將彌補(bǔ)代價與cost比較.若彌補(bǔ)代價≥cos t，按照淘汰規(guī)則逐層淘汰彌補(bǔ)策略；若彌補(bǔ)代價cos t，則cos t＝彌補(bǔ)代價，然后，按照淘汰規(guī)則逐層淘汰彌補(bǔ)策略.

步驟4 依次類推，直至所有的彌補(bǔ)策略都被淘汰.即1－彌補(bǔ)，2－彌補(bǔ)，…，n－彌補(bǔ)都為空，與此同時，得到最優(yōu)彌補(bǔ).

2 算法復(fù)雜度分析

目標(biāo)網(wǎng)絡(luò)系統(tǒng)中主機(jī)數(shù)量為H，初始屬性節(jié)點數(shù)量為C.在具體的實現(xiàn)過程中，首先，分析1－彌補(bǔ)中的彌補(bǔ)策略；然后，分析2－彌補(bǔ)中的彌補(bǔ)策略；依次類推，1－彌補(bǔ)算法的復(fù)雜度比其他彌補(bǔ)算法的復(fù)雜度要高.因此，該算法的時間復(fù)雜度即1－彌補(bǔ)算法的時間復(fù)雜度.

在1－彌補(bǔ)算法中，主要有兩個子函數(shù)：彌補(bǔ)策略淘汰子函數(shù)和彌補(bǔ)策略判斷子函數(shù).其中，前者的目標(biāo)是依據(jù)淘汰規(guī)則逐層淘汰xn的彌補(bǔ)策略，后者的目標(biāo)是判斷該彌補(bǔ)策略是否已被淘汰.

彌補(bǔ)策略判斷子函數(shù)的時間復(fù)雜度為O（C），在彌補(bǔ)策略淘汰子函數(shù)中，首先，將十進(jìn)制彌補(bǔ)策略轉(zhuǎn)換為二進(jìn)制形式，時間復(fù)雜度為O（C）；然后，遍歷［xa，xb）中的所有彌補(bǔ)策略，依次判斷該策略是否被淘汰，時間復(fù)雜度為O（｜xb－xa｜）·O（C）.［xa，xb）為彌補(bǔ)策略中包含未被淘汰彌補(bǔ)策略的最小敬意，｜xb－xa｜≤2C.因此，彌補(bǔ)策略淘汰子函數(shù)的時間復(fù)雜度為

在1－彌補(bǔ)算法中，依次判斷1－彌補(bǔ)中的彌補(bǔ)策略，時間復(fù)雜度為O（C）.若該彌補(bǔ)策略的g（x）＝0，調(diào)用彌補(bǔ)策略淘汰子函數(shù)，按照淘汰規(guī)則逐層淘汰彌補(bǔ)策略，時間復(fù)雜度為O（2C）·O（C）；然后，計算該彌補(bǔ)策略的彌補(bǔ)代價，時間復(fù)雜度為O（C）；將彌補(bǔ)代價與cos t比較，若彌補(bǔ)代價小于cos t，則cos t等于彌補(bǔ)代價，按照淘汰規(guī)則逐層淘汰彌補(bǔ)策略，時間復(fù)雜度為O（2C）·O（C）.因此，1－彌補(bǔ)算法的時間復(fù)雜度為

3 實驗結(jié)果與分析

為了驗證HSE－ONHM的可行性和有效性，分別采取窮舉法（算法1）和層次化淘汰算法［12］（算法2）求解同一目標(biāo)網(wǎng)絡(luò)環(huán)境的最優(yōu)彌補(bǔ).實驗環(huán)境如下：服務(wù)器為PowerEDGE R710；操作系統(tǒng)為RetHAT V5.4；內(nèi)存為32GB；CPU為2.26GHz.無論是淘汰次數(shù)還是CPU消耗時間，層次化淘汰算法比窮舉法要優(yōu)越很多；層次化淘汰算法的計算時間會隨著初始屬性節(jié)點數(shù)量呈指數(shù)增加，該實驗結(jié)果與算法性能分析結(jié)果一致.

步驟1 求約束條件g（x）.假設(shè)攻擊者的攻擊目標(biāo)是屬性節(jié)點c15，g（x）為

由于g（x）＝0，因此，屬性節(jié)點c15不能被滿足，即e11，c11，e10，c12構(gòu)成的循環(huán)路徑在實際的應(yīng)用中是不存在的，而且該循環(huán)路徑涉及的節(jié)點c15，e13，c13，e11，c11，e10，c12應(yīng)被刪除.

簡單的攻擊圖，如圖1所示.簡化的攻擊圖，如圖2所示.

圖1 簡單攻擊圖示例Fig.1 Simple attack graph example

圖2 簡化攻擊圖Fig.2 Simplified attack graph

步驟2 利用HSE－ONHM求最優(yōu)彌補(bǔ).在步驟1獲得g（x）的基礎(chǔ)上，求攻擊目標(biāo)c9的最優(yōu)彌補(bǔ)，令彌補(bǔ)初始屬性節(jié)點的成本代價為｛cos t（c1），cos t（c5），cos t（c14），cos t（c16），cos t（c17）｝＝｛2，4，3，5，6｝.求解過程，如表1所示.表1中：淘汰策略列中｛c17＝1｝表示逐層淘汰｛c17＝1｝的彌補(bǔ)策略.

在HSE－ONHM中，雖然對初始屬性節(jié)點采取了二進(jìn)制編碼，將彌補(bǔ)策略轉(zhuǎn)化成了二進(jìn)制序列，但在具體的實現(xiàn)過程中，為了提高算法的性能和效率，將二進(jìn)制序列轉(zhuǎn)化成了十進(jìn)制數(shù).由表1可知：最優(yōu)彌補(bǔ)為｛c1，c5，c14，c16，c17｝＝｛1，0，0，0，0｝，即只彌補(bǔ)初始屬性c1，并且彌補(bǔ)成本代價為2.

表1 HSE－ONHM的求解過程Tab.1 Solving process of the HSE－ONHM

4 結(jié)束語

網(wǎng)絡(luò)脆弱性評估方法的最終目標(biāo)之一，針對實際的目標(biāo)網(wǎng)絡(luò)系統(tǒng)，得到該網(wǎng)絡(luò)的最優(yōu)彌補(bǔ)，從而指導(dǎo)網(wǎng)絡(luò)安全管理者有針對性地進(jìn)行保護(hù).運(yùn)用基于層次化分類淘汰法的最有彌補(bǔ)模型求解最優(yōu)彌補(bǔ)，對彌補(bǔ)策略進(jìn)行層次化淘汰，依據(jù)代價最小原則，淘汰成本代價相對比較大的彌補(bǔ)策略，直至分類中的所有彌補(bǔ)策略都被淘汰，從而得到最優(yōu)彌補(bǔ).

［1］ YEH W C.A Revised layered－network algorithm to search for all d－minpaths of a limited－flow acyclic network［J］.IEEE Transations on Reliability，1998，47（4）：436－442.

［2］ IN Yongkun.A Simple algorithm for reliability evaluation of a stochastic－flow network with node failure［J］.Computers and Operations Research，2001，28（13）：1277－1285.

［3］ 駱劍鋒，陳俞強(qiáng).采用環(huán)加星型網(wǎng)絡(luò)結(jié)構(gòu)負(fù)載均衡集群技術(shù)的云平臺設(shè)計［J］.華僑大學(xué)學(xué)報（自然科學(xué)版），2016，37（2）：164－167.

［4］ CHEN Run，MO Yong，PAN Zhan.Performance improvement of edge expansion technique for BDD－based network reliability analysis［J］.Journal of Computers 2013，8（9）：2190－2196.

［5］ JHA S，SHEYNER O，WING J M.Two formal analyses of attack graphs［C］∥Proceedings of 15th IEEE Computer Security Foundations Workshop.Ottawa：IEEE Press，2002：234－238.

［6］ NOEL S，JAJODIA S，O＇BERRY B，et al.Efficient minimum－cost network hardening via exploit dependency graphs ［C］∥Proceedings of 19th Annual Computer Security Applications Conference.Hangzhou：IEEE Press，2003：86－95.

［7］ PHILLIPS C，SWILER L.A graph－based system for network vulnerability analysis［C］∥Proc of the New Security Paradigms Workshop.Charlottesville：User Evaluation，1998：71－79.

［8］ SHEYNER O，HAINES J，JHA S，et al.Automated generation and analysis of attack graphs［C］∥Proc of the IEEE Symposm on Security and Privacy.Oakland：IEEE Computer Society Press，2002：254－265.

［9］ SHEYNER O.Scenario graphs and attack graphs［D］.Pittsburgh：Carnegie Mellon University，2004：256－257.

［10］ HOMER J.A comprenhensive approach to enterprise network security management［D］.Manhattan：Kansas State University，2008：148－150.

［11］ WANG Lingyu，NOEL S，JAJODIA S.Minimum－cost network hardening using attack graphs［J］.Computer Communications，2006，29（18）：3812－3824.

［12］ CHEN Feng，WANG Lingyu，SU Junshang.An efficient approach to minimum－cost network hardening using attack graphs［C］∥Proc of the Fourth International Conference on Information Assurance and Security.Tokyo：User E－valuation，2008：209－212.

（責(zé)任編輯：陳志賢 英文審校：吳逢鐵）

Optimal Network Hardening Model Based on Hierarchical Classification Elimination

LI Yuanmin
（College of Computer and Information Engineering，Xiamen University of Technology，Xiamen 361024，China）

This paper considers the characteristics and requirement of solving the optimal hardening problem.A new optimal network hardening model based on hierarchical separatal elimination（HSE－ONHM）is proposed and accurate solution for optimal hardening is got.In order to verify the feasibility and effectiveness of the model，the optimal exhaustive method and hierarchical algorithm is taken for elimination of the same target for network environment.Experimental results show that either eliminated or the number of CPU time consuming，HSE－ONHM is superior.The computation time of HSE－ONHM with initial attribute node increases exponentially with the number.The experimental results are consistent with the performance analysis of the algorithm.

optimal hardening model；hierarchical classification elimination algorithm；enumeration method；network security

TP 393

A

1000－5013（2016）04－0515－04

10.11830／ISSN.1000－5013.201604025

2016－01－20

李遠(yuǎn)敏（1970－），男，副教授，主要從事信息融合、嵌入式系統(tǒng)的研究.E－mail：cxllymin＠163.com.

福建省教育廳A類項目（JA09217）；廈門理工學(xué)院高層次人才科技項目（YKJ08013R）