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

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

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

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

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

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