学点算法搞安全之apriori

*原创作者：兜哥，本文属FreeBuf原创奖励计划，未经许可禁止转载

前言

在企业安全建设专题中偶尔有次提到算法的应用，不少同学想深入了解这块，所以我专门开了一个子专题用于介绍安全领域经常用到的机器学习模型，从入门级别的SVM、贝叶斯等到HMM、神经网络和深度学习（其实深度学习可以认为就是神经网络的加强版）。

关联规则数据

关联规则挖掘通常是无监督学习，通过分析数据集，挖掘出潜在的关联规则，最典型的一个例子就是尿布和啤酒的故事。相传沃尔玛的数据分析人员通过分析大量购物清单发现相当一部分消费者会同时购买尿布和啤酒，结果他们把尿布和啤酒赫然摆在一起出售，结果销量又双双增长。关联规则分析的结果是客观现象的体现，有的显然易见，比如同时购买三文鱼和芥末，有的勉强可以解释，比如尿布和啤酒，有的就匪夷所思，比如打火机和奶酪。关联算法中最著名的就是apriori算法。

apriori 简介

首先介绍三个基本概念，支持度、置信度和频繁k项集。

支持度，P(A ∩ B)，既有A又有B的概率，它表现的是A和B两个事件相对整个数据集合同时发生的频繁程度，比如尿布和啤酒的支持度是0.2，表明有20%的消费清单中，消费者同时购买了尿布和啤酒。

置信度，P(B|A)，在A发生的事件中同时发生B的概率 P(AB)/P(A)，它表现的是在AB两个事件的相关程度，和整个数据集合的大小没有关系，比如尿布和啤酒的置信度为0.8，表明在同时购买了两者的消费者中，购买尿布的80%又购买了啤酒。

需要特别说明的是，P(A ∩ B)=P(B ∩ A)，但是P(B|A)和P(A|B)是两回事。

如果事件A中包含k个元素，那么称这个事件A为k项集事件A满足最小支持度阈值的事件称为频繁k项集。

apriori算法就是挖掘同时满足最小支持度阈值和最小置信度阈值的关联规则。

apriori 基本原理

apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做L1，然后利用L1找频繁2项集的集合L2，L2找L3，如此下去，直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。

其中，apriori算法具有这样一条性质：任一频繁项集的所有非空子集也必须是频繁的。因为假如P(I)< 最小支持度阈值，当有元素A添加到I中时，结果项集（A∩I）不可能比I出现次数更多，因此A∩I也不是频繁的。

apriori 的代码实现

主流的机器学习库对apriori支持很少，不过aprior的实现的确比较简单，网上资源很多，建议参看peter harrington的《机器学习实战》，其中对apriori实现后封装的函数如下：

apriori 的应用

在安全领域，apriori的应用非常广泛，凡是需要挖掘潜在关联关系的都可以尝试使用，比如关联waf的accesslog与后端数据库的sqllog，识别ssh操作日志中异常操作等。我们这里以分析accesslog为例子。我们从xssed网站的样例以及waf的拦截日志中提取xss攻击日志作为样本，示例日志如下：

我们目标是分析出潜在的关联关系，然后作为SVM、KNN等分类算法的特征提取依据之一。机器没有办法直接识别日志，需要逐行将日志文本向量化，最简单的方式就是按照一定的分割符切割成单词向量，示例代码如下：

切割后的向量示例如下：

我们以十分严格的置信度来运行，试图找到关联关系接近100%的情况：

有趣的现象出现了：

有些结果容易理解，比如’script’和’1′、’alert’出现的话会100%的概率导致’/script’，有些结果匪夷所思，比如’a'和’c'出现的话会100%的概率导致’m'。

我们进一步降低门槛，讲支持度也下降到0.001，这意味着即使对应的关联关系出现的概率只有千分之一，主要它对应的是强关联，置信度超过0.99，我们也认为这是一种有价值的关联

这个学习的过程会比较慢，我们选取了部分结果：

我们通过关联挖掘识别一种潜在的关联关系，’object’ ‘base64′ ‘data’ ‘text/html’

测试结果

通过分析20w条xss攻击样本数据，完全通过机器学习的方式挖掘潜在的关联关系，得到如下结果举例如下：

总结

挖掘的关联关系，可以作为SVM、KNN等分类算法的特征提取依据，进一步的攻击识别需要依赖分类算法，apriori等关联挖掘算法提供了一种挖掘潜在关联关系的自动化方式。基于SVM的XSS检测可以参考我上篇文章《学点算法搞安全之SVM》