一种改进的关联规则挖掘算法在入侵检测中的应用研究

1、一种改进的关联规则挖掘算法在入侵检测中的应用研究张应征 成新红(湖南工程职业技术学院 湖南 长沙 410114)摘 要: 为了解决网络入侵检测领域使用Apriori算法挖掘频繁模式效率不高、精度不够的问题,本文引入自适应步长跃进、动态修剪候选频繁项集的概念，提出一种新的改进关联规则挖掘算法，该算法较Apriori算法有比较明显的优势, 可以广泛应用于大规模入侵检测数据库的关联规则挖掘中。关键词: 关联规则; Apriori算法; 入侵检测中图法分类号：TP391 文献标识码：AAn Improved Algorithm for Mining Association Rules in The A

2、pplication of Intrusion DetectionZHANG Ying-zheng， CHENG Xin-hong（HuNan Engineering Polytechnic HuNan ChangSha 410114）Abstract: In order to solve the network intrusion detection field use Apriori algorithm frequent itemsets efficiency is not high， precision insufficient problems， this article introd

3、uces adaptive step jump， dynamic clip candidate frequent itemsets concept， put forward a new algorithm for mining association rules algorithm， the proposed algorithm is Apriori has obvious advantages， and can be widely used in large database of intrusion detection of association rule mining.Keywords

4、: association rules; Apriori algorithm;Intrusion detection1 引 言关联规则挖掘是数据挖掘中一个重要的研究内容, 可以从海量数据中发现正常和异常的行为模式, 将其应用于入侵检测不仅可以有效地检测已知入侵, 而且还具有检测未知攻击模式的能力, 具有更高的准确性和适应性。因此研究关联规则的高效挖掘算法对于提高入侵检测的准确性和时效性具有非常重要的意义。本文在分析经典Apriori算法的基础上,针对其存在的问题提出一种自适应步长跃进的改进Apriori算法I-Apriori算法。该算法引入自适应步长跃进、动态修剪候选频繁项集的算法优化技术,解

5、决了Apriori算法数据库扫描次数过多、频繁项长度增加时运算时间显著增加,产生候选集数目过大等问题能显著提高算法效率。其算法有较明显的优势,可以广泛应用于入侵检测数据库的关联规则挖掘中。2 传统的关联规则挖掘算法定义1 关联规则: 令I = i1, i2, im为项的集合(item set) ,简称项集, D为事务数据库, 其中每个事务T是一个项目子集(TI), 并具有一个惟一的标识符TID。关联规则是形如X=Y 的逻辑蕴含式, 其中XT , YT , 且XY =。定义2 频繁项集: 包含k 个项的项集称为k项集。规定一个最小支持度min_sup 为支持度阈值, 如果项集的出现频率大于等于m

6、in_sup, 则称该项集为频繁项集(frequent itemset) , 简称频集, 频繁k项集的集合记作Lk。以上就是传统的 Apriori算法,然而它存在以下三个不足：(1) 需要重复地扫描数据库。如果存在较长的频繁项目集, 则要重复扫描数据库的次数就很多, 对于入侵检测数据库的大量数据而言, 该算法的时间复杂度是非常庞大的。(2) 产生大量的候选项集, 特别是候选2项集。如果有1000个频繁1项集,那么该算法将会产生105数量级的候选2项集。 (3) 支持度计数的工作量很大。3 改进的关联规则挖掘算法基于Apriori 算法存在的问题, 提出入侵检测数据库的改进关联规则挖掘算法I-A

7、priori算法, 其改进的算法思想如下：3.1 自适应步长跃进Apriori算法中,产生每个频繁项集需要扫描一次数据库。为了减少对数据库的扫描次数, 本算法是在己产生的Lk基础上以hi为步长, 通过连接、剪枝一次性产生新的以hi为步长的(k+j)-itemset (j= 1,2, hi )的候选频繁集, 然后再扫描数据库,确定其中真正的频繁项集, 从而可以大大减少挖掘过程中的数据库扫描时间,对于海量数据库,效果尤为明显。 在步长h的选择上采取了自适应可变步长的确定方法, 即h1=2, hi+1=2I(i)hi , 其中I(i)用来表示步长的自适应方向, 即当有频繁项集产生时I(i)=1, 无

8、频繁项集产生时I(i)=1/2hi 。之所以将步长越设越大,是因为随着算法的进行, 频繁k-itemset蕴含的频繁1-itemset的个数只可能越来越少, 因而产生的候选集规模也会越来越小, 这样,可以较大程度地提高内存利用率。 在扫描大规模数据库时, 自适应步长跃进可显著减少对数据库的扫描次数,但是,却产生了相对较大的候选集。针对这一问题, 可采用下面提出的方法改进, 产生尽可能小的候选集, 以节省内存空间。3. 2 动态修剪候选项集为了更好地描述算法的优化思想, 先给出频繁项集的一些性质：性质1: 若k维数据项目集I=i1 , i2, ,ik 中,至少有一个imI（m=1,2k）使得Nk

9、-1(im)1) (7) i+；(8) Ck+i =Apriori_gen(Ck+i-1 ， min_sup)；(9) j-； (10) for each transaction tD / 扫描数据库，统计支持数(11) Ct =subset (Ck， t)； / 候选集合由事务t产生的(12) c.count+； /对候选集合的候选集计数(13) end； (14) return L=kLk2、进行动态修剪候选项集(1) for each itemset lLk-1(2) for each item il / l为数据库中所有项目的集合(3) for each item il(4) if i

10、.countk-1(5) for each itemset lLk-1(6) if il(7) Lk-1 = Lk-1 l； / 动态修剪候选项集(8) for each itemset l1Lk-1(9) for each itemset l2Lk-1(10) if l11= l21 l12= l22 l1k-2= l2k-2 l1k-1 l2k-1 (10) for each itemset l2Lk-1(11) if l11= l21 l12= l22 l1k-2= l2k-2 l1k-1 l2k-1 (12) c= l1l2(13) if has_infrequent_subset (

11、c, Lk-1)(14) then delete c;(15) else add c to Ck; (16) return Ck4改进的算法在入侵检测中的应用基于关联规则挖掘的入侵检测方法是采集用户的历史审计数据,利用频繁项集挖掘算法进行挖掘，然后系统对当前网络数据进行关联分析, 寻找当前网络的频繁项目模式,并对网络连接记录进行检测和标记，发现可能存在的入侵。一、规则生成模块。该模块的主要任务是运用前面所提出的改进Apriori算法对经过预处理的网络连接数据进行挖掘,分别在不包含攻击数据的纯净训练数据集和含有入侵行为的训练数据集上进行, 建立系统和用户的正常行为模型和攻击模型, 形成规则库。二

12、、实时检测模块。该模块主要对当前用户的网络连接数据进行关联规则挖掘, 根据训练阶段所得的规则库, 发现可疑入侵, 并及时对正常行为模型和攻击模型规则库进行更新, 以检测可能存在的新的入侵。 因此,该系统具有一定的自学习能力, 系统规则库中的规则会随着网络数据的变化不断完善, 即使系统出现新的攻击类型,仍可以保证检测的精确度。5 结束语 针对现行的入侵检测方法不够准确、完善，容易造成误报或漏报的问题, 本文在Apriori算法基础上，提出了一种新的改进算法。该算法引入自适应步长跃进、动态修剪候选项集的概念, 从而大大减少了对数据库的扫描次数, 并显著减少了候选集的数量, 提高了算法的效率。下一步

13、的工作主要研究更优的自适应步长计算方法以及更高效的动态剪枝策略, 以使算法具有更高的执行效率。参考文献：1 卿斯汉, 蒋建春, 马恒太等. 入侵检测技术研究综述 J . 通信学报, 2004, 25 (7) : 19-29.2 R Agrawal, T Imielinskia , A Swami. Mining Association Rules between Sets of Items in Large Databases C. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of D

14、ata, Washington, D.C, 1993: 207 -216.3 Lee W K, Stolfo S J. Data mining approaches for intrusion detectionZ. The seventh USENIX Security Symposium (SECURITY 98), San Antonio, TX, 1998: 79-94.4 吴际, 黄传河, 王丽娜. 基于数据挖掘的入侵检测系统研究J. 计算机工程与应用, 2003 , 40 (4) : 166 -168.6张应征.数据挖掘技术在物流管理信息中的应用D.武汉：华中科技大学，2009.7

15、 KDD CUP 1999 datasetEB/OL. /databases/kddcup99/kddcup99.html, 1999.作者简介： 张应征：1970年4月生，讲师，硕士，研究方向：计算机应用、数据库等。 成新红：1974年3月生，硕士 研究方向：计算机应用工作单位：地址：湖南省长沙市大托铺湖南工程职业技术学院（南院） 邮寄地址：湖南省长沙市井奎路中建五局华欣公寓3-604号。 邮编：410004 电话电子邮箱：zyzsuper Author introduction: ZhangYingZheng: in April 1970 born, lecturer, master degree, research direction: computer applications, databases, etc. ChengXinHong: March 1974 born, master research di