基于图聚类的入侵检测算法

收稿日期:2011-01-13;修回日期:2011-03-03。

基金项目:江苏省自然科学基金资助项目（BK2007035）；中国矿业大学青年科技基金资助项目（0D061035;2007A047）。

作者简介:王国辉（1987-），男，黑龙江大兴安岭人，硕士研究生，主要研究方向：网络安全； 林果园（1975-），男，山东济宁人，副教授，主要研究方向：网络安全。

文章编号:1001-9081（2011）07-1898-03doi:10.3724/SP.J.1087.2011.01898

（中国矿业大学 计算机科学与技术学院，江苏 徐州 221116）

（）

摘 要:针对当前聚类算法仅依赖于初始聚类中心并且无法精确区别非凹形状类的不足，将图学习知识应用到聚类算法中，提出一种基于图聚类的入侵检测算法P-BFS。为得到较准确的分类模型，算法中引入了一种基于逼近函数的相似性度量方法。实验结果论证了图聚类思想应用于入侵检测系统的优越性；同时表明了，与K-means聚类算法相比，P-BFS图聚类算法具有较高的性能。

关键词:入侵检测；聚类分析；图聚类；逼近函数；聚类熵

中图分类号:TP393.09文献标志码:A

Intrusion detection method based on graph clustering algorithm

WANG Guo-hui, LIN Guo-yuan

（School of Computer Science and Technology, China University of Mining and Technology, Xuzhou Jiangsu 221116,China）

Abstract: Concerning the defects of the current clustering algorithm for its dependence only on the initial clustering center and failure in exactly distinguishing classes of non-concave shape, this paper applied the knowledge of group learning into the clustering algorithm and proposed the anomaly intrusion detection algorithm P-BFS based on graph clustering. In order to obtain more correct classification model, this algorithm introduced a measurement method of data points similarity based on the approximate function. The experimental results suggest the advantages of the application of the graph clustering algorithm in the intrusion detection system. In addition, it indicates that compared with the classical K-means clustering algorithm, P-BFS has better performance.

Key words: intrusion detection; clustering analysis; graph clustering; approximate function; clustering entropy

0 引言

聚类分析［1］是数据挖掘中一种常用的、典型的分析方法，特别适合于数据之间的内部关系探索。从数据处理的角度看入侵检测，入侵行为对应的数据可以看成异常数据，入侵检测问题可以看成一种特殊的异常数据挖掘问题。正常行为和入侵行为具有不同的特征，入侵行为偏离正常行为，正常行为与入侵行为对应的数据彼此分离。基于聚类的入侵检测最重要的特点是无监督性，可以检测未标记的审计数据，将相似的数据划分进同一个簇，不相似的数据划分进不同簇中，这就比有监督的检测方法更加优越。

基于聚类的入侵检测技术是现阶段入侵检测的主要研究内容之一。2001年，Portnoy等人将样本抽象为多维空间中的一个点，提出了基于距离度量的聚类算法并应用于入侵检测［2］；Lazarevic等人提出了使用孤立点分析来检测入侵的方法,该方法通过检查样本点到点间距离来决定哪些点属于孤立点［3］；中国科学院向继等人对无监督聚类算法用于入侵检测进行了实验研究分析［4］，取得了很好的效果。基于聚类的入侵检测技术具有很高的优越性和实用性，能够获得更加精确的检测结果。然而，当前聚类算法仅依赖于初始聚类中心并且无法精确区别非凹形状类。因此，本文将图学习知识应用到聚类算法中，获得一种更加灵活的聚类算法，并通过实验论证其优越性。

K均值（K-means）算法作为一种有效的聚类算法已经应用到入侵检测中，但存在以下不足［5］:1）簇的个数难以确定；2）聚类结果对初始值的选择较敏感；3）容易陷入局部最优解；4）对噪声和异常数据敏感；5）不能用于发现非凹形状的类，或具有各种不同大小的类。

近年来，许多科学家在类的相似性和分类模型的精确度量方面提出了一些有效的方法，其中最重要的方法之一就是特征属性的聚类变体――图聚类。2004年，Vempala引入图的谱信息，提出了基于聚类分割技术的图聚类方法［6］，由此引出Kernighan-Lin算法、传统的谱平分聚类算法等；Hartuv等人提出了一种基于图论的递归裁剪边的方法［7］；Newman将约减边介数的方法应用于基于统计特性的聚类算法，提出了GN算法和Newman快速算法［8］等。这些算法都证明了图聚类方法的有效性和高效性。因此，本文针对图聚类方法做了进一步的工作，将图学习知识应用到聚类算法中，提出了一种基于图聚类的入侵检测算法P-BFS。该算法具有时间复杂度低、聚类精度高、能将不同类型的数据聚集在分离的类中、得到更加准确的分类模型等特点。除此之外，该算法的聚类结果不受初始聚类中心的影响，比K-means算法有更高的全局搜索能力。

1 图聚类算法

1.1 图聚类定义

图聚类［9］指的是把图中相对连接紧密的节点及其相关的边分组形成一个可以用抽象节点表示的子图，子图内各节点具有较高的相似度，而子图之间各节点的相似度则相对较低。这样的子图就称为聚类图，这种聚类图可以极大地降低可视复杂度，增强图的可视性，有利于可视化分析和观测。

1.2 图聚类表示及相似性度量方法研究

聚类表示和相似性度量方法是聚类分析中最基础的问题，直接影响聚类的结果。本文提出了一种简单的图聚类表示方法，推广应用了基于函数逼近的相似性度量方法，使图聚类算法可以有效处理含复杂属性的数据。

1.2.1 图聚类表示模型

假设图节点Ai有n个特征属性，其中nc个分类属性和nm个数值属性。

把数据集A{A1,A2，…，Am}和连接节点对的边集E组成的无向加权图G（A，E）称为一个聚类图，权值W（eij）表示节点Ai与Aj的相似度。

给定聚类图Gi，Gi的摘要信息GSIi定义为：

GSIi{Ai，summary}

其中，Ai为聚类图Gi的聚类中心，summary为聚类图中节点相似度的平均值。

1.2.2 相似性度量方法

入侵检测系统所处理的数据包含复杂属性的非线性数据，这种数据通常隐含在多维特征空间中，被看成是多维空间中的一个点（向量），然后运用基于线性代数、几何学和统计学的算法对非线性数据进行高效分析。按照这种方式，本文提出了基于魏尔斯特拉斯定理［10］的相似性度量方法。

魏尔斯特拉斯定理 若函数f（x）在区间〖a,b〗上连续，则对任意正数ε,存在多项式g（x）,使对一切x∈〖a,b〗都有f（x）－g（x）

在〖a,b〗上的连续函数f（x）与g（x）,定义f（x）与g（x）的逼近度为：

f－gmaxa≤x≤bf（x）－g（x）

结合入侵检测系统处理数据的特点，本文选择逼近函数为n次代数多项式f（x）∑nk1a2kxk,其中系数ak为数据对象Ai的特征属性组成的n维向量，不失一般性取x∈〖－1,1〗。

给定数据对象Ai〖Ai1,Ai2…Ain〗与Aj〖Aj1,Aj2,…,Ajn〗，逼近函数分别为f（x）∑nk1A2ikxk与f ′（x）∑nk1A2jkxk，数据对象Ai与Aj的相似度定义为：

D（Ai,Aj）max－1≤x≤1f（x）－f′（x）

对象与类之间的相似性度量有多种定义，通常采用类平均连接规则，即用对象与类中所有样本对之间的平均相似度来度量对象与类之间的相似程度：

D（Ai,Gj）∑p∈GjD（Ai,p）

1.3 图聚类算法P-BFS描述

图聚类算法P-BFS属于分裂式层次聚类，从任一节点开始对图中各节点进行广度优先搜索，删除不符合条件节点的边，将图划分为多个聚类图。过程如下：

初始化时将相似度小于阈值r的节点两两相连，形成一个图（或图集）G0。

步骤1 若G0为空，退出；反之，从G0中选任一节点Ai（0≤i≤| G0|）作为聚类图Gj（j为聚类数，依次增加）的中心，G0G0-{Ai}，更新Gj的GSIj。

步骤2 以广度优先遍历方式对Ai进行遍历，得到遍历序列Gj′。

步骤3 若GGj′-{Ai}为空，转至步骤1。

步骤4 从G中选择节点Ak（0≤k≤|G|），GGj′-{Ak}，若GSIj中summary减小则将该节点加入聚类图Gj，G0G0-{Ak}，更新Gj的GSIj；反之，转至步骤3。

考虑到数据集较大的情况，采用抽样技术〖11〗来计算阈值r范围：

1）在数据集A中随机选择N对对象；

2）计算每对对象间的相似度；

3）计算2）中相似度的平均值EA和标准方差DA；

4）取r∈〖EA-2DA，EA+0.25DA〗。

2 实验结果分析与比较

2.1 实验数据

为评价图聚类算法P-BFS在入侵检测上的应用效果，选用基于数据挖掘的入侵检测技术研究中使用的KDDCup99网络入侵检测数据集进行实验。

KDDCup99数据集中每条数据共包含42个特征属性［12］，其中41个固定属性和1个类标识。标识用于表示该条数据为正常数据还是某个具体的攻击类型，如表1所示。

表1 KDDCup99数据集中攻击类型标识

随机抽取数据集中的三种不同类型数据，如下：

0,icmp,ecr_i,SF,1032,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,511,511,0.00,0.00,0.00,0.00,1.00,0.00,0.00,255,255,1.00,0.00,1.00,0.00,0.00,0.00,0.00,0.00,smurf

0,tcp,telnet,S0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,6,5,0.83,1.00,0.00,0.00,0.83,0.33,0.00,5,6,1.00,0.20,0.33,1.00,0.83,0.00,0.00,nepture

0,udp,domain_u,SF,29,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,1,0.00,0.00,0.00,0.00,0.50,1.00,0.00,10,3,0.30,0.30,0.30,0.00,0.00,0.00,0.00,0.00,normal

实验只采用包含正常数据的kddcup. data_10_percent中的“kdd-train-nor”数据集作为训练数据集，对包含入侵数据的“corrected”数据集进行检测。如果数据对象Ai加入到各聚类图中时summary均减小，则为入侵数据，反之为正常数据。

2.2 数据预处理

KDDCup99中每条数据记录包含分类属性和数值属性，相似性度量之前需做以下预处理：

对于分类属性，通常采用Ralambondarmy提出的一种处理方法，即将分类属性转化为多个取值为0到n的数值属性［13］（0到n分别表示不同的属性特征）。例如，数据记录的第二个特征属性（协议类型protocol_type）共有三种类型：TCP, UDP, ICMP，可根据以上方法转化为1-TCP、2-UDP、3-ICMP。

对于数值属性，不同的属性特征具有不同的度量标准，容易产生“大数吃小数”的问题，为此需对数据进行标准化处理：

Aij ′ ∑ni1Aij

其中Aij′为Aij数值标准化后的值。数据集中每条记录项的第11到第32条属性特征为数值型属性，所以i和j的值域为:1≤i≤n，11≤j≤n。

2.3 检测结果分析和算法性能评价

实验用Matlab 6.5语言编程环境，分别用K-means算法和P-BFS图聚类算法对训练集和检测数据集进行操作。

表2给出的是聚类数为50的入侵数据检测结果对比。

表2 对攻击数据的检测率对比

%

由表2知，P-BFS图聚类算法对已知攻击类型的平均检测率为73.43%，高于K-means算法的70.35%；对未知攻击类型的平均检测率为64.49%，远高于K-means算法的28.89%。

算法性能评价标准采用Boley提出的聚类熵［12］，聚类熵值越小，聚类效果越好。

假设数据集G被聚集k个类G{G1，G2，…，Gk}，n│Gi│表示类Gi中包含的数据个数，n│Ti，Gi│表示类Gi中包含数据类别Ti的数据个数。

对于类Gi，聚类熵e（Gi）定义为

e（Gi）－∑jlog

整体聚类熵定义为所有聚类熵的加权平均值：

e∑mi1nGie（Gi）

P-BFS图聚类算法性能评价如图1所示。

由图1知，当聚类个数n20时，其收敛相对平稳；P-BFS图聚类算法不存在随机选择初始类的缺陷，因此其聚类熵值低于K-means算法的聚类熵值，具有更好的聚类效果。

3 结语

P-BFS图聚类算法将图学习知识应用到聚类算法中，聚类效果不受初始类选择的影响，可用于发现非凹形状的类；算法中提出的相似性度量方法能够得到较准确的分类模型。对KDDCup99数据集进行的仿真实验表明，P-BFS图聚类算法在处理大规模数据时收敛效果更好，是一种有效的方法。其次，与K-means算法对攻击类型数据检测结果的对比体现出P-BFS图聚类算法应用于入侵检测系统是有效的。

图1 算法的收敛曲线

参考文献:

［1］ 肖敏,韩继军,肖德宝,等.基于聚类的入侵检测研究综述［J］.计算机应用，2008，28（6）: 34-38.

［2］ PORTNOY L, ESKIN E, STOLFO S J. Intrusion detection with unlabeled data using clustering［C］// Proceedings of ACM CSS Workshop on Data Mining Applied to Security. New York: ACM, 2001: 123-130.

［3］ ROSCOE A W. WOODCOCK J C P, WULF L. Non-interference through determinism〖J〗.Journal of Computer Security, 1996, 4（1）：27-54.

［4］ 向继,高能,荆继武.聚类算法在网络入侵检测中的应用［J］.计算机工程,2003,29（16）:48-185.

［5］ 王令剑,腾少华.聚类和时间序列分析在入侵检测中的应用［J］.计算机应用，2010, 30（3）:699-701.

［6］ KANNAN R, VEMPALA S, VETTA A. On clusterings: Good, bad and spectral ［J］. Journal of the ACM, 2004, 51（3）: 497-515.

［7］ HARTUV E, SHAMIR R. A clustering algorithm based on group connectivity ［J］.Information Processing Letters, 2000,76（4/5/6）: 175-181.

［8］ NEWMAN M E J. Fast algorithm for detecting community structure in networks ［J］. Physical Review E:Statistical, Nonlinear, and Soft Matter Physics,2004, 69（6）: 5-10.

［9］ FLAKE G W, TARJAN R E, TSIOUTSIOULIKLIS K. Graph clustering and minimum cut trees ［J］. Internet Mathematics, 2003, 1（4）: 355-378.

［10］ 蔺小林.计算方法［M］.西安:西安电子科技大学出版社，2009.

［11］ 蒋盛益，李庆华.聚类分析的差异性度量方法研究［J］.计算机工程与应用，2005,25（4）:146-149.

［12］ 王洁松，张小飞.KDDCup99网络入侵检测数据的分析和预处理［J］.科技信息, 2008（15）: 407-408.

［13］ BOLEY D L. Principal direction divisive partitioning［J］. Data Mining and Knowledge Discovery, 1998, 2（4）: 325-344.