并行串匹配算法研究

发布时间：2019-07-11 16:18

【摘要】：随着网络的迅猛发展，网络安全的重要性也日益凸显，对网络内容的检测成为网络安全体系中不可或缺的一部分。海量数据的处理和层出不穷的应用需求使网络内容检测技术面临着严峻的挑战，而字符串匹配算法正是网络内容检测的核心技术，因此，提高串匹配算法的性能至关重要。而传统的以串行方式执行的串匹配算法的性能难以满足日益增长的网络需求，用并行代替串行成为解决问题的关键。随着GPU (Graphic Processing Unit?图形处理单兀）、TCAM (TernaryContent Addressable Memory，三元内容可寻址存储器）、FPGA (FieldProgrammable Gate Array*现场可编程门阵列）和Bloom filter等硬件的兴起和发展，基于硬件的并行算法成为了研究的热点。同时，由于NVIDIAGPU具有成本低和高吞吐量的特点，成为了高性能并行计算的新生力量。 本文分别介绍了基于软件和硬件实现的并行串匹配算法，深入分析了基于GPU、TCAM、FPGA和Bloomfilter等硬件的并行串匹配算法的基本理论。基于GPU的高性能并行架构，把经典的AC (Aho-Corasick)算法移植到GPU平台上进行加速，设计并实现了数据并行的PAC (Parallel Algorithm based on AC)算法。PAC算法的预处理部分在CPU上串行执行，模式匹配部分交由GPU并行处理，将数据集分块，GPU的每个线程处理一个数据块，进行模式匹配。但是，PAC算法需要进行“边界检测”，降低了算法的性能。 为了消除PAC算法在内的数据并行算法存在的“边界检测”问题，本文提出了一种新颖的并行串匹配算法PAT (Parallel Algorithm based on Trie),该算法的设计也是本文的创新点。移除AC自动机的所有失效转移和初始状态的自循环转移，得到一棵Trie树，称之为PAT自动机，为输入数据的每个字符分配一个线程，搜索PAT自动机完成模式匹配。重点研究了PAT算法的实现以及GPU实现上的优势，并提出了算法的优化策略，包括减少GPU全局存储器的内存处理、消除输出表的访问和减小状态转移表查找的延迟。 通过实验得出，在NVIDIA GPU G94上实现的PAC和PAT算法与AC算法相比，分别达到了4.75和8.43的加速比。通过GPU的加速技术，大大提高了字符串匹配算法的性能，并且PAT算法在GPU实现上获得了更优的性能。
文内图片：
图片说明： 对于串匹配问题的实现也可分为两个方面，单纯基于软件的实现和基于的实现。绝大多数的串匹配算法采用串行方式执行，称为串行的串匹配算法于算法本身的特性，如位并行算法，或者借助硬件实现，，如多核或基于 G实现，这种以并行方式执行的算法，称为并行的串匹配算法。字符串匹配问分类如图 1-1 所示，该图主要体现了精确匹配的部分。
文内图片：
图片说明： 最简单的字符串匹配算法。首先比较文本串的第一个字符与模式串的第一个字符，如果相等，继续比较文本串的第二个字符和模式串的第二个字符，否则，比较文本串的第二个字符与模式串的第一个字符是否相等，以此类推，直到得出最后的匹配结果。图 1-2 用一个例子展示了 BF 算法的匹配过程。其中文本为“ababcabcac”，模式串为“abcac”，“X”代表不匹配。
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.08

【共引文献】

相关期刊论文 前10条

1 艾鑫;田志宏;张宏莉;;深度包检测技术中多模式匹配算法研究[J];智能计算机与应用;2013年05期

2 石金龙;孙翼;;基于Libnids库的Internet网络协议还原系统研究[J];电子技术;2014年03期

3 刘鹰;;基于局部最大相似设想的串匹配算法[J];电子设计工程;2014年14期

4 蔡恒;张帅;;基于BF算法改进的字符串模式匹配算法[J];电脑编程技巧与维护;2014年22期

5 王开云;孔思淇;付云生;潘泽友;马卫东;赵强;;两种基于双向比较的最长公共子串算法[J];计算机研究与发展;2013年11期

6 杨子江;聂瑞华;;一种快速的单模式匹配算法[J];华南师范大学学报(自然科学版);2013年05期

7 侯整风;杨波;朱晓玲;;一种适合中文的多模式匹配算法[J];计算机科学;2013年11期

8 李志文;张伟;;一种面向大规模短特征集的字符串匹配技术[J];计算机工程与应用;2014年01期

9 燕红文;杨怀卿;;WM与MWM算法分析[J];农业网络信息;2013年12期

10 马占飞;杨树英;郭广丰;;一种快速的基于BM模式匹配的改进算法[J];控制与决策;2013年12期

相关会议论文 前1条

1 李天磊;马兆丰;;应用层协议识别中AC算法的改进[A];第十九届全国青年通信学术年会论文集[C];2014年

相关博士学位论文 前5条

1 李丹;基于流聚类的网络业务识别关键技术研究[D];北京邮电大学;2013年

2 刘应玲;带可变长度通配符的模式匹配算法研究[D];合肥工业大学;2014年

3 马冬;网络威胁检测与态势预测关键技术研究[D];国防科学技术大学;2013年

4 张丽果;路由器SoC系统架构的研究与设计[D];西安电子科技大学;2014年

5 杨天龙;面向网络入侵检测的串匹配算法优化[D];哈尔滨工业大学;2014年

相关硕士学位论文 前10条

1 潘冠桦;单模式字符串匹配算法效率的研究[D];太原理工大学;2013年

2 马晓文;带通配符的多序列模式挖掘研究[D];合肥工业大学;2013年

3 杨波;基于有限状态自动机的中文多模式匹配算法研究[D];合肥工业大学;2013年

4 范宇健;大流量网络下串匹配算法的优化研究[D];哈尔滨工业大学;2013年

5 胡浩南;基于入侵检测系统的单模式匹配算法的研究[D];江西理工大学;2013年

6 曹晓龙;千万模式集高效匹配算法的研究与实现[D];哈尔滨工业大学;2012年

7 刘益铭;基于网关的统计波形数据包分类研究[D];哈尔滨工业大学;2012年

8 王海强;非精确深度包检测技术研究[D];哈尔滨工业大学;2013年

9 艾鑫;众核环境下深度包检测系统的设计与优化[D];哈尔滨工业大学;2013年

10 张兴彪;海量多模式串匹配算法关键技术研究[D];哈尔滨工程大学;2013年

本文编号：2513295