基于谱聚类的网络入侵检测算法研究

摘 要： 针对传统聚类分析算法在入侵检测中存在的问题，提出基于谱聚类的入侵检测算法。阐述入侵检测与聚类分析相结合的优势，并分析几种入侵检测系统中常用的聚类方法。谱聚类算法可以在任意形状的样本空间上聚类，并能获得全局最优解。将谱聚类用在经典的入侵检测数据集KDD CUP99中，实验结果表明，与基于K-means的入侵检测方法相比，该方法有较高的检测率和较低的误检率。

关键词： 谱聚类； 入侵检测； K-means算法； KDD CUP99

中图分类号：TP393 文献标志码：A 文章编号：1006-8228（2016）06-40-03

Abstract： Aiming at the problem of traditional clustering analysis algorithm in intrusion detection， an intrusion detection algorithm based on spectral clustering is proposed. The advantages of combining intrusion detection and cluster analysis are described， and the commonly used clustering methods in several intrusion detection systems are analyzed. Spectral clustering algorithm can cluster on any shape of the sample space， and can obtain a global optimization solution. Using spectral clustering algorithm to the classic intrusion detection data set KDD CUP99， and comparing to the intrusion detection method based on K-means， the experiment results show that this algorithm has higher detection rate and lower false detection rate.

Key words： spectral clustering； intrusion detection； K-means algorithm； KDD CUP99

0 引言

随着计算机网络的普及和黑客技术的发展，网络攻击和安全问题越来越严峻。为了实时有效地发现攻击行为以保证网络正常运行，继防火墙、信息加密等传统安全保护措施后，入侵检测（Intrusion Detection System，IDS）作为一种新的安全防护手段应运而生[1]。入侵检测是对入侵行为的发觉，它通过收集计算机网络或计算机系统中若干关键点的信息并对其进行分析，从中发现网络或系统中是否有违反安全策略的行为和被攻击的迹象，对网络或系统中非授权的，或威胁到系统安全，又或存在攻击的行为作出响应。

网络入侵检测方法一般分为误用检测和异常检测两类。误用检测根据已知系统的安全漏洞和应用软件的弱点及其攻击行为特征，与审计数据进行匹配来判断入侵行为，它可以准确地检测已知的入侵行为，具有检测率高、检测效果稳定、误检率低的特点，但不能发现新的入侵行为，漏报率较高。而异常检测是基于行为的检测，其特点是通过对系统异常行为的检测来发现未知的攻击模式，不但能检测已知入侵，也能检测未知入侵。异常检测对系统的依赖性相对较小，可移植性强，其难点在于正常行为模型库的建立，且误检率较高。为了解决传统入侵检测系统的缺陷，研究者将异常检测与数据挖掘的聚类分析方法相结合来提高检测精确度和检测性能。

本文提出基于谱聚类（Spectral Clustering，SC）的异常检测算法，实验采用部分KDD CUP99的数据集，并与K-Means算法相比较，其结果表明，所提出的算法比传统的聚类检测算法有更高的检测率和更低的误检率。

1 入侵检测系统中常用的聚类算法

数据挖掘也称数据库中知识发现（knowledge discovery in database，KDD），通过对海量的安全审计数据进行智能化的处理，从中提取系统安全相关的行为特征，从而识别出入侵行为。

聚类，就是按照事物的某些特征，把事物分成若干类或簇，使得在同一个类内的对象之间最大程度相似，而不同类之间的对象最大程度不同。聚类是数据挖掘和机器学习领域中的一个研究热点，它可以对大量数据进行分析并将这些数据对象自动归类，适合用于异常检测。基于聚类分析的入侵检测技术是采用无参数的方法用向量表示事件流，再利用聚类算法将它们分为行为类。每一类都代表相似的活动或用户的行为，以辨别出正常和异常的行为[1]。

本文主要介绍K-means、模糊C均值（Fuzzy C-Means，FCM）聚类和谱聚类算法。

K-means算法最早被用到入侵检测系统中，且使用率较高。应用于异常检测的优点是算法简单、计算复杂性小，速度快，易达到入侵检测的实时性要求。但是，由于K-means采用随机法选取初始聚类中心，初值不同的情况下，可能会产生不同的聚类结果，将其应用于入侵检测系统中，算法的执行结果将会不稳定。并且，该算法基于梯度下降进行搜索常使算法陷入局部最优[2]。K-means算法的这两大缺陷极大地限制了其应用范围。

FCM算法也是目前应用广泛的一种聚类方法。根据客观事物间的不同特性、相似性和亲疏程度等，通过建立模糊相似关系对客观事物进行分类。和其他传统聚类算法一样，FCM算法用欧式距离度量数据对象之间的相似性，但只能对类球状聚类[3]。同K-means算法，FCM算法对初始值的选取依赖性也很大，对孤立点和噪音点敏感，使得其在异常检测中得到的结果不能满足要求。

相对于前两种聚类算法，谱聚类算法由给定的样本数据集定义一个描述数据点之间相似度的亲和矩阵，再计算矩阵的特征值和特征向量，最后选择合适的特征向量聚类不同的数据点[4]。谱聚类算法是一个判别式算法，其思想相对简单易于实现，且不受数据点维数的限制。谱聚类能对任意形状的样本空间聚类，并能获得全局最优解，非常适用于入侵检测中。

近年来上述算法的运用改善了入侵检测的性能，但也存在着不足之处。在实际的应用中，必须要根据数据类型、聚类的目的，以及具体的聚类应用情况等选择聚类算法。因此，选择合适的聚类算法应用于入侵检测是一项很具挑战性的工作。本文基于以上研究背景，将谱聚类算法应用于网络入侵检测系统中，以提高入侵检测的效率。

2 实验设置与结果

2.1 实验数据集

选择合适的数据训练集对于聚类结果有很大影响，网络异常检测系统中采用聚类算法的目的是为了建立正常行为模式匹配库。如果训练集太小，导致模式匹配库包含行为特征太少，匹配的未知行为过多，会降低检测效率；如果选择的训练集过大，会增加计算的时间复杂度以及空间复杂度。因此，选择合适的数据集对于模式匹配库的建立尤为重要。

本文实验数据采用了在第三届国际知识发现和数据挖掘工具竞赛上使用的KDD CUP99数据集，其提供了从模拟美国空军局域网上收集的9周时间的网络连接和系统审计数据，仿真各种用户类型、各种不同的网络流量和攻击手段。这些原始数据被分为两个部分：7周时间的训练数据大概包含5百万个网络连接记录；其余2周时间的测试数据大概包含2百万个网络连接记录。一个网络连接是指，在某个时间内由开始到结束的TCP数据包序列，并且在该时间内，数据在预定义的协议下（如TCP、UDP）从源IP地址到目的IP地址的传递。每个网络连接被标记为正常（normal）或异常（attack）。KDD CUP99数据集都采用相同的文本记录格式存储，每行表示一个记录，每条记录用一条连接中提取的41个特征（一共42个，未包括最后标注的攻击类型）[5]来描述，被细分为4大类共39种攻击类型，其中22种攻击类型出现在训练集中，另有17种未知攻击类型出现在测试集中[6]。所以，使用该数据集的实验更加接近真实的网络环境。

2.2 提取数据集

由于数据集过大，为了使之能适用于谱聚类算法，首先对KDD CUP99数据集做分块处理，以减少单次分析的数据量大小[7]。根据service属性特征（目标主机网络服务类型）将该数据集分为http、ftp、smtp和other四个部分，每个部分包含10%入侵数据。在这四个部分，http服务在数据集中所占的比例比较高，实验选取http服务的数据记录数略多于其他服务的记录数，数据记录一共为800条，正常和入侵数据的比例如表1。

2.3 数据处理

KDD CUP99数据集中的数据中存在连续变量和离散变量，根据本实验设计，需要将离散型变量做连续化的处理。一共7个离散型变量中，flag、land、logged_in、is_host_login和is_guest_login 5个属性特征均只包括两种状态：0或者1。因此，这里只用对提取的数据集的protocol_type（协议类型）和service（网络服务）特征转换成连续化特征变量，如表2和表3。为了在计算的时候不产生误差，还要确保每条记录间同一离散型特征之间的距离相等[8]。

接着用谱聚类的NJW算法对数据进行降维和归一化处理[8]，得到新的数据源。

2.4 实验结果及分析

将处理后得到的新数据源所获得的重要特征应用到谱聚类算法和传统的聚类算法K-means中，并进行比较。实验结果用检测率（DR）和误检率（Fdr）2个参数作为评价标准，既要保证较低的误检率，又要获得尽可能高的检测率。聚类结果如表3。

3 结束语

本文在经典的入侵检测KDD CUP99数据集上进行实验，采用基于谱聚类的异常检测算法，在选取的数据集中能达到较好的检测率和较低的误检率。相对于K-means算法，克服了随机选取初始聚类中心和容易受到局部最优解的缺陷[1]。在后续研究中，除了在真实环境下检验本实验方法的有效性，还将实验谱聚类算法与其他方法相结合用于异常检测中，提高聚类精度和速度。

参考文献（References）：

[1] 杜强，孙敏.基于改进聚类分析算法的入侵检测系统研究[J].

计算机工程与应用，2011.47（11）：106-108

[2] 李斌，王劲松，黄玮.一种大数据环境下的新聚类算法[J].计算

机科学，2015.42（12）：247-250

[3] 李玲俐.一种基于属性分解的FCM融合聚类算法[J].计算机

应用与软件，2013.30（8）：65-67

[4] 蔡晓妍，戴冠中，杨黎斌.谱聚类算法综述[J].计算机科学，

2008.35（7）：14-18

[5] 张新有，华燊，贾磊.入侵检测数据集KDDCUP99研究[J].计

算机工程与设计，2010.31（22）：4809-4812

[6] KDD CUP 99数据集[EB/OL].[2011-11-18]. http：//blog.

csdn.net/com_stu_zhang/article/details/6987632.

[7] 吴建胜，张文鹏，马垣.KDDCUP99数据集的数据分析研究[J].

计算机应用与软件，2014.31（11）：321-325

[8] 朱正伟.谱聚类研究及其在入侵检测中的应用[D].重庆大学，

2010.