Apriori关联规则算法在网络入侵检测中的研究与应用

杨丽萍

摘要：本文深入研究Apriori关联规则算法，并将该算法应用于网络入侵检测中，通过该算法可以发现网络环境中对主机端口的访问规则，从而利用访问规则可以检测非法的网络入侵。

关键词：关联规则；Apriori算法；网络入侵

中图分类号：TP311.13；TP393.08 文献标识码：A 文章编号：1007-9416（2018）08-0107-02

关联规则能够反映不同事物之间的相互依赖关系，如果一个事物的发生会影响其他事物的发生，那么这些事物之间就可能存在一定的关联关系，通过挖掘不同事物之间的关联关系，得到关联规则，利用关联规则就可以预测与某些事物相关联的其他事物的发生。关联规则挖掘算法可以被应用于市场营销、银行业、零售业、保险业、电信业、信息安全管理、网络入侵检测及公司经营管理等各个方面。

本文重点研究Apriori算法，深入分析算法的实现原理，并利用java语言实现了该算法，利用该算法发现网络中对主机端口的访问规则，可以检测非法的网络入侵。

1 Apriori算法分析

1.1 算法思想

Apriori算法多次扫描交易记录集，产生长度不同的频繁集。首先产生1-频繁集F1，在此基础上经过连接、修剪产生2-频繁集F2，直到无法产生新的频繁集则算法终止。在第i次循环中，也就是在产生i-频繁集Fi的过程中，首先产生i-候选频繁集的集合Ci，Ci中的每一个项集是对两个只有一个项不同的属于Fi-1的频繁集连接产生。连接后，还要根据Apriori的性质，即频繁集的子集一定是频繁的，来对Ci进行修剪，产生对应的Fi。

1.2 算法伪代码

输入：事务数据库T，最小支持度min_sup。

输出：所有频繁集Fi。

Ci：i-候选频繁集。

Fi：i-频繁集。

（1）F1=find_frequent_1_itemset（T）； //找到1-频繁集F1

（2）for（i=2；Fi-1≠；i++）{

（3）Ci=apriori_gen（Fi-1，min_sup）； //根据上一步的频繁集的集合选出候选集

（4）for each t∈T { //判断候选项集是否是频繁项集

（5）Ct=subset（Ci，t）；

（6）for each c∈Ct c.count++；

（7）}

（8）Fi={c∈Ci∣c.count> min_sup}；

（9）}

（10）return F=∪Fi；

第（3）步apriori_gen（Fi-1，min_sup）的算法如下：

输入：i-1频繁集Fi-1，最小支持度min_sup。

输出：i-候选频繁集Ci。

（3.1）for each f1∈Fi-1

（3.2）for each f2∈Fi-1

（3.3）if（（f1[1]=f2[1]）∧…∧（f1[i-2]=f2[i-2]）∧（f1[i-1]

（3.4）c= f1f2；//对两个只有一个项不同的属于Fi-1的频繁集进行连接

（3.5）if has_infrequent_subset（c，Fi-1）

（3.6）delete c；//如果某个候选项中包含非频繁子集，则将该候选项删除

（3.7）else Ci=Ci∪{c}；

（3.8）}

（3.9）return Ci；

第（3.5）步has_infrequent_subset（c，Fi-1）的算法如下：

输入：由Fi-1频繁集连接产生的Ci的每个子集c

输出：将包含非Fi-1频繁集的子集c从Ci中删除。

（3.5.1）for each（i-1）-subset n of c

//根据算法性质：候选集的子集一定是频繁的

（3.5.2）if n Fi-1 return TRUE；

else return FALSE；

2 Apriori算法实现

本文采用java语言实现该算法，主要包括以下几个方法：

//算法主程序

public Map apriori（ArrayList dataList）；

//找到1-频繁集L1

private Map findFrequentOneSets（ArrayList dataList）；

//根据上一步的频繁项集的集合选出候选集

private Map aprioriGen（Map setMap）；

//判断候选集是否是频繁项集

private boolean hasInfrequentSubset（String candidateSet， Map setMap）；

//由频繁项集产生关联规则

public Map getRelationRules（Map frequentSetMap）；

3 实验测试与分析

在网络攻擊过程中，通常是首先利用扫描工具探测系统的弱点，而对各个端口的扫描是常用的探测手段。可以将Apriori算法应用于网络端口扫描，发现异常的扫描行为，提前预防网络入侵，提高系统的安全性。

通过在一定时间段不断地获取网络数据包，在对网络数据包进行预处理后，得到客户端对端口的访问列表，如表1所示。

对于上表所示的访问端口记录集，设定最小支持度阈值supmin=2/10。利用Apriori算法产生频繁集的过程如下：

由项集I={20，21，23，80，1433，1434}的所有项目直接产生1-候选集C1，计算其支持度。去除支持度小于supmin的项集，形成1-频繁集F1，如表2所示。

利用F1中的各项目组合连接，来产生2-候选集C2，然后扫描记录集，以获得C2中各项集的支持度。去除支持度小于supmin的项集，形成2-频繁集F2，如表3所示。

利用L2中的各项目组合连接，来产生3-候选集C3，连接时只能将只差最后一个项目不同的项集进行连接。然后扫描記录集，以获得C3中各项集的支持度。去除支持度小于supmin的项集，形成3-频繁集F3，如表4所示。

重复上述步骤，则C4为空，所有频繁集都被找到，算法到此结束。此后，可以根据需要设定规则的最小可信度confmin，利用频繁项集产生强关联规则。

设定最小可信度confmin=0.6，则利用上述算法产生的强关联规则如下：

21 23 ->80：0.6666666666666666

80 ->21：0.7142857142857143

21 ->80：0.8333333333333334

23 ->80：0.6666666666666666

20 ->80：1.0

通过分析强关联规则，可以得到结论：如果客户端访问主机的20端口或21端口或23端口，却没有访问80端口，就很可能是进行攻击的扫描；若只访问80端口，却没有访问21端口，也可能是进行攻击的扫描；在同时对三个端口的访问中，除了21，23，80端口，对其余任意三个端口的同时访问则可能是进行攻击的扫描。

4 结语

本文深入分析Apriori算法，并将该算法应用于网络入侵中，利用该算法挖掘出网络中对主机端口的访问规则，通过与访问规则相比较，可以发现非法的网络入侵，提高系统的安全性。

参考文献

[1]陈志泊主编.数据仓库与数据挖掘[M].清华大学出版社，2009.

[2]陈国君主编.Java程序设计基础（第5版）[M].清华大学出版社，2015.

[3]王培吉，赵玉琳，吕剑峰.基于Apriori算法的关联规则数据挖掘研究[J].统计与决策，2011.