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

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

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

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