摘  要： 大量的入侵检测警报使得IDS的功能无法得到有效发挥。本文用面向对象属性的归纳方法实现概念聚类算法，并对其改进后应用到入侵检测警报研究中，以减少误警数量。
关键词： 入侵检测警报  概念聚类  面向属性的归纳算法

　　入侵检测是一种新的能保护计算机系统的有效技术。在该技术中，入侵检测系统（IDS）监视并分析发生在计算机网络系统中的事件。当IDS检测到发生违反安全的事件时，它就触发警报，然后通过对警报进行处理来增强网络安全性。 然而对这些警报进行处理并采用相应的防御措施是一件很困难的工作。实际上，不少研究者都发现，被触发的成千上万的警报中,有99％的警报是误警。误警使得网络分析员不堪重负，而真正的攻击隐藏在大量误警中，很难从中识别。
1  相关工作
有人使用关联分析方法挖掘警报，然后丢弃与“正常模式”一致的警报，但这项工作没有考虑丢失有用警报的可能[1]。此外，还可以使用序列模式分析方法挖掘警报来指导构造用户自定义过滤器规则[2]。
警报相关性[3]的思想是设法将警报分类，以使同类别的现象引发相同的警报。可以使用数据挖掘技术从手工标志的训练数据实例中学习相关性规则。该方法假定存在一个人类专家知道这些相关性规则，而机器能从专家处学到这些规则。
本文将讨论如何把概念聚类用于警报处理。聚类分析与相关性分析的根本不同在于：在相关性分析中分析者知道这些相关性规则，而聚类中分析者不需要这些先验知识。为了更好地描述问题，下面给出本文需要用到的一些概念。
2  警报处理问题
2.1 定  义
定义1  警报、警报属性及警报属性值：当IDS认为发生安全入侵时就触发警报。用笛卡尔集Dom(A₁)×Dom(A₂)×……Dom(A_n)来表示警报模型。其中{A₁，A₂，……，A_n}是一系列警报属性，Dom(A_i)是警报属性Ai的值域(即Ai的取值范围)。警报属性是指能体现警报本质的特征，例如警报源地址、警报目的地址、警报类型和时间戳等。其中把一个警报a的Ai属性值表示为a.A_i。
定义2  警报根源：警报根源是导致重复并频繁触发大量警报的根源。
定义3  警报属性概化值：属性概化值是一个概念性的名称，能代表Dom(A_i)中一系列A_i属性值。例如，FTP属性值能代表一系列提供FTP服务的主机IP地址。
2.2 警报特征
由于网络组件之间相关性很强，一个组件的错误会导致很多与其相连的组件报错，从而触发大量警报。通常这些错误会导致90%以上的警报，而这些警报不是真正意义上的入侵。这类网络错误就是警报根源。这类警报具有很强的相似性和重复性。
2.3 减少警报的方法
要减少警报就要减少警报的根源。但是一般很难控制或消除警报根源。因此可以通过定制过滤规则去自动抛弃警报。
本文利用数据挖掘技术来发现警报中误警的特征，然后将这些特征提供给网络安全专家进行警报根源分析，并采取相应的解决警报根源的措施，以消除相应的误警。对那些无法消除的警报根源，则设计过滤规则过滤误警。由于误警大部分都是重复发生的，而且频率很高，因此假定网络上发生入侵是小概率事件，则所有频繁发生的警报都是误警。
3  概念聚类
　　概念聚类是一种机器学习方法。它不仅能产生基于某种度量的分类，而且能为每种类别找出有意义的描述[4]。聚类的目的是把目标分类，以区分不同聚类中的成员。概念聚类有2个重要优点：(1)聚类的分层结构由领域知识得到。(2)概念聚类特别擅长于处理像IP地址、端口地址这样的分类属性。
4  面向属性的归纳
4.1 面向属性的归纳的描述
面向属性的归纳(Attribute-Oriented Induction，AOI)是一种面向关系数据库查询的、基于概化的、联机的数据分析处理技术，是用于数据库的知识发现方法。其基本思想是：先使用关系数据库查询并收集与任务相关的数据；然后，通过考察与任务相关数据中每个属性的不同值的个数进行概化。概化通过属性删除或属性概化来实现。
4.2 面向属性的归纳与概念聚类的关系
只要给面向属性的归纳赋予特定的概念描述语言，它就可以被看成是一种概念聚类方法。面向属性的归纳表现出的这种性质，一方面是由于概念聚类具有通用性，另一方面归功于对概念聚类描述语言的成功选择。
5  使用概念聚类处理入侵检测警报
本文使用概念聚类处理入侵检测警报，然后根据挖掘出的结果推导出过滤规则，以减少警报的误警率。
5.1 使用AOI算法处理入侵检测警报
已知警报数据库T（{A₁，A₂，……A_n，计数值C})、各属性的概化分层图和各个属性Ai相应的阀值f_i后，可以按照下面的算法进行聚类：

　　假定根据领域知识得到地址和端口的概化分层图分别如图1和图2所示，将AOI算法应用于入侵检测警报处理过程的示例数据如表1所示。

设阀值f₁=f₂=f₃=f₄=15，根据AOI算法进行处理的过程如下：
(1)扫描所有属性。若发现会话id属性没有相应的概化分层图而且存在大量不同值，则删除该属性。本算法中不考虑计数值C的属性，将其删除。
(2)考虑源地址属性。显然不同警报数超过阀值f₁。把ip1概化为其上层属性值FTP，地址A1到地址Z1分别概化为A网段到Z网段。继续考虑源地址属性，发现仍然不够抽象，则继续概化。把FTP概化为本网地址，A网段到Z网段概化为外网地址。最后只剩下本网地址和外网地址这2个属性值没超过阀值f1。此时，源地址属性已经充分概化。
(3)考虑目的地址属性。执行方法类似。同理处理源端口和目的端口属性，直到所有属性都达到概化需要。
(4)结束。最后得到的概化结果为：(本网地址，本网地址，低端端口，高端端口)、(本网地址，外网地址，低端端口，高端端口)、(外网地址，本网地址，高端端口，高端端口)。显然，该结果被过度概化，丢失了很多重要细节。由这样的结果很难推出有意义的过滤规则。实际上，希望能获得形如(ip1，ip3，21，3500)、(ip1，外网地址，21，高端端口)和(外网地址，ip3，3500，高端端口)的结果。因为它们更加具体并且信息更多，有助于寻找产生警报的根源和推导出有意义的过滤规则。
5.2 改进的AOI算法
应用传统AOI算法而产生过度概化的结果有2个原因：(1)没有设置有效的概化终止控制条件。(2)一个属性概化成功后，在对另一个属性概化前未消除前一个属性概化过程中的影响，导致第二个属性概化时有积累效应。
为此，提出增设计数值属性，并设定min-value变量为终止控制条件。同时，在一个属性概化成功且处理下一个属性之前，先将所有属性还原为初始状态，以消除前一属性概化过程产生的影响。
此外，传统AOI算法没有规定属性概化的先后顺序，下面用函数来决定如何选择待概化的属性：
F(A_i)＝max{f_i(v_j) | v_j∈Dom(A_i)且j=1，2，……n}
其中，f_i(v_j)表示数据库中Ai属性的属性值为v_j的所有警报的计数值总和，A_i属性的每个不同的v_j属性值都有一个对应的f_i(v_j)值。
这样，得到改进后的AOI算法如下。
T′=T/*为数据记录保留一个副本，以便未来执行恢复操作*/
For(T′中每个警报a)
  　　　　a.C=1；/*初始化，设每个警报的计数值C为1*/
    For（每个警报属性 A_i）
          删除不能概化的属性；
    While（T′中警报适合概化） Do
         使用启发式算法选择合适的属性Ai；
    For（T′中每个警报a）
    a.A_i=the father(a.A_i)；/*对属性执行概化操作*/
    For（T′中任意警报a₁和a₂）
         If (a₁=a₂)
            a1.C=a₁.C+a₂.C；
    delete a2；/*合并相同属性*/
    If （存在合适的概化警报）
            提交合适的概化警报给用户；
从T′中删除提交的概化警报；
    for (T′中每个警报a)
            a=T.a；/*将剩余警报恢复为未概化状态*/
用表1所示的示例数据再次运行改进后的AOI算法，得到下面3个概化警报：
(IP1，IP3，21，3500，500）、（IP1，外网地址，21，高端端口，28）和（外网地址，IP3，高端端口，3500，26）。
6  结  论
　　本文用面向属性归纳方法实现概念聚类，并通过对传统AOI算法的改进使得概化结果更加具体，有助于安全人员分析误警根源，从而减轻人工分析的代价。
参考文献
1 Manganaris S，Christensen M，Zerkle D et al.A Data Mining Analysis of RTID Alarms.Computer Networks，2000；34(4)
2 Clifton C，Gengo G.Developing Custom Intrusion Detection  Filters Using Data Mining.In：Military Communications Intl Symposium(MILCOM2000)，2000
3 Debar H，Wespi A.Aggregation and Correlation of  Intrusion-Detection Alerts.In：Proc of the 4th Intl Symposium on Recent Advances in Intrusion Detection(RAID)，2001
4 Pitt L.Reinke E.Criteria for Polynomial-time(conceptual) Clustering.Machine Learning，1998；(2)
5 Biswas G.ITERATE：A Conceptual Clustering Algorithm for Data Mining.IEEE Transactions on Systems，1998；28(2)