论文部分内容阅读
随着科技的发展，网络应用层出不穷，各种攻击也日益猖獗，给网络信息安全带来了严重威胁。深度数据包检测(Deep Packet Inspection,DPI)是网络入侵检测与防御系统(Network Intrusion Detection/Prevention System,NIDS/NIPS)的核心，常用正则表达式来描述攻击规则的特征，不仅检查数据包的头部也检查数据包的有效载荷。正则表达式匹配(Regular Expression Matching,REM)是DPI的主要组成部分。传统的正则表达式匹配算法常采用非确定有限自动机(NondeterministicFinite Automaton,NFA)和确定有限自动机(DeterministicFinite Automaton,DFA)来实现。NFA存储空间需求小，但带宽需求大；而DFA带宽需求小，但存储空间大。因此构建时空高效的正则表达式匹配算法成为当前深度数据包检测的研究热点之一。为了对DFA的存储空间进行有效的压缩，本文提出一个简单新颖的基于行程累加长度压缩的正则表达式匹配算法(Run Accumulation Length Encoding DFA,RALE-DFA)。该算法引入正则表达式集的出现字符集对字母表进行压缩，并利用RALE算法对字母压缩迁移表进行进一步压缩，同时位图被用来加快匹配过程。实验结果表明，RALE-DFA算法有效的减少了DFA的存储空间开销。与原始DFA算法、CSDFA(Character Substitution DFA)算法和D2FA(DelayedInputDFA,D2FA)算法相比，RALE-DFA算法的存储空间开销分别减少了95.81%~98.56%、48.17%~73.34%和38.09%~76.15%。在某些情况下，正则表达式中包含长度限制子表达式会导致DFA状态爆炸，并使得DFA无法构建。为解决长度限制带来的问题，本文在计数自动机(CountingFA,Counting-FA)的基础上提出了跳跃计数自动机(Jump Counting FA,Jump-CFA)算法。该算法将长度限制部分与正则表达式相分离，并对长度限制部分实施跳跃和计数策略来减少DFA状态并且提高DFA匹配速度。实验结果表明，Jump-CFA算法有效的解决了长度限制问题；与传统的DFA算法和Counting-DFA算法相比，Jump-CFA算法的自动机状态数分别减少了73%~96%和5%~18%；Jump-CFA与Counting-FA相比匹配速度提高了2到10倍。