基于改进Apriori算法的审计日志关联规则挖掘

1、基于改进apriori算法的审计日志关联规则挖掘摘要：针对安全审计系统中存在的智能程度低、 日志信息没有充分利用的问题，提出一个基于关联规 则挖掘的安全审计系统。该系统充分利用已有审计曰 志，结合数据挖掘技术，建立用户及系统的行为模式 数据库，做到及时发现异常情况，提高了计算机的安 全性。在传统apriori算法的基础上提出一种改进的 eapriori算法，该算法可以缩小待扫描事务集合的范 围，降低算法的时间复杂度，提高运行效率。实验结 果表明基于关联规则挖掘的审计系统对攻击类型的识 别能力提升在10%以上，改进的eapriori算法相比经 典apriori算法和fpgrowth算法在性能上得

2、到了提 高，特别是在大型稀疏数据集中最高达到51%。关键词：安全审计系统；审计日志；数据挖掘；关联规则 挖掘；apriori算法中图分类号：tp391.4文献标志码：a 0引言随着计算机技术的快速发展，网络传播带来开放 性，计算机操作系统也面临着越来越多的安全威胁。计算机系统、网络系统甚至整个信息技术基础设施的 安全性，成为一个亟待解决的问题。除却防火墙隔离、 入侵检测，安全领域的另一个重要的技术研宄方向就 是安全审计1。伴随着一系列新的攻击的产生，对于 审计技术的要求随之提高。目前，安全审计的主要工 作是在事前记录、事后追踪，记录用户的操作行为作 为证据2，这对于获悉用户行为、检测安全隐患、

3、进 行事后追查和分析都具有十分重要的意义。安全审计 员为系统管理员提供及时的警告信息，实现对系统事 件的追踪、审查、统计和报告3。审计系统对用户及操作系统的行为判断都是基于 采集到的用户相关操作以及系统各关键路径上的状 态，最终生成审计日志。虽然审计系统不断地进行记 录，拥有丰富的数据信息，但是对这些数据的利用却 仍然非常有限，这事实上是一种资源的浪费。本文提 出通过建立独立于用户平台的用户审计模块，使用改进的apriori算法，缩短运行时间，提高算法效率，提 取出可靠性强的关联规则，挖掘审计日志中蕴藏的状 态信息，建立行为规则库并及时更新，提升用户平台 识别攻击的能力，为审计系统追溯攻击者提

4、供证据， 进一步提高操作系统的安全性。1关联规则挖掘1.1数据挖掘数据挖掘作为一种从大量初级数据中发现潜在规 则和有价值知识信息的技术，是数据库知识发现 (knowledge discovery in database， kdd)中的一 个步骤4，也是基于多个领域的理论和技术方法，例 如人工智能、机器学习、并行计算、数学分析等。在 当今信息爆炸的时代环境下，数据量呈指数增长，数 据挖掘技术变得越来越流行，就是为了从大量的数据 源中获取有用的信息。过去的十年间，很多挖掘方法 都被提出并得到应用，关联规则挖掘得益于它的广泛 适用性而备受关注。在安全操作系统中同样存在许多 没有充分利用的知识数据，本

5、文结合安全操作系统的 审计日志，利用数据挖掘的方法获取用户和系统的行 为模式5。1.2关联规则关联规则最早由agrawal等6-7提出，是一个用 来从原数据中发现令人感兴趣的规则的方法，是近年 来数据挖掘的研宄方向之一。经典的apriori算法用于 关联规则挖掘，但由于该算法在产生关联规则时需要 首先生成大量的规则集，效率不高，在2000年由han 等8提出了基于fptree生成频繁项目集的 fpgrowth算法，只需要扫描两次原始数据库，提高了频繁项目集的挖掘效率。把原始数据库映射成内 存中的一棵fptree，采用共享前缀对原数据库进行 极大的压缩，使得较小的数据库可以在内存中完成挖 掘。类

6、似的算法也有提出，比如c0fitree9，但是 这些算法都需要驻留在内存中，所以会受到系统内存 不足的限制。关联规则可以在评价重要关联时提供有意义的信 息，比如：从心肌梗塞的病例登记中找出血液和疾病 史之间的关系10，khalili等11利用apriori算法建 立利用临界状态测定工业入侵的系统检测方法，在不 访问数据库的情况下推理产生所有关联规则12，在 保护各自隐私的情况下进行分布式数据库的数据挖掘 13，rozenberg等14研究了垂直分区分布式数据库 的关联规则挖掘，ding等15提出一种基于目标关联 挖掘的恶意软件快速检测算法。2基于日志挖掘的审计系统当前的审计系统存在信息记录过于

7、简单、机械， 对曰志信息利用率低，系统智能程度低，警告功能缺 失等问题16，因此需要结合其他技术，如人工智能、 数据挖掘等，为安全审计提供更多解决方法，理想的 审计系统基于这样一个理论基础，任何一种偏离预期 的系统状态和违反规定的操作行为都应该被记录下来，并在事后及时发现危险进行弥补。然而，这是建 立在对历史攻击方法和系统漏洞知识积累的基础上的 方法，因此需要建立包含上述知识信息的行为模式数 据库。1所示为基于日志挖掘的安全审计系统，该安 全审计系统可以提供以下功能：审计事件统计、异常 情况分析、系统报警等，并对上述审计记录进行统一 检索、分析处理，提供有效的日志检索查询机制，发 现潜在的攻击

8、征兆，为系统安全事件的事后追踪提供 证据。安全审计系统由硬件及软件组成，通过收集和分 析计算机系统中各关键点的日志信息，建立用户的行 为模式，同数据库中已知的行为模式进行比对，检查 系统可能遭受的入侵或攻击，描述违规操作中各步骤 之间的关系，及时发现系统中用户的行为是否违反安 全策略。该系统包括用户平台审计代理、信息收发处 理模块和用户审计模块3个部分。1）用户平台审计代理。部署于用户平台，用于收 集用户的日志文件，按照策略定期从日志文件中取出 这些批量数据，封装打包后传输给位于安全域的用户 审计模块，为其提供数据支持。同时，将当前记录曰 志同数据库中行为模式进行匹配，根据判定结果作出适当响应

9、。操作系统主要对用户平台的启动、软件安 装/加载/卸载和运行、设备打开/关闭、网络连接、文 件输出/拷贝/修改、密钥/算法管理等关键操作以及操 作系统关键动作进行记录，将这些数据实时地存入用 收发处理模块。部署于安全域，负责接收用户平台审 计代理发送的审计日志，确认它们是安全可信的，然 后上传给用户审计模块，经过分拣和预处理后，提交 审计处理；下载用户审计模块的挖掘结果，即用户审 计模块的行为模式数据库，为安全监控提供保障。户平台日志文件并进行汇总和分析2）信息3）用户审计模块。部署于安全域，可进一步划分 为审计数据预处理、审计数据分析和行为模式数据库 3个部分：第1部分负责将信息收发处理模块

10、发送的 用户平台审计数据进行过滤、分拣、重组，形成统一 的格式存入安全数据库；第2部分负责对审计日志数 据进行挖掘、分析，提取审计日志的特征集和规则集， 同时提供多条件下的审计日志查询；第3部分负责建 立操作系统中安全或危险的用户行为模式，及时更新 数据库中的用户行为模式信息。3关联规则挖掘算法关联规则挖掘可以用来在数据中发现各项集之间 可信的、有代表性的关联规则，挖掘过程可以分为以 下两个步骤：1）发现频繁项集。找出所有支持度不低 于最小支持度的最大频繁项集。2）生成强关联规则。 从最大频繁项集中找出满足最小可信度的规则17。事实上，第1）步寻找所有最大频繁项集是整个过程 的关键步骤。3.1

11、传统的apriori算法该算法采用广度优先搜索找出频繁1项集，经过 多次迭代，将（k-1）项集同自身连接得到候选k项集， k=2，3，1; 1代表最大频繁项集的长度，并根据 最小支持度剪枝，最终得到满足条件的频繁项集。 apriori算法是挖掘频繁项集的一个重要算法，它有一 个经常应用于剪枝的定理18。定理1频繁项集的子集也必须是频繁项集，非频 繁项集的超集肯定是非频繁项集。apriori算法为了生成所有频繁项集，使用了递归 的方法，该算法的伪代码可以表示如下。min_support表示最小支持度；l1表示所有频繁1 项集组成的集合;ck表示所有候选k项集组成的集合; lk表示所有频繁k项集组

12、成的集合；d表示事务数据 库;ck表示候选项集的第k个集合元素。有序号的程序shift+alt+y程序前1)cl 一 i|iei2)k 13)while ck 乒 do4)for each transaction t e d do5)for each candidate itemset ck ck do6)if ckt then7)support (ck) support (ck) +1/支持度计数8)lk ck|ckeck，s (ck) min_support/利用最小支持度剪枝9)ck+1 10)for each 11, 12elk, |lini2|=k-l do 11)m - 11 u1

13、2/对频繁项集进行自连接12)if jm, |j|=k and j e lk then/性质1对得到的候选(k+1)项集筛选13)ck+1 ck+1um/生成频繁(k+1)项集14)k - k+115)return lk程序后在利用频繁(k-1)项集生成k项集时，如果频繁 (k-1)项集数量很多，apriori算法需要进行大量的 i/o操作并占用cpu，扫描事务数据库，计算候选k 项集的支持度会占用大量资源，算法的效率低。下面 对apriori算法复杂度进行分析。n表示事务数据库d的交易数，e表示最大交易 长度，则第一遍数据库扫描时间为0 (exn)，在每 一步中，连接时间开铺是0 (|lk-

14、l|x|lk-l|)，剪枝时 间开销是o (|ck|),扫描计数时间是o (nx|ck|)o 所以apriori算法总的时间开销为：o (exn) +zk2 (0 (|lk-l|x|lk-l|) +o (|ck|)+o (nx|ck|)由于频繁-22是否应该是“2-” ？请明确。后面的 “-3”也是如此。项集是在l1上进行连接和剪枝，频 繁-33项集是在l2上进行连接和剪枝，且|li|>|lj|，2 <i，jk, i 算法 2eapriori 算法。步骤 lll=find_l_itemsets (t)，生成表 fi/生成 频繁1项集步骤 2for (k=2； lk-1 关；k+)

15、步骤3ck=lk-l*lk-l/利用lk-1执行自连接操作 生成ck步骤 4x=getitem_minsup (ck, fi)/利用f1从ck的k个项中找到支持度最小的项x 步骤 5target=get_transaction_id (x)/查询表f1得到含有项x的目标事务步骤6统计ck中各项在目标事务target中的支持度步骤7根据最小支持度进行筛选剪枝改进的eapriori算法时间复杂度分析如下：针对apriori算法中计算候选项集支持度的部分作出改进，每次迭代的扫描计数时间复杂度降低为o (akxnx |ck|),其中ak=target/n，表示支持度最小的项x对应 的目标事务数在总事务

16、数中所占比例。改进的eapriori算法总时间开销为：o (exn) + (o (|lk-l|x|lk-l|) +o (|ck|) +o(akxnx|ck|)每次迭代中各步骤的算法时间复杂度比较如表1 所示，其中第1遍扫描数据库时间开销0 (exn)只 计算1次。由表1可知，算法总的时间开销由4个部分组成: 第1遍扫描数据库、项集连接、扫描计数和筛选剪枝。 其中，在总时间开销中占据比例最大的就是扫描计数， 其次是项集连接和筛选剪枝。在改进算法当中，扫描 计数阶段的时间复杂度增加了一个变量ak，而ak和k 成反比关系，即随着迭代次数k的增加，目标事务target在事务数据库中所占的比例越来越小，

17、时间复杂度也随之下降。由于处理的审计日志数据库和购物 篮数据库类似，都属于稀疏型数据，因此变量ak的下 降速度会非常快，而扫描时间在总时间开销中占有较 大的比例，因此改进算法的时间复杂度较传统算法有 较大程度的降低，特别是在大型稀疏数据库中，迭代 次数越多，数据库的稀疏程度越高，改进算法的效率 提升越明显。4实验分析 4.1算法功能测试为了验证上述改进算法的有效性，采用snort 2.4.2 版本在alert_full模式下输出报警。实验采用mit lincoln实验室提供的darpa 1999数据集19。共有 38种攻击类型分别归属于收集信息攻击(probe)、获 取访问权限攻击(usert

18、oroot, u2r)、拒绝服务攻击 (denial of service，dos)和远程未授权访问攻击 (remotetologin， r2l)四种类型。记录按时间分为50份，首先对前20份数据进行 关联规则挖掘，建立攻击模式数据库。测试阶段包括 两组，分别对原有的安全审计系统和结合数据挖掘的 安全审计系统进行测试。测试共有117次攻击事件， 从实验结果可以看出，原有的审计系统对常见的pro b e 和u2r类型攻击的发现效率是比较高的；但对r2l 和dos攻击类型的审计判别不是很准确。原因是前两 种攻击出现时，审计系统已经可以较好地发现和记录 攻击特征，对于后两种攻击类型，审计系统对攻击的

19、 特征描述不够全面，所以检测准确率低。在结合关联 规则挖掘技术之后，建立全面的攻击模式数据库，审 计系统对攻击类型的识别能力提升在10%以上，检测 结果对比如图2所示。4.2算法性能测试1) 实验环境。本文采用java编程实现算法，操作系统为windows xp sp3,实验机器配置因特尔酷睿 2四核处理器，cpu频率为3.0ghz，ram3.17gb, 使用怀卡托智能分析环境(waikato environment for knowledge analysis)即weka软件平台完成，实验数据最终由matlab进行汇总制图和分析。2) 测试数据。为测试改进后的eapriori算法的性 能，本

20、文选用数据挖掘领域用来对比不同算法性能的 标准数据ucimlrepository中的4个数据集进行实 验，可以较全面地验证改进的关联规则挖掘方法在实 际数据集上的性能，表2给出了所选用的4个数据集(http： //ml/about.html)的咅p 分信息。3) 验证方法。为突出算法改进效果，采用关联规 则挖掘中经典的apriori算法和fpgrowth算法作为 对比，对上述4个数据集合采用10折交叉验证(lofold crossvalidation)，将数据集分成 10 份 si，s2,，s10, 分别作为训练集和测试集进行10次实验，即在第i次 迭代，

21、si用作测试集，其余子集都用于训练规则库的 建立。每个数据集的正确预测数10次迭代正确次数的 总和。4) 度量标准。正确的预测结果是衡量一个挖掘法性能重要的标准，关联规则挖掘方法的准确率可以 估计一个给定的挖掘算法对未来数据正确预须!的能力，定义如下:accuracy: （z10i=lsi） /dataset其中：|dataset|表示数据样本总数；|si|表示每次迭代中正确的次数。4.3实验结果分析 1）实验一。从4个数据集中随机抽取1000，6000，11000，16000个记录，分别作为测试案例testl、test2、test3、 test4,最小支持度定为18%，算法运行时间如图3所o

22、2）实验二。正确率和运行时间是评估算法性能的两个重要指 标，在weka平台下使用10折交叉验证法，对经典的 fpgrowth算法和改进的eapriori算法在4个训练 数据集上的规则预测正确率进行比较。表3实验结果 表明改进后的eapriori算法在数据集关联规则挖掘方 面的准确率提升在8%到74%之间，实验数据越多， 准确率提升越明显。3）实验三。利用上述4个测试数据集，在不同的最小支持度下，运行传统的apriori算法、fpgrowth算法和改 进的eapriori算法，将得到的运行时间分别进行比较，使实验结果更具充分性。在matlab中进行数据分析和图像化处理，x轴代表最小支持度的不同取

23、值，y轴 代表当前数据集下的算法运行时间，包括输入和输出 阶段的时间。实验结果如图4所示。从实验数据绘制的结果图4可以看出，改进的 eapriori算法运行效率比前两种算法有所提高，然而， 将前两个数据集同后两个数据集的实验结果进行比较 可以发现，改进的eapriori算法对于稀疏型数据集的 性能提升更为明显，最高能够达到51%。随着最小支 持度的提高，性能表现更加稳定，这是由于稀疏数据 集的密度较小，最小支持度增加，实际加入的计算数 据却比较少，因此算法运行时间没有明显的变化。相 比之下，该算法对于密集型数据集的性能提升幅度较 小，随着最小支持度的增加，实际加入的计算数据明 显增多，导致运行

24、时间的变化更加显著。5结语本文在对关联规则挖掘apriori算法和 fpgrowth算法进行研究的基础上，提出了一个改 进的eapriori算法。该方法通过对扫描的事务集合进 行限定，能够较好地提高算法的运行效率，尤其是在 大型稀疏数据集中；在此基础上又提出了一个结合该法进行关联规则挖掘的安全审计系统，并对它的系统结构进行了设计；最后对系统的有效性及算法的运行效率进行了分析。本文提出的基于关联规则挖掘的 安全审计系统可以提高计算机识别攻击行为的能力。 同时由于关联规则挖掘自身的缺陷，无法对所有的攻 击模式进行学习，因此接下来的工作中，同其他的数 据挖掘方法进行结合，比如序列模式挖掘等，提高审

25、计系统的智能程度和运行效率是下一步工作的方向。参考文献：1石文昌，孙玉芳.安全操作系统研究的发展j.计 机科学，2002, 29 (6)： 5-12. (shiwc，sunyf.development of secure operating system research j. computer science，2002，29 (6):5-12.)2丁丽萍，周博文，王永吉.基于安全操作系统的电 子证据获取与存储j.软件学报，2007, 18 (7)： 1715-1729. (dinglp, zhoub w, wang y j.capture and storage of digital evi

26、dence based on security operating system j. journal of software, 2007，18(7)：1715-1729.)3刘海峰，卿斯汉.安全操作系统审计的设计与实现 j.计算机研究与发展，2001，38 (10)： 1262-1268.(liu h f，qing s h. design and realization of auditing in secure os j. journal of computer research and development，2001，38 (10):1262-1268.)4moradim, keyva

27、npour m r. an analytical review of xml association rules mining j. artificial intelligence review，2015，43 (2):277-300.5songs j, kim eh, kimhg, etal. querybased association rule mining supporting user perspective j. computing，2011，93 (1)： 1-25.6agrawal r， srikant r. fast algorithms for mining associa

28、tion rules c/ proceedings of the 20th international conference on very large data bases. san francisco，ca: morgan kaufmann，1994： 21 -30.7agrawal r，imielinskit swami a. mining association rules between sets of items in large databases j. acm sigmod record, 1993, 22(2)： 207-216.8han j, pei j, yin y. m

29、ining frequent patternswithout candidate generation j. acm sigmod record，2000，29 (2)：1-12.9elhajj m， zaiane o r. cofi approach for mining frequent itemsets revisited c/ proceedings of the 2004 acm sigmod workshop on research issues in data mining and knowledge discovery. new york： acm, 2004：70-75.10

30、 dong g l, ryuks，bashir m, et al. discovering medical knowledge using association rule mining in young adults with acute myocardial infarction j. journal of medical systems，2013，37(2)： 1-10.11khalilia， sami a. sysdetect： a systematic approach to critical state determination for industrial intrusion

31、detection systems using apriori algorithm j. journal of process control，2015，2776：154-160.12sahoo j, das ak, goswami a. an effective association rule mining scheme using a new generic basis j. knowledge and information systems，2015，43(1)： 127-156.13keshavamurthy b n, khan am, toshniwal d. privacy preserving association rule mining over distributed databases using genetic algorithm j. neural computing & application