改進(jìn)的Apriori算法的入侵檢測系統(tǒng)研究

陳真

（韓山師范學(xué)院 潮州師范分院辦公室，廣東 潮州 521012）

改進(jìn)的Apriori算法的入侵檢測系統(tǒng)研究

陳真

（韓山師范學(xué)院 潮州師范分院辦公室，廣東 潮州 521012）

綜述了數(shù)據(jù)挖掘技術(shù)在網(wǎng)絡(luò)入侵檢測中的應(yīng)用，闡述了關(guān)聯(lián)規(guī)則分析在網(wǎng)絡(luò)入侵檢測中的應(yīng)用原理和最新的研究與改進(jìn)，并指出了目前存在的問題和未來研究的方向.改進(jìn)由k階頻繁項(xiàng)集生成k+1階候選頻繁項(xiàng)集時(shí)的連接和剪枝策略；改進(jìn)對事務(wù)的處理方式，當(dāng)所有聯(lián)接完成時(shí)只掃描一遍Lk-1，減少Apriori算法中的模式匹配所需的時(shí)間開銷.實(shí)驗(yàn)表明，該算法應(yīng)用于此系統(tǒng)來提取用戶行為特征和入侵模式特征，提高了整個(gè)系統(tǒng)的性能.

關(guān)聯(lián)規(guī)則；頻繁項(xiàng)集；候選項(xiàng)集；Apriori算法；Apriori_ids算法；入侵檢測

入侵檢測系統(tǒng)（intrusion detection system，IDS）是通過掃描操作系統(tǒng)的審計(jì)數(shù)據(jù)或網(wǎng)絡(luò)數(shù)據(jù)包信息來檢測未經(jīng)過授權(quán)或非法進(jìn)入系統(tǒng)和網(wǎng)絡(luò)或者濫用系統(tǒng)和網(wǎng)絡(luò)的用戶行為的系統(tǒng)，該系統(tǒng)通過系統(tǒng)審計(jì)記錄、分析和檢測網(wǎng)絡(luò)流量等手段來識(shí)別系統(tǒng)中的存在非法入侵的行為，及時(shí)地判斷、記錄并報(bào)警，使系統(tǒng)管理人員及時(shí)采取有效的措施來彌補(bǔ)系統(tǒng)漏洞.美國哥倫比亞大學(xué)Wenke Lee最早[1]提出將數(shù)據(jù)挖掘技術(shù)應(yīng)用于入侵檢測系統(tǒng)，在檢測中將審計(jì)記錄數(shù)據(jù)和網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行預(yù)處理及關(guān)聯(lián)規(guī)則挖掘分析，將產(chǎn)生的關(guān)聯(lián)規(guī)則添加到關(guān)聯(lián)規(guī)則庫中去，然后通過關(guān)聯(lián)規(guī)則庫中的規(guī)則匹配來判斷用戶行為是否入侵，從而達(dá)到提高檢測系統(tǒng)的可擴(kuò)展性和自適應(yīng)性，并有效減少漏報(bào)率和誤報(bào)率.

關(guān)聯(lián)規(guī)則[2]表示數(shù)據(jù)庫中某種關(guān)聯(lián)關(guān)系的一組對象之間的規(guī)則，其數(shù)學(xué)表達(dá)式：X→Y[c，s]，X，Y表示數(shù)據(jù)庫中的記錄，C為確信度，S為支持度.挖掘關(guān)聯(lián)規(guī)則就是將產(chǎn)生支持度和可信度數(shù)值分別與預(yù)先給定的Min_support和Min_conf相比較，若項(xiàng)集滿足其最小支持度，則稱之為頻繁項(xiàng)集.本文以Snort入侵檢測系統(tǒng)為基礎(chǔ)，提出了利用改進(jìn)的Apriori算法應(yīng)用于入侵檢測系統(tǒng)，該算法能夠更為高效的提取用戶行為特征和入侵模式特征，優(yōu)化了整個(gè)系統(tǒng)的性能.

1 相關(guān)工作

1.1 Apriori算法

最為經(jīng)典的關(guān)聯(lián)規(guī)則挖掘Apriori算法，是一種挖掘單維、布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)目集的算法，由Rakesh Agrawal Rama和krishnan Skrikant于 1993年提出的[3]，其算法思想：先掃描數(shù)據(jù)庫中所有事務(wù)，統(tǒng)計(jì)每個(gè)項(xiàng)集出現(xiàn)的頻繁項(xiàng)，剔除不滿足用戶設(shè)定的支持度的項(xiàng)集，得到頻繁1-項(xiàng)集；利用頻繁1-項(xiàng)集的連接，再生成候選2-項(xiàng)集.然后統(tǒng)計(jì)每個(gè)候選項(xiàng)集的支持計(jì)數(shù)，得到頻繁項(xiàng)集2-項(xiàng)集的集，如此重復(fù)下去，直到得到數(shù)據(jù)集中的所有頻繁項(xiàng)集.Apriori作為經(jīng)典的頻繁項(xiàng)目集生成算法，在關(guān)聯(lián)規(guī)則挖掘中具有里程碑的意義，但是隨著研究的進(jìn)一步深入，它的不足也暴露出來[4]：

1）每生成一個(gè)k-頻繁項(xiàng)集（k=1，2，…，k）都需要掃描一次數(shù)據(jù)庫，如此重復(fù)掃描數(shù)據(jù)庫的算法，對內(nèi)存占用較大的I/O開銷過大.

2）連接程序中重復(fù)相同的項(xiàng)目步驟太多，算法效率有待進(jìn)一步改進(jìn).

3）算法的剪枝步，?c∈C ，判斷Ck的k個(gè)（k-1）-子集是否都在Lk中，若存在一個(gè)（k-1）-子集不在Lk中，則剔除Ck.此步驟會(huì)多次掃描Lk，當(dāng)Ck很大時(shí)，算法的效率明顯低下.

1.2 目前改進(jìn)算法的研究

許多學(xué)者已經(jīng)開始Apriori算法從不同的層面或不同的策略提出了各種優(yōu)化算法，主要從減少生成候選項(xiàng)目集的數(shù)目及減少對數(shù)據(jù)庫的掃描次數(shù)方面進(jìn)行優(yōu)化，如在文獻(xiàn)[5]中作者把支持度低于Min_support對后面的頻繁項(xiàng)集不起作用的事務(wù)直接從數(shù)據(jù)庫中刪除，這樣提高了候選項(xiàng)集的計(jì)數(shù)速度，在一定程度上優(yōu)化了算法的效率.文獻(xiàn)[6]中提到在對第K次數(shù)據(jù)庫掃描中優(yōu)先適用于每個(gè)長度為l（l≥k）的事務(wù)來生成候選K-項(xiàng)集，從而減少對數(shù)據(jù)庫的掃描次數(shù)，以提高空間復(fù)雜度.王卉，屈強(qiáng)提出基于因子項(xiàng)集的并行化策略GP以發(fā)揮串行算法的剪枝功效[7]等，這些改進(jìn)后的算法挖掘的效率和性能都明顯高于Apriori算法.

2 Apriori算法的改進(jìn)

由于經(jīng)典Apriori算法需要循環(huán)多次掃描事務(wù)數(shù)據(jù)庫，對生成的候選集Ck中的每個(gè)元素都必須通過k循環(huán)掃描數(shù)據(jù)庫來檢驗(yàn)是否滿足Lk中，這樣占用了大量的的I/O負(fù)載.因此，減少兩個(gè)項(xiàng)集之間比較的項(xiàng)的個(gè)數(shù)和減少比較的項(xiàng)集個(gè)數(shù)，將直接影響后面減少連接的運(yùn)算量，確保提高運(yùn)行的效率的關(guān)鍵.

因此，本文在對生成的Lk及對支持度的計(jì)數(shù)中直接剔除不滿足條件的非頻繁項(xiàng)集，對事務(wù)數(shù)據(jù)進(jìn)行事務(wù)壓縮，從而減少Apriori算法中的模式匹配和剪枝步驟，減小掃描事務(wù)數(shù)據(jù)庫的大小，從而提高算法的效率.

2.1 Apriori算法改進(jìn)的思路

關(guān)聯(lián)規(guī)則挖掘Apriori算法改進(jìn)的主要思路如下：

1）減少候選集Ck的生成.在掃描數(shù)據(jù)庫之后，如果事務(wù)t不包含Ck中任何一個(gè)項(xiàng)集或事務(wù)t是Ck中某一項(xiàng)集的子集但不滿足預(yù)先給定的min_sup?port，就直接過濾掉.

2）減少判斷次數(shù).通過從Lk-1中提取元素來判斷是否滿足Ck中元素的子集，對Ck中數(shù)據(jù)項(xiàng)集的子集個(gè)數(shù)進(jìn)行統(tǒng)計(jì)，從而減少該算法的運(yùn)算量.

2.2 性質(zhì)及相關(guān)推論

性質(zhì)1 任何頻繁項(xiàng)集的一切非空子集為頻繁項(xiàng)集，則該項(xiàng)集的非頻繁項(xiàng)集的超集也是非頻繁項(xiàng)集[8].

證明 ?項(xiàng)集X，且X非頻繁項(xiàng)集，即P（X）＜min_support，則項(xiàng)集X中的子集i，項(xiàng)集i?X也不是頻繁的，即P( )i?X ＜min_support，則 Apriori性質(zhì)滿足反單調(diào)性.

性質(zhì)2 如果頻繁k-1項(xiàng)集存在頻繁k項(xiàng)集，則頻繁k-1項(xiàng)目集的個(gè)數(shù)必大于等于k.

證明 由性質(zhì)1可得，Lk生成頻繁k-1項(xiàng)集中必存在k個(gè)不同的k-1項(xiàng)子集，因此k-1項(xiàng)集的子集的個(gè)數(shù)必大于等于k，證畢.

推論1 若頻繁k-項(xiàng)目集還存在X為頻繁項(xiàng)目子集，則X生成的k個(gè)k-1維子集中，對?i∈X均存在.

證明 假設(shè)?X生成的k個(gè)k-1維子集中?i∈e，使 |LK-1(i)|＜ k-1 |，因?yàn)閕∈e，則可得i∈X，而根據(jù)性質(zhì)2證明可得知 |LK-1(i) |＞k-1，這與假設(shè)相矛盾.

此推論在修剪頻繁項(xiàng)集階段應(yīng)用將有效減少挖掘候選頻繁項(xiàng)集的時(shí)間開銷.

2.3 算法描述

根據(jù)以上性質(zhì)和算法改進(jìn)的思路，設(shè)計(jì)的改進(jìn)算法如下：

2.4 算法的分析

1）算法Apriori_ids完成連接，只要對Lk-1進(jìn)行1次掃描，對于Lk-1中存在元素e，判斷e是否為Ck中元素c的子集，對于小于k則剔除，反之，則對子集C進(jìn)行計(jì)數(shù).這樣避免了對事務(wù)的項(xiàng)目進(jìn)行大量的重復(fù)掃描集合和模式匹配計(jì)算，在一定程度上提高了算法的時(shí)間效率.

2）算法采用的數(shù)據(jù)結(jié)構(gòu)相對簡單，減少候選項(xiàng)集的迭代操作，避免了其他改進(jìn)算法中構(gòu)造復(fù)雜的數(shù)據(jù)結(jié)構(gòu)花費(fèi)太多的時(shí)間，也避免了對相應(yīng)的數(shù)據(jù)結(jié)構(gòu)復(fù)雜的算法操作，如文獻(xiàn)[5]對矩陣進(jìn)行相乘運(yùn)算就比較費(fèi)時(shí).

3 改進(jìn)的算法在IDS中的應(yīng)用

3.1 入侵檢測系統(tǒng)

根據(jù)入侵檢測系統(tǒng)和數(shù)據(jù)挖掘技術(shù)的特征，本文提出了一種基于關(guān)聯(lián)規(guī)則挖掘技術(shù)的入侵檢測系統(tǒng)，見圖1[10].

首先通過數(shù)據(jù)挖掘相關(guān)模塊對收集到數(shù)據(jù)信息進(jìn)行關(guān)聯(lián)挖掘，利用改進(jìn)Apriori算法找出滿足min_support和min_conft的頻繁K-項(xiàng)集，不滿足頻繁項(xiàng)集的，過濾掉，反之生成相應(yīng)的關(guān)聯(lián)規(guī)則，并利用特征構(gòu)造算法為模式添加附加特征，送入分類器形成分類規(guī)則，通過規(guī)則的添加和合并處理，形成入侵規(guī)則庫和正常行為規(guī)則庫，最后，檢測引擎通過規(guī)則相似度和規(guī)則匹配比較來檢測入侵.

圖1 基于關(guān)聯(lián)規(guī)則挖掘的入侵檢測模型Fig.1 Model of intrusion detection based on the mining technique of association

3.2 算法仿真實(shí)驗(yàn)分析

為了比較改進(jìn)Apriori算法與原始Apriori算法之間的運(yùn)算效率，本文進(jìn)行了實(shí)驗(yàn)，下面是實(shí)驗(yàn)結(jié)果和分析.

試驗(yàn)測試環(huán)境：主頻Intel3.0GHz，內(nèi)存為2GB，Windows XP的操作系統(tǒng)上進(jìn)行實(shí)驗(yàn).

實(shí)驗(yàn)參考數(shù)據(jù)來源于KDDCup99入侵檢測經(jīng)典數(shù)據(jù)集，KDDCup99共有4 898 345條數(shù)據(jù)記錄，其中正常數(shù)據(jù)972 780條，覆蓋4種類型的攻擊：Probing 41 102條、R2L90條、Dos 3 883 370條、U2R 1 003條.由于各方面復(fù)雜限制，我們這里選擇4個(gè)類型8種常見攻擊方式[11]進(jìn)行實(shí)驗(yàn)，見表1.

表1 實(shí)驗(yàn)攻擊類型Tab.1 Attack date types of experiment

實(shí)驗(yàn)主要基于原Apriori算法和改進(jìn)Apriori算法在相同數(shù)據(jù)量不同支持度下的執(zhí)行效率、以及相同支持度下不同數(shù)據(jù)量的執(zhí)行效率.這里我們?nèi)∽钚≈С侄萻upport=10%，confidence=50%（support（Xi→Yi）=|Xi∪Yi|，confidence（Xi→Yi）=|Xi∪Yi|/|Xi|，其中（Xi，Yi為事務(wù)集中同時(shí)包含Xi和Yi的事務(wù)數(shù)），實(shí)驗(yàn)數(shù)據(jù)見圖2、圖3.

圖3 不同事務(wù)規(guī)模下算法執(zhí)行的時(shí)間比較Fig.3 The analysis and comparison of the execution time of algorithms under different support degrees

由圖2可以看出，在相同支持度下Apriori_ids算法的時(shí)間曲線低于Apriori算法，即得到改進(jìn)的Apriori_ids算法時(shí)間開銷小于Apriori算法，在支持度較小的情況下，效果更明顯.

由圖3可以看出，傳統(tǒng)的Apriori算法隨著頻繁項(xiàng)集數(shù)量以及掃描數(shù)據(jù)集次數(shù)增多，執(zhí)行時(shí)間有突變性的增加，而改進(jìn)的Apriori_ids算法有效地應(yīng)用了性質(zhì)2及推論1，過濾了不滿足條件的候選項(xiàng)集，減少了頻繁項(xiàng)集數(shù)量以及數(shù)據(jù)集掃描次數(shù)，實(shí)驗(yàn)結(jié)果表明，Apriori_ids算法在性能優(yōu)于Apriori算法，特別在支持度小和數(shù)據(jù)規(guī)模大時(shí).

4 結(jié)束語

本文提出一種基于關(guān)聯(lián)規(guī)則挖掘的入侵檢測系統(tǒng)原型，利用改進(jìn)的Apriori_ids算法，能從大量審計(jì)數(shù)據(jù)中快速提取出規(guī)律，有效提高算法的運(yùn)行效率，解決入侵檢測海量數(shù)據(jù)挖掘，存儲(chǔ)優(yōu)化工作，大大提高了入侵檢測系統(tǒng)的性能.隨著網(wǎng)絡(luò)的進(jìn)一步發(fā)展，云計(jì)算即將成為未來網(wǎng)絡(luò)發(fā)展方向，而關(guān)聯(lián)規(guī)則的置信度和支持度模型在網(wǎng)絡(luò)動(dòng)態(tài)實(shí)時(shí)化方面表現(xiàn)了不足，對入侵檢測在實(shí)時(shí)性要求方面較差，因此，如何發(fā)展關(guān)聯(lián)規(guī)則對并行計(jì)算或分布式計(jì)算的支持將是我們繼續(xù)努力的主要方面，也是未來發(fā)展的趨勢.

[1]Lee W K.A framework for constructing features and mod?els for intrusion detection systems[J].ACM Transactions on Inforrnation and System Security,2000,3(4):227-261．

[2]劉君強(qiáng),孫曉瑩,潘云鶴.關(guān)聯(lián)規(guī)則挖掘技術(shù)研究的新進(jìn)展[J].計(jì)算機(jī)科學(xué),2004,31(1):110-113．

[3]Agrawa R,Imielinski T,Swami A.Mining Association Rules Between Sets ofItems in Large Databases[C]．Wash?ington DC,USA In Proceedings of the ACM SIGMOD Conf.on Management ofData(SIGMOD’93).New York:ACM Press,1993:207-216．

[4]區(qū)玉明,張師超,徐章艷,等.一種提高Apriori算法效率的方法[J].計(jì)鋅機(jī)工程與設(shè)計(jì),2004,25(5):846-848．

[5]Treinen J J,Thurimella R.A framework for the applica?tion of association rule mining in large intrusion detection infras tructures[C].you xiao ming.Recent Advance in In?trusion Detection May 2006.Berlin：Springer Verlag,2006:1-18．

[6]李清峰,楊路明,張曉峰,等.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則的一種高效的Apriori算法[J].計(jì)算機(jī)應(yīng)用與軟件,2004,21(12):84-86.

[7]王卉,屈強(qiáng).挖掘最大頻繁項(xiàng)集的并行化策略[J].微電子學(xué)與計(jì)算機(jī),2007,24(9):123-125．

[8]黃進(jìn),尹治本.關(guān)聯(lián)規(guī)則挖掘的Apriori算法的改進(jìn)[J].電子科技大學(xué)學(xué)報(bào),2003,32(1):76-79．

[9]何海濤,呂士勇,田海燕.基于改進(jìn)Apriori算法的護(hù)數(shù)據(jù)庫入侵檢測[J].計(jì)算機(jī)工程,2009,35(16):154-156.

[10]李家春,李之棠.神經(jīng)模糊入侵檢測系統(tǒng)的研究[J].計(jì)算機(jī)工程與應(yīng)用,2001,17:37-38．

[11]王勇,何倩,楊輝華,等.面向連接網(wǎng)絡(luò)入侵檢測實(shí)驗(yàn)測試系統(tǒng)的研究[J].計(jì)算機(jī)應(yīng)用,2006,26(增刊1):154-156.

Research on the Intrusion Detection Systems Based on the Improved Apriori Algorithm

CHEN Zhen
（Chaozhou Teacher's College，Hanshan Normal University，Chaozhou521012，China）

Main applications of data mining to network intrusion detection are reviewed，It describes the application theory of association rules analysis in network invasion monitoring and the latest research and improvements,and points out the existing problems and the direction for the future research.firstly，the strategy of the join step and the prune step was improved when candidate frequent（k+1）-itemsets were generated from frequent k-itemsets；secondly,the method of dealing with transaction was improved to reduce the time of pattern matching to be used in the Apriori algorithm；in the end,the method of dealing with data base was improved，which lead to only once scanning of frequent k-itemsets during the whole course of the algorithm.The experimental results of the improved algorithm show that the improved algorithm is more efficient than the original.

association rule；frequent itemsets；candidate item set；Apriori algorithm；Apriori_ids algorithm；intrusion detection system

TP 311.131

A

1674-4942（2012）01-0041-05

2011-11-29

黃 瀾