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

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

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

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

1 攻擊圖模型分析

1.1 屬性攻擊圖

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

圖1 屬性攻擊圖示例

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

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

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

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

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

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

通過前序描述可以將其理解為數(shù)學(xué)表達(dá),設(shè)在某一個(gè)具體網(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)ω(α)達(dá)到1時(shí),上述數(shù)學(xué)問題則可以理解為無權(quán)重節(jié)點(diǎn)的最小碰撞集的計(jì)算,同時(shí)由于上述問題描述中集合中的所有元素都能夠滿足NP問題的前置要求,將攻擊圖轉(zhuǎn)換為最小碰撞集的數(shù)學(xué)問題,則可以將關(guān)鍵攻擊集分析定性為NP難問題。圖2為攻擊圖實(shí)例。

圖2 攻擊圖實(shí)例

在圖2中可以看到能夠到達(dá)攻擊目標(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},在通過最小碰撞集的計(jì)算后得到{N6,N9}、{N7,N9};這可以看出,如果這2個(gè)攻擊機(jī)得到重點(diǎn)加固,則目標(biāo)的可達(dá)路徑則全部被封堵。

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

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

(1)

同時(shí)在第i個(gè)節(jié)點(diǎn)在t時(shí)刻擁有的所有信息要素的總和為:

(2)

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

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

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

由于螞蟻算法存在著較快的收斂和后期搜索速度過慢等問題,致使算法在局部最優(yōu)解附近會(huì)產(chǎn)生停頓,無法計(jì)算全局最優(yōu)解。同時(shí)因?yàn)橐话阆伻核惴ㄗ陨淼恼蚍答仚C(jī)制,使得信息要素會(huì)產(chǎn)生路徑擁塞,從而造成早熟停滯的情況。為了解決這一問題,在蟻群算法中引入了自適應(yīng)的信息要素動(dòng)態(tài)更新原理,并引入了自適應(yīng)GA進(jìn)行上述問題的改進(jìn)[16-17]。

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

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

(5)

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

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

(6)

(7)

2.2 局部搜索機(jī)制

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

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

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

(8)

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 算法分析

為了驗(yàn)證2.2節(jié)中的局部搜索機(jī)制改進(jìn)策略合理性,選取了遺傳算法、自適應(yīng)排序作為基線進(jìn)行性能分析。其中設(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í)驗(yàn)設(shè)定Tab.1 Test set

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

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

3.2 仿真實(shí)驗(yàn)

3.2.1Oliver問題實(shí)驗(yàn)分析

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

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

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

3.2.2仿真實(shí)驗(yàn)

在本次仿真實(shí)驗(yàn)中,選取5種屬性攻擊圖,具體如表3所示。

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

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

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

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

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

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

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

3.2.3攻擊概率

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

表5 攻擊概率對(duì)比Tab.5 Comparison of attack probability

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

4 結(jié)語

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