IDS中串匹配臭算法并行优化研究

发布时间：2017-05-15 17:17

  本文关键词：IDS中串匹配算法并行优化研究，由笔耕文化传播整理发布。

【摘要】：随着网络技术的迅速发展,日益严重的网络安全问题已引起了人们的高度重视,对网络内容的检测已成为网络安全体系中的重要组成部分。作为网络安全检查的核心技术,字符串匹配算法在处理海量数据和各种应用需求中面临巨大的挑战。由于经典的串行串匹配算法在入侵检测系统中性能提升空间已经很小,面对复杂的网络环境,考虑将串行算法并行化成为解决这一问题的有效途径。随着多核技术的兴起和发展,基于多核的并行算法成为了研究的热点。本文基于对多核处理器平台及串匹配算法的相关研究,开展了多核平台下串匹配算法的并行化改进、实现和优化。(1)对现有的单模式精确串匹配算法进行实验分析。本文对于不同长度的模式串,分别在大小为32和64的字符集上进行了实验,得出了在一般情况下性能最好的算法。(2)通过对现有串匹配算法的分析,本文在实际性能较优的Horspool算法基础上提出了一种改进的Horspool算法,该改进的算法增大了窗口平均移动距离,提高了匹配效率。(3)基于双核和四核处理器平台,采用数据分解的方式对改进的Horspool算法、Shift-Or算法进行了并行化设计与实现,并利用多线程开发工具OpenMP实现了该并行算法。(4)借助目前流行的VTune高性能分析工具对并行化后的代码进行了性能分析,然后针对并行算法的并行度、负载均衡以及高速缓存命中率等问题进行了优化,再将它们应用到具体的串匹配实验中,通过实验数据分析了两种并行算法在双核和四核处理器平台上获得的匹配速度以及加速比等方面的性能。本文所提出的在多核处理器平台上的并行方法,还可用于其它串匹配算法以改进其性能。
【关键词】：串匹配 多核处理器 OpenMP 并行算法
【学位授予单位】：西安建筑科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.08
【目录】：

• 摘要3-4
• Abstract4-8
• 1 绪论8-14
• 1.1 研究背景8-9
• 1.2 研究意义9
• 1.3 国内外研究现状9-11
• 1.4 论文的研究内容11-12
• 1.5 论文的组织安排12-14
• 2 相关知识及相关研究14-24
• 2.1 入侵检测系统概述14-15
• 2.2 多核并行技术概述15-17
• 2.2.1 多核架构特点15
• 2.2.2 多核并行分类15-16
• 2.2.3 多核多线程技术16-17
• 2.3 OpenMP简介17-19
• 2.3.1 OpenMP并行编程模型17-18
• 2.3.2 OpenMP语法简要介绍18-19
• 2.4 多核并行算法性能评价准则19-20
• 2.4.1 运行时间19
• 2.4.2 加速比和并行效率19-20
• 2.4.3 可扩展性20
• 2.5 OpenMP并行程序优化方法20-23
• 2.6 多核性能分析工具VTune简介23
• 2.7 小结23-24
• 3 单模式串匹配算法研究24-38
• 3.1 字符串匹配的基本概念24-25
• 3.2 精确串匹配算法的研究现状25-35
• 3.2.1 基于前缀扫描的经典算法[BF, KMP, shift-and/or]25-29
• 3.2.2 基于后缀扫描的经典算法[BM, Horspool, QS]29-32
• 3.2.3 基于子串扫描的算法经典[BDM, BNDM, BOM]32-34
• 3.2.4 精确串匹配算法性能总结34-35
• 3.3 现有串匹配算法的实验研究35-37
• 3.3.1 实验环境35-36
• 3.3.2 字符集大小为32时的实验数据与分析36-37
• 3.3.3 字符集大小为64时的实验数据与分析37
• 3.4 小结37-38
• 4 串匹配算法并行化设计与实现38-58
• 4.1 串行优化38-42
• 4.1.1 串行优化分析38
• 4.1.2 对Horspool算法的一个改进38-42
• 4.2 并行化分析42-43
• 4.3 并行化设计和实现43-48
• 4.3.1 并行化设计43
• 4.3.2 改进的Horspool算法的并行化实现43-45
• 4.3.3 Shift-And/Shift-or算法的并行化实现45-48
• 4.4 并行程序的性能优化48-52
• 4.4.1 基于VTune的程序性能分析48-49
• 4.4.2 基于编译器之外的程序优化49-52
• 4.5 实验结果分析52-56
• 4.5.1 实验环境52-54
• 4.5.2 实验结果分析54-56
• 4.6 小结56-58
• 5 总结与展望58-60
• 5.1 总结58
• 5.2 展望58-60
• 参考文献60-64
• 附录 研究生期间发表论文情况64-66
• 致谢66

【参考文献】

中国期刊全文数据库 前5条

1 周挺辉;严正;唐聪;李乃湖;景雷;李慧杰;;基于多核处理器技术的暂态稳定并行算法[J];电力系统自动化;2013年08期

2 眭俊华;刘慧娜;王建鑫;秦庆旺;;多核多线程技术综述[J];计算机应用;2013年S1期

3 贺龙涛,方滨兴,余翔湛;一种时间复杂度最优的精确串匹配算法[J];软件学报;2005年05期

4 刘萍;刘燕兵;郭莉;方滨兴;;串匹配算法中模式串与文本之间关系的研究[J];软件学报;2010年07期

5 张国平;徐汶东;;字符串模式匹配算法的改进[J];计算机工程与设计;2007年20期

中国硕士学位论文全文数据库 前3条

1 徐金棒;基于多核多线程的FFT算法和堆排序算法的并行优化和实现[D];郑州大学;2011年

2 莫德敏;对串匹配技术中的Wu-Manber算法的研究[D];太原科技大学;2008年

3 范洪博;高性能精确单模式串匹配算法研究[D];哈尔滨工程大学;2009年

  本文关键词：IDS中串匹配算法并行优化研究，由笔耕文化传播整理发布。

，

本文编号：368387