吳海寧,杜 端,可 紅,張 超,鄭 舒

(湖北華中電力科技開發(fā)有限責(zé)任公司,湖北 武漢 430000)

對于愈加復(fù)雜的大規(guī)模網(wǎng)絡(luò)而言,隨著可能攻擊路徑的指數(shù)級增長,狀態(tài)攻擊圖需要大量的迭代與計算才能夠描述出所有的安全風(fēng)險,這也導(dǎo)致其性能大大降低,因此屬性攻擊圖模型應(yīng)運而生,其核心思想就是以最低成本進行網(wǎng)絡(luò)安全的加固[1]。

Sheyner使用模型檢測的方法來自動生成攻擊圖,雖然使用該方法可以生成所有的攻擊路徑,但存在狀態(tài)空間爆炸的問題[2]。Shiaeles等使用自定義方式生成多目標(biāo)完全攻擊圖,但它的時間復(fù)雜度較高[3]。目前對于大規(guī)模網(wǎng)絡(luò)的屬性攻擊圖大部分的研究基本集中在攻擊圖的構(gòu)建和簡化工作中,鮮有針對簡化后攻擊圖的求解優(yōu)化,因此文中基于一般蟻群算法的缺陷,提出了基于自適應(yīng)要素更新和自適應(yīng)遺傳算法的局部搜索機制的改進思路,以期提高網(wǎng)絡(luò)安全風(fēng)險評估的最小關(guān)鍵集求解和搜索性能。

1 攻擊圖模型分析

1.1 屬性攻擊圖

屬性攻擊模型中主要包含攻擊和屬性2類對象,其中攻擊節(jié)點代表被原子攻擊的節(jié)點,而屬性節(jié)點則代表攻擊的前后要素;同時在屬性攻擊圖模型中還包括需求關(guān)系和實現(xiàn)關(guān)系的邊,屬性攻擊模型的原理如圖1所示[4-6]。

圖1 屬性攻擊圖示例

在圖1中,“c*”文字代表屬性,圓形代表攻擊,如原子攻擊源表示為m,那么對于e1而言,它的執(zhí)行前提包括c1、c2,執(zhí)行輸出包括c5、c6。從屬性攻擊圖原理可以看出,其問題構(gòu)建表現(xiàn)出多項式級的復(fù)雜性,也就更適用于規(guī)模較大的網(wǎng)絡(luò)安全環(huán)境評估。

1.2 關(guān)鍵攻擊集分析

當(dāng)然在一般的大規(guī)模網(wǎng)絡(luò)安全風(fēng)險評估工作中,往往會通過攻擊圖優(yōu)化算法對其進行簡化,一方面提高了攻擊圖的可理解性;另一方面也大大降低后續(xù)安全防御加固的成本[7]。

在這里設(shè)攻擊圖AG=(Ns,Nm,Ne,E),其中Ns為初始化的屬性節(jié)點,在實際中則可以理解為攻擊人員所擁有的所有資源;Nm為實際可達的攻擊目標(biāo);Ne為所有的攻擊執(zhí)行;E為有向邊集合。因此,定義一個具體的攻擊目標(biāo)d,PATHS表示d可達的所有路徑;同時設(shè)C為d目標(biāo)中的所有攻擊節(jié)點集合;S為關(guān)鍵節(jié)點的集合,那么有?S∈PATHSS∩C≠?。定義N為S的最小節(jié)點集合,那么S′?N∧S′∈S永不成立。

那么對于屬性攻擊圖AG而言,設(shè)存在攻擊路徑Vi,將其進行序列狀態(tài)變換成N1,N2,N3…Nn,Ni∈E。那么一次完全的攻擊需要從狀態(tài)一條完整的路徑需要從N1持續(xù)到Ns,這樣Vi則表示為所有攻擊集的一個子集。

對于一個具體的s∈S,如果在攻擊庫中消除了C,那么在狀態(tài)s下是無法達成攻擊目的的;同理若C是s的關(guān)鍵攻擊集合。

通過前序描述可以將其理解為數(shù)學(xué)表達,設(shè)在某一個具體網(wǎng)絡(luò)中包含了原子攻擊集A,|A|=m。路徑集合C={A1,…,An},其中Ai?A?i={1,…,n},那么有A的碰撞集H?A,H∩Ai≠?,?i=1,…,n;設(shè)數(shù)學(xué)函數(shù)ω:ω(α)→Z+,那么有碰撞集最小目標(biāo)函數(shù)ω(H)=∑α∈HΣα∈Hω(α)。

當(dāng)ω(α)達到1時,上述數(shù)學(xué)問題則可以理解為無權(quán)重節(jié)點的最小碰撞集的計算,同時由于上述問題描述中集合中的所有元素都能夠滿足NP問題的前置要求,將攻擊圖轉(zhuǎn)換為最小碰撞集的數(shù)學(xué)問題,則可以將關(guān)鍵攻擊集分析定性為NP難問題。圖2為攻擊圖實例。

圖2 攻擊圖實例

在圖2中可以看到能夠到達攻擊目標(biāo)N11的路徑共有5條:{N1,N3,N6,N7,N10,N11}、{N1,N4,N6,N7,N10,N11}、{N1,N3,N6,N7,N11}、{N1,N9,N11}、{N1,N4,N6,N7,N11},在通過最小碰撞集的計算后得到{N6,N9}、{N7,N9};這可以看出,如果這2個攻擊機得到重點加固,則目標(biāo)的可達路徑則全部被封堵。

1.3 關(guān)鍵集蟻群算法求解

通過上述分析,采用蟻群算法來解決關(guān)鍵攻擊集的求解需要進行以下數(shù)學(xué)定義[8-9]:

(1)

同時在第i個節(jié)點在t時刻擁有的所有信息要素的總和為:

(2)

那么在t+1時刻,其增量的信息要素為:

τi(t+1)=ρτi(t)+Δ(τi(t))

(3)

因此求解最優(yōu)解的過程就是蟻群所擁有的最優(yōu)路徑,定義概率函數(shù)為:

(4)

式中:α為信息要素在整體網(wǎng)絡(luò)中權(quán)重,而β則代表貪心權(quán)重。那么當(dāng)α=0,β=1時,則代表了攻擊目標(biāo)可能存在路徑的最高概率選擇。這樣可以看出基于蟻群算法的關(guān)鍵集求解時間復(fù)雜度為o(n3),它能夠一定程度上解決大規(guī)模網(wǎng)絡(luò)最小關(guān)鍵集的最優(yōu)化計算問題,但由于蟻群算法的計算性能較低,計算時長較長,同時在不同的α、β參數(shù)條件下其計算結(jié)果差異較大,甚至?xí)霈F(xiàn)過快收斂從而只能達到結(jié)果局部最優(yōu)的情況,因此其收斂與性能穩(wěn)定性上并不能夠完全滿足要求[14-15]。

2 基于改進蟻群算法的關(guān)鍵節(jié)點描述

由于螞蟻算法存在著較快的收斂和后期搜索速度過慢等問題,致使算法在局部最優(yōu)解附近會產(chǎn)生停頓,無法計算全局最優(yōu)解。同時因為一般蟻群算法自身的正向反饋機制,使得信息要素會產(chǎn)生路徑擁塞,從而造成早熟停滯的情況。為了解決這一問題,在蟻群算法中引入了自適應(yīng)的信息要素動態(tài)更新原理,并引入了自適應(yīng)GA進行上述問題的改進[16-17]。

2.1 要素動態(tài)更新

對于蟻群算法的改進策略中,在路徑遍歷中下一路徑節(jié)點的選擇采用偽隨機比例的機制,其推導(dǎo)函數(shù)表示為:

(5)

式中:q是概率隨機數(shù),其與下一節(jié)點的路徑?jīng)Q策呈負(fù)相關(guān)。

那么式(5)可以轉(zhuǎn)換為:

(6)

(7)

2.2 局部搜索機制

為了解決蟻群算法在搜索過程中存在的后續(xù)性能較低的缺陷,前人提出了3-opt、遺傳算法等局部搜索機制來改進。文中提出了一種基于自適應(yīng)的遺傳算法來解決搜索性能的問題。具體做法是在每一次迭代后,都會對所獲得的攻擊集進行最優(yōu)調(diào)整,把所獲得的路徑相互重新配對,并可行解的計算進行增速,從而使算法的效果更好。

但由于一般的遺傳算法在適用大部分研究場景時都具有較大的魯棒性,因此根據(jù)蟻群的種族信息變化動態(tài)地設(shè)定交叉率和變異率。

因此針對局部搜索機制優(yōu)化可以表達為數(shù)學(xué)目標(biāo):

(8)

式中:X代表決策因子。那么整體改進思路為首先對蟻群的數(shù)量進行初始化,采用每一螞蟻周期計算一次攻擊集合的方式,并將各蟻群按其信息要素的動態(tài)更新機制選取的后續(xù)節(jié)點。并在每次迭代完畢時采用自適應(yīng)GA計算其循環(huán)數(shù)量,直至達到預(yù)設(shè)的數(shù)量后退出周期,從而獲得最小臨界攻擊集合。結(jié)果表明,該算法的迭代數(shù)量在時間復(fù)雜度上比傳統(tǒng)蟻群算法少,空間復(fù)雜度也更低。

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

3.1 算法分析

為了驗證2.2節(jié)中的局部搜索機制改進策略合理性,選取了遺傳算法、自適應(yīng)排序作為基線進行性能分析。其中設(shè)定種群的初始數(shù)量為60,迭代的上限為200次,一般遺傳算法的交叉變異設(shè)置為0.79、0.005 8,Adapt排序中分別設(shè)定μ1=0.368,μ2=1.4,μ3=1.8,μ4=2.0,其余設(shè)定如表1所示;3種算法的適應(yīng)性曲線如圖3所示。

表1 實驗設(shè)定Tab.1 Test set

圖3 適應(yīng)性變化曲線

由圖3可見,在早中期,自適應(yīng)遺傳算法的搜索性能一直非常有優(yōu)勢,直到160次后才開始逐漸放緩。另2種算法從30次迭代開始就一直處于快速下降的趨勢,并且在70次后搜索速率就已經(jīng)很低,超過100次迭代后搜索能力幾乎消失。

3.2 仿真實驗

3.2.1Oliver問題實驗分析

在實例仿真驗證中,結(jié)合TSPLIB的Oliver30問題進行實驗,蟻群算法的實驗設(shè)定如下:α=1,β=4,ρ=0.5,q= 0.5,迭代上限 500 次;實驗結(jié)果如表2所示。

表2 Oliver30問題實驗結(jié)果Tab.2 Experiment results of oliver 30 problem

由表2可知,改進的蟻群算法在Oliver30問題上求解結(jié)果,不管是最優(yōu)解還是平均解都更接近于TSPLIB官方的最優(yōu)解,最優(yōu)迭代次數(shù)比一般蟻群算法降低200次,因此可以看出基于要素動態(tài)更新和局部搜索機制的改進策略大大提高了最小關(guān)鍵攻擊集的求解性能。

3.2.2仿真實驗

在本次仿真實驗中,選取5種屬性攻擊圖,具體如表3所示。

表3 5種攻擊圖參數(shù)Tab.3 Parameters of five attack graphs

在其他參數(shù)條件保持一致的情況下,實驗結(jié)合一般蟻群算法和改進蟻群算法在其最優(yōu)的參數(shù)設(shè)定下計算最小關(guān)鍵攻擊集和搜索時長,通過大量的實驗樣本整理最小關(guān)鍵攻擊集的數(shù)量統(tǒng)計如表4所示。

表4 最小攻擊集的數(shù)量統(tǒng)計Tab.4 Statistics of min attack set

由表4可以看出,基于改進蟻群算法在最小攻擊集的計算能夠更大程度地避免攻擊路徑忽略。

算法比較和搜索時間的對比結(jié)果如圖4所示。

(a) 最小攻擊集數(shù)對比

從圖4可以看出,隨著網(wǎng)絡(luò)規(guī)模的復(fù)雜程度增大,攻擊路徑越來越多時,改進的蟻群算法在最優(yōu)解的計算上表現(xiàn)出更好的性能,并且搜索的運行時長也更低,比一般蟻群算法的搜索速率提高了9.11%。這可以得知,基于要素動態(tài)更新和局部搜索機制的蟻群算法改進更符合當(dāng)前復(fù)雜網(wǎng)絡(luò)風(fēng)險評估需求。

3.2.3攻擊概率

為了驗證基于改進蟻群算法網(wǎng)絡(luò)安全評估的實用價值,采用12個常見漏洞與標(biāo)準(zhǔn)漏洞評分CVSS和參考文獻[5]中方法的原子攻擊概率進行了比較,結(jié)果如表5所示。

表5 攻擊概率對比Tab.5 Comparison of attack probability

從表5可以看出,CVSS中超過一半的攻擊概率均為1,文獻[5]中攻擊概率基本都達到了80%;而文中提出方法的平均攻擊概率不超過30%,最高攻擊概率為65%。由此可以得出,基于要素動態(tài)更新和局部搜索機制的網(wǎng)絡(luò)安全評估加固能夠有效地降低網(wǎng)絡(luò)攻擊的達成率。

4 結(jié)語

文中結(jié)合屬性攻擊圖模型,分析了屬性攻擊圖中最小關(guān)鍵集的求解等同于NP問題的解決,同時在應(yīng)用蟻群算法進行計算時發(fā)現(xiàn)隨著網(wǎng)絡(luò)規(guī)模的增大,一般蟻群算法計算性能較低,計算運行時長較長;同時,在不同的參數(shù)條件下求解結(jié)果不穩(wěn)定,甚至?xí)霈F(xiàn)過快收斂從而只能達到結(jié)果局部最優(yōu)的情況。因此引出了基于動態(tài)要素更新和自適應(yīng)遺傳算法局部搜索機制的改進思路。通過算法分析和實驗對比可以看出,提出的算法在最小關(guān)鍵集的計算性能上得到了較大提升,迭代次數(shù)相較于一般蟻群算法減少了92%,搜索性能也得到了增強9.11%,同時對比與通用漏洞攻擊評分策略攻擊概率下降了40%,更適用于大規(guī)模網(wǎng)絡(luò)安全風(fēng)險的評估應(yīng)用。