淺析入侵模式挖掘系統結構算法

[摘 要]網絡日志數據量日益增大。如何從巨大的網絡數據中提取有效信息是數據研究人員一直關心的問題。入侵模式挖掘系統（Intrusion Digger）結合了數據挖掘技術與入侵檢測技術，旨在通過發現關聯規則而對網絡數據進行判別。最小支持度小于所有支持度的項集稱為頻繁項集，簡稱頻集。基于劃分改進的Apriori算法明顯優越于原來的算法。基于劃分改進的Apriori算法為入侵模式挖掘系統的設計提供了重要的理論支持。

[關鍵詞]入侵模式挖掘系統 基于劃分改進的Apriori算法 數據挖掘

[中圖分類號] G642 [文獻標識碼] A [文章編號] 2095-3437（2013）15-0036-02

一、系統的實現原理

眾所周知，網絡日志數據量日益增大，從巨大的網絡數據中提取有用信息是入侵模式挖掘系統所要完成的工作。在這里我們使用數據挖掘的關聯分析方法，即產生頻繁項集與關聯規則。關聯規則就是我們得到的有用信息。在得到關聯規則后，我們便可以使用關聯規則對測試數據進行分析，判斷測試數據是正常數據還是非正常數據。對于判斷的結果，我們用一個評價體系來評測判斷結果的好壞。入侵模式挖掘系統結合了數據挖掘技術與入侵檢測技術，旨在通過發現關聯規則而對網絡數據來進行判別。因此，根據以上分析，入侵模式挖掘系統的總體大致設計圖如圖1.1所示。

■

圖1.1 入侵模式挖掘系統總體設計圖

圖1.1中方框內為數據或文件如原始網絡日志數據、測試結果文件等，初步設計有三個大的子系統，分別是模式挖掘系統、測試系統、評價系統。箭頭代表數據的流向或者結果的輸出，橢圓框內為入侵模式挖掘系統的初步設計的子系統。

二、系統的設計算法分析

（一）Apriori算法

本系統采用關聯分析方法中的Apriori算法作為核心算法。目前，該算法是挖掘布爾關聯規則頻繁項集算法中最有影響力的一種，基于兩階段頻集思想的遞推算法是其核心。在此，最小支持度小于所有支持度的項集稱為頻繁項集，簡稱頻集。[1]在分類上該關聯規則屬于單層、單維和布爾關聯規則，該關聯規則為了生成所有頻集，采用了遞推的方法。

算法思路：第一步，找出所有出現的頻繁性至少和預定義的最小支持度一樣的頻集。第二步，由頻集產生必須滿足最小可信度和最小支持度的強關聯規則。第三步，使用第一步找到的頻集產生只包含集合項的所有規則，其中每一條定義為中規則的右部只有一項的規則。第四步，大于用戶給定的最小可信度的規則被留下來生成我們需要的規則。

程序算法如下：

（1）L1 = find_frequent_1_itemset（D）；

（2）for（k = 2； Lk-1≠φ； k++）{

（3） Ck = apriori_gen（Lk-1）；

（4） for each t ∈ D{

（5） Ck = subset（Ck，t）；

（6） For each c ∈ Ct c.count++； }

（7）Lk = {c∈Ck| c.count > min_sup} }

（8）retrurn L = ∪Lk

該算法中首先產生頻繁1項集L1，其次產生頻繁2項集L2，然后直到有一個頻繁r值使得對應項集Lr為空，此時算法終止。Ck中的項集是用來產生頻集的候選項集，最終的頻集Lk一定是集合Ck的一個子集。在第k次循環中，算法先產生候選項k項集的集合Ck，Ck中的每一個項集屬于項集Lk-1的頻集來產生的下一個連接集合。Ck中的每個元素都需要在數據庫中進行驗證，然后才能決定該項是否能夠加入頻集Lk中。

Apriori算法的兩個嚴重不足會導致挖掘的效率非常低。一個方面，該算法在每進行一次迭代的時候掃描一次數據庫，多次掃描數據庫帶來巨大I/O開銷。另一個方面，該算法在迭代過程中需要在內存中產生、處理和保存數量巨大的候選頻集，這也導致算法在深度和廣度上的適應性很差。

（二）基于劃分改進的Apriori算法

為了提高Apriori算法的效率，需要對Apriori算法進行改進。本系統引入了一種基于劃分改進的Apriori算法，該算法只需要掃描數據庫兩次。第一次掃描中，將產生一組潛在的頻集，這組項集是最后需要確定的頻集的超集，它也可能包含錯誤的選擇，但絕對不可能漏掉正確的選擇。第二次掃描中，對這些潛在的頻集進一步計算它在整個數據庫中的實際支持度，可以最后確定所求得的真正的頻集。

算法思路：第一步，將整個數據庫盡可能劃分成N個子塊。第二步，針對每一個子塊單獨產生一組潛在的頻集。第三步，將上一步所有潛在的頻集合并為一個全局的候選頻集。第四步，在整個數據庫中，計算每個候選頻集的實際支持度，從而確定最后有用的頻集。

程序算法如下：

（1） P=partion_database（D）

（2）n=number of partitions

（3）for i=1 to n begin

（4）read_in_partition（PiP）

（5）LPi=gen_large_itemset（Pi）

（6）end

（7）for（i=2；LPi=φ，，J=1，2，…，n； i++）do

（8）CGi=ULPi

（9）forall candidates c∈CG do begin

（10）c.count++；

（11）Lk={c∈Ck|c.count≥min_sup}

（12）end

（13）answer=UkLk；

（14）Produce gen_large_itemset（Pi，min_sup）

（15）L1={Pi}；

（16）for（k=2；Lk-1≠？覫；k++）do begin

（17）Ck=apriori_gen（Lk-1，min_sup）；

（18）forall transactions∈tPi do begin

（19）Ct=subset（Ck，t）；

（20）forall candidations∈cCt do

（21）c.count++；

（22）end

（23）Lk={c= Ck|c.count≥min_sup*n}

（24）end

（25）return Lk

（26）Produce apriori_gen（Lk-1，min_sup）

（27）forall items l1∈Lk-1

（28）forall items l2∈Lk-1

（29）if（（l1[1]=l2[2]（∧…∧ l1[k-1]= l2[k-2]）∧（ l1[k-1] ？芻l2[k-2]））do begin

（30）c=l1？茌l2；

（31）if has_infrequent_itemset（c， Lk-1）

（32）delete c；

（33）else Ck=Ck∨{c}

（34）end；

（35）return Ck

（36）Produce has_infrequent_subset（c，Lk-1）

（37）forall （k-1）subset s of c

（38）if s？埸Lk-1 return true；

（39）else return 1

通過對基于劃分改進的Apriori算法解析，我們發現該算法有三大優點。

優點1、兩種算法掃描次數相比，基于劃分改進的Apriori算法掃描數據庫次數少。

優點2、基于劃分改進的Apriori算法第一次掃描數據庫產生的一組潛在的既有需要的也有不需要的頻集，它為第二次掃描數據庫進行計算及確認最后挖掘出有效頻集做了鋪墊。

優點3、基于劃分改進的Apriori算法進行數據挖掘是將數據庫劃分成N個子塊，先對每個子塊單獨產生一組頻集，然后再合并所有獨立產生的各組頻集構成一個全局的候選頻集。在數據量逐漸增多的情況下，這種“以大劃小，以小并行”的思想，可以使數據挖掘的效率大大提高。

綜上，通過分析比較可以看出，基于劃分改進的Apriori算法跟Apriori算法相比，確實有了相當不錯的改進，數據挖掘的效率大大提高了。基于劃分改進的Apriori算法為入侵模式挖掘系統的設計提供了重要的理論支持。

[ 參 考 文 獻 ]

[1] 劉明輝，周萍.基于Web挖掘的網站優化系統的研究[J].長春大學學報（自然科學版），2009，19（3）.

[2] aul Ammann，Duminda wijesekera and Saket kaushie. Scalable，graph-based network vulnerability analysis[A]. CCS’02[C]， Washington， DC， USA，2002.18-22.

[責任編輯：戴禎杰]