学点算法搞安全之apriori

学点算法搞安全之apriori。在企业安全建设专题中偶尔有次提到算法的应用，不少同学想深入了解这块，所以我专门开了一个子专题用于介绍安全领域经常用到的机器学习模型，从入门级别的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)

apriori的代码实现

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

L, suppData = apriori(myDat, support=0.5)

rules = generateRules(L, suppData, minConf=0.5)

apriori的应用

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

/0_1/?%22>&nszixunid=291&m=nszixun

src javascript iframe对应举例/%22/e/?xss_test%3Ciframe%20src=javascript：this[%22%5Cx61%5Cx6c%5Cx65%5Cx72%5Cx74%22](%2242873%22)%3E

style expression alert对应举例/144/user.php?back_act=http://127.0.0.1%22style=x:expression(alert(42873))%3E

总结

挖掘的关联关系，可以作为SVM、KNN等分类算法的特征提取依据，进一步的攻击识别需要依赖分类算法，apriori等关联挖掘算法提供了一种挖掘潜在关联关系的自动化方式。