改進(jìn)關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘在網(wǎng)絡(luò)入侵檢測中的應(yīng)用

張群慧

(湖南信息科學(xué)職業(yè)學(xué)院 湖南 410151)

0 引言

要從海量的數(shù)據(jù)中挖掘出有用的信息知識(shí)，關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的主要工具之一。它主要是能夠從大量的數(shù)據(jù)中尋找出數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系。作為傳統(tǒng)網(wǎng)絡(luò)安全技術(shù)的補(bǔ)充，入侵檢測受到更多的重視。基于模式匹配、統(tǒng)計(jì)分析和完整性分析的傳統(tǒng)入侵檢測方法，逐漸不能適應(yīng)快速發(fā)展的網(wǎng)絡(luò)安全技術(shù)。將關(guān)聯(lián)規(guī)則引入到入侵檢測中，可以適應(yīng)快速發(fā)展的網(wǎng)絡(luò)技術(shù)并提高入侵檢測的檢測效率。

1 傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法

Apriori 是一種最有影響的挖掘頻繁項(xiàng)集的算法。早在1994年Agrawal等人在項(xiàng)目集格空間理論的基礎(chǔ)上提出了用于發(fā)現(xiàn)頻繁項(xiàng)目集的Apriori算法。這種經(jīng)典的Apriori算法是采用一種叫做“逐層搜索”的迭代方法。要使用k-項(xiàng)集來生成(k+1)-項(xiàng)集，首先必須對數(shù)據(jù)庫進(jìn)行掃描以計(jì)算出頻繁l-項(xiàng)集的集合,將該集合記為：L1，然后再執(zhí)行迭代過程來計(jì)算頻繁k-項(xiàng)集，一直到生成頻繁了k-項(xiàng)集的集合（記為：Lk）為空，其過程為：

（1）連接：用Lk-1進(jìn)行自連接運(yùn)算,來生成候選k-項(xiàng)集的集合（記為：Ck）。通過運(yùn)算后，Ck集合將包含所有的頻繁k-項(xiàng)集。

（2）剪枝：連接生成的Ck就是Lk的超集，通過掃描DataBase來計(jì)算Ck中每個(gè)候選項(xiàng)集的支持度。用戶首先給定最小支持度，對于支持度大于給定的最小支持度的候選k-項(xiàng)目集就是頻繁k-項(xiàng)目集。

Apriori算法存在以下缺點(diǎn)：

（1）可能產(chǎn)生大量的候選項(xiàng)集，特別是候選2-項(xiàng)集。如果有1000個(gè)頻繁1-項(xiàng)集，那么該算法將會(huì)產(chǎn)生105數(shù)量級(jí)的候選2-項(xiàng)集。

（2）可能需要重復(fù)地掃描數(shù)據(jù)庫。

（3）計(jì)數(shù)工作量可能非常大。

2 改進(jìn)的Apriori 算法及其算法實(shí)驗(yàn)

采用自適應(yīng)步長躍進(jìn)。因?yàn)槊總€(gè)頻繁項(xiàng)集對數(shù)據(jù)庫需要掃描一次。為了減少對數(shù)據(jù)庫的掃描次數(shù)，本算法是在己產(chǎn)生的Lk基礎(chǔ)上以hi為步長，通過連接、剪枝一次性產(chǎn)生新的以hi為步長的(k+j)-itemset (j= 1，2…， hi)的候選頻繁集，然后再掃描數(shù)據(jù)庫，確定其中真正的頻繁項(xiàng)集，從而可以大大減少數(shù)據(jù)庫挖掘過程中的掃描時(shí)間，以提高效率。

3 動(dòng)態(tài)修剪候選項(xiàng)集。頻繁項(xiàng)集的特征

特征1: 若k維數(shù)據(jù)項(xiàng)目集I={i1，i2，…，ik}中，存在至少有一個(gè)im使得Nk-1(im)

特征2：對于不包含Ck-1的事務(wù)產(chǎn)生的任何項(xiàng)集，則刪除該事務(wù)對Lj(j≥k)的計(jì)算沒有影響。

本文主要是在一次生成候選項(xiàng)集的時(shí)候按照上述性質(zhì)，通過縮減和刪除數(shù)據(jù)集的規(guī)模，減少候選項(xiàng)集的個(gè)數(shù)，從而使得搜索空間比原來小，使Apriori算法在搜索空間上得到改進(jìn)。

在原來的Apriori算法基礎(chǔ)上，改進(jìn)算法U-Apriori的實(shí)現(xiàn)的主要步驟如下：

輸入：經(jīng)過布爾化的數(shù)據(jù)庫D，最小化支持閾值min_sup

輸出：Li，D中的頻繁項(xiàng)集。

（1）L1=find_freguent_1_itemset(D)；

（2）for(k=2;Lk≠ф;k++)

（3）Ck=apriori_gen(Lk-1,min_sup)；

（4）for each c∈Ck);

（5）for each p∈Lk-1&&q∈Lk-1；

（6）if(p⊕q==c)

（7）for(i=1;i

（8）m[i]=p[i]*q[i];

（9）if(m[i]==1)m.count++

（10）if(m.count＞=min_sup)

（11）Insert_into_Lk(m)

（12）return l=UkLk

特征3：改進(jìn)Apriori 算法的實(shí)驗(yàn)。在一臺(tái)計(jì)算機(jī)CPU Intel P4 2.0G， 內(nèi)存為512M 上對Apriori 算法與其改進(jìn)算法進(jìn)行實(shí)驗(yàn)測試對比（時(shí)間單位：小時(shí)） 。試驗(yàn)仿真數(shù)據(jù)來源：chess數(shù)據(jù)集（http：//fimi.cs. helsinki. fi/）。所得實(shí)驗(yàn)結(jié)果如圖1所示。

從圖1中可以看出， 在挖掘速度上，改進(jìn)Apriori算法較改進(jìn)前有比較明顯的優(yōu)勢，在數(shù)據(jù)集大小為5萬條以下不明顯，但數(shù)據(jù)集超過10萬時(shí)開始有較大區(qū)別，改進(jìn)算法的優(yōu)勢已經(jīng)很明顯。這是應(yīng)為改進(jìn)算法因?yàn)闇p少了對數(shù)據(jù)庫的掃描次數(shù)，并顯著減小了候選集的大小，所以較大程度地提高了算法效率。

4 改進(jìn)的算法在入侵檢測中的應(yīng)用

數(shù)據(jù)挖掘在入侵檢測中的應(yīng)用，主要是利用數(shù)據(jù)挖掘中的數(shù)據(jù)分類、關(guān)聯(lián)分析和序列模式挖掘，對來自不同數(shù)據(jù)源的安全審計(jì)數(shù)據(jù)進(jìn)行智能化的分析處理，通過提取數(shù)據(jù)本身存在的規(guī)律性，幫助系統(tǒng)生成入侵檢測規(guī)則和建立異常檢測模型，最大限度的降低在處理安全審計(jì)數(shù)據(jù)時(shí)對先驗(yàn)知識(shí)的要求。關(guān)聯(lián)分析算法可用于挖掘描述入侵行為模式的關(guān)聯(lián)規(guī)則，通過這些規(guī)則進(jìn)行入侵檢測。

圖1 Aprior算法改進(jìn)前和改進(jìn)后算法性能比較

（1）數(shù)據(jù)獲?。涸诰W(wǎng)絡(luò)上截取用于檢測的數(shù)據(jù)。

（2）數(shù)據(jù)預(yù)處理：對網(wǎng)絡(luò)上捕獲到的原始網(wǎng)絡(luò)數(shù)據(jù)，需要先進(jìn)行預(yù)處理，將它們轉(zhuǎn)換成ASCII碼格式的網(wǎng)絡(luò)分組信息，再將網(wǎng)絡(luò)分組信息處理成網(wǎng)絡(luò)連接記錄，并將其放入審計(jì)記錄庫，為數(shù)據(jù)挖掘做準(zhǔn)備。

（3）審計(jì)記錄庫：審計(jì)記錄庫存放從網(wǎng)絡(luò)上得到的各種數(shù)據(jù)。

（4）數(shù)據(jù)訓(xùn)練集：在系統(tǒng)初期，需要收集數(shù)據(jù)進(jìn)行訓(xùn)練，把已知系統(tǒng)缺陷和其他已知攻擊模式裝入知識(shí)庫中。

（5）數(shù)據(jù)挖掘算法庫：在挖掘算法庫的指導(dǎo)下, 數(shù)據(jù)挖掘引擎對審計(jì)數(shù)據(jù)進(jìn)行挖掘得出新的入侵規(guī)則，然后與知識(shí)庫中的規(guī)則對比。

（6）知識(shí)庫：此處存放數(shù)據(jù)挖掘所需要的領(lǐng)域知識(shí)，這些知識(shí)將用于指導(dǎo)數(shù)據(jù)挖掘的搜索過程或者用于幫助對挖掘結(jié)果的評估。

（7）數(shù)據(jù)挖掘引擎：這是數(shù)據(jù)挖掘系統(tǒng)的最基本部件，它通常包含一組挖掘功能模塊，以便完成定性歸納、關(guān)聯(lián)分析、分類歸納、進(jìn)化計(jì)算和偏差分析等挖掘功能。

（8）決策模塊：負(fù)責(zé)對非正常模式或未知模式進(jìn)行人工判斷。如果判斷結(jié)果是正常模式，則將其添加到知識(shí)庫中與其相近的正常模式。如果判斷結(jié)果為異常模式，則把它添加到知識(shí)庫中與其相近的異常模式，并立即執(zhí)行必要的防范措施。

5 結(jié)束語

本文在傳統(tǒng)的Apriori算法基礎(chǔ)上，提出了引入自適應(yīng)步長躍進(jìn)、動(dòng)態(tài)修剪候選項(xiàng)集的算法，大大減少了對數(shù)據(jù)庫的掃描次數(shù)，并顯著減少了候選集的數(shù)量，提高了算法的效率，具有重要的價(jià)值和廣泛的意義。

[1]郭山清，謝立，曾英佩.入侵檢測在線規(guī)則生成模型[J].計(jì)算機(jī)學(xué)報(bào)，2006(29),1523-1532.

[2]胡亮,金剛,于漫等.基于異常檢測的入侵檢測技術(shù)[J].吉林大學(xué)學(xué)報(bào)( 理學(xué)版)，2009(47),1264-1270.