大约九年前，Cloudflare是一家小公司，我是客户而不是员工。Cloudflare已经提前一个月发布了，有一天警报告诉我，我的小网站jgc.org似乎没有工作DNS了。Cloudflare已经推翻了对Protocol Buffers的使用的改变，并破坏了DNS。
我直接给马修·普林斯写了一封名为“我的dns在哪儿？”的电子邮件，他回复了一个详细的，技术性的回复（你可以在这里阅读完整的电子邮件交流），我回答说：
From: John Graham-Cumming
Date: Thu, Oct 7, 2010 at 9:14 AM
Subject: Re: Where's my dns?
To: Matthew Prince
Awesome report, thanks. I'll make sure to call you if there's a
problem. At some point it would probably be good to write this up as
a blog post when you have all the technical details because I think
people really appreciate openness and honesty about these things.
Especially if you couple it with charts showing your post launch
traffic increase.
I have pretty robust monitoring of my sites so I get an SMS when
anything fails. Monitoring shows I was down from 13:03:07 to
14:04:12. Tests are made every five minutes.
It was a blip that I'm sure you'll get past. But are you sure you
don't need someone in Europe? :-)
他回答说：
From: Matthew Prince
Date: Thu, Oct 7, 2010 at 9:57 AM
Subject: Re: Where's my dns?
To: John Graham-Cumming
Thanks. We've written back to everyone who wrote in. I'm headed in to
the office now and we'll put something on the blog or pin an official
post to the top of our bulletin board system. I agree 100%
transparency is best.
所以，今天，作为一个更大，更大的Cloudflare的员工，我会成为那个写作的人，透明地讲述我们犯下的错误，影响以及我们正在做的事情。
7月2日的事件
7月2日，我们在WAF托管规则中部署了一条新规则，导致CPU在每个处理全球Cloudflare网络上的HTTP / HTTPS流量的CPU核心上耗尽。我们不断改进WAF托管规则以应对新的漏洞和威胁。例如，在5月份，我们使用了更新WAF的速度来推动规则以防范严重的SharePoint漏洞。能够快速全局部署规则是我们WAF的一个重要特征。
不幸的是，上周二的更新包含了一个正常表达式，该表达式极大地回溯了用于HTTP / HTTPS服务的CPU耗尽。这降低了Cloudflare的核心代理，CDN和WAF功能。下图显示了专用于提供HTTP / HTTPS流量的CPU，这些CPU在我们网络中的服务器上使用率接近100％。
这导致我们的客户（及其客户）在访问任何Cloudflare域时看到502错误页面。502错误是由前线Cloudflare Web服务器生成的，这些服务器仍然具有可用的CPU核心但无法访问提供HTTP / HTTPS流量的进程。
我们知道这对我们的客户有多大伤害。它发生了我们感到羞愧。在我们处理这一事件时，它也对我们自己的运营产生了负面影响。
如果您是我们的客户之一，那一定是令人难以置信的压力，令人沮丧和可怕。更令人沮丧的是，因为我们六年没有全球停电。
CPU耗尽是由单个WAF规则引起的，该规则包含写得不好的正则表达式，最终导致过多的回溯。停电核心的正则表达式是(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))
虽然正则表达式本身对很多人很感兴趣（下面将对此进行详细讨论），但Cloudflare服务如何停止27分钟的真实故事要比“正则表达式变坏”复杂得多。我们花时间写出导致停电的一系列事件，并阻止我们快速响应。而且，如果您想了解有关正则表达式回溯的更多信息以及如何处理它，那么您可以在本文末尾的附录中找到它。
发生了什么
让我们从事件序列开始。本博客中的所有时间都是UTC。
在13:42，一名在防火墙团队工作的工程师通过自动过程对XSS检测规则进行了一些微小的改动。这生成了变更请求票证。我们使用Jira来管理这些票证，下面是截图。
三分钟后，第一个PagerDuty页面出现，表明WAF有问题。这是一个综合测试，它检查来自Cloudflare外部的WAF（我们有数百个这样的测试）的功能，以确保它正常工作。紧随其后的是页面，其中显示了Cloudflare服务失败的许多其他端到端测试，全球流量丢失警报，广泛的502错误，以及来自全球城市中我们的存在点（PoP）的许多报告，表明存在CPU疲惫。
当我们的解决方案工程部门的一位负责人告诉我，我们已经失去了80％的流量时，其中一些警报出现在我的手表上，我跳出了我所在的会议并回到了我的办公桌。我跑到SRE那里，团队正在调试情况。在停电的最初时刻，有人猜测这是我们以前从未见过的某种类型的攻击。
Cloudflare的SRE团队遍布全球，持续全天候覆盖。这些警报，其中绝大多数都注意到局部区域范围有限的非常具体的问题，在内部仪表板中进行监控，并且每天都要进行多次处理。然而，这种页面和警报模式表明发生了严重严重的事情，SRE立即宣布了P0事件，并升级为工程领导和系统工程。
当时伦敦工程团队正在我们的主要活动场所听取内部技术讲座。谈话被打断了，每个人都聚集在一个大型会议室，其他人拨打了电话。这不是SRE单独处理的正常问题，它需要每个相关团队立即联机。
在14:00，WAF被确定为导致问题的组件，并且攻击被视为可能。性能团队从一台清楚显示WAF负责的机器中提取了实时CPU数据。另一名团队成员使用strace确认。另一个团队看到了错误日志，表明WAF遇到了麻烦。在14:02时，当我们提议使用“全局杀戮”时，整个团队都在看着我，这是一种内置于Cloudflare中的机制，用于禁用全球的单个组件。
但是，进入全球WAF杀戮是另一回事。事情挡在了我们的路上。我们使用自己的产品和我们的Access服务，我们无法对我们的内部控制面板进行身份验证（一旦我们回来，我们发现团队中的某些成员因为安全功能而无法访问其凭据而失去了访问权限他们不经常使用内部控制面板）。
而且我们无法访问其他内部服务，如Jira或构建系统。为了得到它们，我们不得不使用一种不经常使用的旁路机制（在事件发生后继续钻研）。最终，一名团队成员在14:07执行了全球WAF杀戮，并且在14:09的流量水平和CPU回到了全球的预期水平。Cloudflare的其余保护机制继续运作。
然后我们继续恢复WAF功能。由于这种情况的敏感性，我们进行了两项负面测试（在问我们自己“是否真的引起问题的特定变化？”）以及在删除我们之后使用一部分流量在一个城市中进行积极测试（验证回滚是否有效）从该位置支付客户的流量。
在14:52，我们100％满意，我们了解原因并进行了修复，并在全球范围内重新启用了WAF。
Cloudflare如何运作
Cloudflare拥有一支工程师团队，负责我们的WAF管理规则产品; 他们不断致力于提高检测率，降低误报，并在新威胁出现时迅速做出反应。在过去的60天里，已经为WAF管理规则处理了476个变更请求（平均每3个小时一个）。
此特定更改将以“模拟”模式部署，其中真实客户流量通过规则但没有任何阻止。我们使用该模式来测试规则的有效性并测量其假阳性和假阴性率。但即使在模拟模式下，规则实际上也需要执行，在这种情况下，规则包含一个消耗过多CPU的正则表达式。
从上面的变更请求可以看出，有一个部署计划，一个回滚计划和一个指向此类部署的内部标准操作过程（SOP）的链接。规则更改的SOP特别允许全局推送。这与我们在Cloudflare发布的所有软件非常不同，SOF首先将软件推送到内部dogfooding网络存在点（PoP）（我们的员工通过），然后是隔离位置的少数客户，其次通过推动大量客户，最终走向世界。
软件版本的过程如下所示：我们通过BitBucket在内部使用git。致力于更改的工程师推送由TeamCity构建的代码，当构建通过时，将分配审阅者。一旦拉取请求被批准，代码就会生成，测试套件会再次运行。
如果构建和测试通过，则生成变更请求Jira，并且变更必须由相关经理或技术主管批准。一旦批准部署到我们称之为“动物PoP”的地方：DOG，PIG和Canaries。
DOG PoP是Cloudflare PoP（就像我们在全球任何一个城市一样）但它仅由Cloudflare员工使用。这种dogfooding PoP使我们能够在任何客户流量触及代码之前及早发现问题。它经常这样做。
如果DOG测试通过成功，代码将转到PIG（如“豚鼠”）。这是一个Cloudflare PoP，来自非付费客户的一小部分客户流量通过新代码。
如果成功，代码将移至加那利群岛。我们在世界各地有三个Canary PoP，并在新代码上运行支付和非付费客户流量作为最终检查错误。
一旦在Canary成功，代码就可以上线了。整个DOG，PIG，Canary，Global流程可能需要数小时或数天才能完成，具体取决于代码更改的类型。Cloudflare的网络和客户的多样性使我们能够在将版本推送给全球所有客户之前彻底测试代码。但是，根据设计，WAF不会使用此过程，因为需要快速响应威胁。
WAF威胁
在过去几年中，我们看到常见应用程序中的漏洞急剧增加。这是由于偶然的软件测试工具，提高了可用性，如模糊化，例如（我们刚刚张贴在模糊一个新的博客在这里）。
常见的是创建概念证明（PoC）并经常在Github上快速发布，以便运行和维护应用程序的团队可以进行测试以确保他们有足够的保护。因此，Cloudflare必须能够尽快对新的攻击做出反应，以便让我们的客户有机会修补他们的软件。
Cloudflare主动提供此类保护的一个很好的例子是在5月份部署我们针对SharePoint漏洞的保护措施（博客，此处）。在公布的公告的短时间内，我们看到了利用我们客户的Sharepoint安装的巨大飙升。我们的团队不断监控新威胁并编写规则以代表客户缓解这些威胁。
导致上周二中断的具体规则是针对跨站点脚本（XSS）攻击。近年来，这些也急剧增加。
WAF托管规则更改的标准过程表明，持续集成（CI）测试必须在全局部署之前通过。这通常发生在上周二，并且规则已经部署。在13:31，团队中的工程师在批准后合并了包含更改的Pull Request。
在13:37，TeamCity制定了规则并运行测试，让它成为绿灯。WAF测试套件测试WAF的核心功能，并包含大量单独匹配功能的单元测试。在单元测试运行之后，通过对WAF执行大量HTTP请求来测试各个WAF规则。这些HTTP请求旨在测试应该被WAF阻止的请求（以确保它能够捕获攻击）以及应该通过的请求（以确保它不会过度阻塞并产生误报）。它没有做的是测试WAF失控的CPU利用率，并检查以前的WAF版本中的日志文件，结果显示测试套件运行时间没有增加，最终导致CPU耗尽的规则。
测试通过后，TeamCity会在13:42自动开始部署更改。
水银
由于需要WAF规则来解决紧急威胁，因此使用我们的Quicksilver分布式键值（KV）存储来部署它们，这些存储可以在几秒钟内全局推送更改。在我们的仪表板中或通过API进行配置更改时，我们的所有客户都使用此技术，这是我们服务能够非常快速地响应变更的支柱。
我们还没有真正谈论过Quicksilver。我们以前使用Kyoto Tycoon作为全球分布式的键值商店，但我们遇到了运营问题并编写了我们自己的KV商店，这些商店在180多个城市中被复制。Quicksilver是我们如何推动客户配置更改，更新WAF规则以及使用Cloudflare Workers分发客户编写的JavaScript代码。
通过单击仪表板中的按钮或进行API调用以将配置更改为该更改生效需要几秒钟，全局。客户已经开始喜欢这种高速可配置性。而对于工人，他们期望近乎即时的全球软件部署。平均而言，Quicksilver每秒分发约350次更改。
而Quicksilver非常快。平均而言，我们达到了2.29的p99，以便将更改分发给全球的每台机器。通常，这种速度是一件好事。这意味着当您启用某项功能或清除缓存时，您知道它几乎可以立即在全球范围内直播。当您使用Cloudflare Workers推送代码时，它会以相同的速度推出。这是Cloudflare在您需要时快速更新的承诺的一部分。
但是，在这种情况下，这种速度意味着规则的变化在几秒钟内就会变得全球化。您可能会注意到WAF代码使用Lua。Cloudflare在生产中广泛使用Lua，之前已经讨论过WAF中Lua的细节。Lua WAF在内部使用PCRE，它使用回溯进行匹配，没有机制来防止失控的表达。更多关于这一点以及我们在下面做了些什么。
在部署规则之前发生的所有事情都是“正确”完成的：提出拉取请求，批准，CI / CD构建代码并对其进行测试，提交了一个带有SOP详细说明部署和回滚的变更请求，并且执行了部署。
什么地方出了错
如上所述，我们每周都会向WAF部署数十条新规则，并且我们有许多系统可以防止该部署产生任何负面影响。因此，当事情出错时，通常不会出现多种原因。在满足的同时找到一个根本原因可能会掩盖现实。以下是融合到Cloudflare的HTTP / HTTPS服务脱机的多个漏洞。
- 一位工程师写了一个很容易回溯的正则表达式。
- 在WAF周重构之前，错误地删除了一个有助于防止正规表达式过度使用CPU的保护 - 重构是使WAF使用更少CPU的一部分。
- 正在使用的正则表达式引擎没有复杂性保证。
- 测试套件没有办法识别过多的CPU消耗。
- SOP允许非紧急规则变更全球投入生产而无需分阶段推出。
- 回滚计划需要花费太长时间来运行完整的WAF构建两次。
- 全球交通量下降的第一个警报耗时太长。
- 我们没有足够快地更新我们的状态页面。
- 由于停电和旁路程序没有经过良好的培训，我们很难访问我们自己的系统。
- SRE失去了对某些系统的访问权限，因为出于安全考虑，他们的凭据已超时。
- 我们的客户无法访问Cloudflare Dashboard或API，因为他们通过Cloudflare边缘。
自上周二以来发生了什么事
首先，我们完全停止了对WAF的所有发布工作，并且正在执行以下操作：
- 重新引入已删除的过多CPU使用保护。（完成）
- 手动检查WAF托管规则中的所有3,868条规则，以查找并更正可能过度回溯的任何其他实例。（检查完成）
- 为测试套件引入所有规则的性能分析。（ETA：7月19日）
- 切换到re2或Rust正则表达式引擎，它们都具有运行时保证。（ETA：7月31日）
- 更改SOP以按照Cloudflare中其他软件使用的相同方式分阶段推出规则，同时保留为主动攻击执行紧急全局部署的能力。
- 实施紧急能力，使Cloudflare Dashboard和API脱离Cloudflare的优势。
- 自动更新Cloudflare Status页面。
从长远来看，我们正在远离几年前写的Lua WAF。我们正在移植WAF以使用新的防火墙引擎。这将使WAF更快，并增加另一层保护。
结论
这对我们的客户和团队来说是一个令人不安的中断。我们迅速做出反应以纠正这种情况，并正在纠正允许中断发生的流程缺陷，并通过更换所使用的基础技术来更深入地防止我们使用正则表达式的方式进一步可能出现的问题。
我们对停电感到羞耻，并对我们对客户的影响感到抱歉。我们相信我们所做的改变意味着这种停电永远不会再发生。
附录：关于正则表达式回溯
要完全了解(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*))) CPU耗尽的原因，您需要了解标准正则表达式引擎的工作原理。关键部分是.*(?:.*=.*)。的(?:和匹配)是一种非捕获基团（即，括号内的表达式被分组在一起作为单个表达）。
出于讨论为什么这种模式导致CPU耗尽的目的，我们可以安全地忽略它并将模式视为.*.*=.*。当减少到这个时，模式显然看起来不必要地复杂; 但重要的是任何“现实世界”表达（如我们的WAF规则中的复杂表达）要求引擎“匹配任何事物后跟任何东西”都可能导致灾难性的回溯。这就是原因。
在正则表达式中，.表示匹配单个字符，.*意味着贪婪地匹配零个或多个字符（即尽可能.*.*=.*匹配），因此意味着匹配零个或多个字符，然后匹配零个或多个字符，然后找到文字=符号，然后匹配零或更多字符。
考虑测试字符串x=x。这将匹配表达式.*.*=.*。所述.*.*前等于可以匹配第一x（的一个.*匹配的x，其他匹配零字符）。在.*之后的=冠军争夺战x。
这场比赛需要23步才能发生。第一次.*在.*.*=.*行动贪婪和整个匹配x=x的字符串。引擎继续考虑下一个.*。没有剩余的字符可供匹配，因此第二个.*匹配零个字符（允许）。然后引擎继续前进到=。由于没有匹配的字符（第一个.*消耗了所有字符x=x），匹配失败。
此时正则表达式引擎回溯。它返回到第一个.*并匹配x=（而不是x=x），然后移动到第二个.*。这.*匹配第二个x，现在没有更多的字符可供匹配。所以当引擎试图匹配=时.*.*=.*，匹配失败。发动机再次回溯。
这次它回溯，以便第一个.*仍然匹配，x=但第二个.*不再匹配x; 它匹配零个字符。然后引擎继续尝试=在.*.*=.*模式中找到文字，但它失败了（因为它已经与第一个匹配.*）。发动机再次回溯。
这次第一次.*匹配只是第一次x。但.*第二幕贪婪和匹配=x。你可以看到即将发生的事情。当它尝试匹配文字时，=它会失败并再次回溯。
第一个.*仍然匹配第一个x。现在第二.*场比赛就是=。但是，你猜对了，引擎无法匹配文字，=因为第二个.*匹配它。所以引擎再次回溯。请记住，这都是匹配三个字符的字符串。
最后，第一个.*匹配只是第一个x，第二个.*匹配零个字符，引擎能够=将表达式中的文字与=字符串中的文字匹配。它继续前进，决赛.*与决赛相匹配x。
匹配的23个步骤x=x。这是使用Perl Regexp :: Debugger的简短视频，显示了发生时的步骤和回溯。
这是很多工作，但如果字符串从更改x=x到会发生什么x=xx？这个时间需要33步才能匹配。如果输入是x=xxx45，那就不是线性的。下面是示出匹配的图表从x=x至x=xxxxxxxxxxxxxxxxxxxx（20 x后的=）。20 x秒后，=发动机需要555步才能匹配！（更糟糕的是，如果x=丢失了，那么字符串只有20 x秒，引擎将需要4,067步才能找到模式不匹配）。
此视频显示了匹配所需的所有回溯x=xxxxxxxxxxxxxxxxxxxx：
这很糟糕，因为随着输入大小的增加，匹配时间会超线性上升。但是，正则表达式略有不同，事情可能更糟。假设它已经存在.*.*=.*;（即模式结尾处有一个字面分号）。这很容易写成试图匹配表达式foo=bar;。
这次回溯本来就是灾难性的。要匹配x=x需要90步而不是23.步骤数增长得非常快。匹配x=后跟20 x秒需要5,353步。这是相应的图表。仔细查看Y轴值与前一个图表的比较。
要在这里完成的图片都是5353个步骤未能匹配的x=xxxxxxxxxxxxxxxxxxxx对.*.*=.*;
使用延迟匹配而不是贪婪匹配有助于控制在这种情况下发生的回溯量。如果原始表达式被更改为.*?.*?=.*?则匹配x=x需要11步（而不是23步），匹配也是如此x=xxxxxxxxxxxxxxxxxxxx。那是因为在?继续之前.*指示引擎首先匹配最小数量的字符。
但懒惰不是这种回溯行为的完全解决方案。将灾难性示例更改.*.*=.*;为.*?.*?=.*?;根本不会更改其运行时间。x=x仍然需要555步，x=然后20 x秒仍然需要5,353步。
唯一真正的解决方案是，不再完全重写模式更具体，是通过这种回溯机制摆脱正则表达式引擎。这是我们在未来几周内所做的事情。
自1968年Ken Thompson写了一篇题为“ 编程技巧：正则表达式搜索算法 ” 的论文以来，人们就已经知道了这个问题的解决方案。本文描述了一种机制，用于将正则表达式转换为NFA（非确定性有限自动机），然后使用一种算法在NFA中跟踪状态转换，该算法在时间上与所匹配的字符串的大小成线性关系。
Thompson的论文实际上没有讨论NFA，但是线性时间算法已经清楚地解释了，并且提出了一个为IBM 7094生成汇编语言代码的ALGOL-60程序。实施可能是神秘的，但它提出的想法不是。
这里是什么样.*.*=.*的正则表达式看起来当以类似的方式在汤普森的纸的照片图解等。
图0有五个从0开始的状态。有三个循环以状态1,2和3开始。这三个循环对应.*于正则表达式中的三个循环。带有圆点的三个含片符合一个字符。带有=标志的菱形与文字=符号相匹配。状态4是结束状态，如果达到则则正则表达式匹配。
要了解如何使用这种状态图来匹配正则表达式，.*.*=.*我们将检查匹配字符串x=x。程序从状态0开始，如图1所示。
使该算法工作的关键是状态机同时处于多个状态。NFA将同时进行每次转换。
它读取任何输入甚至之前，它立即转移到两个如图2状态1和2。
看图2，我们可以看到它x在第一次考虑时发生了什么x=x。所述x可以通过从状态1转变并返回到状态1匹配顶部圆点或x可以通过从状态2转换并且返回到状态2匹配它下面的点。
所以匹配后先x在x=x各州仍然1和2，这是不可能的，因为字面达到国家3或4 =所需要的迹象。
接下来算法考虑=in x=x。与x之前的情况非常相似，它可以通过从状态1转换到状态1或状态2转换到状态2的前两个循环中的任一个匹配，但另外文字=可以匹配并且算法可以将状态2转换到状态3（和立即声明4）。如图3所示。
接下来的算法达到最终x在x=x。从状态1和2开始，相同的转换可以返回到状态1和2.从状态3，x可以匹配右边的点并转换回状态3。
此时x=x已经考虑了每个字符，并且因为已到达状态4，正则表达式匹配该字符串。每个字符都被处理一次，因此算法在输入字符串的长度上是线性的。并且不需要回溯。
也可能很明显，一旦达到状态4（在x=匹配之后），正则表达式匹配并且算法可以在不考虑最终结果的情况下终止x。
该算法的输入大小是线性的。
