在企業安全建設專題中偶爾有次提到算法的應用，不少同學想深入了解這塊，所以我專門開了一個子專題用于介紹安全領域經常用到的機器學習模型，從入門級別的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等關聯挖掘算法提供了一種挖掘潛在關聯關系的自動化方式。基于SVM的XSS檢測可以參考我上篇文章《學點算法搞安全之SVM》
| 
