多模式快速匹配算法的研究與實(shí)現(xiàn).pdf

1、當(dāng)前網(wǎng)絡(luò)安全形勢(shì)日益嚴(yán)峻，基于模式匹配的入侵檢測(cè)系統(tǒng)成為近年來(lái)的研究熱點(diǎn)。然而現(xiàn)有的算法中，基于軟件的算法很難滿足高速網(wǎng)絡(luò)的要求，而基于硬件的算法又存在功耗過(guò)大等缺點(diǎn)。 本文首先概述了入侵檢測(cè)系統(tǒng)和入侵檢測(cè)技術(shù)，介紹了著名的開(kāi)源入侵檢測(cè)系統(tǒng)Snort的結(jié)構(gòu)和工作原理，尤其是對(duì)其規(guī)則庫(kù)進(jìn)行了細(xì)致的介紹和分析。本文隨后介紹了CAM/TCAM和Bloom Filter。其中，CAM/TCAM具備高速精確匹配的優(yōu)點(diǎn)，但是具有功耗過(guò)大的缺

2、陷；而B(niǎo)loom filter具有占用存儲(chǔ)小、快速匹配和絕不漏報(bào)的優(yōu)點(diǎn)，但是它的匹配結(jié)果帶有一定的誤報(bào)率。 本文提出了一種兩級(jí)結(jié)構(gòu)的多模式匹配算法：BF—TCAM，將Bloom filer作為第一級(jí)的過(guò)濾性匹配，TCAM作為第二級(jí)的精確匹配。BF—TCAM通過(guò)將模式集合按照長(zhǎng)度分組，建立相應(yīng)的(BF，TCAM)配對(duì)，提高了存儲(chǔ)效率，降低了存儲(chǔ)開(kāi)銷(xiāo)；通過(guò)Bloom filter的過(guò)濾性匹配，降低了TCAM的啟動(dòng)次數(shù)，從而克服了TC

3、AM功耗過(guò)大的缺點(diǎn)；通過(guò)TCAM的精確匹配，克服了Bloomfilter誤報(bào)的缺點(diǎn)，實(shí)現(xiàn)了精確匹配。 通過(guò)對(duì)BF—TCAM的結(jié)構(gòu)和性能分析得知，由于模式集合的離散特性，使得當(dāng)模式集合很大時(shí)BF—TCAM的結(jié)構(gòu)過(guò)于復(fù)雜。因此本文應(yīng)用字符串截短理論，對(duì)BF—TCAM進(jìn)行了改進(jìn)，提出了新的兩級(jí)多模式匹配結(jié)構(gòu)TBF—TCAM，在性能與BF—TCAM一致的前提下，結(jié)構(gòu)變得更加簡(jiǎn)潔，更加易于實(shí)現(xiàn)。 本文對(duì)BF-TCAM和TBF-TC