2018，54（20）1引言随着网络技术的飞速发展，互联网、云计算、移动通信、物联网等已深入到生产和生活中的各个方面，成为像水电气一样必不可少的基础设施，全球互联网用户已经
突破了40亿[1]，每月的互联网流量已经达到了121694PB [2]。伴随网络技术迅速发展和普及的是层出不穷的安全事高性能正则表达式匹配算法综述
付哲1，2，李军2
FU Zhe 1，2,LI Jun 2
1.清华大学自动化系，北京100084
2.清华大学信息技术研究院，北京100084
1.Department of Automation,Tsinghua University,Beijing 100084,China
2.Research Institute of Information Technology,Tsinghua University,Beijing 100084,China
FU Zhe,LI Jun.Survey on high performance regular expression matching algorithms.Computer Engineering and Applications,2018,54（20）：1-13.
Abstract ：Deep inspection is playing an important role in providing secure network environment and guaranteeing net-work service quality.As a key technology for high-performance deep inspection,regular expression matching algorithms attract a great deal of attention in both academic research and industrial practice.With the rapid development of network technology,the volume of network traffic keeps increasing,the rulesets used for deep inspection are becoming larger while more complex,and the network topology is more flexible and dynamic than ever.Existing matching methods are facing many challenges,including those in matching speed,memory consumption,update ability,and so on.This survey first introduces the background of regular expression matching problem,then categorizes existing algorithms in the aspects of memory compression,speed acceleration,new automata design,and rule partition and grouping,and evaluates them in matching speed,memory consumption,as well as preprocessing with real life network traffic and rulesets.A guideline for efficient regular expression matching under different scenarios,and an outline of future work on high performance regular expression matching algorithms are also provided.
Key words ：regular expression matching;finite automata;algorithm;evaluation
摘要：深度检测在维护网络安全、保证服务质量等方面扮演着重要的角。正则表达式匹配算法作为高性能深度检测的核心技术，具有重要的研究价值和实践意义。随着网络流量不断增长、规则数目持续增
多以及网络结构日趋灵活和动态，现有的正则表达式匹配算法面临着匹配速度、内存占用和更新能力等多方面的挑战。介绍了正则表达式匹配算法的研究背景，从空间压缩、匹配加速、新型自动机设计以及规则拆分和分组四个角度入手，分类总结了学术界具有影响力的研究成果。通过基于真实网络流量的评测，比较了几种经典匹配算法在不同规则集上的匹配速度、内存占用和预处理时间等性能指标，并给出了不同需求场景下高效正则表达式匹配算法的选择建议，归纳了高性能正则表达式匹配算法的下一步发展方向。
关键词：正则表达式匹配；有穷自动机；算法；评测
文献标志码：A 中图分类号：TP 393doi ：10.3778/j.issn.1002-8331.1808-0339
⦾热点与综述⦾
基金项目：国家重点研发计划（No.2016YFB1000102）。
作者简介：付哲（1991—），男，博士，主要研究领域为高性能算法，E-mail ：zhefu0@outlook ；李军（1962—），男，博士，研究员，
主要研究领域为网络体系结构和网络安全。
收稿日期：2018-08-20修回日期：2018-09-17文章编号：1002-8331（2018）20-0001-13
Computer Engineering and Applications 计算机工程与应用
1
Computer Engineering and Applications计算机工程与应用2018，54（20）
件。近几年爆发的Heartbleed、WannaCry、Memcache放大攻击等安全威胁已经给互联网服务提供商带来数百亿的损失[3-4]。网络安全问题已成为社会无法回避、并且需要高度重视的关键问题之一。另一方面，网络应用的多样化和差异化，需要网络服务提供商能够提供满足不同服务质量的网络服务，云际网络更是为网络服务的发展提供了宽广的平台[5]。近年来，大量新型应用层出不迭，如基于点对点技术
的视频分发、在线直播等，需要更加复杂和灵活的规则对其进行准确识别和管理。
网络流量的急剧增大和应用类型的迅速增多极大地提高了对网络流量进行检测和管理的难度。防火墙（Firewall）、入侵检测系统（Intrusion Detection System，IDS）、入侵防御系统（Intrusion Protection System，IPS）等是目前广泛使用的网络流量检测与管理设备。传统的防火墙需要对网包（packet）的第三层、第四层包头（header）信息进行检测，包括源IP地址、目的IP地址、源端口号、目的端口号、协议等五元组信息。然而，越来越多的特征隐藏在网包载荷（payload）中，仅使用包头五元组信息无法对流量进行细粒度识别，不足以检测出复杂的安全威胁。深度检测（Deep Inspection）应运而生，其不仅对网包包头进行检测，还会对网包载荷进行匹配。因此，深度检测技术广泛应用于流量检测和管理设备。一般说来，网络流量进入防火墙和IDS/IPS等设备中后，首先解析网包的五元组信息，分类为不同的网流（flow），根据管理策略表，执行不同的处理动作。对于需要进行深度检测的网流，相应设备会对网包载荷进行规则匹配，并根据匹配结果执行相应的操作。
早期，深度检测通常使用字符串匹配算法。经典的字符串匹配算法有Knuth-Morris-Pratt（KMP）[6]，Boyer-Moore（BM）[7]，Aho-Corasick（AC）[8]和Wu-Manber（WM）[9]等。随着网络服务和应用的不断发展，待检测的特征变得越来越复杂，难以用精确字符串进行准确的描述。正则表达式使用单个字符串可以描述一系列满足某个句法规则的字符串集合，因此其语义表达能力和灵活性远远高于精确字符串，逐渐成为深度检测中规则描述和匹配的首选方法，广泛应用于安全检测、应用分类、协议识别等领
域。
高性能正则表达式匹配算法作为网络流量深度检测的关键技术，一直受到学术界和工业界的广泛关注。本文对近年来基于通用平台的高性能正则表达式匹配算法进行了全面的分析和总结，主要贡献包括：（1）介绍了正则表达式匹配算法的研究背景，并总结了现阶段匹配算法面临的挑战。
（2）归纳了通用平台上高性能正则表达式匹配算法研究：从空间压缩、性能加速、新型自动机以及规则拆分和分组四个不同出发点总结了现有的研究成果，并分析比较各算法的优缺点。
（3）测试了高性能正则表达式匹配算法性能：以匹配速度、内存占用和预处理时间作为评测指标，通过真实网络流量比较了几种经典的匹配算法在不同规则集上的实际性能。
（4）提供了正则表达式算法的选用建议：针对不同的应用场景和需求，本文给出了高效正则表达式匹配算法选择方案。
2背景与挑战
网络流量深度检测中，正则表达式由于其灵活、强大的表达能力，成为定义复杂特征的首选形式。然而，正则表达式匹配在多个指标上都面临着性能挑战，成为了深度检测的瓶颈。
2.1正则表达式
从历史上来看，正则表达式最初是作为一个简单计算模型被理论计算机科学家于20世纪50年代提出的[10]。1968年，Thompson编写的文本编辑器QED首先实现了程序意义上的正则表达式匹配[11]。他和Ritchie 随后创造的Unix，将正则表达式匹配引入了计算机的主流应用[12]。到了20世纪70年代晚期，正则表达式匹配已成为Unix的关键功能，成为ed、sed、grep、egrep、awk 等工具中的核心方法。
一般而言，正则表达式由一系列ASCII（American Standard Code for Information Interchange，美国信息交换标准代码）字符构成，其中一部分作为元字符（Meta-character）。点号（.）、星号（*）和垂直符号（|）是正则表达式中应用最广泛的元字符。与普通ASCII字符不同，元字符表示特殊的含义。表1列举了正则表达式中最常见的若干种元字符以及它们的含义及示例。元字符给予了正则表达式丰富的表达能力：一条正则表达式可以匹配一组满足要求的精确字符串，而不仅仅是单条精确字符串。例如，Snort[13]利用正则表达式“[?&]（search|topic）= [^&]*?（\x27|\%27）（\s*|（\%20）*）（\x3b|\%3b）”（见图1）检测Twiki[14]搜索函数的非法远程代码调用。这一特征无法用单条精确字符串描述。
2.2自动机
在网络流量检测中，精确字符串匹配一般通过BM、WM、AC等匹配算法实现，或采用哈希、bloom-filter 等方法进行加速。然而，传统的精确字符串匹配方法难以实现正则表达式中元字符所描述的语义，
因此，正则表达式通常首先编译为有穷自动机（Finite Automata）进行匹配。理论证明，正则表达式和有穷自动机在数学上是完全等价的[15]。对于任何一个正则表达式r，总存在一个有穷自动机A，其表达的语义与r完全相同；反
2
2018，54（20）之，对于任何一个有穷自动机A ，总存在一条正则表达式r ，其表达的语义与A 完全相同。非确定型有穷自动机（Nondeterministic FA ，NFA ）与确定型有穷自动机（Deterministic FA ，DFA ）是最常见的两种自动机，它们均由五元组(Q ,Σ,δ,q 0,F )构成，如下：Q ：有限的状态集合，表
示自动机的状态空间。Σ：有限的输入字符集合，表示自动机接受的输入字符范围（对于网络流量检测，一般为ASCII 中的256个字符）。δ：状态转移函数，Q ×Σ→Q ，表示对于每一个输入字符，自动机的状态应该如何进行跳转。q 0⊆Q ：初始状态，表示自动机匹配前所处的状态。F ⊆Q ：匹配状态的集合，表示跳转到自动机中这些状态时，发生了规则匹配。在DFA 中，状态转移函数δ在任意时刻对于输入字符仅返回一个确定的状态，即DFA 中状态的跳转是唯一确定的。而对于NFA ，状态转移函数δ会返回三种结果：一个状态，多个状态或者空。因此，NFA 中的状态转移是非确定的。Thompson 构造法[11]是常见的将正则表达式集合转换为NFA 的算法。此外，McNaughton-Yamada 构造法[16]是另一种将正则表达式转化为自动机的方法。构造后的NFA 可以进行ε精简化，以消除冗余的ε状态和转移边[17]。NFA 通过子集构造法[15]可被转化为DFA ，而DFA 可以进一步的最小化，消除多余状态和
死状态。
图2和图3分别展示了规则“ab.*cd ”对应的NFA 和
DFA 结构图。图中，状态0为起始状态，双层圆圈为匹
配状态（表示若该状态激活，则有规则被匹配）。状态之间的箭头表示状态转移，如果箭头上的字符为输入字
符，则发生如箭头所示的状态跳转。例如在图2中，若
当前状态1处于激活状态，输入字符是“b ”，那么状态1
将会沿着箭头跳转至状态3，即读入输入字符“b ”后，状
态3处于激活状态，状态1处于非激活状态。
从图中可以直观地看出，NFA 相对于DFA 结构更简单。理论分析[18]表明，对于长度为n 的正则表达式规
则，NFA 的空间复杂度为O (n )。但是，NFA 中可能出现多个状态同时激活的情况。例如，当图2中状态3处于激活状态时，若输入字符“c ”，状态3会跳转到状态5，同时由于状态3有一个对于任何字符均指向自己的状态
转移，因此状态3依旧处于激活状态。所以读入输入字符“c ”后，状态3和状态5均处于激活状态。在最坏情况
下，NFA 中所有状态均处于激活状态，而每一个状态可能会跳转到其他所有的状态，因此对于长度为n 的正则表达式规则，NFA 在通用软件平台上的时间复杂度高
达O (n 2)。
在DFA 中，所有状态的状态跳转是确定和唯一的。例如，若图3中状态3处于激活状态，输入字符是“c ”，那么状态3将会确定地跳转到状态5，不会再激活其他状态。因此，DFA 的时间复杂度为O (1)，在匹配性能上相对于NFA 有巨大的优势，逐渐成为深度检测中规则匹配的首选方案。然而，DFA 优秀的时间性能是以
元字符.[][^]*+{m ，}{m ，n }|^$含义及举例任意字符例如：“a.b ”匹配“aab ”，“abb ”，“acb ”等括号中的任意字符
例如：“[ab]”匹配字符“a ”或者“b ”不在括号中的任意字符例如：“[^ab]”匹配除“a ”，“b ”之外的任意字符前一元素的零次或多次匹配例如：“a*b ”匹配“ab ”，“aab ”，“aaab ”等前一元素的一次或多次匹配
例如：“a+b ”匹配“aab ”，“aaab ”等前一元素至少重复m 次例如：“a{2，}”匹配“aa ”，“aaa ”，“aaaa ”等前一元素至少重复m 次，不超过n 次
例如：“a{2，4}”匹配“aa ”，“aaa ”，“aaaa ”符号前或后的元素之一
例如：“foo|bar ”匹配“boo ”或者“bar ”字符串内起始位置例如：“^foo ”仅匹配起始处有“foo ”的字符串字符串内结束位置例如：“bar\$”仅匹配结尾处有“bar ”的字符串表1正则表达式中常见的元字符含义及示例[?&]（search |topic ）=[^&]*?（\×27|%27）（\s *|（%20）*）（\×3b|%3b ）“?”或“&”单条字符串非“&”字
符字符“'”空格字符“；”或0或多次重复（非贪婪）0或多次重复（贪婪）图1Snort 中用来检测Twiki 非法远程调用的正则表达式规则0
2468
7
531a
b c d *
*
*f g h e 图2规则“ab.*cd ”对应的NFA
a a a e e
b c d f c d h g b h g
a e f e other other other other
13
5
69
024
7811
10
1213
15
14
图3规则“ab.*cd ”对应的DFA 付哲，李军：高性能正则表达式匹配算法综述
3
Computer Engineering and Applications计算机工程与应用2018，54（20）
巨大的空间消耗为代价的。子集构造法实际上是遍历NFA中所有可能的状态组合，将每一种状态组合转化为DFA中的一个新状态，因此，对于长度为n的正则表达式规则，DFA的空间复杂度高达O(|Σ|n)（|Σ|是输入字符集合中的元素个数）。在图2和图3的例子里，规则“ab.*cd”对应的NFA有9个状态，而DFA有16个状态，空间消耗增长了近一倍。当语义更加复杂，规则数目更大时，DFA所需的状态空间将指数级增长，甚至超过编译器的物理内存上限，发生“状态爆炸”。因此，DFA方法很难直接应用于大规模复杂规则集。
此外，子集构造法本身的时间复杂度也为指数级，由NFA构造DFA需要大量的预处理时间，使得DFA方法难以应对规则频繁更新的场景。
2.3现阶段的挑战
正则表达式匹配技术经过数十年的探索与发展，已经有一定的成果与积累。然而，目前的匹配算法依然存在诸多待解决的问题。
（1）匹配速度
深度检测规则匹配引擎的处理速度一直是正则表达式规则匹配算法最主要的关注点之一。随着网络技术的不断发展，网络带宽已从传统的1Gb/s、10Gb/s，逐步提高到40Gb/s、100Gb/s，正迈向400Gb/s大关。另一方面，软件定义网络（Software-Defined Networking，SDN）和网络功能虚拟化（Network Functions Virtualization，NFV）等技术逐渐兴起和成熟后，越来越多的网络功能与专有硬件设备解耦，采用通用的计算、存储、网络设备实现各种网络功能，降低成本，并且同时带来灵活部署、资源共享等多方面优势。然而，通用平台上的正则表达式匹配算法性能难以与FPGA、TCAM等专有硬件相比，匹配速度成为高性能网络流量检测与管理的瓶颈之一。
（2）内存占用
深度检测使用的正则表达式规则数目增长迅速。以开源入侵检测系统Snort为例，它从2003年开始使用正则表达式对匹配特征进行描述。到2006年，采用正则表达式的规则数目增加到1131条。截止到2018
年，这一数字已经快速上升到28086条（根据snortrules-snapshot-29111规则集进行统计，该规则集发布于2018年1月16日）。许多实验[19-20]表明，对于较小规模规则集（编译后的DFA约有1万个状态），DFA内存占用约为10MB，传统的规则匹配引擎能取得较高的匹配性能。但是，对于像Snort这样超过10000条规则的大规模规则集，所对应的DFA状态数会超过1百万，内存占用达到数GB，超过了很多深度检测设备的内存空间上限。除了规则数目之外，为了描述丰富的匹配特征，规则的语义也变得越来越复杂。复杂的语义增大了自动机的处理难度，进一步加剧了匹配过程中的内存占用。
（3）更新能力
在SDN与NFV环境下，网络拓扑动态变化。传统的网络流量检测和管理设备被抽象为虚拟的网络功能，可以在网络拓扑中灵活实施和扩展。此外，为了及时应对突发网络威胁，安全规则需要快速部署和及时生效。例如，在思科的邮件安全应用中，检测规则的更新频率为3~5min[21]。因此，网络流量的检测和管理规则动态性大大增加。然而，目前常见的基于DFA的规则匹配方法在规则数目较多时，预处理耗时太长，无法满足动态更新规则的网络管理需求。另一方面，基于NFA的规则匹配方法虽然预处理时间短，但是较低的匹配性能制约了NFA方法在网络流量检测与管理中（特别是虚拟网络环境下）的大范围应用。如何在规则预处理时间受限的情况下，实现快速的规则更新和高速的规则匹配，是正则表达式匹配方法所面临的新挑战。
3研究现状分析
自21世纪初至今，正则表达式匹配问题的相关研究持续受到高度关注，涌现出了一大批优秀的研究成果。本章着眼于通用平台上的正则表达式匹配算法，按照压缩自动机空间、提升匹配速度、设计新型自动机以及规则拆分和分组四个方面，对代表性的正则表达式匹配算法进行归类、分析和总结。
3.1压缩自动机空间
DFA处理速度上的优势使其成为规则匹配的首选方案。然而，DFA过高的空间复杂度是大规模规则匹配应用中不可回避的问题。目前学术界已有不少研究着眼于解决以DFA自动机空间消耗过大的问题[22-31]。通常来说，DFA使用状态转移表（State Transition Table，STT）表示自动机的结构，状态转移表可以看作一个二维的矩阵，矩阵的行表示DFA中的状态，矩阵的列表示输入字符。从不同的切入点入手，DFA空间压缩方法可以分为三类：字母表重编码、相似状态合并以及冗余转移边压缩。
在DFA的状态转移表中，如果存在多个不同的输入字符，所有的DFA状态在这些输入字符下状态跳转情况一致，那么这些输入字符可以看作是等价的。因此，可以用一个新的字符重新编码这些输入字符，从而达到压缩状态转移表列的目的[22-23]。如图4所示，在原始状态转移表中，输入字符a、c、d所在列完全相同，因此可以用一个新的输入字符a'重新编码a、c、d三个字符。同理，b和e可以由新字符b'替代，等等。字母表重新编码后，状态转移表的列数由8压缩至4，因此所占空间减少了50%。通过在查状态转移表前使用一个专门的
4
2018，54（20）索引表将原输入字符与重新编码后的输入字符对应，压缩后的状态转移表与原始状态转移表表示完全相同的DFA 。Kong 等人[24]进一步观察到，在多数情况下一些输入字符对于绝大多数DFA 状态是等价的，仅有一小部分状态在这些输入字符下跳转情况不同。因此，Kong 等人将整个状态集合划分成若干互不相交的子集，对于每一个子集使用不同的字母表重编码方式。在状态合并方面，Becchi 等人[25]提出了一种将多个相同跳转目的地的状态合并为一个状态的方法。通过引入带标签的状态转移边，这些相似的状态可以合并为一个状态，从而大大减少DFA 状态数。实验结果证明该方法与原始DFA 状态转移表相比，可以节省90%的空间消耗。字母表重编码和相似状态合并减少了DFA 状态转移矩阵的
正则化相位跟随代码列数或者行数，而冗余转移边压缩通过精简的表示方法，等同于减少了状态转移表中有效元素的个数。D 2FA [26-27]是最经典的转移边压缩方法之一。图5表示了正则表达式规则“a+”“b+c ”和“c*d+”对应的原始DFA 以及冗余转移边压缩后的D 2FA 的示意图。三条规则对应的原始DFA 结构如图5（a ）所示，图5（b ）表示压缩后的D 2FA 结构，其中加粗箭头表示该状态的默认转移。图5（c ）和图5（d ）展示了两种方法的状态转移表。如果在D 2FA 的状态转移表中无法到相对应的状态转移，那么先按照默认转移跳转到下一状态，之后继续查状态转移表，不断重复上述步骤，直到到正确的下一跳状态为止。例如，当状态3处于激活状态，输入字符是“a ”时，由于无法在D 2FA 状态转移表到相对应的下一跳状态，因此状态3先按照默认转移跳转至状态1，继续查状态转移表，到状态1在输入字符是“a ”时的下一跳状态为状态2，因此状态3会跳转至状态2。在实践中，D 2FA 最多可以取得95%的压缩率。然而，在最坏情况下，对于每个输入字符，D 2FA 需要多次默认状态转移才能到正确的状态，匹配性能无法得到保证。许多方法对D 2FA 作出了改进[28-31]。A-DFA [28]通过限制默认转移状态的方向，取得了确定的默认状态跳转次数上界。在最坏情况下，A-DFA 中每个输入字符需要平均两次内存访问。然而，相比于D 2FA ，A-DFA 牺牲了一定的压缩率。OD 2FA [29]通过将源自同一NFA 状态的
多个DFA 状态合并为一个超级状态，进一步压缩空间。Patel 等人[30]提出一种“先最小化再联合”的框架，可以先对于每一条正则表达式构造出单独的D 2FA ，然后将多个D 2FA 合并为一个整合的D 2FA ，构造起来更加灵
活。δFA [31]
关注于相邻状态间的冗余转移。对于任意状态，δFA 仅储存与父状态（父状态定义该状态的上一跳状态）不同的状态转移。在实际状态跳转时，δFA 通过将父状态的状态转移情况与该状态相对于父状态的差别相结合，即可得到该状态的状态转移情况。对于每一个输入字符，δFA 平均仅需1次内存访问。但是，δFA 的
匹配速度提升依旧是以较低的压缩率作为代价的。综上所述，DFA 空间压缩方法实际上是在空间消耗和匹配时间之间取得一个权衡。几乎所有压缩方法都依赖于DFA 的生成，因此并不能从根源上解决DFA 状态爆炸问题。此外，这些方法均没有考虑预处理时间上的消耗。实验结果表明，在通用处理器平台上构造12条正则表达式对应的D 2FA 需要超过71小时的时间；即使采用优化后的D 2FA 合并方法，构造19条正则表达式对应的D 2FA 依旧需要超过77分钟的时间[32]。因此，过长的预处理时间使得这些方法不适用于大规模规则集下规则频繁更新的动态网络场景。3.2提升匹配速度近年来，一些研究利用自动机或者计算平台的特性，加速自动机的匹配速度[19，22-23，33-43]。多步自动机通过在一个时间周期读入多个输入字符，理论上能够取得成倍的吞吐率[22-23]。图6展示了正则表达式规则“ab+[cd]e ”对应的NFA 以及两步NFA （2-
NFA ）。在图6（b ）的2-NFA 中，匹配引擎一次性读入两个待处理字符。如果两个输入字符为“ab ”，那么2-NFA 中的状态2将被激活。如果之后的两个输入字符是“cd ”或者“de ”，那么状态4将被激活，
即发生了匹配。若输入字符DFA 状态1234a'3223b'2341c'2311d'1141输入字符DFA 状态1234a 3223b 2341c 3223d 3223e 2311f 2341g 1141（a ）原始状态转移表（b ）字母表重编码后的状态转移表图4字母表重编码方法示例DFA 状态12345输入字符a 22222b 33333c 11511d 44
444输入字符DFA 状态12
345a
2b 3c 15d 4默认转移
1
1
11
14532145
32c c a a b b
b c c d d b d b
c a a a d
c a b d
c d
（a ）原始DFA 结构（b ）D 2FA 结构
（c ）原始DFA 状态转移表（d ）D 2FA 状态转移表
图5D 2FA 算法示例
付哲，李军：高性能正则表达式匹配算法综述
5

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。