面向网络流的正则表达式匹配改进算法

吴君钦，王 凯

(江西理工大学 信息工程学院，江西 赣州 341000)

在网络安全监控中，深度报文检测技术是一种主要的手段，它通过字符串匹配算法把网络中捕获到的数据流与特定的字符串进行匹配。这里所说的特定字符串是指在分析数据报文协议的基础上提取的特征字符，通过这种方式可以识别并阻断某些数据流，实现有效的网络安全防范。

在深度报文检测技术上，经典的字符串匹配算法有单模式匹配的KMP和BM算法,改进的多模式匹配的AC算法、CM算法、WANG方法和 Wu-Manber算法，然而这些算法都采用字符串匹配为基础。随着网络的不断发展，应用软件特征字符识别的复杂度越来越大，采用字符串匹配已难以匹配识别，因此这些算法的局限性也凸显出来。基于正则表达式的多模式匹配具备了优越的表达匹配能力和灵活性，相比传统的字符串匹配更加精确高效。

基于正则表达式的多模式匹配是把正则表达式转变为自动机，自动机分为两种：非确定有限自动机(NFA)和确定有限自动机(DFA)。NFA的优点是占用内存和系统资源少，但是需要对每个字符进行遍历，处理状态集里的所有状态，很耗费时间。如 good(day|night|evening)：若要搜 goodday，NFA需要把goodday、goodnight、goodevening全部遍历一次才能完成搜索。相比之下，DFA搜索一个字符只需要访问一个状态,但是若把所有的正则表达式都转变为DFA将会占用非常大的系统内存资源，目前的硬件条件还无法满足这一点。

结合NFA和DFA各自的优缺点，本文提出了一种猜测-分组-检验的匹配算法。……