基於AC-BM改進演算法的入侵檢測技術研究論文

　　摘要：網路的飛速發展帶來了諸多安全隱患，入侵檢測技術作為一種積極防禦手段成為了網路安全領域的研究熱點。模式匹配由於原理簡單、無需訓練、檢測效率高、擴充套件性好廣泛用於目前的入侵檢測系統。本文首先分析了模式匹配，比較了經典的模式匹配演算法，總結了其存在的問題，並在此基礎上對AC-BM模式匹配演算法進行最佳化，提出了AC-BM改進演算法，有效提高了檢測效率，降低了檢測過程中的資源消耗。

　　關鍵詞：入侵檢測模式匹配 AC-BM改進演算法檢測效率

　　隨著網路的日新月異，網路入侵行為變得越來越複雜，因此網路安全也日益受到人們廣泛關注。入侵檢測系統能夠在不影響網路正常工作的前提下，對網路資料進行監測、收集和分析，進而從中發現是否存在入侵行為 [1]。根據入侵檢測方法的不同，可以分為異常檢測技術和誤用檢測技術。誤用檢測技術存在一個已知攻擊模式特徵庫，透過網路資料與庫中攻擊模式進行匹配來判斷是否存在入侵行為，其檢測的誤報率較低。誤用檢測中使用的檢測技術主要有模式匹配、專家系統、狀態轉移等，而模式匹配由於原理簡單、可擴充套件性好等特點被廣泛應用[2]。網路資料包的高速傳輸使得模式匹配演算法應用於入侵檢測領域面臨了諸多問題，模式匹配的效率將直接影響入侵檢測的效能。

　　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]。

　　網路入侵型別日益複雜，為了提高匹配速度期望可以實現每次可以同時對多個模式進行匹配，這種方法稱為多模式匹配方法。也就是說，文字字串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改進演算法在每次匹配開始前，首先檢驗待匹配文字串的最後兩個字