資源描述：
《入侵檢測(cè)模式匹配算法的研究與改進(jìn)》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、入侵檢測(cè)模式匹配算法的研究與改進(jìn)摘要:網(wǎng)絡(luò)安全已經(jīng)成為國(guó)家和官方安全的重要組成部分,入侵檢測(cè)也就變的至關(guān)重要?，F(xiàn)今大多數(shù)入侵檢測(cè)系統(tǒng)還是采用的基于規(guī)則的模式匹配策略,模式匹配算法的好壞直接影響到入侵檢測(cè)系統(tǒng)的準(zhǔn)確性和實(shí)時(shí)性。提出了一種改進(jìn)的bm算法,并從改進(jìn)的意義、原理和實(shí)驗(yàn)分析說(shuō)明了改進(jìn)算法在匹配效率上的提高。關(guān)鍵詞:模式匹配;入侵檢測(cè);算法1bm算法研究1977年boyer和moore提出了一種全新的算法,即bm算法。它的特點(diǎn)在于匹配過(guò)程中,模式從左向右移動(dòng),但字符比較卻從右向左進(jìn)行。其基本算法思想是:(1)匹配從右至左進(jìn)行。(2)若匹配失敗發(fā)生在pi≠ti且ti
2、不出現(xiàn)在模式p中,則將模式右移直到pi位于匹配失敗位置t的右邊第一位(即ti+1位),若ti在p中有若干地方出現(xiàn),則選擇j=max{k
3、pk=ti}即通過(guò)skip函數(shù)計(jì)算文本字符ti失配時(shí)模式向右移動(dòng)的距離,也稱(chēng)壞字符啟發(fā)。(3)若模式后面k位與文本t中一致的部分有一部分在p中其他地方出現(xiàn),則可以將p向右移動(dòng),直接使這部分對(duì)齊,且要求這一部分盡可能大,shift函數(shù)通過(guò)對(duì)已經(jīng)匹配部分的考查決定模式向右移動(dòng)的距離,也稱(chēng)好后綴啟發(fā)。實(shí)例分析:第1次匹配:examplehereisasimpleexample第2次匹配(壞字符啟發(fā)):examplehereisasimple
4、example第3次匹配(壞字符啟發(fā)):examplehereisasimpleexample第4次匹配(好后綴啟發(fā)):examplehereisasimpleexample第5次匹配(壞字符啟發(fā)):examplehereisasimpleexamplebm算法預(yù)處理時(shí)間復(fù)雜度為o(m+s),空間復(fù)雜度為o(s),s是與p,t相關(guān)的有限字符集長(zhǎng)度,搜索階段時(shí)間復(fù)雜度為o(mn)。LocALhOSt最壞情況下要進(jìn)行3n次比較,最好情況下的時(shí)間復(fù)雜度為o(n/m)。2改進(jìn)bm匹配算法研究2.1改進(jìn)的意義綜合分析會(huì)發(fā)現(xiàn)雖然bm算法考慮較全面,但它使用了兩個(gè)數(shù)組,預(yù)處理時(shí)間開(kāi)
5、銷(xiāo)較大,于是在bm算法基礎(chǔ)上我們對(duì)其進(jìn)行了簡(jiǎn)化,使得算法更簡(jiǎn)單、高效,提出了一種改進(jìn)的bm算法。通過(guò)實(shí)驗(yàn)表明改進(jìn)的模式匹配算法能減少比較次數(shù),有效地提高了匹配效率。2.2改進(jìn)的原理在bm算法匹配過(guò)程中,常出現(xiàn)模式的一部分后綴與文本匹配,而模式的前綴卻不匹配,在這種情況下,就進(jìn)行了一些不必要的比較。因此在bmgj算法中,我們?cè)趯?duì)模式串與文本字符串進(jìn)行匹配時(shí)采用從模式兩端向中間位置交替的匹配順序,模式匹配先從模式最右端pm開(kāi)始進(jìn)行。若pm匹配不成功,則通過(guò)skip函數(shù)計(jì)算出模式向右移動(dòng)的距離,這與bm算法中壞字符啟發(fā)思想相同;若pm匹配成功,則比較模式p1與文本中相應(yīng)的字
6、符。若p1匹配不成功,則考查文本中與模式中pm下一個(gè)字符對(duì)齊的字符,若該字符不出現(xiàn)在模式中,則模式可以向右移動(dòng)m+1個(gè)位置,若該字符出現(xiàn)在模式中,則計(jì)算其skip函數(shù),然后將模式向右移動(dòng)相應(yīng)的長(zhǎng)度;若p1匹配成功,則按上述方法依次對(duì)pm-1,p2,pm-2,p3,…進(jìn)行匹配,依此類(lèi)推,直到匹配過(guò)程完成。實(shí)例分析:第1次匹配:examplehereisasimpleexample第2次匹配:examplehereisasimpleexample第3次匹配(傳統(tǒng)bm算法匹配中,此遍比較需要從右端比較5次才可以找到一個(gè)壞字符,但對(duì)于改進(jìn)后的算法,只比較兩次就可以找到一個(gè)壞字
7、符):examplehereisasimpleexample第4次匹配:examplehereisasimpleexample第5次匹配:examplehereisasimpleexample在上例中,我們可以看出用傳統(tǒng)的bm算法匹配共進(jìn)行了4次移動(dòng)15次比較,用改進(jìn)的bm算法匹配共進(jìn)行了4次移動(dòng)12次比較,匹配次數(shù)減少。改進(jìn)后的bm算法的預(yù)處理時(shí)間復(fù)雜度為o(m+s),空間復(fù)雜度為o(s),搜索階段時(shí)間復(fù)雜度為o(mn)。該算法在比較右端字符失配時(shí)采用bm壞字符啟發(fā)的思想,在比較了左端字符失配時(shí)采用對(duì)文本中與模式最右端對(duì)齊的下一個(gè)字符進(jìn)行考查的方法,使得大多數(shù)情況下
8、具有比bm算法更大的右移長(zhǎng)度,從而有更好的平均性能。2.3改進(jìn)的實(shí)驗(yàn)分析我們所做的實(shí)驗(yàn)軟件環(huán)境主要是:采用的操作系統(tǒng)是microsoftwindowsxpprofessional(servicepack2),使用jbuilder2006編譯工具,所用jdk為jdk1.6。為了對(duì)各算法的性能進(jìn)行比較次數(shù)和比較用時(shí)的測(cè)試,我們隨機(jī)地選取了一段純英文自然語(yǔ)t文本和模式串p,在同一臺(tái)計(jì)算機(jī)上用不同算法進(jìn)行3萬(wàn)、5萬(wàn)、10萬(wàn)次循環(huán)匹配,分別統(tǒng)計(jì)各算法循環(huán)匹配所進(jìn)行的字符比較次數(shù)和總消耗的時(shí)間。文本串:t=onedayonepigorepigscameinand
