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

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

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

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