本文關(guān)鍵詞：高性能在線模式匹配算法研究

  更多相關(guān)文章： 模式匹配 在線匹配 矩陣 指紋模型 URL最長(zhǎng)前綴匹配

【摘要】：隨著計(jì)算機(jī)和網(wǎng)絡(luò)通信技術(shù)的發(fā)展,網(wǎng)絡(luò)流量日益增大。近年來我國網(wǎng)絡(luò)帶寬以每年80%的增長(zhǎng)率迅猛增長(zhǎng),目前國際出口帶寬已達(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è)基于Bloom 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)串行模式匹配算法的并行化,本文建立了兩種并行模式匹配模型——向量模型和矩陣模型�；谙蛄磕Ｐ吞岢隽司_單模式匹配算法和近似單匹配算法;基于矩陣模型提出了精確多模式匹配算法和近似多模式匹配算法。之后在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é)果可以看出,矩陣模型更適合處理并行模式匹配問題。其次,針對(duì)百萬級(jí)規(guī)模的大模式集匹配方法內(nèi)存占用和沖突率過高的問題,本文提出了一種隨機(jī)指紋模型和基于該隨機(jī)指紋模型的WM多模式精確匹配算法(RFP-WM)。算法對(duì)每個(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)存占用大的問題,本文充分利用URL的結(jié)構(gòu)化特點(diǎn),提出了一個(gè)可擴(kuò)展多哈希URL最長(zhǎng)前綴匹配方法(SMH)。與傳統(tǒng)方式不同,該方法并不將URL整體作為哈希的鍵值,而是將其以分隔符‘/’和‘.’為間隔單位的URL字符塊作為哈希鍵值。所有鍵值按該字符塊在URL中的次序以擴(kuò)展哈希表的形式存儲(chǔ)。擴(kuò)展哈希表的桶中存儲(chǔ)URL塊和指向URL ID的指針,以此來降低誤報(bào)率,提高匹配效率。實(shí)驗(yàn)結(jié)果表明,SMH的匹配效率高于經(jīng)典的最長(zhǎng)前綴匹配算法NCE、CT和BH,同時(shí)在內(nèi)存消耗和可擴(kuò)展性方面也體現(xiàn)出非常好的性能,適合處理百萬級(jí)大規(guī)模URL模式集。
【關(guān)鍵詞】：模式匹配 在線匹配 矩陣 指紋模型 URL最長(zhǎng)前綴匹配
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP393.08
【目錄】：

• 摘要4-6
• ABSTRACT6-13
• 第1章 緒論13-38
• 1.1 課題背景及研究的目的和意義13-14
• 1.2 模式匹配概述14-15
• 1.3 研究現(xiàn)狀分析15-35
• 1.3.1 精確模式匹配算法16-26
• 1.3.2 近似模式匹配算法26-29
• 1.3.3 并行模式匹配算法29-31
• 1.3.4 基于硬件的模式匹配方法31-34
• 1.3.5 網(wǎng)絡(luò)內(nèi)容安全中模式匹配存在的關(guān)鍵問題34-35
• 1.4 本文的研究?jī)?nèi)容及組織結(jié)構(gòu)35-38
• 1.4.1 本文研究?jī)?nèi)容35-36
• 1.4.2 本文章節(jié)安排36-38
• 第2章 基于擴(kuò)展BLOOM FILTER的并行模式匹配方法38-58
• 2.1 引言38-39
• 2.2 BLOOM FILTER結(jié)構(gòu)39-41
• 2.3 擴(kuò)展BLOOM FILTER (EBF)41-44
• 2.4 并行擴(kuò)展BLOOM FILTER(PEBF)44-47
• 2.5 PEBF在GPU上的實(shí)現(xiàn)(G-PEBF)47-49
• 2.6 G-PEBF算法分析49-52
• 2.7 實(shí)驗(yàn)結(jié)果及分析52-56
• 2.8 本章小結(jié)56-58
• 第3章 基于矩陣模型的并行模式匹配方法58-73
• 3.1 引言58
• 3.2 基于向量模型的單模式匹配方法58-60
• 3.3 基于矩陣模型的多模式匹配方法60-63
• 3.4 基于矩陣模型的匹配算法在GPU上的實(shí)現(xiàn)63-67
• 3.4.1 MBMPA在GPU上的實(shí)現(xiàn)(G-MBMPA)64-67
• 3.4.2 MBMPE在GPU上的實(shí)現(xiàn)(G-MBMPE)67
• 3.5 實(shí)驗(yàn)結(jié)果及分析67-71
• 3.5.1 G-MBMPA算法的性能測(cè)試68
• 3.5.2 G-MBMPE算法的性能測(cè)試68-71
• 3.7 本章小結(jié)71-73
• 第4章 基于隨機(jī)指紋模型的模式匹配方法73-85
• 4.1 引言73-74
• 4.2 隨機(jī)指紋模型74-75
• 4.3 隨機(jī)指紋單模式匹配算法75
• 4.4 隨機(jī)指紋多模式匹配算法75-77
• 4.5 隨機(jī)指紋WM算法77-80
• 4.6 實(shí)驗(yàn)結(jié)果及分析80-84
• 4.7 本章小結(jié)84-85
• 第5章 大模式集URL匹配方法85-102
• 5.1 引言85-86
• 5.2 URL特征統(tǒng)計(jì)與分析86-89
• 5.2.1 URL長(zhǎng)度分布統(tǒng)計(jì)86-87
• 5.2.2 URL子串?dāng)?shù)分布統(tǒng)計(jì)87-88
• 5.2.3 URL子串長(zhǎng)度分布統(tǒng)計(jì)88
• 5.2.4 URL子串出現(xiàn)頻率分布統(tǒng)計(jì)88
• 5.2.5 統(tǒng)計(jì)分析小結(jié)88-89
• 5.3 擴(kuò)展多哈希URL匹配方法89-93
• 5.3.1 分解URL89-91
• 5.3.2 擴(kuò)展多哈希匹配表91
• 5.3.3 URL匹配91-93
• 5.3.4 快速更新93
• 5.4 SMH算法分析93-95
• 5.5 實(shí)驗(yàn)結(jié)果及分析95-101
• 5.5.1 實(shí)驗(yàn)建立95-96
• 5.5.2 哈希算法的選取96-98
• 5.5.3 性能評(píng)價(jià)98-101
• 5.6 本章小結(jié)101-102
• 結(jié)論102-104
• 參考文獻(xiàn)104-117
• 攻讀博士學(xué)位期間發(fā)表的論文及其它成果117-119
• 致謝119-121
• 個(gè)人簡(jiǎn)歷121

，

本文編號(hào)：805809