基于apriori算法的IDS技术实现

王福新

摘 要：使用关联规则算法apriori与入侵检测相结合，并针对Apriori算法对数据库的描次数过多、系统的I/O负载大和产生大量的无关中间项集等弊端，提出了一种改进的Apriori算法，打破了传统的算法实现步骤减少了数据库的扫描次数，降低了系统I/O负载；实验表明，改进的Apriori算法能有效地提高运行速度和效率，同时提高入侵检测的效率与准确性。

关键词：关联规则；apriori算法；IDS

中图分类号：TP311.13 文献标识码：A 文章编号：1671-2064（2017）19-0018-04

1 关联规则挖掘算法

关联规则（Association rules）挖掘是从大量数据中挖掘发现其项目集（itemset）之间的关联或相关联系.关联规则挖掘问题是R.Agrawal等人于1993年在文献中首先提出的.关联规则是描述数据库中一组数据项之间的某种潜在关系的规则。

经典的apriori。在已经提出的诸多关联规则挖掘算法中，R.Agrawal和 R.Srikant在Apriori算法是挖掘布尔关联规则频繁项集算法中最有影响的.目前绝大多数的频繁项集挖掘算法都是以Apriori算法为核心，或是其变体，或是其扩展。

Apriori算法的名字基于這样的事实：算法使用频繁项集性质的先验知识，Apriori算法实际上是一种逐层搜索的迭代算法，k-项集用于探索（k+1）项集该算法将关联规则的发现分为两部分：

第一步是迭代出所有的频繁项集；

第二步是由频繁项集产生强关联规则，根据定义，这些规则必须满足最小支持度和最小置信度。

对于Apriori算法而言，它存在着本身难以克服的缺陷。

（1）多次扫描数据库，在Apriori算法的描述中，每生成一个候选项集，都要对数据库进行一次搜索.如果要生成最大长度为K的频繁项集，则要对数据库进行K次扫描，当数据库中存放大量的数据时，在有限的内存容量下，系统I/O的负载就会相当大，每次扫描数据库的时间就会很长，这样效率当然非常低。

（2）它的瓶颈在于它的巨大的候选集的生成，例如，104个频繁1-项集要生成107个候选2-项集要找尺寸为100的频繁模式，如{X1，X2，…，X100}，你必须先产生2100（1030个候选集，因此，优化Apriori算法主要在于减少其候选集的生成。

2 apriori与入侵检测

2.1 入侵检测

入侵检测系统（Intrusion Detection System IDS）可以定义为识别针对计算机或网络资源的恶意企图和行为并对此做出响应的系统.它通过对计算机网络或计算机系统中的若干关键点收集信息并对其进行分析，从中发现网络或系统中是否有违反安全策略的行为和被攻击的迹象。入侵检测系统是将进行入侵检测的软件与硬件的组合，它是一种主动的防护措施，它从系统内部和网络中收集信息，从这些信息中分析计算机是否有安全问题，并采取相应的措施。

2.2 基于apriori的入侵检测模型（见图1）

通过对网络信息进行预处理通过apriori提取用户行为特征或规则等，再对所得的规则进行归并更新，建立起规则库，依据规则库的规则对当前用户的行为进行模式匹配，判断用户的访问行为是否合法并将结果输出给用户。

3 apriori的优化

Apriori算法每次生成候选项目集后，又要回去扫描数据库来判断这些是否频繁项目集，来判断这些候选项目集是否频繁项目集，造成了I/O的开销很大，效率很低，因此，在算法的第一步对Apriori进行优化。

（1）优化方法一：根据频繁k-项集的支持事务来计算候选（k+1）-项集中候选项的支持度，进而找出候选集中的频繁项目，也就是说支持（k+1）-项集的事务必然也会支持它的k阶子集.换句话说，支持（k+1）-项集的所有k阶子集的事务必然也支持（k+1）-项集.这里我们定义：若集合D中有K+1个元素，那么由其中任何k元素组成的非空集合称为集合D的k阶子集.如果能够从所有k阶子集的支持事务中找出其交集即公共部分，那就相当于求出了（K+1）-项集的支持事务，这样就避免了对源数据库进行多次扫描，从而提高了算法的效率，以最小支持事务来作为剪枝的标准，我们定义最小支持事务为最小支持度（minsup）与数据库记录总数的乘积。

算法描述：TID事务的唯一编号，定义TIDS（Xk）是数据库中项集Xk支持的事务的集合，TIDS（Xk）={TID：TID是Xk支持的}，最小支持事务=minsup×|D|。

算法伪代码如下：

Procedure weight_apriori（Lk：find_frequent_k _itemset，S： descend power subset of Ck，TIDS（Ck）： set of Ck support transactions）

{

Scan D；

Find TIDS //扫描数据库，记录支持每个项目的事务

C1=Generate_C1（DB）；//生成候选1-项集

L1=find_frequent_1_itemset；//频繁1-项集

K=2；

While Lk-1≠ {

CK = apriori_gen （LK - 1 ） ；//生成新的候选集

For each candidates itemset C∈CK {

Ck.suptrans= TIDS（Ck）；

For each descend power subset S {endprint

Ck.suptrans= Ck.suptrans∩S.suptrans；}

C.count= |Ck.suptrans|；//计算支持事务集中的元素个数.

K++；

}

//计算加权支持度

Lk = {c ∈Ck | C.count ≥ wminsup*|D|}；

}

Return F=Uk Lk ；

}

function Apriori_Gen（ Lk ）{

For all itemset g1 ， g2 ∈ Lk do {

if then {

add c to Ck ；

For all k-1 项集 do //剪枝

if （） then delete c from Ck ；

}}

Return Ck ；

}

算法的有效性分析：对于Apriori算法而言，在每次生成候选频繁项目集后，要重复扫描数据库计算项目集支持度判断候选项目集是否频繁项目集，造成了系统的布必要开销，本算法只需要扫描一次数据库，通过对降阶子集支持的事务的交集进行计算，从而避免多次扫描数据库即可求出所有频繁项集，进而提高了算法的效率.关于权重的设定，对于权重的设定将直接影响关联规则的挖掘结果，对于不同属性的权重值的设定除了依赖于主观的设定以外还可以根据实际情况建立模型来给出。

（2）优化方法二：在生成候选项目集之前判断出某些候选项目集是非频繁项目集，则可以在再次扫描数据库计算支持度时不予考虑，这样计算候选项目集支持度的记录的数目小于数据库原来的数目，以达到提高算法的效率的目的。

算法的描述：

Procedure weight_apriori（Lk：find_frequent_k _itemset，Rm： set of rm_item）

{

C1=Generate_C1（DB）；//生成候选1-项集

L1=find_frequent_1_itemset；//频繁1-项集

K=2；

While Lk-1≠ {

CK = apriori_gen （LK - 1 ） ；//生成新的候选集

If RmCk

Delete Rm ；

K++；}

//计算加权支持度

Lk = {c ∈Ck | C.sup ≥ wminsup}；

Return F=Uk Lk

}

4 实验结果及分析

经典的apriori应用IDS结果。使用麻省理工学院的林肯实验室的一次分布式拒绝服务攻击的数据作为实验室数据，该数据使用基于网络的tcpdump嗅探器采集保存为XML格式的日志文档。

程序是使用C#语言进行编程实现的基于关联规则的入侵检测系统，该系统使用XML数据作为分析数据的来源，其中部分程序如下：

public void CreateItemsetSubsets（int Level， ItemsetArrayList itemSubset， ItemsetArrayList parentItemset，Database transactionsData）

{

int length = 0；

ItemsetArrayList childSubset = new ItemsetArrayList（1）；

ItemsetArrayList rulesItemset；

if（itemSubset.Count > Level）

{

foreach（ItemsetArrayList item in itemSubset）

{

ItemsetArrayList [] subsets = this.CreateItemsetSubsets（item）；

//仅有一个父项目用来生成关联规则

if（parentItemset == null）

{ parentItemset = item； }

if （subsets ！= null）

{ length = subsets.Length； }

else{ break； }

for（int count = 0； count < length； count++）

{

//向项目表中添加项目与子集

transactionsData.AddSubset（item，subsets[count]）；

childSubset.Add（subsets[count]）；

//仅向 ItemsetArrayList 类中添加unique值

//创建一个含有的支持度，信任度和关联规则的与子集相关的如

//父项-子集的规则项

rulesItemset = （parentItemset-subsets[count]）；

this.CreateItemsetRuleset（parentItemset， subsets[count]， rulesItemset，transactionsData）；

}

}

//為项目递归生成子集tendprint

childSubset.TrimToSize（）；

this.CreateItemsetSubsets（0， childSubset， parentItemset， transactionsData）；

}

}

由于tcpdump嗅探器保存下来的数据需要首先进行转换预处理.既进行离散化，通过实验得到一下结果.例如172.16.115.20， 202.77.162.213，tcp，1023，514。

通過试验我们得到了一系列的关联规则，如第84条规则。

202.77.162.213，tcp --> 514 63.1578947368421%

程序结果如图2。

5 结语

基于Apriori的加权关联规则算法是在Apriori算法基础上针对Apriori算法由候选项目集生成频繁项目集的过程进行的算法的优化。在Apriori算法的描述中每生成一个候选项集，都要对数据库进行一次扫描，因此需要多次对数据库进行扫描，当数据库中存放大量的事务数据时，在有限的内存容量下，系统I/O负载就会非常大，每次扫描数据库的时间就会很长，效率就非常低。

第一种优化方法只需要扫描一次数据库，然后通过统计后选项集Ck的K阶子集支持的事务来计算支持度的方法，减少了扫描数据库的次数，从而提高了Apriori算法的运行效率；第二种优化方法并没有从根本减少对数据库的扫描次数，只是通过减少生成频繁项目集中候选项目集中的记录个数来达到提高Apriori算法效率的目的，这种方法在在数据库的数据量很大时，效果并明显，因此比较而言，第一种方法的效率应该较高.而两种算法都是对经典apriori的效率改进，极大的提高了IDS的运行速度以及降低了其误报率。实验结果，见图3。

参考文献

[1]沈亮.网络入侵检测系统原理与应用[M].电子工业出版社，2013，（10）.

[2]崔贯勋，李梁，王柯柯，苟光磊，邹航.关联规则挖掘中Apriori算法的研究与改进[J]，计算机应用，2010（11）.

[3]薛静锋，祝烈煌.入侵检测技术[M].人民邮电出版社，2016，（1）.

[4]关心，王新.基于数据挖掘的入侵检测系统研究[J].信息技术，2007，（10）：100-103.

[5]章小龙.基于数据挖掘的入侵检测系统研究[J].沈阳工程学院学报（自然科学版），2007，（10）：364-366.

[6]宋世杰，胡华平，胡笑蕾，金士尧.数据挖掘技术在网络型异常入侵检测系统中的应用[J]. 计算机应用，2003，（12）：20-23.

[7]牛建强，曹元大.基于数据挖掘的IDS日志数据分析处理[J].计算机应用研究，2003：82-84.

[8]张译，刘衍珩，田大新，李川川，王媛.基于关联规则的入侵检测系统[J].吉林大学学报（信息科学版），2006，（3）：204-209.

[9]李川，张永辉译.Ian H.Witten Eibe Frank Mark A.Hall著.数据挖掘实用机器学习工具与技术[M].机械工业出版社，2014，（5）.endprint