基于吸收Markov鏈的網絡入侵路徑預測方法

胡 浩 劉玉嶺 張紅旗 楊英杰 葉潤國

1(解放軍信息工程大學 鄭州 450001) 2(中國科學院軟件研究所可信計算與信息保障實驗室 北京 100190) 3(河南省信息安全重點實驗室 鄭州 450001) 4 (中國電子技術標準化研究院 北京 100007) (wjjhh_908@163.com)

網絡入侵是指攻擊者利用目標網絡中的一些漏洞，通過實施蓄意的多步驟攻擊行為來達到最終的攻擊目的，使得網絡安全領域面臨嚴峻的考驗與挑戰[1-3].如臭名昭著的Zeus僵尸網絡[2]實施掃描探測、溢出攻擊、感染目標主機、病毒傳播和竊取用戶信息這5個步驟使國家、企業和個人遭受了無法挽回的經濟損失.日益泛濫的蠕蟲攻擊[3]也屬多步攻擊范疇，防護基于多步攻擊的網絡入侵刻不容緩.入侵路徑預測旨在通過分析網絡節點的脆弱性關系，從攻擊者角度出發，分析可能的攻擊路徑，預測潛在的攻擊行為，挖掘關鍵威脅節點，為網絡安全主動防御提供重要依據，受到國內外學者的廣泛關注[4-20].

早期研究主要圍繞設計隨機模型來描述多步攻擊狀態變遷過程，進而利用概率論及數學推理的相關知識來預測可能的狀態轉移情形.Yu等人[4]利用隱彩色Petri網區分不同攻擊行為節點，對告警進行關聯，能夠預測潛在的攻擊路徑.呂慧穎等人[5]構造了威脅狀態轉移圖來分析威脅事件的時空關聯，實時識別威脅狀態，并預測攻擊路徑.考慮到不同攻擊步驟間存在因果關聯，王碩等人[6]將單步攻擊間的轉移概率表示為因果知識，設計了因果知識網絡描述網絡入侵過程，并利用Dijkstra算法預測不同能力的攻擊者在入侵路徑選擇上的差異性.劉玉嶺等人[7]融合攻擊方、防護方和網絡環境信息，通過時空維度分析，預測了基于攻擊威脅的網絡安全態勢的變化趨勢，輔助攻擊意圖識別和路徑預測的研究.

近年來，攻擊圖(attack graph, AG)[8-22]作為一種基于圖論的脆弱性評估模型，已成為研究多步攻擊的主流方法，它從攻擊者的角度出發，在綜合分析多種網絡配置和脆弱性信息的基礎上，枚舉所有可能的攻擊路徑，從而幫助防御者直觀地理解目標網絡內各個脆弱性之間的關系，以及由此產生的潛在威脅.目前研究者已開發多種攻擊圖自動生成工具(如MulVAL，TVA，NetSPA等[8])，興起了攻擊圖研究的新一輪熱潮.

Kerem[8]綜述了攻擊圖的研究現狀，指出攻擊圖的可達性分析和路徑研究是攻擊圖研究的重點之一.Sheyner等人[9]最早將概率論與攻擊圖相結合，基于Markov決策過程，利用條件轉移概率分析非確定性節點，指出攻擊者傾向于選擇最有利于實現攻擊目標的路徑完成狀態轉移.Sarraute等人[10]改進了Floyd-Warshall算法來預測最短攻擊路徑.Abraham等人[11]通過分析漏洞生命周期，預測了路徑長度隨時間的變化規律.針對攻擊發生的不確定性問題，劉強等人[12]引入不確定攻擊圖，利用最佳漏洞利用鏈，衡量最有可能的攻擊路徑.陳小軍等人[13]在攻擊圖模型中引入轉移概率表，利用觀測事件推理單步攻擊的不確定性，通過累積概率預測最有可能的攻擊路徑.Zhu等人[14]利用聚類告警關聯分析，借鑒神經網絡技術構建完整攻擊場景，挖掘潛在的攻擊策略.相關研究還包括路徑數量評估[15]、路徑長度的中位值分析[16]、平均路徑長度度量[17]、最短耗時路徑預測[18].在實際應用方面，Dai等人[19]分析了如何利用攻擊圖中的最大風險流路徑來預測潛在威脅.通過阻斷最大可能攻擊路徑，Nayot等人[20]設計了網絡安全風險的動態評估方法.

梳理以上研究成果發現，盡管現有研究很多，但主要圍繞理想攻擊場景下的路徑預測展開研究，默認每次漏洞利用都能成功實施，包括了最大可能攻擊路徑、成功概率和路徑數量等，然而理想的最大可能攻擊路徑不一定是攻擊者采用的攻擊路徑，需對攻擊路徑的概率分布、原子攻擊次數和節點威脅度等進行全面感知分析，更全面地輔助安全管理員決策.

針對此問題，本文將吸收Markov鏈 (absorbing Markov chain, AMC)引入到攻擊圖研究領域，由于AMC中狀態轉移具有無后效性和吸收性質，符合網絡攻擊的隨機性和目標狀態節點的可達性特點，提出基于吸收Markov鏈的攻擊路徑預測方法.首先證明完整攻擊圖可以映射到吸收Markov鏈，然后基于通用漏洞評分標準(common vulnerability scoring system, CVSS)[21]提出狀態轉移概率度量方法，分析并構造狀態轉移概率矩陣，在此基礎上設計2種預測算法，計算節點訪問次數期望值和攻擊路徑長度期望值，最后通過實驗驗證本文方法的有效性.

本文的主要貢獻：1)預測不同攻擊狀態節點訪問次數的期望值，并對節點的威脅進行排序；2)分析不同長度攻擊路徑的概率分布，并計算路徑長度的期望值.前者可用于指導網絡安全管理員實施脆弱性修復的優先順序;后者利于掌握攻擊者利用不同路徑入侵的可能性，并預測完成攻擊目標所需攻擊步驟的數量.

1 基于吸收Markov鏈的攻擊圖

吸收Markov鏈適用于隨機模型的狀態轉移預測問題，基本思想是將攻擊圖映射到吸收Markov鏈，建立基于吸收Markov鏈的攻擊圖模型.一方面Markov鏈的無后效性符合攻擊狀態轉移僅與相鄰狀態有關的特點；另一方面，網絡攻擊至少存在一種終止狀態，與吸收Markov鏈的吸收態相符.

1.1 預備知識

為方便描述，文中主要符號及表達式的含義如表1所示：

Table 1 Symbols and Their Descriptions in This Paper表1 本文主要符號及其描述

定義1. 原子攻擊a.指攻擊者在網絡中實施的單個攻擊動作，其可能是對主機服務的掃描或對主機漏洞的1次利用，每個原子攻擊動作觸發攻擊者轉移到1個攻擊狀態S，原子攻擊發生的概率為p(a).

定義2. 攻擊路徑AR.指攻擊者從初始狀態節點到目標狀態節點有向邊的集合，攻擊路徑AR=S1→S2→…→Sn.

定義3. 攻擊路徑長度RL.指攻擊路徑中包含的邊的數量，即RL=n-1.

定義4. 攻擊成功概率p(AR).指攻擊路徑中所有狀態轉移都成功的概率p(AR)=p(a1)×p(a2)×…×p(aRL).

定義5. 攻擊路徑期望長度EARL.指攻擊者為實現攻擊目標所實施的攻擊步驟的數學期望值.

定義6. 狀態訪問期望次數.指實現攻擊目標過程中，某個狀態節點訪問次數的數學期望值.

定義7. 狀態節點威脅排序.指不同狀態節點對實現攻擊目標的貢獻排序，節點排序越靠前，表明該節點的威脅越大.

關于上述定義的3點補充說明：

2) 在定義6中，理想情況下每次狀態轉移都能成功(對應原子攻擊成功實施)，而實際情況下，由于攻擊者對網絡結構不熟悉，原子攻擊存在概率，若攻擊狀態轉移失敗，看作是對原狀態的重復訪問，在存在狀態重復轉移的情況下，求解EARL存在困難性.

3) 在定義7中，對于攻擊者而言，漏洞利用越頻繁的節點對于實現攻擊的貢獻值越高，因而對網絡安全的威脅越大.本文利用定義6中不同狀態節點訪問次數期望值的高低對節點威脅進行排序.

1.2 攻擊圖的概念

攻擊圖是對多步攻擊行為關聯建模的有效方法，從攻擊者角度出發，描述了攻擊狀態轉移過程，是一個有向圖，如圖1所示:

Fig. 1 Model of attack graph圖1 攻擊圖模型

定義8. 攻擊圖AG.使用一個四元組AG=(S,A,E,Δ)來表示，其中，S表示狀態節點集合，A表示原子攻擊節點集合，E表示為狀態節點間的有向邊集合，Δ表示狀態轉移概率集合.

1)S={Si|i=1,2,…,n}表示n個不同狀態節點構成的集合；

2)E?S×S，?ei,j∈E，ei,j表示連接節點Si和Sj的邊，其中Si表示ei,j的起始狀態節點，Sj表示ei,j的目的狀態節點，實現狀態轉移ei,j依賴的原子攻擊為a；

3) ?Δ(ei,j)∈Δ，Δ(ei,j)表示攻擊者由狀態Si轉到狀態Sj的概率p(Sj|Si)，且Δ(ei,j)等于原子攻擊a的發生概率p(a).

利用脆弱性掃描工具如Nessus，Retina[22]對網絡進行漏洞掃描，依據部署網絡的拓撲結構與采集到的脆弱性集，結合攻擊圖自動生成工具MulVAL[23]構建攻擊圖，避免了手動構建的復雜性，是目前的主流構造方法.

1.3 吸收Markov鏈的相關定義

定義9. Markov鏈MC[24].對于一個離散的包含有限狀態的隨機序列集合X={x1,x2,…,xn}，如果每個狀態值僅與前一個相鄰的狀態值有關，而與再之前的狀態無關，稱為Markov鏈.

p(xi|xi-1,xi-2,…,x1)=p(xi|xi-1).

定義10. 狀態轉移概率矩陣P.將Markov鏈中的狀態轉移概率用鄰接矩陣P表示，其中pi,j表示狀態xi→xj的概率，若xi→xj不可達，令pi,j=0，矩陣P滿足

其中,0≤pi,j≤1(1≤i,j≤n).

定義11. 初始狀態.表示攻擊者的出發狀態，該狀態節點只有流出邊，沒有流入邊.

定義12. 吸收狀態.表示攻擊者的目標狀態，該狀態節點只有流入邊，沒有流出邊.

定義13. 過渡狀態.狀態序列中，除去吸收狀態的其他狀態稱為過渡狀態.

定義14. 吸收Markov鏈AMC[24].含有吸收狀態的Markov鏈稱為吸收Markov鏈，對應狀態轉移概率矩陣表示為

其中，Q是t×t的矩陣，表示過渡狀態間的轉移概率；0是r×t的零矩陣；R是t×r的非零矩陣，表示過渡狀態到吸收狀態的轉移概率；I是r×r的單位矩陣；所有狀態數量n=t+r.

1.4 攻擊圖到吸收Markov鏈的映射

本節給出攻擊圖中狀態轉移概率的歸一化處理算法，并生成狀態轉移概率矩陣，在此基礎上證明完整的攻擊圖可以映射到吸收Markov鏈.

命題1. 1個完整的攻擊圖中至少包含1個吸收狀態.

證明. 由于攻擊圖描述了網絡的脆弱性利用關系，通過基于脆弱性利用的多步關聯，攻擊者最終將達到穩定的終止狀態，因此攻擊圖的終止狀態即吸收狀態，且至少包含1個吸收狀態.

證畢.

攻擊圖邊值歸一化處理的具體算法步驟如下：

算法1. 狀態轉移概率歸一化算法.

輸入：攻擊圖AG=(S,A,E,Δ)；

輸出：吸收Markov鏈AMC的狀態轉移概率矩陣P.

步驟1. 令i,j=1，G=S，其中i和j分別表示矩陣P的第i行和第j列；

步驟2. 令k=1，k表示節點Si的第k條流出邊的編號；

步驟4. 對于節點Si∈S，從節點集合G中隨機選取1個節點Sj，令G={G-Sj}；

步驟6. 令j=j+1，若j≤n，則轉至步驟4，否則該步驟結束，令j=1，k=1，G=S；

按序賦值給矩陣P中第i行位置(i,j1),(i,j2),…,(i,jk)上的元素值pi,j1,pi,j2,…,pi,jk，該步驟結束；

步驟8. 令i=i+1，若i≤n，則轉至步驟1，對于每個狀態節點Si，重復步驟4～6，完成節點Si流出邊的概率值歸一化處理，并生成矩陣P的第i行；若i>n，則該步驟結束；

步驟9. 輸出狀態轉移概率矩陣P，算法結束.

命題2. 1個完整的攻擊圖可以映射為1個吸收Markov鏈，若以下2個條件成立:

1) 對于任意狀態節點Si滿足定義10，即該節點的所有流出邊的概率之和等于1；

2) 至少包含1個吸收狀態節點.

證明. 1)利用算法1，得到任意節點Si滿足：

2) 由命題1可知條件2)滿足.

綜上，命題2成立.

證畢.

圖1攻擊圖對應的Markov鏈的狀態轉移概率矩陣如下：

Fig. 2 Exploitability scoring standard of CVSS圖2 CVSS的漏洞可利用性評分標準

2 攻擊路徑預測

在第1節的基礎上，本節首先給出一種通用的基于CVSS的轉移概率度量方法，然后分析節點訪問次數的期望值，最后計算攻擊路徑長度的期望值.

2.1 基于CVSS的轉移概率度量

CVSS由美國國家基礎建設咨詢委員會發布，是漏洞評估的行業公開標準，其制定的漏洞可利用性評分準則(如圖2所示)全面衡量了漏洞的利用難度，通過查詢美國國家漏洞數據庫(national vulner-ability database, NVD)[25]可以得到具體值.本文利用攻擊難度來度量狀態轉移概率，給出一種基于CVSS的轉移概率度量方法，以增強研究的通用性.

由圖2可知，CVSS給出原子攻擊a依賴漏洞的可利用性得分score(a)=20×AV×AC×AU，且0

設攻擊圖AG中狀態轉移邊e的概率值與依賴原子攻擊a的可利用性得分score(a)成正比，即Δ(e)=f×score(a)，其中f是比例系數.對于任意節點Si的流出邊ei,j1,ei,j2,…,ei,jk，利用算法1標準化處理后的轉移概率為

2.2 節點訪問次數的期望值預測

本節首先給出吸收Markov鏈中狀態轉移滿足的若干引理，其中引理1給出n步攻擊后的AMC的狀態轉移概率矩陣，引理2證明經過n(n→∞)步后，過渡狀態間的轉移概率為0，在此基礎上結合概率論，定理1得到狀態節點訪問次數的期望值求解矩陣，最后給出節點訪問次數期望值計算流程.

證明. 利用數學歸納法進行證明：

1) 當m=2時，由下式可知結論成立

2) 假設當m=m-1時結論成立，即:

則滿足:

因此假設成立，由1)2)可知引理1成立.

證畢.

引理2. 攻擊者從任意非吸收狀態出發，最終都會到達吸收狀態，即經過m(m→∞)步后，過渡狀態間的期望轉移概率為0，滿足:

證畢.

定理1. 攻擊者從過渡狀態Si出發，在吸收前訪問過渡狀態Sj的次數期望值用Ni,j表示，其中1≤i,j≤t，設N為大小為t×t的矩陣，將Ni,j賦值給矩陣N中位置(i,j)元素，稱N為攻擊次數期望值矩陣，則N=(I-Q)-1.

證明. 1) 攻擊者從節點Si出發，分別經過m=0,1,2,3,…步，訪問節點Sj的次數期望值總和

綜合1)2)可知，定理1成立.

證畢.

基于網絡拓撲結構和漏洞掃描信息，利用自動生成工具MulVAL生成攻擊圖AG，通過查詢NVD數據庫得到漏洞可利用性得分，在此基礎上給出節點訪問次數的期望值預測步驟如下:

方法1. 節點訪問次數的期望值預測方法.

輸入：攻擊圖AG、所有漏洞的可利用性得分score(a)；

輸出：以狀態節點Si為初始節點，在吸收前轉移到節點S1,S2,…,St的期望次數Ni,1,Ni,2,…,Ni,t，以及節點威脅排序.

步驟1. 依據算法1，利用2.1節轉移概率度量方法，結合AG的漏洞可利用性得分生成AMC的n×n的狀態轉移概率矩陣P，其中矩陣P的第i行向量的位置(i,j1),(i,j2),…,(i,jk)上的元素值為

其余位置的元素值為0；

步驟2. 由矩陣P構造t×t的過渡狀態間的轉移概率矩陣Q；

步驟3. 計算t×t期望值矩陣N=(I-Q)-1，輸出行向量(Ni,1,Ni,2,…,Ni,t)；

步驟4. 依據(Ni,1,Ni,2,…,Ni,t)中元素值大小對節點S1,S2,…,St的威脅進行排序，步驟結束.

下面以圖3攻擊圖為例，簡要說明方法流程.

The value next to the arrow line means the transition probability from one state to another.Fig. 3 Example of attack graph圖3 攻擊圖實例

為簡化說明，圖3中狀態轉移概率值已歸一化處理，過渡狀態為S1,S2,S3，吸收狀態為S4，得到狀態轉移概率矩陣Q和P，并計算期望值矩陣N.

由N的第1行可知，從初始狀態S1出發，訪問節點S2,S3次數的期望值為87，57，此時節點的威脅排序為S2>S3.

2.3 攻擊路徑長度的期望值預測

本節在2.2節的基礎上，首先給出求解攻擊路徑長度的期望值向量的推論，在此基礎上分析路徑長度的期望值計算過程.

推論1. 攻擊者從節點Si(1≤i≤t)出發，吸收前轉移總次數的期望值(期望路徑長度)用Ti表示，設T是大小為t×1的矩陣，C是大小為t×1的單位矩陣，將Ti賦值給T位置(i,1)的元素，稱T為期望路徑長度矩陣，則T=N·C.

證明. 由定理1可知，對于任意節點Si，在吸收前轉移到節點S1,S2,…,St的次數分別為Ni,1,Ni,2,…,Ni,t，則從節點Si出發的期望攻擊路徑長度Ti=Ni,1+Ni,2+…+Ni,t，因此T=(Ti)=(Ni,1+Ni,2+…+Ni,t)=N·C.

結合拓撲分析和漏洞掃描，利用工具MulVAL生成攻擊圖，查詢NVD數據庫得到漏洞信息，并設計攻擊路徑長度的期望值預測方法如下:

方法2. 攻擊路徑長度的期望值預測方法.

輸入：攻擊圖AG、所有漏洞的可利用性得分score(a)；

輸出：狀態節點Si作為初始節點，攻擊路徑長度的期望值Ti.

步驟1. 結合算法1和方法1，構造AMC的n×n狀態轉移概率矩陣P，位置(i,j1),(i,j2),…,(i,jk)值為

第i行其余元素值為0；

步驟2. 構造AMC的過渡狀態間的轉移概率矩陣Q，大小為t×t；

步驟3. 計算t×t的訪問次數期望值矩陣N=(I-Q)-1；

步驟4. 令C=(1,1,…,1)T，大小為t×1，計算t×1的路徑長度期望值向量T=N·C，輸出節點Si出發的路徑長度的期望值EARL(Si)=Ti，步驟結束.

計算復雜度分析如下：

1) 算法執行包含矩陣求逆、矩陣相加和矩陣相乘過程，其中矩陣相乘的時間復雜度最高，當2個n×n矩陣相乘時，包含2n3次乘法運算，因此時間復雜度的階數為O(n3).

2) 算法需要維護n×n矩陣P、t×t矩陣Q、t×t矩陣N、t×1矩陣T和C，因此存儲復雜度為O(n2).

綜上，算法復雜度符合多項式時間級別，在當前計算環境下能夠執行實時運算.

對于圖3的攻擊圖，

則從節點S1,S2,S3出發的攻擊路徑長度的期望值為207，127，157.

結合引理2及定理1，

結合定義14，[Ν·R]i,j表示攻擊者由過渡狀態Si轉移到吸收狀態Sj的概率.計算

驗證任何過渡狀態最終都會以概率1轉移到吸收狀態.

3 實驗與分析

為了驗證本文方法的有效性和適用性，我們設計了2個實驗對該方法進行了測試分析.其中實驗1參照文獻[6]搭建了一個小型模擬攻防環境；實驗2選用林肯實驗室提供的經典DARPA2000標準測試集[26]，分析DDOS攻擊場景下的實驗結果.最后給出本方法與現有方法的綜合對比分析.

Fig. 4 Experimental network topology圖4 實驗網絡拓撲結構

3.1 實驗1

為驗證本文方法的有效性，搭建了一個實際網絡來進行測試.實驗拓撲如圖4所示，網絡中包括防火墻、入侵檢測系統Snort IDS、2臺主機以及3臺服務器.防火墻預先設置策略將網絡分為2個子網，使得服務器H1，H2分布在DMZ Zone，服務器H3，H4，H5分布在Trusted Zone.防火墻1禁止外部主機訪問Trusted Zone中的服務器，僅可以利用HTTP協議(80端口)與DMZ Zone內的主機H1和H2進行通信.防火墻2允許DMZ Zone內的主機和Trusted Zone中的服務器進行通信，且Trusted Zone內的服務器僅可以被動接收服務請求.依據攻擊發起的初始位置，攻擊分為內部和外部攻擊2種.

3.1.1 實驗環境信息

利用脆弱性掃描工具Nessus對各網段進行掃描，并通過查詢NVD得到各主機包含的漏洞信息如表2所示：

Table 2 Host Configuration and Vulnerability Information in Network表2 網絡主機配置及漏洞信息

依據部署網絡的拓撲結構與采集的脆弱性集，利用工具MulVAL生成攻擊圖如圖5所示，不同狀態間轉移依賴的漏洞已標注，到節點自身的狀態轉移邊用虛線標出，邊值標注為狀態轉移的可利用性得分，共有7種不同的攻擊狀態，S1表示外部攻擊者的初始狀態，各狀態信息描述如表3所示:

The value next to the arrow line means the exploitability score of vulnerability. Fig. 5 Attack graph of experimental network圖5 實驗網絡攻擊圖

No.DescriptionNo.DescriptionS1RemoteAttackerS5(H3,Root)S2(H1,Root)S6(H4,User)S3(H2,Root)S7(H5,Root)S4(H3,User)

3.1.2 計算過程描述

步驟1. 基于CVSS的轉移概率度量.

利用2.1節狀態轉移概率歸一化方法，生成吸收Markov鏈的狀態轉移概率表,如表4所示，對應吸收Markov鏈攻擊圖如圖6所示.

Table 4 Probability Table of State Transition表4 狀態轉移概率表

Fig. 6 Absorbing Markov chain attack graph圖6 吸收Markov鏈攻擊圖

步驟2. 節點訪問次數的期望值預測.

理想情況下，若入侵場景中的每次漏洞利用都成功實施，所有可能的11條入侵路徑及其概率分布如表5所示，其中最短路徑長度為3，最長路徑長度為5，路徑長度的中位值為4，理想路徑長度的平均值為(4+4+5+3+4+4+5+3+3+3+4)11=3.818.最大可能攻擊路徑為S1→S3→S6→S7，累積成功概率為0.444×0.391×0.5=0.087，該攻擊過程描述如下：為獲得服務器H5的root權限，攻擊者首先對目標網絡進行IPsweep地址掃描，搜尋有效主機，發現有效主機H2，通過端口掃描，發現其通信端口為80，利用postgresql服務上的漏洞CVE 2014-0063，獲得root權限；隨后攻擊者利用bmc服務上的漏洞CVE 2013-4782獲得服務器H4的用戶權限；進一步以服務器H4為跳板，利用radius服務上的漏洞CVE 2014-1878獲得服務器H5的root權限，實現攻擊目標.

Table5LengthandProbabilityDistributionofIdealAttackRoute

表5 理想攻擊路徑長度及其概率分布

在實際情況下，若單步攻擊的某次漏洞利用不成功，則狀態轉移失敗，看作到自身狀態的1次轉移，路徑長度加1，因而實際的攻擊路徑長度往往高于理論的攻擊路徑長度，下面利用本文方法分析實際網絡環境中的路徑預測信息.

由圖6得到狀態轉移概率矩陣P和Q，結合方法1和方法2計算期望矩陣N和T如下所示:

期望值矩陣N的不同行代表從不同初始狀態出發訪問各節點次數的期望值分布，如圖7所示.若節點訪問次數越高，表明該節點的威脅程度越大，不同節點的訪問次數分布不均勻，表明各節點的威脅程度差別較大.例如外部攻擊者從狀態S1出發，訪問節點S2,S3,S4,S5,S6的次數分別為0.741,1.087,0.584,0.628,1.610，此時節點威脅排序為S6>S3>S2>S5>S4，因此在漏洞修復時應首先考慮狀態S6(H4上的漏洞CVE 2013-4782).

Fig. 7 Distribution of expected number of visits to different state nodes圖7 不同狀態節點訪問次數的期望值分布

步驟3. 攻擊路徑長度的期望值預測.

結合圖6,由矩陣T可知，從不同節點S1,S2,S3,S4,S5,S6出發，到達攻擊目標S7的期望路徑長度分布如圖8所示，例如初始狀態為S1時的期望攻擊路徑長度為5.65，表示攻擊者平均需要實施5.65次原子攻擊才能實現攻擊目標.通過實時檢測攻擊發生的位置，確定攻擊者的狀態，可以預測后續攻擊的期望路徑長度，對于安全管理員實時掌握當前的攻擊狀況、制定安全防護措施具有重要意義.

Fig. 8 Expected attack route length starting from different initial state nodes圖8 從不同狀態節點出發的期望攻擊路徑長度

3.1.3 測試結果分析

借鑒文獻[6]的實驗方法，從課題依托信息安全重點實驗室中隨機挑選100名學員作為攻擊者，分別在部署環境(如圖4所示)中進行攻擊測試實驗，攻擊者的初始狀態為S1，公開網絡的拓撲結構及漏洞信息，既定攻擊目標為S7，實驗時間為2 h.通過實時采集網絡中運行的防火墻、Snort IDS和主機日志的告警信息，進一步利用自動化工具ArCSight[27]分析告警信息，得到100條攻擊序列，由于4名攻擊者未在規定時間內完成攻擊目標，剔除未成功的4條攻擊序列后，統計長度為3～17的路徑數量分別為17，14，13，12，11，9，6，3，3，2，2，1，1，0，0.

Table 6 Probability Distribution of Attack Route Length by Our Method表6 本文攻擊路徑長度的概率分布

從圖9可以看出：

1) 長度為3的路徑出現概率最大，與本文理論預測結果一致，同時概率值隨著路徑長度的增大而不斷減小，理論值表明當路徑長度不斷增大時出現概率逐漸趨于0，驗證了本文方法的有效性.

2) 實驗包含100名攻擊者，采集到100個樣本，受攻擊者自身因素(知識水平、攻擊技能、攻擊經驗等)的影響，不同路徑長度出現概率的測試值與理論值不完全相等，但從整體上看，路徑長度概率分布的測試結果與理論結果的變化趨勢基本一致，符合預期結果.

3.2 實驗2

Fig. 10 Attack graph of LLDOS1.0 scenario圖10 LLDOS1.0場景的攻擊圖

本節以林肯實驗室提供的DARPA2000數據集中LLDOS1.0攻擊場景作為實驗對象，文獻[14]通過基于聚類的告警關聯分析，挖掘了該數據集包含的完整攻擊場景，如圖10所示，受到廣泛認可，并給出如下狀態轉移概率，本文借鑒該攻擊場景進行實驗分析：

Δ(e2,5)=0.15,
Δ(e2,3)=0.28,
Δ(e3,5)=0.1,
Δ(e1,2)=0.29,
Δ(e2,2)=0.2,
Δ(e2,4)=0.28,
Δ(e4,2)=0.18,
Δ(e4,3)=0.42,
Δ(e4,5)=0.15,
Δ(e5,5)=1,
Δ(e1,4)=0.33,
Δ(e4,4)=0.18.

利用算法1構造吸收Markov鏈的轉移矩陣P，進一步利用算法2和算法3計算矩陣N和T：

吸收狀態節點為S5，Ni,j表示狀態Si出發，在到達目標狀態之前訪問狀態Sj的次數，例如從初始狀態節點S1出發，到達節點S2,S3,S4的次數分別為0.84，5.38，0.98，此時過渡狀態節點威脅排序為S3>S4>S2，應首先修復狀態S3的漏洞.由矩陣T可知，從不同節點S1，S2，S3，S4出發，到達目標節點的期望攻擊路徑長度分別為8.198，7.2，7.692，7.197，結果表明從節點S1出發的攻擊者，到達目標狀態節點所實施漏洞攻擊的平均次數最多.

表7給出了LLDOS1.0攻擊場景中理想度量方法和實際度量方法的結果比較，在理想情況下，由于不存在重復狀態轉移行為，統計得到可能路徑數量為8，最短路徑長度為2，路徑長度類型有2，3，4，所有路徑長度的中位值及平均值都是3，攻擊意圖的累積成功概率為0.14.

相反，在實際情況下，實現攻擊意圖的期望概率為1，最長和最短期望路徑長度分別為8.198和7.197，前者表明平均需要實施8.198次漏洞攻擊才能實現目標，后者表明所需要的最少漏洞攻擊次數為7.197，該結果顯然大于理想路徑長度值，與預期相符.因此，利用本文度量方法可以科學評估攻擊者當前狀態，并準確預測后續攻擊行為.

表7 Structural Metrics of LLDOS1.0 Attack Scenario表7 LLDOS1.0攻擊場景的結構化度量

3.3 方案綜合對比

本文與典型相關研究的特點比較如表8所示，從表8中可以看出，多數文獻均有研究最大可能攻擊路徑及其概率值.針對理想攻擊場景(每次漏洞利用都成功)，本文和文獻[6,10,16-17]進一步分析了最短路徑，除此之外，本文和文獻[6,15-17]能夠度量理想攻擊路徑的數量，其中文獻[16-17]和本文又分析了理想路徑長度的平均值，且本文和文獻[16]進一步討論了理想路徑長度的中位值.

Table 8 Comparison of Features Among Our Method and Others表8 本文與典型方法的特點比較

特別地，針對實際網絡環境(單步攻擊實現依賴多次漏洞利用)，本文重點研究了期望路徑長度及其概率分布，并給出了狀態節點訪問次數的期望值預測方法，用于分析節點的威脅排序，更加準確全面地預測攻擊路徑信息，輔助安全管理員決策，為實際網絡環境中應對網絡多步攻擊威脅提供更多指導.

4 結束語

由于網絡入侵者的攻擊狀態轉移過程復雜，因此攻擊路徑預測對于安全管理員直觀地了解攻擊過程具有重要意義.考慮到現有方法主要圍繞理想攻擊路徑展開研究，本文將攻擊圖映射為吸收Markov鏈，給出了基于通用漏洞評分標準的轉移概率量化方法，在此基礎上著重研究了實際網絡環境中不同狀態節點的期望訪問次數，用于分析節點的威脅排序，并計算期望攻擊路徑長度及其概率分布，輔助安全管理員全面分析不同攻擊路徑的發生概率，掌握攻擊者可能實施的原子攻擊次數，并預先制定安全防護措施，為防御網絡入侵提供指導.

如何結合網絡中采集的告警序列，客觀地衡量狀態轉移概率，預測攻擊路徑長度的期望值，并依據實時觀察結果動態修正后續路徑長度的期望值，提高復雜攻擊場景中預測的準確性和適用性是下一步研究的主要工作.

[1]Zhang Huanguo, Han Wenbao, Lai Xuejia, et al. Survey on cyberspace security[J]. Scientia Sinica Informationis, 2016, 46(2): 125-164 (in Chinese)(張煥國, 韓文報, 來學嘉, 等. 網絡空間安全綜述[J]. 中國科學: 信息科學, 2016, 46(2): 125-164)

[2]Jiang Jian, Zhuge Jianwei, Duan Haixin, et al. Research on botnet mechanisms and defenses[J]. Journal of Software, 2012, 23(1): 82-96 (in Chinese)(江健, 諸葛建偉, 段海新, 等. 僵尸網絡機理與防御技術[J]. 軟件學報, 2012, 23(1): 82-96)

[3]Liu Yuling, Feng Dengguo, Wu Lihui, et al. Performance evaluation of worm attack and defense strategies based on static Bayesian game[J]. Journal of Software, 2012, 23(3): 712-723 (in Chinese)(劉玉嶺, 馮登國, 吳麗輝, 等. 基于靜態貝葉斯博弈的蠕蟲攻防策略績效評估[J]. 軟件學報, 2012, 23(3): 712-723)

[4]Yu Dong, Frincke D. Improving the quality of alerts and predicting intruder’s next goal with hidden colored Petri-net[J]. Computer Networks, 2007, 51(3):632-654

[5]Lü Huiying, Peng Wu, Wang Ruimei, et al. A real-time network threat recognition and assessment method based on association analysis of time and space[J]. Journal of Computer Research and Development, 2014, 51(5): 1039-1049 (in Chinese)(呂慧穎, 彭武, 王瑞梅, 等. 基于時空關聯分析的網絡實時威脅識別與評估[J]. 計算機研究與發展, 2014, 51(5): 1039-1049)

[6]Wang Shuo, Tang Guangming, Kou Guang, et al. Attack route prediction method based on causal knowledge[J]. Journal on Communications, 2016, 37(10): 188-198 (in Chinese)(王碩, 湯光明, 寇廣, 等. 基于因果知識網絡的攻擊路徑預測方法[J]. 通信學報, 2016, 37(10): 188-198)

[7]Liu Yuling, Feng Dengguo, Lian Yifeng, et al. Network situation prediction method based on spatial-time dimension analysis[J]. Journal of Computer Research and Development, 2014, 51(8): 1681-1694 (in Chinese)(劉玉嶺, 馮登國, 連一峰, 等. 基于時空維度分析的網絡安全態勢預測方法[J]. 計算機研究與發展, 2014, 51(8): 1681-1694)

[8]Kerem K. A taxonomy for attack graph generation and usage in network security[J]. Journal of Information Security and Applications, 2016, 29(C): 27-56

[9]Sheyner O, Haines J, Jha S, et al. Automated generation and analysis of attack graphs[C]Proc of the 2002 IEEE Symp on Security and Privacy. Piscatawary, NJ: IEEE, 2002: 273-284

[10]Sarraute C, Richarte G, Lucángeli O J. An algorithm to find optimal attack routes in nondeterministic scenarios[C]Proc of the 4th Int ACM Workshop on Security and Artificial Intelligence. New York :ACM, 2011: 71-80

[11]Abraham S, Nair S. A predictive framework for cyber security analytics using attack graphs[J]. International Journal of Computer Networks & Communications, 2015, 7(1): 1-17

[12]Liu Qiang, Yin Jianping, Cai Zhiping, et al. Uncertain-graph based method for network vulnerability analysis[J]. Journal of Software, 2011, 22(6): 1398-1412 (in Chinese)(劉強, 殷建平, 蔡志平, 等. 基于不確定圖的網絡漏洞分析方法[J]. 軟件學報, 2011, 22(6): 1398-1412)

[13]Chen Xiaojun, Fang Binxing, Tan Qingfeng. Inferring attack intent of malicious insider based on probabilistic attack graph model[J]. Chinese Journal of Computers, 2014, 37(1): 62-72 (in Chinese)(陳小軍, 方濱興, 譚慶豐. 基于概率攻擊圖的內部攻擊意圖推斷算法研究[J]. 計算機學報, 2014, 37(1): 62-72)

[14]Zhu Bin, Ghorbani A A. Alert correlation for extracting attack strategies[J]. International Journal of Network Security, 2006, 3(3): 244-258

[15]Ortalo R, Deswarte Y, Kaaniche M. Experimenting with quantitative evaluation tools for monitoring operational security[J]. IEEE Trans on Software Engineering, 1999, 25(5): 633-50

[16]Idika N, Bhargava B. Extending attack graph-based security metrics and aggregating their application[J]. IEEE Trans on Dependable & Secure Computing, 2012, 9(1):75-85

[17]Li Wei, Vaughn R B. Cluster security research involving the modeling of network exploitations using exploitation graphs[C]Proc of the 6th IEEE Int Symp on CLUSTER Computing and the Grid. Piscatawary, NJ: IEEE, 2006: 26-26

[18]Lucangeli J, Sarraute C, Richarte G. Attack planning in the real world [JOL]. Computer Science, 2013[2017-06-17]. http:sciencewise.infoarticles1306.4044

[19]Dai Fangfang, Hu Ying, Zheng Kangfeng, et al. Exploring risk flow attack graph for security risk assessment[J]. IET Information Security, 2015, 9(6): 344-353

[20]Nayot P, Rinku D, Indrajit R. Dynamic security risk management using Bayesian attack graphs[J]. IEEE Trans on Dependable & Secure Computing, 2012, 9(1): 61-74

[21]Schiffman M. Common vulnerability scoring system (CVSS)[EBOL]. [2017-06-17]. https:www.first.orgcvss

[22]Tenable N. Nessus vulnerability scanner[EBOL]. [2017-06-17]. http:www.tenable.comproductsnessus-home

[23]Ou Xinming, Govindavajhala S, Appel A W. MulVAL: A logic-based network security analyzer[C]Proc of the 14th USENIX Security Symp. Berkeley, CA: USENIX Association, 2005: 8-8

[24]Dimitri P, Bertsekas J N. Introduction to probability[EBOL]. [2017-06-17]. http:www.sciencedirect.comsciencebook9780128000410

[25]NIST. National vulnerability database[DBOL]. [2017-06-17]. https:nvd.nist.gov

[26]MIT Lincoln Laboratory. 2000 DARPA intrusion detection scenario specific data sets[EBOL]. [2017-06-17]. http:www.ll.mit.eduidevaldata2000data.html

[27]Hewlett-Packard. ArcSight ESM enterprise security manager[OL]. [2017-06-17]. https:saas.hpe.comen-ussoftwaresiem-security-information-event-management

HuHao, born in 1989. PhD candidate. His main research interests include network security assessment and visual cryptography.

LiuYuling, born in 1982. PhD. Associate professor. His main research interests include network and system security assessment and network security situation awareness.

ZhangHongqi, born in 1962. PhD, professor. His main research interests include network security and classification protection.

YangYingjie, born in 1971. PhD, professor. His main research interests include security management and situation awareness.

YeRunguo, born in 1976. PhD. Engineer. His main research interest is the big data security.