基于改進Apriori算法的多源安全日志關聯分析

甕俊昊

（四川大學計算機學院，成都 610065）

0 引言

隨著網絡規模的逐漸擴大，互聯網相關技術的日新月異，安全問題也日益突出，屢見不鮮的病毒、漏洞、攻擊層出不窮。網絡安全問題不僅嚴重影響了人民的生活，還對一個國家的安全和經濟發展產生了嚴重威脅[1]。對于網絡安全信息分析來說，日志數據作為信息挖掘的依據和基礎在其中占據著重要的地位，日志描述了設備的相關行為，其中存在著大量未知信息，安全日志數據分析可以用來監測網絡的入侵行為，在故障或安全事件發生時，日志就像是黑匣子，維護人員可以從這些數據記錄中進行分析，查找故障源、獲取攻擊行為、重建攻擊過程等，通過對安全隱患或事件的分析，執法機關還可以用來打擊網絡犯罪[2]。

現如今，隨著日志數據的數量越來越多，類型越來越多樣，數據處理的要求也越來越高[3]，日志分析系統的功能就是通過對日志數據的分析發現系統的異常以便提出應對策略。網絡管理人員可以通過對日志進行分析來尋找網絡故障的原因，還可以根據分析結果找到攻擊者遺留的痕跡。但是由于日志數量繁多，而且根據日志的特點，它在種類上具有多樣性，不同設備產生的日志差異較大，所以有效地對日志進行處理分析才能得到分析人員的預期結果[4]。目前為止，針對日志分析已有許多方法，并且也衍生出了許多日志分析工具。目前針對安全日志的關聯分析方法大致可分為4類，分別是基于統計、基于規則庫、基于狀態轉移以及基于數據挖掘的分析方法。本文重心是在研究基于數據挖掘的日志分析的基礎上，對基于Apriori算法的關聯分析方法進行改進，從而在日志分析上能夠提供更高的效率。本文主要提出一個基于矩陣Apriori算法增加權重向量的關聯規則挖掘方法，并根據測試數據集進行效率測試，驗證了該方法在關聯規則的挖掘上能夠大幅提高運行效率。

1 多源安全日志關聯分析

多源日志的關聯分析是指通過特定的規則對從多種設備上收集到的日志進行相關性描述，然后通過使用一些關聯分析算法從這些結果數據中提取安全事件[5]。企業信息系統中包含路由器、防火墻、IDS/IPS、交換機、服務器和SQL數據庫等多個種類的設備[6]。各種復雜的應用系統和網絡設備每天都產生大量的日志信息，查找如此海量的數據并分析出其中的安全事件，對管理員來說意味著海量的工作和拖延的工作效率。在互聯網中海量異構的日志大致分成以下三類：System log（UNIX/LINUX、Windows）、Network de-vice log（硬件設備、安全設備）、Application log（Web、軟件等）。

在基于數據挖掘的網絡安全日志分析方法中，Apriori算法的應用十分廣泛，通過挖掘數據集中的不同規則，找出滿足給定條件下的多個領域之間的依賴關系[7]。通過使用頻繁項目集的挖掘算法挖掘出了網絡中異常事件的IP、端口等屬性間的關聯特征，以幫助分析人員對網絡安全事件進行識別[8]。對網絡安全日志進行關聯分析時，因為網絡中的連接信息是多屬性元組，所以在挖掘過程中使用的是多維關聯規則。例如在對IDS日志進行挖掘分析時得出的其中一條規則：{SIP:220.228.136.38,DIP:11.11.79.83,EventType:Attempted information Leak,123}該規則表示目的IP 11.11.79.83在被監控時間內被源IP 220.228.136.38使用Attempted Information Leak攻擊共計123次。通過Apriori算法可以挖掘出各安全事件IP、端口間的關聯關系，從而建立起各安全事件的屬性特征，提高事件的檢測效率。本文提出了一種基于矩陣的Apriori增加權重向量的改進方法來進行挖掘，下一節將進行詳細描述。

2 基于改進矩陣Apriori算法的關聯規則挖掘研究

2. 1 傳統Apriori算法的關聯規則挖掘

傳統基于Apriori算法的技術通常應用于查找項集之間的具有可信的和代表性的規則[9]，類似A?B的表達式即一條關聯規則，Apriori算法包含兩個常用指標，分別是支持度（Support count）和置信度（Confidence），支持度（Support count）表示事務集T中事件A所發生的頻率，支持度越高，說明這個事件發生的越頻繁，用A.count表示計數：Sup_count(A?B)=，其中N表示事務集T中的事務總數。置信度（Confidence）表示A的前提下B同時發生的條件概率，它決定了關聯規則是否足夠準確，有以下公式計算：

在Apriori算法中，滿足預先設定的最小支持度min_sup的項目集合，稱為頻繁項集，然后從中提取的所有規則中尋找到滿足預先設定的最小置信度min_conf的規則，稱為強關聯規則。關聯規則挖掘算法實際上就是一個不斷生成頻繁項集并尋找強關聯規則的過程。傳統的Apriori使用廣度優先查找方式來找到頻繁1項集，并由（k-1）-itemset自連接生成kitemset，其中 k=2，3，…，m；m 代表最大的項目集合，通過min_sup修剪來獲得最終的頻繁k-itemset。

2. 2 基于矩陣的Apriori算法研究

在傳統的Apriori算法中，當我們使用頻繁（k-1）-itemset自連接生成k-itemset時，如果頻繁（k-1）-itemset的數量非常大，Apriori算法需要進行大量的I/O操作從而占用大量的CPU資源，而且會得到很多的候選項集，效率低下[10]；同時，傳統Apriori算法缺少對安全日志自身結構的考慮，所以在進行關聯挖掘時會產生許多無效規則。針對Apriori算法存在的缺點，眾多學者提出了多種改進方法，例如將矩陣融入到Apriori算法中產生的基于矩陣的Apriori算法[11]，用0-1矩陣的方式存儲和展示數據，只需通過矩陣的運算就能得到所需要的頻繁項集，而且全程只搜索一次數據庫，就能得到所有符合條件的項集，大幅度提高算法效率，同時減少大量候選項集的產生，節約了存儲空間[12]。

事務中的每個屬性及事務集按照序列排列。矩陣中的行表示事務中的屬性，列表示事務。假設在m事務中存在編號n的屬性，則對應生成的矩陣中第m行的第n列的值記為1，反之為0，矩陣中每列數字的和為屬性計數，即為支持度的計算結果。例如對于二項集（Mm,Mn），僅需要查看矩陣的第m、n行上處于相同列中均為1的計數，便為它的支持度。以下是基于矩陣的Apriori算法步驟：

（1）首先根據事務集T構造0-1矩陣MT。其中若屬性n在事務m中出現，則對應矩陣元素Mij=1，反之Mij=0。

（2）對MT每列1的值進行計數，刪除計數結果低于min_sup的項（行向量），對滿足min_sup的結果每兩列做向量的交運算。

（3）利用上述結果構建新矩陣，重復此過程，直到不再產生新矩陣，最終矩陣就是我們要求的頻繁項集。

使用基于矩陣Apriori算法的具體計算流程如圖1。

圖1 基于矩陣Apriori算法計算流圖

2. 3 基于改進的加權矩陣 Apriori算法研究

2.2小節描述的算法在計算過程中會不斷生成新的矩陣，而且根據事務量的不同，矩陣也同樣需要發生變化，本文通過研究Apriori算法生成矩陣中的數據關系，發現很多行和列可以進行優化，通過增加一個權重向量的方式，對矩陣整體進行精簡，提高計算效率。

假設事務集T中含有m條事務和n個屬性，二進制布爾矩陣可據此構建如下：

其中Ti代表事務集合T中第i條記錄，存在一個權重向量WT，初始時WT={1 ,1,...,1}，當連續掃描Ti時如果發現相同的事務，對應權重值加1，同時刪除矩陣中相應行，支持度sup_coun（tI）可由WTI表示，I是矩陣中的列向量，具體算法流程圖如圖2。

圖2 基于改進的加權矩陣Apriori算法流程圖

根據Apriori算法的性質，我們有以下兩個推論：

推論1：如果兩個頻繁項集（k-1）-itemset可以進行連接生成k-itemset，那么它們必然存在一個相同的（k-2）-itemset。

推論2：如果項目集是頻繁的，那么它的所有子集必然也是頻繁的，相應的，非頻繁項集的超集肯定也是非頻繁的。

同樣使用圖一中示例事務集T，構建初始矩陣并進行運算過程如下：

3 實驗對比分析

為了驗證基于矩陣加權的Apriori算法的性能，本節將該方法與傳統基于矩陣的Apriori算法進行相同環境下的對比實驗，實驗環境在處理器為Intel Corei7-7700 CPU@3.6GHz、內存為16G的64位計算機上進行，程序在Weka平臺下測試，數據集選用在UCIMLRepository中的Retail數據集，專門用于數據挖掘中的算法測試。

從該數據集中分別隨機選擇1000,5000,10000,30000,50000條記錄作為測試用例，min_sup=20%，兩種算法的運行時間比較如圖3。

圖3 不同算法的性能測試比較

從圖3所示結果中我們可以看出，在相同數據集的情況下，選擇不同事務數據量的情況下，改進的加權矩陣Apriori算法的性能比較傳統的Apriori算法有著大幅度的提升，同時相對傳統的基于矩陣的Apriori算法也有一定程度的提高，并且在事務量逐漸增大的情況下，改進的算法運行效果的提升越來越明顯。

4 結語

本文研究了多源安全日志的關聯分析方法，首先介紹了多源安全日志的基本概念和常見關聯分析方法，研究了基于數據挖掘的日志分析方法，針對傳統Apriori算法在運行過程中效率低下的缺陷，提出了一種基于Apriori矩陣結合權重向量的改進方法，并通過與傳統Apriori算法、傳統矩陣Apriori算法的對比實驗分析，結果證明了本文提出的改進算法的有效性，為多源安全日志關聯分析方法的進一步研究提供了可靠依據。