數(shù)據(jù)挖掘在入侵檢測系統(tǒng)中的應(yīng)用

1實(shí)驗(yàn)研究中的數(shù)據(jù)挖掘算法和計(jì)算機(jī)病毒隨著網(wǎng)絡(luò)安全問題的加劇，人們越來越重視入侵檢測技術(shù)。入侵檢測是防火墻的必要補(bǔ)充,在不影響網(wǎng)絡(luò)性能的情況下能對網(wǎng)絡(luò)進(jìn)行監(jiān)測,從而提供對內(nèi)部攻擊、外部攻擊和誤操作的保護(hù)。近年來,新的入侵檢測產(chǎn)品不斷出現(xiàn),新的入侵檢測方法理論不斷提出,尤其是將數(shù)據(jù)挖掘理論引入入侵檢測系統(tǒng),為入侵檢測系統(tǒng)的研究開拓了新的領(lǐng)域。哥倫比亞大學(xué)WenkeLee研究組將數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則挖掘、序列模式挖掘和分類算法應(yīng)用于入侵檢測系統(tǒng),是最先開始研究基于數(shù)據(jù)挖掘的入侵檢測系統(tǒng)的。他們利用不同的數(shù)據(jù)源,使用不同的檢測方法作了大量的實(shí)驗(yàn),數(shù)據(jù)源包括來自主機(jī)的數(shù)據(jù)和來自網(wǎng)絡(luò)的數(shù)據(jù),數(shù)據(jù)又可以分為網(wǎng)絡(luò)層數(shù)據(jù)和應(yīng)用層數(shù)據(jù),方法有誤用檢測和異常檢測。另外,新墨西哥大學(xué)的StephanieForrest研究組開發(fā)了系統(tǒng)調(diào)用序列的短序列匹配算法來檢測異常。數(shù)據(jù)挖掘本身是一項(xiàng)通用的知識發(fā)現(xiàn)技術(shù),其目的是要從海量數(shù)據(jù)中提取出我們所感興趣的數(shù)據(jù)信息。它有別于傳統(tǒng)入侵檢測系統(tǒng)的最大特點(diǎn)是特征自動構(gòu)建,免除了繁重的手工編碼過程,并提高了檢測準(zhǔn)確度。對于應(yīng)用到入侵檢測系統(tǒng)中的數(shù)據(jù)挖掘算法,目前主要集中在關(guān)聯(lián)、序列和分類這三種類型上。關(guān)聯(lián)分析算法關(guān)聯(lián)分析算法由R.Agrawal等人提出,希望挖掘出同一條審計(jì)記錄中不同字段之間存在的關(guān)聯(lián)關(guān)系。比較主流的算法有Apriori算法、AprioriTid算法。序列分析算法序列分析是希望挖掘出不同審計(jì)記錄之間的相關(guān)性。序列分析的目標(biāo)是在事務(wù)中挖掘出序列模式,即滿足用戶指定的最小支持度要求的頻繁序列,并且該序列模式不被任何其它序列所包含。代表算法是AprioriAll、AprioriSome以及PSP、GSP等。分類算法分類器的實(shí)質(zhì)是一個函數(shù)f(x)=c,它找出描述并區(qū)分?jǐn)?shù)據(jù)類或概念的模型(或函數(shù)),以便能夠使用模型的預(yù)測類標(biāo)記未知的對象類,導(dǎo)出模型是基于對訓(xùn)練數(shù)據(jù)集的分析。常用的分類算法有Ripper、ID3、C4.5、NaiveBayes、神經(jīng)網(wǎng)絡(luò)等。Ripper是由W.Cohen提出來的,是一種通用的分類規(guī)則生成算法,在對包含大量噪聲數(shù)據(jù)的數(shù)據(jù)集進(jìn)行處理時得到很好的性能。而且Ripper算法中的規(guī)則優(yōu)化模塊可以循環(huán)調(diào)用,從而進(jìn)一步提高了分類的準(zhǔn)確性。根據(jù)數(shù)據(jù)源的不同選擇,數(shù)據(jù)挖掘模型可以分為網(wǎng)絡(luò)型和主機(jī)型。根據(jù)檢測方法的不同又可分為誤用檢測和異常檢測。本文主要闡述網(wǎng)絡(luò)型異常入侵檢測的實(shí)現(xiàn)過程。2異常檢測方法當(dāng)一個用戶冒充另一個用戶時,由于他單獨(dú)的任何一個命令、數(shù)據(jù)包、連接都是正確的,因此,“內(nèi)部”濫用特權(quán)很難檢測到,很難區(qū)分用戶的一個單一事件是正常還是異常。而從整體來觀察,他的行為與被冒充用戶不同,因此可以使用異常檢測方法,通過觀察整個一次登錄會話來檢測這種入侵。使用數(shù)據(jù)挖掘作用戶行為模式的異常檢測,首先,我們對Bro程序中telnet會話的事件處理器程序進(jìn)行修改,可以獲得用戶向telnet主機(jī)遞交的所有shell命令,然后使用關(guān)聯(lián)規(guī)則和序列模式算法形成一個用戶模型框架,最后將用戶模型框架與需要檢測的當(dāng)前模式相比較,由此判斷是否出現(xiàn)異常。關(guān)聯(lián)規(guī)則和序列模式挖掘都有經(jīng)典的算法,本文只對如何比較歷史模式和當(dāng)前模式,產(chǎn)生相似度的方法作重點(diǎn)闡述:1)取得telnet會話中的shell命令審計(jì)記錄;2)挖掘關(guān)聯(lián)規(guī)則、序列模式;3)用遞歸相關(guān)函數(shù)、增量式相似度算法和相似度區(qū)域算法進(jìn)行模式比較。2.1pla的進(jìn)一步預(yù)處理為了進(jìn)行用戶行為的異常檢測,我們將用戶向telnet主機(jī)遞交的所有shell命令作進(jìn)一步預(yù)處理,去除編輯狀態(tài)下用戶輸入的內(nèi)容,命令參數(shù)僅保留文件的后綴名和敏感文件名。經(jīng)預(yù)處理后的shell命令審計(jì)記錄,如表1。2.2基于滑動窗口的歷史正常行為分析關(guān)聯(lián)規(guī)則是指考察一條審計(jì)記錄中的屬性,在滿足屬性最小支持度的條件下,找出頻繁的記錄。也就是說關(guān)聯(lián)規(guī)則用于挖掘數(shù)據(jù)記錄中不同數(shù)據(jù)項(xiàng)之間的關(guān)聯(lián)性。根據(jù)Shell命令審計(jì)記錄,在不同支持度下得到表2的關(guān)聯(lián)規(guī)則。序列模式是指在滿足記錄最小支持度的條件下,找出頻繁的審計(jì)記錄序列,也就是說序列分析就是發(fā)現(xiàn)不同數(shù)據(jù)記錄之間的相關(guān)性。序列模式挖掘的算法有AprioriAll、AprioriSome、DynamicSome等。這些算法通過對被觀察用戶的shell命令序列進(jìn)行計(jì)數(shù)來計(jì)算此用戶shell命令序列的支持度,進(jìn)而發(fā)現(xiàn)滿足支持度要求的大序列。由于我們的目標(biāo)是對單個用戶的shell命令集進(jìn)行常見序列的挖掘,因此采用了如下的滑動窗口分割法來確定序列模式的長度:假設(shè)S是用戶A的shell命令集,S={s1,s2,…,sn},其中si(i=1,2,…,n)代表用戶A執(zhí)行的每一條shell命令。指定滑動窗口的針對長度為Maxlen,最小支持度為MinSup。1)首先設(shè)定滑動窗口寬度的初試值len=1,在S中查找支持度大于MinSup的長度為1的序列,此時相當(dāng)于查找候選頻率大于MinSup的shell命令。2)遞增滑動窗口寬度(len=len+1),將窗口的左邊界重合在s1處,得到從S中獲取的長度為len的子序列Sub1={s1,…,slen},逐步向后滑動窗口,直到窗口的右邊界與sn重合。每滑動一步,都得到一個長度為len的子序列。滑動過程完成之后,得到從S中獲取的n-len+1個長度為len的子序列Subi={si,…,si+len-1},i=1,2,…,n-len+1,對這n-len+1個子序列進(jìn)行支持度計(jì)算,得到滿足MinSup要求的長度為len的序列。不同支持度下挖掘出來的序列模式如表3。從關(guān)聯(lián)規(guī)則和序列模式中總結(jié)出歷史正常行為模式,如表4,并得到相應(yīng)的身份判斷。為了使用歷史行為模式來檢測當(dāng)前的行為,我們模擬了一些異常會話過程,如表5。2.3用戶行為檢測是否異常在得到用戶的歷史行為模式和當(dāng)前行為模式之后,需要進(jìn)行模式比較工作,來檢測用戶行為是否異常。模式比較工作就是序列的比較,這里,引入相似度(similarity)的概念來表示不同行為之間的吻合程度。下面詳細(xì)介紹三種方法。2.3.1基于相關(guān)函數(shù)的挖掘假設(shè)X和Y代表要比較的兩個序列。全序列比較法:如果X序列和Y序列每個單元的值都相同,則比較結(jié)果為1,否則為0。該算法用于匹配關(guān)聯(lián)規(guī)則。相關(guān)函數(shù)法:找出X和Y序列中具有最大重合度的子序列,比較結(jié)果越大,說明X序列和Y序列的相似度越大。如果X和Y序列完全一致,則輸出結(jié)果為1。該算法用于匹配序列模式。遞歸式相關(guān)函數(shù)法:單一的相關(guān)函數(shù)法只能找出兩個序列中具有最大重合度的子序列,對于其它具有較小重合度的部分忽略不計(jì),因此并不能反映兩個序列的相似度,通常會導(dǎo)致計(jì)算結(jié)果低于模式比較相似度的門限值,產(chǎn)生錯誤的用戶異常報告。假設(shè)用戶歷史模式中存在如下命令序列:1)mail->cd->vi.c->gcc而在用戶的當(dāng)前模式中發(fā)現(xiàn)如下命令序列:2)mail->cd->ls->vi.c->gcc序列2)中僅僅在cd和vi命令之間多了一條ls命令。應(yīng)該說這兩個序列存在很好的相似度,然而用相關(guān)函數(shù)法得到的結(jié)果是0.4,也就是說這兩個序列的吻合程度還不到一半,這顯然不符合實(shí)際情況。其問題在于相關(guān)函數(shù)只提取了兩個序列中具有最大重合度的部分,而忽略了序列中的其它部分。遞歸式相關(guān)函數(shù)的算法仍然基于相關(guān)函數(shù)法,不同之處在于采用了循環(huán)的相關(guān)函數(shù)調(diào)用,并考慮了重合子序列在各自原始序列中的位置,可以提取出兩個序列中所有具有重合性的部分,從而得到的序列相似度更符合實(shí)際。使用遞歸式相關(guān)函數(shù)法得到的比較結(jié)果如表6。Roger給出的是關(guān)聯(lián)規(guī)則,他的異常行為是從其它客戶機(jī)登錄到telnet主機(jī)。Eric給出的是序列模式,他的異常行為是改為編輯.tex文件。利用全序列比較法和遞歸式相關(guān)函數(shù)算法計(jì)算關(guān)聯(lián)規(guī)則和序列模式的匹配程度,得到的相似度很高。實(shí)驗(yàn)證明,利用數(shù)據(jù)挖掘技術(shù)對用戶命令進(jìn)行關(guān)聯(lián)規(guī)則及序列模式挖掘,可以有效地發(fā)現(xiàn)用戶的行為模式;而采用遞歸式相關(guān)函數(shù)等序列匹配算法,計(jì)算用戶歷史模式和當(dāng)前模式的相似度,則為準(zhǔn)確判斷用戶行為提供了可能性。2.3.2相同單元個數(shù)相同但不連續(xù)兩個序列的實(shí)現(xiàn)普渡大學(xué)的Terranlan和Brodley,在實(shí)現(xiàn)相似度測量方面做了大量工作,也發(fā)表了許多文章,他們提出了一種增量式相似度算法。遞歸式相關(guān)函數(shù)法只能找出所有重合子序列,如果相比較的兩個序列連續(xù)出現(xiàn)相同的單元,則它們的相似度值應(yīng)該高于出現(xiàn)相同單元個數(shù)相同但不連續(xù)兩個序列,例如:seg1lsfoo;viseg2lsfoocatbarseg3ls-lfoo;seg4ls-Ffoocat則Sim(seg1,seg2)>Sim(seg3,seg4)實(shí)現(xiàn)方法如下:1)設(shè)置一個相鄰計(jì)數(shù)器c:=1,和相似度值Sim:=0;2)對于長度為n的每一個位置i;如果seg1(i)=seg2(i),則Sim:=f(Sim,c),c:=u(c);f(Sim,c)和u(c)為相似度的評分和更新函數(shù);否則c:=1;3)當(dāng)檢查完所有位置,返回相似度值Sim;4)最后得到一個序列segi與一組序列D的相似度值:Sim(segi,D)=max{Sim(segi,segj)}(其中segj∈D)此方法更符合實(shí)際情況,改進(jìn)了遞歸式函數(shù)法。2.3.3用戶異常特征提取上述方法比較了兩個序列的相似度,但是判斷兩個序列是否相似,還需要人為給定一個門限值。因此提出了一個相似度區(qū)域算法,在形成一個用戶歷史模型框架后,再通過訓(xùn)練正常數(shù)據(jù)得到一個相似度的范圍,如果需要檢測的當(dāng)前模式的相似度值落到正常范圍內(nèi),則判斷為正常。若落到另一個用戶組的范圍內(nèi),則判斷為異常,并說明此用戶很可能在冒充該用戶組成員。具體過程如下:利用DARPA數(shù)據(jù),在前4周收集數(shù)據(jù),找出6個用戶(Sysadm,Programmer1,Programmer2,Secretary,Manager1,Manager2)的行為作異常檢測分析,并挖掘出內(nèi)在的關(guān)聯(lián)規(guī)則和序列模式,得到歷史模式。第5周作訓(xùn)練,在此期間,分析一個用戶登錄會話,從命令序列中挖掘頻繁模式和序列模式。比較新模式集與模型框架,并得到一個相似值。假定新集合共有n個模式,其中有m個與模型框架匹配,則相似度簡單地記為m/n。顯然,相似值越高,表明用戶行為與歷史行為越相似。將每一個從會話中得到的模式與模型框架進(jìn)行比較,并記錄相似值的正常范圍。在第6周,出現(xiàn)用戶異常數(shù)據(jù)。對于每個異常會話,將模式與模型框架比較,并把相似值結(jié)果與記錄的正常范圍相比較。可以看到,如果未發(fā)生異常,異常檢測值比正常范圍小得多。表7給出前4周的歷史行為和第6周的異常行為,表8是第5周的訓(xùn)練數(shù)據(jù)模式與歷史模式比較得到的正常值范圍,和第6周的異常數(shù)據(jù)模式與歷史模式比較得到的異常值。假定按照用戶工作功能分n個可能的用戶組。當(dāng)i組的一個用戶沒有遵循組模型框架,于是想?yún)^(qū)分出這個用戶變到了哪一個組(如j組),也就是想知道這個用戶執(zhí)行了什么“不合法”的工作功能。在實(shí)驗(yàn)中,先建立了P組(Programmer)、S組(Secretory)、M組(Manager)、和Sa組(Sysadm)。從前4周的數(shù)據(jù)中,一個組中所有用戶的模式合并成為一個組模型框架。第5周的數(shù)據(jù)用來建立測量每一組所有用戶的相似值范圍。在第6周,用戶異常中包括“不合法的工作功能”實(shí)例,Programmer1變成Secretary,Secretary變成Manager,Sysadm變成Programmer。比較在一個異常會話中測量的每一個用戶相似值與他收集的正常相似值范圍,從每一個用戶正常的相似度測量值對應(yīng)的四個組可以看出,在第5周,每一個用戶確實(shí)有本組最大的相似度測量值。從用戶異常的相似度測量值可以看到,在第6周,每一個“不合法工作功能”實(shí)例,目標(biāo)組的相似度測量值是最大的(使用下劃線標(biāo)出)。例如,當(dāng)Sysadm變成Programmer,P組的相似度測量值是最大的,而Sa的相似度測量值超出了正常范圍。這種方法有待進(jìn)一步完善和實(shí)現(xiàn)。3u3000正常數(shù)據(jù)充足測試作異常檢測需要建立正常模型,正常模型的好壞與收集到的正常數(shù)據(jù)密切相關(guān)。如果收集的正常數(shù)據(jù)不充足,在作入侵檢測時,原本正常的數(shù)據(jù)就會因?yàn)檎ＤＰ偷牟煌晟贫徽`認(rèn)為是入侵。因此,判斷收集的數(shù)據(jù)是否充足是一個很重要的問題。為了結(jié)構(gòu)的完整性,我們在這里使用網(wǎng)絡(luò)級的異常檢測來檢測收集的審計(jì)數(shù)據(jù)是否充足。同樣使用tcpdump抓包工具,收集正常數(shù)據(jù)建立異常檢測模型,我們使用所有service的頻繁規(guī)則集來觀察審計(jì)數(shù)據(jù)是否充足。首先挖掘關(guān)聯(lián)規(guī)則和序列模式,得到規(guī)則集。然后將規(guī)則進(jìn)行編碼、合并,為每一條規(guī)則設(shè)置一個合并計(jì)數(shù)器(merge_count),它代表這條規(guī)則在一段時間內(nèi)出現(xiàn)的次數(shù),也代表這條規(guī)則的頻繁程度。當(dāng)某一條規(guī)則被合并,則這條規(guī)則的相應(yīng)合并計(jì)數(shù)器就加1,當(dāng)merge_count>=min_frequency時,表明這條規(guī)則是頻繁的。當(dāng)收集新的審計(jì)數(shù)據(jù)后,就會有新的頻繁規(guī)則出現(xiàn),規(guī)則總數(shù)在增加。如圖1所示,可以看到,所有service的頻繁規(guī)則數(shù)目在第8周時還處于增加較快階段,當(dāng)?shù)搅说?5周就逐漸變得平穩(wěn)了。這說明,在15周之后,收集的正常審計(jì)數(shù)據(jù)就充足了。雖然合并的規(guī)則集可以被用來識別收集“新行為”,