張恒巍，余定坤，寇　廣，韓繼紅

（解放軍信息工程大學(xué)，鄭州　450001）

基于狀態(tài)約減的信息攻防圖生成算法*

張恒巍，余定坤，寇廣，韓繼紅

（解放軍信息工程大學(xué)，鄭州450001）

針對(duì)攻防圖構(gòu)建中存在的狀態(tài)爆炸問題，提出一種基于狀態(tài)約減的攻防圖生成算法。該算法在分析攻擊者和目標(biāo)網(wǎng)絡(luò)特點(diǎn)的基礎(chǔ)上，對(duì)獨(dú)立狀態(tài)節(jié)點(diǎn)的權(quán)限進(jìn)行對(duì)比；其在保留最高權(quán)限節(jié)點(diǎn)的前提下，實(shí)現(xiàn)對(duì)低權(quán)限節(jié)點(diǎn)的約減，并去除冗余攻擊路徑。仿真實(shí)驗(yàn)表明算法具有計(jì)算復(fù)雜度低、能有效降低狀態(tài)爆炸以及控制攻防圖規(guī)模等優(yōu)點(diǎn)。

攻防圖，狀態(tài)爆炸，節(jié)點(diǎn)權(quán)限，狀態(tài)約減

0　引言

攻擊圖是一種攻擊行為建模方法，其從攻擊者的角度出發(fā)，在分析網(wǎng)絡(luò)結(jié)構(gòu)和系統(tǒng)漏洞的基礎(chǔ)上，生成攻擊路徑，展現(xiàn)針對(duì)特定系統(tǒng)的攻擊預(yù)案集合，能夠幫助安全管理人員開展安全風(fēng)險(xiǎn)評(píng)估和防御策略選擇［1-3］。但是，攻擊圖所關(guān)注的僅是攻擊者的行為，并沒有考慮防御者可能采取的手段，而信息攻防是攻擊者和防御者互相對(duì)抗博弈的過程，安全狀態(tài)及下一步的變化情況是由攻擊與防御行為共同決定的，信息安全受雙方的對(duì)抗行為以及行為所造成結(jié)果的影響［4-5］。因此，不能僅從攻擊者角度出發(fā)，而應(yīng)將防御行為也考慮進(jìn)來，從攻防雙方的角度出發(fā)，建立攻防行為模型，更加全面、準(zhǔn)確地反映信息系統(tǒng)安全的實(shí)際情況。

有學(xué)者在攻擊圖的基礎(chǔ)上進(jìn)一步提出了攻防圖模型。文獻(xiàn)［5］提出了用于網(wǎng)絡(luò)安全測評(píng)的防御圖模型的概念和定義，但未進(jìn)一步給出防御圖建模、生成方法。文獻(xiàn)［6］提出了一種攻防圖模型及其生成算法，但其中攻擊路徑生成方式簡單，且未考慮狀態(tài)空間爆炸的問題。文獻(xiàn)［7］提出一種攻防圖的生成算法，并用于系統(tǒng)安全態(tài)勢分析，但對(duì)安全狀態(tài)及其轉(zhuǎn)化分析不足，存在較為嚴(yán)重的狀態(tài)空間爆炸問題。

本文針對(duì)傳統(tǒng)攻防圖構(gòu)建方法存在狀態(tài)爆炸的問題，對(duì)攻防圖建模過程進(jìn)行深入研究，提出一種基于狀態(tài)約減的信息攻防圖生成算法。在產(chǎn)生攻擊路徑時(shí)，對(duì)各主機(jī)的獨(dú)立狀態(tài)節(jié)點(diǎn)的權(quán)限進(jìn)行對(duì)比，僅保留最高權(quán)限的節(jié)點(diǎn)，約減其余權(quán)限較低的節(jié)點(diǎn)，并減少重復(fù)節(jié)點(diǎn)，去除冗余攻擊路徑，該方法不但能夠控制狀態(tài)空間組合爆炸，而且可以實(shí)現(xiàn)對(duì)目標(biāo)網(wǎng)絡(luò)中主機(jī)的覆蓋。在此基礎(chǔ)上，提出一種較低復(fù)雜度的攻防圖生成算法，仿真實(shí)驗(yàn)和結(jié)果分析驗(yàn)證了算法的有效性。

1　基于狀態(tài)約減的攻防行為建模

1.1基本假設(shè)

在借鑒文獻(xiàn)［7-8］的基礎(chǔ)上，提出如下假設(shè)作為研究的基礎(chǔ)。

假設(shè)1攻擊者是智能且貪婪的，在了解網(wǎng)絡(luò)中的漏洞信息后，知道如何利用漏洞進(jìn)行攻擊，且不會(huì)進(jìn)行無效攻擊。

假設(shè)2攻擊者在一個(gè)節(jié)點(diǎn)獲得權(quán)限提升后，可利用此節(jié)點(diǎn)發(fā)動(dòng)針對(duì)不同節(jié)點(diǎn)的攻擊。

假設(shè)3（單調(diào)性假設(shè)［7］）攻擊者不會(huì)為了獲取已有的權(quán)限而發(fā)動(dòng)攻擊，且攻擊方向只會(huì)向著提升操作權(quán)限的方向發(fā)展。

1.2攻防圖模型

攻防圖主要描述了攻擊者利用網(wǎng)絡(luò)漏洞進(jìn)行多步攻擊，以及防御者采取防御策略進(jìn)行對(duì)抗的過程［9-10］。下面給出攻防圖的形式化描述。

定義1攻防圖ADG（Attack-Defense Graph，簡稱ADG）。定義五元組ADG=（P，B，P0，PG，Sd）為信息攻防圖，簡稱攻防圖。其中，P為攻防圖中表示網(wǎng)絡(luò)安全狀態(tài)的各個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的集合；B為攻防圖的各條邊的集合，攻擊者通過邊（即攻擊行為，或稱攻擊策略）來實(shí)現(xiàn)網(wǎng)絡(luò)安全狀態(tài)的變遷；P0則表示整個(gè)網(wǎng)絡(luò)信息系統(tǒng)的一個(gè)初始狀態(tài)；PG則表示攻擊者在攻擊前所確定的目標(biāo)狀態(tài)集合；Sd是防御者為抵抗攻擊而采取的防御策略的集合。

與攻擊圖類似的是，攻防圖中的節(jié)點(diǎn)代表安全狀態(tài)，表示其自身所擁有的權(quán)限及對(duì)其他節(jié)點(diǎn)的訪問能力；邊代表攻擊者的攻擊行為，通過該行為攻擊者實(shí)現(xiàn)安全狀態(tài)的遷移，從而獲得對(duì)不同主機(jī)的權(quán)限，最終達(dá)到目標(biāo)狀態(tài)。與攻擊圖不同的是，攻防圖為了全面地反映信息攻防的整體情況，不僅需要對(duì)攻擊者的行為有所把握，還要對(duì)防御者的行為進(jìn)行考慮和分析。防御者可以針對(duì)攻擊行為采取相應(yīng)的防御行為（或稱防御策略），防御策略組成集合Sd。

1.3攻防行為建模

攻防行為建模應(yīng)避免出現(xiàn)狀態(tài)爆炸，無法適應(yīng)大規(guī)模網(wǎng)絡(luò)的情況，能夠高效、靈活、全面地對(duì)攻防狀態(tài)進(jìn)行分析和研究。本文從對(duì)安全狀態(tài)約簡的角度出發(fā)，提出一種建模方法。

為描述目標(biāo)網(wǎng)絡(luò)，定義Host元組和Connection元組，分別代表網(wǎng)絡(luò)中的主機(jī)以及網(wǎng)絡(luò)連接關(guān)系。

定義2Host（ID，Serf，Vulf）。Host表示網(wǎng)絡(luò)中的一臺(tái)主機(jī)，為了對(duì)網(wǎng)絡(luò)中運(yùn)行的一臺(tái)主機(jī)進(jìn)行描述，使用3個(gè)元素，分別是主機(jī)ID，用于賦予主機(jī)網(wǎng)絡(luò)中唯一的標(biāo)識(shí)；主機(jī)的運(yùn)行服務(wù)列表Serf，用于記錄所運(yùn)行的服務(wù)；脆弱性列表Vulf，用于記錄主機(jī)存在的脆弱性；由此，可以將網(wǎng)絡(luò)中的主機(jī)表達(dá)為Host（ID，Serf，Vulf）。

定義3Connection（SH，TH，CP）。Connection表示網(wǎng)絡(luò)中的主機(jī)連接關(guān)系。主機(jī)之間相互連接，其中一方為發(fā)起者，一方為接受者。發(fā)起者為源主機(jī)，接受者為目的主機(jī)，它們之間通過端口互相通信。因此，網(wǎng)絡(luò)中主機(jī)的連接關(guān)系可用3個(gè)元素進(jìn)行描述，分別是源主機(jī)SH（Source Host）、目的主機(jī)TH（TargetHost）和連接端口CP（Connected Port）。由此，可以將主機(jī)連接關(guān)系表達(dá)為Connection（SH，TH，CP）。

傳統(tǒng)攻防圖生成過程中產(chǎn)生的狀態(tài)數(shù)量巨大，呈指數(shù)增長，使得攻防圖的產(chǎn)生花費(fèi)時(shí)間多，效率低下。為了減少攻防圖生成的復(fù)雜度，降低攻防圖的規(guī)模，本文提出一種狀態(tài)約簡方法。由于網(wǎng)絡(luò)中的攻防是攻擊者借助脆弱性實(shí)施攻擊，防御者選取防御策略進(jìn)行抵抗的過程。因此，要對(duì)安全狀態(tài)進(jìn)行約簡，需要對(duì)攻擊行為及其造成的安全狀態(tài)遷移進(jìn)行描述。

安全狀態(tài)是指攻擊者通過獲得主機(jī)的權(quán)限從而使主機(jī)達(dá)到的一種狀態(tài)。攻擊者進(jìn)行攻擊是否成功，主要體現(xiàn)在攻擊者的權(quán)限變遷情況。因此，在攻防圖中，安全狀態(tài)可以通過攻擊者在主機(jī)上所擁有的權(quán)限進(jìn)行表述。本文定義主機(jī)權(quán)限為4種，即禁止訪問、遠(yuǎn)程訪問權(quán)限、普通用戶權(quán)限、管理員權(quán)限，4種權(quán)限依次遞增。

基于上述分析，針對(duì)攻擊模板，本文從攻擊者所在主機(jī)、攻擊者在主機(jī)上擁有的權(quán)限、攻擊者所在主機(jī)與其余主機(jī)的聯(lián)系、攻擊目標(biāo)主機(jī)或目標(biāo)網(wǎng)絡(luò)、最大攻擊步數(shù)等角度進(jìn)行描述。對(duì)攻擊所在主機(jī)采用該主機(jī)的ID進(jìn)行標(biāo)識(shí)；攻擊者在主機(jī)上擁有的權(quán)限可使用權(quán)限列表HA-List（Host Authority List）表示；攻擊者所在主機(jī)與網(wǎng)絡(luò)中其余主機(jī)的聯(lián)系通過Connection-List列表進(jìn)行記錄；攻擊目標(biāo)主機(jī)或目標(biāo)網(wǎng)絡(luò)是攻擊者的最終目標(biāo)，使用Target對(duì)最終目標(biāo)主機(jī)進(jìn)行標(biāo)識(shí)；最大攻擊步數(shù)采用MX （max-steps）來表示。由上，可得攻擊模板的形式化表示為：Attack-Template=（ID，Authority-List，Connection-List，Target，MX）。參數(shù)具體定義見文獻(xiàn)［11］。

由于攻擊者可以利用同一主機(jī)的不同漏洞，借助網(wǎng)絡(luò)連接關(guān)系，通過不同的攻擊行為對(duì)另一主機(jī)進(jìn)行滲透和攻擊。此時(shí)，攻擊者在另一主機(jī)上便可能獲得多種安全狀態(tài)，所獲得的權(quán)限也可能有高有低。若這些漏洞并不存在依賴關(guān)系，則只需要保留攻擊者在另一主機(jī)的較高權(quán)限的安全狀態(tài)，這樣可有效降低安全狀態(tài)的總數(shù)量。以上過程，稱之為安全狀態(tài)約簡（State Reduction）。狀態(tài)約簡原理如圖1所示。

圖1　狀態(tài)約簡原理

Pi-1和Pj-1是主機(jī)n的安全狀態(tài)，Pi和Pj是主機(jī)m的安全狀態(tài)，而ai和aj則是攻擊者的不同攻擊行為。若攻擊行為ai所對(duì)應(yīng)的漏洞與攻擊行為aj不存在依賴關(guān)系，且Pi狀態(tài)下攻擊者的權(quán)限高于在狀態(tài)Pj下攻擊者的權(quán)限，則可以按照?qǐng)D中所示，將攻擊行為aj和安全狀態(tài)Pj刪去，僅留下ai和Pi。而若攻擊行為ai所對(duì)應(yīng)的漏洞與攻擊行為aj存在依賴關(guān)系，則攻擊者必須先對(duì)主機(jī)m進(jìn)行攻擊行為aj來達(dá)到安全狀態(tài)Pj，再采取攻擊ai才能到達(dá)狀態(tài)Pi，此時(shí)不能進(jìn)行狀態(tài)約簡。

由于攻防圖建模不僅要考慮攻擊者的攻擊行為，還需要對(duì)防御者的策略進(jìn)行分析考慮。因此，引入攻防模板對(duì)攻擊者、防御者的行為規(guī)則進(jìn)行描述。一個(gè)攻防模板應(yīng)由攻擊者行為、攻擊者在源主機(jī)和目標(biāo)主機(jī)上的權(quán)限、攻擊利用的漏洞、攻擊后攻擊者在目標(biāo)主機(jī)上的權(quán)限、防御策略、攻防收益組成。攻防模板可形式化表示為一個(gè)元組：Attack-Defense Template=（AM，SHA，THA，Vul，THA’，AR，DS，DR），其中AM（Attack Movement）為攻擊者的攻擊行為，SHA（Source Host Authority）為攻擊者在源主機(jī)上的權(quán)限，THA（TargetHostAuthority）為攻擊者在目標(biāo)主機(jī)上的權(quán)限，Vul為攻擊者所利用的網(wǎng)絡(luò)中的漏洞，THA’為攻擊者攻擊后在目標(biāo)主機(jī)上具有的權(quán)限，AR（Attack Reward）表示攻擊者通過攻擊所獲得的回報(bào)，DS（Defense Strategies）表示防御者為減少其損失所采取的防御策略，DR（Defense Reward）表示防御者通過采取防御策略所獲得的回報(bào)。參數(shù)具體定義見文獻(xiàn)［11-12］。

2　攻防圖構(gòu)建框架與生成算法

攻防圖的建模和生成首先需要對(duì)目標(biāo)網(wǎng)絡(luò)中的漏洞信息、拓?fù)浣Y(jié)構(gòu)信息、配置文件信息等進(jìn)行收集和掌握，并進(jìn)行分析和研究，之后將攻防模板、攻擊模板輸入攻防圖生成算法，通過網(wǎng)絡(luò)安全狀態(tài)約簡，生成優(yōu)化后的攻防圖，如圖2所示。

圖2　攻防圖構(gòu)建框架

攻防圖生成算法是構(gòu)建攻防圖的關(guān)鍵和核心，在基于狀態(tài)約減的攻防行為建模研究的基礎(chǔ)上，提出下面的攻防圖生成算法。

首先從攻擊者已獲得最高權(quán)限的主機(jī)出發(fā)，對(duì)目標(biāo)網(wǎng)絡(luò)進(jìn)行掃描，收集拓?fù)湫畔?、漏洞信息等。然后，攻擊者利用漏洞?duì)網(wǎng)絡(luò)中的主機(jī)進(jìn)行攻擊，以獲得更高的權(quán)限。此后，攻擊者又可基于已獲得一定權(quán)限的主機(jī)對(duì)網(wǎng)絡(luò)中與該主機(jī)相關(guān)聯(lián)的、具有漏洞的其他主機(jī)進(jìn)行攻擊。攻擊行為持續(xù)進(jìn)行，直到達(dá)到攻擊目標(biāo)。另一方面，防御者選取可用的防御策略實(shí)施抵抗，最終形成攻防圖。

依據(jù)以上思路，給出基于安全狀態(tài)約簡的攻防圖生成算法的具體描述。

基于狀態(tài)約簡的攻防圖生成算法

原始主機(jī)隊(duì)列和主機(jī)權(quán)限隊(duì)列

算法中攻擊路徑生成部分是算法的主體。其中，主機(jī)信息隊(duì)列用Host_queue表示；攻擊者在主機(jī)上具有的權(quán)限隊(duì)列由HA_queue表示；隨著攻防進(jìn)程的推進(jìn)，新產(chǎn)生的狀態(tài)節(jié)點(diǎn)隊(duì)列由P_queue表示；狀態(tài)節(jié)點(diǎn)間的相互關(guān)系用Connection_queue表示；攻擊過程由攻擊模板attack_template_queue描述；Initialize函數(shù)用于隊(duì)列生成和初始化，QueueEmpty函數(shù)用于判斷隊(duì)列是否為空，Dequeue函數(shù)用于從隊(duì)列中取出元素，Attack函數(shù)用于判定攻擊是否成功；State Reduction是狀態(tài)約簡函數(shù)，依據(jù)1.3節(jié)的方法實(shí)現(xiàn)對(duì)安全狀態(tài)的約簡，避免產(chǎn)生狀態(tài)爆炸現(xiàn)象。

分析算法可知，本文提出的攻防圖生成算法的空間復(fù)雜度為O（nml），時(shí)間復(fù)雜度為O（n2mt），其中n表示網(wǎng)絡(luò)中的主機(jī)數(shù)，m表示主機(jī)的漏洞數(shù)，l表示主機(jī)所擁有的權(quán)限狀態(tài)，t表示漏洞處理時(shí)間。算法的復(fù)雜度為多項(xiàng)式級(jí)別，時(shí)空開銷較低，滿足應(yīng)用需求。

3　仿真實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證本文提出方法的有效性，采用如圖3所示的網(wǎng)絡(luò)環(huán)境進(jìn)行仿真實(shí)驗(yàn)。其中，攻擊者位于主機(jī)0處發(fā)動(dòng)攻擊，并具有該主機(jī)的最高權(quán)限。目標(biāo)網(wǎng)絡(luò)由防火墻、入侵檢測系統(tǒng)、主機(jī)1和主機(jī)2組成。

圖3　網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

主機(jī)1和主機(jī)2分別為Web服務(wù)器、數(shù)據(jù)庫服務(wù)器，操作系統(tǒng)為Linux，具體參數(shù)如下頁表1所示。

假設(shè)攻擊者具有主機(jī)0的管理員權(quán)限，且具有主機(jī)1和主機(jī)2的遠(yuǎn)程訪問權(quán)限。由于防火墻的隔離防護(hù)作用，外部主機(jī)僅能使用主機(jī)1的ftp、Http服務(wù)和主機(jī)2的ftp服務(wù)。

表1　主機(jī)提供的服務(wù)及其漏洞

依據(jù)上述假設(shè)構(gòu)造攻防模板，假定攻擊目標(biāo)是獲得主機(jī)2的管理員權(quán)限，由此控制數(shù)據(jù)庫服務(wù)器。由于防火墻的存在，攻擊者無法直接使用主機(jī)2的數(shù)據(jù)庫服務(wù)，但是由于主機(jī)存在漏洞，且漏洞之間具有相互聯(lián)系，攻擊者可以利用漏洞及其關(guān)聯(lián)性進(jìn)行攻擊，實(shí)現(xiàn)目標(biāo)。假設(shè)攻擊策略如表2所示，包括攻擊行為的名稱、類別、攻擊致命度AL［12］。防御者可選的防御策略如表2所示。

表2　攻防策略描述

在對(duì)攻防行為建模后，利用文獻(xiàn)［7］的方法，未進(jìn)行狀態(tài)約簡直接生成攻防圖，結(jié)果如圖4所示，共有攻擊路徑13條，狀態(tài)結(jié)節(jié)31個(gè)。

圖4　未約簡的攻防圖

利用本文提出的基于安全狀態(tài)約簡的攻防圖生成算法，得到結(jié)果如下頁圖5所示?？梢钥闯?，在引入單調(diào)性假設(shè)并對(duì)狀態(tài)進(jìn)行約簡后，攻擊路徑為9條，狀態(tài)節(jié)點(diǎn)為23個(gè)。由此可見，對(duì)安全狀態(tài)進(jìn)行約簡可有效降低攻防圖規(guī)模和狀態(tài)爆炸程度，使攻防行為建模更加合理、高效、實(shí)用。

將本文方法和文獻(xiàn)［5-7］進(jìn)行對(duì)比，結(jié)果如表3所示。

表3　方法比較

圖5　約簡后的攻防圖

由表3可以看出，相比其他文獻(xiàn)，本文方法在攻防圖生成方面，具有狀態(tài)節(jié)點(diǎn)、攻擊路徑數(shù)量少，攻防圖規(guī)模較小，算法復(fù)雜度較低等優(yōu)點(diǎn)，在一定程度上減小了狀態(tài)爆炸，取得了較好效果。

4　結(jié)論

本文面向攻防圖自動(dòng)生成的需求，針對(duì)傳統(tǒng)攻防圖構(gòu)建方法存在狀態(tài)爆炸的問題，通過分析攻擊者和目標(biāo)網(wǎng)絡(luò)的特點(diǎn)以及傳統(tǒng)算法的不足，在設(shè)計(jì)合理假設(shè)的前提下，提出了基于狀態(tài)約減的攻防圖生成算法。通過對(duì)該算法的復(fù)雜度分析和仿真實(shí)驗(yàn)驗(yàn)證，表明算法具有計(jì)算復(fù)雜度低，能有效降低狀態(tài)爆炸，控制攻防圖規(guī)模等優(yōu)點(diǎn)。在下一步的工作中，將在大規(guī)模的真實(shí)網(wǎng)絡(luò)中進(jìn)一步驗(yàn)證算法的性能并進(jìn)行改進(jìn)。

［1］LIU X，REN TC，MA L，etal.Research on an improved information network security defence model and production method［C］//Proceedings of the 15th IEEE Conference on DecisionandControlCancun，Mexico：Springer，2013：829-834.

［2］吳金宇，金舒原，楊智.基于網(wǎng)絡(luò)流的攻擊圖分析方法［J］.計(jì)算機(jī)研究與發(fā)展，2014，50（8）：497-1505.

［3］宋舜宏，陸余良，夏陽，等.基于貪心策略的網(wǎng)絡(luò)攻擊圖生成方法［J］.計(jì)算機(jī)工程，2012，38（2）：126-13.

［4］王元卓，林闖，程學(xué)旗，等.基于隨機(jī)博弈模型的網(wǎng)絡(luò)攻防量化分析方法［J］.計(jì)算機(jī)學(xué)報(bào)，2010，33（9）：1748-1762.

［5］姜偉，方濱興.基于攻防隨機(jī)博弈模型的防御策略選取研究［J］.計(jì)算機(jī)研究與發(fā)展，2012，47（10）：1214-1223.

［6］劉剛，李千目，張宏.基于狀態(tài)攻防圖模型的網(wǎng)絡(luò)安全防御策略生成方法［J］.計(jì)算機(jī)應(yīng)用，2013，33（11）：121-125.

［7］SHAMIIOR O，HANBERGE J.Automated generation and analysisofattack-defensegraphs［C］//Proceedingsof the51th IEEE Symposium on Security and Privacy，Washington DC：IEEEComputer Society，2013：273-284.

［8］李玲娟，孫光輝.網(wǎng)絡(luò)攻擊圖生成算法研究［J］.計(jì)算機(jī)研究與發(fā)展，2014，20（10）：171-175.

［9］張恒巍，張健，王晉東，等.基于連通度算子的系統(tǒng)漏洞風(fēng)險(xiǎn)評(píng)估研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2015，36（1）：71-76.

［10］何江湖，潘曉忠.基于漏洞關(guān)聯(lián)攻擊代價(jià)的攻擊圖生成算法［J］.計(jì)算機(jī)應(yīng)用研究，2012，29（5）：1908-1913.

［11］MAN D P，ZHANG B，YANGW，etal.Amethod for global attack graph generation［C］//Proceedings of the 9th IEEE ConferenceonNetworking，NewYork：Springer，2013：736-741.

［12］王晉東，余定坤.靜態(tài)貝葉斯博弈主動(dòng)防御策略選取方法［J］.西安電子科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，20 （10）：102-107.

Attack-defense Graph Generation Algorithm Based on State Reduction

ZHANG Heng-wei，YU Ding-kun，KOU Guang，HAN Ji-hong
（PLA Information Engineering University，Zhengzhou 450001，China）

To solve the issue of state explosion in attack-defense graph generation，an algorithm of attack-defense graph generation based on state reduction is proposed.This algorithm compares the authority of nodes in independent state on the basis of analyzing the characteristics of attacker and the target network.It achieves reduction to low-privileged nodes and elimination of redundant attack path under the premise of reserving nodes of highest permission.Simulation results show that the algorithm has advantages of low computational complexity，effectively reducing state explosion and controlling the scale of attack-defense graph.

attack-defensegraph，stateexplosion，node permission，state reduction

TP393

A

1002-0640（2016）08-0064-06

2015-06-25

2015-07-17

國家自然科學(xué)基金（61303074；61309013）；河南省科技攻關(guān)計(jì)劃基金資助項(xiàng)目（12210231003；13210231002）

張恒?。?978-），男，河南洛陽人，博士研究生，講師。研究方向：信息安全與網(wǎng)絡(luò)對(duì)抗、安全風(fēng)險(xiǎn)評(píng)估。