一种改进聚类算法在入侵检测中的应用

开篇：润墨网以专业的文秘视角，为您筛选了一篇一种改进聚类算法在入侵检测中的应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

【 摘 要 】 本文首先介绍入侵检测系统的基本结构和研究情况，然后介绍了K-means聚类算法的目标函数、算法流程；在总结K-means聚类算法存在的问题的基础上，提出了一种改进的聚类算法。该算法为基于数据挖掘的入侵检测的设计提供了相关可操作的理论依据。最后，通过模拟实验，证明了改进算法的有效性。

【 关键词 】 数据挖掘；入侵检测；聚类算法

The Application of An Improved Clustering Algorithm in Intrusion Detection

Zhao Yun Gu Jian Zhang Xiao-xiao

（The Third Research Institute of Ministry of Public Security Shanghai 200031）

【 Abstract 】 In this paper， the basic structure and research situation of intrusion detection system are introduced firstly， and then the objective function and procedure of the K-means clustering algorithm are presented. Based on the summarized problems of K-means clustering algorithm， an improved clustering algorithm is proposed. The algorithm provides a related operable theoretical basis for intrusion detection design based on data mining. The simulated experiments prove the validity of the improved algorithm.

【 Keywords 】 data mining； intrusion detection； clustering algorithm

0 引言

由于计算机网络的广泛使用和网络之间信息传输量的急剧增长，入侵行为正在不断的扩大，随着时间的推移，攻击的手段和原理也越来越复杂，而攻击的工具却越来越自动化，使得攻击越来越自动化。普通的网民可以利用工具进行攻击，不需要依赖黑客。对网络安全工作提出了很大的挑战。

入侵检测技术是近20年来继防火墙、数据加密等传统安全机制之后出现的一种主动保护自己以免受黑客攻击的积极主动的安全防御技术。入侵检测系统（Intrusion Detection System，IDS）通过对入侵行为过程和特征的研究，使安全系统能够对入侵事件和入侵过程做出实时相应，它是一种随着当前网络状态变化而动态相应得安全防御手段，被认为是防火墙之后的第二道安全闸门。它在不影响网络性能的前提下对网络进行监测，从而提供对内部攻击、外部攻击和误操作的实时保护，并采取相应的防护手段，这些手段包括记录证据用于跟踪入侵者和灾难恢复、发出警报，甚至终止进程断开网络连接等。可是目前的入侵检测系统只是将抓取的数据包或者数据与已有的模式数据库做比较，采用目前的模式匹配方法对已经存在的攻击具有很高的检测效率和正确率，但对目前流行的

很多新的入侵攻击行为和手段却有很大的局限性，检测效率和正确率比较低. 因此利用数据挖掘技术不仅可以提高检测速度，减少手工操作的工作量，用来进行入侵检测，还将提高入侵检测的检测效率和准确性。数据挖掘技术能够从大量的数据中挖掘出有效的、新颖的具有潜在用途并最终可理解的格式。如何将数据挖掘技术应用到入侵检测领域，探索可行的有效的数据挖掘算法，解决入侵检测系统自适应性和高效性的瓶颈问题成为入侵检测领域一个重要的研究方向。

1 K-means算法研究

K-means聚类算法是由Steinhaus于1955年、Lloyd于1957年、Ball&Hall于1965年、McQueen于1967年分别在各自的不同的科学研究领域独立的提出。它是一套很典型的基于划分的聚类算法，由于其简单、计算复杂度小和快速收敛等优点，很多聚类任务都选择该经典算法。它采用距离作为评价相似性的指标，即如果两个对象的距离越近则其相似度就越大。该算法将相似的某些对象定义为簇。

算法描述如下：假设样本集是E，类C定义成E的一个非空子集，即C∈E且C=。每个类或簇就是满足下面两个条件的类或簇C1，C2，...，Ck的集合：

C1∪C2... ∪Ck=E （1）

Ci ∩Cj=，（对任意i≠j） （2）

由公式（1）可以知道，样本集E中的任何一个一定属于某一个类或簇。由条件2可以知道，样本集E中的任何一个最多中属于一个类或簇。由欧几里得距离（简称欧式距离）（Euclidean Distance），设X，Y为两个模式向量样本X=（x1，x2，...xn）T，Y=（y1，y2，...yn）T，则X，Y的欧几里得距离定义为公式：

D=| X-Y |=[（xi-yi）] （3）

显然D越小，X与Y越相似（D为n维空间中X与Y之间的距离）。由以上公式很容易推演到样本中反映个体间的距离的情形下，聚类准则函数的定义：设模式样本集为{X}={X1，X2，...Xn}，且模式样本集被分为c类，既S1，S2，...Sc。Mj是Sj的均值向量：

Mj=X，Nj=| Sj | （4）

其中Nj为Sj的样本数目，则可以定义聚类准则函数公式：

J=|| X-Mj ||2 （5）

J代表了所有类别中样本与均值之间的误差平方和，即样本与均值之间距离的和，所以取其极小值就是我们聚类的目标。

K-means聚类算法从一个初始的c类别划分开始，然后将各数据点指派到各个类别中，以减少总的距离平方和。因为K-means聚类算法中总的距离平方和随着类别个数c的增加而趋向于减少（当c=n时，J=0）。因此，总的距离平方和只能在某个确定的类别个数c下，取得最小值。

算法流程图如图1所示。

在K-means算法中K是事先给定的，这个K值的选定是非常难以估计的，很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是K-means算法的一个最大的不足，在实际中，K值是难以准确界定的，普通的用户不是数据分析专家或知识专家，并不知道采用什么样的K值聚类会对自己更有利。此外，无法确定聚类结果中哪些是正常的聚类，哪些是异常的聚类，并且只能处理连续型数值对象而不能处理离散型对象，如字符等。

针对入侵检测技术中的实际情况，网络数据包并不是所有属性值都是连续型数值，有些是离散型的，如协议名称，服务名称等，这些属性K-means无法直接处理，必须将其预处理转化成为数值型。

2 K-means算法的参数及其改进

针对上述K-means算法的不足，本文提出以下改进思路：网络数据报实时性无法预先确定聚类个数K的问题，提出一种定宽的聚类算法，该算法工作前需要设定一个参数聚类半径r，第一个聚类的中心以获取到的第一个数据包为中心。后续数据包到达后计算与各聚类中心的距离，若小于或者等于r，则将其归类到相应得聚类，并重新计算该聚类的中心。若距离大于r，则以该数据包作为一个新的聚类中心。每一个创建的聚类都分配一个编号作为标示。

针对聚类结果无法确定正常聚类与异常聚类的问题，我们将正常聚类和异常聚类分别放在正常聚类链表和异常聚类链表中，设定一个阀值，当聚类成员数目与所有成员比例大于或者等于时，表明它是一个正常聚类，此时将该聚类从异常聚类链表移到正常聚类链表中。最终形成正常的聚类链表作为网络正常行为模式供异常检测引擎使用。该思想的提出是基于以下两个前提：网络中正常数据的数量远远大于入侵数据：入侵数据与正常数据之间存在很大的差异。

针对传统K-means无法处理网络数据包中离散属性的问题，将离散属性转化为多个取值为0和1的数值属性（1表示出现，0表示没有出现），再利用K-means算法进行聚类分析。但该方法有两个局限性：离散属性取值个数多时，将导致转换时的计算代价和转换后的存储代价急剧增加；得到的对应均值没有实际意义，难以解释，针对这一问题，本文提出的算法利用离散属性值出现频率最高的值作为聚类中心的属性值，从而简化了预处理的过程，减小了算法复杂度以及计算和存储的开销。

改进后的K-means的异常检测算法，应用于异常检测工作步骤。

第一步：

输入：训练数据集T，聚类半径r；

输出：网络数据包行为模式聚类C1，C2，...Ck。

步骤：

1）对T进行标准化预处理；

2）初始时，聚类集合为空，读入第一个数据包T（1），以T（1）构造第一个聚类C1；

3）Repeat；

4）继续读入后续的T（i），i=1，2，3...计算其与每一个已有聚类的相似度，并选择最小相似度d（T（i），Cj）；

5）若d（T（i），Cj）≤r，将T（i）归类到C1，即T（i）∈Cj；重新计算Cj的聚类中心， Cj的成员数目count++；

6）若d（T（i），Cj）r，以T（i）创建一个新的聚类；

7）until无数据包的输入。

第二步：

输入：C1，C2，...Ck，阀值；

输出：正常聚类链表Lnormal，异常聚类链表Labnormal。

步骤：

1）若Cj中的成员数目与全部聚类成员比例大于或等于阀制，则Cj判断为正常类，将其移入正常聚类链表Lnormal；

否则Cj判断为异常类，将其移入异常聚类链表Labnormal。

以Lnormal构建正常行为模式后，在异常检测时，通过计算网络数据包与各正常聚类中的相似度来判断是正常数据还是异常数据。

3 实验测试

我们采用KDD CUP99的10%子集来测试算法的性能，将子集随机分割成P1和P2两个子集，其中P1含40459条记录（其中normal占96%），作为训练数据用来建立正常行为模式和异常行为模式，P2含有P1中没有出现的guess_word、imap、land、perl、ftpwrite、spy等攻击类型，作为测试数据用来检测算法性能。

分析输入参数对聚类结果的影响，我们采用异常检测引擎的误检率（FR）作为评价算法建立模型效果的度量指标，其定义如公式：

（6）

聚类半径r和阀值是改进K-means算法的两个重要参数，其值大小的设定直接影响聚类分析结果。聚类分析模块在对实验数据集进行聚类的时候要计算网络数据包与各聚类中心的距离，如果距离大于聚类半径r将新建一个聚类，否则将此数据包归到与之距离最近的聚类中。因此，聚类半径r会影响聚类效果，并且聚类半径r越大，产生的聚类个数越少，相反，聚类半径r越小，产生的聚类个数越多。聚类个数少，就意味着网络攻击数据被误判为正常数据的可能性大，而聚类个数多，聚类分析就越细化，网络攻击数据被误判为正常数据的可能性就相对越小。因此，聚类半径r对误检率有着直接的影响。

阀值是区分聚类后结果中网络正常行为模式类和异常行为模式类的重要指标。聚类分析模块算法进行时，只有聚类成员比例超过阀值，我们才判定其为正常行为模式类。因此，阀值越小，聚类分析后得到的网络正常行为模式类越多而异常行为模式类越少；相反，阀值越大，聚类分析后得到的网络正常行为模式类就越少，而异常行为模式类越多。同理可以推断，阀值越大，网络异常行为模式类就越难转化为正常行为模式类，攻击数据被误认为正常数据的可能性就越小；而阀值越小，网络异常行为模式类就越容易转化为正常行为模式类，攻击数据被误认为正常数据的可能性就越大。实验中，我们多次选取不同的r和，以验证算法的性能。

首先分析聚类半径r的影响（设定阀值=0.4）我们对实验训练数据进行多次聚类分析，设定阀值=0.4，变化聚类半径r的值，结果如表1所示。

从表1可以看出，聚类半径r对于异常检测率有着很大的影响。当r=1时的误检率为0，r=5时误检率为0.2%，r=10时为8.63%，r=20时为30.77%，当r=40时误检率已高达95.65%。由此可以得出结论，误检率随着聚类半径r的增大而增大，聚类半径r越大，误检率越大。高误检率意味着检测引擎误将攻击数据包当成正常数据包，将起丢弃不处理，这样容易造成漏警现象。

阀值的影响（设定聚类半径r=5）我们对实验数据多次进行聚类分析，设定聚类半径r=5，不断变化阀值的值；实验结果如表2所示。

可见实验结果和理论分析一致，综合上述实验结果及分析，可知聚类半径r和阀值对聚类结果及异常检测引擎的判断有着直接关系，产生深刻影响。在实际应用中，可根据具体情况调整聚类半径r和阀值的值以达到较好的聚类效果。一般而言，阀制可设置一个较大值，以避免一些异常数据包被误认为正常数据。我们在异常检测时宁肯牺牲计算量和硬件代价，也不愿因异常数据误判为正常数据造成漏警，而聚类半径r设置的值可相对小些。因此需综合考虑，不断调整这两个值才能达到更好的检测效果。

再分析输入参数对检测效率的影响，算法的检测时间直接说明了算法的检测效率。算法执行分两步，第一步根据训练数据集生成聚类，第二步将生成的聚类建立正常行为模式和异常行为模式进而进行异常检测。聚类半径r直接影响第一步生成聚类的簇数，而阀值则对正常行为模式和异常行为模式中的簇数产生影响。因此，两个参数对于算法的检测效率造成影响。

聚类半径r的影响（设定阀值=0.4）实验中我们设定=0.4，变化r的值，记录算法检测时间，结果如表3所示。

从表中可以看出，聚类半径r的大小与算法检测效率有着很重要的关系。R越大。算法检测时间越短，效率越高。反之，r越小，检测时间越长，效率也越低。

阀值的影响（设定聚类半径r=5）实验中我们设定r=5，变化的值，记录算法检测时间，结果如表4所示。

从表4可以看出，阀值半径的大小与算法检测效率有着很重要的关系。越大，算法检测时间越长，效率越低。相反，越小，检测时间越短，效率也越高。

综合上述实验结果及分析，聚类半径r和阀值对算法检测效率有着直接关系。检测时间随着聚类半径r的增大而减少，而随着阀值的增大而增加。由于聚类半径r增大会使得产生聚类的数量减少，减少了算法的运算量，因而检测速度提高。另一方面，当阀值增大时候，系统需要花更多时间来建立网络正常行为模型，因而检测速度变慢。在实际运用中，可根据具体情况选择合适的聚类半径和阀值的值。

4 结束语

入侵检测技术已成为当前研究的热点，然而传统的入侵检测系统存在着一些问题，如检测效率低，自适应性差等。数据挖掘技术能在海量审计数据中挖掘潜在的有用信息，它在入侵检测中的应用事入侵检测技术未来发展的方向之一。然而数据挖掘时一门通用的技术，并不是所有算法都适合于入侵检测，如何选取合适的数据挖掘算法，并将其应用于入侵检测中，以解决目前入侵检测的瓶颈问题，是入侵检测领域研究的一个方向。

参考文献

[1] Anil K J.Data clustering：50 years beyond K-Means[J].Pattern Recognition Letters，2010，31（8）：651-666.

[2] Huang Z.Extensions to the K-means A lgorithm for C lustering Large Data Sets with Categorical Values[J] .Data Mining and Knowledge Discovery ，1998，2：283-304.

[3] Zhang Y F，Mao J L An efficient clustering algorithm[J].Proceeding of the Second International Conference on Machine Learning and Cybernetics，Xian 2003：2-5.

[4] Mahajan M，Nimbor P，Varadarajan K.The planar K-means problem is NP-hard[J].lecture Notes in Computer Science，2009（5431）：274-285.

[5] Aloise D，Deshpande A，Hansen P，et al.NP-hardness of Euclidean sum-of-squares clustering [J].Machine Learning，2009，75（2）：245-248.

[6] Krishma K，Murty M N.Genetic K-means algorithm[J].IEEE Trans on System：Man，and Cybernetics ，Part B，1999，9（3）：433-439.

[7] Jain A K，Dubes R C.Algorithms for clustering data[M].NJ，USA：Prentice-Hall Inc，Upper saddle River，1998：320.

[8] Ramze R M，Ixlieveldt B P，Reiber J H.A new cluster validity index for the fuzzy K-means [J].Pattem RecognitionsLetters，1998 19：237-246.

[9] pena J M， Larranaga P.An empirical comparison of four initialization methods for the K-means algorithm[J].Pattern Recognition Letters，1999（20）：1027-1040.

基金项目：

由国家科技重大专项（2012ZX03002011）资助。

作者简介：

赵云（1983- ），男，河北人，硕士，助理工程师；研究和关注领域：信息安全。