基于攻擊圖的復合入侵關聯及預測方法

肖琳琳 王曉輝 李杰

中南大學信息科學與工程學院 湖南 410083

0 引言

如何檢測復合攻擊是當前入侵檢測的熱點問題。大量研究圍繞此問題展開，并已經取得可觀的成果。由于復合入侵的靈活性及復雜性，一般入侵檢測系統會產生大量的孤立報警，但很難確定報警之間因果關系，無法重構入侵場景，所以實用性很低。大多數關聯技術為離線應用而開發的，這些方法的計算復雜度和內存需求都與已接收到的報警數目成線性關系。在警報數目已知道的離線應用中，這不成問題。但在實時的警報關聯中，就會遇到很大的問題。比如，入侵者可以消極等待或者通過故意制造大量無關的試探，避免有因果關系的報警被關聯。

一般而言，報警關聯引擎接收到新的警報時就會向后搜索以前接收的警報，看是否存在新報警的前因報警(存在多個情況下，選擇最近的報警)。由于這一過程對任意新報警都要重復，可以斷言隨著報警數目的不斷增加，搜索時間和內存需求將無法負荷。解決這一問題的，直觀方法就是設置滑動窗口，只對離當前警報最近的一定數目的報警進行關聯。但這種改進，也有明顯的不足之處。顯然，意識到窗口存在的攻擊者可以放慢攻擊步驟，使得原本的相關報警間產生足夠多的其他報警，從而避開關聯，甚至也可以主動發動干擾攻擊以產生大量的干擾警報。

圖1 一般的關聯方法以及帶時間窗口的關聯方法

1 基于攻擊圖的exploit隊列模型

許多研究工作圍繞如何自動生成攻擊圖展開，取得了豐富的成果，現已經有不少工具能夠自動產生攻擊圖。本文基于獲得目標網絡攻擊圖的前提，提出種入侵檢測關聯模型(exploit queue graph,EQG)以及相關警報關聯算法，能有限免疫慢攻擊和注入垃圾攻擊。

攻擊圖描述了關于網絡連接和漏洞間關系的知識。目前，攻擊圖的表示方法不一，每種方法各有特點。一般來說，攻擊圖可以表示為有兩種頂點類型的有向圖，類型一表示exploit，圖示為矩形；類型二表示security condition，圖示為矩形。本文中，exploit可以表示為(hs,hm,hd,v)，意思是從主機hs經過中間主機hm利用目標主機hd上的v漏洞，如果沒有中間主機，則表示為(hs,hd,v)。本機上的漏洞利用表示為(h,v)。而security condition表示為(h,d,c)，意思是源主機與目標主機之間存在條件c，如果只涉及一臺主機，則表示為(h,c)，例如c可以表示兩臺主機之間要存在無防火墻的鏈接或者一臺主機上需要開啟ftp服務。Exploit與condition之間存在兩種有向邊。一種是從exploit指向condition，表示蘊含關系。第二種是從condition指向exploit，表示需求關系。其中，蘊含關系是析取的，需求關系是合取的。

定義1 給定exploit的集合E, condition的集合C，需求關系Rr ?C×E，蘊含關系Ri?E×C，則稱有向圖G(E∪C,Rr∪Ri)為一攻擊圖(E∪C i為頂點集合，Rr∪Ri為邊集)。

本文方法以安全漏洞為中心，首先將接受到的報警映射為exploit，然后在利用攻擊圖表示的知識進行關聯。為了將報警映射為exploit，我們需要利用域知識將報警的事件類型屬性映射為exploit的漏洞屬性，例如Snort識別符與Nessus識別符之間的對應關系。為簡單起見，我們用A2P( )表示從報警集到exploit集的映射。

基于目標網絡的知識，以漏洞為中心的關聯途徑可以有效減輕干擾性警報的負面影響。例如，某攻擊者對Windows主機發動本應該是針對 Unix系統的攻擊，這種情況就會被忽略，而不會進行沒有必要的關聯。

定義2 G(E∪C, Rr∪Ri)為一攻擊圖，其中E ={ei| 1 ≤i≤n}，

C = {ci| 1 ≤ i ≤ m}，Rr?C×E，and Ri? E ×C.

For k=1, 2… n

——BFSR(k)表示從ek出發對G順各有向邊進行廣度優先進行遍歷而得到的邊及集合。

——BFS(k)表示從ek出發對G逆各有向邊進行廣度優先進行遍歷而得到的邊集合。

攻擊圖G對應的EQG包含以下部件

ES= = {Qi| 1 ≤ i ≤ n}, n個長度為一的exploit隊列的集合

CS == {vi|1 ≤ i ≤ m} , m個表示條件的變量的集合第k層向后指針集合

BLk= {＜Qj,vi＞| (ci, ej)∈ BFS(k)}∪{＜vi,Qj＞ | (ej, ci) ∈BFS(k)}

第k層向前指針集合

FLk={＜vi,Qj＞| (ci,ej)∈BFSR(k)}∪{＜Qj,vi＞ | (ej,ci)∈

圖2 一個簡單攻擊圖對應的EQG示例

2 利用EQG進行警報關聯及其預測

直觀來說，報警序列依次流過EQG，我們通過搜索EQG來收集關聯結果。具體過程：當新接收到一個警報，通過A2E()映射為對應的exploit，然后讓新警報進入此exploit隊列，由于隊列長度為一，若原本就有警報在隊列中，則必須將其出隊。接著在對應的層中搜索，進行關聯，得到一個結果圖。結果圖Gr有一個頂點集 V，兩個邊集 Er和 El。Er的邊表示警報間的關聯，而 El中的邊表示和同一 exploit匹配的警報間的時間順序關系。

關聯算法Procedure EQG Alert Correlation

Input: A queue graph Qgwith n queues and m variables, the initial result graph Gr(V,Er∪El), and an alert anewsatisfying A2E(anew) = ei(1 ≤ i ≤ n)

Output: The updated result graph Gr(V,Er∪El)

Method:

（1）Insert anewinto V

（2）If Qicontains an alert aold

Insert edge (aold,anew) into El

Dequeue aoldfrom Qi

（3）Enqueue anewinto Qi

（4）For each Qj(1 ≤ j ≤ n) satisfying ＜Qi, vk＞ ∈BLi∧＜vk,Qj＞ ∈BLi(1 ≤ k ≤ m)

If Qjcontains an alert aj

Insert (aj,anew) into Er

（5）Return Gr(V,Er∪El)

以下指出EQG模型以及關聯算法的優越性。

（1）處理每個新警報的時間復雜度是O(m + n)；

（2）算法的空間復雜度為O(n(n + m))；

（3）該方法對放慢攻擊以及注入垃圾攻擊免疫。

預測過程類似于關聯過程，只不過搜索的方向不同。它是從最新報警出發，順 FLi中的指針對攻擊圖進行局部的寬度優先搜索。預測過程的結果是非空集合Con1,Con2,…的序若c屬于Coni，則表示攻擊者從當前狀態到滿足條件c必須至少要進行i步exploit。

3 應用

以本文算法為基礎的警報關聯程序，作為為中南大學鐵道學院網絡中心智能網絡管理系統的子系統，為網絡管理人員提供了大量有效的參考信息。

4 總結

本文提出的基于入侵圖警報關聯以預測方法在時間復雜度和空間復雜度方面較之傳統方法有明顯優勢。而且可以有效的免疫放慢攻擊和諸如垃圾攻擊。但不足之處在于該方法沒有考慮到報警可能來自不同的傳感器，以及網絡延遲的存在，警報流存在失序的情況。在這種情況下，無法準確關聯相關警報。這是下一步繼續研究的目標。

[1]P. Ning and D. Xu. Learning attack strategies from intrusion alerts.In Proceedings of the 10thACM Conference on Computer and Communications Security (CCS’03).2003.

[2]R.Lippmann and K.Ingols.An annotated review of past papers on attack graphs. Technical report, MIT Lincoln Laboratory,March 2005.

[3]S. Jajodia, S. Noel, and B. O’Berry. Topological analysis of network attack vulnerability. In V. Kumar, J. Srivastava, and A.Lazarevic, editors,Managing Cyber Threats: Issues, Approaches and Challenges.Kluwer Academic Publisher.2003.