一種面向DPI的內(nèi)存高效的布魯姆過(guò)濾器研究.pdf

1、在網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)中，深度包檢測(cè)(Deep Packet Inspection，DPI)是一個(gè)至關(guān)重要的組件，它影響了整個(gè)系統(tǒng)的性能。DPI不僅檢測(cè)數(shù)據(jù)包的包頭而且對(duì)數(shù)據(jù)包的內(nèi)容也進(jìn)行檢測(cè)。一項(xiàng)對(duì)開(kāi)源的網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)SNORT的分析顯示，特征檢測(cè)就消耗了系統(tǒng)30％至80％的CPU資源?？梢?jiàn)，隨著網(wǎng)絡(luò)帶寬和特征集的飛速增長(zhǎng)，實(shí)現(xiàn)高性能的實(shí)時(shí)深度包檢測(cè)是一個(gè)重要議題。 布魯姆過(guò)濾器(Bloom Filter)采用一個(gè)位數(shù)組表示數(shù)據(jù)

2、集合并能有效支持元素的哈希查找，是一種能夠簡(jiǎn)潔地表示集合并支持集合查詢的數(shù)據(jù)結(jié)構(gòu)。但是布魯姆過(guò)濾器在達(dá)到其高效簡(jiǎn)潔表示集合的同時(shí)，卻存在某元素不屬于數(shù)據(jù)集合而被指稱屬于該數(shù)據(jù)集合的可能性，即假陽(yáng)性誤判率。盡管可以在布魯姆過(guò)濾器查詢之后再增加一個(gè)分析器來(lái)降低誤判，但是這樣將帶來(lái)兩個(gè)缺陷。首先，分析器的性能可能會(huì)成為系統(tǒng)的性能瓶頸。其次，特征集的大小會(huì)對(duì)分析器的性能有著負(fù)面影響，并且分析器的內(nèi)存利用率是不高的。 本論文對(duì)布魯姆過(guò)濾器

3、進(jìn)行了深入的研究，系統(tǒng)地綜述了布魯姆過(guò)濾器查詢算法迄今為止的主要研究成果，分析了目前布魯姆過(guò)濾器查詢算法的研究現(xiàn)狀與缺陷。針對(duì)布魯姆過(guò)濾器存在的不足，提出并實(shí)現(xiàn)了一種內(nèi)存高效的值域哈希布魯姆過(guò)濾器(Value Hash Bloom Filter，VHBF)，值域哈希布魯姆過(guò)濾器采用二次哈希過(guò)濾方法減少了對(duì)內(nèi)存空間的占用，有效地降低了布魯姆過(guò)濾器的假陽(yáng)性誤判率。通過(guò)對(duì)值域哈希布魯姆過(guò)濾器進(jìn)行了理論分析與實(shí)驗(yàn)仿真，實(shí)驗(yàn)結(jié)果表明值域哈希布魯姆