基于攻击图的复合入侵关联及预测方法

肖琳琳 王晓辉 李杰

中南大学信息科学与工程学院 湖南 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.