论文部分内容阅读
网络入侵检测与防御系统(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%,从而提高了正则表达式匹配的时空效率。