基于審計日志的關聯規則挖掘

王京, 譚玉波，*, 邢曉蕭

(1.河南工業大學信息科學與工程學院， 鄭州 450001； 2.河南工業大學信息化管理中心， 鄭州 450001)

伴隨著全球化信息技術的發展，世界越來越依賴于網絡化的信息系統，人們享受著互聯網提供的信息交流的便利，但與此同時，網絡安全事故和信息泄露事件屢屢發生[1]。系統審計日志可以很詳細地記錄主機上的系統調用過程，因此很適用于入侵攻擊的取證工作。但是系統審計日志每天產生的日志記錄太過龐大且冗余，對日志數據的剖析就顯得尤為的重要。數據挖掘的方法可以提取隱藏在大批數據中可能有關聯有意義的信息，所以數據挖掘的方法適用于分析日志數據。

關聯規則挖掘是一種難度低且易于應用的技術，它能找出千千萬萬數據集中事務間的關聯性，從而形容某一事物的某些屬性在同一時間段呈現的規律和模式。1994年，Agrawal等[2]提出Apriori算法，目的是在超市交易數據庫中找到一種商品與另一種商品之間的關系，使商家可以依照客戶購買商品之間的關系重新展示商品的陳列位置，從而更好地銷售商品。后來PCY(Park-Chen-Yu)算法[3]、多階段算法[3]針對Apriori算法頻繁遍歷數據庫的缺點，各自進行了改進。PCY算法將哈希(Hash)函數應用在經常出現的項集之中，并在第1次掃描事務數據庫時使用剩余的空間存儲Hash表，減少2次掃描占用的內存空間；多階段算法在PCY算法的前2次掃描之間插入一個獨立的掃描過程，再使用不同Hash函數的獨立Hash表中存儲2-項集。

一些學者在對經典關聯規則挖掘算法發掘數據集過大、發現頻繁集的過程需要多次讀取數據庫這些問題進行了研究。石升等[4]采用了組合思想，每次從原集合中選出不同的項的方法生成原集合的所有子集，在尋找頻繁項集時，每一個事務集包含的頻繁項集只能是該事務集的子集，來減少遍歷數據庫的次數；曾子賢等[5]提出了MIFP-Apriori算法結合矩陣、改進頻繁模式樹和候選集頻數優化策略，有效解決了生成大量重復候選集的缺陷，提高算法效率；孫帥等[6]提出了基于概率交易壓縮的相關規則改進算法，利用概率論和有效參數的設置，優化后的算法很大程度上減少不必要的候選項集，提升了Apriori算法的性能。盡管上述算法較Apriori算法執行效率上得到改善，但是并沒有解決實質性的問題。當數據集規模龐大時，上述算法產生的頻繁集較多。Han等[7]提出了FP-Growth算法直接生成頻繁項集，生成了FP-Tree樹，省去了反復計數的時間。

關聯規則挖掘的算法正在蓬勃發展中，其和信息安全領域的結合也需要更多的研究，現將審計日志與關聯規則算法結合起來，給出審計日志的參考數據，為發現攻擊類型的結果提供判別依據，分析經典算法和改進算法的性能，為審計日志挖掘的研究提供一定參考價值。

1 相關工作

1.1 數據挖掘

數據挖掘技術是從不計其數的事務中發掘出事務之間的潛在關系，基于眾多領域的理論范疇和實踐方法。像近年來研究火熱的人工智能(artificial intelligence)、機器學習(machine learning)、邊緣計算(edge computing)和云計算(cloud computing)等。在信息爆炸的今天，數據挖掘技術變得非常盛行。近10年來，許多挖掘方法被提出并得到應用。關聯規則挖掘因其具有廣泛普適性而備受關注?，F結合河南工業大學安全系統中的審計日志，采用數據挖掘的方法進行分析，使審計日志數據得到充分利用。

1.2 關聯規則

關聯規則(association rules)體現這一項與另一項之間的潛在相關性和依賴性，作為數據挖掘領域的一項關鍵技術，從多如牛毛的事務中挖掘出數據項之間的潛在關系。假設兩個或者兩個以上的事物之間存在一定的關聯，那么其中一個事物可以通過與它存在關聯的事物推測出來。置信度(confidence)、支持度(support)、期望置信度(expected confidence)和提升度(lift)是關聯規則的屬性特征。其中支持度和置信度可以更直觀地解釋相關規則的性質。當開始解析關聯規則定義時，可以隨機給出一組帶有交易的兩個商品，關聯規則存在于它們之間，區別在于屬性值的差異。在實際應用中，人們通常只關注達到一定支持度和置信度的關聯規則，相關的公式定義如下。

定義1I={i1,i2,…,im},m個不同交易的集合記作I，每個ik是一個項目，將項目的集合I叫作項集。

定義2[8-9]每個事務T都是項集I的一個子集，每個事務都有一個唯一的標識事務號TID。交易數據庫D是由所有交易構成,|D|表示交易數據庫D中包含的交易數。

定義3項集X有X?T。count(X?T)是事務D中包含X的事務數,對項集X的支持度為

(1)

定義4Sup，min是項集的最小支持度。具有Sup，min或更高support的項集記錄在頻繁集里，長度為k的頻繁項集記錄在k-頻繁項集。

定義5關聯規則[17-19]數學表達式為

R:X?Y

(2)

式(2)中：X?I,Y?I,并且X∩Y不為空。假定某次交易中有項集X，那么Y某一概率也可在此交易找到。

定義6關聯規則R的支持度是事務集包含X和Y的交易數量與|D|之比，即

(3)

式(3)中：X、Y同時出現的概率代表support，經常出現項集的support等同于關聯規則的support。

定義7關聯規則R的置信度是指包含X和Y的交易數與包含X的交易數之比，即

(4)

定義8[8-11]若規則R的support和confidence不小于Sup,min和Con，min，稱為強關聯規則。

1.3 最小支持度和最小置信度的判定

在關聯規則挖掘中要注意選取適當的支持度和置信度，這依賴于用戶對目標的估量以及實際數據訓練場景的情況[12-16]。假定support和confidence取值太小，就會產生很多無用的規則；倘如設定值過大，則可能出現找不到規則的情況。目前，Sup，min與Con，min閾值的確定基本是采用試錯法，詳細方法可參考如下幾點。

(1)確定試錯期間可以容忍的誤差范圍和超過誤差的概率。

(2)用中心極限定理之類的概率工具，計算出保證誤差和概率的樣本大小。

(3)對數據集進行采樣。

(4)試錯直到得到想要的結果。

(5)正式挖掘。

1.4 審計日志

系統審計日志[14,20]可以很詳細地記錄主機上的系統調用過程，因此很適用于入侵攻擊的取證工作。但是系統審計每天產生的日志記錄太過龐大且冗余，對日志數據的剖析就顯得尤為的重要。數據預處理的目的是將審計日志源數據轉化為可靠的數據，總結為三個階段：數據清洗(data cleaning)、數據描述(data description)、特征選擇(feature selection)。

(1)數據清洗。數據清洗旨在審查系統生成的日志數據，并在校正過程中去除冗余信息、糾正現有錯誤。數據預處理的首要環節便是data cleaning，這對數據分析至關重要。在此階段，涉及的任務包括對缺失數據的處理、對離群點的處理以及要對比重復數據，將其排序后做進一步處理。

(2)數據描述。在數據描述階段，通常使用數據可視化工具來展示其統計量和整體情況。從許多數據中將具有共同特征的屬性提取，丟棄個別不必要的數據，使用匯總的事務數據信息對其進行抽象概括。這些抽象概括得到的數據是通過對初始數據整理總結得到的，用較少的變量可以替代整體數據信息，相對來說反映了數據的總體特性。

(3)特征選擇。當對數據做特定分析時，常常遇到屬性非常多的情況，有些屬性是不相關的，有些屬性是重復的，這時就需要用特征分析來挑選出最相關的屬性，降低分析難度。

2 關聯規則挖掘算法

關聯規則挖掘可用來在不同事務交易之間找到可靠且有意義的關聯規則，發掘步驟可以分為兩個階段。

(1)由事務集創建生成一組候選項集并尋覓一組頻繁項集。找出全部support高于Sup，min閾值的最大頻繁項集集合。

(2)由階段(1)生成強關聯規則。從最大頻繁的項目集中找出滿足Con，min要求的規則。

2.1 Apriori算法

Apriori算法利用候選項目集得到頻繁項集，由k-項頻繁集得出k+1項頻繁集的候選集合，之后依照Con，min得到相關的交易規則。在Apriori算法中，需說明兩條先驗定理[5-9]。

定理1假定一個項集不屬于頻繁項，則這個項集超集不屬于頻繁項。

定理2假定一個項集屬于頻繁項，則這個項集的子集屬于頻繁項。

Apriori算法的偽代碼表示如下：

算法1 Apriori 算法

輸入 Log databaseD,minsupport。

輸出 Strong association rules。

(1)Set up a function advanced

(2)Function advanced(minsupport)

(3)C1←{{i}|i∈I}

(4)K→1

(5)WhileCk≠?

(6)for each transactionT∈Ddo

(7)for each candidate itemsetcK∈CKdo

(8)If thenck?T

(9)support(ck)←support(ck)+1

(10)Lk←{ck|ck∈Ck,s(ck)≥minsupport}

(11)Ck+1←?

(12)for eachl1,l2∈Lk,|l1∩l2|=k-1

(13)M←l1∪l2

(14)If then ?J?M,|J|=KandJ∈Lk

(15)Ck+1←Ck+1∪M

(16)K→K+1

(17)returnLk

(18)End If

(19)End If

(20)End While

(21)End Function

以上代碼中，L1代表所有頻繁1-項集組成的集合；CK是全部候選K-項集組成的集合；LK為全部頻繁K-項集組成；候選項集的第k個集合元素記作ck。

假定數據庫D的交易數量為N，最大交易長度是E，則第一遍掃描數據庫的時間是o(E×N)，連接時間花費為o(|Lk-1|×|Lk-1|)，剪枝時間是o(|Ck|)，頻繁項計數的時間是o(N×|Ck|)。因此得到Apriori算法花費的總時間為

O(|CK|)+O(N×|CK|)]

(5)

由此可知Apriori算法效率低下的原因在于對候選集的support計數以及尋找頻繁集，若能克服多次掃描數據庫和減少頻繁集數量的不足，算法性能將得到改善。

2.2 PCY算法

PCY(Park-Chen-Yu)算法是由三位中國科學家Park、Chen和Yu共同開發的[3,21]。PCY算法基于Apriori算法，利用了Apriori算法首個步驟中剩余未使用的內存，將研究重心放在頻繁項集發掘中的第一步，旨在利用大批未使用的內存空間。

該算法用基于散列的技術來壓縮一組候選k項集的集合β(k>1)。例如，當掃描數據庫中的每個事務并從候選集中創建頻繁集時，將哈希表中每個事務生成的整個字段項目集合進行散列，將其存儲在不同桶來增加桶的計數。由此可知此項技術減少了經常出現的項集數量，使得到的候選k項集更為精簡。

PCY算法的偽代碼表示如下：

算法2 PCY 算法查找頻繁集

輸入 數據庫databaseD,支持度閾值value，計數值count。

輸出 頻繁項集。

(1)此算法運用存儲桶和mapreduce概念來尋找頻繁項集。

(2)映射給定數據庫中的所有元素以找到其長度。

(3)將候選集設定為所有長度為1的候選集。

(4)成對映射候選集，并找到每個對的長度。

(5)列出長度大于最小元素長度閾值的所有集合，應用于哈希函數，生成存儲桶編號。

(6)根據獲得的編號進行升序排列，繪制圖表。

(7)檢查是否有重復對，檢查計數值是否低于支持度閾值，生成頻繁集。

2.3 FP-Growth算法

FP-Growth算法是建立FP-Tree來達到壓縮事務數據庫中信息的目的，使得創建頻繁項集更容易[17]。頻繁項的support越高離根節點就越近，這樣可以共享FP-Tree給更多的頻繁項。在韓家煒教授[7]提出FP-Growth算法之前,關聯分析算法通常采用的是Apriori算法以及它的改良算法，然而，Apriori算法及其改良算法掃描交易數據庫次數繁多，性能不大理想。FP-Growth算法創造的FP-Tree，使此問題得到解決。構建FP-Tree[18-20]的方法如下:

(1)掃描一次交易數據庫。尋找頻繁項集并采集每個頻繁項的support。假定Sup，min為2，則L=[(A1:6),(B1:4),(B2:2),(B3:2),(C3:2),(D4:2)]。事務數據庫如表1所示。

(2)FP-Tree的根節點是空節點，逐條將排序篩選后的記錄插入樹中。若記錄中的節點在樹的該路徑中已存在，則將該節點計數加一，否則分支。構建好的FP-Tree表示如圖1所示。

表1 事務數據庫

圖1 FP-Tree構建過程Fig.1 FP-Tree setting process

基于上述的描述，可以根據FP-Tree得到頻繁模式的算法。偽代碼表示如下：

算法3 使用FP-Tree挖掘頻繁模式

輸入Atransaction databaseD2,FP-Tree,minsupport。

輸出 The complete set frequent patterns。

(1)If tree contains a single prefix path

(2)LetPthe single prefix-path part of tree

(3)LetQbe the multipath part with the top branching node replaced by a null root

(4)For each combination(denoted asβ) of the nodes in the pathPdo

(5)generated patternβ∪αwith support=minsupport of nodes inβ

(6)let freq pattern set (P) be the set of patterns so generated

(7)else letQbe Tree

(8)For each item ai in q do{

(9)generate paternβ=ai∪αwith support=ai.support

(10)constructβ’s conditional pattern-base and thenβ’s conditional FP-tree Treeβ

(11)If Treeβ≠?

(12)then call FP-Growth(Treeβ,β)

(13)let freq pattern set(Q) be the set of patterns so generated}

(14)return(freqpatternset(P)∪freq pattern set(Q)∪(freq pattern set(P)×freq pattern set(Q)))

(15)End if

(16)End for

(17)End for

由此，可得到一個頻繁項集列表F-list,即{{A1:6},{B1:4},{B2:2},{B3:2},{C3:2},{D4:2},{A1,B1:2},{A1,B2:2},{A1,B3:2},{B1,C3:2},{B1,D4:2},{C3,D4:2}.{B1,C3,D4:2}}。這使得到強關聯規則的效率大幅度提升。

2.4 改進KAFP-Growth算法

2.4.1 算法具體描述

FP-Growth算法遞歸生成事務數據庫并建立FP-Tree,內存占比大，該算法的弊端是僅用于發掘一維的布爾(Boolean)關聯規則。針對這些問題，設計了KAFP-Growth算法,在生成FP-Tree的同時，以預處理過的審計日志為事務集，加以關鍵詞屬性約束。

圖2 排序篩選事務集并建立KAFP_TreeFig.2 Sort and filter transaction set and build KAFP_Tree

日志記錄通常是由一些不同的字段組成，例如時間戳、源IP地址、目的IP地址、端口號等信息。不同的字段有著不同的權重，有些字段是日志記錄的關鍵屬性，有些字段是輔助屬性，并不是所有的字段都是描述一個網絡連接活動的重要字段。我們設一個元組，記為：<時間戳，源IP，目的IP，源端口，目的端口>，元組里的字段為重要屬性。

定義1設A是所要研究的屬性集合，F是不同屬性間依賴關系的集合，K?A，若A完全依賴于K，則稱K是關鍵屬性集，任一屬性k∈K，都稱為關鍵屬性。

定義2標記域用來描述某個項是否屬于關鍵屬性集合，如果屬于該集合，標記為a。

2.4.2 KAFP-Tree的建立

首先建立KAFP-Tree,首要任務是將事務中的冗余項找出并刪去。首先刪去全部事務支持度小于最小支持度的項；其次刪去未被標記為a的項。為了更加直觀形象地理解本算法，摘取5個日志事件為事務集D，以此作為案例。其中11代表2021年8月8日 03：35：47，IP地址為1.1xx.2xx.252發起的登錄請求記錄；12代表的是2021年8月10日 21時到23時，IP為218.2xx.1xx.233嘗試訪問用戶無權限的文件目錄；13代表的是2021年8月9日1時到6時，IP為218.2xx.1xx.233對同一設備嘗試訪問用戶無權限的文件目錄；2021年8月10日16時42分13秒，IP地址110.1xx.2x.64多次登陸失敗，記作14；15代表7月25日08時39分05秒，IP為1.1xx.2xx.252多次登錄失敗。

篩選事務集并建立KAFP_Tree具體流程如圖2所示。

圖2中13和15分別包含元組中的關鍵屬性。F-List是項頭表，使標記好的關鍵屬性可以通過指針指向它在KAFP_Tree中的位置。根據篩選排序后建立的KAFP_Tree,尋找包含關鍵屬性的頻繁項集集合LE。對于顯示為a的項集，根據每個項集指針指向的位置，從KAFP_Tree中搜索分支進行挖掘。

若挖掘的是標記為a的項的分支。比如15，其生成的頻繁項集只有標記為a的頻繁項集，依照FP-Growth算法，遞歸挖掘頻繁項集即可。

2.4.3 KAFP-Growth算法挖掘頻繁集

具體偽代碼如下。

算法4 使用KAFP_Tree挖掘頻繁模式

輸入 Log databaseD，kaFP-Tree,minsupport。

輸出 The set frequent patterns。

(1)gen-LE(KAFP_Tree,FR-List,minsup)

(2)for each item in FR-List

(3)If item.link≠null

(4)branchset←find branch(item.link,kafp_tree)

(5)for each branch in branchsetdo

(6)a←find-key attribute(branch,FR-List)

(7)as←non-empty-powerset(A)

(8)If item.label=′a′

(9)for each (Asj∈As) do

(10)IEt←Asj//找到每一分支關鍵屬性項集合IEt

(11)CEt←aggregateIEt

(12)for eachCEtdo

(13)IfCEt≥minsupport×D

(14)LEt←CEt//生成頻繁項集LEt

(15)LE←addLEt//將LEt添加進LE

對于改進的KAFP-Growth算法，設在D個事務中含有的項集數量為X,帶有關鍵屬性的項集數量為K，最大事務中含有的項的數量設為M。掃描事務數據庫一次，訪問每個項用來生成FP-Tree，所有k-項均會進行一次遍歷，在每個分支上尋找所設定的關鍵屬性,則該過程的時間復雜度為O(XM+K)，對每個分支所得到的帶有關鍵屬性的項目進行局部頻繁項集的挖掘，最終將挖掘結果聚集，輸出全局頻繁項集，所需時間復雜度為O[X×(IK×CK)]，以這樣的方式來挖掘數據庫中的頻繁項，把用時最多的掃描時間轉為局部頻繁項集挖掘時間，且使用最大事務中的深度遍歷，其時間復雜度要比傳統的遞歸查找小得多。因此得到KAFP-Growth算法花費的總時間為O(XM+K)+O[X×(IK×CK)]。

3 實驗結果與分析

3.1 算法性能分析

3.1.1 實驗環境

使用Python編程實現算法，操作系統為Windows10,實驗室及其配置環境為AMD Ryzen 5 3600 6-Core Processor 3.60 GHz處理器。實驗數據最終由Origin進行匯總制圖和分析。

3.1.2 測試數據

為測試改進KAFP-Growth算法的性能，用河南工業大學信息化管理中心提供的2021年7月10—8月10日30 d的審計日志數據Events和在UCIML-Repository中的三個常用在數據挖掘方面的數據集進行實驗，比較四種算法的性能。改進KAFP-Growth算法的性能可以在實際數據集上得到充分驗證，表2顯示了實驗所用的4個數據集。

表2 數據集特性

3.2 實驗結果分析

3.2.1 實驗一

不同數據集規模運行時間對比。從Events數據集中隨機抽取1 000、5 000、7 000、10 000條記錄，將KAFP-Growth算法與Apriori算法、PCY算法、FP-Growth算法進行比較。關于設置最小置信度和最小支持度方法，基本是采用研究人員的經驗通過試錯法確定閾值。參照前文關于最小支持度的取值方法來確定Sup，min的值。首先將容忍誤差范圍設定在5%～10%，其次運用概率論中的中心極限定理討論數據集中某一屬性所產生的影響分布是否漸進于正態分布。獨立同分布的中心極限定理公式為

(5)

(6)

將FP-Growth算法和改進KAFP-Growth算法在Events審計日志數據上進行關聯規則挖掘，從實驗數據得出，KAFP-Growth算法得出的結果更接近于期望值，檢測結果如圖4所示。

圖3 不同記錄數算法運行時間比較Fig.3 Comparison of execution time of algorithms with other record numbers

圖4 算法改進前后檢測攻擊對比Fig.4 Detection attack comparison before and after algorithm improvement

從圖3可以看出，隨著數據集規模的擴大，KAFP-Growth算法的時間優勢越明顯，可以更好地發現安全事件，及時阻斷網絡攻擊，營造更加安全的網絡環境。

3.2.2 實驗二

依據所用的四個數據集設定不同的Sup，min，對比Apriori算法、PCY算法、FP-Growth算法和改進KAFP-Growth算法的執行時間，結果如圖5所示。

圖5 4個數據集分別對應的運行時間Fig.5 Execution time for 4 datasets

圖5所示結果表明，改進的KAFP-Growth算法運行時間比其他算法執行時間都短。與其他數據集相比，改進的KAFP-Growth算大大提高了Retail和Events兩個大型數據集的性能。規定審計日志的關鍵屬性約束，對KAFP-Tree上的每個分支所帶有關鍵屬性的項目進行局部頻繁項集的挖掘，最終將挖掘結果聚集，輸出全局頻繁項集結果，省去了傳統算法連接、剪枝生成候選項集的時間，大幅度減少了時間開銷。隨著Sup，min的不斷提高，可以看到整個算法的性能逐漸穩定。由于密集型數據集的數據密度較高，若Sup，min持續增加，實際上會增加更多的數據到計算中，因此密度高的數據集算法運行變化比稀疏型數據集變化顯著。

4 結論

為克服傳統關聯規則挖掘算法的不足，提出了基于審計日志的KAFP-Growth算法。實現對審計日志更為精準的安全事件分析。

(1)采用試錯法確定最小支持度。在可容忍的誤差范圍內確定最小支持度的值，使得到的關聯規則最理想化，經驗證，針對數據集Events，本文中所取的Sup，min準確率高于其他數值，解決了因Sup，min和Con，min取值問題而產生的冗余關聯規則。

(2)利用數據預處理技術，對審計日志進行清洗、描述、變換等操作，能有效減少臟數據對信息提取的影響，同時引入關鍵屬性概念，約束數據集條件。將規定的屬性標簽應用在建立KAFP-Tree上，有效過濾了不重要或是不需要的頻繁集，縮小了查找范圍。結合不同規模的挖掘數據集，表明該算法在對較大規模數據集上具有良好適用性。