動態攻擊網絡Markov演化博弈安全分析模型*

李　艷，黃光球，張　斌

西安建筑科技大學 管理學院，西安 710055

動態攻擊網絡Markov演化博弈安全分析模型*

李艷+，黃光球，張斌

西安建筑科技大學 管理學院，西安 710055

攻防演化；演化博弈；Markov博弈；網絡攻擊模型；網絡安全

1　引言

在信息技術革命的背景下，計算機、網絡通信等技術使全世界的運轉方式發生了根本性的改變，尤其是近年來云計算、大數據、物聯網等理念的深入研究與產業化，使信息的控制權成為新的戰略制高點。2014年2月，“中央網絡安全和信息化小組”的成立標志著我國互聯網國家意識的蘇醒，彰顯了國家信息安全戰略的重要性。但隨著網絡的開放化和新型攻擊手段的簡易化，各種組織嚴密、目標直接的盈利型組織會對國家信息化程度較高的基礎設施造成嚴重的破壞，如何保護網絡空間成為安全領域的研究熱點，也與核問題一起成為新世紀亟待解決的難題。

網絡安全技術的發展主要分為入侵檢測、主動防御和態勢感知3個階段。入侵檢測（intrusion detection system，IDS）起源于Anderson的技術研究報告[1]，之后的研究大體上可以分為異常檢測和誤用檢測兩類[2]，目前大部分科研機構和商業組織的IDS也是基于這兩類技術的。入侵檢測技術在網絡攻擊發生時給出預警信息來保證網絡安全，但其對繞墻隱秘攻擊、多步復合攻擊等無能為力。針對IDS等被動防御技術的缺陷，脆弱性風險評估等主動分析技術[3]成為研究的熱點，意圖在攻擊發生之前制定防御策略。風險評估主要分為模型構建和分析方法構建兩個步驟。模型構建的過程將網絡中和風險評估相關的各要素進行抽象并以形式化的語言表達，目前的工作主要圍繞著攻擊圖模型[4-5]展開。分析方法構建主要包含定性分析和定量分析兩種：定性分析的關注點是脆弱性邏輯關聯問題，即通過對攻擊場景的可視化分析得出所有可能攻擊路徑的過程[6-7]；定量分析一般在模型構建過程中同時對一些因素進行量化，通過數字化的計算方法表述網絡的安全形勢[8-9]。隨著對可生存性研究的深入，1999年，Bass等人首次提出了網絡態勢感知（network situation awareness，NetSA）的概念[10]，意圖感知時間和空間環境中的元素，使人們可以更好地把握網絡整體安全狀況及預測未來變化趨勢。在此方面的研究大都以Bass態勢感知概念模型為基礎進行評估算法優化[11-12]，很少有成型系統的實現。

網絡攻防對抗過程中，一定存在著非合作性、策略依存性等特征，因此博弈論一直是網絡安全的重要研究方向[13]。博弈論與IDS技術的結合多數都建立在一次博弈分析的基礎上[14]，因此本文更關注博弈論與主動防御或態勢感知技術的結合。我國學者姜偉等人[15]以攻擊圖為基礎提出了防御圖模型，同時基于博弈基礎給出了安全測評及防御算法，但模型對攻擊策略和效用的差異性不能區分，也很難適用于大規模復雜網絡。文獻[16]以脆弱性傳播為基礎，運用Markov博弈來分析脆弱性的定量關系及網絡各方行為選擇對網絡安全的動態影響，意圖找到威脅最大的節點或者路徑來提高安全性，但也同樣存在狀態空間過大和評估效率低的問題。文獻[17]在對已有網絡攻防安全評估模型進行有效總結的基礎上，提出了基于隨機Petri網的攻防博弈策略模型，所得安全評價具有一定的實用性，但只能對某一時刻的攻防狀態進行分析。朱建明等人[18]對非合作演化博弈攻防過程中的納什均衡點的存在性和唯一性進行了論證，但模型的結果更關注于現象的客觀解釋而非安全評價策略的得出。綜上所述，目前針對攻防博弈的研究多停留在技術改進階段，即在某一形式化模型的基礎上應用博弈分析，缺乏宏觀的深入探討，這使得研究工作局限于傳統博弈研究框架，只能針對某一時刻的靜態網絡進行對抗策略研究。然而網絡攻防過程定然是多狀態轉移的過程（如圖1所示，在初始時刻攻擊者Eve具有對節點A、H的訪問權限，管理員Admin針對D進行了防御，系統轉換到狀態S1；在狀態S1，Admin增加了對節點G的防御，但防御失敗，攻擊者權限擴大，演化到狀態S2；經過有限步的博弈之后系統到達狀態Sn），這需要在準確刻畫狀態轉移的基礎上建立新的模型。

在計算機網絡攻防對抗過程中，存在著多個系統狀態上的對抗，而且每個狀態的收益矩陣各不相同，攻擊或防御策略選取的隨機性會導致網絡系統狀態變化的隨機性。本文使用Markov決策過程對這一隨機性進行刻畫，形成了多狀態多智能體的Markov演化博弈安全分析模型；在形式化建模的基礎上，證明了均衡策略的存在；通過非線性規劃的求解方法得到了攻防策略方案。最后對一個典型的企業網絡攻防過程使用本文模型進行了仿真分析和推演，結果表明本文模型符合實際應用，評估結果準確，有助于攻防博弈研究的發展。

本文的主要貢獻有：

（1）將攻擊圖中的描述節點細化到了部件級，使模型的描述能力更加精確。同時突破了傳統攻擊圖進行靜態分析評價的限制，將部件攻擊圖與Markov博弈結合，形成了多狀態多智能體的Markov演化博弈安全分析模型。該模型能夠對攻防雙方的心智模式、過程中的非合作性和隨機性等動態演化機制進行很好刻畫。

（2）針對單步攻擊/檢測概率給出了可操作的計算方法，依托攻防收益函數和折扣期望準則函數給出了Markov演化博弈安全分析模型的目標函數，在均衡策略定義的基礎上，證明了該模型一定存在混合策略下的納什均衡。

Fig.1　Example of Markov game progress in network attack and defense圖1　網絡攻防中的Markov博弈過程示意圖

（3）為簡化模型的求解方法，給出了模型非線性規劃求解方法的證明過程；通過實例和仿真，給出了模型應用的詳細示例，并得到了攻防雙方的均衡策略，結果分析表明了模型的有效性。

2　形式化建模

使用圖的形式來刻畫網絡拓撲結構是復雜網絡分析的重要方法。攻擊圖模型可以很好地展示攻擊者利用目標網絡中多個脆弱點，從初始狀態向攻擊目標狀態的進發過程。本文在攻擊圖定義的基礎上給出Markov演化博弈分析模型的形式化表述方法。

定義1攻擊圖為一個五元組G=(V,C,Cp,Cl,Aα)，其中V是網絡系統中獨立的主機實體節點的集合；C= (v,s)表示計算機設備或主機節點v上提供的一個部件主體s（代表這個主機節點所提供的用戶、應用程序或服務等）；Cp=(Cxi,Cyj,p)表示節點x的部件主體i在節點y的部件主體 j上擁有權限p，p∈{None,Access,User, Superuser,Root}且滿足None

定義2 Markov演化博弈安全分析模型是一個六元組MGM={N,S,θ,P,R,U}，其中：

（1）N={1,2,…,n}是局中人的集合，本文考慮只有一個攻擊者和防御者的參與情況，即|N|=2，如果攻擊者或者防御者多于一個則進行合并處理。

（2）S={S1,S2,…,Sk}是攻防過程中的博弈狀態集合，這里的每一個狀態為定義1所定義的在某一個時間片上的攻擊圖，狀態之間的轉化是不同部件之間訪問權限或連接關系的變化。

（3）θ={θA,θD}是攻防雙方的行動策略集合。|θA|=m表示攻擊者的攻擊策略集合，表示在狀態Sk時攻擊者采用第i種攻擊策略，且滿足|θD|=n表示防御者的防御策略集合，表示在狀態Sk時防御者采用第j種防御策略，且滿足

（4）本文將轉移概率P分為3種：P(ai|Sk)（在狀態Sk下攻擊事件ai的發生概率），P(Sk|ai)（攻擊動作ai攻擊成功并轉移到狀態Sk的概率），P(ai|oi)（防御者監測事件oi能證明攻擊ai發生的防御概率），即。各種概率的取值參照文獻[19]中表1至表3的經驗取值法，為了突出攻擊事件的影響，概率之間采用“或”操作進行計算。

（5）Rn=Si×θ×Sj∈(-∞,+∞)表示局中人n從狀態Si轉移到狀態Sj時的收益函數。收益函數是攻防雙方各階段博弈的收益值，針對攻擊者和防御者收益函數的計算公式可參照文獻[15]中3.3節的量化方法進行。

按照上述定義，經過有限步（k步）的博弈過程后，系統在不同狀態之間進行轉化會形成一個樹形結構，攻防雙方的目標都是使各自的目標函數最大化，下文將會給出本文模型均衡策略存在性的證明和求解方法。

3　模型均衡策略求解

3.1均衡策略定義

在攻防雙方博弈過程中，假設每一個局中人都會盡可能最大化自己的目標函數，對于Markov演化博弈分析模型MGM={N,S,θ,P,R,U}，當網絡處于狀態Sk時，攻防雙方的策略分別為，則均衡策略的定義和充要條件均可由一般矩陣對策得出。若為均衡策略，則對于任意的滿足[20]：

從整個博弈過程來看，模型MGM的均衡策略是指每一個子博弈都達到納什均衡的Markov策略組合。這是因為轉化過程中狀態自然包含了子博弈的影響，若對手選擇Markov策略，則參與人定然會有一個Markov最優響應策略[21]。因此，若為本文所定義的Markov演化博弈分析模型某局中人n的均衡策略，則對于任意時刻t都滿足：

定理1對于給定的Markov演化博弈分析模型MGM={N,S,θ,P,R,U}，若||S<∞，||θ<∞，那么該MGM模型一定存在混合策略下的納什均衡。

證明 根據Markov演化博弈分析模型的定義，假設S0為系統博弈的初始狀態，θ0×θ1×…×θk為局中人n的策略集合，依據轉移概率P和收益函數R可知，存在與MGM相對應的隨機博弈，且收益函數為凹函數。根據文獻[20-22]中隨機博弈均衡策略存在性的證明可知，該隨機博弈存在混合策略下的納什均衡，通過該納什均衡即可得到MGM模型對應混合策略下的納什均衡。

3.2均衡策略求解方法

若攻防雙方能夠按照均衡策略的要求來選擇自己的行為，則可以通過文獻[23]中的方法預測攻擊者和防御者的概率向量，通過Shapley算法[24]來求解均衡策略。但是該過程較為困難，本文將MGM模型轉化為一個非線性規劃問題進行求解。

定理2對于給定的Markov演化博弈分析模型MGM={N,S,θ,P,R,U}及其確定馬氏策略 f*和穩定收益值U*，f*和U*為均衡策略的充要條件為：f*和U*是下述非線性規劃np的最優值。

證明（1）必要性證明。非線性規劃np中最后兩個條件是對自變量的描述，因此只需對前3個條件及最優值進行證明。假設在折扣率λ下，存在確定馬氏策略 f*和穩定收益值U*，由于馬氏策略 f*的穩定性，則非線性規劃np第2、3個約束條件自然成立。

因為均衡狀態下，每一個局中人n∈N都遵從折扣率為λ的Markov決策過程，所以?n∈N，如果所有其他的局中人n′的策略 f′固定，則局中人n的決策為Markov決策過程中的最大值策略[20]，即：

同時 f是單個局中人的最優穩定策略，則：

根據式（1）和式（2）可以得出非線性規劃np的目標函數值為0，因此(f*,U*)為非線性規劃的最優值。

（2）充分性證明。假設(f*,U*)為非線性規劃的最優值，根據上述推導過程可知非線性規劃np的目標函數值為0，在約束條件下，對每一個局中人n來說其均衡策略 fn和U*一定滿足式（1）和式（2）的要求，因此?n∈N，當其他局中人的策略固定時，策略 fn必然為符合Markov過程的最優策略，可得證 f*為Markov演化博弈分析模型的均衡策略。

4　應用實例與分析

4.1應用及驗證

本文模擬了一個典型的Web服務應用系統，在此實驗環境下來驗證本文模型及算法的準確性。實驗網絡系統的拓撲環境如圖2所示，通過防火墻將網絡分為攻擊者Eve所在的外網區、DMZ隔離區和內網安全區3部分。在DMZ區域中Web Server為Apache服務器；內網中SQL Server為Apache服務器提供數據庫服務，由于工作的需要SQL Server同時提供了RPC Service供外網區域訪問，內網中的兩臺工作機中H1和H2可以運行Email、Ftp和SSH程序。

Fig.2　Topological graph of experimental network圖2　實驗網路系統拓撲圖

根據預先設計的隔離原則，外網區域的用戶可以訪問Apache服務器上的任何服務以及SQL Server上的RPC服務，Apache服務器可以訪問SQLServer或者任何工作機，SQL Server可以訪問任何工作機，工作機H1可以訪問Apache服務器，H2可以訪問SQL Server并且工作機之間可以互相訪問。通過Nessus脆弱點掃描器得出的各個區域的脆弱點信息如表1所示。

本文的攻擊圖細化到部件級，在此忽略部件節點之間連接關系的變化，重點考慮不同部件之間的權限訪問關系。在初始狀態下（正常狀態S1），實驗網絡的初始訪問權限關系如圖3（a）所示。在此實驗中，狀態集合為S={S1（正常狀態），S2（攻擊Apache的Root權限），S3（攻擊Apache的User權限），S4（攻擊Apache的Access權限），S5（攻擊SQL Server的File的User權限），S6（攻擊SQL Server的User權限），S7（攻擊工作主機的Ftp），S8（攻擊工作主機的Outlook)，S9（攻擊工作主機的Root權限）}，狀態之間的轉移變化如圖3 （b）所示（狀態轉移之間黑色的圓點表示攻擊過程，三角形符號表示防御過程）。本文使用文獻[19]中專家經驗取值法來確定狀態之間的轉移概率，結果如表2所示（其中表示在狀態i下，攻擊者采用攻擊策略m，防御者使用防御策略n到達狀態j的概率）。

Table 1　Vulnerability information in experimental network表1　實驗網絡脆弱點信息

Fig.3　State transfer graph of access privilege in experimental network圖3　實驗網絡訪問權限狀態轉移圖

Table 2　State transfer probability of experimental network表2　實驗網絡狀態轉移概率

Table 3　Attack and defense strategy for each state in experimental network表3　實驗網絡各狀態攻防策略

Table 4　Gain matrix for attacker in experimental network表4　實驗網絡攻擊者收益矩陣

實驗網絡各個狀態下攻防策略集如表3所示，本文參照文獻[15]中的做法，將系統損失作為攻擊者收益，結合網絡攻防的相關量化思想[8,18]，可以得到實驗網絡在各個狀態下攻防雙方的收益矩陣，如表4所示。

根據3.2節中Markov演化博弈安全分析模型的求解方法，可以轉化成如圖4所示的非線性規劃模型(λ=0.7)，針對該非線性規劃模型np，使用Matlab等求解工具可以獲得各個狀態下的均衡策略，如表5所示。

4.2結果分析

（1）攻擊路徑分析。假設攻擊目標是位于主機節點H2上的文件數據，只要攻擊者獲取了目標文件的Access權限即認為達到攻擊的最終狀態。由上節的分析可知共有兩條攻擊路徑：

Table 5　Result of evolutionary game for experimental network表5　實驗網絡演化博弈結果

① S1,{S2,S3},{S5,S6,S7,S8},即攻擊者通過Apache的漏洞發起攻擊，進而獲取SQL Server的User權限，最后通過主機節點的漏洞達到攻擊目的。在每一種狀態下攻擊者和防御者都有不同的動作可以選擇，例如：在狀態S時攻擊者有=溢出攻擊，=函數

Fig.4　Nonlinear programming transformation results for experimental network model圖4　實驗網絡模型非線性規劃轉化結果

2溢出=不攻擊}3種攻擊策略，防御者也有=補丁升級=關閉服務，=不響應}3種防御策略。根據表2中的取值可知，在狀態S2下攻擊者采用第1種攻擊策略，防御者采用第1種防御策略，攻擊成功到達狀態S5的概率為0.6（即：P(2,1,1,5)=0.6），此條攻擊路徑也可描述為

②S1,S4,S9即攻擊者通過針對Apache的異常攻擊，獲取部件的User權限，通過主機節點FTP漏洞獲取文件的Access權限，同樣此條路徑也可以描述為

（2）攻防策略選擇分析。針對上述攻擊路徑①，根據表5中的博弈分析結果，在狀態S1時攻擊者選擇的攻擊=特權攻擊和=注入攻擊都很大（3種攻擊方式的概率分別為P()=0），防御者一定會采用=補丁升級的方式進行防御（P()=1），但是防御收益卻很低（R= 62.1）。在攻擊路徑的第二步中，針對SQL Server的攻擊方法較為普遍，選擇各種攻擊方法的可能性相差不大。例如在狀態S2下，各種攻擊選擇的可能性分別為P()=0.28，P)=0.33，P()=0.39，但是防御者的收益卻很大，在狀態S2和狀態S3下的防御收益分別為539.2和381.4。在攻擊路徑②中，通過狀態S1的博弈分析結果可知，攻擊者選擇針對Apache異常攻擊的概率為0，因此這條路徑不必過分關注；最后針對主機節點的攻擊各種方法的收益和選擇概率都相差不大，因此可得出防御者的防御重點應該是針對內網中數據庫服務器進行補丁升級，而不是直觀上的對Apache服務器進行防御。

5　總結與展望

在網絡安全分析中應用博弈論等技術是網絡安全領域的主要發展方向之一，但是以往的分析模型大都在某個時間片的靜態模型下研究單狀態的對抗問題。本文提出的基于Markov過程的演化博弈分析模型，充分考慮了網絡對抗中的非合作性、策略依存性等特征，使用Markov過程對網絡攻擊或防御策略選取的隨機性進行描述，將傳統的單矩陣博弈模型擴展為多狀態多智能體的Markov演化博弈模型，給出了模型嚴謹的定義，在平衡策略存在性證明的基礎上，給出了模型的非線性規劃求解方案。最后對一個典型的企業網絡攻防過程使用本模型進行了仿真分析和推演，結果表明該模型的方法符合實際應用，評估結果準確。

復雜動態網絡的相關理論成功應用到網絡攻擊圖分析模型中是作者一直努力的方向之一，進一步的研究包括：根據博弈結果得出有效的防御方案；構建適合大規模網絡風險評估分析的數據集；繼續驗證本文所提模型的合理性和有效性。

References:

[1]Anderson J P.Computer security threat monitoring and surveillance,Contract 79F26400[R].Fort Washington,USA: James PAnderson Company,1980.

[2]Li Zhoujun,Zhang Junxian,Liao Xiangke,et al.survey of software vulnerability detection techniques[J].Chinese Journal of Computers,2015,38(4):717-731.

今年3月，全國政協委員、中華全國供銷合作總社黨組成員、理事會副主任楊建平首次將中國鉀鹽產業發展提升到“兩會”高度，引起行業關注。他建議，統籌利用國內國外兩種資源，解決我國“缺鉀”問題。他提出，應當加強國內鉀鹽資源保護性開發，加大對“境外找鉀”的戰略統籌和引導扶持，提升我國在國際鉀肥供應中的話語權，保障我國鉀肥長期穩定供應和農業戰略安全。他建議，依托“一帶一路”國際合作，統籌規劃、有序引導中國企業“走出去”實施境外鉀鹽開發。

[3]Xing Xujia,Lin Chuang.A survey of computer vulnerability assessment[J].Chinese Journal of Computers,2004,27(1): 1-11.

[4]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.

[5]Ye Yun,Xu Xishan,Qi Zhichang,et al.Attack graph generation algorithm for large-scale network system[J].Journal of Computer Research and Development,2013,50(10):2133-2139.

[6]Gao Xiang,Zhu Yuefei,Liu Shengli.Attack composition model based on generalized stochastic colored Petri nets[J].Journal of Electronics&Information Technology,2013,35(11): 2608-2614.

[7]Su Tingting,Pan Xiaozhong,Xiao Haiyan,et al.Research on attack graph based on attributes adjacncy matrix[J].Journal of Electronics&Information Technology,2012,34(7): 1744-1747.

[8]Feng Xuewei,Wang Dongxia,Huang Minheng,et al.A mining approach for causal Knowledge in alert correlating based on the markov property[J].Journal of Computers Research and Development,2014,51(11):2493-2504.

[9]Wang Huimei,Xian Ming,Wang Guoyu.A network attack decision-making algorithm based on the extended attack graph[J].Journal of Electronics&Information Technology, 2011,33(12):3015-3021.

[10]Bass T,Gruber D.A glimpse into the future of ID[EB/OL]. [2015-06-20].http://www.usenix.org/publications/login/1999-9/ features/future.html.

[12]Zhu Jianming,Song Biao,Huang Qifa.Evolution game model of offense-defense for network security based on system dynamics[J].Journal on Communications,2014,35(1):54-61.

[13]Hamilton S N,Miller W L,Ott A,et al.The role of game theory in information warfare[C]//Proceedings of the 4th InformationSurvivabilityWorkshop,Vancouver,Canada,2002: 45-46.

[14]Reddy Y B.A game theory approach to detect malicious nodes in wireless sensor networks[C]//Proceedings of the 3rd International Conference on Sensor Technologies and Application,Athens,Greece,Jun 18-23,2009.Washington, USA:IEEE Computer Society,2009:462-468.

[15]Jiang Wei,Fang Binxing,Zhang Hongli,et al.Evaluating network security and optimal active defense based on attackdefense game model[J].Chinese Journal of Computers, 2009,32(4):817-827.

[16]Zhang Yong,Tan Xiaobin,Cui Xiaolin,et al.Network security situation awareness approach based on Markov game model[J].Journal of Software,2011,22(3):495-508.

[17]Wang Yuanzhuo,Lin Chuang,Cheng Xueqi,et al.Analysis for network attack-defense based on stochastic game model [J].Chinese Journal of Computers,2010,33(9):1748-1762.

[18]Zhu Jianming,Raghunathan S.Evaluation model of information security technologies based on game theoretic[J].Chinese Journal of Computers,2009,32(4):828-834.

[19]Chen Xiaojun,Fang Binxing,Tan Qingfeng,et al.Inferring attack intent of malicious insider based on probabilistic attack graph model[J].Chinese Journal of Computers,2014, 37(1):62-72.

[20]Operations research teaching material drawing board.Operationsresearch[M].Beijing:TsinghuaUniversityPress,2012: 383-394.

[21]Borkovsky R N,Doraszelski U,Kryukov Y.A user’s guide to solving dynamic stochastic games using the homotopy method[J].Operation Research,2010,58(4):1116-1132.

[22]Nilim A,Ghaoui L E.Robust control of Markov decision processes with uncertain transition matrices[J].Operations Research,2005,53(5):780-798.

[23]Sallhammar K,Helvik B E,Knapskog S J.On stochastic modeling for integrated security and dependability evaluation[J].The Journal of Networks,2006,1(5):31-42.

[24]Shapley L S.Stochastic games[J].Proceedings of the National Academy of Science USA,1953,39(10):1095-1100.

附中文參考文獻：

[2]李舟軍,張俊賢,廖湘科,等.軟件安全漏洞檢測技術[J].計算機學報,2015,38(4):717-731.

[3]邢栩嘉,林闖.計算機系統脆弱點評估研究[J].計算機學報,2004,27(1):1-11.

[4]劉玉嶺,馮登國,連一峰,等.基于時空維度分析的網絡安全態勢預測方法[J].計算機研究與發展,2014,51(8):1681-1694.

[5]葉云,徐錫山,齊治昌,等.大規模網絡中攻擊圖自動構建算法研究[J].計算機研究與發展,2013,50(10):2133-2139.

[6]高翔,祝躍飛,劉勝利.一種基于廣義隨機著色Petri網的網絡攻擊組合模型[J].電子與信息學報,2013,35(11): 2608-2614.

[7]蘇婷婷,潘曉中,肖海燕,等.基于屬性鄰接矩陣的攻擊圖表示方法研究[J].電子與信息學報,2012,34(7):1744-1747.

[8]馮學偉,王東霞,黃敏恒,等.一種基于馬爾可夫性質的因果知識挖掘方法[J].計算機研究與發展,2014,51(11): 2493-2504.

[9]王會梅,鮮明,王國玉.基于擴展網絡攻擊圖的網絡攻擊策略生成算法[J].電子與信息學報,2011,33(12):3015-3021.

[11]陳小軍,時金橋,徐菲,等.面向內部威脅的最優安全策略算法研究[J].計算機研究與發展,2014,51(7):1565-1577.

[12]朱建明,宋彪,黃啟發.基于系統動力學的網絡安全攻防演化博弈模型[J].通信學報,2014,35(1):54-61.

[15]姜偉,方濱興,田志宏,等.基于攻防博弈模型的網絡安全測評和最優主動防御[J].計算機學報,2009,32(4):817-827.

[16]張勇,譚小彬,崔孝林,等.基于Markov博弈模型的網絡安全態勢感知方法[J].軟件學報,2011,22(3):495-508.

[17]王元卓,林闖,程學旗,等.基于隨機博弈模型的網絡攻防量化分析方法[J].計算機學報,2010,33(9):1748-1762.

[18]朱建明,Raghunathan S.基于博弈論的信息安全技術評價模型[J].計算機學報,2009,32(4):828-834.

[19]陳小軍,方濱興,譚慶豐,等.基于概率攻擊圖的內部攻擊意圖推斷算法研究[J].計算機學報,2014,37(1):62-72.

[20]《運籌學》教材編寫組.運籌學[M].北京:清華大學出版社,2012:383-394.

LI Yan was born in 1984.He is a Ph.D.candidate at School of Management,Xi’an University of Architecture and Technology,and the member of CCF.His research interests include network security,system engineering and information countermeasure,etc.

李艷（1984—），男，河北承德人，蒙古族，西安建筑科技大學管理學院博士研究生，CCF會員，主要研究領域為網絡安全，系統工程，信息對抗等。

HUANG Guangqiu was born in 1964.He received the Ph.D.degree in complex system modeling from Xi’an University of Architecture and Technology in 1995.Now he is a professor and Ph.D.supervisor at Xi’an University of Architecture and Technology.His research interests include network security,complex system modeling and system engineering,etc.

黃光球（1964—），男，湖南桃源人，1995年于西安建筑科技大學獲得博士學位，現為西安建筑科技大學教授、博士生導師，主要研究領域為網絡安全，復雜系統建模，系統工程等。

ZHANG Bin was born in 1984.He is a Ph.D.candidate at Xi’an University of Architecture and Technology.His research interests include network security and system engineering,etc.

張斌（1984—），男，陜西渭南人，西安建筑科技大學博士研究生，主要研究領域為網絡安全，系統工程等。

Markov Evolutionary Game Model for Dynamic Network Attacks Safety Analysis*

LI Yan+,HUANG Guangqiu,ZHANG Bin
School of Management,Xi’an University of Architecture and Technology,Xi’an 710055,China
+Corresponding author:E-mail:sy_liyan137@126.com

LI Yan,HUANG Guangqiu,ZHANG Bin.Markov evolutionary game model for dynamic network attacks safety analysis.Journal of Frontiers of Computer Science and Technology,2016,10(9)：1272-1281.

The random selection of network attack or defense strategy will cause that the system state changes randomly, the process of network attack and defense is certainly a multi-state confrontation also,whose gain matrix is different. This paper provides a new Markov evolutionary game model with multi-state and multi-agent,which uses Markov decision processes to describe the randomness and extend the game model from single-state to multi-state.After the formalization,this paper proves the existence of equilibrium strategy and gets the defense strategy by solving a corresponding nonlinear programming model.Finally,this paper takes a typical enterprise network attack process for example,does simulation analysis and deduction,the results show that this model can match the actual application,the evaluation results are accurate,and helpful to the development of the offensive and defensive game.

offensive and defensive evolution;evolutionary game;Markov game;network attack model;network security

網絡攻擊或防御策略選取的隨機性會導致系統狀態變化的隨機性，網絡攻防的過程也定然是收益矩陣各不相同的多狀態上的對抗。使用Markov決策過程對這一隨機性進行刻畫，將單狀態的博弈模型擴展到多狀態，形成了多狀態多智能體的Markov演化博弈模型；在形式化建模的基礎上，證明了均衡策略的存在；通過非線性規劃的求解方法得到了攻防策略方案。最后以一個典型的企業網絡攻防過程為例，使用該模型進行了仿真分析和推演，結果表明該模型符合實際應用，評估結果準確，有助于攻防博弈研究的發展。

2015-08,Accepted 2015-12.

*The Science and Technology Research and Development Plan of Shaanxi Province under Grant No.2013K1117(陜西省科學技術研究發展計劃項目);the Special Funds Project for the Construction of Key Disciplines of Shaanxi Province under Grant No.E08001(陜西省重點學科建設專項資金項目);the Science and Technology Project of Shaanxi Provincial Education Department under Grant No.12JK0789(陜西省教育廳科技計劃項目).

CNKI網絡優先出版:2015-12-09,http://www.cnki.net/kcms/detail/11.5602.TP.20151209.1024.002.html

A

TP393.08；TP309.5