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

匹配時(shí)取移動(dòng)距離為：dist=max{distl(j)，dist2}。文獻證明算法需要的預處理時(shí)間為O(m+σ)，最壞運行時(shí)間為O[(n―m+1)m+σ]，即掃描部分運行時(shí)間為O[(n―m)m]。在大字母表(相對于模式長(cháng)度)情況下，BM算法非?？?，實(shí)際比較次數只有目標串長(cháng)度的20％～30％。
1．4 RK算法
Karp和Rabin在1981年提出來(lái)的RK算法利用了Hash方法和素數理論。
RK算法的思想是：首先定義一個(gè)Hash函數，用該函數計算出模式串P的Hash函數值，再計算出目標串T中所有長(cháng)度為m的子串的Hash函數值，然后用相應的Hash函數值進(jìn)行比較。當出現Hash沖突時(shí)，再進(jìn)行相應字符串的比較，當構造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中長(cháng)度為m的子串t1=T[i…i+m一1]為Hash函數值ti的方法是：
令：

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

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