学点算法搞安全之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》

原文发布于微信公众号 - FreeBuf(freebuf)

原文发表时间:2017-05-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏悦思悦读

【机器学习实践】水果图片分类

学习理论之外,自己寻找资源动手实践,在实际做项目中巩固了习得的理论知识,并进一步体会到了日常积累的重要性。

6903
来自专栏数据派THU

怎样构建中文文本标注工具?(附工具、代码、论文等资源)

来源:Paperweekly 本文长度为2218字,建议阅读4分钟 本文为你介绍中文文本标注工具的构建方法,并提供多个开源文本标注工具。 项目地址: https...

1.3K7
来自专栏fangyangcoder

MaskRCNN-Keypoints

这个月先写一篇吧,后面要复习数学考试了,可能到时候就忘了。今天写一个比较有意思的东西,关于人体的分割与姿态估计。如下图所示:

3223
来自专栏DHUtoBUAA

Design and Implementation of Global Path Planning System for Unmanned Surface Vehicle among Multiple

  针对多任务点的全局路径规划,是指在存在静态障碍物的环境中,给定水面无人艇起始点、目标点以及多个任务点的情况下,设计从起始点出发,安全地遍历各个任务点,最终返...

970
来自专栏石瞳禅的互联网实验室

【TensorFlow实战——笔记】第2章:TensorFlow和其他深度学习框架的对比

可以看到各大主流框架基本都支持Python,目前Python在科学计算和数据挖掘领域可以说是独领风骚。虽然有来自R、Julia等语言的竞争压力,但是Python...

1271
来自专栏PaddlePaddle

【AI核心技术】课程八:卷积网络简介

UAI与PaddlePaddle联合推出的【AI核心技术掌握】系列课程持续更新中!

893
来自专栏机器之心

业界 | 详解Horovod:Uber开源的TensorFlow分布式深度学习框架

选自Uber 作者:Alex Sergeev、Mike Del Balso 机器之心编译 参与:李泽南、路雪 Horovod 是 Uber 开源的又一个深度学...

8356
来自专栏数据科学与人工智能

【算法】关联规则挖掘算法

小编邀请您,先思考: 1 关联算法有什么应用? 2 关联算法如何实现? 温馨提示:加入圈子或者商务合作,请加微信:luqin360 关联规则挖掘是一种基于规则的...

4428
来自专栏数说工作室

文本相似比较

大家好,我是数说君,这篇文章是想跟大家讨教一下。 如果有两段简单文本,如何比较它们的相似度?这里我们就假设是英文,不存在中文的分词问题,文本就类似于: text...

37714
来自专栏CVer

开源 | 商汤联合港中文开源 mmdetection

项目地址:https://github.com/open-mmlab/mmdetection

3023

扫码关注云+社区

领取腾讯云代金券