團樹傳播算法在貝葉斯網(wǎng)絡(luò)攻擊圖中概率計算分析

顧士星

摘 要：攻擊圖模型中對屬性節(jié)點的狀態(tài)評估主要是通過計算該節(jié)點置信度進而分析節(jié)點的威脅狀態(tài)。當(dāng)前運用貝葉斯攻擊圖評估整體網(wǎng)絡(luò)安全性，在計算貝葉斯攻擊圖先驗概率以及結(jié)合入侵檢測系統(tǒng)計算后驗概率方面，存在屬性節(jié)點增加，貝葉斯網(wǎng)的計算復(fù)雜度呈指數(shù)級增長的問題。針對計算復(fù)雜度問題，提出了一種將貝葉斯網(wǎng)絡(luò)攻擊圖轉(zhuǎn)化成團樹的方法，降低了計算過程中的時間復(fù)雜度。實驗結(jié)果表明，采用該方法使計算節(jié)點的置信度、時間復(fù)雜度得到一定程度降低。

關(guān)鍵詞：貝葉斯網(wǎng)絡(luò)；攻擊圖；團樹傳播；風(fēng)險評估

DOIDOI：10.11907/rjdk.171323

中圖分類號：TP309

文獻標(biāo)識碼：A 文章編號：1672-7800（2017）007-0174-04

0 引言

云計算、虛擬化等技術(shù)的發(fā)展使人們可以便捷地、隨需應(yīng)變地從可配置資源共享池中獲取計算、存儲、網(wǎng)絡(luò)等資源，在便利的同時也帶來了網(wǎng)絡(luò)規(guī)模越來越大、主機應(yīng)用數(shù)量呈指數(shù)級增長等問題。網(wǎng)絡(luò)攻擊牽一發(fā)而動全身，網(wǎng)絡(luò)管理人員需要實時了解網(wǎng)絡(luò)的運行狀態(tài)、服務(wù)器的安全性等。網(wǎng)絡(luò)安全的態(tài)勢預(yù)測可以幫助系統(tǒng)管理員更好地理解網(wǎng)絡(luò)安全態(tài)勢，為采取防護策略提供參考，有效降低網(wǎng)絡(luò)安全風(fēng)險。本文使用基于攻擊圖（Attack Graph）模型的方法評估網(wǎng)絡(luò)安全態(tài)勢，構(gòu)建貝葉斯網(wǎng)絡(luò)攻擊圖（Bayesian Attack Graph），推理方法采用團樹（Clique Tree）方法。團樹傳播算法可應(yīng)用在局域網(wǎng)中每個機器的威脅指數(shù)分析等方面，對相應(yīng)主機采取升級系統(tǒng)、安裝補丁等防護措施。

1 相關(guān)工作

攻擊圖技術(shù)研究方向主要包括：目標(biāo)模型構(gòu)建、攻擊圖構(gòu)建以及攻擊圖分析。在目標(biāo)模型構(gòu)建方面，從目標(biāo)網(wǎng)絡(luò)和攻擊者建模兩個角度來構(gòu)建目標(biāo)模型， Sheyne[1]在前人的基礎(chǔ)上深入分析后，提出了經(jīng)典的五元組來描述目標(biāo)網(wǎng)絡(luò)。Ou等[1-2]提出一種使用邏輯推理分析網(wǎng)絡(luò)的脆弱性，并基于該方法提供了生成攻擊圖的工具（Multi-host， multistage vulnerability analysis， MulVAL），為攻擊圖分析提供了基礎(chǔ)。Xie等[3]使用貝葉斯網(wǎng)絡(luò)對攻擊發(fā)生的不確定性進行建模，但是沒有引入攻擊事件的后驗概率。在攻擊圖分析方面，Homer等[4]提出借助漏洞的指標(biāo)量化網(wǎng)絡(luò)整體安全性。張瑜等[5]通過使用危險理論的APT多步攻擊實時響應(yīng)模型，解決了不依據(jù)變量實時改變攻擊圖模型的問題。高妮等[6]結(jié)合入侵檢測系統(tǒng)檢測到的實時攻擊事件，運用貝葉斯推理方法對單步攻擊行為的后驗概率進行動態(tài)更新，實現(xiàn)對目標(biāo)網(wǎng)絡(luò)整體安全性評估。

上述攻擊圖分析方法，能夠很完整地表示出所有的攻擊路徑，但是無法定量描述某個節(jié)點被攻擊者獲得的概率以及多個攻擊之間的因果關(guān)系等。基于貝葉斯網(wǎng)絡(luò)攻擊圖的方法在進行概率推理時無法解決大規(guī)模網(wǎng)絡(luò)中后驗概率計算的NP問題。本文使用團樹傳播算法對貝葉斯網(wǎng)絡(luò)攻擊進行精確推斷，能夠很好地改善后驗概率計算存在的問題。

2 貝葉斯網(wǎng)絡(luò)攻擊圖

大部分攻擊都是利用一系列脆弱性漏洞的組合來攻破系統(tǒng)。攻擊圖是一種用于建立系統(tǒng)脆弱信息和攻擊者用來獲得一定目的的所有可能攻擊序列的一般化表示方法。使用攻擊圖可以發(fā)現(xiàn)潛在的脆弱性信息進而評估網(wǎng)絡(luò)的安全性，通過分析脆弱性之間的依賴關(guān)系和內(nèi)部網(wǎng)絡(luò)配置來分析多個有序原子攻擊組合，描述網(wǎng)絡(luò)系統(tǒng)中可能存在的攻擊路徑。貝葉斯網(wǎng)絡(luò)攻擊圖[7]可以解決不確定性問題，如攻擊之間相互的因果關(guān)系以及被攻擊利用成功的概率等，而攻擊圖只能表示存在攻擊卻無法描述節(jié)點的威脅程度。

貝葉斯網(wǎng)絡(luò)攻擊圖模型主要描述了資源屬性狀態(tài)、攻擊行為及相互因果關(guān)系。資源屬性、原子攻擊和局部條件概率定義如下：

定義1（資源屬性）：屬性描述一個資源（S）被攻擊者獲取的狀態(tài)，其中狀態(tài)的取值符合伯努利隨機二值變量。

資源屬性狀態(tài)取值為S=0或者S=1。其中1表示資源被攻擊者占據(jù)，Pr（S）表示資源狀態(tài)為1的概率，相反的0表示資源未被占據(jù)，Pr（S）表示資源狀態(tài)為0的概率。

定義2（原子攻擊a）：定義原子攻擊a：Spre⊕Spost→[0，1]，其中，Spre，Spost∈S且滿足以下條件：①Spre≠Spost；②給定Spre = 1且Spost=1，狀態(tài)從Spre成功加入Spost的概率P（Spre，Spost）>0；

③不存在S1，S2，…，Sj∈S-{Spre，Spost}，滿足P（Spre，S1）>0，P（S1，S2）>0，…，P（Sj-1，Sj）>0且P（Sj，Spost）>0。

定義3（貝葉斯網(wǎng)絡(luò)攻擊圖）：貝葉斯網(wǎng)絡(luò)攻擊圖定義為一個有向無環(huán)圖BAG=（S，τ，A，ε，Lc），其中：①S=Ninternl∪Nexternal∪Nterminal，Ninternal為攻擊圖的內(nèi)部節(jié)點，Nexternal表示攻擊圖的外部節(jié)點（遠程攻擊者），Nterminal表示攻擊圖的目標(biāo)節(jié)點；②τS×S，其中，（Spre，Spost）∈τ且Spre⊕Spost∈A表示兩個資源間可達，即存在攻擊路徑。定義狀態(tài)節(jié)點Si的父節(jié)點為Pa[Si]={Sj∈S|（Sj，Si）∈τ}；③A={ai|i=1，…，n}表示攻擊圖中存在原子攻擊，ai=0或1分別表示原子攻擊未發(fā)生或已發(fā)生；④ε表示狀態(tài)節(jié)點與其父節(jié)點之間的關(guān)系，分解為一個二元組，dj∈{AND，OR}。dj=AND表示一次原子攻擊達到狀態(tài)Sj需滿足其所有父節(jié)點狀態(tài)全部為1，即Sj=1→Si∈Pa[Sj]，Si=1。dj=OR表示一次原子攻擊到達狀態(tài)Sj滿足其父節(jié)點中存在一個節(jié)點的狀態(tài)為1，即Sj=1→Si∈Pa[Sj]，Si=1；⑤Lc表示一組條件獨立的率分布函數(shù)，每一個資源屬性Sj∈Ninternal∪Nterminal都有一個局部條件概率分布（Local Conditional Probability Distribution，LCPD）。

定義4 （LCPD函數(shù)）：假設(shè)BAG=（S，τ，A，ε，Lc）是一個攻擊圖，同時Sj∈Ninternal∪Nterminal，即資源屬性Sj屬于攻擊圖內(nèi)節(jié)點或者攻擊者占據(jù)的節(jié)點。假設(shè)vi是與原子攻擊Si⊕Sj相關(guān)的漏洞被成功利用的概率。資源Sj的局部條件概率取決于該節(jié)點與所有父節(jié)點之間的ε關(guān)系。

當(dāng)dj=AND時：Pr（Sj|Pa[Sj]）=0，Pr（∩Si=1vi）， Si∈Pa[Sj]|Si=0其它（1）

當(dāng)dj=OR時：

2.1 漏洞利用成功率計算

每一個節(jié)點的LCPD需要安全管理員根據(jù)攻擊過程中每個漏洞的利用成功率確定。漏洞的利用成功率與每個漏洞被利用的難易程度有關(guān)。本文采用美國通用標(biāo)準(zhǔn)與技術(shù)研究院提供的通用CVSS[8] （ Common Vulnerability Scoring System）評估漏洞利用成功率。

CVSS評分如表1所示，由0～10范圍的數(shù)字來度量，其中每個漏洞由base、temporal和environmental屬性組成，base屬性跟漏洞利用成功概率有關(guān)。

漏洞利用成功概率可從CVSS的子項exploitability計算獲得，計算公式為Pr（vi）=2×AV×AC×Au。

2.2 構(gòu)建貝葉斯網(wǎng)絡(luò)攻擊圖

本文研究關(guān)注點主要集中在貝葉斯網(wǎng)絡(luò)攻擊圖分析，貝葉斯網(wǎng)絡(luò)攻擊圖構(gòu)建主要借助于Ou等提出的MulVAL工具生成攻擊圖方法，具體步驟如下：

（1）基礎(chǔ)信息采集。局域網(wǎng)中資產(chǎn)信息、網(wǎng)絡(luò)配置以及防火墻配置等信息；基于OVAL掃描器對網(wǎng)絡(luò)中主機的漏洞掃描，利用CVSS評估系統(tǒng)對漏洞利用成功率進行評估，并生成漏洞利用成功率P。

（2）攻擊圖模型建立。利用MulVAL工具根據(jù)采集的信息生成攻擊圖。

（3）貝葉斯網(wǎng)絡(luò)攻擊圖模型構(gòu)建。貝葉斯網(wǎng)絡(luò)攻擊圖構(gòu)建主要依賴MulVAL生成的攻擊圖以及漏洞利用成功概率來生成網(wǎng)絡(luò)結(jié)構(gòu)模型以及LCPD函數(shù)的計算，生成貝葉斯模型算法如算法1所示：

算法1 BAG_gengeration（AG，Pstart，P）輸入：攻擊圖AG=（S，τ，a，ε）；Pstart表示遠程攻擊者初始攻擊能力，即S0的取值；P表示漏洞利用成功率。

輸出：貝葉斯網(wǎng)絡(luò)攻擊圖BAG=（S，τ，A，ε，Lc）。初始化攻擊圖BAG；復(fù)制攻擊圖AG的資源屬性節(jié)點、邊、原子攻擊每條關(guān)系至BAG的S，τ，A，ε；for （each node Sj in BAG）； if（ j = 1 ）； Lc1（ S1 = True ） = Pstart； Lc1（ S1 = False ） = 1-Pstart； else； for（each edge τj in BAG）； if（ d in εi = AND ）；使用公式（1）計算LCPD； else； 使用公式（2）計算LCPD； endfor（08）；endfor（03）

3 團樹傳播算法

在給定一個貝葉斯網(wǎng)絡(luò)模型的情況下，根據(jù)已知條件，利用條件概率計算出感興趣節(jié)點發(fā)生的概率。使用貝葉斯網(wǎng)絡(luò)，實現(xiàn)根據(jù)網(wǎng)絡(luò)中節(jié)點已存在的值推斷其它節(jié)點的概率值。

貝葉斯網(wǎng)絡(luò)推理[9]有3種方式：①因果推理（Causal Inference）：從原因出發(fā)，根據(jù)一定的原因，求出在該原因下某個或多個節(jié)點結(jié)果發(fā)生的概率；②診斷推理（Diagnostic Inference）：由結(jié)果推出原因，根據(jù)產(chǎn)生的結(jié)果，計算條件概率的后驗概率即為導(dǎo)致該結(jié)果發(fā)生的原因；③混合推理（Mixed Inference）：既包括因果推理又包括診斷推理。

貝葉斯網(wǎng)絡(luò)推理算法分為精確推理算法和近似推理算法。團樹傳播算法首先將貝葉斯圖轉(zhuǎn)換成一個團樹[10]，然后通過信息傳遞將信息依次傳遍團樹的每個節(jié)點，最終使團樹滿足全局一致性。

3.1 團樹構(gòu)造

團樹構(gòu)造包括構(gòu)造端正圖、三角化以及構(gòu)造團樹的過程。端正圖的構(gòu)造主要涉及對貝葉斯網(wǎng)絡(luò)模型中具有相同孩子的父節(jié)點用無向邊連接起來，并將有向邊轉(zhuǎn)化為無向邊。貝葉斯網(wǎng)絡(luò)攻擊圖構(gòu)造端正圖見圖1。

三角化過程本質(zhì)上就是對頂點按照以下順序進行：①預(yù)消除頂點的鄰居頂點節(jié)點聯(lián)接起來；②刪除該頂點，并添加邊；③刪除的頂點滿足添加的邊最少的原則。端正圖的消元順序如表2所示。

結(jié)果形成的團樹結(jié)構(gòu)如圖2所示。

3.2 團樹傳播推理算法

團樹傳播推理算法先將貝葉斯網(wǎng)絡(luò)轉(zhuǎn)換為一種二次結(jié)構(gòu)，通過對二次結(jié)構(gòu)的推理得到貝葉斯網(wǎng)絡(luò)推理的精確結(jié)果。SS=（CT，PP），其中：CT=（C，S）為團樹，C為貝葉斯網(wǎng)絡(luò)中的團集，S為CT中的邊集；PP為與團和邊相關(guān)的概率勢（Probability Potentials），可從每個團中的變量概率分布經(jīng)計算得到。在SS上計算聯(lián)合概率是通過計算CT上團和邊的PP實現(xiàn)的。團樹傳播推理算法的目的是計算每一個非證據(jù)變量的后驗概率分布。團樹傳播算法流程如下：算法2 團樹傳播算法Clique（G，Gc，An）輸入：G貝葉斯攻擊圖；Gc表示一個覆蓋G的團樹；An表示原子攻擊是否發(fā)生的取值。輸出：每一個非攻擊變量S的后驗概率P{S/A1=a1，A2=a2，…，An=an}

利用G將Gc初始化

在Gc的函數(shù)中，將證據(jù)變量集合中的An設(shè)置為其取值

在Gc中任選一個團節(jié)點Cp作為樞紐

for（每一個與Cp相鄰的節(jié)點C）

調(diào)用CollectMessage（Cp，C）

for（每一個與Cp相鄰的節(jié)點C）

調(diào)用DistributeMessage（Cp，C）

for（G中每一個非證據(jù)變量X） a：選擇一個包含X的團Cx； b：把初始化時和信息傳遞過程與儲存在Cx處的函數(shù)相乘，得到一個C'x的函數(shù)h（C'x），這里C'x=CxE； c：計算∑C'x＼＼{X}h（C'x）∑C'xh（C'x）即為證據(jù)變量X的后驗概率。endprint

上述算法中，CollectMessage（Cp，C）表示信息的分發(fā)，即將Cp節(jié)點所含有的信息向團樹中所有的節(jié)點依次傳播過去。DistributeMessage（Cp，C）表示信息的收集，即將團樹除Cp之外的團節(jié)點信息收集到Cp的團節(jié)點。其中，相鄰節(jié)點的信息傳遞算法sendMessage（C，C'）描述如下：輸入：團樹中的兩個相鄰節(jié)點C，C'。作用：計算并存儲從C到C'的信息。設(shè)C'1，C'2，…，C'k為除C以外的其它鄰居節(jié)點；

對i=1，2，…，k，gi為在節(jié)點C中存儲的C'i到C的信息；設(shè)f1，f1，…，fl為初始化時存儲在C處的函數(shù)，且設(shè)Z=CC'∪E ；計算如下函數(shù)：ψ←∑Z∏li=1fi∏kj=1gj；ψ即為C到C'的信息，將此信息存儲在節(jié)點C中，以備以后信息傳遞時使用。

4 實驗分析

給出一個網(wǎng)絡(luò)拓撲結(jié)構(gòu)如圖3所示，防火墻規(guī)則設(shè)置遠程攻擊者通過端口能夠訪問主機的方式，如圖3所示，防火墻后主要包括Web服務(wù)器、文件服務(wù)器以及數(shù)據(jù)庫服務(wù)器等。

漏洞信息獲取采用Oval漏洞掃描器掃描實驗環(huán)境中的主機，結(jié)合網(wǎng)絡(luò)拓撲等信息作為Mulval工具的輸入信息，生成通用的攻擊圖模型。

使用算法1來生成該節(jié)中定義的部分貝葉斯網(wǎng)絡(luò)攻擊圖模型如圖4所示。節(jié)點S1、S2的概率表示攻擊者初始的攻擊能力，定義為P（S1）=0.6、P（S2）= 0.8，此處略去每個節(jié)點的LCPD表，貝葉斯網(wǎng)絡(luò)先驗概率計算結(jié)果如表3所示。

結(jié)合入侵檢測系統(tǒng)的入侵報警數(shù)據(jù)以及漏洞利用成功率等，檢測到發(fā)生A3攻擊事件，根據(jù)算法2使用團樹傳播算法計算貝葉斯網(wǎng)絡(luò)算法后驗概率，計算結(jié)果如表3所示。

通過在防火墻后不同主機中安裝多個不同應(yīng)用來模擬資源節(jié)點變化，多次使用Oval漏洞掃描器對系統(tǒng)掃描，利用文中所述方法構(gòu)建貝葉斯攻擊圖以及團樹攻擊圖。通過多次試驗計算分析得到使用貝葉斯算法以及團樹傳播算法的時間對比如圖5所示，可以看出使用團樹的方法來計算貝葉斯的后驗概率，在算法時間復(fù)雜度上得到了一定程度的降低。

5 結(jié)語

使用基于團樹傳播推理分析的方法對貝葉斯網(wǎng)絡(luò)攻擊圖進行推理分析，能夠在一定程度上降低貝葉斯攻擊圖推理的時間復(fù)雜度，實驗結(jié)果驗證了這個方法的可行性。能夠形式化描述一個資源節(jié)點被攻擊者攻擊成功的概率，以及獲得該資源節(jié)點后下一個最具威脅性的資源節(jié)點，有利于網(wǎng)絡(luò)管理人員采取相應(yīng)措施，如修復(fù)官方給出的補丁、關(guān)閉不需開啟的網(wǎng)絡(luò)服務(wù)等，進一步提高信息系統(tǒng)的安全性。本文提出的推理方法在一定程度上可以減少計算貝葉斯攻擊圖后驗概率的時間。消元順序的選擇對概率計算的時間復(fù)雜度有一定影響，本文采取隨機選擇方式進行消元順序選擇。未來將研究最優(yōu)化的消元順序以進一步降低概率計算時間。利用攻擊圖來尋找整個信息系統(tǒng)的脆弱點對保護系統(tǒng)安全、維護個人信息隱私等有著非常重要的意義。

參考文獻：

[1]SHEYNER O， WING J. Tools for generating and analyzing attack graphs[J]. Lecture Notes in Computer Science， 2003.

[2]OU X. A logic-programming approach to network security analysis[EB/OL]. http：//www.cs.princeton.edu/research/techreps/TR-735-05.

[3]XIE P， LI J H， OU X， et al. Using Bayesian networks for cyber security analysis[C]. IEEE/IFIP International Conference on Dependable Systems & Networks， Chicago， 2010.

[4]HOMER J， ZHANG S， OU X， et al. Aggregating vulnerability metrics in enterprise networks using attack graphs[J]. Journal of Computer Security， 2013，21（4）：561-597.

[5]張瑜， QINGZHONG LIU， 李濤， 等. 基于危險理論的APT攻擊實時響應(yīng)模型[J]. 四川大學(xué)學(xué)報：工程科學(xué)版， 2015，47（4）：83-90.

[6]高妮， 高嶺， 賀毅岳， 等. 基于貝葉斯攻擊圖的動態(tài)安全風(fēng)險評估模型[J]. 四川大學(xué)學(xué)報：工程科學(xué)版， 2016，48（1）：111-118.

[7]POOLSAPPASIT N，DEWRI R， RAY I. Dynamic security risk management using bayesian attack graphs[J]. IEEE Transactions on Dependable & Secure Computing， 2011，9（1）：61-74.

[8]SCHIFFMAN M.Common vulnerability scoring system（CVSS）[EB/OL].[2016-09-07].http：//www.first.org/cvss/user-guide.

[9]TARONI F. Bayesian networks for probabilistic inference and decision analysis in forensic science[M]. Wiley， 2014.

[10]李志瑤， 宗芳， 張屹山. 貝葉斯網(wǎng)絡(luò)推理分析的團樹傳播算法——以停車行為分析為例[J]. 長春大學(xué)學(xué)報， 2012（5）：505-509.endprint