基于多步投机的正则表达式匹配算法的研究

论文摘要

网络防御系统（Intrusion Detection and Prevention Systems，IPS）是维护网络安全的有效方式。IPS的核心是深度数据包检测（Deep Packet Inspection，DPI）。现在网络在以极快的速度发展。IPS的性能要跟上线速需要借助多核或者硬件技术。由于正则表达式的表达能力更强更灵活，特征规则多用正则表达式匹配算法实现匹配。正则表达式匹配算法用有限自动机来完成。有限自动机分为确定有限自动机（Deterministic Finite Automata，DFA）和非确定有限自动机（NondeteministicFinite Automata，NFA）。DFA较NFA匹配速率更快，更常用。但是DFA的处理速率还是难以满足线速处理的要求，特别是DFA每次只能匹配一个字符产生延时成为IPS的性能瓶颈。因此，研究基于DFA的高效正则表达式匹配算法具有重要意义。接着，本文介绍了几种基于硬件的正则表达式匹配算法，如基于多核技术的投机正则表达式匹配算法（Speculative Parallel Pattern Matching, SPPM）等，并分析了它们的理论依据及算法关键，还指明了各自的优点及不足。针对上述算法的不足之处，通过分析和实验验证Snort规则集特征，本文在正则表达式匹配算法中运用到“投机”的概念，辅以多核技术，将输入字符串分为多段并行匹配，如果投机失败会在后期进行纠正。围绕提高投机成功率这个算法关键问题，本文提出了基于多步投机的正则表达式匹配算法（Regular ExpressionMatching with Muti-step Speculation, MSPPM），有效提高投机成功率，缩短了并行匹配外对DFA的访问次数，减少延时。通过仿真比较实验可见，MSPPM的并行迭代次数和访问DFA的次数相对SPPM减少约15%，从而进一步缩短匹配时由访问DFA产生的内存延时。时间性能方面，MSPPM相对传统DFA算法的加速率平均提高约15%，算法匹配速率更高。所以，MSPPM算法是一种低延时高效的基于多核技术的正则表达式匹配算法，可达到提高匹配效率和系统吞吐量的目的，可使IPS更好的适应网络的发展。

论文目录

• 摘要
• Abstract
• 目录
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 研究背景及意义
• 1.2 研究内容
• 1.3 论文结构
• 第2章 相关理论及研究综述
• 2.1 引言
• 2.2 正则表达式及其相关定义
• 2.3 传统正则表达式算法
• 2.3.1 自动有限机
• 2.3.2 NFA 算法
• 2.3.3 DFA 算法
• 2.4 正则表达式匹配算法发展介绍
• 2.4.1 多模式匹配算法
• 2.4.2 DFA 改进算法
• 2.4.3 基于硬件的快速正则表达式匹配算法
• 2.5 小结
• 第3章 基于多步投机的正则表达式匹配算法
• 3.1 引言
• 3.2 投机算法理论
• 3.2.1 投机及投机算法简介
• 3.2.2 传统 DFA 算法的局限性
• 3.2.3 投机 DFA 匹配算法
• 3.2.4 投机算法理论
• 3.3 已有投机正则表达式匹配算法存在的问题
• 3.4 基于多步投机的正则表达式匹配算法思想
• 3.5 基于多步投机的匹配算法原理
• 3.5.1 活跃状态
• 3.5.2 规则特征
• 3.5.3 选择投机
• 3.6 MSPPM 算法设计
• 3.6.1 双核 MSPPM 算法设计
• 3.6.2 单核 MSPPM 算法设计
• 3.6.3 算法复杂度分析比较
• 3.7 小结
• 第4章 性能分析与仿真实验
• 4.1 引言
• 4.2 SPPM 算法和 MSPPM 算法性能分析及比较
• 4.3 仿真实验及结果
• 4.3.1 实验环境
• 4.3.2 准备工作
• 4.3.3 双核仿真比较实验
• 4.3.4 单核仿真比较实验
• 4.4 小结
• 结论
• 参考文献
• 致谢
• 附录A 攻读硕士学位期间所发表的学术论文目录