模式匹配算法在入侵檢測(cè)中的應(yīng)用

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

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

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

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

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