柔性多模正则匹配引擎-InfoQ

导读：正则表达式，每个计算机从业人员都熟知的技术，你真的懂吗？一个老掉牙的、不时尚的技术如何在"国内首款分布式流式关联分析引擎 sabre"中翻新？你肯定感兴趣！

01 背景

正则表达式是对字符串操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个"规则字符串"，这个"规则字符串"用来表达对字符串的一种过滤逻辑。正则表达式是一种文本模式，该模式描述在搜索文本时要匹配的一个或多个字符串。

用来深度包检测的正则表达式匹配算法是网络安全监测引擎的核心技术，但当前的正则表达式匹配引擎，在同时应对"单模正则表达式"、"数据适中 ( 一百条左右 ) 多模正则表达式"和"海量级 ( 百万条以上 ) 多模正则表达式"时，或者匹配性能较低，或者容易出现内存溢出，均没有实现一个切实有效的解决方案。

网络技术不断发展，网络流量不断增长，网络恶意行为的种类也层出不穷，网络安全成为重要的、不能回避的关键问题。能够同时处理不同规模正则表达式集合，且执行时间较短的深度包检测算法是网络安全规则引擎的核心技术。现有技术或者匹配性能不高，或者容易发生内存溢出，均不能满足实际应用需求。

02 创新

2.1 预处理

A）头部预处理，用于判定是否需要在头部增加"前缀.*"。

正则匹配模式包含两种：搜索和匹配。"搜索"表示字符串是否包含符合正则表达式的子串，"匹配"表示整个字符串是否符合正则表达式。

如果正则匹配为"搜索"模式，并且正则第一个字符不是"^" ( 字符^用于限定开头 ),则需要为此正则表达式增加"前缀.*"。例如：搜索模式的正则表达式"abc"，在头部增加"前缀.*“得到的正则表达式为”.*abc"。

B）大小写适配，用于处理"正则匹配是否忽略大小写"需求。

如果正则匹配忽略大小写，则需要将"正则表达式"和"待匹配字符串"都预先转换为小写"。如果正则匹配不能忽略大小写，则正则表达式保持不变。例如：忽略大小写的正则表达式"^aBcD"，处理之后结果为"^abcd"。

2.2 正则表达式 NFA 的高效构造方法

概述：

现有的正则表达式 NFA ( 非确定有穷自动机，Non-deterministic finite automaton ) 构造方法，通常分两个步骤，首先，借助"堆栈 ( Stack ) "构造"语法树 ( SyntaxTree ) "，然后，将语法树转换为 NFA。但是，堆栈的大小不受控制，可能会出现内存溢出问题，导致程序挂掉。同时，构造语法树也需要一定的消耗 CPU。

提出一种高效的正则表达式 NFA 构造方法，用以解决构造时间较慢，及消耗内存不可控的问题。采用遍历正则表达式直接构造 NFA 的方法，略过语法树步骤，提升构造速度，降低内存使用，加快了正则表达式编译效率。

详细步骤：

遍历正则表达式，同步构造 NFA，无需创建"语法树 ( SyntaxTree ) "。

创建"当前自动机为 nowNfa"。
遍历正则表达式，根据"当前字符 nowChar"所属的字符类型 ( 字符转换、量词、或、小括号 )，分别执行对应操作。

① 字符转换

如果"当前字符 nowChar"为"转义字符"，则解析"转义字符"、“16 进制”、“8 进制"得到"结果字符集 resultCharSet”。

如果"当前字符 nowChar"为"非元字符"，则解析为只包含"非元字符"的"结果字符集 resultCharSet"。

如果"当前字符 nowChar"为"任意字符."，则解析为包含"所有字符"的"结果字符集 resultCharSet"。

如果"当前字符 nowChar"为"区间值[]"，则解析为包含"所有区间值"的"结果字符集 resultCharSet"。

默认情况，解析为只包含"一个字符"的"结果字符集 resultCharSet"。

如果"下一个字符 nextChar"为"量词"，则将当前结果转化为"下一个自动机 nextNfa"。否则，为"当前自动机为 nowNfa"根据"结果字符集 resultCharSet"添加跳转操作。

② 量词

如果“当前字符 nowChar”为“*”，则解析值为“{0，+∞}”的“量词区间 QuantifierInterval”。

如果“当前字符 nowChar”为“？”，则解析值为“{0，1}”的“量词区间 QuantifierInterval”。

如果“当前字符 nowChar”为“+”，则解析值为“{1，+∞}”的“量词区间 QuantifierInterval”。

如果“当前字符 nowChar”为“{”，则解析值为“{m，n}”的“量词区间 QuantifierInterval”。

首先针对“下一个自动机 nextNfa”执行量词操作 repeat，然后针对“当前自动机为 nowNfa”和“下一个自动机 nextNfa”执行连接操作 connact。

③ 或

如果“当前字符 nowChar”为“|”，则针对“后续的正则表达式子串”构造“单独的自动机 newNfa”。

针对“当前自动机为 nowNfa”和“单独的自动机 newNfa”执行或操作 or。

④ 小括号

如果“当前字符 nowChar”为“（”，则针对 “处于小括号内正则表达式子串”构造“单独的自动机 newNfa”。

针对“当前自动机为 nowNfa”和“单独的自动机 newNfa”执行连接操作 connact。

流程图：

2.3 具有较少空跳转特性的正则 NFA 引擎构造算法

概述：

传统的 Thompson 正则 NFA ( 非确定有穷自动机，Non-deterministic finite automaton ) 引擎构造法，但具有“大量的空跳转”和“较多的状态数”。“空跳转”使得 NFA 转化为 DFA ( 确定有穷自动机，Deterministic finite automaton ) 执行时间较长。同时，“空跳转”及“较多的状态数”使得 NFA 模式正则表达式匹配速度较慢。

本发明针对正则表达式的三大基本算子 ( “连接”、“或”和“闭包” )，提出一种高效的具有较少空跳转特性的正则 NFA 引擎构造算法，能够快速地构造出“较少空跳转”和“较少状态数”的 NFA，并且，此 NFA 具有较快的匹配速度。

详细步骤：

A）连接优化，用于优化“当前自动机 nowNfa”和“下一个自动机 nextNfa”的连接操作。

如果“当前自动机 nowNfa”为空，则用“下一个自动机 nextNfa”替换“当前自动机 nowNfa”。例如：a。

如果“当前自动机 nowNfa”非空，并且“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”不存在输入边，则将“当前自动机 nowNfa 的尾部状态 nowLastNfaState”与“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”合并。例如：a*b。

如果“当前自动机 nowNfa”非空，并且“当前自动机 nowNfa 的尾部状态 nowLastNfaState”不存在输出边，则将“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”与“当前自动机 nowNfa 的尾部状态 nowLastNfaState”合并。例如：ab*。

如果“当前自动机 nowNfa”非空，并且“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”存在输入边，并且“当前自动机 nowNfa 的尾部状态 nowLastNfaState”存在输出边，则“当前自动机 nowNfa 的尾部状态 nowLastNfaState”添加到“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”的空跳转。例如：a*b*。

B）或优化，用于优化“当前自动机 nowNfa”和“下一个自动机 nextNfa”的或操作。

① 头部状态优化

如果“当前自动机 nowNfa 的头部状态 nowHeadNfaState”不存在输入边，并且“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”不存在输入边，则将“当前自动机 nowNfa 的头部状态 nowHeadNfaState”与“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”合并。例如：a|b。

如果“当前自动机 nowNfa 的头部状态 nowHeadNfaState”不存在输入边，并且“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”存在输入边，则“当前自动机 nowNfa 的头部状态 nowHeadNfaState”添加到“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”的空跳转。例如：a|b*。

如果“当前自动机 nowNfa 的头部状态 nowHeadNfaState”存在输入边，并且“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”不存在输入边，则“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”添加到“当前自动机 nowNfa 的头部状态 nowHeadNfaState”的空跳转。例如：a*|b。

如果“当前自动机 nowNfa 的头部状态 nowHeadNfaState”存在输入边，并且“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”存在输入边，并且“当前自动机 nowNfa 的头部状态 nowHeadNfaState”能够与“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”合并，则将“当前自动机 nowNfa 的头部状态 nowHeadNfaState”与“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”合并。例如：.*a|.*b。

如果“当前自动机 nowNfa 的头部状态 nowHeadNfaState”存在输入边，并且“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”存在输入边，并且“当前自动机 nowNfa 的头部状态 nowHeadNfaState”不能与“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”合并，则先为“当前自动机 nowNfa” 创建“新的头部状态 newNowHeadNfaState”，然后为“新的头部状态 newNowHeadNfaState”添加到“前自动机 nowNfa 的头部状态 nowHeadNfaState”的空跳转，然后为“新的头部状态 newNowHeadNfaState”添加到“下一个自动机 nextNfa 的头部状态 nextHeadNfaState”的空跳转。例如：a*|b*。

② 尾部状态优化

如果“当前自动机 nowNfa 的尾部状态 nowLastNfaState”不存在输出边，并且“下一个自动机 nextNfa 的尾部状态 nextLastNfaState”不存在输出边，则将“当前自动机 nowNfa 的尾部状态 nowLastNfaState”与“下一个自动机 nextNfa 的尾部状态 nextLastNfaState”合并。例如：a|b。

如果“当前自动机 nowNfa 的尾部状态 nowLastNfaState”不存在输出边，并且“下一个自动机 nextNfa 的尾部状态 nextLastNfaState”存在输出边，则“下一个自动机 nextNfa 的尾部状态 nextLastNfaState”添加到“当前自动机 nowNfa 的尾部状态 nowLastNfaState”的空跳转。例如：a|b*。

如果“当前自动机 nowNfa 的尾部状态 nowLastNfaState”存在输出边，并且“下一个自动机 nextNfa 的尾部状态 nextLastNfaState”不存在输出边，则“当前自动机 nowNfa 的尾部状态 nowLastNfaState” 添加到“下一个自动机 nextNfa 的尾部状态 nextLastNfaState” 的空跳转。例如：a*|b。

如果“当前自动机 nowNfa 的尾部状态 nowLastNfaState”存在输出边，并且“下一个自动机 nextNfa 的尾部状态 nextLastNfaState”存在输出边，并且“当前自动机 nowNfa 的尾部状态 nowLastNfaState”能够与“下一个自动机 nextNfa 的尾部状态 nextLastNfaState”合并，则将“当前自动机 nowNfa 的尾部状态 nowLastNfaState”与“下一个自动机 nextNfa 的尾部状态 nextLastNfaState”合并。例如：a.*|b.*。

如果“当前自动机 nowNfa 的尾部状态 nowLastNfaState”存在输出边，并且“下一个自动机 nextNfa 的尾部状态 nextLastNfaState”存在输出边，并且“当前自动机 nowNfa 的尾部状态 nowLastNfaState” 不能与“下一个自动机 nextNfa 的尾部状态 nextLastNfaState”合并，则先为“当前自动机 nowNfa” 创建“新的尾部状态 newNowLastNfaState”，然后为“当前自动机 nowNfa 的尾部状态 nowLastNfaState”添加到“新的头部状态 newNowHeadNfaState”的空跳转，然后为“下一个自动机 nextNfa 的尾部状态 nextLastNfaState”添加到“新的头部状态 newNowHeadNfaState”的空跳转。例如：a*|b*。

C）闭包优化，用于优化“当前自动机 nowNfa”的闭包操作。

将“当前自动机 nowNfa 的头部状态 nowHeadNfaState”与“当前自动机 nowNfa 的尾部状态 nowLastNfaState”合并。例如：(ab)*。

2.4 前后缀优化的正则 NFA 引擎构造算法

概述：

现有的正则表达式匹配引擎，先将正则表达式编译为 NFA（非确定有穷自动机，Non-deterministic finite automaton）。然后，如果内存空间和执行时间允许，再将 NFA 转换为 DFA（确定有穷自动机，Deterministic finite automaton）。最后，根据匹配模式（“子串搜索”和“全文匹配”），执行匹配任务。但是，在“子串搜索”模式下，没有针对前后缀“.* ”做特殊处理，导致 NFA 转换为 DFA 执行时间较长，并且转换得到的 DFA 状态数量较大，内存空间利用率较低。

针对“子串搜索”模式的正则表达式匹配任务，提出了一种前后缀优化的正则 NFA 引擎构造算法，用以解决“子串搜索”模式的正则表达式编译期耗时较长，及内存空间利用率较低的问题。充分优化前后缀“.*”,提升了 NFA 转换 DFA 速度，极大减少了 DFA 状态数量，增加了正则表达式匹配任务使用 DFA 的可能性。

详细步骤：

A）前缀优化，用于判定是否需要清除“子串搜索”模式的正则表达式前缀“.*”。

① 清除前缀“.*”。

如果输入到“头部 NFA 状态 headNfaState”的空跳转边为空，并且“头部 NFA 状态 headNfaState”的“输出空跳转边列表 epsilonEdgeList”非空，则继续遍历“输出空跳转边列表 epsilonEdgeList”，判断“输出空跳转 NFA 状态”是否可以清除“.*”。

如果输入到“非头部 NFA 状态 unHeadNfaState”的空跳转边有且仅有一条，并且输入到自身的“区间跳转边 gotoSelfRangeEdge”有且仅有一条，并且此区间边包含所有字符集，则首先删除此“区间跳转边 gotoSelfRangeEdge”，然后判断此“非头部 NFA 状态 unHeadNfaState”的“输出空跳转边列表 epsilonEdgeList”是否为空。如果非空，则继续遍历“输出空跳转边列表 epsilonEdgeList”，判断“输出空跳转 NFA 状态”是否可以清除“.*”。

② 合并前缀空跳转。清除前缀“.*”后，如果非头部 NFA 状态，有到头部 NFA 状态的空跳转，则需要将此非头部 NFA 状态与头部 NFA 状态合并。

B）后缀优化，用于判定是否需要清除“子串搜索”模式的正则表达式后缀“.*”。

① 清除后缀“.*”。

如果“尾部 NFA 状态 lastNfaState”的“输出非自身空跳转边列表 epsilonEdgeList”为空，并且“尾部 NFA 状态 lastNfaState”的“输出非自身跳转边 gotoUnSelfRangeEdge”非空，并且输入到自身的“区间跳转边 gotoSelfRangeEdge”有且仅有一条，并且此区间边包含所有字符集，则首先删除此“区间跳转边 gotoSelfRangeEdge”，然后判断此“尾部 NFA 状态 lastNfaState”的“输入空跳转边列表 epsilonIntoEdgeNfaStateSet”是否为空。如果非空，则继续遍历“输入空跳转边列表 epsilonIntoEdgeNfaStateSet”，判断“输入空跳转 NFA 状态”是否可以清除“.*”。

如果输入到“非尾部 NFA 状态 unLastNfaState”的“输出非自身空跳转边列表 epsilonEdgeList”为空，并且“输出非自身跳转边 gotoUnSelfRangeEdge”有且仅有一条，并且输入到自身的“区间跳转边 gotoSelfRangeEdge”有且仅有一条，并且此区间边包含所有字符集，则首先删除此“区间跳转边 gotoSelfRangeEdge”，然后判断此“非尾部 NFA 状态 unLastNfaState”的“输入空跳转边列表 epsilonIntoEdgeNfaStateSet”是否为空。如果非空，则继续遍历“输入空跳转边列表 epsilonIntoEdgeNfaStateSet”，判断“输入空跳转 NFA 状态”是否可以清除“.*”。

② 合并后缀空跳转。清除后缀“.*”后，如果非尾部 NFA 状态，有到尾部 NFA 状态的空跳转，则需要将此非尾部 NFA 状态与尾部 NFA 状态合并。

2.5 快速的 NFA 到 DFA 转换算法

概述：

现有的正则表达式匹配引擎，先将正则表达式编译为 NFA（非确定有穷自动机，Non-deterministic finite automaton）。然后，使用“子集构造法”将 NFA 转换为 DFA（确定有穷自动机，Deterministic finite automaton）。最后，采用 DFA 执行匹配任务。但如果采用了不合理的数据结构，NFA 转换为 DFA 执行时间会较长，不仅浪费了 CPU 资源，而且降低了正则表达式匹配引擎的整体性能。

针对“NFA 转换为 DFA”的“子集构造法”，采用了合理的数据结构，实现了一种快速的 NFA 到 DFA 转换算法，用以解决“NFA 到 DFA 转换”执行时间较长，消耗较多 CPU 资源的问题。采用合理的数据结构，加快了 NFA 转换 DFA 速度，节省了 CPU 资源，提升了正则表达式匹配引擎的整体性能。

详细步骤：

A）求取 NFA 状态子集，用于求取 DFA 状态跳转包含的“NFA 状态集合 gotoNfaStateSet”，以及对应的“跳转 NFA 状态编号有序列表 gotoNfaStateIdList”。

如果“NFA 状态集合 gotoNfaStateSet”只有一个 NFA 状态，则“跳转 NFA 状态编号有序列表 gotoNfaStateIdList”为此 NFA 状态的闭包 NFA 状态编号的有序列表。

如果“NFA 状态集合 gotoNfaStateSet”包含多个 NFA 状态，则“跳转 NFA 状态编号有序列表 gotoNfaStateIdList”为“NFA 状态集合 gotoNfaStateSet”中所有 NFA 状态的闭包 NFA 状态编号的有序列表。首先，创建一个“临时跳转闭包 NFA 状态编号数组 tempGotoClosureNfaStateArray”，并且此数组长度为“NFA 包含的 NFA 状态总量”。然后，在此数组基础上逐步叠加“NFA 状态的闭包 NFA 状态编号”。最后，遍历“临时跳转闭包 NFA 状态编号数组 tempGotoClosureNfaStateArray”中的有效值得到“跳转 NFA 状态编号有序列表 gotoNfaStateIdList”。较传统的 Map 数据结构相比，此方法具有“无须计算哈希值”和“无须比较多次”的优点。

B）创建 DFA 状态，用于判定当前是否已存在 DFA 状态等价于“跳转 NFA 状态编号有序列表 gotoNfaStateIdList”，如果不存在，则需要创建新的 DFA 状态。

采用“Radix 树”检索“跳转 NFA 状态编号有序列表 gotoNfaStateIdList”。如果存在，则说明已有等价的 DFA 状态。如果不存在，则说明当前没有与之等价的 DFA 状态，需要创建新的 DFA 状态 newDFAState，同时需要将“跳转 NFA 状态编号有序列表 gotoNfaStateIdList”和“新建的 DFA 状态 newDFAState”添加到“Radix 树”。较传统的 Map 数据结构相比，此“Radix 树”方法无须计算哈希值，直接比较 NFA 状态编号值即可，并且“Radix 树”较 Map 内存空间利用率更高，更适应于“NFA 转 DFA”过程“DFA 状态数量爆炸”的情形。

C）构造 DFA 状态跳转，用于构造各个 DFA 状态之间的跳转关系，添加跳转的开始字符为 gotoCharStart，添加跳转的结束字符为 gotoCharEnd，添加跳转的 DFA 状态为 gotoDfaState。创建“跳转边列表 gotoEdgeList”，并添加元素“ (0,255,null)”。

①“跳转边列表 gotoEdgeList”有且只有一个元素

如果开始字符 gotoCharStart 等于 0，并且结束字符 gotoCharEnd 等于“字符集最大索引 charSetMaxIndex”。首先，清空“跳转边列表 gotoEdgeList”，然后，往“跳转边列表 gotoEdgeList” 添加元素“(gotoCharStart,gotoCharEnd,gotoDfaState)”。

如果开始字符 gotoCharStart 等于 0，并且结束字符 gotoCharEnd 不等于“字符集最大索引 charSetMaxIndex”。首先，清空“跳转边列表 gotoEdgeList”，然后，往“跳转边列表 gotoEdgeList” 添加两个元素“(gotoCharStart,gotoCharEnd,gotoDfaState)”和“(gotoCharEnd+1,charSetMaxIndex,null)”。

如果开始字符 gotoCharStart 不等于 0，并且结束字符 gotoCharEnd 等于“字符集最大索引 charSetMaxIndex”。首先，清空“跳转边列表 gotoEdgeList”，然后，往“跳转边列表 gotoEdgeList” 添加两个元素“(0,gotoCharStart-1,null)”和“(gotoCharStart，gotoCharEnd,gotoDfaState)”。

如果开始字符 gotoCharStart 不等于 0，并且结束字符 gotoCharEnd 不等于“字符集最大索引 charSetMaxIndex”。首先，清空“跳转边列表 gotoEdgeList”，然后，往“跳转边列表 gotoEdgeList” 添加三个元素“(0,gotoCharStart-1,null)”、“(gotoCharStart,gotoCharEnd,gotoDfaState)”和“(gotoCharEnd+1，charSetMaxIndex,null)”。

② “跳转边列表 gotoEdgeList”有多个元素

倒数第一条跳转边为 end1GotoEdge，倒数第二条跳转边为 end2GotoEdge，倒数第二条跳转边的结束字符为 gotoCharEnd2，倒数第二条跳转边的 DFA 状态为为 nowGotoDfaState。

如果开始字符 gotoCharStart 等于“gotoCharEnd2+1”，并且跳转的 DFA 状态 gotoDfaState 与 nowGotoDfaState 相同，则 gotoCharEnd2 更新为 gotoCharEnd。

如果开始字符 gotoCharStart 等于“gotoCharEnd2+1”，并且跳转的 DFA 状态 gotoDfaState 与 nowGotoDfaState 不相同，则“跳转边列表 gotoEdgeList”在倒数第一个位置添加“(gotoCharStart,gotoCharEnd,gotoDfaState)”。

如果开始字符 gotoCharStart 不等于“gotoCharEnd2+1”，则“跳转边列表 gotoEdgeList”需要插入两条新边，即在倒数第一个位置添加“（gotoCharEnd2 + 1,gotoCharStart - 1,null)”，在最后一个位置添加“(gotoCharStart,gotoCharEnd,gotoDfaState)”。

执行完上述步骤，检测“结束字符 gotoCharEnd”是否等于“字符集最大索引 charSetMaxIndex”。如果等于，则需要将“倒数第一条跳转边 end1GotoEdge”从“跳转边列表 gotoEdgeList”中移除。如果不等于，则将“倒数第一条跳转边 end1GotoEdge”的开始字符修改为“gotoCharEnd + 1”。

上述方法最多仅需要与倒数两个元素比较，比较次数较少，执行速度较快。

2.6 高性能有限自动机空间压缩算法

概述：

正则表达式匹配引擎，需将正则表达式对应的 NFA ( 非确定有穷自动机，Non-deterministic finite automaton ) 转换为 DFA ( 确定有穷自动机，Deterministic finite automaton )，然后采用处理速度较快的 DFA 执行匹配任务。然而，DFA 较 NFA 具有极高的空间复杂度，进而影响了 DFA 在大规模复杂正则表达式情形下的完美使用。目前有限自动机状态转移采用二维矩阵存储结构，行表示有限制动机状态，列表示跳转字符。但是基于二维矩阵存储结构进行的有限自动机压缩算法，压缩比例较低，有限自动机空间利用率较低。

详细步骤：

A）NFA 空间压缩，用于构造压缩比例较高的“NFA 状态转移”存储数据结构。本步骤保持 NFA 状态数目不变，只针对 NFA 状态之间的跳转关系做优化。

传统的 NFA 二维矩阵存储结构，行表示 NFA 状态，列表示跳转字符。但是，正则表达式中的跳转字符可以分为两类：第一类是单个跳转字符，比如：ab；第二类是跳转字符区间（包含多个连续字符），比如：[a-h]。

基于上述理论，NFA 状态跳转边分“单个跳转字符”和“跳转字符区间”两种情况分别存储，其中“跳转字符区间”可以合并为一条存储记录。但是，“无效跳转字符”及“跳转字符区间”无须记录，“DFA 状态之间的跳转关系”采用链式列表存储。

然后，将上述的“单个跳转字符”和“跳转字符区间”的存储结构合并到“有序数组列表”，单个跳转字符可能对应多个目的 NFA 状态。此“有序数组列表”不仅可以缩短“NFA 到 DFA”转换时间，而且可以提高“基于 NFA 匹配技术”的执行效率。

B）优化 NFA 到 DFA 转换，用于合并 NFA 状态之间的跳转关系，进而改善“子集构造法”的性能，优化 NFA 到 DFA 转换效率。

NFA 到 DFA 转换过程中，有很大一部分时间用于查询当前跳转字符对应的“活跃 NFA 状态集”是否已经存在。但是，DFA 状态的跳转边往往是有限的，并且存在极大的重复概率。至少大部分情况下正则表达式为 BASE64 所含的 64 个常用字符，重复率近似为 64/256=75%。

预处理 DFA 状态包含的“活跃 NFA 状态集”，多个连续的跳转字符具有相同的“跳转活跃 NFA 状态集”，只需执行一次“Radix 树检索”，极大减少了“Radix 树检索次数”，进而缩小了 NFA 到 DFA 的执行时间。

C）DFA 空间压缩，用于构造压缩比例较高的“DFA 状态转移”存储数据结构。本步骤保持 DFA 状态数目不变，只针对 DFA 状态之间的跳转关系做优化。

传统的 DFA 二维矩阵存储结构，行表示 DFA 状态，列表示跳转字符。但是，DFA 的跳转字符可以分为两类：第一类是单个跳转字符跳转到目的 DFA 状态，并且这个跳转字符与相邻跳转字符目的 DFA 状态不同；第二类是跳转字符区间（包含多个连续字符）具有相同的目的 DFA 状态。

基于上述理论，DFA 状态跳转边分“单个跳转字符”和“跳转字符区间”两种情况分别存储，其中“跳转字符区间”可以合并为一条存储记录。同时，为了加快 DFA 匹配速度，“无效跳转字符”及“跳转字符区间”也须记录，“DFA 状态之间的跳转关系”采用有序数组列表存储。

流程图：

2.7 面向正则表达式的新型混合有限自动机

概述：

由于 DFA ( 确定有穷自动机，Deterministic finite automaton ) 较 NFA ( 非确定有穷自动机，Non-deterministic finite automaton ) 匹配性能较好，因此现有正则表达式匹配引擎均在满足 CPU 和内存限制的情况下，尽最大可能地将 NFA 转换为 DFA，后采用 DFA 执行匹配任务。但如果在“NFA 转换为 DFA”执行过程中超出了 CPU 和内存限制，则需要采用“基于 NFA 匹配技术”执行匹配任务。同时，现有的混合自动机，在遇到导致状态增长 ( 比如：“.*”、“.{n}” ) 的情况就结束 DFA 构造，虽然包含头部 DFA 和尾部 NFA 两部分，但其头部 DFA 具有很大不确定性，并且在利用尾部 NFA 时候不能很好的利用头部 DFA。

详细步骤：

A）生成新型混合有限自动机，用于在有限时间的前提下，构造内存空间利用率较高的一种新型混合有限自动机。

① 将正则表达式格式化（补充、转义），采用三大计算性算子（连接、并、闭包）表示。

② 将格式化的正则表达式转化为抽象语法树。

③ 采用 Thompson 算法将抽象语法树转化为 NFA。

④ 在满足执行时间和内存空间的条件下，按照“分层模式”尽最大可能的构造“半成品 DFA 自动机 UnFinished-DFA”，“半成品 UnFinished-DFA”最后一级 DFA 状态标记为“未完成 DFA 状态 UnFinishedDFAState”，其他 DFA 状态标记为“已完成 DFA 状态 FinishedDFAState”。其中，“分层模式”表示按照 DFA 状态层次构造，即先构造层次较低的 DFA 状态。

生成新型混合有限自动机执行参照附图 2

B）基于新型混合有限自动机执行匹配任务，用于利用性能较好的“半成品 DFA 自动机 UnFinished-DFA”执行正则表达式匹配任务。

① 采用“半成品 DFA 自动机 UnFinished-DFA”执行匹配任务。如果匹配失败，则返回结果 false。如果处于“未完成 DFA 状态 UnFinishedDFAState”，则采用“尾部 NFA 自动机 Tail-NFA”继续执行匹配任务。

② 采用“尾部 NFA 自动机 Tail-NFA”执行匹配任务。

如果没有跳转字符对应的“活跃 NFA 状态集合”，则表示匹配失败，需返回结果 false。

否则，先判断“活跃 NFA 状态集合”在“半成品 DFA 自动机 UnFinished-DFA”是否有等价的 DFA 状态。如果有等价的“已完成 DFA 状态 FinishedDFAState”，则复用此“已完成 DFA 状态 FinishedDFAState”（回归到“半成品 DFA 自动机 UnFinished-DFA”匹配模式）。如果没有等价的 DFA 状态，则采用“NFA 匹配模式”继续执行。

2.8 高性能超大规模正则表达式匹配算法

概述：

海量（千万级）正则表达式匹配引擎通常采用过滤方法实现，包含“过滤器”和“验证器”两大核心模块。“过滤器”采用抽取的有效指纹构建自动机实现，“验证器”采用 NFA-DFA 正则表达式引擎实现。但是，现有的“有效指纹”提取算法，均是针对“连接”操作的关键子串，没有考虑正则表达式的“或”操作，进而过滤能力较低，并且“有效指纹”长度不可控，容易发生内存溢出错误。

提出一种高性能超大规模正则表达式匹配算法，用以解决过滤性能力较低，“自动机过滤器”内存空间不可控的问题。同时考虑正则表达的“连接”操作和“或”操作，抽取更加有效“有效指纹”，减少了需进一步验证的正则表达式条数。控制“有效指纹”长度，进而构建内存可控的“自动机过滤器”，避免发生内存溢出错误。通过定序比较“有效指纹子串”的方式，提供更有效的过滤器性能。

详细步骤：

A）定长有效指纹抽取。遍历正则表达式，根据“当前操作”所属类型分别执行对应“有效指纹抽取”操作。并将最原始的“有效指纹”转化为定长“有效指纹”。

① 抽取最原始的有效指纹

如果为“连接”操作,则将两个子模块的索引连接，后面索引模块，索引值 indexValue 不变，但是索引偏移 indexOffset 需要在前面索引模块的基础上递增。例如：“abcdf”。

如果为“或”操作,则每个子串提供相同数量的有效截取串，这几个截取串会共用同一个“位置”，并且如果某个子串不存在有效截取串，则抛弃此“或”模块。将两个子模块的索引合并，索引值 indexValue 可以不同，但索引偏移 indexOffset 必须相同。也就是，一个索引偏移 indexOffset 会同时对应多个不同的索引值 indexValue。例如：“(abcd)|(efg)”。

如果为“闭包/量词”，需要进一步分类处理。形如“a{n,m}”，则等价于“a{n}”，n 大于等于 3，则只截取一个子串，aaa；n 小于 3，则和后续连接字符关联。形如“a+”，则等价于 a。

如果为“转义字符”，则保留“16 进制”、“8 进制”、“无效转义字符”，其他跳过。

如果为其他字符，则全部抛弃。

② 转换为定长有效指纹

将最原始的“有效指纹”划分为多个定长子串。例如：有效子串为 “abcdef”，定长为 3，有效指纹划分为两个子串“abc”和“def”。

正则表达式定长有效指纹抽取执行参照附图 2

C）自动机过滤器构建，利用已划分的“有效指纹子串”集合构建内存可控的“自动机过滤器”。

“有效指纹子串”即为“精确字符串”，因此可以采用“多模精确字符串匹配自动机”实现过滤器。本发明实现采用 AC（Aho-Corasick automaton）自动机。

所有“有效指纹子串”均为定长字符串，由此也限定了“自动机过滤器”的最大深度，进而控制了“自动机过滤器”内存空间。

自动机过滤器实例参照附图 3

D）有效指纹定序比较。使用“自动机过滤器”得到需要进一步验证的正则表达式集合。

使用“自动机过滤器”匹配“待匹配字符串”，得到“待验证正则表达式 filterSuccessRegex”及其“有效指纹子串索引 index”。创建存储“待验证正则表达式匹配进度的映射 filterSuccessRegexMap”,键为“待验证正则表达式 filterSuccessRegex”，值为“有效指纹子串索引 index”。

如果“待验证正则表达式匹配进度的映射 filterSuccessRegexMap”没有对应的“待验证正则表达式 filterSuccessRegex”，并且对应的“有效指纹子串索引 index”为 0，则将“待验证正则表达式 filterSuccessRegex”添加到“待验证正则表达式匹配进度的映射 filterSuccessRegexMap”，并设置其值为“0”。

如果“待验证正则表达式匹配进度的映射 filterSuccessRegexMap”没有对应的“待验证正则表达式 filterSuccessRegex”，并且对应的“有效指纹子串索引 index”不为 0，则不做任何操作。

如果“待验证正则表达式匹配进度的映射 filterSuccessRegexMap”已有对应的“待验证正则表达式 filterSuccessRegex”，并且值等于对应的“有效指纹子串索引 index”减 1，则将“待验证正则表达式匹配进度的映射 filterSuccessRegexMap”键为“待验证正则表达式 filterSuccessRegex”单元的值设置为“有效指纹子串索引 index”。

如果“待验证正则表达式匹配进度的映射 filterSuccessRegexMap”已有对应的“待验证正则表达式 filterSuccessRegex”，并且值不等于对应的“有效指纹子串索引 index”减 1，则不做任何操作。

最终，只有“待验证正则表达式 filterSuccessRegex”对应的“有效指纹子串索引 index”为正则表达式“有效指纹子串”最大索引值时，才会进入验证阶段。

流程图：

2.9 资源控制

03 文献

3.1 NFA 的ε跳转优化

3.2 自动机空间压缩

Becchi M，Crowley P.An improved algorithm to accelerate regular expression evaluation[C]//Proceedings of the 3rd ACM/IEEE Symposium on Architecture for Networking and Communications Systems，2007：145-154.

Becchi M，Crowley P.A-DFA：a time- and space-efficient DFA compression algorithm for fast regular expression evaluation[J].ACM Transactions on Architecture and Code Optimization（TACO），2013，10（1）：4.

徐乾, 鄂跃鹏, 葛敬国, et al. 深度包检测中一种高效的正则表达式压缩算法[J]. 软件学报, 2009, 20(8):2214-2226.

3.3 提升匹配速度

Fu Z，Liu Z，Li J.Efficient parallelization of regular expression matching for deep inspection[C]//2017 26th International Conference on Computer Communication and Networks（ICCCN），2017：1-9.

Jiang P，Agrawal G.Combining SIMD and many/multicore parallelism for finite state machines with enumerative speculation[J].ACM SIGPLAN Notices，2017，52（8）：179-191.

Kim J, Park J. FPGA-Based Memory Efficient Shift-And Algorithm for Regular Expression Matching[C]// International Symposium on Applied Reconfigurable Computing. 2018.

3.4 新型自动机

Becchi M , Crowley P . A hybrid finite automaton for practical deep packet inspection[C]// Acm Conference on Emerging Network Experiment & Technology. DBLP, 2007.

张树壮, 吴志刚, 罗浩. 一种高效的正则表达式匹配方法[J]. 高技术通讯, 2014, 24(6):551-557.

Fu Z, Zhou S, Li J. bitFA: A Novel Data Structure for Fast and Update-friendly Regular Expression Matching[C]// Sigcomm Posters & Demos. 2017.

Yang X , Qiu T , Wang B , et al. Negative Factor:Improving Regular-Expression Matching in Strings[J]. Acm Transactions on Database Systems, 2016, 40(4):1-46.

3.5 规则拆分和分组

Becchi M , Franklin M , Crowley P . A workload for evaluating deep packet inspection architectures[C]// Workload Characterization, 2008. IISWC 2008. IEEE International Symposium on. IEEE, 2008.

柳厅文,孙永,卜东波,等. 正则表达式分组的 1/(1-1/k)-近似算法[J]. 软件学报, 2012, 23(9):2261-2272.

Liu T，Liu A X，Shi J，et al.Towards fast and optimal grouping of regular expressions via DFA size estimation[J].IEEE Journal on Selected Areas in Communications，2014，32（10）：1797-1809.

Fu Z，Wang K，Cai L，et al.Intelligent and efficient grouping algorithms for large-scale regular expressions[J]. Computers & Electrical Engineering，2018，67：223-234.