基于扩展K均值算法的入侵检测模型

摘要：该文提出了一个基于扩展K均值算法的入侵检测模型。首先介绍了入侵检测研究的发展概况以及K均值算法及其扩展版本。接着描述了基于扩展K均值算法的入侵检测模型。最后，通过实验仿真利用KDD Cup1999数据集对模型的效能进行了验证。

关键词：入侵检测；网络安全；扩展K均值算法；数据挖掘

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2013）14-3267-03

保障计算机网络的安全无论对于维护国家正常的经济秩序还是对于维护广大因特网用户的隐私都是十分重要的。入侵检测是通过统计与分析系统中的各项参数值来判断系统是否被入侵的一种技术，是网络安全研究领域的一个热门。

可以把入侵检测看成是一个分类问题——将搜集的数据进行分类：什么样的数据代表系统正常，什么样的数据代表系统被监视与探测，什么样的数据代表系统遭受拒绝服务攻击，什么样的数据代表系统中发生非法提权行为等。Anderson【1】提出了入侵检测的概念。Forrest【2】等人把入侵检测和生物免疫进行类比，区分“自我”（正常）和“非自我”（不正常）。W.Lee【3】探讨了入侵检测系统利用数据挖掘方法的实现。以上方法都需要完备的审计数据才能达到比较高的性能，并且训练时间较长。

将扩展的K均值算法应用到入侵检测中，可以克服上述缺点。该文首先介绍了K均值算法及其扩展版本，然后描述了基于扩展K均值算法的入侵检测模型，最后通过实验仿真用KDD Cup1999数据集详细讨论了模型的工作过程，并对模型的效能进行了验证。

1 算法

1.2 K均值算法

K均值算法的基本思路是首先随机选取K个数据当做初始聚类中心，然后计算其他每个数据到每个聚类中心的距离，把数据归到与他最近的聚类中心的聚类中；对生成的聚类重新计算中心，相邻两次计算的聚类中心如果相同，则说明数据的聚类结束。否则进入下一次迭代。流程如下：

输入：聚类的个数k和n个对象的数据集

1.3 K均值算法的扩展

本文中对K均值算法进行了两方面的扩展，第一是对聚类结果进行层次聚类，生成一个聚类树。第二是给K均值算法添加分类功能。此扩展算法只适用于训练数据都已被标记分类的情况。

1.3.1 聚类树的生成

对于一次聚类而言，它的结果包含了多个划分，每个划分表示一个子类。每个子类中可能只含有一种类别的数据，也可能包含多种类别的数据。对于后一种情况而言，子类中包含干扰数据，用一种类别来对该子类进行最终标记并不完善。因此判断一个子类是否可以代表一种类别，是否需要对该子类进行再聚类，需要引入聚类精度的概念。

聚类精度的计算步骤如下：

1.3.2 数据匹配分类

为待检验数据预测类别的过程实际上就是在聚类树中为这条待检验数据寻找距离最近的节点的过程。从聚类树的根节点开始，不断地向下寻找距离最近的节点。具体步骤如下：

1）判断当前节点是否为叶子节点，若是，则当前节点的类别即是待检验数据的类别；否则，继续下面的步骤。

2）计算出当前节点与待检验数据之间的距离MinDistance。

3）判断当前节点是否有孩子节点，若有，继续下面的步骤；否则跳到第（7）步。

4）在当前节点的孩子节点中找出距离最近的节点，记为TempNode。

5）计算TempNode与待检验数据之间的距离TempDistance。

6）将MinDistance的值更新为TempDistance，并将TempNode设置为当前节点，然后跳至第（3）步。

7）当前节点的类别就是待检验数据的类别。

2 基于扩展K均值算法的入侵检测模型

数据预处理的作用是对数据进行清洗和变换。由于K均值算法只能对数值型维数相同的向量进行分类，而原始数据中的数据属性可能不是数字类型的，所以必须转换。整个模型的工作过程分为两大阶段：在训练阶段，根据已经标记好的数据来生成聚类树。在检测阶段，通过分类器对待检测数据进行分类，最后将分类结果输入数据库中。

3 实验仿真

本文选用KDD Cup1999数据集进行仿真。此数据集是ACM 第三届KDD竞赛所用数据集。该数据集通过记录一个模拟的军事网络环境下的9周的局域网原始TCP dump数据，生成了大约700万条连接记录。此数据集分为两部分。训练数据集部分用于提取数据特征，生成检测模型；测试数据集部分用于验证模型的效能。

KDD Cup199910%数据集对每一条连接记录都进行了分类（label）。所有记录分为正常（normal）与攻击（attack）两大类，其中攻击又可以进一步分为以下4种类型：

1）DOS：拒绝服务攻击，如SYN Flood攻击。

2）R2L：来自于远程主机的非法入侵，如猜测密码。

3）U2R：非法获得本地主机的超级用户权限。

4）Probing：监视与探测，即对本地系统各种信息的收集与扫描。

除了分为以上4种类型以外，KDD Cup1999数据集中的10%数据集的每条记录还包含41项属性。该文选择下文所述的18项属性。

3.1 属性选择与预处理

3.2 数据样本

我们选用KDD Cup1999数据集中kddcup.data_10_percent.gz文件中的数据作为训练数据集，corrected.gz文件中的数据作为测试数据集。训练数据集包含23种攻击行为（其中正常数据包也算为一种攻击类型），测试数据集包含38种。

3.3 仿真结果

参考文献：

[1] Anderson J Puter Security Threat Monitoring and Surveillance[M].Fort Washington，PA：James P.Anderson Co.，1980：6-7.

[2] Forrest S， Perrelason A S， Allen L， Cherukur R. Self_Nonself discrimination in a computer[C]//Rushby J， Meadows C.Proceedings of the 1994 IEEE Symposium on Research in Security and Privacy. Oakland， CA： IEEE Computer Society Press，1994：202-212.

[3] Lee W， Stolfo S J. A data mining framework for building intrusion detection model[M]//Gong L， Reiter M K.Proceedings of the 1999 IEEE Symposium on Security and Privacy. Oakland， CA： IEEE Computer Society Press，1999：120-132.

[4] Dorothy E.Denning. An intrusion detection model. IEEE Transactions on Sonware Engineering， 1987，SE-13（2）：222-232.

[5] Heberlein L T， Dias G V， Levitt K N， et al. A network security monitor[C].IEEE Symposium on Research in Security and Privacy，1990.

[6] Ghosh A K， Michael C， Schatz M. A real-time intrusion detection system based on learning program behavior[M]//Debar H， Wu SF.Recent Advances in Intrusion Detection （RAID 2000）. Toulouse： Spinger-Verlag， 2000：93-109.