高性能在線模式匹配算法研究.pdf

1、隨著計算機和網(wǎng)絡(luò)通信技術(shù)的發(fā)展，網(wǎng)絡(luò)流量日益增大。近年來我國網(wǎng)絡(luò)帶寬以每年80％的增長率迅猛增長，目前國際出口帶寬已達到3688Gbps。與此同時，網(wǎng)絡(luò)攻擊也越發(fā)呈現(xiàn)多樣性和復(fù)雜性，對網(wǎng)絡(luò)信息內(nèi)容安全提出了嚴峻的挑戰(zhàn)。目前迫切需要對大流量網(wǎng)絡(luò)環(huán)境下信息內(nèi)容進行實時監(jiān)測，高性能、低內(nèi)存占用的模式匹配技術(shù)是其中亟待突破的關(guān)鍵技術(shù)之一。
　　首先，為了進一步提高串行模式匹配算法的性能，本文借助于GPU的并行處理能力，提出了一個基于Blo

2、om Filter實現(xiàn)的精確并行多模式匹配算法(PEBF)。根據(jù)模式長度將模式集劃分成N個子集，為每個子集建立一個擴展Bloom Filter；并建立N個線程并行處理。在GPU上的實驗結(jié)果表明，在最差的情況下，G-PEBF也可以達到10倍的加速比。
　　然后，為了實現(xiàn)串行模式匹配算法的并行化，本文建立了兩種并行模式匹配模型——向量模型和矩陣模型?；谙蛄磕Ｐ吞岢隽司_單模式匹配算法和近似單匹配算法；基于矩陣模型提出了精確多模式匹配

3、算法和近似多模式匹配算法。之后在GPU上對基于矩陣的多模式匹配算法實現(xiàn)并行化，得到G-MBMPE和G-MBMPA。實驗結(jié)果表明，G-MBMPE和G-MBMPA算法的效率分別是實驗中各自對比算法效率的1.5倍左右。從實驗結(jié)果可以看出，矩陣模型更適合處理并行模式匹配問題。
　　其次，針對百萬級規(guī)模的大模式集匹配方法內(nèi)存占用和沖突率過高的問題，本文提出了一種隨機指紋模型和基于該隨機指紋模型的WM多模式精確匹配算法(RFP-WM)。算法對

4、每個模式串都計算出一個唯一指紋，可以有效降低誤報率。實驗結(jié)果表明，與WM算法相比，RFP-WM算法極大地降低了哈希沖突率，提高了命中率。在本文的5組實驗數(shù)據(jù)集上，算法效率提高約48%-65%。
　　最后，針對網(wǎng)絡(luò)信息監(jiān)測中以海量URL為模式集的匹配算法效率低、內(nèi)存占用大的問題，本文充分利用URL的結(jié)構(gòu)化特點，提出了一個可擴展多哈希URL最長前綴匹配方法(SMH)。與傳統(tǒng)方式不同，該方法并不將URL整體作為哈希的鍵值，而是將其以分隔