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

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

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

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