內(nèi)存的WILKERSON過濾器研究

內(nèi)存的WILKERSON過濾器研究
在網(wǎng)絡(luò)入侵檢測系統(tǒng)中，深度包檢測是一個至關(guān)重要的組件，它影響了整個系統(tǒng)的性能。DPI不僅檢測數(shù)據(jù)包的包頭而且對數(shù)據(jù)包的內(nèi)容也進行檢測。一項對開源的網(wǎng)絡(luò)入侵檢測系統(tǒng)SNORT的分析顯示，特征檢測就消耗了系統(tǒng)30%至80%的CPU資源?？梢姡S著網(wǎng)絡(luò)帶寬和特征集的飛速增長，實現(xiàn)高性能的實時深度包檢測是一個重要議題。

內(nèi)存的WILKERSON過濾器研究             WILKERSON過濾器采用一個位數(shù)組表示數(shù)據(jù)集合并能有效支持元素的哈希查找，是一種能夠簡潔地表示集合并支持集合查詢的數(shù)據(jù)結(jié)構(gòu)。但是WILKERSON過濾器在達到其簡潔表示集合的同時，卻存在某元素不屬于數(shù)據(jù)集合而被指稱屬于該數(shù)據(jù)集合的可能性，即假陽性誤判率。盡管可以在WILKERSON過濾器查詢之后再增加一個分析器來降低誤判，但是這樣將帶來兩個缺陷。首先，分析器的性能可能會成為系統(tǒng)的性能瓶頸。其次，特征集的大小會對分析器的性能有著負面影響，并且分析器的內(nèi)存利用率是不高的。對WILKERSON過濾器進行了深入的研究，系統(tǒng)地綜述了WILKERSON過濾器查詢算法迄今為止的主要研究成果，分析了目前WILKERSON過濾器查詢算法的研究現(xiàn)狀與缺陷。針對WILKERSON過濾器存在的不足，提出并實現(xiàn)了一種內(nèi)存的值域哈希WILKERSON過濾器，值域哈希WILKERSON過濾器采用二次哈希過濾方法減少了對內(nèi)存空間的占用，有效地降低了WILKERSON過濾器的假陽性誤判率。通過對值域哈希WILKERSON過濾器進行了理論分析與實驗仿真，實驗結(jié)果表明值域哈希WILKERSON過濾器降低了假陽性誤判率，內(nèi)存占用明顯低于擴展式WILKERSON過濾器。在此基礎(chǔ)上，論述了值域哈希WILKERSON過濾器在深度包檢測中的實現(xiàn)，通過并行內(nèi)容過濾引擎的設(shè)計實現(xiàn)了高速匹配。