改進關聯規則數據挖掘在網絡入侵檢測中的應用

張群慧

(湖南信息科學職業學院 湖南 410151)

0 引言

要從海量的數據中挖掘出有用的信息知識，關聯規則是數據挖掘的主要工具之一。它主要是能夠從大量的數據中尋找出數據之間的關聯關系。作為傳統網絡安全技術的補充，入侵檢測受到更多的重視。基于模式匹配、統計分析和完整性分析的傳統入侵檢測方法，逐漸不能適應快速發展的網絡安全技術。將關聯規則引入到入侵檢測中，可以適應快速發展的網絡技術并提高入侵檢測的檢測效率。

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

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

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

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

Apriori算法存在以下缺點：

（1）可能產生大量的候選項集，特別是候選2-項集。如果有1000個頻繁1-項集，那么該算法將會產生105數量級的候選2-項集。

（2）可能需要重復地掃描數據庫。

（3）計數工作量可能非常大。

2 改進的Apriori 算法及其算法實驗

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

3 動態修剪候選項集。頻繁項集的特征

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

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

本文主要是在一次生成候選項集的時候按照上述性質，通過縮減和刪除數據集的規模，減少候選項集的個數，從而使得搜索空間比原來小，使Apriori算法在搜索空間上得到改進。

在原來的Apriori算法基礎上，改進算法U-Apriori的實現的主要步驟如下：

輸入：經過布爾化的數據庫D，最小化支持閾值min_sup

輸出：Li，D中的頻繁項集。

（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：改進Apriori 算法的實驗。在一臺計算機CPU Intel P4 2.0G， 內存為512M 上對Apriori 算法與其改進算法進行實驗測試對比（時間單位：小時） 。試驗仿真數據來源：chess數據集（http：//fimi.cs. helsinki. fi/）。所得實驗結果如圖1所示。

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

4 改進的算法在入侵檢測中的應用

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

圖1 Aprior算法改進前和改進后算法性能比較

（1）數據獲取：在網絡上截取用于檢測的數據。

（2）數據預處理：對網絡上捕獲到的原始網絡數據，需要先進行預處理，將它們轉換成ASCII碼格式的網絡分組信息，再將網絡分組信息處理成網絡連接記錄，并將其放入審計記錄庫，為數據挖掘做準備。

（3）審計記錄庫：審計記錄庫存放從網絡上得到的各種數據。

（4）數據訓練集：在系統初期，需要收集數據進行訓練，把已知系統缺陷和其他已知攻擊模式裝入知識庫中。

（5）數據挖掘算法庫：在挖掘算法庫的指導下, 數據挖掘引擎對審計數據進行挖掘得出新的入侵規則，然后與知識庫中的規則對比。

（6）知識庫：此處存放數據挖掘所需要的領域知識，這些知識將用于指導數據挖掘的搜索過程或者用于幫助對挖掘結果的評估。

（7）數據挖掘引擎：這是數據挖掘系統的最基本部件，它通常包含一組挖掘功能模塊，以便完成定性歸納、關聯分析、分類歸納、進化計算和偏差分析等挖掘功能。

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

5 結束語

本文在傳統的Apriori算法基礎上，提出了引入自適應步長躍進、動態修剪候選項集的算法，大大減少了對數據庫的掃描次數，并顯著減少了候選集的數量，提高了算法的效率，具有重要的價值和廣泛的意義。

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

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