基于數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則Apriori改進(jìn)算法的入侵檢測系統(tǒng)的研究

1、第29卷第3期2011年8月貴州師范大學(xué)學(xué)報(自然科學(xué)版Journal of Guizhou Normal University (Natural Sciences Vol29No3Aug 2011文章編號:10045570(201103008404基于數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則Apriori 改進(jìn)算法的入侵檢測系統(tǒng)的研究張浩,景鳳宣*,謝曉堯(貴州師范大學(xué)貴州省信息與計算科學(xué)重點實驗室,貴州貴陽550001摘要:在眾多的關(guān)聯(lián)規(guī)則挖掘算法中,Apriori 算法是最為經(jīng)典的一個,但Apriori 算法有以下缺陷:需要掃描多次數(shù)據(jù)庫、生成大量候選集以及迭代求解頻繁項集。因而提出了一種新方法,使Aprior

2、i 算法產(chǎn)生的候選項集再通過數(shù)據(jù)庫查找是否為頻繁項集,從而提高算法的效率。最后針對入侵檢測系統(tǒng)形成關(guān)聯(lián)規(guī)則。實驗結(jié)果表明,改進(jìn)后的算法能有效地提高關(guān)聯(lián)規(guī)則挖掘的效率。關(guān)鍵詞:數(shù)據(jù)挖掘;Apriori 算法;頻繁項集;入侵檢測系統(tǒng)中圖分類號:TP309文獻(xiàn)標(biāo)識碼:AThe Research of Intrusion Detection System Based on ImprovedApriori Algorithm of Data Mining Association RulesZHANG Hao ,JING Feng-xuan *,XIE Xiao-yao(Key Laboratory of

3、 Information and Computing Science of Guizhou Provinces ,Guizhou Normal University ,Guiyang ,Guizhou 550001,China Abstract :Among a large number of association rule mining algorithms ,Apriori algorithm is the most classic one ,but it has three deficiencies ,including scanning databases many times ,g

4、enerating a large number of candidate anthology ,and mining frequent itemsets iterativelyThis paper presented a meth-od ,Apriori algorithm to generate the candidate itemsets and then finds whether it is the frequent item-sets through the database ,thereby enhancing the efficiency of the algorithmFin

5、ally ,intrusion detec-tion system for the formation of association rules (IDS The experimental results show that the opti-mized algorithm can effectively improve the efficiency of mining association rulesKey words :Date mining ;Apriori algorithm ;Itemset ;Intrusion Detection System (IDS 0引言數(shù)據(jù)挖掘就是從存放

6、在數(shù)據(jù)庫、數(shù)據(jù)倉庫或其它信息庫中的大量數(shù)據(jù)中獲取有效的、最終可理解、新穎的、有用的模式的過程。因為數(shù)據(jù)量過大,所以大量的工作在于數(shù)據(jù)挖掘算法的方面。管理規(guī)則(Associate Rule 在數(shù)據(jù)挖掘中具有非常重要48收稿日期:20110608基金項目:貴州省科學(xué)技術(shù)基金(200917,貴州省科學(xué)技術(shù)基金(201037,貴州省科技廳工業(yè)攻關(guān)(20083009作者簡介:張浩(1986,男,碩士,信息安全,E mail :zhanghao_056163com*通訊作者:景鳳宣(1955,女,教授,信息安全,E mail :fxj989gznueducn的地位,也是數(shù)據(jù)挖掘的較為重要任務(wù)之一。入侵檢測

7、系統(tǒng)(Intrusion Detection System, IDS是對入侵行為的檢測。它通過收集和分析網(wǎng)絡(luò)行為、安全日志、審計數(shù)據(jù)、其它網(wǎng)絡(luò)上可以獲得的信息以及計算機(jī)系統(tǒng)中若干關(guān)鍵點的信息,檢查網(wǎng)絡(luò)或系統(tǒng)中是否存在違反安全策略的行為和被攻擊的跡象。入侵檢測作為一種積極主動地安全防護(hù)技術(shù),提供了對內(nèi)部攻擊、外部攻擊和誤操作的實時保護(hù),在網(wǎng)絡(luò)系統(tǒng)受到危害之前攔截和響應(yīng)入侵。因此被認(rèn)為是防火墻之后的第二道安全閘門,在不影響網(wǎng)絡(luò)性能的情況下能對網(wǎng)絡(luò)進(jìn)行監(jiān)測1。若在兩個或多個變量的取值之間存在某種規(guī)律性,則稱為關(guān)聯(lián),關(guān)聯(lián)規(guī)則是尋找在同一個事件中出現(xiàn)的不同項的管理性,其挖掘可以發(fā)現(xiàn)大量數(shù)據(jù)中數(shù)據(jù)項集之間

8、的關(guān)聯(lián)。比較經(jīng)典的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)方法是RAgrawal等人在ASI算法基礎(chǔ)上提出的改進(jìn)算法:Apriori算法,本文在經(jīng)典的Apriori 算法基礎(chǔ)上提出改進(jìn)方案,并應(yīng)用于入侵檢測系統(tǒng)中,并且具有一定實用價值。1Apriori算法11Apriori算法簡介Apriori算法首先找出所有的頻集,這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然后由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則,這些規(guī)則必須滿足最小可信度和最小支持度。再使用前面一步找到的期望的規(guī)則,產(chǎn)生只含有集合的項的所有規(guī)則,其中每一條規(guī)則的右部只有一項。Apriori算法主要缺點在于會產(chǎn)生大量的候選集,以及可能需要重復(fù)掃描數(shù)據(jù)庫。從下面幾個方面提高Ap

9、riori算法:1在通過掃描事務(wù)數(shù)據(jù)庫D,來甄別修剪后Ck中候選的k項集是否為頻繁的過程中,同時也將每個包含k項集的事務(wù)中包含的所有可能的(k+1項集加進(jìn)散列表中,如此,落在計數(shù)小于最小支持計數(shù)(=min-sup*|D|內(nèi)的(k+1項集就必定是非頻繁項集,給予刪除。2D的任一全局頻繁項集必須至少也是某個Di中的局部頻繁項集;反之,非局部頻繁項集必定非局部頻繁。如此,可以通過高效處理,大幅度壓縮D候選項集的集合。3通過隨機(jī)取樣建立D的子集,只從子集搜索頻繁項集,并使子集能一次性進(jìn)入內(nèi)存做高效處理,相當(dāng)于只需對D的子集做一次掃描。12算法舉例該例來自于Park等人的事務(wù)數(shù)據(jù)庫D。數(shù)據(jù)庫中有9個事務(wù)

10、,5個屬性,假定min_sup=2,min-support_count=3。對每個事務(wù)產(chǎn)生的2項目集,將它們散列到項目集的分配中。(1L1=find_frequent_1itemsets(D;(2for(k=2;Lk1;k+(3Ck=apriori_gen(Lk1,min_sup;(4for every transaction tD(5Ct=subset(Ck,t;(6for every candidate cCt(7ccount+;(8(9Lk=cCk|ccountmin_sup(10(11return L=Lk;2Apriori算法的改進(jìn)21關(guān)聯(lián)規(guī)則定義關(guān)聯(lián)規(guī)則是Agrawl等人于1993

11、年提出來的,關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則中的一個重要的研究內(nèi)容。關(guān)于這個算法有一個非常有名的故事:“尿布和啤酒”。故事是這樣的:美國的女性們經(jīng)常會囑咐她們的丈夫下班后為孩子買尿布,而丈夫在買完尿布后又要順手買自己愛喝的啤酒,因此啤酒和尿布在一起被購買的機(jī)會很多。這個舉措使尿布和啤酒的銷量均增加,并且一直為眾商家所津津樂道2。資料庫(Transaction Database:存儲二維結(jié)構(gòu)的記錄集。定義為:D所有項集(Items:所有項目的集合。定義為:I。記錄(Transaction:在資料庫里的記錄。定義為:T,TD項集(Itemset:同時出現(xiàn)的項的集合。定義為:k-itemset(k項集,k

12、-itemset T。除非特別聲明,否則下文出現(xiàn)的k均為項數(shù)。支持度(Support:定義為supp(X=count (X/count(D=P(X。解釋1:例如選秀比賽,選秀的支持度和它比較類似,觀眾(資料庫,其中有多少人是選擇(支持你的,那個就是支持度;解釋2:例如100個人去超市買東西的,其中58第3期張浩,景鳳宣,謝曉堯:基于數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則Apriori改進(jìn)算法的入侵檢測系統(tǒng)的研究買蘋果的有7個人,即說蘋果在這里的支持度是7,7/100;解釋3:P(X,意思是事件X出現(xiàn)的概率;解釋4:關(guān)聯(lián)規(guī)則當(dāng)中是有絕對支持度(個數(shù)和相對支持度(百分比之分的。置信度(Confidence/Streng

13、th:定義為conf(X Y=supp(XY/supp(X=P(Y|X。候選集(Candidate itemset:通過向下合并得出的項集。定義為Ck。頻繁集(Frequent itemset:支持度大于等于特定的最小支持度(Minimum Support/minsup的項集。表示為Lk。注意,頻繁集的子集一定是頻繁集。提升比率(提升度Lift:lift(XY=lift (YX=conf(XY/supp(Y=conf(YX/supp(X=P(X and Y/(P(XP(Y剪枝步:只有當(dāng)子集都是頻繁集的候選集才是頻繁集,這個篩選的過程就是剪枝步3。經(jīng)過關(guān)聯(lián)規(guī)則分析后,有針對性推銷(根據(jù)某規(guī)則比盲

14、目推銷(一般來說是整個數(shù)據(jù)的比率,這個比率越高越好,我們稱這個規(guī)則為強(qiáng)規(guī)則4。22算法的改進(jìn)由于Apriori算法重復(fù)掃描事務(wù)數(shù)據(jù),不僅浪費(fèi)大量時間,還增加I/O負(fù)載。因此本文試圖通過找到一種新的算法來取代通過候選集去找頻繁集的過程。具體算法如下:階段1:掃描數(shù)據(jù)庫D,得到頻繁1項集;將頻繁1項集按照支持度從大到小進(jìn)行排序,且記排好的序列為N;再次掃描D,構(gòu)建FP樹。階段2:搜索FP樹中對應(yīng)于葉子節(jié)點的每個項的條件模式集;從每個條件模式集構(gòu)建條件FP樹;從每顆條件FP樹遞歸地挖掘頻繁模式。這樣不僅可以避免大量候選集的產(chǎn)生,而且能減少對數(shù)據(jù)庫的掃描次數(shù),從而提高效率。該算法特點是只生成一顆條件模

15、式樹,且在遍歷條件模式樹時也不需要對全樹的進(jìn)行遍歷。本文用Java實現(xiàn)了上述改進(jìn)算法,事務(wù)數(shù)為80000,事務(wù)平均長度8,屬性長度235。運(yùn)行結(jié)果如下:23數(shù)據(jù)挖掘的入侵檢測模型圖2中,報警處理模塊對來自嗅探器,對于同一個攻擊原始數(shù)據(jù)形成新的攻擊事件,規(guī)則庫利用關(guān)聯(lián)規(guī)則知識庫的頻繁模式對事件進(jìn)行關(guān)聯(lián)分析,并預(yù)測未知的可能攻擊。將其結(jié)果提交給用戶5 。3實驗分析為了證明該算法的性能的改進(jìn),本文采用Snort2903在alert_fast模式下輸出報警6。數(shù)據(jù)采用未改進(jìn)的Apriori算法和改進(jìn)后的Apriori算法實驗數(shù)據(jù)。算法使用Java語言在MyEclipse平臺上實現(xiàn)。表1列出了在使用改進(jìn)

16、前的Apriori算法Snort 在所有檢測數(shù)據(jù)庫開啟時,每天報告的報警種類、報警數(shù)目以及誤報率。表2統(tǒng)計了改進(jìn)后Apriori 算法的報警種類、報警數(shù)目以及誤報率。實驗中min_sup=002,min_conf=002。表1算法改進(jìn)前數(shù)據(jù)表Tab1Before improve algorithm data數(shù)據(jù)來源報警數(shù)目報警類型誤報率/%算法改進(jìn)前第一天內(nèi)網(wǎng)164043算法改進(jìn)前第二天內(nèi)網(wǎng)134026算法改進(jìn)前第三天內(nèi)網(wǎng)143033算法改進(jìn)前第四天內(nèi)網(wǎng)83015算法改進(jìn)前第五天內(nèi)網(wǎng)11402768貴州師范大學(xué)學(xué)報(自然科學(xué)版第29卷表2算法改進(jìn)后數(shù)據(jù)表Tab2After improve al

17、gorithm data數(shù)據(jù)來源報警數(shù)目報警類型誤報率算法改進(jìn)后第一天內(nèi)網(wǎng)134024%算法改進(jìn)后第二天內(nèi)網(wǎng)940算法改進(jìn)后第三天內(nèi)網(wǎng)103018%算法改進(jìn)后第四天內(nèi)網(wǎng)630算法改進(jìn)后第五天內(nèi)網(wǎng)840實驗分析得到的強(qiáng)關(guān)聯(lián)規(guī)則數(shù)約占報警總數(shù)的03%。數(shù)據(jù)挖掘到IP地址為210406531: 5556頻繁受到“DOS”攻擊;同時挖掘到IP地址為210406560向其他IP發(fā)送包中都包含了“SYN”洪泛攻擊。從改進(jìn)的Apriori算法實驗中的數(shù)據(jù)集檢測到大量的IP地址為2104065246和IP地址為2101065251之間相互PING。從實驗結(jié)果分析還得知一般情況下系統(tǒng)的負(fù)載小于40%時,系統(tǒng)的誤

18、報率保持為0,系統(tǒng)負(fù)載高于40%時,系統(tǒng)的誤報率出現(xiàn)增加,并且誤報率會出現(xiàn)較快提升。通過實驗可以挖掘出一些有價值的信息,減少管理人員的工作量。4結(jié)束語經(jīng)典的Apriori算法多次掃描事務(wù)數(shù)據(jù)庫,需要很大的I/O負(fù)載和可能產(chǎn)生龐大的候選集從而導(dǎo)致挖掘效率很低。本文提出一種新的改進(jìn)算法。實驗表明,改進(jìn)后的算法能夠很快得到一些強(qiáng)關(guān)聯(lián)規(guī)則,在短時間內(nèi)挖掘出有價值的報警,減少管理人員的工作量。今后適用于入侵檢測技術(shù)的關(guān)聯(lián)規(guī)則挖掘算法的研究將會是研究的重點內(nèi)容之一。同時,通過關(guān)聯(lián)規(guī)則得到特征模式規(guī)則體現(xiàn)了決策屬性和行為之間的關(guān)聯(lián)關(guān)系,為進(jìn)一步運(yùn)用數(shù)據(jù)庫關(guān)聯(lián)規(guī)則挖掘提供可靠的依據(jù)。參考文獻(xiàn):1Han Jia Wei,Kamber M數(shù)據(jù)挖掘概念與技術(shù)M范明,孟曉峰,譯北京:機(jī)械工業(yè)出版社,2006:102-1032蘇新寧,