本文關鍵詞：高性能在線模式匹配算法研究

  更多相關文章： 模式匹配 在線匹配 矩陣 指紋模型 URL最長前綴匹配

【摘要】：隨著計算機和網絡通信技術的發(fā)展,網絡流量日益增大。近年來我國網絡帶寬以每年80%的增長率迅猛增長,目前國際出口帶寬已達到3688Gbps。與此同時,網絡攻擊也越發(fā)呈現(xiàn)多樣性和復雜性,對網絡信息內容安全提出了嚴峻的挑戰(zhàn)。目前迫切需要對大流量網絡環(huán)境下信息內容進行實時監(jiān)測,高性能、低內存占用的模式匹配技術是其中亟待突破的關鍵技術之一。首先,為了進一步提高串行模式匹配算法的性能,本文借助于GPU的并行處理能力,提出了一個基于Bloom Filter實現(xiàn)的精確并行多模式匹配算法(PEBF)。根據(jù)模式長度將模式集劃分成N個子集,為每個子集建立一個擴展Bloom Filter;并建立N個線程并行處理。在GPU上的實驗結果表明,在最差的情況下,G-PEBF也可以達到10倍的加速比。然后,為了實現(xiàn)串行模式匹配算法的并行化,本文建立了兩種并行模式匹配模型——向量模型和矩陣模型�；谙蛄磕Ｐ吞岢隽司_單模式匹配算法和近似單匹配算法;基于矩陣模型提出了精確多模式匹配算法和近似多模式匹配算法。之后在GPU上對基于矩陣的多模式匹配算法實現(xiàn)并行化,得到G-MBMPE和G-MBMPA。實驗結果表明,G-MBMPE和G-MBMPA算法的效率分別是實驗中各自對比算法效率的1.5倍左右。從實驗結果可以看出,矩陣模型更適合處理并行模式匹配問題。其次,針對百萬級規(guī)模的大模式集匹配方法內存占用和沖突率過高的問題,本文提出了一種隨機指紋模型和基于該隨機指紋模型的WM多模式精確匹配算法(RFP-WM)。算法對每個模式串都計算出一個唯一指紋,可以有效降低誤報率。實驗結果表明,與WM算法相比,RFP-WM算法極大地降低了哈希沖突率,提高了命中率。在本文的5組實驗數(shù)據(jù)集上,算法效率提高約48%-65%。最后,針對網絡信息監(jiān)測中以海量URL為模式集的匹配算法效率低、內存占用大的問題,本文充分利用URL的結構化特點,提出了一個可擴展多哈希URL最長前綴匹配方法(SMH)。與傳統(tǒng)方式不同,該方法并不將URL整體作為哈希的鍵值,而是將其以分隔符‘/’和‘.’為間隔單位的URL字符塊作為哈希鍵值。所有鍵值按該字符塊在URL中的次序以擴展哈希表的形式存儲。擴展哈希表的桶中存儲URL塊和指向URL ID的指針,以此來降低誤報率,提高匹配效率。實驗結果表明,SMH的匹配效率高于經典的最長前綴匹配算法NCE、CT和BH,同時在內存消耗和可擴展性方面也體現(xiàn)出非常好的性能,適合處理百萬級大規(guī)模URL模式集。
【關鍵詞】：模式匹配 在線匹配 矩陣 指紋模型 URL最長前綴匹配
【學位授予單位】：哈爾濱工業(yè)大學
【學位級別】：博士
【學位授予年份】：2015
【分類號】：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 網絡內容安全中模式匹配存在的關鍵問題34-35
• 1.4 本文的研究內容及組織結構35-38
• 1.4.1 本文研究內容35-36
• 1.4.2 本文章節(jié)安排36-38
• 第2章 基于擴展BLOOM FILTER的并行模式匹配方法38-58
• 2.1 引言38-39
• 2.2 BLOOM FILTER結構39-41
• 2.3 擴展BLOOM FILTER (EBF)41-44
• 2.4 并行擴展BLOOM FILTER(PEBF)44-47
• 2.5 PEBF在GPU上的實現(xiàn)(G-PEBF)47-49
• 2.6 G-PEBF算法分析49-52
• 2.7 實驗結果及分析52-56
• 2.8 本章小結56-58
• 第3章 基于矩陣模型的并行模式匹配方法58-73
• 3.1 引言58
• 3.2 基于向量模型的單模式匹配方法58-60
• 3.3 基于矩陣模型的多模式匹配方法60-63
• 3.4 基于矩陣模型的匹配算法在GPU上的實現(xiàn)63-67
• 3.4.1 MBMPA在GPU上的實現(xiàn)(G-MBMPA)64-67
• 3.4.2 MBMPE在GPU上的實現(xiàn)(G-MBMPE)67
• 3.5 實驗結果及分析67-71
• 3.5.1 G-MBMPA算法的性能測試68
• 3.5.2 G-MBMPE算法的性能測試68-71
• 3.7 本章小結71-73
• 第4章 基于隨機指紋模型的模式匹配方法73-85
• 4.1 引言73-74
• 4.2 隨機指紋模型74-75
• 4.3 隨機指紋單模式匹配算法75
• 4.4 隨機指紋多模式匹配算法75-77
• 4.5 隨機指紋WM算法77-80
• 4.6 實驗結果及分析80-84
• 4.7 本章小結84-85
• 第5章 大模式集URL匹配方法85-102
• 5.1 引言85-86
• 5.2 URL特征統(tǒng)計與分析86-89
• 5.2.1 URL長度分布統(tǒng)計86-87
• 5.2.2 URL子串數(shù)分布統(tǒng)計87-88
• 5.2.3 URL子串長度分布統(tǒng)計88
• 5.2.4 URL子串出現(xiàn)頻率分布統(tǒng)計88
• 5.2.5 統(tǒng)計分析小結88-89
• 5.3 擴展多哈希URL匹配方法89-93
• 5.3.1 分解URL89-91
• 5.3.2 擴展多哈希匹配表91
• 5.3.3 URL匹配91-93
• 5.3.4 快速更新93
• 5.4 SMH算法分析93-95
• 5.5 實驗結果及分析95-101
• 5.5.1 實驗建立95-96
• 5.5.2 哈希算法的選取96-98
• 5.5.3 性能評價98-101
• 5.6 本章小結101-102
• 結論102-104
• 參考文獻104-117
• 攻讀博士學位期間發(fā)表的論文及其它成果117-119
• 致謝119-121
• 個人簡歷121

，

本文編號：805809