入侵檢測中BM模式匹配算法的研究和改進(jìn).pdf

1、入侵檢測是一種動(dòng)態(tài)的安全防護(hù)手段，它能主動(dòng)識(shí)別入侵信息，為網(wǎng)絡(luò)系統(tǒng)提供安全保護(hù)。模式匹配技術(shù)是入侵檢測系統(tǒng)識(shí)別攻擊行為的主要技術(shù)，它能夠快速探測攻擊的存在，具有誤報(bào)率低、準(zhǔn)確性高、實(shí)用性強(qiáng)等優(yōu)點(diǎn)。在高速網(wǎng)絡(luò)環(huán)境下，入侵檢測的速度有可能跟不上數(shù)據(jù)包傳輸速率，導(dǎo)致攻擊行為的漏報(bào)，因而入侵檢測系統(tǒng)的檢測速度越來越成為其獲得實(shí)效的瓶頸之一。降低入侵檢測中常用的模式匹配算法的時(shí)間復(fù)雜度和空間復(fù)雜度是提高檢測性能的一種有效途徑。本文的研究重點(diǎn)是對(duì)入

2、侵檢測中使用的模式匹配算法進(jìn)行研究和改進(jìn)。 本文首先對(duì)入侵檢測的現(xiàn)狀進(jìn)行了分析，重點(diǎn)研究了網(wǎng)絡(luò)入侵檢測的核心技術(shù)--模式匹配。研究從模式匹配方法的原理出發(fā)，提出了其面臨的問題。在此基礎(chǔ)上，對(duì)當(dāng)前最流行的BM算法從原理到性能進(jìn)行了詳細(xì)地分析和討論。BM算法擁有較好的匹配效率，但是它不能記錄上一次匹配結(jié)果，而且算法的預(yù)處理過程也會(huì)帶來較大的內(nèi)存占有量。本文從時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面進(jìn)行了算法的改進(jìn)研究，分別提出兩種改進(jìn)算法：B

3、MLT和BMLS。BMLT通過設(shè)定一個(gè)新的預(yù)處理函數(shù)來計(jì)算移動(dòng)量，能有效增加模式串的移動(dòng)距離。BMLS通過減少處理規(guī)則和判斷壞字符在模式串中出現(xiàn)的次數(shù)，能在對(duì)時(shí)間復(fù)雜度影響不大的前提下，減少算法的空間復(fù)雜度。 本文利用著名的開源入侵檢測系統(tǒng)Snort和實(shí)際的網(wǎng)絡(luò)環(huán)境，從匹配速度和空間占用兩方面對(duì)BMLT和BMLS算法進(jìn)行了測試分析，并與BM算法進(jìn)行了比較。相比改進(jìn)前，算法的時(shí)間復(fù)雜度最多減少了60％，空間復(fù)雜度最多減少了26％。