基于AC-BM改進(jìn)算法的入侵檢測(cè)技術(shù)研究論文
摘 要：網(wǎng)絡(luò)的飛速發(fā)展帶來(lái)了諸多安全隱患，入侵檢測(cè)技術(shù)作為一種積極防御手段成為了網(wǎng)絡(luò)安全領(lǐng)域的研究熱點(diǎn)。模式匹配由于原理簡(jiǎn)單、無(wú)需訓(xùn)練、檢測(cè)效率高、擴(kuò)展性好廣泛用于目前的入侵檢測(cè)系統(tǒng)。本文首先分析了模式匹配，比較了經(jīng)典的模式匹配算法，總結(jié)了其存在的問(wèn)題，并在此基礎(chǔ)上對(duì)AC-BM模式匹配算法進(jìn)行優(yōu)化，提出了AC-BM改進(jìn)算法，有效提高了檢測(cè)效率，降低了檢測(cè)過(guò)程中的資源消耗。
關(guān)鍵詞：入侵檢測(cè) 模式匹配 AC-BM改進(jìn)算法 檢測(cè)效率
隨著網(wǎng)絡(luò)的日新月異，網(wǎng)絡(luò)入侵行為變得越來(lái)越復(fù)雜，因此網(wǎng)絡(luò)安全也日益受到人們廣泛關(guān)注。入侵檢測(cè)系統(tǒng)能夠在不影響網(wǎng)絡(luò)正常工作的前提下，對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行監(jiān)測(cè)、收集和分析，進(jìn)而從中發(fā)現(xiàn)是否存在入侵行為 [1]。根據(jù)入侵檢測(cè)方法的不同，可以分為異常檢測(cè)技術(shù)和誤用檢測(cè)技術(shù)。誤用檢測(cè)技術(shù)存在一個(gè)已知攻擊模式特征庫(kù)，通過(guò)網(wǎng)絡(luò)數(shù)據(jù)與庫(kù)中攻擊模式進(jìn)行匹配來(lái)判斷是否存在入侵行為，其檢測(cè)的誤報(bào)率較低。誤用檢測(cè)中使用的檢測(cè)技術(shù)主要有模式匹配、專(zhuān)家系統(tǒng)、狀態(tài)轉(zhuǎn)移等，而模式匹配由于原理簡(jiǎn)單、可擴(kuò)展性好等特點(diǎn)被廣泛應(yīng)用[2]。網(wǎng)絡(luò)數(shù)據(jù)包的高速傳輸使得模式匹配算法應(yīng)用于入侵檢測(cè)領(lǐng)域面臨了諸多問(wèn)題，模式匹配的效率將直接影響入侵檢測(cè)的性能。
1 模式匹配
模式匹配是指：已知一長(zhǎng)度為n的文本字符串T=T1T2….Tn和一長(zhǎng)度為t (t
目前的模式匹配算法多分為單模式匹配和多模式匹配[3]。若每次文本串只能對(duì)一種模式串進(jìn)行模式匹配，這種方法稱(chēng)為單模式匹配算法。即己知文本串Text=T[l...n]和模式串Pattern=P[l...t]，對(duì)于1<=f<=n，存在T[f+1...f+t]=P[1…t]。
網(wǎng)絡(luò)入侵類(lèi)型日益復(fù)雜，為了提高匹配速度期望可以實(shí)現(xiàn)每次可以同時(shí)對(duì)多個(gè)模式進(jìn)行匹配，這種方法稱(chēng)為多模式匹配方法。也就是說(shuō)，文本字符串Text=T[l...n]對(duì)模式樹(shù)進(jìn)行掃描時(shí)，至少在模式樹(shù)種發(fā)現(xiàn)其中一個(gè)模式串與之相匹配。
2 應(yīng)用于入侵檢測(cè)的經(jīng)典模式匹配算法
2.1 BM算法[4]
BM基本思想是進(jìn)行匹配時(shí)，將文本字符串和模式串左邊對(duì)齊，然后從右向左進(jìn)行字符比較。如果字符匹配，則繼續(xù)進(jìn)行下一次比較;若模式字符P[k]和文本字符串T[i+k]文本字符串不匹配，此時(shí)分別計(jì)算Goodsuffix[k]和Badchar[T[i+k]]-(m-k) 兩個(gè)函數(shù)值中更大的那個(gè)作為偏移量，文本字符串指針向右移動(dòng)偏移量的長(zhǎng)度，進(jìn)而重新開(kāi)始匹配。此外，若找到了模式串在文本字符串中出現(xiàn)過(guò)一次，則文本字符串向右移動(dòng)Goodsuffix[0]的距離。一直進(jìn)行下去直到找出模式串所有可能出現(xiàn)的位置。
2.2 AC算法[5]
AC算法巧妙地將字符比較轉(zhuǎn)化為了狀態(tài)轉(zhuǎn)移。AC算法有以下兩個(gè)特點(diǎn)：一是掃描字符時(shí)不需要回溯;二是時(shí)間復(fù)雜度為O(n)，與模式的數(shù)目和長(zhǎng)度無(wú)關(guān)。
該方法的核心思想是在AC算法匹配開(kāi)始之前，首先建立轉(zhuǎn)向函數(shù)goto()，失效函數(shù)failure()和輸出函數(shù)output()，在此基礎(chǔ)上構(gòu)建出樹(shù)形狀態(tài)機(jī)。在掃描匹配階段，AC算法采用以上三個(gè)函數(shù)掃描文本字符串，從而搜索島模式串在文本字符串中所有出現(xiàn)的位置。
2.3 AC-BM算法[6]
AC-BM 算法的模式樹(shù)從文本右端向左邊移動(dòng)，每一次匹配時(shí)字符從左到右進(jìn)行比較，AC-BM算法同時(shí)使用壞字符移動(dòng)規(guī)則和好前綴移動(dòng)規(guī)則。
壞字符移動(dòng)：如果模式串與文本字符串不匹配，則移動(dòng)模式樹(shù)中其他模式分支和當(dāng)前比較字符相同的`那個(gè)字符的位置。如果在當(dāng)前深度上，模式樹(shù)中的任何一個(gè)模式分支在文本字符串中都沒(méi)有出現(xiàn)，則模式樹(shù)的移動(dòng)偏移量等于模式書(shū)中最短的模式分支的長(zhǎng)度min l。
好前綴移動(dòng)：移動(dòng)模式樹(shù)，使其與已經(jīng)匹配成功另一個(gè)模式分支的完全前綴的后一位置處，也可以是移動(dòng)到模式樹(shù)中的另一個(gè)模式分支的后綴可以匹配成功文本的前綴的后一位置。需要注意的是，移動(dòng)模式樹(shù)時(shí)，其移動(dòng)偏移量必須小于模式樹(shù)中最短模式分支的長(zhǎng)度min l。
3 改進(jìn)的AC-BM算法
AC-BM算法結(jié)合了AC算法和BM算法的優(yōu)點(diǎn)，允許將不同模式放在一棵模式樹(shù)上同時(shí)進(jìn)行搜索匹配。但AC-BM算法仍舊存在一些問(wèn)題。一是每一次模式串的移動(dòng)距離必須小于模式樹(shù)中模式分支的最短長(zhǎng)度 min l。二是AC-BM算法沿用了BM算法壞字符移動(dòng)和好前綴移動(dòng)，但好前綴規(guī)則預(yù)處理階段過(guò)程比較復(fù)雜，并且難以實(shí)現(xiàn)。三是每一次的匹配都對(duì)所有字符進(jìn)行一一比較，即便是有些字符在模式樹(shù)中沒(méi)有出現(xiàn)過(guò)也要進(jìn)行比較，并且模式樹(shù)的跳躍距離是根據(jù)匹配過(guò)程中單個(gè)“壞字符”決定的，但這些壞字符在下一輪匹配中卻不一定能匹配成功。四是AC-BM算法的每次匹配都是從左往右，因此可能出現(xiàn)模式串和文本字符串的相當(dāng)一部分前綴一致，但最后極少數(shù)后綴不同時(shí)還是需要進(jìn)行很多次字符比較的浪費(fèi)。
基于以上缺點(diǎn)，并結(jié)合AC-BM算法自身特點(diǎn)，主要考慮從加大算法跳躍距離和減少每輪匹配字符比較次數(shù)兩方面對(duì)其進(jìn)行改進(jìn)。
3.1 改進(jìn)算法描述
為了避免匹配過(guò)程中壞字符存在于文本串最后幾個(gè)字符，使之前的字符比較都是浪費(fèi)的情況，AC-BM改進(jìn)算法在每次匹配開(kāi)始前，首先檢驗(yàn)待匹配文本串的最后兩個(gè)字
【基于AC-BM改進(jìn)算法的入侵檢測(cè)技術(shù)研究論文】相關(guān)文章：
網(wǎng)絡(luò)信息理入侵檢測(cè)技術(shù)研究論文11-07
基于改進(jìn)多級(jí)中值濾波的加權(quán)濾波算法論文06-16
基于遺傳算法的車(chē)牌定位技術(shù)研究論文11-06
基于數(shù)據(jù)流SFCM挖掘的入侵檢測(cè)系統(tǒng)模型論文04-29
網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)研究論文07-03
基于遺傳算法的優(yōu)化設(shè)計(jì)論文11-20
碰撞檢測(cè)中的KDOPS算法論文06-15