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

吳蓓

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

關(guān)鍵詞： 網(wǎng)絡(luò)脆弱性； 攻擊圖； 網(wǎng)絡(luò)脆弱性彌補； PGA?ONHM

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

0 引 言

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

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

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

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

3.1 算法性能驗證實驗

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

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

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

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

3.2 算法對比實驗

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

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

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

4 結(jié) 論

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