資源描述：
《入侵檢測模式匹配算法的研究與改進 》由會員上傳分享，免費在線閱讀，更多相關內容在工程資料-天天文庫。
1、入侵檢測模式匹配算法的研究與改進 摘要:網(wǎng)絡安全已經(jīng)成為國家和官方安全的重要組成部分,入侵檢測也就變的至關重要。現(xiàn)今大多數(shù)入侵檢測系統(tǒng)還是采用的基于規(guī)則的模式匹配策略,模式匹配算法的好壞直接影響到入侵檢測系統(tǒng)的準確性和實時性。提出了一種改進的BM算法,并從改進的意義、原理和實驗分析說明了改進算法在匹配效率上的提高?！ ￡P鍵詞:模式匹配;入侵檢測;算法 1BM算法研究 1977年Boyer和Moore提出了一種全新的算法,即BM算法。它的特點在于匹配過程中,模式從左向右移動,但字符比
2、較卻從右向左進行。其基本算法思想是:(1)匹配從右至左進行。(2)若匹配失敗發(fā)生在Pi≠Ti且Ti不出現(xiàn)在模式P中,則將模式右移直到Pi位于匹配失敗位置T的右邊第一位(即Ti+1位),若Ti在P中有若干地方出現(xiàn),則選擇j=max{k
3、Pk=Ti}即通過Skip函數(shù)計算文本字符Ti失配時模式向右移動的距離,也稱壞字符啟發(fā)。(3)若模式后面k位與文本T中一致的部分有一部分在P中其他地方出現(xiàn),則可以將P向右移動,直接使這部分對齊,且要求這一部分盡可能大,Shift函數(shù)通過對已經(jīng)匹配部分的考查決定模式向
4、右移動的距離,也稱好后綴啟發(fā)?！ 嵗治? 第1次匹配: Example hereisasimpleexample 第2次匹配(壞字符啟發(fā)): Example hereisasimpleexample 第3次匹配(壞字符啟發(fā)): Example hereisasimpleexample 第4次匹配(好后綴啟發(fā)): Example hereisasimpleexample 第5次匹配(壞字符啟發(fā)): Example hereisasimpleexample BM算
5、法預處理時間復雜度為O(m+s),空間復雜度為O(s),s是與P,T相關的有限字符集長度,搜索階段時間復雜度為O(mn)。最壞情況下要進行3n次比較,最好情況下的時間復雜度為O(n/m)?！ ?改進BM匹配算法研究 2.1改進的意義 綜合分析會發(fā)現(xiàn)雖然BM算法考慮較全面,但它使用了兩個數(shù)組,預處理時間開銷較大,于是在BM算法基礎上我們對其進行了簡化,使得算法更簡單、高效,提出了一種改進的BM算法。通過實驗表明改進的模式匹配算法能減少比較次數(shù),有效地提高了匹配效率。 2.2改進的原理
6、 在BM算法匹配過程中,常出現(xiàn)模式的一部分后綴與文本匹配,而模式的前綴卻不匹配,在這種情況下,就進行了一些不必要的比較。因此在BMGJ算法中,我們在對模式串與文本字符串進行匹配時采用從模式兩端向中間位置交替的匹配順序,模式匹配先從模式最右端Pm開始進行。若Pm匹配不成功,則通過Skip函數(shù)計算出模式向右移動的距離,這與BM算法中壞字符啟發(fā)思想相同;若Pm匹配成功,則比較模式P1與文本中相應的字符。若P1匹配不成功,則考查文本中與模式中Pm下一個字符對齊的字符,若該字符不出現(xiàn)在模式中,則模式可以
7、向右移動m+1個位置,若該字符出現(xiàn)在模式中,則計算其Skip函數(shù),然后將模式向右移動相應的長度;若P1匹配成功,則按上述方法依次對Pm-1,P2,Pm-2,P3,…進行匹配,依此類推,直到匹配過程完成。實例分析: 第1次匹配: Example hereisasimpleexample 第2次匹配: Example hereisasimpleexample 第3次匹配(傳統(tǒng)BM算法匹配中,此遍比較需要從右端比較5次才可以找到一個壞字符,但對于改進后的算法,只比較兩次就可以找到一個壞字
8、符): Example hereisasimpleexample 第4次匹配: Example hereisasimpleexample 第5次匹配: Example hereisasimpleexample 在上例中,我們可以看出用傳統(tǒng)的BM算法匹配共進行了4次移動15次比較,用改進的BM算法匹配共進行了4次移動12次比較,匹配次數(shù)減少。 改進后的BM算法的預處理時間復雜度為O(m+s),空間復雜度為O(s),搜索階段時間復雜度為O(mn)。該算法在比較右端字符失配時采用B
9、M壞字符啟發(fā)的思想,在比較了左端字符失配時采用對文本中與模式最右端對齊的下一個字符進行考查的方法,使得大多數(shù)情況下具有比BM算法更大的右移長度,從而有更好的平均性能?！ ?.3改進的實驗分析 我們所做的實驗軟件環(huán)境主要是:采用的操作系統(tǒng)是MicroSoft算法,匹配效率有所提高?！ ?結語 隨著網(wǎng)絡規(guī)模的不斷擴大和入侵手段的不斷更新,對入侵檢測也提出了更高的要求。目前,BM算法還是入侵檢測系統(tǒng)中主要使用的模式匹配方法,而它本身存在的一些問題使其還是有改進的余地,本文對其進行了改進,并
