模式匹配算法在入侵檢測中的應用

匹配時取移動距離為：dist=max{distl(j)，dist2}。文獻證明算法需要的預處理時間為O(m+σ)，最壞運行時間為O[(n―m+1)m+σ]，即掃描部分運行時間為O[(n―m)m]。在大字母表(相對于模式長度)情況下，BM算法非常快，實際比較次數只有目標串長度的20％～30％。
1．4 RK算法
Karp和Rabin在1981年提出來的RK算法利用了Hash方法和素數理論。
RK算法的思想是：首先定義一個Hash函數，用該函數計算出模式串P的Hash函數值，再計算出目標串T中所有長度為m的子串的Hash函數值，然后用相應的Hash函數值進行比較。當出現Hash沖突時，再進行相應字符串的比較，當構造Hash函數的素數選擇得合理，Hash沖突出現的概率就可以做到很小。
Hash函數的構造及相應Hash值的計算如下：

設c∈∑，構造Hash函數：
h(asc(c))=asc(c)mod q
式中：q∈[1…n2m]且為素數；asc(c)為任意字符c的ASCII碼。
映射模式串P為Hash函數值x(0≤x≤q一1)的方法為：
令：

同理，映射目標串T中長度為m的子串t1=T[i…i+m一1]為Hash函數值ti的方法是：
令：

根據上述公式可把目標串T中每個長度為m的子串的Hash函數值計算出來。
如果Hash沖突不發生，即不再需要額外的字符匹配，RK算法的時間復雜度是O(m+n)；若考慮字符匹配，則RK算法的時間復雜度是0(mn)。在實際應用中，可設法取適當大的素數q，使得mod q仍可執行并且Hash沖突又幾乎不發生，從而使得KR算法的實際運行時間只需O(m+n)。
RK算法采用了與KMP和BF算法不同的思路，盡量減少字符之間的比較次數，從而達到提高效率的目的。
1．5 單模式匹配算法改進情況簡介
研究人員對單模式匹配算法提出了不少變形和改進算法。
在文獻中黃占友等人提出的KMP算法的改進對特殊的字符串能夠提高效率；文獻中龐善臣等人對BM算法的改進有效地減少了最壞情況下的比較次數，同時方便在二位匹配和不精確匹配中推廣；文獻中賀龍濤等人通過將好后綴與壞字符兩種情況合并進行處理對BM進行改進。采用該思想的同類改進算法還有很多，如：發表于2006年12月32卷23期《計算機工程》上渠瑜等人的對《對BM模式匹配算法的一個改進》，限于篇幅，不一一列舉。在文獻中張國平等人對BM算法的改進是通過定義一個距離函數來求出每次匹配失敗時的最大可能移動距離；文獻蔡曉妍等人對BM算法的改進則是結合了BM算法和TunedBM算法的優點，采用TunedBM的壞字符和BM的好后綴對模式進行預處理，然后根據當前嘗試中匹配失敗字符的位置信息，決定查找好后綴跳躍表還是壞字符跳躍表以期獲得更大的跳躍距離。文獻張立航等人對RK算法的改進是通過引入2次Hash運算進行的。通過兩次Hash運算使出現Hash沖突的情況大為減少。

2 多模式匹配算法
2．1 入侵檢測中采用多模式匹配的必要性
與單模式匹配算法相比，多模式匹配算法的優勢在于一趟遍歷可以對多個模式進行匹配，從而大大提高了匹配效率。對于單模式匹配算法，如果要匹配多個模式，那么有幾個模式就需要幾趟遍歷。當然多模式匹配算法也適用于單模式的情況。在入侵檢測系統中，一條入侵特征可能匹配或部分匹配很多條規則，如果采用單模式匹配，在匹配每條規則時都需要重新運行匹配算法，效率很低。然而，日益增多的網絡攻擊使得入侵檢測的規則數目仍在不斷增長，例如，Snort1．8．3的規則為1 270條，snort2．O的規則為2 300多條，到Snort 2．6．1則增加到3 600多條規則，因此，單純提高單模式匹配算法的效率，很難使入侵檢測系統滿足越來越大的網絡數據吞吐量和日益增加的攻擊。
目前比較常見的多模式匹配算法有Aho―Corasick算法、Aho―COrasick―Boyer-Moore算法、Manber―Wu算法、Set一Wise Boyel-Moore一Hospool算法等。下面介紹其中2種經典的多模式匹配算法。
2．2 AC算法
AC算法1975年產生于貝爾實驗室，最早用于圖書館的書目查詢程序中。該算法基于有限狀態自動機(FSA)，在進行匹配之前先對模式串集合SP進行預處理，形成模式樹(樹形FSA)，然后只需對目標串T掃描一次就可以找出所有與其匹配的模式串P。模式樹K的構成如下：
K的每一條邊e上都用1個字符作為標簽；
與同一節點相連的邊的標簽均不同；
每1個模式p∈SP都存在1個節點v，使得L(v)=p，其中L(v)表示從根節點到口所經過的所有邊上的標簽的拼接；
每一個葉子節點v，都存在一個模式p∈SP使得以L(v’)=p。
例如：對于模式集SP={he，she，his，hers}模式樹如圖3所示，其中圓圈表示節點，雙圈是根節點，邊上的字符就是該邊的標簽，填充點圈的標簽就是各個模式。