郭紅艷，谷保平

（河南廣播電視大學(xué)，鄭州 450000）

一、引言

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

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

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

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

基于關(guān)聯(lián)規(guī)則的入侵檢測(cè)分類(lèi)學(xué)習(xí)包括以下三個(gè)主要步驟：

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

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

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

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

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

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

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

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

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

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

（2）AAR 分類(lèi)步驟。

AAR產(chǎn)生分類(lèi)器經(jīng)過(guò)以下三個(gè)步驟：

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

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

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

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

（3）分類(lèi)器的算法。

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

②為Hash樹(shù)的各個(gè)葉子節(jié)點(diǎn)生成一個(gè)候選原子規(guī)則r。

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

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

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

⑥最后輸出知識(shí)要點(diǎn)。

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

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

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

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

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

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

三、基于AAR入侵檢測(cè)實(shí)驗(yàn)

1.實(shí)驗(yàn)環(huán)境。

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

2.性能評(píng)估。

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

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

執(zhí)行時(shí)間：

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

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

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

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

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

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

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

3.實(shí)驗(yàn)對(duì)比。

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

四、結(jié)論

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

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

[2]谷保平，許孝元，郭紅艷.基于粒子群優(yōu)化的k均值算法在網(wǎng)絡(luò)入侵檢測(cè)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用，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.