高性能在线模式匹配算法研究

发布时间：2017-09-06 22:29

  本文关键词：高性能在线模式匹配算法研究

  更多相关文章： 模式匹配 在线匹配 矩阵 指纹模型 URL最长前缀匹配

【摘要】：随着计算机和网络通信技术的发展,网络流量日益增大。近年来我国网络带宽以每年80%的增长率迅猛增长,目前国际出口带宽已达到3688Gbps。与此同时,网络攻击也越发呈现多样性和复杂性,对网络信息内容安全提出了严峻的挑战。目前迫切需要对大流量网络环境下信息内容进行实时监测,高性能、低内存占用的模式匹配技术是其中亟待突破的关键技术之一。首先,为了进一步提高串行模式匹配算法的性能,本文借助于GPU的并行处理能力,提出了一个基于Bloom Filter实现的精确并行多模式匹配算法(PEBF)。根据模式长度将模式集划分成N个子集,为每个子集建立一个扩展Bloom Filter;并建立N个线程并行处理。在GPU上的实验结果表明,在最差的情况下,G-PEBF也可以达到10倍的加速比。然后,为了实现串行模式匹配算法的并行化,本文建立了两种并行模式匹配模型——向量模型和矩阵模型。基于向量模型提出了精确单模式匹配算法和近似单匹配算法;基于矩阵模型提出了精确多模式匹配算法和近似多模式匹配算法。之后在GPU上对基于矩阵的多模式匹配算法实现并行化,得到G-MBMPE和G-MBMPA。实验结果表明,G-MBMPE和G-MBMPA算法的效率分别是实验中各自对比算法效率的1.5倍左右。从实验结果可以看出,矩阵模型更适合处理并行模式匹配问题。其次,针对百万级规模的大模式集匹配方法内存占用和冲突率过高的问题,本文提出了一种随机指纹模型和基于该随机指纹模型的WM多模式精确匹配算法(RFP-WM)。算法对每个模式串都计算出一个唯一指纹,可以有效降低误报率。实验结果表明,与WM算法相比,RFP-WM算法极大地降低了哈希冲突率,提高了命中率。在本文的5组实验数据集上,算法效率提高约48%-65%。最后,针对网络信息监测中以海量URL为模式集的匹配算法效率低、内存占用大的问题,本文充分利用URL的结构化特点,提出了一个可扩展多哈希URL最长前缀匹配方法(SMH)。与传统方式不同,该方法并不将URL整体作为哈希的键值,而是将其以分隔符‘/’和‘.’为间隔单位的URL字符块作为哈希键值。所有键值按该字符块在URL中的次序以扩展哈希表的形式存储。扩展哈希表的桶中存储URL块和指向URL ID的指针,以此来降低误报率,提高匹配效率。实验结果表明,SMH的匹配效率高于经典的最长前缀匹配算法NCE、CT和BH,同时在内存消耗和可扩展性方面也体现出非常好的性能,适合处理百万级大规模URL模式集。
【关键词】：模式匹配 在线匹配 矩阵 指纹模型 URL最长前缀匹配
【学位授予单位】：哈尔滨工业大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP393.08
【目录】：

• 摘要4-6
• ABSTRACT6-13
• 第1章 绪论13-38
• 1.1 课题背景及研究的目的和意义13-14
• 1.2 模式匹配概述14-15
• 1.3 研究现状分析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 本文章节安排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上的实现(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上的实现63-67
• 3.4.1 MBMPA在GPU上的实现(G-MBMPA)64-67
• 3.4.2 MBMPE在GPU上的实现(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特征统计与分析86-89
• 5.2.1 URL长度分布统计86-87
• 5.2.2 URL子串数分布统计87-88
• 5.2.3 URL子串长度分布统计88
• 5.2.4 URL子串出现频率分布统计88
• 5.2.5 统计分析小结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
• 攻读博士学位期间发表的论文及其它成果117-119
• 致谢119-121
• 个人简历121

，

本文编号：805809