基于原子分類關(guān)聯(lián)規(guī)則的網(wǎng)絡入侵檢測研究

郭紅艷，谷保平

（河南廣播電視大學，鄭州 450000）

一、引言

入侵檢測方法一般分為兩大類：誤用檢測和異常檢測[1]，誤用檢測技術(shù)主要是檢測與已知的不可接受行為之間的匹配程度。收集非正常操作的行為特征，建立特征庫，檢測時依據(jù)具體特征庫進行判斷是否有入侵行為，這種檢測模型誤報率低、漏報率高；異常檢測技術(shù)是先定義一組系統(tǒng) “正?！鼻闆r的數(shù)值，如CPU利用率、內(nèi)存利用率等，然后將系統(tǒng)運行時的數(shù)據(jù)與所定義的“正?！鼻闆r比較，得出是否有被攻擊的跡象，若兩者偏差足夠大，則說明發(fā)生了入侵。這種方法的優(yōu)點是能檢測未知的攻擊類型，適應性強。

入侵檢測的關(guān)鍵技術(shù)在于分類。目前，應用于入侵檢測分類方法有很多，如統(tǒng)計分類方法、支持向量機、神經(jīng)網(wǎng)絡和遺傳算法等。隨著新技術(shù)的大規(guī)模應用，研究者發(fā)現(xiàn)一些新穎的分類方法，例如關(guān)聯(lián)規(guī)則分類法就是其中一種，目前普遍接受的觀點是關(guān)聯(lián)規(guī)則分類準確度高。

本文中，我們把原子分類關(guān)聯(lián)規(guī)則應用于入侵檢測中，利用原子型分類關(guān)聯(lián)規(guī)則構(gòu)建分類器的思想，它是模仿認識事物一般規(guī)律，運用“先易后難策略”分類。它具有執(zhí)行速度快、準確度較高、挖掘的分類模型易于理解的特點，比較適合于大規(guī)模數(shù)據(jù)挖掘。

二、原子分類關(guān)聯(lián)規(guī)則

基于關(guān)聯(lián)規(guī)則的入侵檢測分類學習包括以下三個主要步驟：

（1）入侵信息的收集。入侵檢測首先要進行信息源的收集，包括審計跡、系統(tǒng)日志、網(wǎng)絡數(shù)據(jù)包、數(shù)據(jù)等。

（2）入侵信息的分析。入侵行為一般都是隱藏在大量正常的信息之中，為了獲取入侵信息，就必須對信息源進行分析。常用的分析方法有關(guān)聯(lián)規(guī)則、聚類分析和模式匹配等?？梢?，信息分析是入侵檢測過程中的關(guān)鍵環(huán)節(jié)。

（3）入侵檢測的響應。系統(tǒng)對攻擊行為發(fā)出報警通知或?qū)嵤┛刂?，從而降低攻擊行為對系統(tǒng)所造成的破壞。

1.關(guān)聯(lián)規(guī)則。

自Agrawal提出關(guān)聯(lián)規(guī)則挖掘后，關(guān)聯(lián)規(guī)則算法及應用得到迅速發(fā)展。在1998年的KDD （KDD：Knowledge Discovery in Databases）會議上，B.Liu等人提出了分類關(guān)聯(lián)規(guī)則算法（CBA0）。該算法使用類Apriori算法產(chǎn)生關(guān)聯(lián)規(guī)則，被認為關(guān)聯(lián)分類的基準算法。使用支持度閾值是1%與置信度閾值是50%。該算法有兩個問題：一是候選規(guī)則的運算非常耗時同時占有大量內(nèi)存資源；二是由于是基于置信度的關(guān)聯(lián)分類從而降低分類準確度。

2.原子分類關(guān)聯(lián)規(guī)則。

原子分類關(guān)聯(lián)規(guī)則算法是利用“基于突出特征和先易后難策略”的分類原理，采取人們認識事物一般常識：“先易后難”。具體做法如下：先找出最易識別進行一次分類，刪除第一次易分類，在余下的數(shù)據(jù)分類中，進行同樣的分類處理，直到將所有數(shù)據(jù)分類完畢。原子分類關(guān)聯(lián)規(guī)則分類技術(shù)的關(guān)鍵技術(shù)是分類原子性，它的主要原理是找事物的“突出特征”和人們處理事情“先易后難”分類方法。為了便于記憶，我們把原子分類關(guān)聯(lián)規(guī)則 （Atomic Association Rule）簡稱為AAR。

（1）數(shù)據(jù)結(jié)構(gòu)。

AAR算法中比較關(guān)鍵的步驟是發(fā)現(xiàn)強原子規(guī)則。

在AAR算法的數(shù)據(jù)挖掘算法中，為了方便數(shù)據(jù)集中的項和項集計數(shù)，我們使用一個的雙層Hash樹來實現(xiàn)。為了提高算法的計算效率，可以將雙層的Hash樹簡化為一個三維數(shù)組。

（2）AAR 分類步驟。

AAR產(chǎn)生分類器經(jīng)過以下三個步驟：

①選擇高置信度規(guī)則進行分類。首先進行數(shù)據(jù)集的掃描，比較各種分類方法置信度，然后選擇置信度比較高的規(guī)則進行分類。

②強原子規(guī)則進行排序、刪除分類好的記錄。對強原子分類關(guān)聯(lián)規(guī)則按置信度高低進行降序排序，首先找第一關(guān)鍵字；然后，進行強原子分類關(guān)聯(lián)規(guī)則分類，分類完成后，把覆蓋的記錄從數(shù)據(jù)集中刪除。

③數(shù)據(jù)集中剩余的數(shù)據(jù)繼續(xù)步驟②進行分類處理，到數(shù)據(jù)集沒有任何記錄為止。

最后，正確組合分類數(shù)據(jù)，生成正確的數(shù)據(jù)模型。

（3）分類器的算法。

①項集計數(shù)：掃描數(shù)據(jù)集，利用一個兩層的Hash樹，用來標記每個類標簽的數(shù)目和候選原子分類關(guān)聯(lián)規(guī)則的數(shù)目。

②為Hash樹的各個葉子節(jié)點生成一個候選原子規(guī)則r。

③通過Hash樹直接計算候選原子規(guī)則r的支持度。

④刪除支持度小于最小支持度的候選原子規(guī)則，得到頻繁的原子規(guī)則集。并計算原子分類關(guān)聯(lián)規(guī)則的置信度。利用置信度閾值提取強的原子分類關(guān)聯(lián)規(guī)則。

⑤利用頻繁的原子規(guī)則集在后件相同的條件下進行組合，導出候選的復合規(guī)則。

⑥最后輸出知識要點。

圖1 是建立原子分類關(guān)聯(lián)規(guī)則分類器的算法：

AAR算法具有如下顯著的優(yōu)點：

①原子分類關(guān)聯(lián)規(guī)則挖掘的是占有系統(tǒng)資源比較少，分類時間短；

②使用最高置信度的強原子分類關(guān)聯(lián)規(guī)則可以保證分類預測精度；

③該規(guī)則產(chǎn)生的分類模型包含的規(guī)則數(shù)少，規(guī)則簡單，易于理解，分類過程具有置信度閾值自適應的特點，無需用戶設(shè)定。

下面把原子分類關(guān)聯(lián)規(guī)則算法應用于入侵檢測的情況進行了研究，詳細研究了AAR與CBA兩種典型的關(guān)聯(lián)分類算法在數(shù)據(jù)集分類中的應用，結(jié)果表明AAR算法在分類準確度、分類模型的簡潔性、分類學習速度和魯棒性等方面顯著地優(yōu)于CBA。

三、基于AAR入侵檢測實驗

1.實驗環(huán)境。

實驗用的處理器為2.2 GHz CUP：E2200，主存為2048MB。操作系統(tǒng)為Windows 7，入侵檢測數(shù)據(jù)集是來自KDD cup“kddcup.data10.percent”。在該數(shù)據(jù)集中，入侵記錄的類型有Dos、U2R、R2L和 Probe。實驗選用的樣本集如表1所示，分別是Dos、U2R、R2L和ALL（所有四類入侵數(shù)據(jù)）。為了評價分析原子分類關(guān)聯(lián)規(guī)則算法的分類準確性，我們使用誤報率FAR（false alarm rate）和檢測率 DR（detection rate）來測試算法性能[2，3]。

2.性能評估。

為了評估AAR的算法性能，我們從執(zhí)行時間和產(chǎn)生的規(guī)則數(shù)兩個方面與CBA算法進行比較。經(jīng)過反復實驗，對于該數(shù)據(jù)集，AAR的自適應置信度閾值調(diào)節(jié)系數(shù)為COEF=0.92。這樣既保證了較高的分類準確度又具有能接受的建模時間。而CBA的置信度閾值取缺省值minconf=50%。

表1 兩種算法系統(tǒng)性能

執(zhí)行時間：

兩種算法執(zhí)行時間如圖2所示，在同樣的條件下實驗結(jié)果表明：CBA比AAR算法要占有更多的時間。在較小的minsup下，CBA算法會產(chǎn)生大量滿足約束的強規(guī)則。因此在最小支持度比較小的情況下，挖掘頻繁k-項集的k值較小，執(zhí)行時間較短。隨著minsup的增加，k值相對變大，挖掘頻繁候選k-項集也相應地增加，產(chǎn)生強規(guī)則要花費更多的時間。當minsup值較大時，由于產(chǎn)生頻繁k-項集的減少，執(zhí)行速度也較快，執(zhí)行時間更短。

圖2 不同minsup的執(zhí)行時間

從圖2也可以看出，在minsup從小變大時，AAR算法的執(zhí)行時間相對于CBA算法比較平穩(wěn)，執(zhí)行時間大概在14秒上下，minsup的改變對AAR挖掘的影響比較小。

分類規(guī)則數(shù)：

兩種算法分類規(guī)則數(shù)如圖3所示，從圖中可以看出在CBA算法和AAR算法在不同最小支持度下產(chǎn)生的分類關(guān)聯(lián)規(guī)則數(shù)目。CBA比AAR算法要產(chǎn)生更多的分類規(guī)則數(shù)。對于CBA算法，最小支持度從小到大增加時，規(guī)則數(shù)目迅速降低，同時有部分分類規(guī)則不能形成正確的分類效果。而AAR算法采用加入自適應的置信度閾值的思想。所以，產(chǎn)生的分類關(guān)聯(lián)規(guī)則數(shù)目變化不大，相對于CBA算法來說，AAR算法比較平穩(wěn)，效果更好些。

圖3 不同minsup的規(guī)則數(shù)

通過AAR和CBA的綜合指標比較，兩種關(guān)聯(lián)分類算法在入侵檢測數(shù)據(jù)集的分類結(jié)果可以看出AAR表現(xiàn)優(yōu)異，同時AAR算法生成了更少的規(guī)則數(shù)，執(zhí)行效率高。而CBA算法執(zhí)行速度較慢，產(chǎn)生分類規(guī)則數(shù)較多。

3.實驗對比。

綜合考慮算法性能下，把最小支持度的默認值設(shè)置為1%。對AAR算法與CBA在入侵檢測方面進行對比實驗，實驗結(jié)果如表1所示。從實驗數(shù)據(jù)結(jié)果可以看出，原子分類關(guān)聯(lián)規(guī)則（AAR）算法不論在誤報率還是在檢測率方面都優(yōu)于CBA算法，特別是對于DOS類型的入侵檢測效果更好，說明改進的算法（AAR算法）是可行的。

四、結(jié)論

在本文中，介紹了原子關(guān)聯(lián)規(guī)則算法 （AAR算法），并將其應用于網(wǎng)絡入侵檢測中，AAR算法可以快速準確對入侵檢測數(shù)據(jù)進行分類，該分類算法支持動態(tài)閥值，能提高分類的準確性。對比AAR算法和CBA算法，實驗表明，AAR能快速和準確分類入侵檢測數(shù)據(jù)，取得了不錯的綜合性能表現(xiàn)。今后的工作是進一步研究增強該算法適應能力，研究改進特征提取的方法，建立準確、簡單、易于理解的分類模型。

[1]蔣建春，馬恒太，任黨恩，等.網(wǎng)絡安全入侵檢測研究綜述[J].軟件學報，2000，11（11）：1460-1466.

[2]谷保平，許孝元，郭紅艷.基于粒子群優(yōu)化的k均值算法在網(wǎng)絡入侵檢測中的應用[J].計算機應用，2007，27（6）：1368-1370.

[3]Wang Hai-rui，Li Wei.Decision Tree Algorithm Based on Association Rules[J].Computer Engineering，2011，37（9）：104-106.