柔性多模正则匹配引擎

分享嘉宾：王彬@奇安信

出品平台：DataFunTalk

导读： 正则表达式，每个计算机从业人员都熟知的技术，你真的懂吗？ 一个老掉牙的、不时尚的技术如何在 "国内首款分布式流式关联分析引擎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 ) "。

1. 创建"当前自动机为nowNfa"。

2. 遍历正则表达式，根据"当前字符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的ε跳转优化

Jing M, Yang Y, Ning L, et al. Postfix automata[J]. Theoretical Computer Science, 2014, 562(C):590-605.

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.

3.6 工程软件

1. 腾讯安全零距离之大眼——大型网络流量分析系统软件篇

https://security.tencent.com/index.php/blog/msg/40

2. HOW WE MATCH REGULAR EXPRESSIONS

https://www.hyperscan.io/2015/10/20/match-regular-expressions/

3. WELCOME TO HYPERSCAN!

https://www.hyperscan.io/2015/10/13/welcome-to-hyperscan/

今天的分享就到这里，谢谢大家。

在文末分享、点赞、在看，给个三连击呗~~

嘉宾介绍：

王彬

奇安信 | 异常检测研发工程师

告警监控领域从业7年，近年发表分布式流式异常检测相关专利20余个，对Flink源码、智能异常检测算法有深入理解。

社群推荐：

欢迎加入  DataFunTalk 大数据 交流群 ，跟同行零距离交流。如想进群，请识别下面的二维码，回复“ DSJ ”入群 。

文章推荐：

基于 Flink 构建 CEP 引擎的挑战和实践

关于我们：

DataFunTalk  专注 于大数据、人工智能技术应用的分享与交流。发起于2017年，在北京、上海、深圳、杭州等城市举办超过100场线下沙龙、论坛及峰会，已邀请近500位专家和学者参与分享。其公众号 DataFunTalk 累计生产原创文章300+，百万+阅读，7万+精准粉丝。

分享、点赞、在看 ，给个 三连击 呗！ :point_down: