Automata概述使用Linux开发环境的程序员一定用过sed、grep、lex等Linux系统工具，sed、grep是Linux中重要的数据流搜索和处理工具，而Lex是linux下广泛使用的词法分析器生成器，用于复杂的语言解析，编译器前端开发等。虽然这些linux系统工具的功能各不相同，但是这些工具内部都实现了一个自动机，用于基于正则表达式的文本搜索关于输入期望。自动机是正则表达式的等效实现。在计算理论方面，正则表达式和自动机在理论上具有严格的等价性，正则表达式和自动机在定义匹配模式方面具有等价的能力。正则表达式是匹配模式的形式化表达，自动机是匹配模式的计算机实现表达。安全检测与防护领域的入侵检测系统（IntrusionDetectionSystems，IDS）、入侵防御系统（IntrusionPreventionSystem，IPS）、网络应用防火墙（WebApplicationFirewall，WAF）等都应用了大量的网络数据流的自动机技术。正则表达式匹配，实现对网络数据包的检测和分析。IPS/IDS和WAF系统自动机技术也广泛应用于DPI系统（DeepPacketInspection，DPI）中，实现对网络数据包的分析和识别。DPI系统应用于应用程序识别2.正则表达式和自动机2.1正则表达式和自动机初识在形式语言和自动机理论中，正则表达式和有穷自动机在理论上具有严格的等价性。正则表达式与自动机的等价性自动机分为确定性有限自动机（DFA）和非确定性有限自动机（NFA）。在确定性有穷自动机中，对于给定的确定状态和确定输入，其状态转移关系是确定且唯一的，每一时刻只有一个活动状态。相反，在非确定性有穷自动机中，对于给定的确定状态和确定输入，可能存在多种状态转移关系，在某一时刻可能存在多个激活状态。非确定性有穷自动机主要分为epsilon-NFAwithepsilontransfer和NFAwithoutepsilontransfer，其经典代表分别是ThompsonNFA和GluskovNFA。ThompsonNFA上图显示了识别正则表达式(AB|CD)*AFF*的ThompsonNFA。可以看出thompsonNFA是由epsilon边连接的基本子正则表达式NFA单元组成的，epsilon边连接的两个状态可以通过空字符进行转换，即存在无条件状态转换关系，由字母标识的边连接的两个状态表示需要在两个状态之间输入相应的字符才能转移到活动状态。GluskovNFA上图显示了识别正则表达式(AB|CD)*AFF*的GluskovNFA。显然，GluskovNFA比ThompsonNFA简洁得多，而且GlukovNFA中NFA的状态数与正则表达式中出现的字符和字符集的总数是一致的。与ThompsonNFA相比，GluskovNFA状态更少，结构更紧凑。同时，在GluskovNFA中，状态间的跳转条件被移到节点中，成为节点的激活条件，因此GluskovNFA的运行时处理会变得更简单。运行时读取一个字符c，可以知道字符c可以激活的状态集reach(c)，那么只需要根据当前激活状态计算其后继状态集succ(s)集合GluskovNFA的s，并取reach(c)和succ(s)的交集，得到的交集就是GluskovNFA的下一时刻激活状态集。对于ThompsonNFA，节点的激活条件不唯一，需要处理epsilon边连接的状态转移关系，下一时刻激活状态集的计算会比较复杂。使用ThompsonNFA或GluskovNFA的子集构造算法，您可以将NFA转换为DFA。与NFA相比，DFA最大的优势是性能，劣势是空间开销。这是因为DFA状态转移的确定性是通过组合NFA的不同状态获得的。因此，DFA和NFA在理论上是功能等价的。DFA状态数上限与NFA状态数呈指数关系。上面的DFA状态图是将识别正则表达式(AB|CD)*AFF*的thompsonNFA使用子集构造算法转化为DFA后的状态图。图中每个蓝色框的序号集合中的序号对应thompsonNFA中状态的序号，反映了DFA中的每个状态都对应NFA状态集的一个子集。2.2主流开源自动机相关库目前广泛使用的主流开源自动机相关库主要有Pcre、RE2、Hyperscan：Pcre支持的正则表达式语法最全面、最复杂，PCRE只支持block模式编译和匹配。并且只支持单个正则表达式的编译匹配，性能是三款软件中最差的。对于需要并行匹配大规模正则规则的场景，pcre显得力不从心。Google开源的正则匹配引擎RE2是一个基于虚拟机方法C++的快速、安全、线程友好的正则匹配自动机。它支持的正则表达式语法比pcre少，但比hyperscan多。RE2支持少量正则规则集的并行匹配，不支持只能用回溯算法实现的正则表达式语法。Hyperscan是Intel开源的基于正则表达式NFA/DFA图分析和反汇编的高性能正则表达式混合自动机。三款软件中，hyperscan支持的正则语法最少，但性能最强，支持大规模正则规则集的并行匹配。3.自动机性能优化实践正则表达式的匹配率是制约IDS/IPS、WAF、DPI等业务的重要性能瓶颈。提高正则表达式自动机的匹配性能是提升上述业务能力的关键。下面介绍自动机性能优化的几种主流方法。3.1基于预过滤的性能优化基于预过滤的正则表达式优化策略上图展示了基于字符串匹配器预过滤的正则表达式匹配优化策略。该方案会在正则表达式的编译过程中提取正则表达式中的字符串信息，并根据提取的字符串构建多字符串预匹配器。例如，对于规则0，将提取字符串SEARCH，对于规则N，将提取字符串SUBSCRIBE。在匹配输入期望的过程中，首先会使用多字符串匹配器来匹配字符串。如果在匹配过程中匹配到字符串SERACH，但没有匹配到字符串SUBCRIBE，则根据正则表达式规则0进一步使用，进行第二阶段的正则表达式匹配。可以看出，基于预过滤的正则表达式匹配方案是一个两阶段的匹配过程。虽然基于字符串匹配器的预过滤正则表达式匹配方案可以提前过滤掉不匹配的语料。但仍存在诸多不足：(1)正则表达式中存在字符串重复匹配，即预过滤的字符串匹配组件匹配一个字符串一次，自动机重复匹配一个字符串；(2)过滤匹配方案的第二阶段，难以有效利用CPU的SIMD指令集，利用自动机匹配字符串进行字符串匹配的并行加速；(3)关键串选择不合理容易拖累正则表达式公式匹配的整体性能。针对基于字符串匹配器预过滤的正则表达式匹配方案的不足，一种更加新颖有效的基于正则表达式分解的正则表达式匹配方案应运而生。3.2基于正则表达式分解的性能优化基于正则表达式分解的正则表达式匹配方案首先将正则表达式分解为若干子串和子正则表达式。反汇编后的子串将构造为字符串匹配器（字符串匹配器可以有效利用CPU的SIMD指令集进行并行加速，比使用自动机器匹配进行字符串匹配具有数量级的性能优势），反汇编后的子正则表达式将构造为子自动机，例如NFA或DFA。在对输入语料进行正则表达式匹配时，该方案会按照一定顺序调用各个匹配器，尽量先调用字符串匹配器进行字符串匹配。只有当前匹配器匹配成功后，才会调用下一个匹配器。只有所有的匹配器按照预定的顺序匹配成功，反汇编后的正则表达式才能匹配成功。基于规则拆分的正则表达式匹配策略上图为使用反汇编后的正则表达式.*start[^x]comA+匹配输入字符串AstarZcomA的例子。首先将正则表达式拆解为五部分，分别对应自动机部分FA2、FA1、FA0和字符串部分STR2、STR1。反汇编后构建的各个子自动机与子串匹配器的匹配顺序为STR1->STR2->FA1->FA0->FA2。反汇编后构造的每个子自动机和子串遵循以下优先级原则：字符串匹配优先于自动机匹配。两个字符串中间的自动机匹配优先于其他地方的自动机匹配。匹配语料库尾部的自动机优先于匹配语料库头部的自动机。第一优先原则很好理解，因为字符串匹配率比自动机匹配率有一个数量级的性能优势。自动机需要在两个字符串之间匹配的语料库的行首和末尾是锚定的，因此其优先级高于其他自动机，即优先级原则2。由于匹配末尾的自动机corpus锚定到行首，不需要回溯，具有更高的优先级，即优先原则3。可以看出，拆解后的各个子自动机与子串匹配器的匹配顺序原则上遵循：性能开销较小的匹配过程，其匹配顺序较高。对于输入语料，AstarZcomA会首先使用字符串匹配器来匹配字符串STR1。此时字符串匹配成功，继续调用字符串匹配器匹配字符串STR2。此时字符串STR2匹配失败，后续的FA1、FA0、FA2进行匹配。如果输入字符串为AstartZcomA，则依次匹配STR1、STR2、FA1、FA0、FA2，最后输出匹配成功信息。4、对正则规则匹配应用的思考在互联网领域的各种开发和应用中，网络攻击检测、应用流量识别等大量场景都需要使用正则引擎来匹配正则表达式。正则表达式的匹配效率不仅取决于所使用的正则引擎的性能，还取决于正则表达式的书写形式。揭秘正则引擎的实现原理，可以让我们更深入地了解正则表达式的形式与正则引擎的效率之间的关联，更好地指导我们进行正则引擎的性能调优。以下原则的正则表达式编写指南可以帮助我们在开发和应用过程中更高效地匹配正则表达式：尽量避免使用需要通过回溯方法实现的正则表达式语法，例如回溯引用语法。回溯的引入将在最坏情况下以指数方式增加正则匹配的时间复杂度。尽量避免在正则表达式中使用(.*)和{min,max}等语法。(.*)引入的不确定性和{min,max}带来的有界重复是正则表达式引擎瓶颈的重要表现。尽量使正则表达式更明确一些，比如尽量在正则表达式中写入更明确的字符或字符串。
