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