[摘 要] 針對(duì)關(guān)聯(lián)規(guī)則挖掘算法在處理海量數(shù)據(jù)的過(guò)程中存在的效率低、需要反復(fù)訪問(wèn)數(shù)據(jù)庫(kù)等,在入侵檢測(cè)系統(tǒng)產(chǎn)生誤報(bào)、效率低下等問(wèn)題。提出了基于關(guān)聯(lián)規(guī)則挖掘算法的ALT算法,設(shè)計(jì)了基于ALT算法的入侵警報(bào)檢測(cè)系統(tǒng)模型,通過(guò)實(shí)驗(yàn)證明ALT算法在減少入侵警報(bào)的數(shù)量和降低誤報(bào)率等方面明顯優(yōu)于其它算法。
[關(guān)鍵詞] ALT算法 入侵檢測(cè) 數(shù)據(jù)挖掘 警報(bào)分析
引言
入侵檢測(cè)技術(shù)是信息網(wǎng)絡(luò)安全技術(shù)的重要組成部分,而數(shù)據(jù)挖掘本身是一項(xiàng)通用的知識(shí)發(fā)現(xiàn)技術(shù),目的是從海量數(shù)據(jù)中提取出對(duì)解決問(wèn)題感興趣的數(shù)據(jù)信息 。Wenke Lee于1999年首次將數(shù)據(jù)挖掘技術(shù)引入入侵檢測(cè),提高入侵檢測(cè)系統(tǒng)(IDS)的準(zhǔn)確性和自適應(yīng)性。近年來(lái),由于入侵檢測(cè)技術(shù)對(duì)實(shí)時(shí)性要求較高,傳統(tǒng)的IDS效果都不明顯。這里提出一種改進(jìn)的高效關(guān)聯(lián)挖掘算法——ALT算法,將其應(yīng)用到入侵警報(bào)分析過(guò)程中,在保證入侵檢測(cè)實(shí)時(shí)性的前提下,減少侵警報(bào)的數(shù)量、降低誤報(bào)率,最終達(dá)到提高入侵檢測(cè)性能的目的。
一、ALT算法原理
ALT算法原理在于先求取所有的最大頻繁項(xiàng)目集,然后依次求取每一個(gè)最大頻繁項(xiàng)目集的子集,從而得到頻繁項(xiàng)目集。
ALT算法求最大頻繁項(xiàng)目集如下:
輸入:事務(wù)數(shù)據(jù)庫(kù),最小支持度;
輸出:最大頻繁項(xiàng)目集(Answer)。
(1)計(jì)算最小支持計(jì)數(shù),最小支持計(jì)數(shù)(Minsup)=最小支持度×事務(wù)數(shù);(2)生成頻繁1-項(xiàng)目集L,及其對(duì)應(yīng)的鏈表族;(3)依次處理頻繁K-項(xiàng)目集對(duì)應(yīng)的鏈表,據(jù)此得到最大頻繁項(xiàng)目集。
通過(guò)頻繁項(xiàng)目集分析,發(fā)現(xiàn)其中隱藏的異常模式,進(jìn)而進(jìn)行入侵檢測(cè)。
1.關(guān)聯(lián)規(guī)則挖掘。關(guān)聯(lián)規(guī)則挖掘算法中,最有影響的是Agrwal和Srikant于1994年提出的Apriori算法。但缺陷也十分明顯。針對(duì)Apriori算法的缺陷,文獻(xiàn)提出FP2Growth算法。該算法采用分而治之策略,將發(fā)現(xiàn)長(zhǎng)頻繁模式的問(wèn)題轉(zhuǎn)換為遞歸發(fā)現(xiàn)一些短模式。把數(shù)據(jù)庫(kù)中的頻繁項(xiàng)集壓縮進(jìn)一棵頻繁模式樹(shù)( FP2tree) 并分化成條件庫(kù),對(duì)這些條件庫(kù)分別進(jìn)行挖掘,大大降低了搜索開(kāi)銷,大約比Apriori算法快一個(gè)數(shù)量級(jí)。
2.ALT算法思想及實(shí)現(xiàn)步驟。ALT算法的基本思想是該算法只需遍歷事務(wù)數(shù)據(jù)庫(kù)一次,生成頻繁項(xiàng)目集簇,采用鏈表簇?cái)?shù)據(jù)結(jié)構(gòu)來(lái)存貯,通過(guò)指針來(lái)鏈接簇中的下一鏈表,生成新的頻繁項(xiàng)目集……。大大降低了算法存儲(chǔ)結(jié)構(gòu)的復(fù)雜度,提高算法的挖掘效率。其實(shí)現(xiàn)步驟如下:
首先,對(duì)事務(wù)數(shù)據(jù)庫(kù)進(jìn)行處理,遍歷事務(wù)數(shù)據(jù)庫(kù)一次,生成頻繁1-項(xiàng)目集。并由此可以得到頻繁2-項(xiàng)目集,頻繁3-項(xiàng)目集,……,頻繁k項(xiàng)目集。
其次,對(duì)于頻繁i(1≤i≤k)-項(xiàng)目集,采用鏈表簇?cái)?shù)據(jù)結(jié)構(gòu)存貯。簇中的每一鏈表用來(lái)表示頻繁i-項(xiàng)目集各項(xiàng)目的信息,表頭節(jié)點(diǎn)(patternData)和表節(jié)點(diǎn)(tidData)存儲(chǔ)結(jié)構(gòu)如圖1所示。
再次,對(duì)項(xiàng)目集簇進(jìn)行處理。如圖1所示,處理完一個(gè)項(xiàng)目集,用pattern來(lái)存儲(chǔ)頻繁i-項(xiàng)目集某一項(xiàng)目,通過(guò)nextL指針來(lái)鏈接簇中下一鏈表; 用newed來(lái)標(biāo)示項(xiàng)目集pattern域是否生成了新的頻繁項(xiàng)目集,同時(shí)也作為最大頻繁項(xiàng)目集判斷條件。
最后,求最大頻繁項(xiàng)目集,獲取頻繁項(xiàng)目集。初始值置為1,若由pattern域產(chǎn)生了新的頻繁項(xiàng)目集,其值變?yōu)閠rue,當(dāng)新的頻繁K+1項(xiàng)目集的鏈表族生成后,若某頻繁k項(xiàng)目集對(duì)應(yīng)newed域值仍然為1,則該頻繁-k項(xiàng)目集鏈表對(duì)應(yīng)的pattern域值為一最大頻繁項(xiàng)目集。依次求取每一個(gè)最大頻繁項(xiàng)目集的子集,從而得到頻繁項(xiàng)目集。
二、系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)
1.系統(tǒng)設(shè)計(jì)思想。入侵警報(bào)分為正常警報(bào)和異常警報(bào),本文提出的ALT算法入侵檢測(cè)分析系統(tǒng)是利用數(shù)據(jù)挖掘算法從正常警報(bào)數(shù)據(jù)中提取描述正常警報(bào)行為模式的關(guān)聯(lián)規(guī)則,通過(guò)分析入侵警報(bào),提取出真正攻擊的異常警報(bào),減少入侵檢測(cè)系統(tǒng)的警報(bào)數(shù)量,降低誤報(bào)率。最終生成相應(yīng)的頻繁項(xiàng)目集和關(guān)聯(lián)規(guī)則,數(shù)據(jù)挖掘過(guò)程的流程圖如圖2所示。
2.系統(tǒng)框架結(jié)構(gòu)?;谏鲜龅脑O(shè)計(jì)思想,入侵分析系統(tǒng)模型包括警報(bào)采集模塊、提取模塊、預(yù)處理模塊、數(shù)據(jù)挖掘模塊和分析模塊。利用關(guān)聯(lián)規(guī)則挖掘算法對(duì)入侵檢測(cè)系統(tǒng)產(chǎn)生的警報(bào)數(shù)據(jù)進(jìn)行過(guò)濾,提取出包含攻擊的入侵警報(bào),以達(dá)到減少警報(bào)數(shù)量、降低誤報(bào)率的目的。系統(tǒng)總體框架如圖3所示。各模塊功能如下:
(1)采集模塊。將網(wǎng)卡置于混雜模式,捕獲并分析網(wǎng)絡(luò)數(shù)據(jù)包,對(duì)異常的數(shù)據(jù)存入警報(bào)數(shù)據(jù)庫(kù)并報(bào)警產(chǎn)生的警報(bào)。(2)提取模塊。從警報(bào)數(shù)據(jù)庫(kù)中提取出系統(tǒng)需要的字段。(3)預(yù)處理模塊。對(duì)提取的警報(bào)數(shù)據(jù)對(duì)應(yīng)的IP地址由數(shù)值型轉(zhuǎn)化為點(diǎn)分十進(jìn)制的標(biāo)準(zhǔn)IP地址格式,將協(xié)議由數(shù)值型轉(zhuǎn)化為可讀性較好的字符串表示。(4)數(shù)據(jù)挖掘模塊。利用ALT算法挖掘經(jīng)過(guò)預(yù)處理的正常警報(bào)數(shù)據(jù),生成相應(yīng)的頻繁項(xiàng)目集。(5)分析模塊。分析、判斷警報(bào)是否正常,若正常,利用數(shù)據(jù)挖掘模塊更新關(guān)聯(lián)規(guī)則集,否則存入異常警報(bào)數(shù)據(jù)庫(kù)并報(bào)警。
三、實(shí)驗(yàn)結(jié)果和分析
1.算法執(zhí)行效率模擬實(shí)驗(yàn)。為了說(shuō)明ALT算法的執(zhí)行效率,本文在同樣的實(shí)驗(yàn)環(huán)境下將其與Apriori、FP2Growth算法進(jìn)行了比較。
實(shí)驗(yàn)環(huán)境: P4 3.0 GHz處理器, 320 GB硬盤, 512MB內(nèi)存,Windows XP操作系統(tǒng),VC++6.0開(kāi)發(fā)環(huán)境,實(shí)驗(yàn)數(shù)據(jù)集T10 I4D100K。算法執(zhí)行時(shí)間對(duì)比結(jié)果如表1所示,對(duì)比結(jié)果可以看出,在相同的支持度下, ALT算法所用的執(zhí)行時(shí)間比其他算法要少(尤其是在支持度較小的情況下) 。因此算法在執(zhí)行效率方面具有明顯的優(yōu)勢(shì)。
2.系統(tǒng)模擬實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)采用林肯實(shí)驗(yàn)室的DARPA99入侵檢測(cè)評(píng)估數(shù)據(jù)集在LAN中進(jìn)行,運(yùn)行Snort的主機(jī)配置同3.1。前臺(tái)開(kāi)發(fā)環(huán)境采用VC++6.0企業(yè)版,后臺(tái)數(shù)據(jù)庫(kù)采用SQL2000。實(shí)驗(yàn)結(jié)果如表2所示。其中Original表示直接由入侵檢測(cè)系統(tǒng)產(chǎn)生的警報(bào)數(shù)量,Abnormal表示經(jīng)過(guò)警報(bào)分析處理后的警報(bào)數(shù)量。從圖示的實(shí)驗(yàn)結(jié)果可以看出,系統(tǒng)在警報(bào)數(shù)量的精簡(jiǎn)方面效果較好,警報(bào)數(shù)量得到了降低,同時(shí)減少了誤報(bào)率。
四、結(jié)語(yǔ)
本文針對(duì)傳統(tǒng)算法在入侵檢測(cè)系統(tǒng)產(chǎn)生的警報(bào)數(shù)量多、誤報(bào)以及效率低下等問(wèn)題。提出基于關(guān)聯(lián)規(guī)則的改進(jìn)算法——ALT算法,設(shè)計(jì)了基于ALT算法的入侵警報(bào)檢測(cè)系統(tǒng)模型。 該模型借助特殊數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了最大頻繁項(xiàng)目集的挖掘,實(shí)現(xiàn)了關(guān)聯(lián)規(guī)則的快速發(fā)現(xiàn)。最后,通過(guò)實(shí)驗(yàn)證明了ALT算法在減少入侵警報(bào)的數(shù)量和降低誤報(bào)率等方面明顯優(yōu)于Apriori和FP2Growth算法。
參考文獻(xiàn):
[1]AGRAWAL R, IMIEL IENSKI T, SWAMIA. Mining association rulesbetween sets of items in large databases [C]//Proceedings of the ACM SIGMOD Conference on Management of data. New York: ACMPress, 1993: 207 - 216
[2]AGRAWAL A,MANN ILA H, SR IKANT R, et al. Fast discovery of association rules [Z].Cambridge: AAA I Press/M IT Press,1996:307~328
[3]HAN J, PEI H, YIN Y. Mining frequent patterns without candidate generation[C]//2000ACM2SIGMOD.New York: ACM Press,2000
[4]BORGELT C. Efficient implementations of a priori and eclat [C ] / /Proceedings of the IEEE ICDM Workshop on Frequent ItemsetMining Implementations. Melbourne: IEEE Press, 2003
[5]WANG X M, BORGELT C, KRUSE R. Fuzzy frequent pattern discovery based on recursive elimination[C]//ICMLA 2005. New York: IEEE Press, 2005: 391~396
[6]BORGELT C. Keeping things simple: Finding frequent item sets by recursive elimination[C]//OSDM 2005.New York: ACM Press,2005: 66~70
[7]馮玉才 馮劍琳:關(guān)聯(lián)規(guī)則的增量式更新算法[J].軟件學(xué)報(bào),1998,9(1):301~306
[8]IBM Almaden Research Center. Synthetic data generation code for associations and sequential patterns [EB/OL].[2008-02-15].http://www. almaden. ibm. com / software /quest/ resources/ index.shtml