如果你尝试用正则表达式解决一个问题,那么恭喜,现在你有两个问题了。

起源

今年 7 月 2 日,Cloudflare 发生了一次大规模的宕机,许多使用了 Cloudflare 服务的网站出现 502 错误,持续了大约半小时。

安纳金带领的 501 军团

501

本次受影响网站出现的 502 页面

502Page

宕机的元凶是 @带带大师兄 Cloudflare 在测试的一个新添加到 WAF 规则集中的正则表达式,它极容易产生回溯,不巧 Cloudflare WAF 的 CPU 使用保护机制失效,导致在测试时正则表达式引擎消耗了大量计算资源,几乎榨干了了负责处理 HTTP/HTTPS 流量的 CPU。


正则表达式的回溯

什么是正则表达式的回溯?正则表达式的回溯有什么用?怎么才能让正则表达式发生回溯?正则表达式的回溯为什么会耗尽 CPU 资源?小编今天来解答一下大家有关正则表达式的回溯的困惑。

这是导致这次宕机的正则表达式:

1
(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

先别急着关掉网页,尽管它看起来非常长,我们需要关注的仅是其中的一小段关键部分:

1
.*(?:.*=.*)

(?:)表示它们中间是一个非捕获组,意思是两个括号间的内容需要匹配,但在匹配之后会被扔掉。由于我们关注的是匹配的过程,此处的(?:)也可以被忽略,最终化简后的表达式是

1
.*.*=.*

它从表面看上去非常简单,.表示匹配一个任意字符,.*即表示匹配零个或多个任意字符。因此上述表达式先匹配零个到多个任意字符,然后又匹配零个到多个任意字符,再匹配一个等于符号=,最后再匹配零个到多个任意字符。如下图所示。


NFA


这个看似人畜无害的正则表达式,又是如何走向吃尽计算资源的深渊的呢?


贪婪匹配

正则表达式默认使用贪婪匹配原则匹配字符串,也就是说,.*会尽可能多地匹配字符。

我们以字符串x=x为例。

第一次尝试时,为首的.*会匹配整个x=x,接着第二个.*只能匹配零个字符。而到了匹配=时,由于剩余的字符串已经空了,它找不到那个对应的=,匹配失败。

此时正则表达式引擎开始回溯,进行第二次尝试。第一个.*现在仅匹配字符串中的前两个字符x=,第二个贪婪的.*将剩下的x匹配掉了,=仍然只能面对一个空字符串,匹配失败。

现在两个.*依次匹配了x=x,引擎会选择后者进行回溯,那么第三次尝试,前一个.*匹配x=,后一个.*匹配零个字符,留给=的,只剩一个x,匹配又失败了。

第四次尝试,.*只匹配x,然而后一个贪婪的.*又把=x吃掉了,=还是只能面对一个空字符串。匹配失败。

按照同样的原理,又经历了两轮回溯之后,终于前一.*只匹配x,后一.*匹配零个字符串,=才得以匹配成功,最后一个.*匹配末尾的x,整个正则表达式匹配完成。

全部过程由下图表示。

backtracks

仅一个包含三个字符的字符串,就要进行 5 次回溯,共 23 步的匹配过程,同时显然,匹配步骤的数量是随等号后的字符数量呈指数级上升的,当匹配x=xx时,需要 33 步,匹配x=xxxxxxxxxxxxxxxxxxxx需要 555 步。

你可以到 Perl Regexp::Debugger 直观地查看正则表达式引擎如何回溯。下图展示了x=x的匹配过程。

backtracking steps

来源:Cloudflare


懒惰匹配

懒惰匹配能在一定程度上解决上述问题。与贪婪匹配正好相反,懒惰匹配原则会尽量匹配更少的字符,下图直观展示了贪婪匹配与懒惰匹配两种策略下,正则表达式.*b.*匹配字符串ababa的区别。

difference between greedy and lazy


要在默认使用贪婪匹配的引擎中声明使用懒惰匹配原则,只需要将.*替换为.*?。声明使用懒惰匹配原则后,.*?.*?=.*?匹配字符串x=x从 23 步减少到了 11 步,与匹配x=xxxxxxxxxxxxxxxxxxxx一致。


尽管懒惰匹配原则能够解决此次导致 Cloudflare 宕机的这个特定形式的正则表达式,但其仍然存在潜在的回溯问题。

如果我们将正则表达式末尾添加一个分号,改写为.*.*=.*;,或申明懒惰匹配的写法.*?.*?=.*?;,两者在处理匹配失败的字符串时所需要的步数是相同的,如x=x都需要耗费 90 步才能知道匹配失败,而x=后面有 20 个 x时,从原来 555 步增加到了惊人的 5353 步。

下图展示了引擎是如何走了 5353 步才发现x=xxxxxxxxxxxxxxxxxxxx匹配失败的。

backtracking steps

来源:Cloudflare


真正的解决方法

通过改写正则表达式本身消除回溯的方法并不能一劳永逸地解决问题,由于正则表达式本身可读性差,无法指望人工完全消除隐含的回溯。尽管存在相应检测工具,但其一般靠随机数据暴力穷举,费时费力。要完全消除回溯带来的性能问题需要从正则表达式引擎本身入手。

好在 1968 年,Ken Thompson 发表的一篇论文 Programming Techniques: Regular expression search algorithm 提出了解决办法。这篇论文阐述了一种将正则表达式转换为非确定性有穷自动机(NFA)的方法,然后根据在 NFA 中状态的转换,实现正则表达式的匹配。即使是带有回溯的正则表达式的匹配过程,这种算法的时间复杂度与字符串长度也仅呈线性关系。

下面仍以.*.*=.*匹配x=x为例。

先在每一个符号之间添加一个状态,匹配的过程就是状态之间的转移,画出 NFA 如下:

NFA01


状态 0 为初始状态,状态 4 为结束状态(接受状态)。若状态 m 和 n 之间存在没有符号的有向线段,则称它们之间存在 ε 转换,表示状态 m 无需任何输入即可转移到状态 n。那么对于正则表达式.*.*=.*的 NFA,一开始所处的状态可以是 0, 1 和 2:

NFA02


现在考虑输入的第一个字符x,读取x后,状态 0 能转移到状态 1,状态 1 能转移到状态 2,由于状态 2 到 3 需要一个=,无法完成转移,那么,转移后的状态就是 1 和 2。又因为状态 1 和 2 到状态 0 都存在 ε 转换,因此,读取了字符x后的状态仍然是 0, 1 和 2:

NFA02


现在考虑接下来的等号=,同理,状态 0 和 1 分别转移到状态 1 和 2,而状态 2 读取了=可以转移到状态 3,又由于状态 1, 2 到状态 0、状态 3 到状态 4 都有 ε 转换,因此,读取了字符=后的状态是 0, 1, 2, 3 和 4:

NFA03


末位的字符x的读取过程不再赘述,当所有字符读取完毕,可达的状态有 0, 1, 2, 3 和 4,其中包含了接受状态 4,即正则表达式能够成功匹配该字符串。

利用 NFA 来匹配x=x,过程中没有回溯,每个字符仅被处理了一遍,因此匹配所耗费的时间是与字符数量线性相关的。将正则表达式引擎改为此方法来匹配字符串,就可以避免因回溯带来的大量资源消耗,不重蹈 Cloudflare 的覆辙。



原文来自 Details of the Cloudflare outage on July 2, 2019 - Appendix: About Regular Expression Backtracking,有改动。

本文适用 CC BY-NC-SA 4.0 协议。