《基于关联规则挖掘的 SNMP 数据异常发现研究1.doc》由会员分享，可在线阅读，更多相关《基于关联规则挖掘的 SNMP 数据异常发现研究1.doc（6页珍藏版）》请在三一办公上搜索。
1、精品论文大集合基于关联规则挖掘的 SNMP 数据异常发现研究1张羽 1，王慧强 2，赖积保 3 哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨（150001） E-mail: bobo_zhy摘要：由于网络攻击手段的日趋隐秘化和多元化，简单的数据包观察已无法检测出它们，面对这种困境，本文提出了一种基于关联规则挖掘的 SNMP 数据异常发现方法。首先将关 系数据库转换为事务数据库，其次针对 SNMP 数据的特点，在经典的 Apriori 算法的基础上， 给出了一种改进的关联规则挖掘算法。最后，以 DOS 攻击所产生数据集为例，进行了测试。 结果表明此算法能够快速发现兴趣度较高的关联规则。 关键
2、词：SNMP；数据挖掘；关联规则；Apriori 算法中图分类号：TP3931.引 言近年来，很多人工智能的方法被应用于基于 SNMP 的网络数据异常发现，在这些人工 智能的方法中，数据挖掘技术的应用正受到越来越多的关注。众所周知通过 SNMP（简单网 络管理协议）网络管理系统的 MIB（管理信息库）中的各项属性可以方便的进行网络数据 分析和流量分析。然而，如何找到各种类型的属性间存在的关联？如何从大量的数据中发现 有用规律，最终找到攻击隐蔽的特征并加以标识？面对这些急需解决的问题，本文提出将关 联规则挖掘用于 SNMP 数据的异常发现，帮助检测出 MIB 中各属性数据的异常，及时发现 网络中
3、的各种攻击。关联规则挖掘是数据挖掘中的一个重要研究课题，对关联规则进行挖掘能够发现大量数 据的属性之间的相关联系。关联规则最重要的特点就是关联是自然组合的，这对发现所有属 性的子集存在的模式是非常有用的。如果能够发现网络攻击与 MIB 提供的网络中所有被管 设备信息之间的关系，如 ipInReceives（从所有接口收到的 IP 数据报数），tcpInSegs（TCP 段的输入数）等属性的变化之间存在的规则，那么就可以尽可能地发现网络异常和攻击行为。目前，大部分关联规则挖掘算法是针对布尔值属性的，而多值属性或多维规则更具普遍 性。介绍多维关联规则挖掘算法的文献很多，如元规则导致的挖掘算法，基于
4、遗传算法和蚂 蚁算法相结合的多维关联规则挖掘算法。关于增量式关联规则挖掘的研究也较多，Cheung D 等人提出的 FUP 和 FUP2 算法以及冯玉才等人的 IUA 算法，其算法框架与经典的 Apriori 一致。杨明等提出的 PGList 的增量式更新算法则提高了挖掘和维护的效率。本文在深入分析关系数据库中关联规则特点的基础上，吸收经典的 Apriori 算法思想， 形成一种在关系数据库中挖掘多维关联规则的较为高效的算法。该算法一方面克服了经典Apriori 算法不支持多维关联约束，降低了候选集的个数；另一方面，该算法仅需一次数据库扫描，克服了多次扫描造成的 I/O 开销。更重要地是它针对
5、 SNMP 数据的特点，挖掘出基 于 SNMP 的异常数据分析所感兴趣的规则。本文将进行 DOS 攻击实验，利用该数据集，发 现网络攻击与各属性数据之间的关联规则。1 本课题得到高等学校博士学科点专项科研基金项目（20050217007）；国防预研重点资助项目（413150*）； 武备预研基金资助项目（51416060104C*）的资助。- 6 -2.SNMP 信息数据预处理SNMP 信息数据在进行关联规则挖掘之前，要先进行数据分析，根据数据集的特点，对 数据格式进行转换。2.1 预处理方案通过分析发现与攻击相关的 SNMP 数据都是数值类型的，这样问题就得到了简化。为 了运用数值类型属性数据
6、来发现它们中的关联规则，必先对数值属性进行离散化。离散化的 一般方法是通过两个步骤实现的：1.概念分层的产生 对于数值属性，说明概念分层是困难的，这是由于数据的可能取值范围的多样性和数据值的更新频繁，并且有时这种人工的说明还非常随意。然而，自动概念分层就不存在上述问 题，不管它的取值是连续的还是离散的，都可以根据它的分布来分段，然后进行自动的概念 抽象提升，再人工加入特定的语义。通过分析，本文决定采用直方图分析的方法产生概念分层，它是一种最常见的均匀分布 数据的概念分层自动提取算法。例如，在等宽直方图中，将值划分成相等的部分或区间。直 方图分析算法递归地用于每一部分，自动地产生多级概念分层，直
7、到到达一个预先设定的概 念层数，过程终止。2.数值属性映射 产生概念分层之后，把与挖掘任务相关的属性根据预定义的概念分层映射到一个普通的字符集，每个字符作为一项，这样关系数据库就转换成事务数据库。针对基于 SNMP 数据特点，在关系数据库中同一属性离散化后的项之间不可能形成关 联，并且本文所感兴趣的规则仅仅是 MIB 中各属性与一个属性 X 的关联，而属性 X 则代表 网络中是否存在恶意攻击或扫描。因此，为区分出同一属性所产生的项，采用了一种特殊的 映射方法，例如，离散化的数值属性 X1 被映射到 m 个字符串集A1, A2, , Am，X2 被映 射到 n 个字符串集B1,B2, ,Bn，以
8、此类推，所有属性均能被映射成特定的字符串集合。 不难发现，第一个字母相同的项为同一属性内的项。2.2 转换实例下面是在网络遭受攻击和正常情况下，通过 SNMP 采集程序采集到的数据集，有 4 个 属性，10 个时间点，表 1 是映射表，表 2 是原始数据表，表 3 是转换后的数据表。映射表 是通过上面 2.1 中提到的直方图算法产生的。其中，X=0，无攻击；X=1，攻击。表 1 映射表Tab.1 Mapping table5ipInReceives10051005ipInReceives4900549005ipInReceives518770tcpInSegs10001000tcpInSegs
9、4900049000tcpInSegs51906A1A2A3B1B2B30tcpOutSegs22tcpOutSegs3838tcpOutSegsB 称为 T 中的关联规则，其中 A I， B I，AB= 。在事务集合 T 中，包含 A U B 的事务占全部事务的百分比称为 T 中关联规则 A=B 的支持度，记为 support(A=B)=P(A U B)=s。在事务集合 T 中，包含 A U B 的事务占包含 A 的事务的百分比称为 T 中关联规则 A=B的置信度，记为 confidence(A=B)=P(B/A)=c。若 T 中关联规则 A=B 同时满足：support(A=B)min_s
10、up( 最小支持度阈值) 且 confidence(A=B)min_conf（最小置信度阈值），则 A=B 称为 T 中的强关联规则。关联规 则挖掘就是在事务集合中挖掘强关联规则。3.1 算法思想在事务集合库中挖掘强关联规则主要包括两个步骤：一是找出所有频繁项集，即支持度 大于等于最小支持度阈值的项集，二是产生强关联规则。下面分别介绍本文对这两步骤的改 进工作。1.事务数据存储结构为了降低 Apriori 算法重复扫描数据库造成的 I/O 开销，频繁项集的发现采用基于内存 的挖掘算法。算法首先要把事务表映射成若干个一维数组，即事务数据库中每一项映射成一 个一维数组，一维数组元素个数由事务表中的
11、事务数确定。如一事务项出现在某一事物 TD 中，则该对应的数组元素值取逻辑值 true，否则取 false。12.频繁项集的挖掘在把每一事务项转换成数组后立即进行是否为频繁 1-项集的判断，即计算对应的一维 数组中逻辑值为 true 的数组元素个数，若其个数不小于定义的最小支持度计数，则其对应的 项属于频繁 1-项集，那么保留该数组，否则删除该数组以释放空间。1频繁 k-项集 Lk 的挖掘是在频繁 k-1-项集的基础上进行。先由 Lk-1 产生频繁 k-项集的候 选集 Ck，候选集的产生算法采用 Apriori 算法重的“连接”步算法。然后，“剪枝”步的算法由 三部分构成：1)将维内组合的候选
12、 k-项集删除，为第一次“剪枝”；2)将不包含属性 X（代表是否被攻击或扫描）的候选 k-项集删除，这一步正针对本文 所感兴趣的规则的特点而进行的，因为本文所感兴趣仅仅是 MIB 中各性能指标属 性与属性 X 的关联，为第二次“剪枝”，；3)采用 Apriori 算法的“剪枝”算法对候选集第三次“剪枝”。 最后对剪枝后的候选集进行是否为频繁项集的判断，即，将候选集中的项所对应的数组之间按元素次序进行逻辑与运算，若运算结果中逻辑值为 true 的个数不小于定义的最小支 持度计数，则该候选项为频繁 k-项集。当| Lk-1|=2 for each itemset li in lkif(supp(l
13、k)=minconf * supp(li)and (item j.at AT-LEFT li)and(item j.at AT -RIGHT (lk li) /支持度大于最小支持度阈值且出现位置符合限定条件output rule li=( lk li) /则产生规则with conf=supp(lk)/supp(li) and supp=supp(lk);本算法的优势在于：1 仅需一次扫描数据库，克服了 Apriori 多次扫描的 I/O 开销；2 对候选项集进行了“三次剪枝”，在很大程度上减少了候选集的个数；3 影响算法效率的关键运 算是逻辑运算，相对于其他运算效率要高很多；4 规则产生阶段
14、做了限制，能快速发现有趣 规则。4.实验结果与分析4.1 实验本次实验利用上文中提出的算法设计实现了基于 SNMP 数据异常发现模块，于 2008 年5 月 27 日 3：38：41，通过实验室的局域网网络采集某台装有 SNMP 代理的主机的 SNMP 数据，包括 D攻击数据与正常数据，从中抽取 10 条数据进行挖掘分析。数据预处理部 分如 2.2 中表 1，表 2，表 3 所示。由于数据集较小，设置最小支持度（minsup）20%，最小 置信度（minconf）为 80%。挖掘结果如下：表 4 挖掘结果表Tab.4 Mining result table规则ipInReceivestcpIn
15、SegstcpOutSegsX置信度支持度A5-10050-10000-20100%40%B49005-5177749000-5190638-1351100%30%C49005-5177749000-519062-38150%20%4.2 实验分析从表中可以看到规则 A 表达了这样一个信息：某个时间点，若 ipInReceives（从所有 接口收到的 IP 数据报数）属于5,1005），tcpInSegs （TCP 段的输入数）属于0,1000）并且 tcpOutSegs（TCP 段的输出数）属于0,2），那么网络很可能（100%）处于正常状态；若 ipInReceives 属于49005,5
16、1777），tcpInSegs 属于49000,51906）且 tcpOutSegs 属于38,135）， 那么可以得出网络很可能（100%）正在遭受攻击的结论。支持度较低的规则，在实际应用中应酌情考虑。5.结论本文针对 SNMP 数据特点，吸收 Apriori 算法思想，提出一种新的关联规则挖掘算法。 该算法仅需一次扫描数据库，克服了经典 Apriori 算法多次扫描的 I/O 开销；对候选集进行 了三次“剪枝”，大大减少了候选集的个数；并通过对规则中属性出现位置的限制，快速发现 有趣的规则，减少了无用规则的产生。最后，本文利用 DOS 攻击实验数据集测试了算法的 有效性。由于本文只是初步探
17、索了关联规则挖掘在 SNMP 数据异常发现中的应用，在以后 的工作中还需通过大量攻击或扫描试验进一步验证并改进该算法。参考文献1黄勇, 刘锋. 关系数据库中多维关联规则挖掘的一种新算法J.计算机应用与软件,2007, 24(10) :60-61. 2李虹,蔡之华. 关联规则在医疗数据分析中的应用J.微机发展,2003,13(6):94-97.3王选文,丁夷,范九伦. 关联规则挖掘在人事系统中的应用J.西安邮电学院学报,2001,6(1):21-23. 4吴今培,肖健华. 智能故障诊断与专家系统M.北京:科学出版社,1997.5杨海兰,程龙,吴功宜.基于 SNMP 进行数据挖掘的入侵检测系统研究
18、J.计算机工程,2004,30(2):20-22.6Agrawal R, Imielinski T, Swami AMining Association Rules between Sets of Items in Large Database C,In:Proceedings of the ACM SIGMOD Conference on Management of Data ,1993:207-216.7Ordonez C, Santana C A, de Braal L. Discovery Interesting Association Rules in Medical Data EB
19、/OLJ. A Method of SNMP Data Anomaly Detection Based onAssociation Rule MiningZhang Yu, Wang Huiqiang, Lai JibaoCollege Computer Science & Technology, Harbin Engineering University（150001）AbstractNetwork attack behaviors are increasingly secretive and complex, these can not be detected by simply obse
20、rving data packets. A method of SNMP data anomaly detection based on Association Rule Miningis put forward. Firstly, relation database is transformed into transaction database. Secondly, based on analyzing the characteristics of SNMP data and traditional Apriori algorithm, an improved AssociationRul
21、e Ming algorithm is given. Finally, some experiments are made with the dataset caused by DOSattack. The results show that the proposed algorithm is able to fleetly detect association rules of the upper interest measure.Key words: SNMP; data mining; association rule; Apriori algorithm作者简介：张羽 硕士研究生，研究方向为网络安全、异常检测。王慧强 博士，教授，博导，研究方向为可靠性理论、网络技术与信息安全。 赖积保 博士研究生，研究方向计算机网络、信息安全。
