基于攻擊防御樹的CPS最小防御代價計算方法

鐘志成,徐丙鳳,顧久根

(南京林業大學 信息科學技術學院,南京 210037)

0 概述

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

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

當前的研究工作主要以防御措施的數量為標準,在此基礎上結合其他經濟參數來評估防御策略的優劣,然而防御措施的數量并不能決定系統整體防御代價,選擇最小數目的防御措施未必能達到降低防御成本的目的。為此,本文針對CPS的安全防護成本問題,提出一種CPS最小防御代價的計算方法,并設計相應的計算軟件,以提高防御措施的有效性。

1 相關工作

目前對CPS做安全風險評估的定性分析方法,典型的有攻擊樹、攻擊防御樹、故障樹、攻擊圖等。攻擊樹[5]是一種系統化的攻擊場景建模方法,文獻[13]對其做了正式的定義。攻擊樹按從上至下的順序逐層建模攻擊場景,將攻擊目標逐層分解成原子攻擊,可以對攻擊場景做定性和定量分析,被廣泛應用于系統安全性評估。但是攻擊樹僅能描述攻擊場景,無法體現攻擊者和防御者之間的交互行為。為此,文獻[6]提出了攻擊防御樹的概念。攻擊防御樹在攻擊樹的基礎上增加了防御節點,可以建模攻擊防御場景從而對系統進行安全評估。

文獻[14-19]利用攻擊防御樹對CPS進行定量風險評估。文獻[14]針對SCADA系統提出一種基于層次分析法和攻擊防御樹模型的SCADA系統脆弱性評估方法。文獻[15]利用ADTree對CPS進行風險評估,并提出兩個經濟指標來評估攻擊防御樹的有效性。文獻[16]基于攻擊防御樹提出一種針對APT攻擊的風險評估理論模型。文獻[17]通過網絡攻防行為樹來描述網絡攻防場景并利用該模型評估防御措施的效果。文獻[18]利用帶時序邏輯的拓展攻擊防御樹模型,構建一種基于博弈論方法的攻擊防御場景分析框架。文獻[19]針對高級持續性威脅,建立一種攻擊防御樹量化模型,同時分析攻擊行為對防御措施的影響。然而,目前的攻擊防御樹定量分析方法較少考慮對最小防御代價的計算,本文將對此進行研究。

2 最小防御防御代價計算方法

2.1 計算流程

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

圖1 最小防御代價計算流程

2.2 原子攻擊防御樹

如果基于傳統的ADTree來求解最小防御代價,則需要遞歸查詢ADTree的子樹,效率較低。為此,本文提出原子攻擊防御樹(Atom Attack Defense Tree,A2DTree)的概念。A2DTree是一種特殊類型的ADTree,其對一般的ADTree做了如下限制:1)根節點的類型是攻擊節點;2)只有原子節點才有相應的防御節點,其他節點沒有防御節點。由于A2DTree的結構比較特殊,因此要求解A2DTree的最小防御代價,只需要求解A2DTree的徑集并代入防御代價進行計算,即可求出最小防御代價。A2DTree示例如圖2所示。

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

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

A2DTree=,V=Vat∪Vdf

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

割集和徑集提供了關于系統脆弱性的重要信息,下面給出原子攻擊防御樹割集和徑集的定義。

定義1原子攻擊防御樹的割集是導致頂部攻擊事件發生的基本攻擊事件的集合。

?Vc,?vc∈Vc,有vc∈Vl,若集合Vc中的攻擊事件全部成功,頂層攻擊會成功,則Vc是A2DTree的一個割集,Vl是原子攻擊節點的集合。

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

?Vp,?vp∈Vp,有vp∈Vl,若集合Vp中的攻擊事件全部失敗,頂層攻擊會失敗,則Vp是A2DTree的一個徑集,Vl是原子攻擊節點的集合。

2.3 算法描述

2.3.1 攻擊防御樹到原子攻擊防御樹的轉換算法

針對中間攻擊節點也有防御節點的常用ADTree,利用A2DTree的特征求解其最小防御代價,提出一種將一般ADTree轉化為與A2DTree結構一致的等價樹的算法。利用轉化后的ADTree來求解最小防御代價,可以提高ADTree最小防御代價計算算法的性能。

ADTree轉化為A2DTree的形式,需要將所有存在防御子節點的中間攻擊節點下移,使中間攻擊節點成為葉子節點。下移過程分為以下5個步驟:

1)構造2個中間替補節點T1、T2。

2)將需要下移的中間節點N1添加到T1的子節點集合中。

3)將原N1的子節點添加到T2的子節點集合中,原N1子節點之間的邏輯關系不變。

4)將T2節點添加到T1的子節點集合中,T1子節點之間的邏輯關系為AND。

5)將T1節點添加到原N1父節點的子節點集合中。

從ADTree的根節點開始遞歸遍歷,對有防御子節點的中間節點執行上述下移過程,可得到最小防御代價與原ADTree相等的A2DTree。ADTree轉化為A2DTree的示例如圖3所示。

圖3 攻擊防御樹轉化為原子攻擊防御樹的示例Fig.3 Example of attack defense tree being transformed into atom attack defense tree

可以證明ADTree中任意子樹的最小防御代價和經過轉換得到的新子樹的最小防御代價相等。假設ADT1是ADTree中某一棵以N1為根節點的子樹,N1為中間攻擊節點并且有防御節點D1。ADT1能防御成功且防御代價可能最小的方案有2種:1)采用D1防御節點;2)不采用D1防御節點,采用ADT1中其他所有能防御成功的防御節點組合中防御代價最小的組合。2種方案對應的最小防御代價分別為C1、C2,ADT1的最小防御代價MinCost1為C1、C2中的較小值。ADT1經過轉換后得到ADT2,N1移動成為葉子節點。假設T1是ADT2的根節點,T2是N1原來的子節點的新父節點。因為N1和T2之間的邏輯關系為AND且T1、T2沒有防御子節點,所以ADT2防御成功且防御代價可能最小的方案有2種:1)采用D1防御措施;2)采用使T2防御成功的防御節點組合中防御代價最小的組合。2種方案對應的最小防御代價分別為C3、C4,ADT2的最小防御代價MinCost2為C3、C4中的較小值。因為C1=C2,C3=C4,所以MinCost1和MinCost2相等,即ADT1的最小防御代價和ADT2的最小防御代價是一致的。推廣以上結論,可以證明ADTree的最小防御代價和A2DTree的最小防御代價相等。

假設待求解的ADTree共有A個攻擊節點和D個防御節點。攻擊防御樹的轉換過程,實際上是遍歷整個ADTree并把有防御節點的中間攻擊節點下移的過程,因此,轉換算法具有線性時間復雜度O(A+D)。

算法1攻擊防御樹轉換為原子攻擊防御樹

輸入攻擊防御樹ADTree

輸出原子攻擊防御樹A2DTree

1.procedure ConverseToA2DTree(節點root)

2.Children:={root的子節點集合};

3.NewChildren={};

4.i:=1;

5.repeat

6.child:=Children中第i個節點;

7.if child是中間攻擊節點且有防御子節點

8.then

9.T1:=新的攻擊節點;

10.T1的子節點關系:=child的子節點關系;

11.T1的子節點:=child的子節點;

12.T2:=新的攻擊節點;

13.T2的子節點關系:=AND;

14.將child添加到T2的子節點集合中;

15.將T1添加到T2的子節點集合中;

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的子節點個數+1;

24.root的子節點集合:=NewChildren;

25.end procedure

26.NewRoot:=新的根節點;

27.將ADTree的根節點添加到NewRoot的子節點集合中;

28.call ConverseToA2DTree(NewRoot);

2.3.2 最小防御代價求解算法

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

1)將A2DTree的攻擊節點看作布爾變量,從根節點開始逐層向下遞歸,計算出用原子攻擊節點表示根節點的布爾表達式。

2)展開布爾表達式,得到一個析取范式(DNF)。

3)提取該DNF中的每一個簡單合取式,合取式中所有文字對應的攻擊節點構成的集合即A2DTree一個割集。

求出A2DTree的所有徑集后,計算各個徑集中所有原子攻擊對應防御代價之和,所有防御代價中的最小值即為最小防御代價。

假設待求解的ADTree共有A個攻擊節點和D個防御節點,其中有防御節點的中間攻擊節點有A1個。ADTree轉換得到的A2DTree有(A+2A1)個攻擊節點和D個防御節點。算法需要遍歷整個A2DTree求得由原子攻擊節點組成的布爾表達式來計算最小防御代價,因此,其時間復雜度為O(A+2A1+D)。

算法2計算攻擊防御樹最小防御代價

輸入原子攻擊防御樹A2DTree

輸出A2DTree的最小防御代價和需要防御的攻擊節點集合

1.BooleanExpression:=A2DTree的邏輯表達式;

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

3.MinCost:=+∞;

4.PathSet:={};

5.j:=1;

6.repeat

7.pathset:=PathSets中的第j個徑集;

8.cur_cost:=cutset對應的防御代價;

9.if cur_cost

10.then

11.MinCost:=cur_cost;

12.PathSet:=pathset;

13.end if

14.j:=j+1;

15.until j=PathSets中子集合的個數+1;

3 軟件實現與實驗分析

3.1 軟件實現

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

圖4 最小防御代價計算軟件用戶界面Fig.4 User interfaces of the minimum defense cost calculation software

1)導入攻擊防御樹建模工具生成的XML文件,生成相應的攻擊防御樹模型。

2)為防御節點賦予防御代價屬性值。

3)將攻擊防御樹轉換成為原子攻擊防御樹。

4)計算出原子攻擊防御樹的所有徑集和相應的防御代價,并排序輸出。

3.2 實例分析

下面以文獻[20]中電力系統的SCADA系統為例,對本文提出的方法進行驗證。SCADA系統由控制中心網絡、控制中心和變電站之間的通信網絡、變電站自動化系統等網絡組件構成,攻擊者利用網絡組件的漏洞可以對SCADA進行攻擊,獲得非法的操作權限,從而給電力系統造成安全隱患和經濟損失[20]。在本實例中,攻擊者通過網絡攻擊向控制保護繼電器發出跳閘命令,導致斷路器無故障跳閘,從而造成停電。通過本文方法給文獻[20]中的攻擊樹添加防御節點,所得到的攻擊防御樹如圖5所示,其中各節點的具體含義如表1所示。

圖5 斷路器無故障跳閘攻擊防御樹

表1 攻擊防御樹各節點的含義

通過對防御措施的實現難度、需要的時間和資金等因素進行綜合評估,評估人員根據實際情況對防御代價等級進行評級,得到各防御節點的防御代價等級,等級如表2所示。

表2 各防御節點防御代價等級Table 2 Defense cost levels of defense nodes

利用攻擊防御樹建模軟件對攻擊防御樹進行建模,并將模型輸出為XML文件導入攻擊防御樹最小防御代價計算軟件。文件導入結果如圖6所示。

圖6 XML文件導入結果Fig.6 Result of XML file import

選擇“添加防御代價屬性”為防御節點添加防御代價值,防御代價值是一個非負實數,使用具體值還是防御代價等級用戶可自行選擇。屬性賦值結果如圖7所示。

圖7 屬性賦值結果Fig.7 Result of attribute assignment

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

圖8 部分計算結果Fig.8 Partial calculation results

由最小防御代價計算工具輸出的結果可知,有2個節點集合對應的防御代價最小。根據該結果,可以對集合中相應的攻擊節點加強防御,降低防御成本。

3.3 性能比較

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

表3 兩種算法的時間和空間消耗

由表3可知,CONV_ALGO的時間和空間消耗都優于UTDRE_ALGO。UTDRE_ALGO的時間復雜度和攻擊防御樹的包含根節點的子樹個數有關,CONV_ALGO的時間復雜度和攻擊防御樹的節點個數有關。當攻擊防御樹的規模比較大時,子樹的個數會比較多。例如實驗中的攻擊防御樹E,經過粗略計算,樹E中包含根節點的子樹個數約有50 000個,即UTDRE_ALGO需要計算約50 000個ADTree的徑集,而CONV_ALGO只需計算轉換后的A2DTree的徑集,從而減少了計算徑集的時間,提高了效率。

4 結束語

本文對CPS安全防御代價評估問題進行研究,通過建模攻擊防御樹和求解徑集,設計一種適用于CPS 的防御代價計算方法。基于攻擊防御樹給出原子攻擊防御樹的概念,將攻擊防御樹轉換成原子攻擊防御樹,在此基礎上求解原子攻擊防御樹的徑集并計算相應的防御代價。實例驗證結果表明,該方法較自頂向下直接求解的算法效率更高。后續將進一步改進攻擊防御樹的結構,對帶有時序邏輯的攻擊防御樹進行最小防御代價求解,同時優化攻擊防御樹徑集的求解方法,減少中間過程,從而提高算法效率。