層次化分類淘汰法的網絡最優彌補模型

李遠敏（廈門理工學院計算機與信息工程學院，福建廈門361024）

層次化分類淘汰法的網絡最優彌補模型

李遠敏
（廈門理工學院計算機與信息工程學院，福建廈門361024）

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

最優彌補模型；層次化淘汰算法；窮舉法；網絡安全

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

1 網絡最優彌補模型

求解最優彌補時，若只彌補一個初始屬性節點能保證目標網絡系統正常、安全運行，且需耗費的成本代價為a，則其他所有的除彌補該初始屬性節點外，仍彌補其他初始屬性節點的彌補策略，需耗費的成本代價必須大于a.根據代價最小原則，應將這些策略淘汰.

基于此，為了得到目標網絡系統最優彌補的精確解，對精確搜索方法進行了改進，提出一種基于層次化分類淘汰法的最優彌補模型（HSE－ONHM）.該模型首先根據攻擊圖中的初始屬性節點進行分類；然后，對彌補策略進行層次化淘汰，依據代價最小原則，淘汰成本代價相對比較大的彌補策略，直至分類中的所有彌補策略都被淘汰，與此同時，得到最優彌補.

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

步驟1 將彌補策略進行分類.

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

若彌補初始屬性節點c1能保證目標網絡系統正常、安全運行，即g（｛10…0｝）＝0，根據代價最小原則，則除彌補c1外，仍彌補其他初始屬性節點的彌補策略都應被淘汰.設1－彌補｛cN＝1｝，使g（x）＝0，其中，N為初始屬性節點的編號.具體的淘汰規則為

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

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

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

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

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

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

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

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

2 算法復雜度分析

目標網絡系統中主機數量為H，初始屬性節點數量為C.在具體的實現過程中，首先，分析1－彌補中的彌補策略；然后，分析2－彌補中的彌補策略；依次類推，1－彌補算法的復雜度比其他彌補算法的復雜度要高.因此，該算法的時間復雜度即1－彌補算法的時間復雜度.

在1－彌補算法中，主要有兩個子函數：彌補策略淘汰子函數和彌補策略判斷子函數.其中，前者的目標是依據淘汰規則逐層淘汰xn的彌補策略，后者的目標是判斷該彌補策略是否已被淘汰.

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

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

3 實驗結果與分析

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

步驟1 求約束條件g（x）.假設攻擊者的攻擊目標是屬性節點c15，g（x）為

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

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

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

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

步驟2 利用HSE－ONHM求最優彌補.在步驟1獲得g（x）的基礎上，求攻擊目標c9的最優彌補，令彌補初始屬性節點的成本代價為｛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｝的彌補策略.

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

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

4 結束語

網絡脆弱性評估方法的最終目標之一，針對實際的目標網絡系統，得到該網絡的最優彌補，從而指導網絡安全管理者有針對性地進行保護.運用基于層次化分類淘汰法的最有彌補模型求解最優彌補，對彌補策略進行層次化淘汰，依據代價最小原則，淘汰成本代價相對比較大的彌補策略，直至分類中的所有彌補策略都被淘汰，從而得到最優彌補.

［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］ 駱劍鋒，陳俞強.采用環加星型網絡結構負載均衡集群技術的云平臺設計［J］.華僑大學學報（自然科學版），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.

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

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

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

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