一个由正则表达式引发的血案（解决版）

正则表达式一直以来是广大码农处理字符串的福音，但与此同时，也引发过血案。我们发表在ASE'18的论文“ReScue: Crafting Regular Expression DoS Attacks”[1]大幅改进了这类时间复杂性攻击的检测工具，并因此获得了ACM SIGSOFT Distinguished Paper Award。

正则表达式引发的血案

正则表达式

正则表达式（Regular Expressions）可以说是世界上最流行的字符串处理工具之一，它用一个字符串来表示一个字符串的 集合 ，例如 /ab+a/ 表示{ aba , abba , ...}，再加上各种语法特性和API，是处理字符串的神器之一。

比如程序员经常使用的字符串搜索工具 grep (最初作者是天才程序员、图灵奖获得者、UNIX的发明人之一Ken Thompson)，其实就是 ed 命令

grep

的别名（globally search regex and print），现在在vim中输入 :g/re/p 依然可以实现同样的功能。互联网上还流传着很多正则表达式的传说，例如以下正则表达式能判定一个字符串是否恰好由非素数个 1 组成：

/^1?$|^(11+)\1+$/

厉害了，上过《编译原理》、《形式语言与自动机》课的我竟然完全……看不懂？嗯，需要花点时间阅读一下经典教材《精通正则表达式》[2]。人生苦短，正则表达式（还有Python）能显著减少程序的长度、提高开发效率，有效延长了程序员的生命，也许还可以拯救你的发际线，呃，或者也许你能看懂这个正则表达式的时候已经是资深程序员了（逃

程序员资深水平等级图（来自网络）

血案（denny版）

当然，正则表达式也不是那么容易驾驭的。8102年的有一天，还在公司当弱弱的实习生、刚学会正则表达式的denny决定使用一个正则表达式来完成老大交待的Email地址验证需求：

• 老大的需求：验证 .com 结尾的Email地址
• denny的解读：一个字符串， 中间有个 @ ，前面可以有字母、数字、下划线、和点，后面可以有多个后缀，最后一个是 .com
• denny的实现： ^[a-zA-Z0-9._]+@([a-zA-Z0-9]+.)+com$ （其实有bug哦）
• denny觉得: 仿佛哪里不对 ，denny进行了测试：

PASS -- test@test.com (true)
PASS -- test@test.cn  (false)
... 此处省略一百个通过的弱智测试用例 ...
PASS -- test_163.163@test.163.test.com (false)
PASS -- test_163.163@test_163.test.com (false)# OK，很对，上线

• denny在小霸王服务器上进行了版本更新并部署:

commit 4040404040404 (origin/master, origin/HEAD)
Author: denny <denny.syj@hotmail.com>Date:   Mon Sep 25 17:00:00 2018 +0800加入正则表达式Email地址校验

• denny下班之后，小霸王服务器收到了一些奇怪的请求

power.overwhelming@aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
power.overwhelming@aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
power.overwhelming@aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
power.overwhelming@aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
power.overwhelming@aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
...

• 小霸王服务器感受到了巨大压力: CPU 100%

• 小霸王服务器在重压之下选择举手投降（Denial of Service）

正则表达式复杂度攻击

正如另一篇文章里指出的，写得不好的正则表达式可能会导致正则表达式引擎耗费大量的时间在 回溯 上，达到输入长度的 指数级 ！一个不太长的字符串（几十或几百），就能让正则引擎这辈子都跑不出匹配结果，从而导致拒绝服务攻击（Denial of Service），因为是正则表达式导致的，缩写成ReDoS。

而刚才denny写的正则表达式正是这样一个有 指数级最坏情况 例子：

js的正则引擎需要匹配丧心病狂的18秒

而这种出问题的正则表达式，很可能就被不知不觉部署到了生产环境中！

• 正则表达式可能已经通过了严格的测试。
• 在非恶意条件下构造的输入中，可能表现得非常好，例如匹配时间是线性的。

这些正则表达式流入了生产环境，自然就成了Denial of Service攻击的把柄，要是没有log，也许小霸王服务器被压垮都不知道是为什么呢！

正则表达式复杂度攻击：原理

为了支持现代正则表达式的各种神奇语法特性（例如 \1 、 (?:...) 等，刚才已经在判断素数的例子里见过部分特性了），《编译原理》课本上那种构造DFA，或者直接对NFA做dp的匹配方式已经不管用了[3]。概括地说，今天的正则引擎匹配正则表达式的算法就是 搜索 ：

1. 将正则表达式编译成一个有向图，和自动机类似，不妨称为NFA；
2. 在匹配时，维护一个NFA节点和匹配位置的 栈 ，经过一个NFA节点将引起一系列的入栈和出栈操作。

也许你已经反应过来了，栈即对应了回溯搜索的过程。例如在某一时刻面临两种选择（例如 expr1|expr2 ），那就在栈上先存两个节点，一个对应 expr1 ，另一个对应 expr2 ，等一条路径匹配失败返回出栈，就自动开始另一条路径的搜索。

嗯，有没有想起什么？你写过的各种回溯搜索（比如汉诺塔非递归版本）都是这样的套路嘛，这当然有一个指数级的最坏情况了。

正则表达式匹配：例子

以上面denny写的正则表达式 ^[a-zA-Z0-9._]+@([a-zA-Z0-9]+.)+com$ 为例子，当遇到输入 power.overwhelming@aaaa 时：

• 首先前段的 power.overwhelming@ 会顺利匹配正则表达式的前段 ^[a-zA-Z0-9._]+@ ；
• 然后括号内的 [a-zA-Z0-9]+ 会匹配后段所有的字符 aaaa ；
• 然后发现 . 匹配字符串结尾失败，回溯一位，让 [a-zA-Z0-9]+ 匹配 aaa ， . 匹配 a ；
  • 注意，其实denny在这里就已经写错了， 他应该将 . 转义 \. ，这个未转义的 . 也是导致后续回溯的原因之一。
• 最外层的 + 被成功匹配1次，接着 com 的 c 匹配字符串结尾失败，回溯一位， [a-zA-Z0-9]+ 匹配 aa ， . 匹配 a ；
• 最外层的 + 尝试匹配第2次， [a-zA-Z0-9]+ 匹配 a ， . 匹配字符串结尾失败，匹配第2次失败，于是让 c 尝试匹配倒数第二个 a ，匹配失败，回溯；
• [a-zA-Z0-9]+ 匹配 a 成功， . 匹配第2个 a 成功，最外层的 + 尝试重复第2次，经过一次回溯，顺利匹配第3个和第4个 a 成功，然后 c 匹配字符串结尾，匹配失败，再次回溯， [a-zA-Z0-9]+ 无法匹配空字符串，匹配失败，由于 ^ 的存在，不需要从头开始推进，直接返回 False 。

太长不看版

对于 @ 后面的每一个 a ，既可以出现在最外层的 + 的匹配中，也可以出现在内层的 + 的匹配中，也就是说，每一个 a 都存在2种不同的匹配可能，所以当匹配失败需要枚举所有匹配可能时，需要枚举

种可能（其中 n 代表 a 的个数）。

• 即假设每一种可能都能在常数时间里输出结果，那么总的匹配时间将跟 a 的个数（字符串长度）呈指数级关系。

我不识字版

ReDoS匹配视频模拟版，总之你看到它在不停的回溯（在状态机里绕圈圈）就对了！警告：洗脑背景音乐。

ReDoS的状态机模拟版 https://www.zhihu.com/video/1032983004821430272

自动构造正则表达式复杂度攻击字符串

现在进入我们工具的广告部分。说来我们论文里解决的问题也很简单：

给定一个正则 引擎 和一个 正则表达式 ，为这个正则表达式找到一个攻击 字符串 ，它可以最大化正则引擎的匹配时间。

如果这个问题得到解决，我们搞出这么个工具，程序员在写完正则表达式以后，直接把正则表达式拿到工具里跑跑看，如果工具返回一个匹配巨慢的ReDoS字符串，就不应该把它拿到线上去工作，真是省去了很多麻烦。实际上，我们的研究组有相当多此类工作，研究自动化的测试工具。

问题分析

既然问题的输入和输出都明确了，没啥搞不定的，不就是个最优化问题嘛！只要把所有长度为 的字符串都拿来试一试，找一个最慢的就好了。穷举是万能的，但也是万万不能的——如果碰上一个要匹配几百年的正则表达式，再这么搜索

的空间，真是麻烦大了。

另一方面，其实我们也已经有能搞定的算法了：拿点启发式搜索来瞎搞搞，凑个数，十有八九没问题——你猜对了！就是这么简单，我们就拿遗传算法发了篇论文（还不快来读博士？），还得了奖！而且这玩意还有一个高大上的名字：Search-Based Software Engineering [4]（SBSE，基于搜索的软件工程）！

那么怎么才能报考南京大学计算机软件研究所呢？欢迎骚扰软件所的各位老师和同学。

南京大学计算机软件研究所

简单，不简单

当然了，要做一个好的搜索算法也不是那么容易的。我们的确可以直接搬来一个遗传算法，让fitness function是字符串匹配的“性价比”：

然后让遗传算法帮我们找到所有字符串中性价比最高的那个，自然就是能够造成ReDoS攻击的字符串。很不幸的是——实际的正则表达式没那么简单。例如刚才让小霸王服务器垮掉的例子，它匹配的是一个Email地址。因此，如果不生成一个 @ 字符，匹配压根不会进行到后半部分，也不会触发超慢的回溯过程了。而如果刚好有一个字符串，它会引发复杂度问题但却又有很不错的“性价比”，整个种群很快就会充斥类似的字符串，从而导致整个遗传算法陷入局部最优解，错失找到真正问题的机会。

三阶段的检测方法（论文方法概括版）

到这里已经比较技术细节了，我们就上个图，具体的办法还请阅读我们的论文，大体思想是说，我们不仅要再遗传算法里考虑字符串的“性价比”，还需要考虑对正则引擎编译出来的NFA的状态覆盖；最后为了使算法在找到有潜力的攻击字符串后迅速找到实际的复杂度攻击，还利用Pumping Lemma [6]设计了一个快速得到有实际攻击价值字符串的方法。

三阶段的ReDoS检测方法示意图

以危险的正则表达式 (0|[0-1]){2,15}(hello)\2([0-9]+)+# 为例，首先经历的是“Seeding”阶段，生成若干种子字符串，完全不管性价比，只为了覆盖更多正则引擎的NFA的状态：例如 {"0", "00", "00hello", "00hellohello", "00hellohello0", "oohellohello0#", ...} ；有了这些好的种子，我们再做以“性价比”为导向的遗传算法(“Incubating”阶段)，同时保持种群中状态覆盖不降低，构造匹配较慢的字符串，例如 00hellohello00000000 。最后，在“Pumping”阶段将匹配较慢的字符串强化为效果拔群的ReDoS字符串，例如 00hellohello0000000000000000000000000000 。

代码实现参考传送门。我们的遗传算法需要理解正则表达式匹配的过程，因此我们对Java的正则引擎稍做了一些profiling的修改，能够在正则表达式匹配的同时生成matching trace。也正是因为用了这样白盒的算法，实验结果才能比已有的一些技术好那么一丢丢。

附上一些我们的工具在GitHub开源项目中发现的ReDoS问题：

• This regex may be stucked by input · Issue #141 · nhnent/tui.editor
• This regex may be stucked by input · Issue #3638 · ajaxorg/ace
• This regex may be stucked by input strings. · Issue #9731 · meteor/meteor
• Regex timeout · Issue #2020 · openstates/openstates

后记

我们关注到复杂度攻击这个问题，来自机缘巧合在Tim Roughgarden的Coursera课上提到了Crosby和Wallach在2003年USENIX Security上的论文 [7]，结果一句话凑出了一篇论文。当时正好桔子同学入学，就接了这个锅。我们一度想研究Hash Tables，但发现Java 8里的HashMap已经一劳永逸地解决了复杂度攻击问题（你读到这里几乎就可以猜到解决方案：在Hash Bucket超过某个大小时改用红黑树存储），几乎无路可做，又恰好发现正则表达式也是这么一个导致复杂度飙升的类型，顺水推舟就做下去了。匆忙之中完成了投稿，赶上ReDoS火起来（看到CCS'17的SlowFuzz [5]的时候我们都崩溃了），结果却是非常意外的得到了ACM SIGSOFT Distinguished Paper Award。

总之，欢迎大家加入我们的大家庭，一起做有趣的软件工程研究！

参考文献

[1] Shen, Yuju, Yanyan Jiang, Chang Xu, Ping Yu, Xiaoxing Ma, and Jian Lu. ReScue: crafting regular expression DoS attacks. ASE'18.

[2] Jeffrey E F Friedl. Mastering Regular Expressions: Understand Your Data and Be More Productive (3th ed.), 2006.

[3] Ken Thompson. 1968. Programming techniques: Regular expression search algorithm. Communications of the ACM 11(6), 419-422, 1968.

[4] Mark Harman and Bryan F Jones. Search-based software engineering. Information and Software Technology 43(14): 833-839, 2001.

[5] Theofilos Petsios, Jason Zhao, Angelos D Keromytis, and Suman Jana. Slowfuzz: Automated domain-independent detection of algorithmic complexity vulnerabilities. CCS'17.

[6] James Kirrage, Asiri Rathnayake, and Hayo Thielecke. Static analysis for regular expression denial-of-service attacks. NSS'13.

[7] Scott A Crosby and Dan S Wallach. Denial of service via algorithmic complexity attacks. USENIX Security'03.

作者简介 ：本文作者包括南京大学的硕士生沈宇桔、蒋炎岩博士、许畅教授、余萍副教授、马晓星教授和吕建教授。