基于并行遺傳算法的網絡最優(yōu)彌補模型

吳蓓

摘 要： 將攻擊圖與并行遺傳算法相結合，提出了一種基于并行遺傳算法的網絡最優(yōu)彌補模型（PGA?ONHM），該模型能得到目標網絡系統(tǒng)的近似解。為了驗證該模型的可行性、有效性和可擴展性，從不同的分析角度進行仿真驗證，實驗結果表明：并行遺傳算法的CPU消耗時間隨著初始屬性節(jié)點數量的增加呈多項式增加，隨著子群體數量的增加呈減小趨勢；無論是平均迭代次數還是單次迭代的平均計算時間，并行遺傳算法比經典遺傳算法都要優(yōu)越；并行遺傳算法可以得到較好的加速比，能夠克服局部最優(yōu)解的問題，可以適用于大規(guī)模復雜的網絡系統(tǒng)。

關鍵詞： 網絡脆弱性； 攻擊圖； 網絡脆弱性彌補； PGA?ONHM

中圖分類號： TN915.08?34 文獻標識碼： A 文章編號： 1004?373X（2016）05?0105?05

0 引 言

人類在享受互聯互通和信息共享帶來的便捷與效益的同時，網絡技術發(fā)展過程中對安全性的忽視，導致網絡環(huán)境中存在各式各樣的安全隱患，嚴重威脅著網絡運營及合法用戶的信息安全。因此，尋找并彌補威脅網絡關鍵資源的脆弱性是提高網絡安全性的一種有效方法。文獻[1]基于邏輯推理的方法，首先將最優(yōu)彌補求解問題轉化為布爾表達式；然后求解該布爾表達式的析取范式，從而得到所有的彌補措施；最后通過分析比較得到最優(yōu)彌補建議。該方法在最壞情況下具有不可避免的指數時間復雜度，無法應用于網絡規(guī)模較大的真實目標網絡系統(tǒng)。文獻[2]提出采用歸納有序二元決策圖（ROBDD）的方法求解最優(yōu)彌補。該方法可以有效地獲取攻擊圖的最優(yōu)彌補，但在該方法中，未對脆弱性進行度量標準的說明，因此在實際應用上具有一定的局限性。

由于求解最優(yōu)彌補問題是NP完全性問題，對于NP完全性問題，采用啟發(fā)式搜索方法可以更快地獲得結果。并行遺傳算法[3?6]具有以下優(yōu)勢：覆蓋面大，利于全局擇優(yōu)；對問題的依賴性較小，求解的魯棒性較好；具有并行計算的特點，可以用大規(guī)模的并行計算來提高計算速度；特別適用于復雜大系統(tǒng)問題的優(yōu)化求解，但其存在收斂速度慢、局部搜索能力差等不足之處。并行遺傳算法可以克服經典遺傳算法的不足，提高遺傳算法求解的速度和質量。基于此，本文將攻擊圖與并行遺傳算法相結合，提出了一種基于并行遺傳算法的網絡最優(yōu)彌補模型（Optimal Network Hardening Model Based on Parallel Genetic Algorithm，PGA?ONHM）。

3 實驗結果與分析

為了驗證PGA?ONHM模型的可行性、有效性和可擴展性，本文從不同分析角度做了兩組實驗，并對實驗結果進行了分析。實驗環(huán)境如下：服務器PowerEDGE R710，操作系統(tǒng)RetHAT V5.4，內存32 GB，CPU 2.26 GHz。

3.1 算法性能驗證實驗

由算法性能分析可知，該算法性能與目標網絡系統(tǒng)中初始屬性節(jié)點數量[C，]迭代次數[D，]子群體[U]等參數有關。為了驗證不同網絡環(huán)境下這些參數對算法性能的影響，在得到最優(yōu)解的前提下，分別設計了如下兩組實驗。

第一組實驗驗證初始屬性節(jié)點數量不同時，單次迭代的平均計算時間如圖3所示。由圖3可知，單次迭代的平均計算時間隨著初始屬性節(jié)點數量[C]的增加呈多項式增加趨勢。

第二組實驗驗證子群體數量（即處理器數量）對算法性能的影響。令初始屬性節(jié)點數量為500，當子群體數量不同時，單次迭代的平均時間如圖4所示。由圖4可知，單次迭代的平均計算時間隨著[U]的增加呈減小趨勢。

由上述兩組實驗結果可知，在PGA?ONHM模型中，算法CPU消耗的時間隨著初始屬性節(jié)點數量[C]的增加呈多項式增加趨勢，隨著子群體數量[U]的增加呈減小趨勢，實驗結果與算法性能分析結果一致。

3.2 算法對比實驗

（1） 經典遺傳算法和并行遺傳算法對比實驗，實驗結果如表1所示。表1列出了在初始屬性節(jié)點數量不同的情況下，求解最優(yōu)彌補時兩種算法的平均迭代次數和單次迭代的平均計算時間。

從實驗結果可以看出：一方面，針對同一目標網絡環(huán)境，無論是平均迭代次數還是單次迭代的平均計算時間，并行遺傳算法比經典遺傳算法都要優(yōu)越，其主要原因是在并行遺傳算法的具體實現過程中，首先將總群體分成若干子群體，然后將子群體分配到各自的處理機上，獨立地進行遺傳算法的進化操作，實現了從全局角度開發(fā)群體進化的并行性，從而提高了計算效率；另一方面，并行遺傳算法具有良好的可擴展性，當初始屬性節(jié)點數量達到2 000時，單次迭代的平均計算時間也不過7 ms。

（2） 加速比實驗。目前公認的評價并行遺傳算法性能的指標是加速比，即并行遺傳算法與經典遺傳算法完成等量工作所耗時間的比例，它標志著一個并行遺傳算法的好壞。本文在相同的硬件環(huán)境下，對同一目標網絡環(huán)境通過改變處理器數量，進行了加速比實驗，實驗結果如表2所示。加速比和處理器數量的關系如圖5所示。由圖5可知，加速比與處理器幾乎呈線性關系，因此，本文所提并行遺傳算法可以得到較好的加速比，是行之有效的并行手段。

4 結 論

PGA?ONHM模型通過建立數學模型將攻擊圖與并行遺傳算法相結合，得到最優(yōu)彌補的近似解。為了驗證該模型的可行性、有效性和可擴展性，本文從不同的分析角度做了兩組實驗，實驗結果表明：CPU消耗時間隨著初始屬性節(jié)點數量的增加呈多項式增加，隨著子群體數量的增加呈減小趨勢；無論是平均迭代次數還是單次迭代的平均計算時間，并行遺傳算法比經典遺傳算法都要優(yōu)越；加速比與處理器呈線性關系；能夠克服局部最優(yōu)解的問題，可以適用于大規(guī)模復雜的網絡系統(tǒng)。

參考文獻

[1] JHA S， SHEYNER O， WING J M. Two formal analyses of attack graphs [C]// Proceedings of 15th IEEE Conference on Computer Security Foundations Workshop. [S.l.]： IEEE， 2002： 49?63.

[2] NOEL S， JAJODIA S， O′BERRY B， et al. Efficient minimum?cost network hardening via exploit dependency graphs [C]// Proceedings of 19th Annual Conference on Computer Security Applications. [S.l.]： IEEE， 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. From attack graphs to automated configuration management： an iterative approach [R]. Kansas： 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 communications， 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 [C]// Procee?dings of 2008 the 4th International Conference on Information Assurance and Security. Naples： IEEE， 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]. Changsha： National University of Defense Technology， 2008.

[9] ALBANESE M， JAJODIA S， NOEL S. Time?efficient and cost?effective network hardening using attack graphs [C]// Proceedings of the 42nd IEEE/IFIP Annual International Conference on Dependable Systems and Networks. Boston： IEEE， 2012： 1?12.