一种基于孤立点挖掘的入侵检测技术
摘 要:探讨基于孤立点挖掘的异常检测的可行性,将基于2k-距离的孤立点挖掘方法应用到入侵检测中,并针对该方法无法很好地处理符号型属性数据的问题,采用编码映射方法对符号型数据进行处理,同时利用主成分分析来实现对编码映射后扩展的属性进行降维。详细阐述了具体实现方案,并通过仿真实验验证了该方法的可行性。
关键词: 入侵检测; 孤立点; 2k-距离; 编码映射; 主成分分析
中图分类号:TP391 文献标识码:A
文章编号:1004-373X(2010)11-0114-03
Intrusion Detection Method Based on Outlier Mining
YANG Cheng-cheng1, HUANG Bin2
(1. Chang’an University, Xi’an 710021, China; 2. Putian University, Putian 351100,China)
Abstract: The feasibility of the anomaly detection based on the outlier mining is discussed. The anomaly detection method is presented. The outlier detection method based on similar coefficient sum is applied to the intrusion detection. In order to overcome the poor ability of outlier detection techniques,the code mapping method is adopted to process sign type data. The dimension reduction of the mixed attribute expanded after code mappingwas realized by the principal components analysis (PCA). The feasibility of the method was verified with a simulation experiment.
Keywords: intrusion detection; outlier detection; 2k-distance; code mapping; principal component analysis
0 引 言
孤立点挖掘[1]是数据挖掘技术中一个重要的研究方向,其任务是从大量复杂的数据中挖掘出存在于小部分异常数据中的新颖的、与常规数据模式显著不同的数据模式。在统计学上,孤立点挖掘与聚类分析虽然在一定程度上是相似的,但两者还是有着本质的区别:聚类的目的在于寻找性质相同或相近的记录,并归为一个类,而孤立点挖掘的目的则是寻找那些与所有类别性质都不一样的记录。孤立点挖掘的往往是夹杂在大量高维数据中的异常数据,这些异常数据产生的行为可能带来较严重的后果,例如网络入侵中异常数据产生的行为会使得网络中的终端不能工作、且发生数据丢失和程序被改变等情况。
本文尝试将孤立点挖掘算法应用于入侵检测[2-3]中,将基于2k-距离的孤立点挖掘算法应用到入侵检测中。采用KDD99数据集[4]作为实验数据来分析该方案的可行性和检测性能。由于现有的孤立点挖掘方法大多是针对数值属性的,而在入侵检测中,数据包含着数字属性和符号属性,因此本文在数据预处理上采用对符号型属性进行编码映射与主成分分析相结合的方法,从而较好地解决了孤立点挖掘处理混合型的属性问题。
1 基于2k-距离的孤立点算法[5]
基于2k-距离的孤立点算法主要思想:首先计算数据集中每个对象p与所有其他对象之间的距离,选出离它最近k对象的距离,再从中选出最大的距离作为该点的k-距离,然后找出对象p的所有k距离邻居和所有2k距离邻居。下一步计算两个邻居范围内的数据对象个数之比的反比值DKC,最后,选出n个具有最大DKC值的对象作为孤立点。
定义1 对象p的k-距离,记做k-distance(p)
对于任何一个正数k,对象p的k-距离,即k-distance(p),被定义为d(p,o)。d(p,o)指的是p 与o 之间的欧氏距离,在对象p 与对象o 之间必须满足下面的条件。
(1) 至少有k个对象。o′∈D\\{p},满足d(p,o′) ≤d(p,o);
(2) 至多有k-1个对象。o′∈D\\{p},满足d(p,o′)
设数据集中的对象p,定义对象p的k-距离半径邻居为以p为圆心,以k-distance为半径的圆内所有数据对象,即:rkNB(p)=|q∈ DB|dist(p,q)≤k-distance,q≠pl
定义3 对象p的2k-距离半径邻居,记做r2kNB(p)
设数据集中的对象p,定义对象p的2k-距离半径邻居为以p为圆心,以2k-distance为半径的圆内所有数据对象,即:r2kNB(p)=|q∈DB|dist(p,q)≤2k-distance,q≠pl。
定义4 对象p的DKC值,记作DKC(p)
设数据集中的对象p,定义对象p的DKC值为两个圆内数据对象个数之比的反比值,即:
DKC(p)=r2kNB(p)rkNB(p)
DKC值表明了这样一个事实:高的DKC值说明对象p周围是一个稀疏的区域,这个对象很可能是一个孤立点;低的DKC值说明该对象周围是一个密集的区域,它不可能是孤立点。
2 基于孤立点挖掘的入侵检测算法
2.1 设计方案
基于2k-距离算法的形式化描述如下:
Inputs: Data objects,int k n
Outputs: outlier
(1) Compute all distances from p and select the first k-minninum distance from p
(2) select the max of the k-mininum distance as k-distance(p)
(3) Find k-distance neighborhoods of each object p
(4) Find 2k-distance neighborhoods of each object p
(5) Compute tdk of p tdk(p)=r2kNB(p)rkNB(p)
(6) select the top n with max tdk(p) as outlier
基于孤立点挖掘的入侵检测算法的步骤如下:
(1) 计算数据集中所有对象到对象p的距离,并选出其中最小的k个距离。
(2) 计算对象p的k-距离。
(3) 计算对象p的k-距离半径内的邻居数目。
(4) 计算对象p的2k-距离半径内的邻居数目。
(5) 计算对象p的DKC值。
(6) 计算出前n个最大DKC值的对象作为孤立点。
2.2 数据预处理
本文采用的数据集来自于KDD Cup 1999,该数据集包含了4大类入侵类型,即Probe,R2L,U2R和DoS。在分析过程中,从KDD99数据集中选取5个子数据集,每个包含10 000个正常记录和200个入侵记录,其中前4个子集中各含一类攻击,第5个子集中的入侵为混合型。这样处理的目的是:一方面可以检测孤立点挖掘对不同类型的入侵的检测效果;另一方面,由于每个数据子集中,入侵的数量远远小于正常的连接记录数量,从而使得实验能较为真实地反映网络行为中正常和异常行为的统计分布。
2.2.1 特征选取
KDD 数据集中不是每个属性都对检测结果有贡献,Srinivas Mukkamala等人利用支持向量机方法,并通过实验指出在KDD Cup 1999数据集中有13个属性最为重要,这13个属性是duration,srcbytes,dstbytes,urgent,count,srvcount,samesrvrate,dsthostcount,dsthostsrvcount,dsthostsamesrvrate,dsthostsamesrcportrate,protocoltype和service,其中既包含了数值型属性,也包含了符号型属性。这里也采用该特征选取方案。
2.2.2 混合型属性处理方案
在进行相似度计算之前需要对数据的属性值进行标准化[1],因为属性值之间采用不同的度量单位,其差别可能很大,因而对数据间距离的影响也不同,为了消除这种差别,必须采用一些规范化的方法。
(1) 标准化。令:
xy′ij=xij-xjsj, (i=1,2,…,n;j=1,2,…,n)
式中:xj=1n∑ni=1xij,sj=1n-1∑ni=1(xij-xj)2,xj和sj分别是U的第j维一个特征属性的均值和标准偏差。经过标准化变换后,各特征属性的均值为0,方差为1,但是xy′ij的取值范围很可能不在[0,1]区间,通过下面的正规化变换就可以把各个特征属性的取值范围落在[0,1]这个区间。
(2) 正规化。正规化变换的公式如下:
x′ij=xij-min1≤i≤n(xij)max1≤i≤n(xij)-min1≤i≤n(xij),
i=1,2,…,n;j=1,2,…,n
式中:分母相是数据矩阵第j列数据的极差,经过变换后,各变量的最小值为0,极差均为1,并且各特征属性的基点相同,变化范围也相等。
KDD数据集中不仅有数值型属性,还有符号型属性,对符号型属性处理的方法是对其进行编码映射,其做法如下:对于有m种不同取值的符号属性,用m比特对其进行编码,当且仅当属性取值为第i种值时,其码字中的第i比特为1,其余比特为0。例如,对属性protocoltype,有icmp,tcp,udp这3种取值,对每个取值可以做如表1所示编码。
表1 对符号属性的编码映射
码字100010001
ProtocoltypeIcmpTcpUdp
编码映射实际上是将原始的具有多种取值的符号类型属性转换为多个具有布尔取值的新属性。与直接数值映射法相比,编码映射保留了符号类型属性不同取值之间的本质特征,不会对学习算法造成误导。但对于取值可能很多的符号类型特征来说,要完成编码需要的比特位数也会很长。比如对于Service属性来说,其可能取值达六七十种。对如此多的可能取值做编码会带来输入矢量过大的问题。因此,本文在编码映射基础上引入了主成分分析(PCA)来达到降维[7]。经过PCA变换后,通常取2～3个主成分已经足够包含或者代表原有数据集的全部信息,因此可以利用足够代表原有数据全部信息的主成分来对原数据进行缩减。通过PCA分析,找出在权值上发生较大变化的变量项,保留这些属性作为PCA处理后新生成数据集的主干属性,从而得到一个全新的数据集,新生成的数据集较原先数据集在维度上大大降低,并能代表原先数据集的全部信息。
3 实验结果与分析
在实验中选取2.2.1节中的13个主要属性,对11个数值型属性进行标准化,并对符号型属性service和protocoltype进行编码映射后,再对其进行主成分分析,以得到一个新的数据集,最后使用基于相似度的孤立点挖掘算法对这个新数据集进行异常检测的结果如表2所示。
表2 基于2k-距离的孤立点挖掘实验结果
n
DoSR2LU2RProbe数据集
检测率误检率检测率误检率检测率误检率检测率误检率正常记录异常记录
18100%3.57%54.1%4.20%38.1%5.52%100%4.18%10 000200
19100%2.14%54.1%2.46%28.6%4.49%100%2.34%10 000200
20100%1.02%50%1.23%19.1%3.58%100%1.63%10 000200
210037.5%0.20%14.3%2.04%95%010 000200
220037.5%04.76%1.43%0010 000200
从实验结果可以看出,在n=20时,对四类攻击的检测率与误检率达到最好。当取n=20时,对第5个数据样本中混合攻击的检测率与误检率分别为90%和1.63%。此外,对于第5个混合攻击类型数据样本使用k-Means聚类方法进行异常检测实验,其中符号型属性同样采用本文的方法处理,通过聚类分析后得到的检测率与误检率分别为85.03%和3.01%。通过对比可知,在异常检测上,2k-距离比k-Means无论是在检测率,还是在误检率上效果都更好。
从上面给出的实验结果可以看出,孤立点挖掘技术对DoS和Probe入侵攻击的检测都取得了很高的检测率,但是对R2L和U2R入侵的检测效果不理想。这与估计的基本一致。经过分析主要有两个原因:
(1) R2L,U2R攻击,不像DoS和Probe那样在短时间内对一些主机发出很多连接,相反R2L和U2R攻击嵌入到包中,正常情况下只存在于一个连接中,故无法对其进行足够的特征刻画,需要寻找其他更有效的刻画特征;
(2) Probe类和DoS类攻击种类相对来说比较固定,而R2L,U2R类攻击种类比较多,且有很多U2R入侵是伪装合法用户身份进行攻击的,这就使得其特征与正常数据包比较类似,造成了算法检测的困难。而在KDD99的竞赛中,冠军方法对于这两种类型的入侵连接数据的检测率为13.2%和8.4%,这证明本文的方法是有其优越性的。
4 结 语
分析了基于孤立点挖掘的异常检测的可行性,将基于2k-距离的孤立点挖掘方法应用到入侵检测中,给出了该检测方法的流程和混合型属性的数据预处理方案,并通过在KDD99实验数据集进行孤立点挖掘仿真实验,证明该方法能够取得较高的检测率与较低的误检率,尤其是对DoS和Probe入侵攻击的检测都取得了令人满意的检测结果。
实验结果表明,孤立点挖掘技术可以用来完成异常检测工作,而且当异常数据要远小于正常数据时,其检测结果要优于基于聚类的异常检测技术,而在一般情况下,网络数据中异常和正常行为的统计分布基本符合孤立点挖掘的使用条件。当然,目前基于孤立点挖掘的异常检测技术还不能象诸如基于神经网络的异常检测技术那样完成实时在线检测,但这并不妨碍该技术在异常检测中的应用,比如做离线安全分析。如何进一步提高基于孤立点挖掘的异常检测性能指标,以及如何将基于孤立点挖掘应用到实际入侵检测中去将是下一步的主要研究方向。
参考文献
[1]HAN J, KAMBER M. Data mining: concepts and techniques[M]. San Fransisco: Morgan Kaufmann Publishers, 2000.
[2]罗敏,王丽娜.基于无监督聚类的入侵检测方法[J].电子学报,2003,31(11):1712-1716.
[3]PORTNOY L, ESKIN E, STOLFO S. Intrusion detection with unlabeled data using clustering\//ACM. Proceedings of ACM CSS Workshop on Data Mining Applied to Security (DMSA-2001). Philadelphia:ACM CSS, 2001: 156-166.
[4]BRUGGER Terry. KDD99 Cup dataset[DB/OL].\. Http://kdd.ics.uci.edu/ databases/kd- dcup99/kddcup99.html.1999 .
[5]姜灵敏.基于相似系数和检测孤立点的聚类算法[J].计算机工程,2003(7):183-185.
[6]MUKKAMALA S, JANOSKI G, SUNG AH. Intrusion detection using support vector machines and neural networks\. Proc. of the IEEE Int′l Joint Conf. on Neural Networks,2002:1702-1707.
[7]DUDA R O, HART P E, STORK D G. Pattern classification\. 2nd edition, Beijing: China Machine Press, 2004.
