基于apriori算法的IDS技術實現

王福新

摘 要：使用關聯規則算法apriori與入侵檢測相結合，并針對Apriori算法對數據庫的描次數過多、系統的I/O負載大和產生大量的無關中間項集等弊端，提出了一種改進的Apriori算法，打破了傳統的算法實現步驟減少了數據庫的掃描次數，降低了系統I/O負載；實驗表明，改進的Apriori算法能有效地提高運行速度和效率，同時提高入侵檢測的效率與準確性。

關鍵詞：關聯規則；apriori算法；IDS

中圖分類號：TP311.13 文獻標識碼：A 文章編號：1671-2064（2017）19-0018-04

1 關聯規則挖掘算法

關聯規則（Association rules）挖掘是從大量數據中挖掘發現其項目集（itemset）之間的關聯或相關聯系.關聯規則挖掘問題是R.Agrawal等人于1993年在文獻中首先提出的.關聯規則是描述數據庫中一組數據項之間的某種潛在關系的規則。

經典的apriori。在已經提出的諸多關聯規則挖掘算法中，R.Agrawal和 R.Srikant在Apriori算法是挖掘布爾關聯規則頻繁項集算法中最有影響的.目前絕大多數的頻繁項集挖掘算法都是以Apriori算法為核心，或是其變體，或是其擴展。

Apriori算法的名字基于這樣的事實：算法使用頻繁項集性質的先驗知識，Apriori算法實際上是一種逐層搜索的迭代算法，k-項集用于探索（k+1）項集該算法將關聯規則的發現分為兩部分：

第一步是迭代出所有的頻繁項集；

第二步是由頻繁項集產生強關聯規則，根據定義，這些規則必須滿足最小支持度和最小置信度。

對于Apriori算法而言，它存在著本身難以克服的缺陷。

（1）多次掃描數據庫，在Apriori算法的描述中，每生成一個候選項集，都要對數據庫進行一次搜索.如果要生成最大長度為K的頻繁項集，則要對數據庫進行K次掃描，當數據庫中存放大量的數據時，在有限的內存容量下，系統I/O的負載就會相當大，每次掃描數據庫的時間就會很長，這樣效率當然非常低。

（2）它的瓶頸在于它的巨大的候選集的生成，例如，104個頻繁1-項集要生成107個候選2-項集要找尺寸為100的頻繁模式，如{X1，X2，…，X100}，你必須先產生2100（1030個候選集，因此，優化Apriori算法主要在于減少其候選集的生成。

2 apriori與入侵檢測

2.1 入侵檢測

入侵檢測系統（Intrusion Detection System IDS）可以定義為識別針對計算機或網絡資源的惡意企圖和行為并對此做出響應的系統.它通過對計算機網絡或計算機系統中的若干關鍵點收集信息并對其進行分析，從中發現網絡或系統中是否有違反安全策略的行為和被攻擊的跡象。入侵檢測系統是將進行入侵檢測的軟件與硬件的組合，它是一種主動的防護措施，它從系統內部和網絡中收集信息，從這些信息中分析計算機是否有安全問題，并采取相應的措施。

2.2 基于apriori的入侵檢測模型（見圖1）

通過對網絡信息進行預處理通過apriori提取用戶行為特征或規則等，再對所得的規則進行歸并更新，建立起規則庫，依據規則庫的規則對當前用戶的行為進行模式匹配，判斷用戶的訪問行為是否合法并將結果輸出給用戶。

3 apriori的優化

Apriori算法每次生成候選項目集后，又要回去掃描數據庫來判斷這些是否頻繁項目集，來判斷這些候選項目集是否頻繁項目集，造成了I/O的開銷很大，效率很低，因此，在算法的第一步對Apriori進行優化。

（1）優化方法一：根據頻繁k-項集的支持事務來計算候選（k+1）-項集中候選項的支持度，進而找出候選集中的頻繁項目，也就是說支持（k+1）-項集的事務必然也會支持它的k階子集.換句話說，支持（k+1）-項集的所有k階子集的事務必然也支持（k+1）-項集.這里我們定義：若集合D中有K+1個元素，那么由其中任何k元素組成的非空集合稱為集合D的k階子集.如果能夠從所有k階子集的支持事務中找出其交集即公共部分，那就相當于求出了（K+1）-項集的支持事務，這樣就避免了對源數據庫進行多次掃描，從而提高了算法的效率，以最小支持事務來作為剪枝的標準，我們定義最小支持事務為最小支持度（minsup）與數據庫記錄總數的乘積。

算法描述：TID事務的唯一編號，定義TIDS（Xk）是數據庫中項集Xk支持的事務的集合，TIDS（Xk）={TID：TID是Xk支持的}，最小支持事務=minsup×|D|。

算法偽代碼如下：

Procedure weight_apriori（Lk：find_frequent_k _itemset，S： descend power subset of Ck，TIDS（Ck）： set of Ck support transactions）

{

Scan D；

Find TIDS //掃描數據庫，記錄支持每個項目的事務

C1=Generate_C1（DB）；//生成候選1-項集

L1=find_frequent_1_itemset；//頻繁1-項集

K=2；

While Lk-1≠ {

CK = apriori_gen （LK - 1 ） ；//生成新的候選集

For each candidates itemset C∈CK {

Ck.suptrans= TIDS（Ck）；

For each descend power subset S {endprint

Ck.suptrans= Ck.suptrans∩S.suptrans；}

C.count= |Ck.suptrans|；//計算支持事務集中的元素個數.

K++；

}

//計算加權支持度

Lk = {c ∈Ck | C.count ≥ wminsup*|D|}；

}

Return F=Uk Lk ；

}

function Apriori_Gen（ Lk ）{

For all itemset g1 ， g2 ∈ Lk do {

if then {

add c to Ck ；

For all k-1 項集 do //剪枝

if （） then delete c from Ck ；

}}

Return Ck ；

}

算法的有效性分析：對于Apriori算法而言，在每次生成候選頻繁項目集后，要重復掃描數據庫計算項目集支持度判斷候選項目集是否頻繁項目集，造成了系統的布必要開銷，本算法只需要掃描一次數據庫，通過對降階子集支持的事務的交集進行計算，從而避免多次掃描數據庫即可求出所有頻繁項集，進而提高了算法的效率.關于權重的設定，對于權重的設定將直接影響關聯規則的挖掘結果，對于不同屬性的權重值的設定除了依賴于主觀的設定以外還可以根據實際情況建立模型來給出。

（2）優化方法二：在生成候選項目集之前判斷出某些候選項目集是非頻繁項目集，則可以在再次掃描數據庫計算支持度時不予考慮，這樣計算候選項目集支持度的記錄的數目小于數據庫原來的數目，以達到提高算法的效率的目的。

算法的描述：

Procedure weight_apriori（Lk：find_frequent_k _itemset，Rm： set of rm_item）

{

C1=Generate_C1（DB）；//生成候選1-項集

L1=find_frequent_1_itemset；//頻繁1-項集

K=2；

While Lk-1≠ {

CK = apriori_gen （LK - 1 ） ；//生成新的候選集

If RmCk

Delete Rm ；

K++；}

//計算加權支持度

Lk = {c ∈Ck | C.sup ≥ wminsup}；

Return F=Uk Lk

}

4 實驗結果及分析

經典的apriori應用IDS結果。使用麻省理工學院的林肯實驗室的一次分布式拒絕服務攻擊的數據作為實驗室數據，該數據使用基于網絡的tcpdump嗅探器采集保存為XML格式的日志文檔。

程序是使用C#語言進行編程實現的基于關聯規則的入侵檢測系統，該系統使用XML數據作為分析數據的來源，其中部分程序如下：

public void CreateItemsetSubsets（int Level， ItemsetArrayList itemSubset， ItemsetArrayList parentItemset，Database transactionsData）

{

int length = 0；

ItemsetArrayList childSubset = new ItemsetArrayList（1）；

ItemsetArrayList rulesItemset；

if（itemSubset.Count > Level）

{

foreach（ItemsetArrayList item in itemSubset）

{

ItemsetArrayList [] subsets = this.CreateItemsetSubsets（item）；

//僅有一個父項目用來生成關聯規則

if（parentItemset == null）

{ parentItemset = item； }

if （subsets ！= null）

{ length = subsets.Length； }

else{ break； }

for（int count = 0； count < length； count++）

{

//向項目表中添加項目與子集

transactionsData.AddSubset（item，subsets[count]）；

childSubset.Add（subsets[count]）；

//僅向 ItemsetArrayList 類中添加unique值

//創建一個含有的支持度，信任度和關聯規則的與子集相關的如

//父項-子集的規則項

rulesItemset = （parentItemset-subsets[count]）；

this.CreateItemsetRuleset（parentItemset， subsets[count]， rulesItemset，transactionsData）；

}

}

//為項目遞歸生成子集tendprint

childSubset.TrimToSize（）；

this.CreateItemsetSubsets（0， childSubset， parentItemset， transactionsData）；

}

}

由于tcpdump嗅探器保存下來的數據需要首先進行轉換預處理.既進行離散化，通過實驗得到一下結果.例如172.16.115.20， 202.77.162.213，tcp，1023，514。

通過試驗我們得到了一系列的關聯規則，如第84條規則。

202.77.162.213，tcp --> 514 63.1578947368421%

程序結果如圖2。

5 結語

基于Apriori的加權關聯規則算法是在Apriori算法基礎上針對Apriori算法由候選項目集生成頻繁項目集的過程進行的算法的優化。在Apriori算法的描述中每生成一個候選項集，都要對數據庫進行一次掃描，因此需要多次對數據庫進行掃描，當數據庫中存放大量的事務數據時，在有限的內存容量下，系統I/O負載就會非常大，每次掃描數據庫的時間就會很長，效率就非常低。

第一種優化方法只需要掃描一次數據庫，然后通過統計后選項集Ck的K階子集支持的事務來計算支持度的方法，減少了掃描數據庫的次數，從而提高了Apriori算法的運行效率；第二種優化方法并沒有從根本減少對數據庫的掃描次數，只是通過減少生成頻繁項目集中候選項目集中的記錄個數來達到提高Apriori算法效率的目的，這種方法在在數據庫的數據量很大時，效果并明顯，因此比較而言，第一種方法的效率應該較高.而兩種算法都是對經典apriori的效率改進，極大的提高了IDS的運行速度以及降低了其誤報率。實驗結果，見圖3。

參考文獻

[1]沈亮.網絡入侵檢測系統原理與應用[M].電子工業出版社，2013，（10）.

[2]崔貫勛，李梁，王柯柯，茍光磊，鄒航.關聯規則挖掘中Apriori算法的研究與改進[J]，計算機應用，2010（11）.

[3]薛靜鋒，祝烈煌.入侵檢測技術[M].人民郵電出版社，2016，（1）.

[4]關心，王新.基于數據挖掘的入侵檢測系統研究[J].信息技術，2007，（10）：100-103.

[5]章小龍.基于數據挖掘的入侵檢測系統研究[J].沈陽工程學院學報（自然科學版），2007，（10）：364-366.

[6]宋世杰，胡華平，胡笑蕾，金士堯.數據挖掘技術在網絡型異常入侵檢測系統中的應用[J]. 計算機應用，2003，（12）：20-23.

[7]牛建強，曹元大.基于數據挖掘的IDS日志數據分析處理[J].計算機應用研究，2003：82-84.

[8]張譯，劉衍珩，田大新，李川川，王媛.基于關聯規則的入侵檢測系統[J].吉林大學學報（信息科學版），2006，（3）：204-209.

[9]李川，張永輝譯.Ian H.Witten Eibe Frank Mark A.Hall著.數據挖掘實用機器學習工具與技術[M].機械工業出版社，2014，（5）.endprint