基于Apriori算法的安全事件二级关联方法

◆唐湘滟 程杰仁 刘博艺 郑兆华 周静荷

（海南大学信息科学技术学院 海南 571101）

基于Apriori算法的安全事件二级关联方法

◆唐湘滟 程杰仁 刘博艺 郑兆华 周静荷

（海南大学信息科学技术学院 海南 571101）

安全信息的数据关联技术是目前网络安全领域的热点，国际上许多国家的安全机构都在大力研究安全事件关联技术来建立完善可靠的安全防御系统，保障国家利益。本文对网络安全事件关联进行了需求分析，将网络安全事件关联划分为4个子模块，对各个子模块进行了详细设计。采用基于因果关联方法的聚类对安全事件进行归并，将安全告警事件划分为具有逻辑因果关系的集合，然后利用基于Apriori算法的关联规则挖掘方法挖掘出各个安全告警事件集合之间的内在关联关系，实现了对于告警数据进行事件关联的模块功能，较好地提高了对组合攻击的关联效率。

网络安全; Apriori算法; 关联方法

0 前言

安全信息的数据关联技术最早开始于入侵检测研究技术中关于分布式IDS中告警的协同分析方法的研究，是目前网络安全领域的热点。国际上许多国家的安全机构都在大力研究安全事件关联技术来建立完善可靠的安全防御系统，保障国家利益。

1993年R．Agrawal首次提出关联规则的定义[1]，1994年提出了Apriori算法[2]，2000年韩家玮提出了FP-TREE算法[3]，两人的工作为关联规则挖掘技术提供了理论基础。2002年起R．Agrawal 负责的IBM Zurich研究所开始研制“Tivoli关联分析系统”[4]，预计2016年完成。美国国防部从1998年到2006年研制了“EMERALD”系统[4]，提供美国军方使用。美国的DARPA&NSF从2006年起利用数据挖掘关联技术进行IDS告警分析[4]并有偿向大型企业提供商业应用。法国国防部1999年推出“30年远景计划”，是一个具备入侵检测，报警，自动跟踪的MIRADOR项目[4]。国际上虽然已经将关联规则挖掘引入网络安全态势评估系统[5-7]，但是目前大多数系统的关联规则应用与安全事件关联模块是分离的，实现评估功能更多的是凭借高速数据存储技术和高速的巨型机，关联规则的应用大多在数据库中处理物理数据而不是在关联的核心模块中处理逻辑数据，关联还是主要依靠专家系统与人工判断，这样在很大程度上会限制了安全事件关联的效率。

近几年来，随着对于关联规则挖掘的重视和网络安全评估系统的建设，国内在相关领域出现了大量的研究成果[8-14]。华中科大李家春领导研究小组研发了分布式入侵告警关联技术分析系统，西安交通大学李辉提出了一种基于交互式知识发现的入侵事件关联方法。目前，清华大学，北京大学，国防科技大学，信息安全国家重点实验室，东南大学，南京大学，华南理工大学，哈尔滨工业大学等学校均在开展相关的课题研究[12-14]。瑞星公司已经推出了商业产品“SDS-1000 网络安全评估系统”。国内的大多数研究仍然是将安全事件关联与关联规则分离开进行研究，大多数的安全态势评估系统实际上还是在模式匹配方面进行研究。

1 基于Apriori算法的安全事件二级关联方法

基于Apriori算法的安全事件二级关联方法是首先通过事先定义的各种网络安全事件类型因果关联知识,采用因果关联算法对安全事件集聚类，形成因果事件集,然后利用Apriori算法对因果事件集进行关联挖掘，生成关联事件集。由于网络安全事件一般不会孤立存在，绝大多数网络安全事件相互之间具有一定的因果联系。基于这种固有的因果关系可以将描述网络安全事件地关联起来，进而形成可以描述网络安全事件之间关系的攻击场景。

1.1 因果关联模型

因果关联虽然可以揭示网络安全事件之间的关系，但是由于攻击场景的缺损和攻击场景的高噪声问题会阻碍安全人员对攻击场景的识别，甚至在一定程度上误导安全人员。为降低这些问题的影响，本文引入因果可信度（reliability）和支持度（Support）对因果关联程度较强的事件进行加权和累计。

设I={Ia，…，Im }是项集，其中的元素称为项（item）。记D为安全事件S的集合，这里安全事件S是项的集合，并且S∈I。对应每一个安全事件有唯的标识，记作E。设X是一个I中项的集合，如果X∈S，那么称安全事件S包含X。

设X为前提，Y为结果，X与Y有因果关系，记为X-〉Y，其中X∈I，Y∈I并且X与Y的交集是空集。则X-〉Y在安全事件数据库D中的支持度（Support）是安全事件集中包含X和Y的事件数与所有事件数之比，可信度（reliability）是包含X和Y的事件数与包含X的事件数之比。

为了简化的安全事件关联过程和通用性，本文通过匹配前提（prerequisite）和结果（consequence）形成安全事件之间的因果对应关系，将安全事件的前后事件特征进行抽象化处理，即将攻击场景中的原子攻击事件作为某一攻击抽象类集合的一个实例。一个安全事件抽象类A（attack）可以用一个五元组来描述，即C（E，P，R，C，O），E（eventType）为事件的类型标识，P（prerequisite）为攻击事件成功发生所需前提条件事件集合，记为P（E），R（reliability）为前提条件事件可信度集合，记为R（E），C（consequence）为攻击事件发生后可能产生的事件集合，记为C（E），它们可为单个原子谓词或谓词公式，谓词参数变量来自属性名集合O，一般至少包括源IP地址、目的IP地址、源端口和目的端口等。其中每一个属性名都有一个对应的论域。

1.2 关联规则模型

关联规则挖掘的任务是:给定一个因果关联事件集D，求出所有满足最小支持度min-sup和最小可信度min-conf的关联规则事件集，为安全态势评估提供有效的数据源。关联规则挖掘可以分解为两个子问题:求出D中满足最小支持度min-sup的所有频繁项目集; 利用频繁项目集生成满足最小可信度min-conf的所有关联规则。挖掘关联规则过程为两步:第一步产生所有的频繁项目（简称频繁集），即找出所有支持度不低于用户指定的最小支持度的项目集。第二步从已得到的频繁集中构造置信度不低于用户指定的最小置信度的规则。关联规则概念是由Agrawal等人在1993年率先提出的，并随后提出了Apriori算法，Apriori算法使用一种称作“逐层的迭代”的方法通过低维频繁项目集来产生高维频繁项目集。Apriori算法的核心思想见图1。

图1 Apriori算法

2 安全事件二级关联方法

基于Apriori算法的安全事件二级关联方法的伪代码描述见图2。

图2 基于Apriori算法的安全事件二级关联方法

3 测试与分析

3.1 测试环境和工具

测试环境硬件列表见表1，测试软件环境见表2。

表1 测试硬件列表

表2 测试软件列表

3.2 测试结果及分析

测试程序界面截图如图3，测试结果安全事件关联分析效率见图4，安全事件关联规则数量比较见图5。通过对测试结果的分析，得到了一下的一些结论:

在用户定义的可信度和置信度不变的情况下，算法的效率受数据库事件总量影响明显。

数据库事件数量越多，用户的置信度和可信度都应该相应减少，否则很难挖掘出足够多的符合用户需要的关联规则，基于相同的置信度和可信度，一般待挖掘事件集内的事件个数越多，越容易挖掘出更多的关联规则。用户能否在实践中设置适合的可信度参数，对于事件关联的结果有很大的影响。测试结果表明，事件关联模块的关联规则挖掘部分可以较好地实现Apriori算法，在输出的关联规则中标明了该规则的可信度和置信度。

图3 测试界面截图

图4 安全事件关联分析效率

图5 安全事件关联规则数量比较

4 结束语

本章对网络安全事件关联进行了需求分析，将网络安全事件关联划分为4个子模块，对各个子模块进行了详细设计。采用基于因果关联方法的聚类对安全事件进行归并，将安全告警事件划分为具有逻辑因果关系的集合，然后利用基于Apriori算法的关联规则挖掘方法挖掘出各个安全告警事件集合之间的内在关联关系，实现了对于告警数据进行事件关联的模块功能，较好地提高了对组合攻击的关联效率。不足之处是需要进一步优化Apriori算法，解决Apriori算法处理大规模数据库效率不高的问题。

[1]R.Agrawal,R.Srikant.Fast algorithms for mining associati on rules in large databases.Research Report RJ 9839,IBM Al maden Research Center,California,June 1994.

[2]JIAWEI HAN,JIAN PEI,YIWEN YIN,RUNYING M AO,Mining Frequent Patterns without Candidate Generation:A Frequent-Pattern Tree,Data Mining and Kno wledge Discov ery,8,53–87,2004.

[3]李芝棠.网络安全态势关联分析.CERNET,13.昆明,200 6.

[4]Bass T.Intrusion Detection Systems and Muhisensor Da ta Fusion:Creating Cyberspace Situational Awareness.Communi cations of the ACM,2000.

[5]CUPPENS F,LAMBDA OR.A language to model a database for detection of attacks.In:Proc.of Recent Advances in Intrusion Detection（RAID 2000）[C],2000.

[6]Yaxuan Qi,Lianghong Xu,Baohua Yang,Yibo Xue and Jun Li，Packet Classification Algorithms:FromTheory to Pract ice,Proc.of the 28th IEEE INFOCOM,2009.

[7]Bin Z,Gang T,Greg M.Combining Control-Flow Integ rity and Static Analysis for Efficient and Validated Data Sandb oxing[C].ACM Conference on Computer and Communication s Security（CCS）,2011.

[8]熊云燕，毛宜君.安全事件关联分析引擎的研究与实现.计算机工程，2006.

[9]HAN Jia wei，KAMBER M.数据挖掘概念和技术.范明，孟小峰译.北京机械工业出版社，2001.

[10]李家春，李芝棠.分布式入侵告警关联分析.计算机研究与发展，2004.

[11]徐勇等.基于XML数据的关联规则挖掘.计算机工程与设计，2006.

[12]王文娟，王杰等.入侵检测系统报警信息聚合与关联技术研究综述.信息安全，2006.

[13]Margaret H.Dunham等著，郭崇慧等译.数据挖掘教程.清华大学出版社，2005.

[14]彭雪娜，闻英友.网络安全信息关联与分析技术的研究进展.计算机工程，2006.

[15]Fu Z.,Ren K.,etc.(2016).Enabling Personalized Search ov er Encrypted Outsourced Data with Efficiency Improvement[J].IE EE Transactions on Parallel and Distributed Systems.Vol.27,PP.254 6 - 2559.

[16]Gu Bin,Victor S.Sheng.（2016）.A Robust Regularizatio n Path Algorithm for ν-Support Vector Classification[J].IEEE Tran sactions on Neural Networks and Learning Systems.Vol.1，PP. 1 - 8.

[17]Gu B.，Sun X.，etc.（2007）.Structural Minimax Proba bility Machine[J].IEEE Transactions on Neural Networks and Lear ning Systems.Vol.6，PP.1 - 11.

[18]Gu B.，Victor S.Sheng，etc.（2015）.Incremental Supp ort Vector Learning for Ordinal Regression[J].IEEE Transactions o n Neural Networks and Learning Systems.Vol.26，PP.1403 - 1416.

[19]Fu Z.，Sun X.，etc（2015）.Achieving Efficient Cloud S earch Services:Multi-Keyword Ranked Search over Encrypted Cl oud Data Supporting Parallel Computing[J].IEICE Transactions o n Communications.Vol.98，PP.190-200.

[20]Gu B.,Victor S.Sheng,etc.(2015).Incremental learning fo r ν-Support Vector Regression[J].Neural Networks.Vol.67，PP.14 0–150.

[21]Wen X.,Shao L.,etc.(2015).A rapid learning algorithm fo r vehicle classification[J].Information Sciences.Vol.295,PP.395–40 6.

国家自然科学基金（61363071）; 湖南省教育科学十二规划课题资助项目（XJK011BXJ004）; 海南大学博士启动基金（kyqd1328）; 海南大学青年基金（qnjj14444）; 海南省自然科学基金（20166217）; 海南大学研究生实践创新项目。