學點演算法搞安全之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原創獎勵計劃，未經許可禁止轉載

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！