基于数据挖掘的入侵检测

1、基于数据挖掘的入侵检测作者 Su-Yun Wu, Ester Yen摘要：随着网络的流行，网络攻击事件不断增加，攻击方法也是日新月异。所以信息安全问题在全世界成为了一个很重要的课题。如今，我们急切需要一种有效的检测、确认以及控制这种攻击的方法。本次研究主要比较机器学习方法的在入侵检测系统中的有效性，这其中还包括分类树和支持矢量机器，希望能给未来的入侵检测系统的建立提供参考。在对其他基于数据挖掘的入侵检测系统的相关工作进行对比之后，我们用不同攻击比率的正常数据样本计算出平均值，这也使我们以一个更高的精确率观测到现实中的数据。我们还比较了在受到4种不同攻击类型时系统的精确度、检测度、误警率。另外，

2、特别是在U2R型个R2L型攻击下，我们提出的方法的性能和表现要比KDD Winner好。关键字：分类树，支持向量机器，网络攻击，入侵检测系统（IDS）1.引言最近几年，随着网络和个人计算机的流行，网络的使用率也随之上升。这也大大的改变了人们的生活。很多人通过网络学习、创造、交流和购物。除了普通百姓、企业结构以及商业模型由于网络的出现而经历了转变之外，大型企业个政府为了实现管理的目的个效率，法展了许多依赖于网络的应用和服务项目；这些都是在新时代无法抵抗的趋势。然而，尽管网络带来了方便，但也随之带来了信息安全问题；例如：服务器被攻击或瘫痪，内部数据和信息被盗取等等。这些事情的发生，必将导致在财务和

3、商业信誉上的巨大损失。例如：在2000年，美国雅虎受到了Dos攻击，服务器瘫痪了近三个小时，一亿用户受到影响，至于损失已经打到无法计算。其他著名的商业网络，如CNN、eBay、A以及B等等都遭到过网络攻击。由于网络的便利性，接触到攻击知识和方法是很容易的。因此，当前，黑客们不需要拥有很广阔的专业知识。每一年，网络攻击事件都处在一个大幅度上升的趋势。通过从美国计算机紧急回应团队/合作中心（CERT/CC）（/）得到的数据.最近几年，每年的网络攻击事件都呈指数趋势增长；通过有关信息安全（.tw/）的报告, 网络攻击已经成为一种新的世界战争的武器。此项报告中，中国

4、军事黑客对攻击美国航空母舰战斗组已经开始了计划，目标是使之因为网络的故障而失去战斗能力。这个信息反映出我们当前急需一种有效的确认和控制网络攻击的方法。一般的企业采用防火墙来作为网络安全的第一道防线，但是防火墙的主要功能是监视网络的访问行为，它在检测网络攻击上能力是很有限的。所以，入侵检测系统，IDS一直被应用于检测网络的范围内，并且证明了IDS有给信息安全提供保护的能力。IDS表面上看来像网络监视和报警装置，一种观测和分析网络攻击是否发生，并在被攻击之前发送警告，然后执行一种相应的应付措施来降低巨大损失出现的可能的装置。另外，一些技术是基于种低误判率的模式检验，但这种基于模式的方法需要按周期升

5、级，所以它对未知的和更新的攻击方法没有足够的检测能力。最近，一些研究人员开始应用数据挖掘技术和机器学习技术。这种技术可以分析大量的数据并且在对未知攻击的检测能力上有很好的表现。尽管一些学者们已经取得了一些成就，但在这一方面还存在着很大的发展潜力。那么，在一个绝大多数状态相同的环境下，被应用于入侵检测的不同的机器学习方法的效率到底怎么样；除了提出过的方法，还有没有其他的方法？因此，本次研究将要比较被应用于入侵检测的不同机器学习方法的效率，包括分类树，支持向量机器等等，希望能为未来入侵检测系统的建立提供参考。研究的进程在图1中。2.背景回顾2.1 入侵检测系统的介绍入侵检测系统的概念第一次被提出是

6、在Anderson（1980）的一个技术报告中，他认为计算机审查机制应当可以灵活变化的且可以提供给计算机对内部危险和威胁一个安全的防御技术。他进一步提出统计学方法应该应用于分析用户的行为和监测违法接入资源系统的伪装者。在1987年，Dorothy提出一个入侵检测系统的模型：IDES（入侵检测专业系统），之后，入侵检测系统的概念逐渐被人们所知，并且他的论文他也成为了在入侵检测系统领域中一个非常重要的里程碑。随后，不同形式的入侵检测系统被人们提出，如：Discovery， Haystack， MIDAS， NADIR，和，等等（，）。入侵检测系统是监测和控制发生在计算机系统或网络系统中所有可能的情

7、况，分析与安全问题有关的信号，在发生安全问题事发送警告，并且通知相关体系采取措施以降低危险系数（，）。这个框架由三部分组成（，）：. 信息采集：数据采集：采集的数据源在位置上可以分为主机、网络、应用。. 分析引擎：分析引擎是能够分析是否出现了入侵现象。. 回应：在分析后采取行动，记录分析结果，发送实时警告，或调整入侵检测系统等等。图1.入侵检测系统的分类总的来说，对于入侵检测系统有两种分类方法：. 从数据来源上看，入侵检测系统包括基于主机和基于网络的。. 从不同的分析方法上来看，入侵检测系统包括滥用检测和异常检测。下面对这些入侵检测系统的优点和缺点做一下简要的介绍。（）按不同信息源分类：l （

8、基于主机的）（，）：这种数据是来源于主机的不同的活动记录，包括操作系统的审查记录，那个用系统日志，应用程序信息等等。拿操作系统为例，它的事件日志机制搜寻和收集三种不同形式的系统事件：操作系统事件，安全事件和应用事件；其中应用程序信息的例子如下：基于数据系统，服务器等等。下面是它的的优缺点（，）：优点： 它可以更精确的检测出主机是否被入侵。由于它的数据来源于审计记录系统和主机日志系统，与基于网络的入侵检测系统相比，它可以精确的判断出主机是否被网络攻击或入侵。 它可以检测到加密环境下的网络入侵, 那是因为从文件系统中来的数据以及被加密传输的网络数据是在主机中被破译的。所以，数据不会受到攻击。 它不

9、需要其他额外的硬件系统：它只需要把监控系统安装到特定的主机中，而不用额外的硬件设施。 缺点：. 较高的开支：追踪系统必须被安装在每一个主机中；由于主机不同，审查文件和日志形式也有所不同，所以每一个主机要求要有不同的入侵检测系统。. 它会影响监控系统对主机的检测效率：检测系统在监控时的评定会占用主机系统的资源空间。l （基于网络的入侵检测系统）（Bace，2002）：它的数据主要是收集了在网络信息流片段中的网络分类流，如：网络包。它的缺点和有点如下所述：优点：. 低开支：只有基于网络的入侵检测系统可以检测到所有在广域网中的攻击，它的花费仅仅是在这个手段上。. 它可以检测到一些基于主机的入侵检测系

10、统无法检测到的攻击：如Dos， Ddos。缺点：. 流量大，一些数据包可能丢失，且不能检测到在网络中所有的数据包。. 在大容量的网络中，它需要更快的CPU和更多的存储空间来分析大量的数据。. 它不能处理加密的数据包，同时也不能接收到在加密数据包中的攻击信息。（b）基于不同分析方法的分类：n 滥用检测（Bace, 2002）：它也被叫做基于签名的检测，它可以将攻击特征或者违反条例的信息转化成基于转化的下签名或规则，然后将这个信息存储到签名数据库中。判断是否受到攻击，先前判断数据首先会和签名数据中的签名进行比较，那些确认为攻击签名的数据将会判断为攻击。它的优点是较高的检测率和较低的误警率；然而，它

11、对于未知的入侵方法的检测能力低，攻击数据库需要周期性更新。n 异常检测（Bace，2002）：它可以先建立一个用户正常行为的文件，它的来源可以是先前阶段用户行为的统计数据；当检测工作时，这个文件中的数据会和真实的用户数据比较，如果差值超过门限值，用户的行为将被视为异常。异常检测是基于这样一个假设：入侵行为是与正常行为不同的。这种检测方法检测率高，且更容易检测到未知的攻击，当它的误判率也很高。n 混合方法：滥用检测的优点是误判率低，但对于未知攻击检测能力低；相比之下，异常检测拥有对未知攻击的检测能力，但误判率却很高。如果说两种方法结合起来，它们可以互补缺点，如：MINDS, EMERALD,Pr

12、elude等等。2.1.2现有的分析方法 下面描述了用于入侵检测系统中的现有的分析方法。（Bace，2002；Lu，Boedihardjo & Manalwar,2005；Patcha & Park，2007；Verwoerd & Hunt, 2002）：n 状态转换分析（llgun,kemmerer,& Porras, 1995）:状态检测主要用于描述发生的事件间的关系，常被用在滥用检测当中。n 统计方法：统计方法用于建立正常行为模型，其中包括：门限值，中值和标准差，多形式模型，簇和检测轮廓。n 神经网络: 在检测之前，有时需要训练，检测可以在建立模型后开始，

13、它包括：后繁殖，SOM（自我组成图）等等。n Bayesian 网络（BenAmor， Nahla， Benferhat Rue， Salem,& Elouedi，2004）：图表方法被应用于表达多样化之间的关联；当检测开始时，条件概率用来计算合适的检测值。n 基于规则的：行为或模式被表达为规则方法，那些与规则相一致的被判定为攻击。它通常用在滥用检测当中。n 数据挖掘（机器学习）方法：它包含了Markov处理模型（Kuo-Hua Yang，2006），分类树（Ben Amor et al., 2004; Yu-Shan Yang, 2006）,支持向量机器，关联规则，；链接分析，数列分

14、析等等。n 其他方法：其他方法包括免疫系统方法（Aickelin, Greensmith, & Twycross, 2004）, 运算法则分类，基于agent 的检测等等。2.2机器学习机器学习（/wiki/Machine_Learning）是一个人工智能的分支，主要目的是通过一些技术使计算机具备自主学习的能力。它重点研究的方向是如何用计算机和统计学的方法去从庞大的数据当中挑出有用的数据。所以，机器学习和数据挖掘与统计学方法和计算机科学理论有着密切的联系。现今，机器学习被广泛的应用于不同的领域当中，如：指纹差异，搜索引擎，药物诊断，市场关联分

15、析，发音和手写识别，计算机图像等等。下面列出了常用的机器学习技术（Alpaydin，2004）：l Bayesian 决策理论l 多样性方法l 簇l 分类树l 线性识别l 多层次观察l 本地模型l Hidden Markov模型l 强化学习2.3分类树分类树是在机器学习当中的一种预测模型，也被称为决策树。它是一种树形状的图，与表的结构相似；任何一个内部节点是一个性质测试，每一个树枝代表检测结果，最后叶子上的节点代表不同形式的状态分配。在分类树中最基本以及最常用的运算法则是ID3和C4.5（Quinlan，1993）。这是两种建立树的方法，从下到上树的结构和从下到上修剪，ID3和C4.5都属于从

16、下到上树的结构；它们的运算法则表述如下：. 所有样式的训练数据都被放在分类树的根部。. 如果一个节点中没有包含任何数据，或者数据中的节点属于同一种类型的，这个节点将成为空叶，或者所有形式的叶成为同一种类型。如果一个节点中包含多个形式，必须评估所用数据的性质，其方法是通过个别的确认功能以及适当的性质挑拣。通过在节点中的属性值和形式，将它们分成N部分，每一个部分都是一个连接根部节点的新节点。这个过程叫做节点分裂。. 在节点分裂之后，判断这些节点是否是树叶；如果不是，新的节点成为根部的分支树，其用来构成新的分支树。. 重复以上步骤直到所有新节点都成为树叶。决策树通过这种形式引导方法可以完全分类不同形

17、式的训练数据。在第二步的评估功能通用非纯净功能评价；在用非纯净方法计算后，最高值的的特性将被挑选出来。非纯净功能包括：假设S是由样本数据s组成的一个数列，其包含带有m个不同下标的Ci（i=1，, m），si是在数列S中的带有Ci类型的例子。Pi是任何一个样本数据属于Ci类型数据的概率，命名为si/S;再次假设性质A包含v个子数列，Sj代表一个数列在数列S中含有连续j个aj样本数据具有性质A。当一个性质被挑选为测试性质，它将包含Sj中的元素，v代表类型Ci。l 平均信息量功能: (用于ID3和C4.5中)l 收到的信息量：Gain（A）=I（T）-E（A）。其中I（T）= E（A）=l 收到的信

18、息率：GR（A）= 。其中I（A）=l Gini功能：Gini（T）=1- 。在树被建立之后，为了防止过大，建立起来的分类树需要被修剪，常用的方法有两种（Han & Kamber，2006）：修剪在前：在树的建立中，设置一个门限，当分岔点的状态高于门限值时，从分岔点开始停止建立树。修剪在后：当完成树的建立后，再修剪它。通常的方法包括替换分支树和增长分支树：修剪的评估原则包括错误评估，重要点测试等等。最后，在树被建立和修剪之后，规则将通过树来产生，如图2所示。 我们在实验中用C4.5型。图22.4 支持矢量机器支持矢量机器是由Vapnik所提出的（1995）；最近，它被广泛的应用于各种领

19、域当中，它也成为在机器学习领域中一个非常流行的方法。2.4.1. 最优化的分隔超平面首先，我们先用线性分隔为例。假设现在有两种类型的分类问题，用标志r来区分。它的数列是X,Xt的一个矢量，所以在数据中有一个数列，支持矢量机器是寻找一个能根据类型不同来分隔这些数据的超平面。用如下的图举例。它是寻找w 和b 两个参数，这两个参数可以用L2=wx+b来区分开两种类型。在分类后，我们需要wx+b的值，如果它大于0，他将是+1；如果小于0，它将是-1（如图三所示）。支持向量机器是找到一个距离任何一个数据最远的超平面，这样可以减小错误率。图四所示数据和超平面的距离。支持向量机器必须满足如下状态：wXt+b

20、>+1,wXt+b<-1它也可以写成rt(wXt+b)>+1.我们需要让Xt和超平面之间的距离大于p，使p最大。为了得到特别值，使p|W|=1;这个等式可以转换成二次方程最优化问题：Min1/2|W|2 图3图42.4.2.非线性分隔的情况当在非线性分隔情况时，基本功能（X）可以被应用，使原始的非线性坐标特性被转化成线性特性坐标，然后用线性方法计算，如图5所示。用过基本功能之后，辨别功能会有一个基本功能的内在产物 和另外一个功能K（x,x）被用于替换基本功能，这个功能叫做核心功能。图53.系统结构l 系统结构图研究的流程图如图6所示。图6l KDD Cup 99数据研究中数据

21、的来源从KDD Cup 99中得来的，它最开始是用在第三代国际知识探索和数据挖掘工具竞争方面。这个数据是经过挑选和整理美国空气阻力的DARPA数据而来的，由美国哥伦比亚大学在1998年提出的。它被用于评估入侵检测算法的效率。所以，在本次研究中也应用这个数据。在训练数据中，将近有4940000种数据，10%的数据被提供；在测试数据中，有3110291种数据，且在每种网络连接记录中，总共47中类型的网络连接特性（特性分为连续数据和非连续数据）。它的特性可以主要分为三种类型：网络连接的基本特性，网络连接内容的特性，网络传递的特性；数据形式包括名义上的，双重性的，数字的。由附录1来做进一步说明性质细节

22、。在训练信息中有23种类型的攻击，在测试数据中有37种类型的，比训练信息多14种，所以训练信息可以评价检测未知攻击的能力。在测试信息中，攻击可以大体被分为以下几种类型：l 探索型：直白的说，它不应该被称为真的攻击，但它是在攻击开始前的一个准备步骤。攻击者经常利用探索获得信息，检测目标和操作系统的类型。l Dos（服务拒绝）：这种攻击可以停止用户操作，服务器不能提供服务。这种攻击通常复制所有服务器的系统资源或者复制带宽并使系统资源瘫痪，使操作系统停止。一般的攻击包括SYN Flooding，Ping Flooding等等。l U2R（用户获得根）：在这种攻击中，用户利用系统漏统的优势来得到合法的

23、管理者的资料。例如：Buffer Overflow就在其中。l R2L（获取远程文件）：这种攻击利用为用户提供服务的优势，获取相关的安全设置和用户的加密文件，如：Unicode leak，SQJInjection等等。表1列出了攻击的形式和类型。表1表2列出了在训练数据和10%的kddcup.data_10_percent.gz.中不同数据的百分比。表2l 数据处理本次研究想在不同的环境下比较C4.5和SVM的效率。由于KDD Cup 99的数据过于庞大，各种各样的数据被分配的不平均，所以研究将会对训练数据（kddcup.data_10_percent.gz.）和测试数据取样。根据正常的比例，

24、挑选10000组数据，使正常比例分别为10%，20%，90%；其他的数据，我们命名为攻击数据，把他们平均并取样。除了取样，C4.5软件Weka 3.5.6应用于训练阶段，其输入形式为arff;SVWare 软件的应用是由台湾大学信息工程学院的一个教授开发的Lib-svm,其输入形式也是特定的，因此所有数据的形式都可以被转换。Weka3.5.6 也可以传递信息给SVM形式。所以研究应用Weka 软件来转换。l 训练和测试在处理数据之后，训练和测试就可以开始了。在Weka中的C4.5功能是J48,需要设置一些参数，包括降低错误修剪，信任因素，最小对象数目。Libsvm的训练阶段也需要设置参数，用巨

25、蛇程序找到最优化的参数:gridpy.它是用来在本次研究中找到最好参数的方法。. 分析与评估攻击的检测和识别以及非攻击的行为可以大体归纳如下表3中：l 真正（TP）：真正发生攻击时检测到的攻击。l 真反（TN）：正常情况下检测到的正常情况。l 错正（FP）：正常情况下检测到的攻击。也叫做误警。l 错反（FN）：真正发生攻击时检测到的正常情况。也叫做可以被入侵检测系统检测到的攻击。表3如今，入侵检测系统需要高检测率和低误警率，所以论文中比较了精确率，检测率和误警率，并且列出了不同攻击下的结果对比。l 精确率对比精确率涉及到在总数据中，属于精确型数据的比例，也叫做TP和TN状态，所以精确率为： 精

26、确率=表4列出了用原始标签分类的结果比较。图7为折线图。这两种方法在精确度上并没有太大的差异；然而，当正常数据所占的比例小时，C4.5优于SVM；当正常数据的比例大时（>70%），它们的精确率近乎相同，但SVM 好些。通过平均，C4.5要比SVM稍微好些。图7l 检测率比较检测率涉及到检测到的攻击和所有攻击的比，形态为TP，所以检测率为： 检测率=表5列出了C4.5和SVM之间的检测率比较结果。图8为折线图。 图8在检测率上，C4.5随着正常数据的比例不同而下降，但SVM的变化却不定。整体来说，C4.5的曲线要高于SVM；显然，它的检测率要好于SVM。通过平均，C4.5超过SVM将近12

27、%。l 误警率比较误警率涉及到正常数据被错误的检测为攻击，按名称，是FP形态，所以误警率为：误警率=表6列出了C4.5和SVM之间的误警率的比较。图9为折线图。图9表5表6在误警率的比较中，SVM只有在正常数据比例为30%，50%和60%时才劣于C4.5，其他情况下都要优于C4.5。通过平均值，SVM在误警率方面要好于C4.5。4.4不同攻击之间的精确率比较不同攻击下的精确率涉及到数据的类型被正确划分的比例。在论文中用了四种类型攻击，它们是Probe，Dos，U2R，R2L。表7列出了用C4.5和SVM两种方法，在不同攻击下的精确度比较结果；表中两个数据上面的为C4.5的精确信息，下面的为SV

28、M的精确信息。从表格中，你会知道l 对于探索攻击：当正常数据的比例为20%，50%和90%时，SVM的精确率要比C4.5好，但不高于4%；然而在其他环境下，C4.5的精确率超过了SVM将近10%.显然，在这种攻击中，C4.5的精确率要好于SVM。l 对于Dos攻击：当正常数据的比例低时，SVM要好些；然而，当正常数据的比例超过40%时，C4.5要比SVM好，特别是在正常数据的比例为40%，60%和70%时。l 对于U2R攻击：总体来说，C4.5要比SVM好。l 对于R2L攻击：通过平均值，在精确率上两种方法的近乎相同。当正常数据的比例为10%，30%，50%和90%时，SVM好些，其他情况时C

29、4.5好些。l 通过平均值，除了在R2L攻击下两者的精确率差不多，其他攻击下C4.5在精确率上要优于SVM。表7最后，论文中得到的平均结果与从KDD Cup 99 winner 中得到的数据相比较，比较结果在表8中。我们可以看到，KDD Winner的检测率在Dos攻击中很高，当在U2R和R2L攻击中，却比C4.5和SVM差。表8. 结论和建议5.1 结论论文比较了在正常数据的不同比例下的不同攻击的精确率，检测率，误警率。KDD Cup 99数据是当前在入侵检测中的基准数据；然而，它的的数据分配的不均匀。本次研究用了不同的正常数据的比例来做训练和测试，最终得到一个平均值，希望能得到更多目标结果

30、。从比较C4.5和SVM的结果看，我们发现C4.5在精确率和检测率上要比SVM优越；在检测探索，Dos和U2R攻击的精确率上，C4.5也要好于SVM；但在误警率方面，SVM要好些。5.2 未来研究建议l 数据KDD Cup 99在当前很流行的被应用于入侵检测系统当中；然而，它是1999年的数据，网络技术和攻击方法更新的很快，它不能反映现今真实的网络状态。所以，如果更新的信息被加入和测试，它们可以更精确的反应现今的网络状态。l 经过测试和比较，C4.5的检测率和精确率要高于SVM，但是SVM在误警率方面要好些；如果我们可以把两种方法组合起来，整体的精确率会有很大的提高。l 在样本中，研究假设了攻

31、击数据和正常数据是平均分配的，这当然不能得到最优化的结果，在这一点上，在未来应该有所提高和加强论证。l 在研究中，C4.5的参数设置不是最优的，所以未来的工作可以通过C4.5的参数和不同的训练数据来优化参数。l 被应用在研究中的SVM用built-in grid.py来优化它的参数，这需要将近两个小时去寻找研究中的10000组数据的参数；然而这是不合适的，因为在入侵检测系统当中需要实时性。在未来的研究中应当找到一种可以快速选择出最优化的检测方法。参考文献Aickelin,Uwe,Greensmith,Julie,&Twycross,Jamie(2004).Immune systemap

32、proaches to intrusion detectionA review.Berlin,Heidelberg:Springer.Alpaydin,Ethem(2004).Introduction to machine learning.MIT Press.Anderson,James P.(1980).Computer security threat monitoring and surveillance,technical report,James P.Anderson Co.,Fort Washington,Pennsylvania.Bace,Rebecca G.(2002).NIS

33、T special publication on intrusion detection systems.Ben Amor,Nahla,Benferhat Rue,Salem,Elouedi,Zied.(2004).Na¨?ve Bayes.vs.decision trees.In:Symposium on applied computing proceedings of the 2004 ACMsymposium on applied computing.Confusion Matrix.<http:/www2.cs.uregina.ca/dbd/cs831/notes/co

34、nfusion_matrix/confusion_matrix.html>.Dorothy,Denning.1987.An intrusion detection model.IEEE Transaction on SoftwareEngineering.Event Monitoring Enabling Responses to Anomalous Live Disturbances(EMERALD).Ertoz,L.,Eilertson,E.,Lazarevic,A.,Tan,P.,Srivastava,J.,Kumar,V.,et al.(2004).TheMINDSminneso

35、ta intrusion detection system.Next generation data mining.MITPress.Han,J.,&Kamber,M.(2006).Data mining:concepts and techniques(2nd ed.).MorganKaufmann Publishers.Ilgun,K.,Kemmerer,R.A.,&Porras,P.A.(1995).State transaction analysis:A rule-based intrusion detection approach.IEEE Transaction on Software Engineering,21(3).Jiang,Sheng Yi et al.(2006).A clustering-based method for unsupervised intrusiondetections.Pattern Rec