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

顧兆軍 李躍凱

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

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

中圖分類號： 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 ?引 ?言

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

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

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

1 ?風險控制模型

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

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

1.1 ?簡化攻擊圖

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

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

1） 計算每個滲透節(jié)點父節(jié)點個數(shù)，預(yù)先將每個滲透節(jié)點置為FALSE，且將其number_Child值置0。

2） 設(shè)定隊列q，將初始原子攻擊節(jié)點依次插入。

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

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

輸入：攻擊圖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節(jié)點的簡化后攻擊圖

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

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

1.2 ?形成屬性鄰接矩陣

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

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

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

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

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

定義4： 設(shè)矩陣[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）]顯然成立;假設(shè)[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]兩種兩步連續(xù)攻擊行為獲得屬性[e5]，路徑表示為（e1（C2）e2（C5）e5）∪（e1（C3）e3（C6）e5）。

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

多步屬性鄰接矩陣的時間復(fù)雜度不超過O（n3），n為目標網(wǎng)絡(luò)中的節(jié)點數(shù);而在攻擊圖中隨著節(jié)點數(shù)的增加，時間復(fù)雜度呈指數(shù)型增長。

1.3 ?路徑博弈

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

定義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]為參與者的效用函數(shù)的集合，[U=（U1，U2，…，Un）]，[Ui=Ri-Ei]，其中[R（Revenue）]為收益，[E（Expenditure）]為支出。

為簡化攻擊路徑和防御路徑效用值的計算，不考慮脆弱點之間的關(guān)聯(lián)性等其他因素，設(shè)[α]為一個原子攻擊，假定攻擊者的攻擊路徑為[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]。算法如下：

輸入：攻防雙方，網(wǎng)絡(luò)攻防的策略集

輸出：可能攻擊路徑與最優(yōu)防御策略

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

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

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

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

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

5.調(diào)用納什均衡混合策略求解子算法;

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

7.算法結(jié)束

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

輸入：攻防博弈效用矩陣

輸出：納什均衡解

1.Maximize ?[x]

2.[Subject to ??tj∈Tj]

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

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

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

2 ?實 ?驗

2.1 ?實驗環(huán)境

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

圖3 ?網(wǎng)絡(luò)拓撲圖

2.2 ?實驗過程及結(jié)果

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

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

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

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

表1 ?原子攻擊信息表

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

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

研究人員通過對大量真實攻擊數(shù)據(jù)的統(tǒng)計分析，現(xiàn)實的攻擊中有效攻擊路徑長度一般不會超過3。因此本文不對較長的攻擊路徑進行研究。將屬性鄰接矩陣進行運算，并根據(jù)表2攻防雙方的效用值信息表和第1.3節(jié)中求解攻防雙方路徑效用值的公式可以得到攻擊路徑的效用值信息表，如表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進行防御。因此，防御方最優(yōu)防御策略應(yīng)是以0.783 4的概率向Web服務(wù)器安裝微軟Bulletin MS13?004最新版本的安全更新，升級FTP服務(wù)器Serv?U至高版本;以0.216 6的概率向Web服務(wù)器安裝微軟Bulletin MS13?004最新版本的安全更新并安裝微軟IIS MS11?004安全更新。

3 ?結(jié) ?論

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

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

參考文獻

[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] 陸余良，宋舜宏，程微微，等.網(wǎng)絡(luò)攻擊圖生成方法分析[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] 姜偉.基于攻防博弈模型的主動防御關(guān)鍵技術(shù)研究[D].哈爾濱：哈爾濱工業(yè)大學，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] 李慶朋，鄭連清，張串絨，等.基于脆弱點利用關(guān)聯(lián)的攻擊圖優(yōu)化方法[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] 葉云，徐錫山，賈焰，等.基于攻擊圖的網(wǎng)絡(luò)安全概率計算方法[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.