一種基于屬性鄰接矩陣和博弈理論的風險控制模型

顧兆軍 李躍凱

摘 ?要： 為了網絡安全管理員能夠在有限的資源條件下及時加固關鍵節點，減少網絡攻擊帶來的損失，設計一種基于屬性鄰接矩陣和博弈理論的風險控制模型。該模型利用BFS攻擊圖簡化算法刪減攻擊圖中出現的環路和冗余節點，將簡化后的攻擊圖轉化為屬性鄰接矩陣，最后利用博弈理論得出可能的攻擊路徑和最優防御策略。實驗結果表明，與傳統風險控制方法相比，該模型解決了頂點和邊數過多導致圖結構過于復雜的問題，更具可視性地得出了攻擊路徑和原子攻擊序列，可為信息系統管理員提供科學的理論參考。

關鍵詞： 風險控制模型; 攻擊圖; BFS攻擊圖簡化算法; 屬性鄰接矩陣; 博弈理論; 冗余節點

中圖分類號： TN911?34; TP393.08 ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）10?0005?05

A risk control model based on attribute adjacency matrix and game theory

GU Zhaojun1，2， LI Yuekai1，2

（1. Information Security Evaluation Center， Civil Aviation University of China， Tianjin 300300， China;

2. College of Computer Science and Technology， Civil Aviation University of China， Tianjin 300300， China）

Abstract： A risk control model based on the attribute adjacency matrix and game theory is designed for the network security administrators to timely consolidate key nodes under the limited resource condition and reduce losses caused by network attacks. In the model， the BFS attack graph simplified algorithm is used to delete the loops and redundant nodes appearing in the attack graph. The simplified attack graph is transformed to the attribute adjacency matrix. The game theory is used to obtain possible attack paths and the optimal defense strategy. The experimental results show that， in comparison with traditional risk control methods， the model can solve the problem of too complex graph structure caused by excessive vertexes and edges， and obtain the attack paths and atomic attack sequence visually， which provides a scientific and theoretical reference for information system administrators.

Keywords： risk control model; attack graph; BFS attack graph simplified algorithm; attribute adjacency matrix; game theory; redundant node

0 ?引 ?言

網絡安全事件頻繁發生，信息系統的安全性變得越來越重要。由于脆弱點，或稱為安全漏洞的客觀存在，因攻擊行為而導致的網絡安全事件難以避免。傳統防御諸如防火墻、防病毒軟件以及入侵檢測工具等技術手段難以提前準確地預測威脅。目前我國也未形成標準的防御體系。美國計算機安全協會發布的計算機犯罪和安全調查報告[1]顯示，當前網絡面臨的攻擊行為大多表現為多步驟的組合式攻擊，其行為采取多個原子攻擊的方式逐步完成。原子攻擊是指攻擊者通過攻擊主機上或網絡中的某個脆弱點而發起的攻擊，一系列的原子攻擊構成了一個攻擊行為[2?3]。因此，對攻擊圖中原子攻擊和攻擊序列的研究尤為重要。

OU X M指出循環路徑是攻擊圖復雜原因之一[4]。HOMER J等人使攻擊圖不含循環路徑，一個節點在任何一條路徑中不重復出現，但這樣節點增多，攻擊圖更為復雜[5]。NOEL S等人使用鄰接矩陣表示攻擊圖[6]，利用0和1來表示各節點之間是否可達，不能顯示出攻擊的行為和路徑。LYE K W等利用隨機博弈形式分析和推理網絡攻防雙方的博弈關系，驗證了博弈論同網絡攻防相結合的有效性和適用性[7]。姜偉構造了一個網絡防御模型，將博弈論和網絡攻防結合，理性預測攻擊者可能會采取的攻擊行為，但其重點用于攻防雙方狀態的轉換，不能反映攻擊路徑[8]。李慶朋等人利用脆弱點之間關聯性減少大規模網絡攻擊圖中冗余點，但須對原始生成的攻擊圖進行復雜的預處理，加之目前脆弱點的關聯性強度也并不明確，實用性低[9]。

與以上所做工作不同，本文提出一種基于屬性鄰接矩陣和博弈理論的風險控制模型。

1 ?風險控制模型

本文利用屬性鄰接矩陣和博弈理論對系統進行分析的流程如圖1所示。

圖1 ?風險控制模型流程圖

1.1 ?簡化攻擊圖

攻擊圖分為狀態攻擊圖和屬性攻擊圖兩種。由于狀態攻擊圖節點過多時存在狀態爆炸問題[10?11]，執行效率低下，本文采用屬性攻擊圖進行分析。

攻擊圖G=（C，E）是一個有向圖，其中C代表原子攻擊節點集合，E代表滲透節點集合，或稱為攻擊節點獲得的屬性節點集合[12]。攻擊圖簡化過程為：

1） 計算每個滲透節點父節點個數，預先將每個滲透節點置為FALSE，且將其number_Child值置0。

2） 設定隊列q，將初始原子攻擊節點依次插入。

3） 按序從q中取出原子攻擊節點，將其子節點（滲透節點）number值加1。若number的值與已計算出的該滲透節點父節點的數目相等，說明該節點成功發生條件已滿足，將Flag置TRUE，且把該節點的所有子節點（原子攻擊節點）依次加入q中。

4） 去除Flag為FALSE節點和與其相連的邊，得到簡化后攻擊圖。算法如下：

輸入：攻擊圖G=（C，E）

輸出：簡化后攻擊圖

1. Foreach ei [∈]E ?do

2. Count[ei]=number_Parent[ei];

3. Flag[ei]=FALSE;

4. number_Child =0;

5. Foreach Ci[∈]C ?do

6. Insert（q，Ci）;

7. Foreach k=Delete（q）;

8. Foreach ej[∈] Child（k） ?do

9. number_Child[ej]= number_Child[ej]+1;

10. If ?number_Child[ej]==Count[ej] ?Then

11. Flag[ej]=TRUE;

12. Foreach Ct[∈]Child[ej] ?do

13. Insert（q，Ct）;

14. Return 去除Flag為FALSE節點的簡化后攻擊圖

圖2左圖是某業務系統的原始攻擊圖。攻擊者攻破脆弱點C1可以滲透至e1，接著攻破C2可以滲透至e2和e3，攻破C3可以滲透至e3，直至到達攻擊者的目標節點。C1至e1的邊稱為e1的前提邊，e1至C2，e1至C3的邊均為e1的后果邊。顯然，圖中e9→C13→e11→C12→e9為一條循環路徑，現實場景中不會發生這樣的攻擊，應予以刪減，降低攻擊圖冗余度和分析難度。同理e8→C10→e10→C11→e8 也應予以刪減。簡化后的攻擊圖如圖2右圖所示。

圖2 ?原始攻擊圖的簡化（一）

1.2 ?形成屬性鄰接矩陣

對于n個屬性節點的網絡，其屬性鄰接矩[M]是一個n×n的矩陣。mij表示從屬性i到屬性j的一個原子攻擊。mij≠0，說明i到j之間存在攻擊路徑;mij=0，說明i到j之間不存在攻擊路徑[13]。

記單步的屬性鄰接矩陣記為[M]，屬性ei到屬性ej單步的攻擊路徑記為ei（mij）ej，括號內容表示一個原子攻擊行為。

定義1： [i=1nai=a1?a2?…?an（i=1，2，…，n）]。

定義2： [mikΔmkj]為屬性[ei]和[ej]之間兩個相鄰的原子攻擊行為，[k]為中間節點。

定義3： [m2ij]代表[ei]和[ej]之間所有的兩步攻擊路徑，[m2ij=k=1n（mikΔmkj）]。

定義4： 設矩陣[A=（aij）m×k]，[B=（bij）k×n]，記[C=A?B]，[C=（cij）m×n]。其中矩陣元素[cij=] [（ai1Δb1j）?（ai2Δb2j）?…?（ai3Δb3j）=s=1k（aikΔbkj）]。

對兩步屬性鄰接矩陣[M2]，其元素可表示為[k=1n（mikΔmkj）]，那么對于[n]步的屬性鄰接矩陣，給出下列定理及其證明。

定理1： [n]步的屬性鄰接矩陣[Mn]中，[ei]～[ej]的所有[n]步攻擊路徑可表示為[mnij=k=1n（mn-1ikΔmkj）]。

證明：當[n=1]時，[mij]即為攻擊行為;當[n=2]時，[m2ij=k=1n（mikΔmkj）]顯然成立;假設[n=t]時，[mtij=k=1n（mn-1ikΔmkj）]，則[n=t+1]時，[mt+1ij=k=1n（mtikΔmkj）]，其中[mtik] 表示[ei]～[ek]的[t]步攻擊行為，[mt+1ij] 表示在[t]步攻擊行為之后擁有的屬性[ek]，再進行[ek]～[ej]的單步攻擊，原式得證。

圖2右圖的單步屬性鄰接矩陣如下：

對此矩陣進行計算得到兩步屬性鄰接矩陣[M2=M?M]，其中[m216=（m12Δm26）?（m13Δm36）]，表示屬性[e1]可以通過[m12Δm26]和[m13Δm36]兩種兩步連續攻擊行為獲得屬性[e5]，路徑表示為（e1（C2）e2（C5）e5）∪（e1（C3）e3（C6）e5）。

研究表明，20臺主機對應的攻擊圖也相當龐大復雜[14]。采用屬性鄰接矩陣來表示攻擊圖，不僅保留了鄰接矩陣的可視性優點，也可直觀表示出任意兩個節點之間的單步、多步原子攻擊序列，降低了理解和分析的難度。相比頂點和有向邊的表示方法，該方法不僅適用于小規模攻擊圖，在較大規模的攻擊圖中更能體現出優勢。

多步屬性鄰接矩陣的時間復雜度不超過O（n3），n為目標網絡中的節點數;而在攻擊圖中隨著節點數的增加，時間復雜度呈指數型增長。

1.3 ?路徑博弈

網絡攻防雙方的策略依存性正是博弈論的基本觀點，從博弈的視角研究網絡攻防行為具有較高的科學性和合理性。攻防雙方博弈策略的形式可由一個三元組[G=S，T，U]來表示，其中S代表參與者的集合，T代表攻防雙方的策略集（即攻防路徑的集合），[U]代表攻防雙方的效用函數。

定義5：[S={a，d}]，[a]代表攻擊者，[d]代表防御者。

定義6：[T={T1，T2，…，T3}]，并且對于任意的[i]，[Ti] 不為空集，[Ti=（ti1，ti2，…，tin）]，那么攻擊者的策略集[Ta=（ta1，ta2，…，tan），]防御者的策略集[Td=（td1，td2，…，tdm）]。

定義7：[U]為參與者的效用函數的集合，[U=（U1，U2，…，Un）]，[Ui=Ri-Ei]，其中[R（Revenue）]為收益，[E（Expenditure）]為支出。

為簡化攻擊路徑和防御路徑效用值的計算，不考慮脆弱點之間的關聯性等其他因素，設[α]為一個原子攻擊，假定攻擊者的攻擊路徑為[Wa=（α1，α2，…，αn）]，防御者的防御路徑為[Wd=（α1，α2，…，αm）]，攻擊路徑效用值公式[U（Wa）=i=1nU（αi）] ，防御路徑效用值公式[U（Wd）=i=1mU（αi）]。

由納什均衡存在性定理可知，任意給定一個策略形式的三元組[G={（a，d），（Ta，Td），（Ua，Ud）}]，攻防雙方的策略分別為[Ta=（ta1，ta2，…，tan）]和[Td=（td1，td2，…，tdm），]通過效用值計算并生成博弈矩陣進行博弈便可得到其各自策略的概率分布[P（a）=（Pa1，Pa2，…，Pan），][P（d）=（Pd1，Pd2，…，Pdm）][0≤Pdi≤1，][0≤Pai≤1]且[i=1nPai=1，i=1nPdi=1]。算法如下：

輸入：攻防雙方，網絡攻防的策略集

輸出：可能攻擊路徑與最優防御策略

1.初始化[G={S，T，U}];

2.通過屬性鄰接矩陣運算得出所有可能路徑，建立攻防雙方策略集合：

[Ta=（ta1，ta2，…，tan），Td=（td1，td2，…，tdm）;]

3.計算攻防所有路徑效用[U（Wa）]，[U（Wd）];

4.生成效用值博弈矩陣;

5.調用納什均衡混合策略求解子算法;

6.得出可能的攻擊路徑與防御路徑的[P（a）]和[P（d）]，并進行分析，確定最優的防御策略;

7.算法結束

納什均衡混合策略求解子算法如下：

輸入：攻防博弈效用矩陣

輸出：納什均衡解

1.Maximize ?[x]

2.[Subject to ??tj∈Tj]

3.[i=1mpiU（ti，tj）≥x]

4.[i=1mpi=1，0≤pi≤1]

該博弈算法關鍵是博弈模型的建立與求解，包括策略集建立，策略效用值的量化和納什均衡值的求解。其時間復雜度主要取決于納什均衡子算法的求解，可用非線性規劃來求解，該模型的時間復雜度具有多項式級別，計算速度快，可以滿足防御系統快速響應的需求。

2 ?實 ?驗

2.1 ?實驗環境

圖3為民航某業務系統的網絡拓撲圖，本文在該環境模擬以下實驗，驗證了所提方法的簡潔性和有效性。模擬環境包含1臺Windows XP系統的攻擊主機，6臺服務器：Windows Server Web服務器、Windows Server MS SQL服務器、Windows Server FTP服務器、Linux Mail 服務器、DNS服務器、打印服務器。

圖3 ?網絡拓撲圖

2.2 ?實驗過程及結果

根據各主機之間可利用的脆弱點及脆弱點之間的關系，繪制屬性攻擊圖，并簡化，如圖4所示。

圖4 ?原始攻擊圖的簡化（二）

根據簡化后的攻擊圖可得到的屬性鄰接矩陣為：

通過查閱脆弱點信息，得到原子攻擊信息表見表1。

表1 ?原子攻擊信息表

據以往研究成果，利用各脆弱點進行攻擊或防御的攻防雙方的效用值信息如表2所示。

表2 ?攻防雙方效用值信息表

研究人員通過對大量真實攻擊數據的統計分析，現實的攻擊中有效攻擊路徑長度一般不會超過3。因此本文不對較長的攻擊路徑進行研究。將屬性鄰接矩陣進行運算，并根據表2攻防雙方的效用值信息表和第1.3節中求解攻防雙方路徑效用值的公式可以得到攻擊路徑的效用值信息表，如表3所示。

表3 ?攻防雙方路徑效用值信息表

表4為攻防雙方的博弈矩陣。利用該模型求解表4的攻防效用矩陣，可以得到一個混合策略的納什均衡[（0，1，0，0，0，0），（0，0.783 4，0，0，0.216 6，0）]，即攻擊者最可能選擇C1→C2來進行攻擊，防御者以0.783 4的概率選擇C1→C2路徑進行防御，以0.216 6的概率選擇C1→C3→C5進行防御。因此，防御方最優防御策略應是以0.783 4的概率向Web服務器安裝微軟Bulletin MS13?004最新版本的安全更新，升級FTP服務器Serv?U至高版本;以0.216 6的概率向Web服務器安裝微軟Bulletin MS13?004最新版本的安全更新并安裝微軟IIS MS11?004安全更新。

3 ?結 ?論

本文提出一種新的網絡風險控制的模型。用BFS算法簡化攻擊圖，通過屬性鄰接矩陣的運算進一步降低對大規模攻擊圖分析的難度，增強了可視性，可快速得出任意兩個節點之間的所有路徑。最后通過博弈方法得出可能性較高的攻擊路徑和最佳防御策略，幫助網絡管理員在有限的資源條件下有針對性地采取措施，加固關鍵節點。該模型具有多項式級別的時間復雜度，可快速響應防御系統的需求，極具實際意義?，F實場景中攻防雙方的動態博弈也是以后研究的重點。目前我國對風險控制的研究較少，該模型可以為以后網絡風險管控體系的建立提供參考。

注：本文通訊作者為李躍凱。

參考文獻

[1] Computer Security Institute. 15th annual 2010/2011 computer crime and security survey [J]. [2011?08?09]. https：//www.docin.com/p?241701547.html.

[2] 陸余良，宋舜宏，程微微，等.網絡攻擊圖生成方法分析[J].安徽大學學報（自然科學版），2010，34（4）：23?30.

LU Yuliang， SONG Shunhong， CHENG Weiwei， et al. Analysis of the generation approaches to network attack graphs [J]. Journal of Anhui University （Natural sciences）， 2010， 34（4）： 23?30.

[3] 陳鋒，張怡，蘇金樹，等.攻擊圖的兩種形式化分析[J].軟件學報，2010，21（4）：838?848.

CHEN Feng， ZHANG Yi， SU Jinshu， et al. Two formal analysis of attack graphs [J]. Journal of software， 2010， 21（4）： 838?848.

[4] OU X M， BOYER W F， MCQUEEN M A. A scalable approach to attack graph generation [C]// Proceedings of the 13th ACM Conference on Computer and Communications Security. Alexandria： ACM， 2006： 336?345.

[5] HOMER J， OU X M ， SCHMIDT D. A sound and practical approach to quantifying security risk in enterprise networks [J/OL]. [2013?08?09]. http：//people.cs.ksu.edu/～xou/publications/tr_homer_0809.pdf.

[6] NOEL S， JAJODIA S. Understanding complex network attack graphs through clustered adjacency matrices [C]// Proceedings of the 21st Annual Computer Security Applications Conference. Tucson： IEEE， 2006： 160?169.

[7] LYE K W， WING J M. Game strategies in network security [J]. International journal of information security， 2015， 4（1）： 71?86.

[8] 姜偉.基于攻防博弈模型的主動防御關鍵技術研究[D].哈爾濱：哈爾濱工業大學，2010.

JIANG Wei. Research on the key technology of active defense based on offensive and defensive game model [D]. Harbin： Harbin Institute of Technology， 2010.

[9] 李慶朋，鄭連清，張串絨，等.基于脆弱點利用關聯的攻擊圖優化方法[J].計算機工程，2012，38（21）：129?132.

LI Qingpeng， ZHENG Lianqing， ZHANG Chuanrong， et al. Optimization method for attack graph based on vulnerability exploit correlation [J]. Computer engineering， 2012， 38（21）： 129?132.

[10] SHEYNER O M. Scenario graphs and attack graphs [D]. Pittsburgh： Carnegie Mellon University， 2004.

[11] WANG L， NOEL S， JAJODIA S. Minimum?cost network hardening using attack graphs [J]. Computer communications， 2006， 29（18）： 3812?3824.

[12] 葉云，徐錫山，賈焰，等.基于攻擊圖的網絡安全概率計算方法[J].計算機學報，2010，33（10）：1987?1996.

YE Yun， XU Xishan， JIA Yan， et al. An attack graph?based probabilistic computing approach of network security [J]. Chinese journal of computers， 2010， 33（10）： 1987?1996.

[13] 蘇婷婷，潘曉中，肖海燕，等.基于屬性鄰接矩陣的攻擊圖表示方法研究[J].電子與信息學報，2012，34（7）：1744?1747.

SU Tingting， PAN Xiaozhong， XIAO Haiyan， et al. Research on attack graph based on attribute adjacency matrix [J]. Journal of electronics & information technology， 2012， 34（7）： 1744?1747.

[14] RITCHEY R， O′BERRY B， NOEL S. Representing TCP/IP connectivity for topological analysis of network security [C]// Proceedings of the 18th Annual Computer Security Applications Conference. Las Vegas： IEEE， 2012： 156?165.