基于SQAG模型的攻擊熵優化算法

張 俊,張安康,王 輝

(河南理工大學 計算機科學與技術學院,河南 焦作 454000)

0 概述

互聯網的快速發展能夠滿足社會各方面的現實需求,但也引發了越來越多的安全問題。根據國家互聯網應急中心發布的《2018年中國互聯網網絡安全報告》[1],截至2018年底,國家互聯網應急中心CNCERT/CC共接收到境內外報告的網絡安全事件106 700起。網絡安全事件的頻發給人們的正常工作與生活帶來很大的影響[2]。

為降低網絡空間面臨的安全風險,研究人員對網絡攻擊進行了建模。文獻[3]將貝葉斯網與攻擊圖相結合,利用近似貝葉斯推理預測大規模網絡路徑。文獻[4]利用貝葉斯推理對網絡進行動態風險評估。文獻[5]在利用貝葉斯預測攻擊路徑時引入時間增益補償率。文獻[6]通過貝葉斯推理直接求出所有節點的置信度。文獻[7]在假定目標節點被占據的條件下求出了其余節點的置信度。文獻[8]通過攻擊圖的置信度對網絡安全進行了合理度量。文獻[9]通過加固置信度較高的節點,降低了網絡系統被攻擊的風險,使其更加可靠。

本文通過SQAG模型對網絡攻擊進行建模,利用攻擊熵算法消除冗余路徑,運用聯結樹算法進行精確推理,從而獲得理想情況下節點置信度的預測值及消除冗余路徑后節點置信度的合理值。

1 相關研究

近年來,研究人員在網絡攻擊圖的基礎上利用貝葉斯推理對攻擊路徑進行預測。文獻[10]指出攻擊圖的路徑生成和路徑分析是攻擊圖的研究重點之一,明確了在當前的網絡攻擊圖研究中,當節點數增加時路徑數目的增加方式是一個NP難問題,但沒有給出減少冗余路徑的具體方法。

文獻[11]提出一個面向內部攻擊意圖推斷的概率攻擊圖模型,在模型中引入條件概率表來描述單步攻擊檢測結果的不確定,并在模型基礎上給出計算攻擊意圖的算法以及利用累積概率來預測最有可能發生的攻擊路徑的方法。該文中給出的起始節點概率是靜態的,如果對該模型引入時間維度,那么當防火墻收縮訪問尺度時,起始節點概率值將隨時間變化,模型可實現對整個攻擊過程中攻擊意圖的預測。

文獻[12]提出一種成本收益分析方法,其中風險系數隨時間呈指數級降低。將這種風險系數應用在一個包含多次試探攻擊的場景中時,攻擊時間會變長,但在沒有新的節點被占據的情況下,攻擊者對網絡結構的了解程度不會加深,攻擊經驗也不會增加,因此風險成本并不會隨時間以指數級的速度降低。

文獻[13]提出在滿足證據變量時間偏序關系的情況下,利用貝葉斯推理計算攻擊路徑節點置信度的方法。該方法采用似然加權法來近似計算節點置信度,但是在把一個攻擊過程分解為多個時間片段后,當每一個時間片段中的網絡攻擊圖對節點置信度的精度要求都比較高時,似然加權法將需要較大的樣本量,極大地增加了計算量。

為優化攻擊路徑,本文提出SQAG模型和攻擊熵優化算法,在現有資源狀態攻擊圖的基礎上引入時間和當前時刻已經占據的節點,轉換成時序貝葉斯網絡攻擊圖模型,根據聯結樹算法計算出某時刻各個節點的置信度。通過計算某一時刻的攻擊熵,進而計算出該時刻的攻擊風險成本,對基于深度優先搜索算法得出的攻擊路徑進行篩選,以實現對現有的攻擊路徑進行優化的目的。

2 時序網絡攻擊圖

在一個攻擊者為獲取目標節點而反復進行試探性攻擊操作的背景下,本文構造的時序網絡攻擊圖模型主要有3個目標:1)利用該模型對攻擊過程進行建模,預測任意時刻的攻擊路徑;2)根據當前時刻的時序網絡攻擊圖,對子攻擊路徑進行成本收益分析;3)使模型能夠體現出攻擊者在該時刻之前已經獲取的網絡結構、攻擊經驗等信息,并利用攻擊熵對其進行度量。為實現這些目標,在已有模型的基礎上進行擴展,添加時間和每一時刻已經占據的資源節點。本文構造的時序網絡攻擊圖模型及其參數定義如下:

定義1(時序網絡攻擊圖模型) SQAG=(T,R,A,E,W,P,Π)是與發生時刻對應的一組有向無環圖集。其中:

E=E1∪E2為關聯攻擊節點與資源節點的有向邊集合,E1?R×A表示只有當攻擊者成功占據資源節點之后攻擊行為才能發生,E2?R×A表示只有當攻擊行為發生之后才可以占據資源節點。

P=P1∪P2∪P3,其中,P1為初始節點發生的概率,P2=P(ai=true|Pre(ai)=true),Pre(ai)表示攻擊事件之前的資源節點取值,P3=P(Con(aj)=true|aj=true),Con(aj)表示攻擊事件之后的資源節點取值。

Π表示某一時刻攻擊圖中某一節點的置信度,Π(ri,ti)表示攻擊者在ti時刻成功占據節點ri的概率,Π(aj,ti)表示攻擊行為aj在ti時刻發生的概率。

根據以上定義,可以得出SQAG模型。用有向邊連接資源節點與攻擊行為節點,用深色標注攻擊者在該時刻曾經占據的資源節點,并綜合考慮and節點和or節點的幾種排列組合情況,生成時序網絡攻擊圖的主干結構。根據經驗定義起始節點的概率P1以及條件概率P2和P3,得到如圖1所示的時序網絡攻擊圖。

圖1 時序網絡攻擊圖Fig.1 Sequential network attack graph

如圖1所示,在t時刻,攻擊者已經成功占據的資源節點為Rc={r1,r2,r3,r4},新一輪的攻擊者以概率Pt1(R0)分別占據起始資源節點r1、r2、r3,攻擊行為a1、a2以條件概率P2發生,并以條件概率P3分別占據相對應的資源節點r4、r5、r6,最終向目標節點r7靠進。

3 基于SQAG模型的攻擊路徑

攻擊者在占據系統內全部目標資源節點前,從起始節點開始持續進行攻擊,若攻擊被阻斷,則回到起始節點開始新一輪的攻擊。為了能夠直觀地描述攻擊演進過程,在時序網絡攻擊圖的基礎上定義攻擊路徑。

定義2(攻擊路徑) 在t時刻,對于任意一個目標資源節點rn∈Rg,從起始節點R0開始,存在一組由資源節點和攻擊節點交替排列的序列r0,a1,r1,a2,…,aj,ri,…,rn,使得節點序列中任意2個相鄰節點間總有∈E1或∈E2(0

以圖1為例,攻擊者可以從起始節點r2和r3出發,經過a2、r6、a4最終到達目標節點r7,其中由r2∩r3、a2、r6、a4、r7按發生順序組成的節點序列即為一條攻擊路徑(符號∩表示節點間的and關系)。為便于表示攻擊路徑所包含的元素及其之間的關系,用某時刻的線序關系集來表示攻擊路徑,即STEPt-x={,,…,,…,},其中任意一個線序關系表示一條子攻擊路徑。在圖1中,t時刻通向節點Rg={r7}的3條攻擊路徑如下:

STEPt-1={,,

}

STEPt-2={,,

,}

STEPt-3={,,

r4>,,}

4 攻擊熵優化算法

攻擊者在時序網絡攻擊圖中任意時刻有多種占據目標節點的路徑方式。當某一時刻時序網絡攻擊圖的節點增多時,通向目標節點的攻擊路徑數量會呈指數級增長。為有效預測實際情況下可能出現的攻擊路徑,本文定義了攻擊熵,用以度量攻擊者對網絡結構的了解程度和所獲取的攻擊經驗。利用攻擊熵計算風險成本,進而將某一時刻下子攻擊路徑的成本值和收益值進行對比,達到優化攻擊路徑的目的。

4.1 攻擊熵的定義

定義3(攻擊熵) 攻擊熵是用來描述攻擊者對網絡結構了解程度和攻擊經驗平均不確定性的變量,結合時序網絡攻擊圖模型,推導其數學表達式如下:

設P(Attackt-r)是當前時刻未占據節點的聯合概率分布,表示為:

其中,Attackt-r是取值于離散聯合分布集R-Rc上的隨機變量,r∈{1,2,…,nr},nr為該時刻未占據節點的數目。

在此基礎上,定義攻擊熵如下:

隨著攻擊的演進,攻擊圖中未被占領的資源節點數目減少,而攻擊者對網絡結構了解加深,獲得的攻擊經驗增加,這使得信息的不確定性降低,表現為攻擊熵的數值降低,計算得出的風險成本也降低。

4.2 子攻擊路徑的成本分析

子攻擊路徑的成本由風險成本和操作成本兩部分構成。文獻[14]通過對子攻擊路徑的發生原因進行分析,提出操作成本cost(e)由元操作成本cost(meta-operation)和操作序列成本cost(sequence)兩部分組成,表示如下:

cost(e)=α×cost(meta-operation)+

β×cost(sequence)

(1)

其中,e表示子攻擊路徑。

除了攻擊操作需要花費成本外,攻擊者在實施網絡攻擊的過程中還要面臨被安全管理人員發現的風險,即需要承擔相應的風險成本。因此,在分析子攻擊路徑成本時,也要考慮風險因素對子攻擊路徑是否發生影響。

風險系數(用θ表示)是用來衡量某次攻擊行為在占領資源節點時被發現的可能性大小的一種度量,它一方面取決于攻擊目標對攻擊行為的影響系數(用M表示),攻擊目標越重要,管理者對其越重視,攻擊行為就越容易被檢測到;另一方面取決于攻擊行為自身的影響系數(用Γ表示),攻擊行為越復雜,被發現的可能性就越高;另外還取決于攻擊熵,攻擊熵越低,攻擊者規避風險的能力越強。因此,可以把風險系數θ定義為:

(2)

被攻擊目標ri越重要,攻擊者的操作aj復雜度越高,攻擊熵越大,從而暴露的風險也越大。根據以上分析,風險成本cost(r)可表示如下:

cost(r)=cost(e)×θ(e)

(3)

從式(3)可以看出,風險成本隨著風險系數的增長而增長,這符合實際攻擊中風險成本的增長趨勢。進而子攻擊路徑的攻擊成本可用下式計算:

cost(eji)=ε×cost(e)+μ×cost(r)

(4)

其中,ε和μ分別表示兩種成本的權重。

在某一時刻,當子攻擊路徑上獲得的收益大于成本時,認為該條子攻擊路徑是可行的,否則是不可行的。

4.3 攻擊熵優化算法

為解決時序網絡攻擊圖中攻擊路徑隨資源節點個數增加呈指數級增長的問題,本文運用攻擊熵優化算法對子路徑進行成本收益分析,以減少冗余路徑,縮小網絡攻擊圖的規模,具體算法如下:

算法1攻擊熵優化算法

輸入TSAG

輸出STEPt-x

1.n=nr+na

2.Init:matric:G.arc[n,n];G.rel[n,n];G.visited[n];

3.for each ri∈Rorai∈A

4.if ai,rj之間存在有向邊e

5.G.arc[i,j]=1

6.if ri,rj之間或者ai,aj之間存在and關系

7.G.rel[i,j]=1

8.if ri,rj之間或者ai,aj之間存在or關系

9.G.rel[i,j]=2

10.end for

11.//用矩陣存儲SQAG模型的攻擊關系與參數

12.for each ri∈R0

13.DFS(G,i)

14.G.visited[i]=true;

15.輸出G.visited[i];

16.for each j

17.if G.rel[i,j]=1

18.輸出G.visited[j];

19.//輸出當前訪問節點

20.Run ACCA

21.c=cost(eji)

22.if(G.arc[i,j]==1 && !G.visited[j]&&(c

23.//進行成本收益分析

24.i=j goto 第11行

25.end for

26.end for

在消除冗余路徑的過程中,為利用攻擊熵合理計算出風險成本,本文提出一種攻擊成本計算算法,具體步驟如下:

算法2攻擊成本計算算法

輸入SQAG

輸出cost(eji)

1.Init a=0;b=0;

2.for each ri∈R

3.if ri?Rc

4.a=a+1;

5.else b=b+1;

6.end for

7.//計算當前未占據節點和已占據節點

10.//計算當前時刻攻擊熵和最大攻擊熵

12.cos t(r)=cost(e)×θ(e)

13.cos t(eji)=ε×cost(e)+μ×cost(r)

算法1存儲了當前時刻攻擊圖的信息之后,計算出未占據的節點數,通過調用算法2計算出攻擊熵,對其進行歸一化,將資源重要性程度影響系數、攻擊行為自身影響系數、歸一化后的攻擊熵累乘計算出風險系數,進而計算出合理的風險成本,加上操作成本后得出攻擊成本,進而在算法1中進行成本收益分析,消除冗余路徑。攻擊熵優化算法利用攻擊熵這一參數將攻擊者在攻擊過程中已經獲取的網絡結構信息和攻擊經驗包含在內,使得風險成本的計算比較合理。

5 時序網絡攻擊圖中節點置信度的計算

在時序網絡攻擊圖模型的基礎上,利用貝葉斯推理計算節點置信度。相關學者采用似然加權法抽樣得出節點置信度的近似值[15-16],但是精度要求高時,似然加權法需要大量的抽樣。為能夠快速地得到每一時刻各個攻擊圖各條路徑上的節點置信度,本文選擇了精確推理中時間效率最高的算法,即聯結樹算法[17]。

定義4(團集) 團集(Clique,C)是由SQAG模型中某一時刻攻擊圖中3個節點組成集合的集合,其中3個節點組成的集合稱為團。

定義5(聯結樹) 聯結樹(Joint Tree,JT)是由SQAG模型的團集C中的元素Ci和有向邊集合S中的元素Sj連接成的樹狀結構。其中,團集和邊集滿足任何2個團Ci和Cj之間路徑上的每個邊包含于邊集S中,相鄰2個點之間的邊Sij=Ci∩Cj。令團C1={a3,a4,r7},團C2={a3,a4,a5},則S12為邊。

聯結樹算法步驟如下:

步驟1將時序網絡攻擊圖轉換為聯結樹

為將TSAG模型上的推理轉換成JT中的推理,需要將對應的時序網絡攻擊圖2(a)轉變為聯結樹JT=(C,S),將轉換過程分解為以下3步:

1)建立Moral圖

(1)找出時序網絡攻擊圖中每一個資源節點和攻擊節點的父節點。

(2)用無向邊將父節點兩兩相連。

(3)將有向邊改為無向邊。

如圖2(a)所示的時序網絡攻擊圖,其Moral圖為圖2(b)。

2)三角化Moral圖

將Moral圖中每一個大于或等于4的環的非相鄰節點用無向邊連接起來,實現Moral圖的三角化。

如圖2(b)所示的Moral圖,其三角化后的Moral圖為圖2(c)。

3)建立聯結樹

(1)確定所有的團集,其中團集是三角化后的Moral圖中最大全連通圖組成的集合,團集中每對不同的團都由無向邊連接。

(2)在團集中添加一些邊和分割節點構造出一棵聯結樹T。

圖2(c)為三角化后的Moral圖,其聯結樹如圖2(d)所示。

圖2 時序網絡攻擊圖轉換成聯接樹的過程Fig.2 Process of converting sequential network attack graph into joint tree

步驟2初始化聯結樹

聯結樹的初始化是對所有節點給定發生與否的概率,進而得到每個團的分布函數。由時序網絡攻擊圖構建的聯結樹中的團Ci由3個節點組成,其中每一個節點有2種狀態,則共有8種狀態組合。令Φi表示團Ci的分布函數,Φij代表團Ci第j個狀態組合的分布函數,初始化如下:

for eachΦij=1

步驟3消息傳遞

消息傳遞通過更新任意2個團之間的聯合概率分布,使得聯結樹達到全局一致狀態。如圖3所示是相鄰團的節點間進行的一次消息傳遞[18]。

圖3 一次消息傳遞過程
Fig.3 Process of a message delivery

從團Ci到團Cj進行一次消息傳遞包括以下3步:

1)產生消息:

(5)

2)吸收信息,更新團節點的分布函數ΦCj:

(6)

3)更新分隔節點的分布函數:

(7)

步驟4概率計算

步驟5條件概率計算

條件概率計算即是在SQAG模型中某些觀測到的節點值為True的條件下,計算另外的某個節點發生的條件概率。通過對聯結樹進行消息傳遞得到全局一致的聯結樹[20]。當聯結樹加入條件e后達到全局一致時,對任意的團節點C有ΦC=P(C,e),e表示加入的條件。

(8)

將某時刻的時序網絡攻擊圖轉換為聯結樹后,對聯結樹進行賦值,得到一個帶有狀態組合分布函數的聯結樹。通過團節點之間的消息傳遞,聯結樹達到全局一致。在這種狀態下,可得出任意節點的置信度。

6 算法仿真與驗證

在一個攻擊者為占據所有目標節點而不斷反復從起始節點進行攻擊的場景中,為證明該模型能夠較好地模擬出網絡攻擊節點置信度隨時間變化,本文設計如下實驗:首先在matlab軟件上實現聯結樹算法,建立防火墻隨時間收緊情況下的模型,結合聯結樹算法得出各條路徑上節點置信度隨時間的變化;其次在假設子攻擊路徑參數(收益、操作成本系數、風險成本系數)為定值的情況下,計算出某時刻優化后的攻擊路徑及各節點置信度。

以圖1的時序網絡攻擊圖為例,利用聯結樹算法推理計算節點的置信度,其中,條件概率P2=0.7,P3=0.5。隨著攻擊的進行,防火墻會收縮訪問尺度,故可根據經驗設定起始節點概率:

P(vi∈R0)=1-0.1×ti,

i=1,2,3,ti=0,1,2,3,4,5,6

以STEPt-1和STEPt-2為例,畫出在滿足上述假設的情況下7個時刻各條攻擊路徑上節點發生的置信度,如圖4所示,其中圖4(a)和圖4(b)攻擊路徑節點分別為r1、a1、r5、a4、r7和r2、r3、a2、r6、r7。

圖4 節點置信度隨時間的變化過程Fig.4 Change process of node confidence degree with time

在圖4(a)和圖4(b)中,隨著防火墻收縮訪問尺度,各條折線上從高到低的圓點分別代表STEPt-1和STEPt-2上7個時刻各節點置信度隨時間均呈下降趨勢。可以看出,隨著攻擊的演進,防火墻收縮訪問尺度,起始節點發生概率降低,導致該時刻此條路徑上的所有節點置信度都相應地降低。以上分析沒有考慮隨著攻擊熵的增加,某些子攻擊路徑的風險成本增加,導致攻擊路徑變化。

計算各個攻擊階段下對應Attackt-r的攻擊熵,如圖5所示。

圖5 攻擊熵與未占據節點個數的關系Fig.5 Relationship of attack entropy and number unoccupied nodes

經過長時間的攻擊之后,攻擊者未占據的節點隨時間逐漸減少,攻擊者對網絡系統不確定性的了解程度降低,攻擊經驗增加,攻擊熵也隨之降低。

根據經驗,設定圖1中的網絡系統某時刻攻擊權對應的子攻擊路徑上的攻擊參數如表1所示。運行算法1和算法2的代碼可得,攻擊權w1對應的子攻擊路徑上的成本小于收益,而攻擊權w2、w3、w4、w5對應的子攻擊路徑上的成本大于收益,從而可知利用算法1和算法2可合理刪除攻擊者認為不可能發生的子攻擊路徑,證明了該算法可以實現路徑優化。

表1 ti=6時子攻擊路徑上的攻擊參數Table 1 Attack parameters on sub-attack path at ti=6

為進一步描述優化后的攻擊路徑,利用聯結樹算法進行推理,計算STEP6-1和STEP6-2上各節點置信度如圖6所示,其中圖6(a)和圖6(b)攻擊路徑節點分別為r1、a1、r5、a4、r7和r2、r3、a2、r6、r7。由圖6可以看出,STEP6-1可行的攻擊路徑有{},STEP6-2可行的攻擊路徑有{},與圖4推演出的攻擊路徑對比可知,利用攻擊熵優化算法消除了冗余子攻擊路徑,進而利用聯結樹算法推理優化后的節點置信度更加接近實際情況。

圖6 STEP6-1和STEP6-2上的節點置信度Fig.6 Node confidence degree on STEP6-1 and STEP6-2

對于未使用攻擊熵優化算法的情況,即此時風險系數的計算方式為θ(e)=Γ(aj)×M(ri),進行優化后的攻擊路徑及其節點置信度如圖7所示 ,其中圖7(a)和圖7(b)攻擊路徑節點分別為r1、a1、r5、a4、r7和r2、r3、a2、r6、r7。

圖7 未運用攻擊熵時STEP6-1和STEP6-2上的節點置信度Fig.7 Node confidence degree on STEP6-1 and STEP6-2 without attack entropy

對比圖6和圖7可知,圖6中STEP6-1上a1和STEP6-2上a2置信度都不為0,而在圖7中它們的置信度為0。這是由于攻擊熵的引入使得在計算風險成本時,將攻擊者在多次試探性攻擊的過程中所獲取的攻擊經驗和對網絡結構的了解程度包含在內,導致攻擊者的風險成本變低,故可能發生的子攻擊路徑變多。由圖6和圖7對比可以看出,引入攻擊熵算法可合理消除冗余路徑。

7 結束語

對網絡攻擊進行合理建模并實時高效地預測攻擊路徑是網絡安全領域研究的熱點。本文在已有研究基礎上,提出時序攻擊圖模型和攻擊熵優化算法,通過定義在時序網絡攻擊圖中的攻擊熵概念,描述攻擊者對網絡結構了解程度的加深與攻擊經驗的增加對風險成本的影響,利用攻擊熵計算風險成本,合理地消除時序網絡攻擊圖中的冗余路徑。在使用攻擊熵優化算法合理減少冗余路徑后,應用精確推理中的聯結樹算法得到節點置信度的精確值,進而對攻擊路徑進行實時預測。本文所提算法沒有考慮防御者對攻擊方式的了解程序,因此在進行成本收益分析時,不能充分體現雙方的博弈過程,下一步將對此進行改進。