多模式快速匹配算法的研究與實現.pdf

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

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

3、AM功耗過大的缺點；通過TCAM的精確匹配，克服了Bloomfilter誤報的缺點，實現了精確匹配。 通過對BF—TCAM的結構和性能分析得知，由于模式集合的離散特性，使得當模式集合很大時BF—TCAM的結構過于復雜。因此本文應用字符串截短理論，對BF—TCAM進行了改進，提出了新的兩級多模式匹配結構TBF—TCAM，在性能與BF—TCAM一致的前提下，結構變得更加簡潔，更加易于實現。 本文對BF-TCAM和TBF-TC