基于攻擊防御樹(shù)的CPS最小防御代價(jià)計(jì)算方法

鐘志成,徐丙鳳,顧久根

(南京林業(yè)大學(xué) 信息科學(xué)技術(shù)學(xué)院,南京 210037)

0 概述

信息物理融合系統(tǒng)(Cyber Physical System,CPS)是一種利用現(xiàn)代傳感器技術(shù)、計(jì)算技術(shù)和網(wǎng)絡(luò)技術(shù)實(shí)現(xiàn)3C(Computation,Communication,Control)融合,將物理世界和網(wǎng)絡(luò)世界有效聯(lián)結(jié)的復(fù)雜系統(tǒng),是推動(dòng)工業(yè)4.0發(fā)展的核心技術(shù)[1]。近年來(lái),CPS被廣泛應(yīng)用于電力、醫(yī)療、交通運(yùn)輸、供水(天然氣)等工業(yè)控制系統(tǒng),是工業(yè)界和學(xué)術(shù)界的研究熱點(diǎn)[2]。由于CPS各個(gè)部件之間的通信主要依靠網(wǎng)絡(luò),因此其易受網(wǎng)絡(luò)攻擊影響,而CPS物理部件和網(wǎng)絡(luò)部件之間存在高度耦合性,網(wǎng)絡(luò)攻擊很容易引起物理部件的故障,從而導(dǎo)致嚴(yán)重后果[3]。隨著CPS系統(tǒng)不斷發(fā)展,其面臨的攻擊手段也在不斷更新,攻擊方式的多樣性和隱蔽性給系統(tǒng)造成了極大的安全威脅[4]。為防止各種網(wǎng)絡(luò)攻擊對(duì)CPS造成災(zāi)難性后果,對(duì)CPS中的一些節(jié)點(diǎn)增加防御措施十分必要。但是由于CPS的復(fù)雜性很高,針對(duì)其中所有節(jié)點(diǎn)都增加有效的防御措施比較困難,防御代價(jià)較高,因此找到一種既能降低防御代價(jià)又能有效防御攻擊的方法具有重要意義。

利用攻擊樹(shù)(Attack Tree,ATree)[5]、攻擊防御樹(shù)(Attack Defense Tree,ADTree)[6]、攻擊對(duì)策樹(shù)(Attack Countermeasure Tree,ACT)[7]等圖形化模型可以對(duì)CPS進(jìn)行風(fēng)險(xiǎn)建模。圖形化模型可以直觀地體現(xiàn)CPS中攻擊者和防御者的行為,為CPS防御策略的分析工作提供便利。文獻(xiàn)[8]提出為ADTree中的節(jié)點(diǎn)添加攻擊事件的攻擊收益(Return of Attack,ROA)和防御措施的防御收益(Return of Investment,ROI)兩個(gè)經(jīng)濟(jì)指標(biāo),以此評(píng)估ADTree的有效性并指導(dǎo)最佳防御策略的選擇。文獻(xiàn)[9]提出一種ACT和ACT在不同約束下的最優(yōu)防御措施計(jì)算方法,利用約束矩陣和貪心算法計(jì)算覆蓋攻擊節(jié)點(diǎn)最多的防御節(jié)點(diǎn)的集合。文獻(xiàn)[10]利用ADTree建立SCADA(Supervisory Control and Data Acquisition)系統(tǒng)[11]的攻防博弈模型,通過(guò)求解該博弈模型的納什均衡,得到攻防雙方的策略選擇概率分布結(jié)果,從而確定攻防雙方為實(shí)現(xiàn)自身收益最大化而選擇的最優(yōu)策略。文獻(xiàn)[12]利用ATree對(duì)智能電網(wǎng)進(jìn)行風(fēng)險(xiǎn)建模,并基于布爾可滿(mǎn)足性問(wèn)題提出一種最小數(shù)目原子節(jié)點(diǎn)防御措施計(jì)算方法。

當(dāng)前的研究工作主要以防御措施的數(shù)量為標(biāo)準(zhǔn),在此基礎(chǔ)上結(jié)合其他經(jīng)濟(jì)參數(shù)來(lái)評(píng)估防御策略的優(yōu)劣,然而防御措施的數(shù)量并不能決定系統(tǒng)整體防御代價(jià),選擇最小數(shù)目的防御措施未必能達(dá)到降低防御成本的目的。為此,本文針對(duì)CPS的安全防護(hù)成本問(wèn)題,提出一種CPS最小防御代價(jià)的計(jì)算方法,并設(shè)計(jì)相應(yīng)的計(jì)算軟件,以提高防御措施的有效性。

1 相關(guān)工作

目前對(duì)CPS做安全風(fēng)險(xiǎn)評(píng)估的定性分析方法,典型的有攻擊樹(shù)、攻擊防御樹(shù)、故障樹(shù)、攻擊圖等。攻擊樹(shù)[5]是一種系統(tǒng)化的攻擊場(chǎng)景建模方法,文獻(xiàn)[13]對(duì)其做了正式的定義。攻擊樹(shù)按從上至下的順序逐層建模攻擊場(chǎng)景,將攻擊目標(biāo)逐層分解成原子攻擊,可以對(duì)攻擊場(chǎng)景做定性和定量分析,被廣泛應(yīng)用于系統(tǒng)安全性評(píng)估。但是攻擊樹(shù)僅能描述攻擊場(chǎng)景,無(wú)法體現(xiàn)攻擊者和防御者之間的交互行為。為此,文獻(xiàn)[6]提出了攻擊防御樹(shù)的概念。攻擊防御樹(shù)在攻擊樹(shù)的基礎(chǔ)上增加了防御節(jié)點(diǎn),可以建模攻擊防御場(chǎng)景從而對(duì)系統(tǒng)進(jìn)行安全評(píng)估。

文獻(xiàn)[14-19]利用攻擊防御樹(shù)對(duì)CPS進(jìn)行定量風(fēng)險(xiǎn)評(píng)估。文獻(xiàn)[14]針對(duì)SCADA系統(tǒng)提出一種基于層次分析法和攻擊防御樹(shù)模型的SCADA系統(tǒng)脆弱性評(píng)估方法。文獻(xiàn)[15]利用ADTree對(duì)CPS進(jìn)行風(fēng)險(xiǎn)評(píng)估,并提出兩個(gè)經(jīng)濟(jì)指標(biāo)來(lái)評(píng)估攻擊防御樹(shù)的有效性。文獻(xiàn)[16]基于攻擊防御樹(shù)提出一種針對(duì)APT攻擊的風(fēng)險(xiǎn)評(píng)估理論模型。文獻(xiàn)[17]通過(guò)網(wǎng)絡(luò)攻防行為樹(shù)來(lái)描述網(wǎng)絡(luò)攻防場(chǎng)景并利用該模型評(píng)估防御措施的效果。文獻(xiàn)[18]利用帶時(shí)序邏輯的拓展攻擊防御樹(shù)模型,構(gòu)建一種基于博弈論方法的攻擊防御場(chǎng)景分析框架。文獻(xiàn)[19]針對(duì)高級(jí)持續(xù)性威脅,建立一種攻擊防御樹(shù)量化模型,同時(shí)分析攻擊行為對(duì)防御措施的影響。然而,目前的攻擊防御樹(shù)定量分析方法較少考慮對(duì)最小防御代價(jià)的計(jì)算,本文將對(duì)此進(jìn)行研究。

2 最小防御防御代價(jià)計(jì)算方法

2.1 計(jì)算流程

為求解CPS的最小防御代價(jià),首先要用ADTree建模CPS中的攻擊事件和防御事件。建模完成后,需要對(duì)ADTree進(jìn)行轉(zhuǎn)換以提高算法效率,然后計(jì)算轉(zhuǎn)換得到的ADTree的徑集,最后計(jì)算徑集對(duì)應(yīng)的防御代價(jià)并找到最小防御代價(jià)。最小防御防御代價(jià)計(jì)算流程如圖1所示。

圖1 最小防御代價(jià)計(jì)算流程

2.2 原子攻擊防御樹(shù)

如果基于傳統(tǒng)的ADTree來(lái)求解最小防御代價(jià),則需要遞歸查詢(xún)ADTree的子樹(shù),效率較低。為此,本文提出原子攻擊防御樹(shù)(Atom Attack Defense Tree,A2DTree)的概念。A2DTree是一種特殊類(lèi)型的ADTree,其對(duì)一般的ADTree做了如下限制:1)根節(jié)點(diǎn)的類(lèi)型是攻擊節(jié)點(diǎn);2)只有原子節(jié)點(diǎn)才有相應(yīng)的防御節(jié)點(diǎn),其他節(jié)點(diǎn)沒(méi)有防御節(jié)點(diǎn)。由于A2DTree的結(jié)構(gòu)比較特殊,因此要求解A2DTree的最小防御代價(jià),只需要求解A2DTree的徑集并代入防御代價(jià)進(jìn)行計(jì)算,即可求出最小防御代價(jià)。A2DTree示例如圖2所示。

圖2 原子攻擊防御樹(shù)示例Fig.2 Example of atom attack defense tree

原子攻擊防御樹(shù)的形式化描述如下:

A2DTree=,V=Vat∪Vdf

其中:Vat表示所有攻擊節(jié)點(diǎn)的集合;Vdf表示所有防御節(jié)點(diǎn)的集合;e={vs,vd}∈E,表示一條從節(jié)點(diǎn)vs到vd的邊;Q={AND,OR,SAND},表示攻擊防御樹(shù)中邏輯門(mén)的集合;vr∈Vat,表示根節(jié)點(diǎn);Vl表示原子攻擊節(jié)點(diǎn)的集合,Vdf和Vl存在一一映射關(guān)系。

割集和徑集提供了關(guān)于系統(tǒng)脆弱性的重要信息,下面給出原子攻擊防御樹(shù)割集和徑集的定義。

定義1原子攻擊防御樹(shù)的割集是導(dǎo)致頂部攻擊事件發(fā)生的基本攻擊事件的集合。

?Vc,?vc∈Vc,有vc∈Vl,若集合Vc中的攻擊事件全部成功,頂層攻擊會(huì)成功,則Vc是A2DTree的一個(gè)割集,Vl是原子攻擊節(jié)點(diǎn)的集合。

定義2原子攻擊防御樹(shù)的徑集是保證頂部攻擊事件不發(fā)生的基本攻擊事件的集合。

?Vp,?vp∈Vp,有vp∈Vl,若集合Vp中的攻擊事件全部失敗,頂層攻擊會(huì)失敗,則Vp是A2DTree的一個(gè)徑集,Vl是原子攻擊節(jié)點(diǎn)的集合。

2.3 算法描述

2.3.1 攻擊防御樹(shù)到原子攻擊防御樹(shù)的轉(zhuǎn)換算法

針對(duì)中間攻擊節(jié)點(diǎn)也有防御節(jié)點(diǎn)的常用ADTree,利用A2DTree的特征求解其最小防御代價(jià),提出一種將一般ADTree轉(zhuǎn)化為與A2DTree結(jié)構(gòu)一致的等價(jià)樹(shù)的算法。利用轉(zhuǎn)化后的ADTree來(lái)求解最小防御代價(jià),可以提高ADTree最小防御代價(jià)計(jì)算算法的性能。

ADTree轉(zhuǎn)化為A2DTree的形式,需要將所有存在防御子節(jié)點(diǎn)的中間攻擊節(jié)點(diǎn)下移,使中間攻擊節(jié)點(diǎn)成為葉子節(jié)點(diǎn)。下移過(guò)程分為以下5個(gè)步驟:

1)構(gòu)造2個(gè)中間替補(bǔ)節(jié)點(diǎn)T1、T2。

2)將需要下移的中間節(jié)點(diǎn)N1添加到T1的子節(jié)點(diǎn)集合中。

3)將原N1的子節(jié)點(diǎn)添加到T2的子節(jié)點(diǎn)集合中,原N1子節(jié)點(diǎn)之間的邏輯關(guān)系不變。

4)將T2節(jié)點(diǎn)添加到T1的子節(jié)點(diǎn)集合中,T1子節(jié)點(diǎn)之間的邏輯關(guān)系為AND。

5)將T1節(jié)點(diǎn)添加到原N1父節(jié)點(diǎn)的子節(jié)點(diǎn)集合中。

從ADTree的根節(jié)點(diǎn)開(kāi)始遞歸遍歷,對(duì)有防御子節(jié)點(diǎn)的中間節(jié)點(diǎn)執(zhí)行上述下移過(guò)程,可得到最小防御代價(jià)與原ADTree相等的A2DTree。ADTree轉(zhuǎn)化為A2DTree的示例如圖3所示。

圖3 攻擊防御樹(shù)轉(zhuǎn)化為原子攻擊防御樹(shù)的示例Fig.3 Example of attack defense tree being transformed into atom attack defense tree

可以證明ADTree中任意子樹(shù)的最小防御代價(jià)和經(jīng)過(guò)轉(zhuǎn)換得到的新子樹(shù)的最小防御代價(jià)相等。假設(shè)ADT1是ADTree中某一棵以N1為根節(jié)點(diǎn)的子樹(shù),N1為中間攻擊節(jié)點(diǎn)并且有防御節(jié)點(diǎn)D1。ADT1能防御成功且防御代價(jià)可能最小的方案有2種:1)采用D1防御節(jié)點(diǎn);2)不采用D1防御節(jié)點(diǎn),采用ADT1中其他所有能防御成功的防御節(jié)點(diǎn)組合中防御代價(jià)最小的組合。2種方案對(duì)應(yīng)的最小防御代價(jià)分別為C1、C2,ADT1的最小防御代價(jià)MinCost1為C1、C2中的較小值。ADT1經(jīng)過(guò)轉(zhuǎn)換后得到ADT2,N1移動(dòng)成為葉子節(jié)點(diǎn)。假設(shè)T1是ADT2的根節(jié)點(diǎn),T2是N1原來(lái)的子節(jié)點(diǎn)的新父節(jié)點(diǎn)。因?yàn)镹1和T2之間的邏輯關(guān)系為AND且T1、T2沒(méi)有防御子節(jié)點(diǎn),所以ADT2防御成功且防御代價(jià)可能最小的方案有2種:1)采用D1防御措施;2)采用使T2防御成功的防御節(jié)點(diǎn)組合中防御代價(jià)最小的組合。2種方案對(duì)應(yīng)的最小防御代價(jià)分別為C3、C4,ADT2的最小防御代價(jià)MinCost2為C3、C4中的較小值。因?yàn)镃1=C2,C3=C4,所以MinCost1和MinCost2相等,即ADT1的最小防御代價(jià)和ADT2的最小防御代價(jià)是一致的。推廣以上結(jié)論,可以證明ADTree的最小防御代價(jià)和A2DTree的最小防御代價(jià)相等。

假設(shè)待求解的ADTree共有A個(gè)攻擊節(jié)點(diǎn)和D個(gè)防御節(jié)點(diǎn)。攻擊防御樹(shù)的轉(zhuǎn)換過(guò)程,實(shí)際上是遍歷整個(gè)ADTree并把有防御節(jié)點(diǎn)的中間攻擊節(jié)點(diǎn)下移的過(guò)程,因此,轉(zhuǎn)換算法具有線性時(shí)間復(fù)雜度O(A+D)。

算法1攻擊防御樹(shù)轉(zhuǎn)換為原子攻擊防御樹(shù)

輸入攻擊防御樹(shù)ADTree

輸出原子攻擊防御樹(shù)A2DTree

1.procedure ConverseToA2DTree(節(jié)點(diǎn)root)

2.Children:={root的子節(jié)點(diǎn)集合};

3.NewChildren={};

4.i:=1;

5.repeat

6.child:=Children中第i個(gè)節(jié)點(diǎn);

7.if child是中間攻擊節(jié)點(diǎn)且有防御子節(jié)點(diǎn)

8.then

9.T1:=新的攻擊節(jié)點(diǎn);

10.T1的子節(jié)點(diǎn)關(guān)系:=child的子節(jié)點(diǎn)關(guān)系;

11.T1的子節(jié)點(diǎn):=child的子節(jié)點(diǎn);

12.T2:=新的攻擊節(jié)點(diǎn);

13.T2的子節(jié)點(diǎn)關(guān)系:=AND;

14.將child添加到T2的子節(jié)點(diǎn)集合中;

15.將T1添加到T2的子節(jié)點(diǎn)集合中;

16.call conversToA2DTree(T1);

17.將T2添加到Newchildren中;

18.else

19.call ConversToA2DTree(child);

20.將child添加到Newchildren中;

21.end if

22.i:=i+1;

23.until i=Children的子節(jié)點(diǎn)個(gè)數(shù)+1;

24.root的子節(jié)點(diǎn)集合:=NewChildren;

25.end procedure

26.NewRoot:=新的根節(jié)點(diǎn);

27.將ADTree的根節(jié)點(diǎn)添加到NewRoot的子節(jié)點(diǎn)集合中;

28.call ConverseToA2DTree(NewRoot);

2.3.2 最小防御代價(jià)求解算法

將ADTree轉(zhuǎn)化為A2DTree后,利用成功樹(shù)法求A2DTree的徑集。求出A2DTree的對(duì)偶樹(shù),將原A2DTree中的AND換成OR,OR換成AND,對(duì)偶樹(shù)的割集就是原A2DTree的徑集。本文采用代數(shù)法求攻擊防御樹(shù)的割集,具體步驟如下:

1)將A2DTree的攻擊節(jié)點(diǎn)看作布爾變量,從根節(jié)點(diǎn)開(kāi)始逐層向下遞歸,計(jì)算出用原子攻擊節(jié)點(diǎn)表示根節(jié)點(diǎn)的布爾表達(dá)式。

2)展開(kāi)布爾表達(dá)式,得到一個(gè)析取范式(DNF)。

3)提取該DNF中的每一個(gè)簡(jiǎn)單合取式,合取式中所有文字對(duì)應(yīng)的攻擊節(jié)點(diǎn)構(gòu)成的集合即A2DTree一個(gè)割集。

求出A2DTree的所有徑集后,計(jì)算各個(gè)徑集中所有原子攻擊對(duì)應(yīng)防御代價(jià)之和,所有防御代價(jià)中的最小值即為最小防御代價(jià)。

假設(shè)待求解的ADTree共有A個(gè)攻擊節(jié)點(diǎn)和D個(gè)防御節(jié)點(diǎn),其中有防御節(jié)點(diǎn)的中間攻擊節(jié)點(diǎn)有A1個(gè)。ADTree轉(zhuǎn)換得到的A2DTree有(A+2A1)個(gè)攻擊節(jié)點(diǎn)和D個(gè)防御節(jié)點(diǎn)。算法需要遍歷整個(gè)A2DTree求得由原子攻擊節(jié)點(diǎn)組成的布爾表達(dá)式來(lái)計(jì)算最小防御代價(jià),因此,其時(shí)間復(fù)雜度為O(A+2A1+D)。

算法2計(jì)算攻擊防御樹(shù)最小防御代價(jià)

輸入原子攻擊防御樹(shù)A2DTree

輸出A2DTree的最小防御代價(jià)和需要防御的攻擊節(jié)點(diǎn)集合

1.BooleanExpression:=A2DTree的邏輯表達(dá)式;

2.PathSets:={BooleanExpression中的所有簡(jiǎn)單合取式,即A2DTree所有徑集的集合};

3.MinCost:=+∞;

4.PathSet:={};

5.j:=1;

6.repeat

7.pathset:=PathSets中的第j個(gè)徑集;

8.cur_cost:=cutset對(duì)應(yīng)的防御代價(jià);

9.if cur_cost

10.then

11.MinCost:=cur_cost;

12.PathSet:=pathset;

13.end if

14.j:=j+1;

15.until j=PathSets中子集合的個(gè)數(shù)+1;

3 軟件實(shí)現(xiàn)與實(shí)驗(yàn)分析

3.1 軟件實(shí)現(xiàn)

基于攻擊防御樹(shù)建模方法,本文在Eclipse平臺(tái)上利用Java語(yǔ)言實(shí)現(xiàn)了最小防御代價(jià)計(jì)算軟件(獲取地址為https://github.com/zzc1/ADTree_Min_DefCost/releases/tag/1.0),其用戶(hù)界面如圖4所示。具體實(shí)現(xiàn)功能如下:

圖4 最小防御代價(jià)計(jì)算軟件用戶(hù)界面Fig.4 User interfaces of the minimum defense cost calculation software

1)導(dǎo)入攻擊防御樹(shù)建模工具生成的XML文件,生成相應(yīng)的攻擊防御樹(shù)模型。

2)為防御節(jié)點(diǎn)賦予防御代價(jià)屬性值。

3)將攻擊防御樹(shù)轉(zhuǎn)換成為原子攻擊防御樹(shù)。

4)計(jì)算出原子攻擊防御樹(shù)的所有徑集和相應(yīng)的防御代價(jià),并排序輸出。

3.2 實(shí)例分析

下面以文獻(xiàn)[20]中電力系統(tǒng)的SCADA系統(tǒng)為例,對(duì)本文提出的方法進(jìn)行驗(yàn)證。SCADA系統(tǒng)由控制中心網(wǎng)絡(luò)、控制中心和變電站之間的通信網(wǎng)絡(luò)、變電站自動(dòng)化系統(tǒng)等網(wǎng)絡(luò)組件構(gòu)成,攻擊者利用網(wǎng)絡(luò)組件的漏洞可以對(duì)SCADA進(jìn)行攻擊,獲得非法的操作權(quán)限,從而給電力系統(tǒng)造成安全隱患和經(jīng)濟(jì)損失[20]。在本實(shí)例中,攻擊者通過(guò)網(wǎng)絡(luò)攻擊向控制保護(hù)繼電器發(fā)出跳閘命令,導(dǎo)致斷路器無(wú)故障跳閘,從而造成停電。通過(guò)本文方法給文獻(xiàn)[20]中的攻擊樹(shù)添加防御節(jié)點(diǎn),所得到的攻擊防御樹(shù)如圖5所示,其中各節(jié)點(diǎn)的具體含義如表1所示。

圖5 斷路器無(wú)故障跳閘攻擊防御樹(shù)

表1 攻擊防御樹(shù)各節(jié)點(diǎn)的含義

通過(guò)對(duì)防御措施的實(shí)現(xiàn)難度、需要的時(shí)間和資金等因素進(jìn)行綜合評(píng)估,評(píng)估人員根據(jù)實(shí)際情況對(duì)防御代價(jià)等級(jí)進(jìn)行評(píng)級(jí),得到各防御節(jié)點(diǎn)的防御代價(jià)等級(jí),等級(jí)如表2所示。

表2 各防御節(jié)點(diǎn)防御代價(jià)等級(jí)Table 2 Defense cost levels of defense nodes

利用攻擊防御樹(shù)建模軟件對(duì)攻擊防御樹(shù)進(jìn)行建模,并將模型輸出為XML文件導(dǎo)入攻擊防御樹(shù)最小防御代價(jià)計(jì)算軟件。文件導(dǎo)入結(jié)果如圖6所示。

圖6 XML文件導(dǎo)入結(jié)果Fig.6 Result of XML file import

選擇“添加防御代價(jià)屬性”為防御節(jié)點(diǎn)添加防御代價(jià)值,防御代價(jià)值是一個(gè)非負(fù)實(shí)數(shù),使用具體值還是防御代價(jià)等級(jí)用戶(hù)可自行選擇。屬性賦值結(jié)果如圖7所示。

圖7 屬性賦值結(jié)果Fig.7 Result of attribute assignment

屬性賦值完成后,選擇“計(jì)算防御代價(jià)”計(jì)算最小防御代價(jià),所有的計(jì)算結(jié)果會(huì)按防御代價(jià)的大小升序顯示在彈出的文本框中。部分計(jì)算結(jié)果如圖8所示。

圖8 部分計(jì)算結(jié)果Fig.8 Partial calculation results

由最小防御代價(jià)計(jì)算工具輸出的結(jié)果可知,有2個(gè)節(jié)點(diǎn)集合對(duì)應(yīng)的防御代價(jià)最小。根據(jù)該結(jié)果,可以對(duì)集合中相應(yīng)的攻擊節(jié)點(diǎn)加強(qiáng)防御,降低防御成本。

3.3 性能比較

為進(jìn)行相關(guān)工作的對(duì)比,本文采用文獻(xiàn)[21]中的軟件ADTool對(duì)ADTree進(jìn)行最小防御代價(jià)計(jì)算,ADTool采用的是自頂向下遞歸算法(UTDRE_ALGO),該算法需要計(jì)算原樹(shù)的所有包含根節(jié)點(diǎn)的子樹(shù)的徑集。上文提出的先將攻擊防御樹(shù)進(jìn)行轉(zhuǎn)換的算法(CONV_ALGO)則需要計(jì)算轉(zhuǎn)換后的攻擊防御樹(shù)的徑集。為判斷兩種算法的優(yōu)劣程度,分別用兩種算法求解5個(gè)ADTree模型的最小防御代價(jià),并統(tǒng)計(jì)算法的時(shí)間和空間消耗。所有的實(shí)驗(yàn)均是在一臺(tái)雙核四線程,CPU頻率為2.5 GHz、內(nèi)存為8 GB的計(jì)算機(jī)上完成的,實(shí)驗(yàn)結(jié)果如表3所示。

表3 兩種算法的時(shí)間和空間消耗

由表3可知,CONV_ALGO的時(shí)間和空間消耗都優(yōu)于UTDRE_ALGO。UTDRE_ALGO的時(shí)間復(fù)雜度和攻擊防御樹(shù)的包含根節(jié)點(diǎn)的子樹(shù)個(gè)數(shù)有關(guān),CONV_ALGO的時(shí)間復(fù)雜度和攻擊防御樹(shù)的節(jié)點(diǎn)個(gè)數(shù)有關(guān)。當(dāng)攻擊防御樹(shù)的規(guī)模比較大時(shí),子樹(shù)的個(gè)數(shù)會(huì)比較多。例如實(shí)驗(yàn)中的攻擊防御樹(shù)E,經(jīng)過(guò)粗略計(jì)算,樹(shù)E中包含根節(jié)點(diǎn)的子樹(shù)個(gè)數(shù)約有50 000個(gè),即UTDRE_ALGO需要計(jì)算約50 000個(gè)ADTree的徑集,而CONV_ALGO只需計(jì)算轉(zhuǎn)換后的A2DTree的徑集,從而減少了計(jì)算徑集的時(shí)間,提高了效率。

4 結(jié)束語(yǔ)

本文對(duì)CPS安全防御代價(jià)評(píng)估問(wèn)題進(jìn)行研究,通過(guò)建模攻擊防御樹(shù)和求解徑集,設(shè)計(jì)一種適用于CPS 的防御代價(jià)計(jì)算方法?；诠舴烙鶚?shù)給出原子攻擊防御樹(shù)的概念,將攻擊防御樹(shù)轉(zhuǎn)換成原子攻擊防御樹(shù),在此基礎(chǔ)上求解原子攻擊防御樹(shù)的徑集并計(jì)算相應(yīng)的防御代價(jià)。實(shí)例驗(yàn)證結(jié)果表明,該方法較自頂向下直接求解的算法效率更高。后續(xù)將進(jìn)一步改進(jìn)攻擊防御樹(shù)的結(jié)構(gòu),對(duì)帶有時(shí)序邏輯的攻擊防御樹(shù)進(jìn)行最小防御代價(jià)求解,同時(shí)優(yōu)化攻擊防御樹(shù)徑集的求解方法,減少中間過(guò)程,從而提高算法效率。