学点算法搞安全之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)< 最小支持度阈值,当有元素A添加到I中时,结果项集(A∩I)不可能比I出现次数更多,因此A∩I也不是频繁的。

apriori的应用

  在安全领域,aprioir的应用非常广泛,凡是需要挖掘潜在关联关系的都可以尝试使用,比如关联waf的accesslog与后端数据库的sqllog,识别ssh操作日志中异常操作等。

我们这里以分析accesslog为例子。我们从xssed网站的样例以及waf的拦截日志中提取xss攻击日志作为样本,示例日志如下:

/0_1/?%22onmouseover=‘prompt(42873)‘bad=%22%3E

/0_1/api.php?op=map&maptype=1&city=test%3Cscript%3Ealert%28/42873/%29%3C/script%3E

/0_1/api.php?op=map&maptype=1&defaultcity=%e5%22;alert%28/42873/%29;//

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

myDat=[]

with open("xss-train.txt") as f:

for line in f:

tokens=re.split(‘\=|&|\?|\%3e|\%3c|\%3E|\%3C|\%20|\%22|<|>|\\n|\(|\)|\‘|\"|;|:|,‘,line)

myDat.append(tokens)

f.close()

切割后的向量示例如下:

[‘/0_1/‘, ‘‘, ‘onmouseover‘, ‘‘, ‘prompt‘, ‘42873‘, ‘‘, ‘bad‘, ‘‘, ‘‘, ‘‘, ‘‘]

[‘/0_1/api.php‘, ‘op‘, ‘map‘, ‘maptype‘, ‘1‘, ‘city‘, ‘test‘, ‘script‘, ‘alert%28/42873/%29‘, ‘/script‘, ‘‘, ‘‘]

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

L, suppData = apriori(myDat, 0.1)

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

有趣的现象出现了:

frozenset([‘//‘, ‘1‘]) --> frozenset([‘‘, ‘alert‘]) conf: 1.0

frozenset([‘1‘, ‘script‘]) --> frozenset([‘‘, ‘/script‘]) conf: 1.0

frozenset([‘/‘, ‘script‘]) --> frozenset([‘‘, ‘/script‘]) conf: 0.997576736672

frozenset([‘type‘, ‘title‘]) --> frozenset([‘a‘, ‘‘]) conf: 0.996108949416

frozenset([‘a‘, ‘title‘]) --> frozenset([‘‘, ‘type‘]) conf: 0.993210475267

frozenset([‘a‘, ‘c‘]) --> frozenset([‘‘, ‘m‘]) conf: 1.0

frozenset([‘1‘, ‘/‘, ‘script‘]) --> frozenset([‘‘, ‘/script‘]) conf: 1.0

frozenset([‘1‘, ‘alert‘, ‘script‘]) --> frozenset([‘‘, ‘/script‘]) conf: 1.0

frozenset([‘alert‘, ‘/‘, ‘script‘]) --> frozenset([‘‘, ‘/script‘]) conf: 0.997416020672

frozenset([‘1‘, ‘alert‘, ‘/‘, ‘script‘]) --> frozenset([‘‘, ‘/script‘]) conf: 1.0

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

apriori的代码实现

网上apriori的代码实现很多,这里给出其中一种实现。

def createC1(dataSet):
   C1 = []
   for transaction in dataSet:
       for item in transaction:
           if [item] not in C1:
               C1.append([item])
   C1.sort()
   return map(frozenset, C1)
def scanD(D, Ck, minSupport):
   ssCnt = {}
   for tid in D:
       for can in Ck:
           if can.issubset(tid):
               ssCnt[can] = ssCnt.get(can, 0) + 1
   numItems = float(len(D))
   retList = []
   supportData = {}
   for key in ssCnt:
       support = ssCnt[key] / numItems
       if support >= minSupport:
           retList.insert(0, key)
       supportData[key] = support
   return retList, supportData
def aprioriGen(Lk, k):
   retList = []
   lenLk = len(Lk)
   for i in range(lenLk):
       for j in range(i + 1, lenLk):
           L1 = list(Lk[i])[: k - 2];
           L2 = list(Lk[j])[: k - 2];
           L1.sort();
           L2.sort()
           if L1 == L2:
               retList.append(Lk[i] | Lk[j])
   return retList
def apriori(dataSet, minSupport=0.5):
   C1 = createC1(dataSet)
   D = map(set, dataSet)
   L1, suppData = scanD(D, C1, minSupport)
   L = [L1]
   k = 2
   while (len(L[k - 2]) > 0):
       Ck = aprioriGen(L[k - 2], k)
       Lk, supK = scanD(D, Ck, minSupport)
       suppData.update(supK)
       L.append(Lk)
       k += 1
   return L, suppData
def calcConf(freqSet, H, supportData, brl, minConf=0.7):
   prunedH = []
   for conseq in H:
       conf = supportData[freqSet] / supportData[freqSet - conseq]
       if conf >= minConf:
           print freqSet - conseq, ‘-->‘, conseq, ‘conf:‘, conf
           brl.append((freqSet - conseq, conseq, conf))
           prunedH.append(conseq)
   return prunedH
def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
   m = len(H[0])
   if len(freqSet) > m + 1:
       Hmp1 = aprioriGen(H, m + 1)
       Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
       if len(Hmp1) > 1:
           rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
def generateRules(L, supportData, minConf=0.7):
   bigRuleList = []
   for i in range(1, len(L)):
       for freqSet in L[i]:
           H1 = [frozenset([item]) for item in freqSet]
           if i > 1:
               rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
           else:
               calcConf(freqSet, H1, supportData, bigRuleList, minConf)
   return bigRuleList

  

时间: 05-14

学点算法搞安全之apriori的相关文章

学点算法搞安全之SVM

前言 在企业安全建设专题中偶尔有次提到算法的应用,不少同学想深入了解这块,所以我专门开了一个子专题用于介绍安全领域经常用到的机器学习模型,从入门级别的SVM.贝叶斯等到HMM.神经网络和深度学习(其实深度学习可以认为就是神经网络的加强版). 规则VS算法 传统安全几乎把规则的能力基本发挥到了极致,成熟企业的WAF.IPS.杀毒甚至可以达到两个九以上的准确度,很好的做到了"我知道的我都能拦截".但是规则都是基于已有的安全知识,对于0day甚至被忽略的Nday,基本没有发现能力,即所谓的&

学点算法搞安全之HMM(上篇)

前言 隐式马尔可夫(HMM),也称韩梅梅,广泛应用于语音识别.文本处理以及网络安全等领域,2009年I Corona,D Ariu,G Giacinto三位大神关于HMM应用于web安全领域的研究论文,让HMM逐渐被各大安全厂商重视.本篇重点介绍HMM最常见同时也比较基础的基于url参数异常检测的应用,后继文章将介绍HMM结合NLP技术在XSS.SQL.RCE方面的应用."多一个公式少一半读者",所以霍金的<时间简史>和<明朝那些事>一样畅销,我的机器学习系列文

学点算法搞安全之HMM(下篇)

前言 上篇我们介绍了HMM的基本原理以及常见的基于参数的异常检测实现,这次我们换个思路,把机器当一个刚入行的白帽子,我们训练他学会XSS的攻击语法,然后再让机器从访问日志中寻找符合攻击语法的疑似攻击日志. 通过词法分割,可以把攻击载荷序列化成观察序列,举例如下: 词集/词袋模型 词集和词袋模型是机器学习中非常常用的一个数据处理模型,它们用于特征化字符串型数据.一般思路是将样本分词后,统计每个词的频率,即词频,根据需要选择全部或者部分词作为哈希表键值,并依次对该哈希表编号,这样就可以使用该哈希表对

从零开始学回溯算法

本文在写作过程中参考了大量资料,不能一一列举,还请见谅. 回溯算法的定义:回溯算法也叫试探法,它是一种系统地搜索问题的解的方法.回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试. 解题的一般步骤是: 1.定义一个解空间,它包含问题的解: 2.利用适于搜索的方法组织解空间: 3.利用深度优先法搜索解空间: 4.利用限界函数避免移动到不可能产生解的子空间. 问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性. 话不多说,我们来看几个具体的例子慢

前端要不要学数据结构&amp;算法

我们都知道前端开发工程师更多偏向 DOM 渲染和 DOM 交互操作,随之 Node 的推广前端工程师也可以完成服务端开发.对于服务端开发而言大家都觉得数据结构和算法是基础,非学不可.所以正在进行 Node 开发的同学而言,这个答案跃然纸上.我们今天重点说一说纯前端开发的同学到底需不要数据结构与算法. 我先说下结论:需要,非常需要. 第一,只要是程序员,基本功都是数据结构与算法 从我们接触编程的时候就知道一个理论,程序=数据结构+算法.所以,只要写的是程序,就离不开数据结构和算法.当然,有的同学会

零基础学贪心算法

本文在写作过程中参考了大量资料,不能一一列举,还请见谅.贪心算法的定义:贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,只做出在某种意义上的局部最优解.贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关.解题的一般步骤是:1.建立数学模型来描述问题:2.把求解的问题分成若干个子问题:3.对每一子问题求解,得到子问题的局部最优解:4.把子问题的局部最优

------------------学冒泡排序算法跟我走----------------

学这个总体一句话: 外层结束需减一,内层结束减 i 再减一, 打擂算法做对比,对比j 和 j+1, 如若不想报异常,万万不能有等号. //冒泡排序 public static void main(String[] args) { int num []={18,200,27,198,190,175}; //排序前的数组排列. for (int i = 0; i < num.length; i++) { System.out.println(num[i]); } //比较相邻的数,谁大谁在后面, f

Python --深入浅出Apriori关联分析算法(二) Apriori关联规则实战

上一篇我们讲了关联分析的几个概念,支持度,置信度,提升度.以及如何利用Apriori算法高效地根据物品的支持度找出所有物品的频繁项集. Python --深入浅出Apriori关联分析算法(一) 这次呢,我们会在上次的基础上,讲讲如何分析物品的关联规则得出关联结果,以及给出用apyori这个库运行得出关联结果的代码. 一. 基础知识 上次我们介绍了几个关联分析的概念,支持度,置信度,提升度.这次我们重点回顾一下置信度和提升度: 置信度(Confidence):置信度是指如果购买物品A,有较大可能

从零开始学贪心算法

本文在写作过程中参考了大量资料,不能一一列举,还请见谅. 贪心算法的定义: 贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,只做出在某种意义上的局部最优解.贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关. 解题的一般步骤是: 1.建立数学模型来描述问题: 2.把求解的问题分成若干个子问题: 3.对每一子问题求解,得到子问题的局部最优解: 4.把子