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

摘要

网络入侵检测与防御系统(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％,并确保了正则表达式的匹配效率。其次,本文提出了一种基于智能有限自动机(SmartFiniteAutomata,SFA)的正则表达式匹配算法,即在扩展有限自动机(Extended Finite Automata,XFA)的分支迁移边上增加额外的判断操作指令,消除XFA的回退迁移边,从而避免不必要的状态迁移。实验结果表明,与XFA相比,SFA在存储空间开销上减少了44.1％,在存储器访问次数上减少了69.1％,从而提高了正则表达式匹配的时空效率。

目录

文摘

英文文摘

插图索引

附表索引

第1章 绪 论

1.1 研究背景

1.2 研究现状

1.3 研究内容及组织结构

第2章 正则表达式匹配算法概述

2.1 引言及相关定义

2.1.1 正则表达式相关定义

2.1.2 有限自动机

2.2 传统正则表达式匹配算法

2.2.1 NFA算法

2.2.2 DFA算法

2.3 正则表达式匹配算法研究进展

2.3.1 延时输入DFA

2.3.2 治疗法DFA

2.4 小结

第3章 基于融合DFA的正则表达式匹配算法

3.1 引言

3.2 基于状态融合DFA的模式匹配算法

3.2.1 SM-DFA算法介绍

3.2.2 SM-DFA算法理论

3.2.3 SM-DFA算法实现

3.2.4 SM-DFA算法小结

3.3 基于状态融合DFA算法存在问题

3.4 基于迁移边融合DFA的正则表达式匹配算法

3.4.1 TM-DFA.算法理论基础

3.4.2 TM-DFA算法

3.4.3 TM-DFA算法实现

3.5 仿真实验结果及分析

3.6 小结

第4章 扩展有限自动机及智能有限自动机算法

4.1 引言

4.2 扩展有限自动机算法

4.2.1 XFA算法理论

4.2.2 XFA算法实现

4.2.3 XFA匹配算法小结

4.3 扩展有限自动机算法冗余迁移边问题

4.4 智能有限自动机算法

4.4.1 SFA算法灵感触发

4.4.2 SFA算法描述及性能分析

4.4.3 SFA算法的实现

4.5 仿真实验结果及性能分析

4.5.1 空间效率

4.5.2 时间效率

4.6 小结

结论

参考文献

附录A 攻读硕士学位期间发表的论文

附录B 攻读硕士学位期间参加的科研项目

致谢