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

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

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

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

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