论文部分内容阅读
[摘 要] 针对关联规则挖掘算法在处理海量数据的过程中存在的效率低、需要反复访问数据库等,在入侵检测系统产生误报、效率低下等问题。提出了基于关联规则挖掘算法的ALT算法,设计了基于ALT算法的入侵警报检测系统模型,通过实验证明ALT算法在减少入侵警报的数量和降低误报率等方面明显优于其它算法。
[关键词] ALT算法 入侵检测 数据挖掘 警报分析
引言
入侵检测技术是信息网络安全技术的重要组成部分，而数据挖掘本身是一项通用的知识发现技术,目的是从海量数据中提取出对解决问题感兴趣的数据信息 。Wenke Lee于1999年首次将数据挖掘技术引入入侵检测,提高入侵检测系统(IDS)的准确性和自适应性。近年来,由于入侵检测技术对实时性要求较高，传统的IDS效果都不明显。这里提出一种改进的高效关联挖掘算法——ALT算法,将其应用到入侵警报分析过程中,在保证入侵检测实时性的前提下,减少侵警报的数量、降低误报率,最终达到提高入侵检测性能的目的。
一、ALT算法原理
ALT算法原理在于先求取所有的最大频繁项目集，然后依次求取每一个最大频繁项目集的子集，从而得到频繁项目集。
ALT算法求最大频繁项目集如下：
输入：事务数据库，最小支持度；
输出：最大频繁项目集(Answer)。
(1)计算最小支持计数，最小支持计数(Minsup)＝最小支持度×事务数；(2)生成频繁1-项目集L，及其对应的链表族；(3)依次处理频繁K-项目集对应的链表，据此得到最大频繁项目集。
通过频繁项目集分析,发现其中隐藏的异常模式,进而进行入侵检测。
1.关联规则挖掘。关联规则挖掘算法中，最有影响的是Agrwal和Srikant于1994年提出的Apriori算法。但缺陷也十分明显。针对Apriori算法的缺陷,文献提出FP2Growth算法。该算法采用分而治之策略,将发现长频繁模式的问题转换为递归发现一些短模式。把数据库中的频繁项集压缩进一棵频繁模式树( FP2tree) 并分化成条件库,对这些条件库分别进行挖掘，大大降低了搜索开销,大约比Apriori算法快一个数量级。
2.ALT算法思想及实现步骤。ALT算法的基本思想是该算法只需遍历事务数据库一次,生成频繁项目集簇,采用链表簇数据结构来存贮,通过指针来链接簇中的下一链表,生成新的频繁项目集……。大大降低了算法存储结构的复杂度,提高算法的挖掘效率。其实现步骤如下：
首先，对事务数据库进行处理，遍历事务数据库一次，生成频繁1-项目集。并由此可以得到频繁2-项目集，频繁3-项目集，……，频繁k项目集。
其次，对于频繁i(1≤i≤k)-项目集，采用链表簇数据结构存贮。簇中的每一链表用来表示频繁i-项目集各项目的信息，表头节点(patternData)和表节点(tidData)存储结构如图1所示。
再次，对项目集簇进行处理。如图1所示，处理完一个项目集，用pattern来存储频繁i-项目集某一项目，通过nextL指针来链接簇中下一链表； 用newed来标示项目集pattern域是否生成了新的频繁项目集，同时也作为最大频繁项目集判断条件。
最后，求最大频繁项目集,获取频繁项目集。初始值置为false，若由pattern域产生了新的频繁项目集，其值变为true，当新的频繁K+1项目集的链表族生成后，若某频繁k项目集对应newed域值仍然为false，则该频繁-k项目集链表对应的pattern域值为一最大频繁项目集。依次求取每一个最大频繁项目集的子集，从而得到频繁项目集。
二、系统设计与实现
1.系统设计思想。入侵警报分为正常警报和异常警报，本文提出的ALT算法入侵检测分析系统是利用数据挖掘算法从正常警报数据中提取描述正常警报行为模式的关联规则,通过分析入侵警报,提取出真正攻击的异常警报,减少入侵检测系统的警报数量,降低误报率。最终生成相应的频繁项目集和关联规则,数据挖掘过程的流程图如图2所示。
2.系统框架结构。基于上述的设计思想，入侵分析系统模型包括警报采集模块、提取模块、预处理模块、数据挖掘模块和分析模块。利用关联规则挖掘算法对入侵检测系统产生的警报数据进行过滤，提取出包含攻击的入侵警报,以达到减少警报数量、降低误报率的目的。系统总体框架如图3所示。各模块功能如下:
(1)采集模块。将网卡置于混杂模式,捕获并分析网络数据包，对异常的数据存入警报数据库并报警产生的警报。(2)提取模块。从警报数据库中提取出系统需要的字段。(3)预处理模块。对提取的警报数据对应的IP地址由数值型转化为点分十进制的标准IP地址格式,将协议由数值型转化为可读性较好的字符串表示。(4)数据挖掘模块。利用ALT算法挖掘经过预处理的正常警报数据,生成相应的频繁项目集。(5)分析模块。分析、判断警报是否正常,若正常,利用数据挖掘模块更新关联规则集,否则存入异常警报数据库并报警。
三、实验结果和分析
1.算法执行效率模拟实验。为了说明ALT算法的执行效率,本文在同样的实验环境下将其与Apriori、FP2Growth算法进行了比较。
实验环境: P4 3.0 GHz处理器, 320 GB硬盘, 512MB内存,Windows XP操作系统,VC++6.0开发环境,实验数据集T10 I4D100K。算法执行时间对比结果如表1所示，对比结果可以看出，在相同的支持度下, ALT算法所用的执行时间比其他算法要少(尤其是在支持度较小的情况下) 。因此算法在执行效率方面具有明显的优势。
2.系统模拟实验。实验数据采用林肯实验室的DARPA99入侵检测评估数据集在LAN中进行，运行Snort的主机配置同3.1。前台开发环境采用VC++6.0企业版，后台数据库采用SQL2000。实验结果如表2所示。其中Original表示直接由入侵检测系统产生的警报数量，Abnormal表示经过警报分析处理后的警报数量。从图示的实验结果可以看出，系统在警报数量的精简方面效果较好，警报数量得到了降低，同时减少了误报率。
四、结语
本文针对传统算法在入侵检测系统产生的警报数量多、误报以及效率低下等问题。提出基于关联规则的改进算法——ALT算法，设计了基于ALT算法的入侵警报检测系统模型。 该模型借助特殊数据结构实现了最大频繁项目集的挖掘，实现了关联规则的快速发现。最后，通过实验证明了ALT算法在减少入侵警报的数量和降低误报率等方面明显优于Apriori和FP2Growth算法。
参考文献:
[1]AGRAWAL R, IMIEL IENSKI T, SWAMIA. Mining association rulesbetween sets of items in large databases [C]//Proceedings of the ACM SIGMOD Conference on Management of data. New York: ACMPress, 1993: 207 - 216
[2]AGRAWAL A,MANN ILA H, SR IKANT R, et al. Fast discovery of association rules [Z].Cambridge: AAA I Press/M IT Press,1996:307～328
[3]HAN J, PEI H, YIN Y. Mining frequent patterns without candidate generation[C]//2000ACM2SIGMOD.New York: ACM Press,2000
[4]BORGELT C. Efficient implementations of a priori and eclat [C ] / /Proceedings of the IEEE ICDM Workshop on Frequent ItemsetMining Implementations. Melbourne: IEEE Press, 2003
[5]WANG X M, BORGELT C, KRUSE R. Fuzzy frequent pattern discovery based on recursive elimination[C]//ICMLA 2005. New York: IEEE Press, 2005: 391～396
[6]BORGELT C. Keeping things simple: Finding frequent item sets by recursive elimination[C]//OSDM 2005.New York: ACM Press,2005: 66～70
[7]冯玉才 冯剑琳:关联规则的增量式更新算法[J].软件学报，1998，9(1):301～306
[8]IBM Almaden Research Center. Synthetic data generation code for associations and sequential patterns [EB/OL].[2008-02-15].http://www. almaden. ibm. com / software /quest/ resources/ index.shtml
[关键词] ALT算法 入侵检测 数据挖掘 警报分析
引言
入侵检测技术是信息网络安全技术的重要组成部分，而数据挖掘本身是一项通用的知识发现技术,目的是从海量数据中提取出对解决问题感兴趣的数据信息 。Wenke Lee于1999年首次将数据挖掘技术引入入侵检测,提高入侵检测系统(IDS)的准确性和自适应性。近年来,由于入侵检测技术对实时性要求较高，传统的IDS效果都不明显。这里提出一种改进的高效关联挖掘算法——ALT算法,将其应用到入侵警报分析过程中,在保证入侵检测实时性的前提下,减少侵警报的数量、降低误报率,最终达到提高入侵检测性能的目的。
一、ALT算法原理
ALT算法原理在于先求取所有的最大频繁项目集，然后依次求取每一个最大频繁项目集的子集，从而得到频繁项目集。
ALT算法求最大频繁项目集如下：
输入：事务数据库，最小支持度；
输出：最大频繁项目集(Answer)。
(1)计算最小支持计数，最小支持计数(Minsup)＝最小支持度×事务数；(2)生成频繁1-项目集L，及其对应的链表族；(3)依次处理频繁K-项目集对应的链表，据此得到最大频繁项目集。
通过频繁项目集分析,发现其中隐藏的异常模式,进而进行入侵检测。
1.关联规则挖掘。关联规则挖掘算法中，最有影响的是Agrwal和Srikant于1994年提出的Apriori算法。但缺陷也十分明显。针对Apriori算法的缺陷,文献提出FP2Growth算法。该算法采用分而治之策略,将发现长频繁模式的问题转换为递归发现一些短模式。把数据库中的频繁项集压缩进一棵频繁模式树( FP2tree) 并分化成条件库,对这些条件库分别进行挖掘，大大降低了搜索开销,大约比Apriori算法快一个数量级。
2.ALT算法思想及实现步骤。ALT算法的基本思想是该算法只需遍历事务数据库一次,生成频繁项目集簇,采用链表簇数据结构来存贮,通过指针来链接簇中的下一链表,生成新的频繁项目集……。大大降低了算法存储结构的复杂度,提高算法的挖掘效率。其实现步骤如下：
首先，对事务数据库进行处理，遍历事务数据库一次，生成频繁1-项目集。并由此可以得到频繁2-项目集，频繁3-项目集，……，频繁k项目集。
其次，对于频繁i(1≤i≤k)-项目集，采用链表簇数据结构存贮。簇中的每一链表用来表示频繁i-项目集各项目的信息，表头节点(patternData)和表节点(tidData)存储结构如图1所示。
再次，对项目集簇进行处理。如图1所示，处理完一个项目集，用pattern来存储频繁i-项目集某一项目，通过nextL指针来链接簇中下一链表； 用newed来标示项目集pattern域是否生成了新的频繁项目集，同时也作为最大频繁项目集判断条件。
最后，求最大频繁项目集,获取频繁项目集。初始值置为false，若由pattern域产生了新的频繁项目集，其值变为true，当新的频繁K+1项目集的链表族生成后，若某频繁k项目集对应newed域值仍然为false，则该频繁-k项目集链表对应的pattern域值为一最大频繁项目集。依次求取每一个最大频繁项目集的子集，从而得到频繁项目集。
二、系统设计与实现
1.系统设计思想。入侵警报分为正常警报和异常警报，本文提出的ALT算法入侵检测分析系统是利用数据挖掘算法从正常警报数据中提取描述正常警报行为模式的关联规则,通过分析入侵警报,提取出真正攻击的异常警报,减少入侵检测系统的警报数量,降低误报率。最终生成相应的频繁项目集和关联规则,数据挖掘过程的流程图如图2所示。
2.系统框架结构。基于上述的设计思想，入侵分析系统模型包括警报采集模块、提取模块、预处理模块、数据挖掘模块和分析模块。利用关联规则挖掘算法对入侵检测系统产生的警报数据进行过滤，提取出包含攻击的入侵警报,以达到减少警报数量、降低误报率的目的。系统总体框架如图3所示。各模块功能如下:
(1)采集模块。将网卡置于混杂模式,捕获并分析网络数据包，对异常的数据存入警报数据库并报警产生的警报。(2)提取模块。从警报数据库中提取出系统需要的字段。(3)预处理模块。对提取的警报数据对应的IP地址由数值型转化为点分十进制的标准IP地址格式,将协议由数值型转化为可读性较好的字符串表示。(4)数据挖掘模块。利用ALT算法挖掘经过预处理的正常警报数据,生成相应的频繁项目集。(5)分析模块。分析、判断警报是否正常,若正常,利用数据挖掘模块更新关联规则集,否则存入异常警报数据库并报警。
三、实验结果和分析
1.算法执行效率模拟实验。为了说明ALT算法的执行效率,本文在同样的实验环境下将其与Apriori、FP2Growth算法进行了比较。
实验环境: P4 3.0 GHz处理器, 320 GB硬盘, 512MB内存,Windows XP操作系统,VC++6.0开发环境,实验数据集T10 I4D100K。算法执行时间对比结果如表1所示，对比结果可以看出，在相同的支持度下, ALT算法所用的执行时间比其他算法要少(尤其是在支持度较小的情况下) 。因此算法在执行效率方面具有明显的优势。
2.系统模拟实验。实验数据采用林肯实验室的DARPA99入侵检测评估数据集在LAN中进行，运行Snort的主机配置同3.1。前台开发环境采用VC++6.0企业版，后台数据库采用SQL2000。实验结果如表2所示。其中Original表示直接由入侵检测系统产生的警报数量，Abnormal表示经过警报分析处理后的警报数量。从图示的实验结果可以看出，系统在警报数量的精简方面效果较好，警报数量得到了降低，同时减少了误报率。
四、结语
本文针对传统算法在入侵检测系统产生的警报数量多、误报以及效率低下等问题。提出基于关联规则的改进算法——ALT算法，设计了基于ALT算法的入侵警报检测系统模型。 该模型借助特殊数据结构实现了最大频繁项目集的挖掘，实现了关联规则的快速发现。最后，通过实验证明了ALT算法在减少入侵警报的数量和降低误报率等方面明显优于Apriori和FP2Growth算法。
参考文献:
[1]AGRAWAL R, IMIEL IENSKI T, SWAMIA. Mining association rulesbetween sets of items in large databases [C]//Proceedings of the ACM SIGMOD Conference on Management of data. New York: ACMPress, 1993: 207 - 216
[2]AGRAWAL A,MANN ILA H, SR IKANT R, et al. Fast discovery of association rules [Z].Cambridge: AAA I Press/M IT Press,1996:307～328
[3]HAN J, PEI H, YIN Y. Mining frequent patterns without candidate generation[C]//2000ACM2SIGMOD.New York: ACM Press,2000
[4]BORGELT C. Efficient implementations of a priori and eclat [C ] / /Proceedings of the IEEE ICDM Workshop on Frequent ItemsetMining Implementations. Melbourne: IEEE Press, 2003
[5]WANG X M, BORGELT C, KRUSE R. Fuzzy frequent pattern discovery based on recursive elimination[C]//ICMLA 2005. New York: IEEE Press, 2005: 391～396
[6]BORGELT C. Keeping things simple: Finding frequent item sets by recursive elimination[C]//OSDM 2005.New York: ACM Press,2005: 66～70
[7]冯玉才 冯剑琳:关联规则的增量式更新算法[J].软件学报，1998，9(1):301～306
[8]IBM Almaden Research Center. Synthetic data generation code for associations and sequential patterns [EB/OL].[2008-02-15].http://www. almaden. ibm. com / software /quest/ resources/ index.shtml