基于数据挖掘关联规则Apriori改进算法的入侵检测系统的研究

1、第29卷第3期2011年8月贵州师范大学学报(自然科学版Journal of Guizhou Normal University (Natural Sciences Vol29No3Aug 2011文章编号:10045570(201103008404基于数据挖掘关联规则Apriori 改进算法的入侵检测系统的研究张浩,景凤宣*,谢晓尧(贵州师范大学贵州省信息与计算科学重点实验室,贵州贵阳550001摘要:在众多的关联规则挖掘算法中,Apriori 算法是最为经典的一个,但Apriori 算法有以下缺陷:需要扫描多次数据库、生成大量候选集以及迭代求解频繁项集。因而提出了一种新方法,使Aprior

2、i 算法产生的候选项集再通过数据库查找是否为频繁项集,从而提高算法的效率。最后针对入侵检测系统形成关联规则。实验结果表明,改进后的算法能有效地提高关联规则挖掘的效率。关键词:数据挖掘;Apriori 算法;频繁项集;入侵检测系统中图分类号:TP309文献标识码:AThe Research of Intrusion Detection System Based on ImprovedApriori Algorithm of Data Mining Association RulesZHANG Hao ,JING Feng-xuan *,XIE Xiao-yao(Key Laboratory of

3、 Information and Computing Science of Guizhou Provinces ,Guizhou Normal University ,Guiyang ,Guizhou 550001,China Abstract :Among a large number of association rule mining algorithms ,Apriori algorithm is the most classic one ,but it has three deficiencies ,including scanning databases many times ,g

4、enerating a large number of candidate anthology ,and mining frequent itemsets iterativelyThis paper presented a meth-od ,Apriori algorithm to generate the candidate itemsets and then finds whether it is the frequent item-sets through the database ,thereby enhancing the efficiency of the algorithmFin

5、ally ,intrusion detec-tion system for the formation of association rules (IDS The experimental results show that the opti-mized algorithm can effectively improve the efficiency of mining association rulesKey words :Date mining ;Apriori algorithm ;Itemset ;Intrusion Detection System (IDS 0引言数据挖掘就是从存放

6、在数据库、数据仓库或其它信息库中的大量数据中获取有效的、最终可理解、新颖的、有用的模式的过程。因为数据量过大,所以大量的工作在于数据挖掘算法的方面。管理规则(Associate Rule 在数据挖掘中具有非常重要48收稿日期:20110608基金项目:贵州省科学技术基金(200917,贵州省科学技术基金(201037,贵州省科技厅工业攻关(20083009作者简介:张浩(1986,男,硕士,信息安全,E mail :zhanghao_056163com*通讯作者:景凤宣(1955,女,教授,信息安全,E mail :fxj989gznueducn的地位,也是数据挖掘的较为重要任务之一。入侵检测

7、系统(Intrusion Detection System, IDS是对入侵行为的检测。它通过收集和分析网络行为、安全日志、审计数据、其它网络上可以获得的信息以及计算机系统中若干关键点的信息,检查网络或系统中是否存在违反安全策略的行为和被攻击的迹象。入侵检测作为一种积极主动地安全防护技术,提供了对内部攻击、外部攻击和误操作的实时保护,在网络系统受到危害之前拦截和响应入侵。因此被认为是防火墙之后的第二道安全闸门,在不影响网络性能的情况下能对网络进行监测1。若在两个或多个变量的取值之间存在某种规律性,则称为关联,关联规则是寻找在同一个事件中出现的不同项的管理性,其挖掘可以发现大量数据中数据项集之间

8、的关联。比较经典的关联规则发现方法是RAgrawal等人在ASI算法基础上提出的改进算法:Apriori算法,本文在经典的Apriori 算法基础上提出改进方案,并应用于入侵检测系统中,并且具有一定实用价值。1Apriori算法11Apriori算法简介Apriori算法首先找出所有的频集,这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则,这些规则必须满足最小可信度和最小支持度。再使用前面一步找到的期望的规则,产生只含有集合的项的所有规则,其中每一条规则的右部只有一项。Apriori算法主要缺点在于会产生大量的候选集,以及可能需要重复扫描数据库。从下面几个方面提高Ap

9、riori算法:1在通过扫描事务数据库D,来甄别修剪后Ck中候选的k项集是否为频繁的过程中,同时也将每个包含k项集的事务中包含的所有可能的(k+1项集加进散列表中,如此,落在计数小于最小支持计数(=min-sup*|D|内的(k+1项集就必定是非频繁项集,给予删除。2D的任一全局频繁项集必须至少也是某个Di中的局部频繁项集;反之,非局部频繁项集必定非局部频繁。如此,可以通过高效处理,大幅度压缩D候选项集的集合。3通过随机取样建立D的子集,只从子集搜索频繁项集,并使子集能一次性进入内存做高效处理,相当于只需对D的子集做一次扫描。12算法举例该例来自于Park等人的事务数据库D。数据库中有9个事务

10、,5个属性,假定min_sup=2,min-support_count=3。对每个事务产生的2项目集,将它们散列到项目集的分配中。(1L1=find_frequent_1itemsets(D;(2for(k=2;Lk1;k+(3Ck=apriori_gen(Lk1,min_sup;(4for every transaction tD(5Ct=subset(Ck,t;(6for every candidate cCt(7ccount+;(8(9Lk=cCk|ccountmin_sup(10(11return L=Lk;2Apriori算法的改进21关联规则定义关联规则是Agrawl等人于1993

11、年提出来的,关联规则是数据挖掘关联规则中的一个重要的研究内容。关于这个算法有一个非常有名的故事:“尿布和啤酒”。故事是这样的:美国的女性们经常会嘱咐她们的丈夫下班后为孩子买尿布,而丈夫在买完尿布后又要顺手买自己爱喝的啤酒,因此啤酒和尿布在一起被购买的机会很多。这个举措使尿布和啤酒的销量均增加,并且一直为众商家所津津乐道2。资料库(Transaction Database:存储二维结构的记录集。定义为:D所有项集(Items:所有项目的集合。定义为:I。记录(Transaction:在资料库里的记录。定义为:T,TD项集(Itemset:同时出现的项的集合。定义为:k-itemset(k项集,k

12、-itemset T。除非特别声明,否则下文出现的k均为项数。支持度(Support:定义为supp(X=count (X/count(D=P(X。解释1:例如选秀比赛,选秀的支持度和它比较类似,观众(资料库,其中有多少人是选择(支持你的,那个就是支持度;解释2:例如100个人去超市买东西的,其中58第3期张浩,景凤宣,谢晓尧:基于数据挖掘关联规则Apriori改进算法的入侵检测系统的研究买苹果的有7个人,即说苹果在这里的支持度是7,7/100;解释3:P(X,意思是事件X出现的概率;解释4:关联规则当中是有绝对支持度(个数和相对支持度(百分比之分的。置信度(Confidence/Streng

13、th:定义为conf(X Y=supp(XY/supp(X=P(Y|X。候选集(Candidate itemset:通过向下合并得出的项集。定义为Ck。频繁集(Frequent itemset:支持度大于等于特定的最小支持度(Minimum Support/minsup的项集。表示为Lk。注意,频繁集的子集一定是频繁集。提升比率(提升度Lift:lift(XY=lift (YX=conf(XY/supp(Y=conf(YX/supp(X=P(X and Y/(P(XP(Y剪枝步:只有当子集都是频繁集的候选集才是频繁集,这个筛选的过程就是剪枝步3。经过关联规则分析后,有针对性推销(根据某规则比盲

14、目推销(一般来说是整个数据的比率,这个比率越高越好,我们称这个规则为强规则4。22算法的改进由于Apriori算法重复扫描事务数据,不仅浪费大量时间,还增加I/O负载。因此本文试图通过找到一种新的算法来取代通过候选集去找频繁集的过程。具体算法如下:阶段1:扫描数据库D,得到频繁1项集;将频繁1项集按照支持度从大到小进行排序,且记排好的序列为N;再次扫描D,构建FP树。阶段2:搜索FP树中对应于叶子节点的每个项的条件模式集;从每个条件模式集构建条件FP树;从每颗条件FP树递归地挖掘频繁模式。这样不仅可以避免大量候选集的产生,而且能减少对数据库的扫描次数,从而提高效率。该算法特点是只生成一颗条件模

15、式树,且在遍历条件模式树时也不需要对全树的进行遍历。本文用Java实现了上述改进算法,事务数为80000,事务平均长度8,属性长度235。运行结果如下:23数据挖掘的入侵检测模型图2中,报警处理模块对来自嗅探器,对于同一个攻击原始数据形成新的攻击事件,规则库利用关联规则知识库的频繁模式对事件进行关联分析,并预测未知的可能攻击。将其结果提交给用户5 。3实验分析为了证明该算法的性能的改进,本文采用Snort2903在alert_fast模式下输出报警6。数据采用未改进的Apriori算法和改进后的Apriori算法实验数据。算法使用Java语言在MyEclipse平台上实现。表1列出了在使用改进

16、前的Apriori算法Snort 在所有检测数据库开启时,每天报告的报警种类、报警数目以及误报率。表2统计了改进后Apriori 算法的报警种类、报警数目以及误报率。实验中min_sup=002,min_conf=002。表1算法改进前数据表Tab1Before improve algorithm data数据来源报警数目报警类型误报率/%算法改进前第一天内网164043算法改进前第二天内网134026算法改进前第三天内网143033算法改进前第四天内网83015算法改进前第五天内网11402768贵州师范大学学报(自然科学版第29卷表2算法改进后数据表Tab2After improve al

17、gorithm data数据来源报警数目报警类型误报率算法改进后第一天内网134024%算法改进后第二天内网940算法改进后第三天内网103018%算法改进后第四天内网630算法改进后第五天内网840实验分析得到的强关联规则数约占报警总数的03%。数据挖掘到IP地址为210406531: 5556频繁受到“DOS”攻击;同时挖掘到IP地址为210406560向其他IP发送包中都包含了“SYN”洪泛攻击。从改进的Apriori算法实验中的数据集检测到大量的IP地址为2104065246和IP地址为2101065251之间相互PING。从实验结果分析还得知一般情况下系统的负载小于40%时,系统的误

18、报率保持为0,系统负载高于40%时,系统的误报率出现增加,并且误报率会出现较快提升。通过实验可以挖掘出一些有价值的信息,减少管理人员的工作量。4结束语经典的Apriori算法多次扫描事务数据库,需要很大的I/O负载和可能产生庞大的候选集从而导致挖掘效率很低。本文提出一种新的改进算法。实验表明,改进后的算法能够很快得到一些强关联规则,在短时间内挖掘出有价值的报警,减少管理人员的工作量。今后适用于入侵检测技术的关联规则挖掘算法的研究将会是研究的重点内容之一。同时,通过关联规则得到特征模式规则体现了决策属性和行为之间的关联关系,为进一步运用数据库关联规则挖掘提供可靠的依据。参考文献:1Han Jia Wei,Kamber M数据挖掘概念与技术M范明,孟晓峰,译北京:机械工业出版社,2006:102-1032苏新宁,