基于apriori算法的IDS技術(shù)實(shí)現(xiàn)

王福新

摘 要：使用關(guān)聯(lián)規(guī)則算法apriori與入侵檢測(cè)相結(jié)合，并針對(duì)Apriori算法對(duì)數(shù)據(jù)庫的描次數(shù)過多、系統(tǒng)的I/O負(fù)載大和產(chǎn)生大量的無關(guān)中間項(xiàng)集等弊端，提出了一種改進(jìn)的Apriori算法，打破了傳統(tǒng)的算法實(shí)現(xiàn)步驟減少了數(shù)據(jù)庫的掃描次數(shù)，降低了系統(tǒng)I/O負(fù)載；實(shí)驗(yàn)表明，改進(jìn)的Apriori算法能有效地提高運(yùn)行速度和效率，同時(shí)提高入侵檢測(cè)的效率與準(zhǔn)確性。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則；apriori算法；IDS

中圖分類號(hào)：TP311.13 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671-2064（2017）19-0018-04

1 關(guān)聯(lián)規(guī)則挖掘算法

關(guān)聯(lián)規(guī)則（Association rules）挖掘是從大量數(shù)據(jù)中挖掘發(fā)現(xiàn)其項(xiàng)目集（itemset）之間的關(guān)聯(lián)或相關(guān)聯(lián)系.關(guān)聯(lián)規(guī)則挖掘問題是R.Agrawal等人于1993年在文獻(xiàn)中首先提出的.關(guān)聯(lián)規(guī)則是描述數(shù)據(jù)庫中一組數(shù)據(jù)項(xiàng)之間的某種潛在關(guān)系的規(guī)則。

經(jīng)典的apriori。在已經(jīng)提出的諸多關(guān)聯(lián)規(guī)則挖掘算法中，R.Agrawal和 R.Srikant在Apriori算法是挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集算法中最有影響的.目前絕大多數(shù)的頻繁項(xiàng)集挖掘算法都是以Apriori算法為核心，或是其變體，或是其擴(kuò)展。

Apriori算法的名字基于這樣的事實(shí)：算法使用頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)，Apriori算法實(shí)際上是一種逐層搜索的迭代算法，k-項(xiàng)集用于探索（k+1）項(xiàng)集該算法將關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)分為兩部分：

第一步是迭代出所有的頻繁項(xiàng)集；

第二步是由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，根據(jù)定義，這些規(guī)則必須滿足最小支持度和最小置信度。

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

（1）多次掃描數(shù)據(jù)庫，在Apriori算法的描述中，每生成一個(gè)候選項(xiàng)集，都要對(duì)數(shù)據(jù)庫進(jìn)行一次搜索.如果要生成最大長(zhǎng)度為K的頻繁項(xiàng)集，則要對(duì)數(shù)據(jù)庫進(jìn)行K次掃描，當(dāng)數(shù)據(jù)庫中存放大量的數(shù)據(jù)時(shí)，在有限的內(nèi)存容量下，系統(tǒng)I/O的負(fù)載就會(huì)相當(dāng)大，每次掃描數(shù)據(jù)庫的時(shí)間就會(huì)很長(zhǎng)，這樣效率當(dāng)然非常低。

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

2 apriori與入侵檢測(cè)

2.1 入侵檢測(cè)

入侵檢測(cè)系統(tǒng)（Intrusion Detection System IDS）可以定義為識(shí)別針對(duì)計(jì)算機(jī)或網(wǎng)絡(luò)資源的惡意企圖和行為并對(duì)此做出響應(yīng)的系統(tǒng).它通過對(duì)計(jì)算機(jī)網(wǎng)絡(luò)或計(jì)算機(jī)系統(tǒng)中的若干關(guān)鍵點(diǎn)收集信息并對(duì)其進(jìn)行分析，從中發(fā)現(xiàn)網(wǎng)絡(luò)或系統(tǒng)中是否有違反安全策略的行為和被攻擊的跡象。入侵檢測(cè)系統(tǒng)是將進(jìn)行入侵檢測(cè)的軟件與硬件的組合，它是一種主動(dòng)的防護(hù)措施，它從系統(tǒng)內(nèi)部和網(wǎng)絡(luò)中收集信息，從這些信息中分析計(jì)算機(jī)是否有安全問題，并采取相應(yīng)的措施。

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

通過對(duì)網(wǎng)絡(luò)信息進(jìn)行預(yù)處理通過apriori提取用戶行為特征或規(guī)則等，再對(duì)所得的規(guī)則進(jìn)行歸并更新，建立起規(guī)則庫，依據(jù)規(guī)則庫的規(guī)則對(duì)當(dāng)前用戶的行為進(jìn)行模式匹配，判斷用戶的訪問行為是否合法并將結(jié)果輸出給用戶。

3 apriori的優(yōu)化

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

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

算法描述：TID事務(wù)的唯一編號(hào)，定義TIDS（Xk）是數(shù)據(jù)庫中項(xiàng)集Xk支持的事務(wù)的集合，TIDS（Xk）={TID：TID是Xk支持的}，最小支持事務(wù)=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 //掃描數(shù)據(jù)庫，記錄支持每個(gè)項(xiàng)目的事務(wù)

C1=Generate_C1（DB）；//生成候選1-項(xiàng)集

L1=find_frequent_1_itemset；//頻繁1-項(xiàng)集

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|；//計(jì)算支持事務(wù)集中的元素個(gè)數(shù).

K++；

}

//計(jì)算加權(quán)支持度

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 項(xiàng)集 do //剪枝

if （） then delete c from Ck ；

}}

Return Ck ；

}

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

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

算法的描述：

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

{

C1=Generate_C1（DB）；//生成候選1-項(xiàng)集

L1=find_frequent_1_itemset；//頻繁1-項(xiàng)集

K=2；

While Lk-1≠ {

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

If RmCk

Delete Rm ；

K++；}

//計(jì)算加權(quán)支持度

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

Return F=Uk Lk

}

4 實(shí)驗(yàn)結(jié)果及分析

經(jīng)典的apriori應(yīng)用IDS結(jié)果。使用麻省理工學(xué)院的林肯實(shí)驗(yàn)室的一次分布式拒絕服務(wù)攻擊的數(shù)據(jù)作為實(shí)驗(yàn)室數(shù)據(jù)，該數(shù)據(jù)使用基于網(wǎng)絡(luò)的tcpdump嗅探器采集保存為XML格式的日志文檔。

程序是使用C#語言進(jìn)行編程實(shí)現(xiàn)的基于關(guān)聯(lián)規(guī)則的入侵檢測(cè)系統(tǒng)，該系統(tǒng)使用XML數(shù)據(jù)作為分析數(shù)據(jù)的來源，其中部分程序如下：

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）；

//僅有一個(gè)父項(xiàng)目用來生成關(guān)聯(lián)規(guī)則

if（parentItemset == null）

{ parentItemset = item； }

if （subsets ！= null）

{ length = subsets.Length； }

else{ break； }

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

{

//向項(xiàng)目表中添加項(xiàng)目與子集

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

childSubset.Add（subsets[count]）；

//僅向 ItemsetArrayList 類中添加unique值

//創(chuàng)建一個(gè)含有的支持度，信任度和關(guān)聯(lián)規(guī)則的與子集相關(guān)的如

//父項(xiàng)-子集的規(guī)則項(xiàng)

rulesItemset = （parentItemset-subsets[count]）；

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

}

}

//為項(xiàng)目遞歸生成子集tendprint

childSubset.TrimToSize（）；

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

}

}

由于tcpdump嗅探器保存下來的數(shù)據(jù)需要首先進(jìn)行轉(zhuǎn)換預(yù)處理.既進(jìn)行離散化，通過實(shí)驗(yàn)得到一下結(jié)果.例如172.16.115.20， 202.77.162.213，tcp，1023，514。

通過試驗(yàn)我們得到了一系列的關(guān)聯(lián)規(guī)則，如第84條規(guī)則。

202.77.162.213，tcp --> 514 63.1578947368421%

程序結(jié)果如圖2。

5 結(jié)語

基于Apriori的加權(quán)關(guān)聯(lián)規(guī)則算法是在Apriori算法基礎(chǔ)上針對(duì)Apriori算法由候選項(xiàng)目集生成頻繁項(xiàng)目集的過程進(jìn)行的算法的優(yōu)化。在Apriori算法的描述中每生成一個(gè)候選項(xiàng)集，都要對(duì)數(shù)據(jù)庫進(jìn)行一次掃描，因此需要多次對(duì)數(shù)據(jù)庫進(jìn)行掃描，當(dāng)數(shù)據(jù)庫中存放大量的事務(wù)數(shù)據(jù)時(shí)，在有限的內(nèi)存容量下，系統(tǒng)I/O負(fù)載就會(huì)非常大，每次掃描數(shù)據(jù)庫的時(shí)間就會(huì)很長(zhǎng)，效率就非常低。

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

參考文獻(xiàn)

[1]沈亮.網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)原理與應(yīng)用[M].電子工業(yè)出版社，2013，（10）.

[2]崔貫勛，李梁，王柯柯，茍光磊，鄒航.關(guān)聯(lián)規(guī)則挖掘中Apriori算法的研究與改進(jìn)[J]，計(jì)算機(jī)應(yīng)用，2010（11）.

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

[4]關(guān)心，王新.基于數(shù)據(jù)挖掘的入侵檢測(cè)系統(tǒng)研究[J].信息技術(shù)，2007，（10）：100-103.

[5]章小龍.基于數(shù)據(jù)挖掘的入侵檢測(cè)系統(tǒng)研究[J].沈陽工程學(xué)院學(xué)報(bào)（自然科學(xué)版），2007，（10）：364-366.

[6]宋世杰，胡華平，胡笑蕾，金士堯.數(shù)據(jù)挖掘技術(shù)在網(wǎng)絡(luò)型異常入侵檢測(cè)系統(tǒng)中的應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用，2003，（12）：20-23.

[7]牛建強(qiáng)，曹元大.基于數(shù)據(jù)挖掘的IDS日志數(shù)據(jù)分析處理[J].計(jì)算機(jī)應(yīng)用研究，2003：82-84.

[8]張譯，劉衍珩，田大新，李川川，王媛.基于關(guān)聯(lián)規(guī)則的入侵檢測(cè)系統(tǒng)[J].吉林大學(xué)學(xué)報(bào)（信息科學(xué)版），2006，（3）：204-209.

[9]李川，張永輝譯.Ian H.Witten Eibe Frank Mark A.Hall著.數(shù)據(jù)挖掘?qū)嵱脵C(jī)器學(xué)習(xí)工具與技術(shù)[M].機(jī)械工業(yè)出版社，2014，（5）.endprint