多模式匹配算法及其在入侵檢測系統(tǒng)中的應(yīng)用研究.pdf

1、模式匹配問題是計算機科學(xué)中的一個基本問題，其研究內(nèi)容在信息檢索、模式識別等眾多領(lǐng)域均有重要價值，在拼寫檢查、語言翻譯、數(shù)據(jù)壓縮、搜索引擎、入侵檢測、內(nèi)容過濾、計算機病毒特征碼匹配以及基因序列比較等應(yīng)用中起著重要的作用。入侵檢測作為一種積極主動地安全防護技術(shù)，提供了對內(nèi)部攻擊、外部攻擊和誤操作的實時保護，在網(wǎng)絡(luò)系統(tǒng)受到危害之前攔截和響應(yīng)入侵。在網(wǎng)絡(luò)速度突飛猛進(jìn)的今天，研究高效快速的入侵檢測算法對網(wǎng)絡(luò)安全、計算機安全有著重要意義。
　

2、　 本文簡單介紹了入侵檢測系統(tǒng)(Intrusion Detection System，IDS)的基本概念、發(fā)展前景、工作原理、IDS的各種標(biāo)準(zhǔn)，并對KMP(Knuth-Morris-Pratt)、AC(Aho-Corasick)、BM(Boyer-Moore)、WM(Wu-Manber)、BOM(Backward Oracle Matching)、SBOM(Set BOM)算法進(jìn)行了分析和比較。在此基礎(chǔ)上，本文提出了一種節(jié)約時間和空間

3、的快速多模式匹配算法。算法從模式串的右端向左端匹配，利用轉(zhuǎn)移表跳轉(zhuǎn)過濾掉不必要的字符，然后進(jìn)入狀態(tài)機進(jìn)行匹配，提高了匹配速度。在構(gòu)造狀態(tài)機時，利用中國剩余定理和位圖壓縮的存儲方式壓縮狀態(tài)機，減少了狀態(tài)機的存儲空間，節(jié)約了空間。該算法采用的壓縮存儲和跳躍字符思想能夠減少內(nèi)存存儲容量和訪問次數(shù)，因而該算法容易用硬件實現(xiàn)。實驗證明，算法搜索效率有明顯的提高，具有很好的性能。
　　 針對AC算法的缺點，本文設(shè)計了一種適用于硬件實現(xiàn)的匹配