新聞中心

EEPW首頁 > 手機與無線通信 > 設(shè)計應(yīng)用 > 模式匹配算法在入侵檢測中的應(yīng)用

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

作者: 時間:2009-04-24 來源:網(wǎng)絡(luò) 收藏

(2)壞字符移動。P中的某個字符與T中的某個字符不相同時使用壞字符移動。右滑距離函數(shù)dist2(x)定義如下:

本文引用地址:http://m.butianyuan.cn/article/158085.htm


時取移動距離為:dist=max{distl(j),dist2}。文獻證明需要的預(yù)處理時間為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ù)值,然后用相應(yīng)的Hash函數(shù)值進行比較。當出現(xiàn)Hash沖突時,再進行相應(yīng)字符串的比較,當構(gòu)造Hash函數(shù)的素數(shù)選擇得合理,Hash沖突出現(xiàn)的概率就可以做到很小。
Hash函數(shù)的構(gòu)造及相應(yīng)Hash值的計算如下:

設(shè)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算法的時間復(fù)雜度是O(m+n);若考慮字符,則RK算法的時間復(fù)雜度是0(mn)。在實際中,可設(shè)法取適當大的素數(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的好后綴對模式進行預(yù)處理,然后根據(jù)當前嘗試中匹配失敗字符的位置信息,決定查找好后綴跳躍表還是壞字符跳躍表以期獲得更大的跳躍距離。文獻張立航等人對RK算法的改進是通過引入2次Hash運算進行的。通過兩次Hash運算使出現(xiàn)Hash沖突的情況大為減少。


2 多模式匹配算法
2.1 中采用多模式匹配的必要性
與單模式匹配算法相比,多模式匹配算法的優(yōu)勢在于一趟遍歷可以對多個模式進行匹配,從而大大提高了匹配效率。對于單模式匹配算法,如果要匹配多個模式,那么有幾個模式就需要幾趟遍歷。當然多模式匹配算法也適用于單模式的情況。在系統(tǒng)中,一條入侵特征可能匹配或部分匹配很多條規(guī)則,如果采用單模式匹配,在匹配每條規(guī)則時都需要重新運行匹配算法,效率很低。然而,日益增多的網(wǎng)絡(luò)攻擊使得的規(guī)則數(shù)目仍在不斷增長,例如,Snort1.8.3的規(guī)則為1 270條,snort2.O的規(guī)則為2 300多條,到Snort 2.6.1則增加到3 600多條規(guī)則,因此,單純提高單模式匹配算法的效率,很難使入侵檢測系統(tǒng)滿足越來越大的網(wǎng)絡(luò)數(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進行預(yù)處理,形成模式樹(樹形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é)點,邊上的字符就是該邊的標簽,填充點圈的標簽就是各個模式。



評論


相關(guān)推薦

技術(shù)專區(qū)

關(guān)閉