学位论文 > 优秀研究生学位论文题录展示

时空高效的正则表达式匹配算法研究

作　者: 张洁坤
导　师: 张大方
学　校: 湖南大学
专　业: 计算机科学与技术
关键词: 深度数据包检测正则表达式匹配迁移边融合自动机扩展有限自动机智能有限自动机
分类号: TP393.08
类　型: 硕士论文
年　份: 2010年
下　载: 178次
引　用: 2次
阅　读: 论文下载

内容摘要

网络入侵检测与防御系统(Network Intrusion Detection and Prevention Systems, NIDS/NIPS)是网络安全防御的重要手段,即通过实时监测网络流量,检查每个数据包的头部信息和有效载荷(即数据包内容),识别和阻断网络可疑行为。NIDS/NIPS的核心是深度数据包检测(Deep Packet Inspection, DPI),即采用特征匹配算法,将每个数据包内容与一组预定义的特征进行匹配。DPI技术不仅应用于NIDS/NIPS,而且还应用于应用层数据包分类、P2P流量识别、基于内容的流量管理等。由于正则表达式具有更强的表达能力和灵活性,特征匹配已采用正则表达式匹配算法替代字符串匹配算法。正则表达式匹配算法采用有限自动机来表示多个正则表达式特征。有限自动机分为非确定型有限自动机(Nondeterministic Finite Automata, NFA)和确定型有限自动机(Deterministic Finite Automata, DFA)。NFA具有存储空间高效等优点,但是存在匹配速度慢等缺点；而DFA具有时间高效等优点,即匹配速度快,但是存在存储空间开销大等缺点。因此,正则表达式匹配算法的关键问题是如何设计时空高效的有限自动机。首先,本文提出了一种基于迁移边融合DFA的正则表达式匹配算法,即在状态融合DFA基础上,采用优先级将其有限自动机中的迁移边进行融合,从而减少了DFA存储空间开销。实验结果表明,与状态融合DFA和原始DFA相比,迁移边融合DFA在存储空间开销方面分别减少15%-31%和25%-42%,并确保了正则表达式的匹配效率。其次,本文提出了一种基于智能有限自动机(Smart Finite Automata, SFA)的正则表达式匹配算法,即在扩展有限自动机(Extended Finite Automata, XFA)的分支迁移边上增加额外的判断操作指令,消除XFA的回退迁移边,从而避免不必要的状态迁移。实验结果表明,与XFA相比,SFA在存储空间开销上减少了44.1%,在存储器访问次数上减少了69.1%,从而提高了正则表达式匹配的时空效率。

全文目录

摘要  5-6
Abstract  6-10
插图索引  10-12
附表索引  12-13
第1章绪论  13-18
  1.1 研究背景  13-14
  1.2 研究现状  14-16
  1.3 研究内容及组织结构  16-18
第2章正则表达式匹配算法概述  18-27
  2.1 引言及相关定义  18-19
    2.1.1 正则表达式相关定义  18-19
    2.1.2 有限自动机  19
  2.2 传统正则表达式匹配算法  19-23
    2.2.1 NFA算法  19-22
    2.2.2 DFA算法  22-23
  2.3 正则表达式匹配算法研究进展  23-25
    2.3.1 延时输入DFA  23-25
    2.3.2 治疗法DFA  25
  2.4 小结  25-27
第3章基于融合DFA的正则表达式匹配算法  27-42
  3.1 引言  27
  3.2 基于状态融合DFA的模式匹配算法  27-35
    3.2.1 SM-DFA算法介绍  27
    3.2.2 SM-DFA算法理论  27-32
    3.2.3 SM-DFA算法实现  32-35
    3.2.4 SM-DFA算法小结  35
  3.3 基于状态融合DFA算法存在问题  35-36
  3.4 基于迁移边融合DFA的正则表达式匹配算法  36-38
    3.4.1 TM-DFA算法理论基础  36
    3.4.2 TM-DFA算法  36-38
    3.4.3 TM-DFA算法实现  38
  3.5 仿真实验结果及分析  38-41
  3.6 小结  41-42
第4章扩展有限自动机及智能有限自动机算法  42-57
  4.1 引言  42
  4.2 扩展有限自动机算法  42-46
    4.2.1 XFA算法理论  42-43
    4.2.2 XFA算法实现  43-46
    4.2.3 XFA匹配算法小结  46
  4.3 扩展有限自动机算法冗余迁移边问题  46-48
  4.4 智能有限自动机算法  48-52
    4.4.1 SFA算法灵感触发  48
    4.4.2 SFA算法描述  48-50
    4.4.3 SFA算法的实现  50-52
  4.5 仿真实验结果及分析  52-56
    4.5.1 空间效率  53-55
    4.5.2 时间效率  55-56
  4.6 小结  56-57
结论  57-59
参考文献  59-63
附录A 攻读硕士学位期间发表的论文  63-64
附录B 攻读硕士学位期间参加的科研项目  64-65
致谢  65

时空高效的正则表达式匹配算法研究

内容摘要

全文目录

相似论文