基于改進蟻群算法的網絡風險分析與防御加固技術

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

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

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

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

1 攻擊圖模型分析

1.1 屬性攻擊圖

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

圖1 屬性攻擊圖示例

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

1.2 關鍵攻擊集分析

當然在一般的大規模網絡安全風險評估工作中,往往會通過攻擊圖優化算法對其進行簡化,一方面提高了攻擊圖的可理解性;另一方面也大大降低后續安全防御加固的成本[7]。

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

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

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

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

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

圖2 攻擊圖實例

在圖2中可以看到能夠到達攻擊目標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個攻擊機得到重點加固,則目標的可達路徑則全部被封堵。

1.3 關鍵集蟻群算法求解

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

(1)

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

(2)

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

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

(3)

因此求解最優解的過程就是蟻群所擁有的最優路徑,定義概率函數為:

(4)

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

2 基于改進蟻群算法的關鍵節點描述

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

2.1 要素動態更新

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

(5)

式中:q是概率隨機數,其與下一節點的路徑決策呈負相關。

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

(6)

(7)

2.2 局部搜索機制

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

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

因此針對局部搜索機制優化可以表達為數學目標:

(8)

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

3 實驗結果與分析

3.1 算法分析

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

表1 實驗設定Tab.1 Test set

圖3 適應性變化曲線

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

3.2 仿真實驗

3.2.1Oliver問題實驗分析

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

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

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

3.2.2仿真實驗

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

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

在其他參數條件保持一致的情況下,實驗結合一般蟻群算法和改進蟻群算法在其最優的參數設定下計算最小關鍵攻擊集和搜索時長,通過大量的實驗樣本整理最小關鍵攻擊集的數量統計如表4所示。

表4 最小攻擊集的數量統計Tab.4 Statistics of min attack set

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

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

(a) 最小攻擊集數對比

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

3.2.3攻擊概率

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

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

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

4 結語

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