陈真

（韩山师范学院 潮州师范分院办公室，广东 潮州 521012）

改进的Apriori算法的入侵检测系统研究

陈真

（韩山师范学院 潮州师范分院办公室，广东 潮州 521012）

综述了数据挖掘技术在网络入侵检测中的应用，阐述了关联规则分析在网络入侵检测中的应用原理和最新的研究与改进，并指出了目前存在的问题和未来研究的方向.改进由k阶频繁项集生成k+1阶候选频繁项集时的连接和剪枝策略；改进对事务的处理方式，当所有联接完成时只扫描一遍Lk-1，减少Apriori算法中的模式匹配所需的时间开销.实验表明，该算法应用于此系统来提取用户行为特征和入侵模式特征，提高了整个系统的性能.

关联规则；频繁项集；候选项集；Apriori算法；Apriori_ids算法；入侵检测

入侵检测系统（intrusion detection system，IDS）是通过扫描操作系统的审计数据或网络数据包信息来检测未经过授权或非法进入系统和网络或者滥用系统和网络的用户行为的系统，该系统通过系统审计记录、分析和检测网络流量等手段来识别系统中的存在非法入侵的行为，及时地判断、记录并报警，使系统管理人员及时采取有效的措施来弥补系统漏洞.美国哥伦比亚大学Wenke Lee最早[1]提出将数据挖掘技术应用于入侵检测系统，在检测中将审计记录数据和网络数据进行预处理及关联规则挖掘分析，将产生的关联规则添加到关联规则库中去，然后通过关联规则库中的规则匹配来判断用户行为是否入侵，从而达到提高检测系统的可扩展性和自适应性，并有效减少漏报率和误报率.

关联规则[2]表示数据库中某种关联关系的一组对象之间的规则，其数学表达式：X→Y[c，s]，X，Y表示数据库中的记录，C为确信度，S为支持度.挖掘关联规则就是将产生支持度和可信度数值分别与预先给定的Min_support和Min_conf相比较，若项集满足其最小支持度，则称之为频繁项集.本文以Snort入侵检测系统为基础，提出了利用改进的Apriori算法应用于入侵检测系统，该算法能够更为高效的提取用户行为特征和入侵模式特征，优化了整个系统的性能.

1 相关工作

1.1 Apriori算法

最为经典的关联规则挖掘Apriori算法，是一种挖掘单维、布尔关联规则频繁项目集的算法，由Rakesh Agrawal Rama和krishnan Skrikant于 1993年提出的[3]，其算法思想：先扫描数据库中所有事务，统计每个项集出现的频繁项，剔除不满足用户设定的支持度的项集，得到频繁1-项集；利用频繁1-项集的连接，再生成候选2-项集.然后统计每个候选项集的支持计数，得到频繁项集2-项集的集，如此重复下去，直到得到数据集中的所有频繁项集.Apriori作为经典的频繁项目集生成算法，在关联规则挖掘中具有里程碑的意义，但是随着研究的进一步深入，它的不足也暴露出来[4]：

1）每生成一个k-频繁项集（k=1，2，…，k）都需要扫描一次数据库，如此重复扫描数据库的算法，对内存占用较大的I/O开销过大.

2）连接程序中重复相同的项目步骤太多，算法效率有待进一步改进.

3）算法的剪枝步，∀c∈C ，判断Ck的k个（k-1）-子集是否都在Lk中，若存在一个（k-1）-子集不在Lk中，则剔除Ck.此步骤会多次扫描Lk，当Ck很大时，算法的效率明显低下.

1.2 目前改进算法的研究

许多学者已经开始Apriori算法从不同的层面或不同的策略提出了各种优化算法，主要从减少生成候选项目集的数目及减少对数据库的扫描次数方面进行优化，如在文献[5]中作者把支持度低于Min_support对后面的频繁项集不起作用的事务直接从数据库中删除，这样提高了候选项集的计数速度，在一定程度上优化了算法的效率.文献[6]中提到在对第K次数据库扫描中优先适用于每个长度为l（l≥k）的事务来生成候选K-项集，从而减少对数据库的扫描次数，以提高空间复杂度.王卉，屈强提出基于因子项集的并行化策略GP以发挥串行算法的剪枝功效[7]等，这些改进后的算法挖掘的效率和性能都明显高于Apriori算法.

2 Apriori算法的改进

由于经典Apriori算法需要循环多次扫描事务数据库，对生成的候选集Ck中的每个元素都必须通过k循环扫描数据库来检验是否满足Lk中，这样占用了大量的的I/O负载.因此，减少两个项集之间比较的项的个数和减少比较的项集个数，将直接影响后面减少连接的运算量，确保提高运行的效率的关键.

因此，本文在对生成的Lk及对支持度的计数中直接剔除不满足条件的非频繁项集，对事务数据进行事务压缩，从而减少Apriori算法中的模式匹配和剪枝步骤，减小扫描事务数据库的大小，从而提高算法的效率.

2.1 Apriori算法改进的思路

关联规则挖掘Apriori算法改进的主要思路如下：

1）减少候选集Ck的生成.在扫描数据库之后，如果事务t不包含Ck中任何一个项集或事务t是Ck中某一项集的子集但不满足预先给定的min_sup⁃port，就直接过滤掉.

2）减少判断次数.通过从Lk-1中提取元素来判断是否满足Ck中元素的子集，对Ck中数据项集的子集个数进行统计，从而减少该算法的运算量.

2.2 性质及相关推论

性质1 任何频繁项集的一切非空子集为频繁项集，则该项集的非频繁项集的超集也是非频繁项集[8].

证明 ∀项集X，且X非频繁项集，即P（X）＜min_support，则项集X中的子集i，项集i⋃X也不是频繁的，即P( )i⋃X ＜min_support，则 Apriori性质满足反单调性.

性质2 如果频繁k-1项集存在频繁k项集，则频繁k-1项目集的个数必大于等于k.

证明 由性质1可得，Lk生成频繁k-1项集中必存在k个不同的k-1项子集，因此k-1项集的子集的个数必大于等于k，证毕.

推论1 若频繁k-项目集还存在X为频繁项目子集，则X生成的k个k-1维子集中，对∀i∈X均存在.

证明 假设∀X生成的k个k-1维子集中∀i∈e，使 |LK-1(i)|＜ k-1 |，因为i∈e，则可得i∈X，而根据性质2证明可得知 |LK-1(i) |＞k-1，这与假设相矛盾.

此推论在修剪频繁项集阶段应用将有效减少挖掘候选频繁项集的时间开销.

2.3 算法描述

根据以上性质和算法改进的思路，设计的改进算法如下：

2.4 算法的分析

1）算法Apriori_ids完成连接，只要对Lk-1进行1次扫描，对于Lk-1中存在元素e，判断e是否为Ck中元素c的子集，对于小于k则剔除，反之，则对子集C进行计数.这样避免了对事务的项目进行大量的重复扫描集合和模式匹配计算，在一定程度上提高了算法的时间效率.

2）算法采用的数据结构相对简单，减少候选项集的迭代操作，避免了其他改进算法中构造复杂的数据结构花费太多的时间，也避免了对相应的数据结构复杂的算法操作，如文献[5]对矩阵进行相乘运算就比较费时.

3 改进的算法在IDS中的应用

3.1 入侵检测系统

根据入侵检测系统和数据挖掘技术的特征，本文提出了一种基于关联规则挖掘技术的入侵检测系统，见图1[10].

首先通过数据挖掘相关模块对收集到数据信息进行关联挖掘，利用改进Apriori算法找出满足min_support和min_conft的频繁K-项集，不满足频繁项集的，过滤掉，反之生成相应的关联规则，并利用特征构造算法为模式添加附加特征，送入分类器形成分类规则，通过规则的添加和合并处理，形成入侵规则库和正常行为规则库，最后，检测引擎通过规则相似度和规则匹配比较来检测入侵.

图1 基于关联规则挖掘的入侵检测模型Fig.1 Model of intrusion detection based on the mining technique of association

3.2 算法仿真实验分析

为了比较改进Apriori算法与原始Apriori算法之间的运算效率，本文进行了实验，下面是实验结果和分析.

试验测试环境：主频Intel3.0GHz，内存为2GB，Windows XP的操作系统上进行实验.

实验参考数据来源于KDDCup99入侵检测经典数据集，KDDCup99共有4 898 345条数据记录，其中正常数据972 780条，覆盖4种类型的攻击：Probing 41 102条、R2L90条、Dos 3 883 370条、U2R 1 003条.由于各方面复杂限制，我们这里选择4个类型8种常见攻击方式[11]进行实验，见表1.

表1 实验攻击类型Tab.1 Attack date types of experiment

实验主要基于原Apriori算法和改进Apriori算法在相同数据量不同支持度下的执行效率、以及相同支持度下不同数据量的执行效率.这里我们取最小支持度support=10%，confidence=50%（support（Xi→Yi）=|Xi∪Yi|，confidence（Xi→Yi）=|Xi∪Yi|/|Xi|，其中（Xi，Yi为事务集中同时包含Xi和Yi的事务数），实验数据见图2、图3.

图3 不同事务规模下算法执行的时间比较Fig.3 The analysis and comparison of the execution time of algorithms under different support degrees

由图2可以看出，在相同支持度下Apriori_ids算法的时间曲线低于Apriori算法，即得到改进的Apriori_ids算法时间开销小于Apriori算法，在支持度较小的情况下，效果更明显.

由图3可以看出，传统的Apriori算法随着频繁项集数量以及扫描数据集次数增多，执行时间有突变性的增加，而改进的Apriori_ids算法有效地应用了性质2及推论1，过滤了不满足条件的候选项集，减少了频繁项集数量以及数据集扫描次数，实验结果表明，Apriori_ids算法在性能优于Apriori算法，特别在支持度小和数据规模大时.

4 结束语

本文提出一种基于关联规则挖掘的入侵检测系统原型，利用改进的Apriori_ids算法，能从大量审计数据中快速提取出规律，有效提高算法的运行效率，解决入侵检测海量数据挖掘，存储优化工作，大大提高了入侵检测系统的性能.随着网络的进一步发展，云计算即将成为未来网络发展方向，而关联规则的置信度和支持度模型在网络动态实时化方面表现了不足，对入侵检测在实时性要求方面较差，因此，如何发展关联规则对并行计算或分布式计算的支持将是我们继续努力的主要方面，也是未来发展的趋势.

[1]Lee W K.A framework for constructing features and mod⁃els for intrusion detection systems[J].ACM Transactions on Inforrnation and System Security,2000,3(4):227-261．

[2]刘君强,孙晓莹,潘云鹤.关联规则挖掘技术研究的新进展[J].计算机科学,2004,31(1):110-113．

[3]Agrawa R,Imielinski T,Swami A.Mining Association Rules Between Sets ofItems in Large Databases[C]．Wash⁃ington DC,USA In Proceedings of the ACM SIGMOD Conf.on Management ofData(SIGMOD’93).New York:ACM Press,1993:207-216．

[4]区玉明,张师超,徐章艳,等.一种提高Apriori算法效率的方法[J].计锌机工程与设计,2004,25(5):846-848．

[5]Treinen J J,Thurimella R.A framework for the applica⁃tion of association rule mining in large intrusion detection infras tructures[C].you xiao ming.Recent Advance in In⁃trusion Detection May 2006.Berlin：Springer Verlag,2006:1-18．

[6]李清峰,杨路明,张晓峰,等.数据挖掘中关联规则的一种高效的Apriori算法[J].计算机应用与软件,2004,21(12):84-86.

[7]王卉,屈强.挖掘最大频繁项集的并行化策略[J].微电子学与计算机,2007,24(9):123-125．

[8]黄进,尹治本.关联规则挖掘的Apriori算法的改进[J].电子科技大学学报,2003,32(1):76-79．

[9]何海涛,吕士勇,田海燕.基于改进Apriori算法的护数据库入侵检测[J].计算机工程,2009,35(16):154-156.

[10]李家春,李之棠.神经模糊入侵检测系统的研究[J].计算机工程与应用,2001,17:37-38．

[11]王勇,何倩,杨辉华,等.面向连接网络入侵检测实验测试系统的研究[J].计算机应用,2006,26(增刊1):154-156.

Research on the Intrusion Detection Systems Based on the Improved Apriori Algorithm

CHEN Zhen
（Chaozhou Teacher's College，Hanshan Normal University，Chaozhou521012，China）

Main applications of data mining to network intrusion detection are reviewed，It describes the application theory of association rules analysis in network invasion monitoring and the latest research and improvements,and points out the existing problems and the direction for the future research.firstly，the strategy of the join step and the prune step was improved when candidate frequent（k+1）-itemsets were generated from frequent k-itemsets；secondly,the method of dealing with transaction was improved to reduce the time of pattern matching to be used in the Apriori algorithm；in the end,the method of dealing with data base was improved，which lead to only once scanning of frequent k-itemsets during the whole course of the algorithm.The experimental results of the improved algorithm show that the improved algorithm is more efficient than the original.

association rule；frequent itemsets；candidate item set；Apriori algorithm；Apriori_ids algorithm；intrusion detection system

TP 311.131

A

1674-4942（2012）01-0041-05

2011-11-29

黄 澜