基于数据挖掘的入侵检测系统的改进与实现

0 引 言
    从Apriori算法执行过程可以了解到Apriori算法的缺点：一方面，在每一次产生候选项集时循环产生的组合过多，没有具体考虑不符合阈值的组合；另一方面，对每个项集计算支持度时要对整个数据库扫描一遍，对于分析网络数据包这样大型的数据库会增加I／O开销。这种开销是随着数据库的记录的增加呈几何级数的增长。现阶段人们开始探索一种能减少系统I／O开销的更为快捷的算法，相继提出了许多改进的算法。主要有Park等人提出的基于哈希技术的DHP算法，Savasere等人提出的基于划分技术的Partition算法，Toivonen提出的抽样算法，Sampling、Zaki等人提出的基于等价类和图论的MaxCique系列算法，S．Agarwal等人提出的采用有序树数据结构的TreeP-rojection算法以及Orlando等人提出的Apriori增强版的DCP算法等。而对于挖掘数据包是网络数据包时，数据源的特征属性较多而且数据包的记录数较大，这就需要必须选择合理的算法才能发现能描述用户特征的规则。

1 引用作用度的Apriori_lift算法
1．1 作用度
    作用度是采用相关分析描述规则内在价值的度量，它描述的是项集X对Y的影响力的大小。作用度越高表示X的出现对Y出现的可能性影响越大，作用度度量的是X与Y之间蕴涵的实际强度。
    作用度表示为：

   
1．2 Aprior=>lift算法的描述
    第一步：大项集的生成；
    第二步：采用作用度找出强关联规则。
    使用第一步找到的所有频繁项集产生期望的规则。为了获取强有效关联规则，在使用信任度的基础上增加作用度计算来度量规则的有效性。具体描述过程如下：
    (1)对于每个频繁K(K≥2)项集L，产生L的所有非空子集S；
    (2)对于项集L的每个非空子集S，规则：
    如果lift[S=>(L-S)]>1，则规则“S=>(L-S)”是强有效关联规则，输出。

2 算法性能比较
    在局域网环境中(如图1所示)捕获网络数据包2 000个，分别采用Apriori，Apriori_lift算法挖掘，其挖掘过程及结果如下：

    表3是实验采用的两个数据集Tcppro，Udppro。

    表4是二种算法在不同支持度(Supp)信任度(Conf)下的挖掘结果统计。

    由表4可知，在相同的作用度与支持度的情况下，Apriori，Apriori_lift算法挖掘得到的规则逐渐递减；在不同的作用度与支持度情况下，参数值越低挖掘出的规则越多，这主要体现在Apriori算法的挖掘上，而对于Apriori_lift算法当参数值达到一定阈值时，改变参数值对其挖掘结果影响不大，改善了挖掘规则遗漏的情况。
    由表4可以看出，Apriori算法和Apriori_lift算法的运行时间随挖掘规则变化的比较情况。Apriori算法随着挖掘结果中规则数的增长，时间上有数量级的提高，而Apriori_lift随着时间的增长，其挖掘出的规则数量增幅不大。而Apriori_lift存在额外的作用度比较的开销，在高支持度时，由于要处理的频繁项目及模式数目都较少，此时从挖掘结果上看Apriori_lift表现了比Apriori更好的性能。

3 挖掘结果分析
    以Apriori_lift算法挖掘数据集udppro为例，挖掘过程如下：
    过程一：挖掘数据源的生成。
    Udppro数据集经过数据预处理后生成了挖掘数据源Udpsource．txt，共计7 585条描述网络连接的记录，其记录格式如下：

    pro：UDP sip：192．168．0．1
    sport：67 dip：255．255．255．255 dport：68 lenth：315ttl：128
    过程二：算法挖掘
    (1)find association rules with the apriori algorithm    (2)reading f：＼mining＼udpsource．txt…[163 item(s)，7585 transaction(s)]done[0．13s]．
    (3)sorting and recoding items…[21 item(s)]done[0．01s]．
    (4)creating transaction tree…done[0．04s]．
    (5)checking subsets of size 1 2 3 4 5 done[0．00s]．
    (6)writing f：＼mining＼apriori．txt…[540 rule(s)]done[0．37s]．
    过程三：挖掘结果分析
    挖掘出540条规则，经过规则合并以及多属性并存的原则过滤之后筛选出17条规则如下：
    Apriori_lift挖掘结果

    (1)lenth：58 sport：137 dip：202．198．178．255 ttl：128 dport：137 pro：UDP
    (2)sip：192．168．0．22 dport：161 ttl：128pro：UDP dip：202．198．181．65
    (3)dport：138 sport：138 dip：202．198．178．255 ttl：128 pro：UDP
    (4)dip：202．198．181．65 ttl：127 sip：202．198．178．131 dport：161 pro：UDP
    (5)sport：4126 sip：192．168．0．22 dip：202．198．181．65dport：161 ttl：128
    (6)sport：2039 ttl：127 sip：202．198．178．131 dip：202．198．181．65 dport：161 ttl：127
    (7)lenth：58 sport：137 dip：202．198．178．255 dport：137
    (8)sip：192．168．0．22 dip：202．198．181．65 dport：161ttl：128
    (9)sport：138 dip：202．198．178．255 dport：138 ttl：128 pro：UDP
    (10)sip：202．198．178．131 sport：4126 dip：202．198．181．65ttl：127 dport：161 pro：UDP
    (11)sip：202．198．178．131 sport：2039 dip：202．198．181．65dport：161 ttl：127 pro:UDP
    (12)sport：137 dip：202．198．178．255 dport：137 lenth：58ttl：128
    (13)sip：192．168．0．22 dip：202．198．181．65 dport：161 ttl：128 pro：UDP
    (14)sport：138 dip：202．198．178．255 dport：138 lenth：58ttl：128 
    (15)sip：202．198．178．131 dip：202．198．181．65 dport；161ttl：127 pro：UDP
    (16)sport：4126 sip：192．168．0．22 dip：202．198．181．65dport：161 ttl：128 pro：UDP
    (17)sip：202．198．1 78．65 sport：2039 dip：202．198．178．131dport：161 ttl：127 pro：UDP
    对于以上挖掘结果归类如下：
    规则归类：
    类一：规则1，3，7，9，12，14。
    类别特征：dip：202．198．178．255 sport：137／138dport：137／138(sport=dport)
    pro：udp ttl：127／128 lenth：58
    类二：规则4，6，10，11，15，17。
    类别特征：sip／dip：202．198．178．131 sport：2300／4126 dip／sip：202．198．181．65
    dport：161 ttl：128／127 pro：udp
    类三：规则2，5，8，13，16。
    类别特征：sip／dip：192．168．0．22 sport：4126 dip／sip：202．198．181．65 dport：161
    ttl：128／127 pro：udp
    根据图1网络实验环境可知202．198．178．131是IP192．168．0．22的网关，故规则类二与类三可以合并为一类规则。
    过程四：挖掘结果说明
    规则类一说明：137，138是UDP端口，当通过网上邻居传输文件时用这两个端口，137端口是NetBIOS名称UDP。138端口是NetBIOS数据报UDP
    规则类二说明：子网主机192．168．0．22通过网关202．198．178．131与外部网主机202．198．181．65进行SNMP通信。

4 结 语
    对基于支持度一信任度挖掘的关联规则有效性进行了分析，指出在挖掘过程中仅考虑支持度和信任度的不足．产生的关联规则不一定是有效有趣的，甚至可能是欺骗性的，具有误导作用。因此引入相关性分析来衡量规则，大大增强了规则的有效性。