深入浅出 Hyperscan：高性能正则表达式算法原理与设计

版权信息

书名：深入浅出 Hyperscan：高性能正则表达式算法原理与设计

ISBN：978-7-115-55209-9

本书由人民邮电出版社发行数字版。版权所有，侵权必究。

您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。

我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。

如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。

版　　权

著　　　　王 翔 　昌 昊　 洪 扬　 张 磊

责任编辑　武晓燕

人民邮电出版社出版发行　　北京市丰台区成寿寺路11号

邮编　100164 　电子邮件　315@ptpress.com.cn

网址　http://www.ptpress.com.cn

读者服务热线：(010)81055410

反盗版热线：(010)81055315

内容提要

本书系统、全面、循序渐进地介绍Hyperscan技术。全书共8章，主要介绍正则表达式、经典匹配算法和正则表达式匹配所依赖的自动机原理、正则表达式匹配库等，并重点介绍Hyperscan的功能特性、设计原理和性能调优技巧，以及匹配引擎的核心算法和SIMD加速技术的运用，还展示了Hyperscan多样化的应用场景。

本书既适合作为Hyperscan开发者的学习用书，也适合作为高等院校计算机相关专业的师生用书和相关培训学校的教材。

前　　言

正则表达式的概念早在20世纪50年代就由美国数学家Kleene提出了。由于其丰富的描述性特征，正则表达式在网络安全场景下被广泛用于以规则匹配为核心的深度报文检测。流量特征的多样性决定了网络处理需要定义大量正则规则进行匹配，这成为了网络处理中的一大性能瓶颈。尽管在几十年的发展过程中，人们对正则表达式匹配的研究层出不穷，并沉淀了许多经典的算法，但在CPU上以软件形式运行这些经典算法还是难以满足网络处理性能的要求。因此定制化硬件（如FPGA）的正则匹配加速方案曾经一直主导潮流。在如今网络功能虚拟化（Network Function Virtualization，NFV）的浪潮中，如何在CPU上进行高效正则匹配以满足网络场景的需求已成为一大痛点。Hyperscan 应运而生，它让使用通用 x86 处理器进行高性能深度报文检测成为可能。

学术界研究者和产品开发者因此对Hyperscan产生了浓厚的兴趣，是什么样的算法设计让其显著优于先前的软件解决方案？由于实现上的复杂性，单纯从代码层面剖析Hyperscan对大多数人而言较为晦涩和烦琐，这也成为诸多探索者身前的一大壁垒。作为Hyperscan的开发者，我们想通过更好的渠道来分享其中的技术精华，让大家从中汲取一些核心设计思想以应用于实际工作和学习中。因此，我们编写了本书，将开发过程中的经验总结整理成册，供广大读者参考。

本书由浅入深，从正则表达式的介绍和经典算法的剖析来引导感兴趣的初学者入门；接着从Hyperscan总体设计原理逐步深入内部匹配引擎的介绍，梳理Hyperscan的核心技术点；最后以性能优化和应用场景收尾。为使本书更易于理解，我们使用大量图片和伪代码来解释各种算法和概念。

本书适合那些对算法有强烈兴趣的初学者，以及觉得算法晦涩难懂而无所适从的人阅读，也适合作为计算机相关专业的师生用书。同时它可为相关领域的工作者提供技术上的参考。本书不仅能帮助你理解经典的匹配算法，同时可以在系统设计层面教授你如何将理论与实践相结合。希望广大读者都能从本书中有所收获！

本书内容

本书主要介绍正则表达式算法库Hyperscan的设计原理、实现方法、技术细节以及具体应用。本书围绕Hyperscan的以下方面展开。

第1章介绍正则表达式的语法和相关背景知识。

第2章讲解字符串匹配和正则匹配的各类常规算法。

第3章介绍并比较目前业界广泛使用的较为成熟的正则匹配算法库。

第4章全面介绍Hyperscan算法库的功能特性。

第5章和第6章是本书的核心内容。

第5章介绍Hyperscan总体设计原则，并详细描述了对正则表达式的全新解构思路。

第6章介绍解构后的正则表达式模型的实现方法，并详细描述了优化手段。

第7章针对Hyperscan的使用，介绍了性能调优的若干原则与技巧。

第8章展示了Hyperscan与现实应用的整合案例。

本书特色

本书具有以下几个特色。

（1）算法思想，由浅入深。字符串匹配和正则匹配算法，一直是基础算法中比较晦涩的一类，讲解难度较大。而这些都是Hyperscan思想的“基石”。本书搜集诸多基础匹配算法，介绍顺序从简单到复杂，从直观到抽象。本书对每个算法源码抽丝剥茧，分析其优势或局限，对于Hyperscan算法本身的介绍，也蕴含着自顶向下、从宏观到微观的叙述脉络。读者可以从本书的内容编排感受到，即使是思想艰深的算法，也能有层次感。

（2）优化手段，精心打磨。Hyperscan算法的灵魂是优化。本书会在合适的位置展示经过体系化总结的Hyperscan与传统匹配方案的差异性内容，比如基于有效字符串提取的过滤设计、状态机的分类和调优思想、x86指令集加速技术等。上述内容作为对算法基础思想的完整补充，可以使读者充分体会Hyperscan算法之所以高性能的必要原因。

（3）伪码源码，相辅相成。代码是算法书中讲解算法必不可少的素材，但伪码和源码的取舍，却有讲究。本书基于“因地制宜”的原则来安排所需代码的形式。本着让读者完全明晰细节的初衷，我们会选择源码来介绍基础算法，完全展示算法的实现步骤，并配以详细讲解。而对于Hyperscan内部的算法实现，则会使用伪码，因为Hyperscan相较于基础算法而言，背景问题的上下文离一般读者更远，有许多实现细节是和项目本身强相关的，放在书中不免带来干扰，因此我们抽取了最核心的部分，写成伪代码，方便读者理解。

（4）图例表格，精准实用。本书对算法讲解的基本模式是，从基本思想出发，借助代码来解释关键步骤，通常还会辅以一个精心设计的实例运行过程。本书为算法实例的运行设计了风格简约的示意图和表格，力求还原出可以匹配算法运行的整个动态过程，以加深读者对算法的理解。

（5）理论实践，兼收并重。除了最核心的Hyperscan算法库的设计和相关内容的实现，本书还涵盖了算法库在实际应用中的更多丰富内容，比如：业界同类型算法库产品的对比；针对Hyperscan普通用户给出进行性能调优的实用建议；Hyperscan与成熟的开源产品整合的案例分析。本书将这些内容也分享出来，期望给读者呈现出一个全面的、立体的关于Hyperscan这个产品的故事。

建议和反馈

写书是一项极其琐碎、繁重的工作，尽管我已经竭力使本书接近完美，但仍然可能存在漏洞和瑕疵。欢迎读者提供关于本书的反馈意见，这有利于我们改进和提高，从而帮助更多的读者。如果你对本书有任何评论和建议，可以致信作者邮箱xiang.w.wang@intel.com进行交流或登录异步社区的本书页面进行评论，我将不胜感激。

致谢

感谢Langdale Geoffrey和Ravisundar Subhiksha为本书撰写的宝贵内容！感谢网络平台事业部经理周林和李雪峰在本书编写过程中提供的大力支持！感谢提供宝贵意见的同事们，感谢提供技术支持的同学们！感恩我遇到的众多良师益友！

资源与支持

本书由异步社区出品，社区（https://www.epubit.com/）为您提供相关资源和后续服务。

提交勘误

作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。

当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，单击“提交勘误”，输入勘误信息，单击“提交”按钮即可。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。

与我们联系

我们的联系邮箱是contact@epubit.com.cn。

如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。

如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区在线提交投稿（邮箱为wuxiaoyan@ptpress.com.cn）。

如果您所在的学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。

如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。

关于异步社区和异步图书

“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT技术图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT技术图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。

“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社近30年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。

异步社区

微信服务号

第1章　正则表达式简介

正则表达式是为了匹配特定的字符串而定义的描述字符串特征的模式，通常用于查找、替换符合特征的字符串，或者用来验证某个字符串是否符合指定的特征。

正则表达式最初的想法源于1940年，神经生理学家Warren McCulloch与Walter Pitts 研究出了一种用数学方式来描述神经网络的模型，他们将神经系统 中的神经元描述成小而简单的自动控制元。1951年，数学家Stephen Kleene利用被他称为“正则集合”的数学符号来描述此模型，这种表达式称为“正则表达式”，正则表达式从此成为现实。之后1968年，UNIX操作系统之父Ken Thompson将这套符号系统引入了他的文本编辑器qed，这种编辑器后来成了UNIX ed编辑器的基础，并由ed将正则表达式引入了grep。自此以后，正则表达式被广泛地应用到各种UNIX操作系统或类UNIX操作系统中。

正则表达式是一种强大、便捷、高效的文本处理工具，其赋予了使用者描述和分析文本的能力。从更高的层面上来说，正则表达式允许使用者掌控自己的数据为自己服务^[1]。掌握正则表达式，就是掌握自己的数据。接下来就让我们来了解一下正则表达式的相关知识。

1.1　正则表达式的语法

完整的正则表达式是由普通字符和元字符组成的文本模式。

普通字符包括大写和小写字母、所有的数字，以及没有特殊定义的标点和符号。元字符则是在正则表达式中具有特殊含义的一些符号。

正则表达式具有非常丰富的元字符并且提供了强大的描述能力，这是正则表达式具有强大处理能力的关键。构造正则表达式的方法和创建数学表达式的方法一样，可以通过多种元字符将子表达式结合在一起来创建更大的表达式。

正则表达式的元字符

下面列举了一些常见正则表达式的元字符，这里仅做简要的说明。此外，不同的流派支持的元字符和这些元字符代表的意义存在着细微的差异，这里参考了 Perl 兼容正则表达式（Perl Compatible Regular Expression，PCRE）的语法。关于PCRE的内容，请参考1.2.1小节。类似于数学运算符，正则表达式的元字符之间也有优先权顺序。在匹配过程中，按照正则表达式中从左到右、不同优先权先高后低来匹配相应的元字符。下面列举了优先权从高到低的正则表达式元字符的类型：转义符、字符组、分组、匹配量词、锚点和零宽断言，以及多选结构和嵌入条件等。

1．转义符

转义符用来清晰简便地表示一些特定的字符，包括一些不可打印字符。转义符和相关元字符，如表1.1所示。

表1.1　转义符和相关元字符

（1）利用转义符来匹配具有特殊含义的元字符本身。举例说明，*在正则表达式中是一个量词元字符，表示匹配前面的子表达式零次或任意次，但是转义之后*匹配的是*这个元字符本身。同样地，要匹配\元字符本身，需要写成\。

（2）利用字符缩略表示法来匹配其他方式很难描述的ASCII控制字符和不可打印字符，最常见的就是\n匹配换行符LF，\r匹配回车符CR。其中一个特别的用法是用\cX来匹配X指明的控制字符，X的值为A～Z或者a～z，例如\cJ匹配换行符LF，\cM匹配回车符CR。

（3）八进制转义和十六进制转义。\0dd表示八进制数dd所代表的字符，\xhh表示十六进制数hh所代表的字符。

2．字符组

字符组指在正则表达式中的某个位置表示一组指定的字符。常见的字符组表示方法有点号、普通字符组和字符组简记法，如表1.2所示。

表1.2　字符组

（1）点号可以匹配除了换行符之外的任意一个字符，如果设置了点号通配模式（dot-match-all），则可以匹配任意一个字符。

（2）普通字符组指通过[…]来匹配方括号中所列字符组合中的任意一个字符，或者通过[^…]来匹配方括号中所列字符组合之外的任意一个字符。

（3）字符组简记法指对一些常见字符更简便的表示方法。例如\d匹配任意一个数字，等价于[0-9]，\D匹配任意一个非数字字符，等价于[^0-9]。

需要强调的是，元字符的规定在字符组内外是有差别的。例如在字符组内部，*不是元字符，而-是元字符。此外，有些元字符在字符组内外的含义是不同的，例如\b匹配ASCII退格符，仅在字符组内部有效，在字符组外部则匹配单词边界。

3．分组

分组主要包括捕获型分组和非捕获型分组，如表1.3所示。

表1.3　捕获型分组和非捕获型分组

捕获型分组指的是以(…)标记的一个子表达式作为分组并捕获这个子表达式的匹配结果，这个捕获的结果可以利用前文提到的\1、\2……编号的方式来引用。这种分组并捕获匹配结果的(…)称之为捕获型分组。分组编号的规则是按照左括号(从左往右出现的顺序，从1开始编号。

还有一种命名捕获型分组(?<name>…)能够为捕获的内容命名，捕获的结果可以利用\1、\ 2……编号的方式来引用，也可以通过\k<name>的方式来引用。注意，如果捕获型分组和命名捕获型分组都用编号来引用，分组编号的规则是先只对普通捕获型分组按照左括号顺序编号，然后再对命名捕获型分组从左往右累计编号。

除此之外，(?:…)只支持分组，而不会捕获子表达式的匹配结果，因而也无法反向引用，这种称为非捕获型分组。非捕获型分组的作用主要是把复杂的表达式变得清晰，并且可以避免一些无用的捕获来提高正则表达式的效率。

还有一种特殊的分组(?>…)称为原子分组。也就是分组内的子表达式匹配之后，匹配的内容就固定下来不会交还已匹配的字符。原子分组也是非捕获型分组。

4．匹配量词

匹配量词能够用来限制前面子表达式的匹配次数。匹配量词又可以分为标准匹配量词、忽略优先量词和占有优先量词，如表1.4所示。

表1.4　匹配量词

（1）标准匹配量词包括*、+、?、{n}、{n,}和{n, m}。标准匹配量词都是贪婪（greedy）的，会尽可能地匹配更多的内容。举例来说，当正则表达式ab+去匹配字符串abbbb时，量词+会尽可能多地匹配字母b，所以最终的匹配结果是abbbb。

（2）忽略优先量词是在标准匹配量词之后紧跟?修饰符，即*?、+?、??、{n}?、{n,}?和{n,m}?。忽略优先量词和匹配优先量词正好相反，是非贪婪(non-greedy)的，会尽可能少地匹配内容。举例来说，当正则表达式ab+?去匹配字符串abbbb时，量词+?会尽可能少地去匹配字母b，所以最终的匹配结果是ab。

（3）占有优先量词是在标准匹配量词之后接+字符，即*+、++、?+、{n}+、{n,}+和{n,m}+。占有优先量词类似于标准匹配量词，但是匹配的结果不会“交还”或者说回溯。举例来说，当正则表达式a.*b和a.*+b同时去匹配字符串acccb时，a.*b会匹配成功，而a.*+b会匹配失败。原因是不管是.*还是.*+，它们都是匹配优先的，并且“贪婪”地匹配到了字符串acccb中的cccb, 但是.*+不会回溯已匹配到的结果，所以正则表达式 a.*+b 中的b会发现这时候字符串中已经没有b可以匹配，从而整个正则表达式匹配失败。占有优先量词能够控制匹配和不能匹配的内容，在某些场合下使用占有优先量词能够提高匹配效率。原子分组的概念类似于占有优先量词，例如，(?>\d+)的含义等价于\d++。

5．锚点和零宽断言

正则表达式中的锚点和零宽断言都不会匹配实际的字符，而是寻找和定位字符在文本中的位置，可以认为都是定位符，如表1.5所示。

表1.5　锚点和零宽断言

6．多选结构和嵌入条件

多选结构…|…能够在同一位置测试多个子表达式，每个子表达式被称为一个多选分支。在匹配时，整个多选结构被视为单个元素，只要其中某个子表达式能够匹配，整个多选结构的匹配就成功；如果所有子表达式都不能匹配，则整个多选结构匹配失败。

多选结构常常和嵌入条件一起使用，如表1.6所示。常用的嵌入条件形式是(?(ref)yes_exp|no_exp)，表示如果编号ref引用的捕获型分组存在，则匹配yes_exp，否则匹配no_exp。例如，上海地区固定电话号码一般写成021-12345678或者(021)12345678，可以用正则表达式(()?021(?(\1))|-)\d{8}来匹配这两种写法。其中(?(\1))|-)部分表示如果前面(()捕获到了匹配，那么继续匹配一个右括号)，否则匹配一个横线-。

表1.6　多选结构和嵌入条件

7．模式修饰符

除了常用的元字符以外，正则表达式也经常可以通过模式修饰符(?modifier)来设置匹配的模式，如表1.7所示。常见的模式modifier的值如下。

（1）i：表示忽略大小写的模式。

（2）s：表示点号通配模式，即点号可以匹配换行。

（3）m：表示多行模式，在这种模式下^、$、\A和\Z这些锚点符匹配的是行起始位置。

表1.7　模式修饰符

模式修饰符设置模式打开之后可以通过(?-modifier)来停用。此外，模式修饰符的作用范围局限于一个括号分组内。还有一种更简单的指定模式修饰符作用范围的方法是(?modifier:…)，表示其作用范围只在当前这个括号内有效。

1.2　正则表达式的流派与标准

前文提到，自从Ken Thompson将正则表达式引入qed编辑器之后，越来越多的UNIX操作系统或者类UNIX操作系统开始使用正则表达式，例如grep、egrep、lex、awk和sed等。不同的开发语言，例如C/C++、Java、Tcl、Python、Perl和PHP等也都包含了各自的正则表达式包。

但是，不同的工具和不同的开发语言在自身的发展过程中对正则表达式支持的元字符和这些元字符的意义的规定存在着较多的差异，导致形成众多正则表达式的流派。

不同流派之间的差异给正则表达式的发展和使用造成了一定程序的混乱，不同流派的整合和相关标准的制定成为一个必然的趋势。

1.2.1　PCRE简介

随着互联网的发展，文本和数据处理变得越来越重要。在众多的工具和开发语言发展过程中，Perl 5由于其强大、便捷的文本和数据处理能力广受欢迎，Perl支持的正则表达式也逐渐成为最重要的流派之一，越来越多的工具和开发语言开始支持兼容Perl正则表达式的语法。与此同时，PCRE也出现了。

PCRE是由Philip Hazel在1997年发布的一套兼容Perl正则表达式的库。PCRE的正则引擎质量很高，继承了Perl的正则表达式的语法和语义。开发者可以把PCRE整合到自己的工具和语言中，为用户提供丰富且极具表现力的各种正则功能。许多软件都使用了PCRE，例如PHP、Apache 2和Nmap等^[1]。

PCRE有两个主要的版本，当前版本是PCRE2，于2015年发布，最新版本号是10.35。而目前使用得最广泛的仍然是1997年发布的PCRE，当前版本号是8.44。

PCRE语法从严格意义上来说是正则表达式的一个流派，而不是正则表达式的一个标准，但是由于PCRE使用广泛和受欢迎程度高，开发者也常常把兼容PCRE语法称为符合PCRE标准。

1.2.2　POSIX标准

在Perl和PCRE发展时，电气与电子工程师学会（Institute of Electrical and Electronics Engineers，IEEE）也开始制定正则表达式的可移植操作系统接口（Portable Operating System Interface，POSIX）标准来规范不同的正则表达式流派。

1．BRE和ERE

正则表达式POSIX标准把正则表达式分成两大类：基本正则表达式（Basic Regular Expression，BRE）和扩展正则表达式（Extended Regular Expression，ERE），遵循POSIX标准的程序必须支持其中任意一种。BRE和ERE的主要区别如表1.8所示。

表1.8　BRE和ERE的主要区别

在传统的UNIX常用工具中，grep、vi和sed等都属于BRE流派，所以当它们使用像()、{}这样的元字符时，元字符前面必须要加转义符，而且BRE流派也不支持+、?量词，以及…|…多选结构。但是，今天纯粹的BRE已经很少见了，GNU对BRE做了扩展，使得BRE也能支持+、?量词，以及…|…多选结构，不过这些元字符前面都必须要加转义符变成+、\?、|。所以，GNU的grep等工具严格地说应该属于GNU BRE^[2]。

而在传统的UNIX常用工具中，egrep、grep –E和awk等就属于ERE流派。ERE名为扩展，但其并不是BRE的扩展，而是自成一体。ERE中元字符使用时前面无须加转义符，并且支持+和?量词，支持…|…多选结构。值得注意的是，POSIX ERE标准中并没有定义\x反向引用的实现。GNU同样对ERE做了扩展，使得ERE能够支持\x反向引用的功能。所以，GNU的egrep等工具严格地说属于GNU ERE^[2]。

其实从功能来看，GNU BRE和GNU ERE已经基本没有区别了。最大的不同就是GNU ERE元字符使用时前面不需要加转义符。

2．POSIX字符组　

在POSIX标准中，[a-z]和[^a-z]这样的字符组表示是合法的。但是POSIX标准还支持一种特别的字符组表示，类似于[[:alnum:]]和[[:alpha:]]，这其实是POSIX标准方括号表达式的一种特殊功能。POSIX方括号表达式与PCRE字符组[…]和[^…]最主要的区别在于，POSIX方括号表达式内部\不是用来转义的，所以在POSIX中[\d]匹配的是\和d两个字符。

POSIX字符组其实就是在POSIX方括号表达式内使用几种特殊元字符。值得注意的是，POSIX字符组表示的是当前语言环境下对应的字符，因此POSIX字符组详细的列表会根据当前语言环境的变化而变化。此外，这种特殊的元字符只有在方括号表达式内部才是有效的，所以使用完整的POSIX字符组时必须写成[[:alnum:]]。

表1.9列举了一些常见的POSIX字符组的元字符及其含义，这些元字符通常在不同的语言环境下都能支持^[1]。

表1.9　POSIX字符组的元字符及其含义

1.3　本章参考

[1]　Friedl E F．精通正则表达式[M]．3版．余晟，译．北京：电子工业出版社，2012．

[2]　余晟．正则指引[M]．2版．北京：电子工业出版社，2018．