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