大约9年前，Cloudflare是一家小公司，但是我没有在其中工作，我只是一个客户。 在启动Cloudflare之后一个月，我收到了一条通知，说jgc.org 网站上的DNS似乎不起作用。 Cloudflare对协议缓冲区进行了更改，并且DNS损坏。
我立即写信给马修·普林斯（Matthew Prince），标题为“我的DNS在哪里？”，他发送了一个很长的答案，其中包含技术细节（ 请在此处阅读所有信函 ），我回答：
来自：约翰·格雷厄姆·卡明
日期：2010年10月7日9:14
主题：Re：我的DNS在哪里？
至：马修·普林斯
很酷的报告，谢谢。 如果有问题，我一定会打电话。 收集所有技术信息后，可能值得写一篇有关此的文章。 我认为人们会喜欢一个开放而诚实的故事。 特别是如果您在上面附加图形以显示启动后流量如何增长。
我在网站上进行了良好的监控，并且收到有关每个失败的SMS。 监视显示故障是从13:03:07到14:04:12。 每五分钟进行一次测试。
我相信您会弄清楚的。 您在欧洲绝对不需要自己的人吗？ :-)
他回答：
来自：马修·普林斯
日期：2010年10月7日，9：57
主题：Re：我的DNS在哪里？
致：约翰·格雷厄姆·卡明（John Graham Cumming）
谢谢啦 我们回答了所有写信的人。 我现在要去办公室，我们将在博客上写点东西或在公告板上发布正式帖子。 我完全同意，诚实是我们的一切。
现在Cloudflare是一个非常大的公司，我在其中工作，现在我必须公开地写关于我们的错误，其后果和我们的行动。
7月2日活动
7月2日，我们在WAF的托管规则中部署了一条新规则，由于该规则会在处理Cloudflare网络上的HTTP / HTTPS流量的每个处理器核心上耗尽处理器资源 。 我们不断改进WAF的托管规则，以应对新的漏洞和威胁。 例如，在5月，我们急着添加一条规则来保护自己免受SharePoint中的严重漏洞的侵害。 我们WAF的重点在于能够快速，全局地部署规则。
不幸的是，上周四的更新包含一个正则表达式，该正则表达式在回溯上花费了过多的处理器资源专用于HTTP / HTTPS。 这影响了我们的核心代理，CDN和WAF功能。 该图显示，在我们网络中的服务器上，用于服务HTTP / HTTPS流量的处理器资源几乎达到100％。
在事件发生时在存在点之一使用处理器资源
结果，我们的客户（以及我们客户的客户）在Cloudflare域中遇到了502错误的页面。 Cloudflare前端Web服务器生成了502个错误，这些前端Web服务器仍然具有免费的内核，但是它们无法与处理HTTP / HTTPS流量的进程进行通信。
我们知道这给我们的客户带来了多少不便。 我们非常as愧。 这种失败使我们无法有效地处理这一事件。
如果您是这些客户之一，它可能会让您感到恐惧，愤怒和不安。 此外，我们已经6年没有发生全球性故障了。 CPU使用率高是由于一个WAF规则的正则表达式编写得不好，导致过多的回溯。 这是有罪的表达式： (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))
尽管它本身很有趣（我将在下面向您详细介绍），但Cloudflare服务被切断了27分钟，这不仅是因为不适合使用正则表达式。 我们花了一些时间描述导致失败的事件的顺序，因此我们没有迅速做出响应。 在文章的结尾，我将以正则表达式描述回溯并告诉您如何做。
发生什么事了
让我们按顺序开始。 所有时间都以UTC表示。
在13:42，防火墙团队的工程师对使用自动过程检测XSS的规则进行了少量更改。 因此，创建了变更请求票证。 我们通过吉拉（以下屏幕截图）管理这些票证。
3分钟后，出现第一个PagerDuty页面，报告WAF问题。 这是一项综合测试，用于检查Cloudflare之外的WAF（我们有数百个）功能，以监视正常运行。 然后立即有页面通知Cloudflare服务的其他端到端测试失败，全球流量问题，广泛的502错误以及来自我们在世界各地城市的服务点（PoP）发出的大量报告，这些信息表明处理器资源不足。
当我的解决方案开发部门负责人说我们丢失了80％的流量时，我收到了几条这样的通知，从会议上摔下来，已经走到桌子旁。 我遇到了已经在解决此问题的SRE工程师。 最初，我们认为这是某种未知的攻击。
Cloudflare SRE工程师遍布世界各地，并全天候监控情况。 通常，此类警报会通知您有限范围内的特定本地问题，在内部仪表板上进行监视，并且每天会被解决多次。 但是这样的页面和通知表明确实很严重，SRE工程师立即宣布了P0严重性级别，并求助于管理和系统工程师。
那时我们的伦敦工程师正在大厅听演讲。 演讲必须中断，每个人都聚集在一个大会议室中，并邀请了更多的专家。 这不是SRE可以自行解决的常见问题。 迫切需要联系合适的专家。
在14:00，我们确定WAF存在问题，并且没有攻击。 绩效部门检索了处理器数据，很明显是WAF的罪魁祸首。 另一位合作者通过strace证实了这一理论。 有人在日志中看到了WAF的问题。 在14:02时，当有人提议使用全局kill时，整个团队都来找我-一种内置于Cloudflare中的机制，该机制禁用了全世界的一个组件。
我们如何对WAF进行全球杀戮是另外一回事。 这不是那么简单。 我们使用自己的产品，并且由于Access服务无法正常工作，因此我们无法进行身份验证并进入内部控制面板（修复所有内容后，我们得知该团队的某些成员由于安全功能而失去了访问权限，如果在（请勿长时间使用内部控制面板）。
而且我们无法获得内部服务，例如Jira或构建系统。 我们需要一个不常用的解决方法（这也需要解决）。 最终，一名工程师能够在14:07切断WAF，并在14:09处的流量和处理器水平恢复正常。 Cloudflare的其余防御机制按预期工作。
然后，我们着手恢复WAF。 这种情况与众不同，因此我们在一个城市中使用单独的流量进行了负面测试（询问问题是否确实是这种变化）和正面（确保回滚有效），从那里转移了付费客户。
下午2时52分，我们确信我们已了解原因并进行了更正，然后再次打开WAF。
Cloudflare如何运作
Cloudflare拥有一支工程师团队，负责管理WAF的托管规则。 他们试图提高检测率，减少误报的数量，并在出现新威胁时迅速做出反应。 在过去60天内，已处理476项针对WAF托管规则的变更请求（平均每3个小时提出一次）。
需要在仿真模式下部署此特定更改，在该模式下，实际的客户端流量会通过规则，但不会阻塞任何内容。 我们使用这种模式来检查规则的有效性，并衡量假阳性和假阴性结果的比例。 但是，即使在仿真模式下，规则也必须实际执行，在这种情况下，规则包含正则表达式会消耗过多的处理器资源。
从上面的更改请求中可以看出，我们有一个部署计划，一个回滚计划，以及指向这种部署类型的内部标准操作过程（SOP）的链接。 更改规则的SOP允许您在全局范围内发布它。 实际上，在Cloudflare中，一切安排都完全不同，SOP要求首先将用于测试和内部使用的软件发送到内部存在点（PoP）（供我们的员工使用），然后发送给孤立地点的少量客户，然后再发送给大量客户，然后全世界
这是它的外观。 我们通过BitBucket在内部系统中使用git。 变更工程师将他们生成的代码发送给TeamCity，并在生成通过时分配审阅者。 池请求获得批准后，将收集代码并再次进行一系列测试。
如果组装和测试成功，那么将在Jira中创建更改请求，并且更改必须由适当的主管或首席专家批准。 批准后，将部署到所谓的“ PoP监狱”：DOG，PIG和Canary （狗，腮腺炎和金丝雀）。
DOG PoP是Cloudflare PoP（就像我们其他城市一样），仅Cloudflare员工使用。 内部使用的PoP使您甚至可以在解决方案开始接收客户流量之前发现问题。 有用的东西。
如果DOG测试成功，则代码进入PIG阶段（豚鼠）。 这是Cloudflare PoP，其中少量免费客户端流量通过新代码流动。
如果一切顺利，代码将转到Canary。 我们在世界不同地区拥有三个Canary PoP。 付费和免费客户的流量通过其中的新代码传递，这是最后的错误检查。
Cloudflare软件发布流程
如果该代码在Canary中还可以，我们将其释放。 经历所有阶段-DOG，PIG，Canary和整个世界-花费数小时或数天，具体取决于代码更改。 由于Cloudflare的网络和客户的多样性，我们在对所有客户进行全球发布之前都对代码进行了全面的测试。 但是WAF并没有特别遵循此过程，因为需要快速响应威胁。
威胁WAF
在过去的几年中，常规应用中存在着明显更多的威胁。 这是由于软件测试工具的可用性更高。 例如，我们最近撰写了有关fuzzing的文章 。
资料来源： https : //cvedetails.com/
通常，会创建该概念的确认并立即在Github上发布，以便为应用程序提供服务的团队可以对其进行快速测试，并确保对其进行了充分的保护。 因此，Cloudflare需要能够尽快响应新攻击的能力，以便客户有机会修复其软件。
Cloudflare快速响应的一个很好的例子是5月份部署SharePoint漏洞保护（请参阅此处 ）。 广告发布后几乎立即，我们注意到进行了大量尝试来利用客户端的SharePoint安装中的漏洞。 我们的员工不断监视新的威胁并编写规则以保护我们的客户。
导致星期四发生此问题的规则是防止跨站点脚本（XSS）。 近年来也有更多此类攻击。
资料来源： https : //cvedetails.com/
修改WAF托管规则的标准过程需要在全局部署之前进行连续集成测试（CI）。 上周四，我们做到了，并扩大了规则。 在13:31，一位工程师发送了批准的池请求并进行了更改。
在13：37，TeamCity收集了规则，进行了测试并批准了。 WAF测试套件测试WAF核心功能，并且包含针对单个功能的大量单元测试。 经过单元测试后，我们使用大量HTTP请求检查了WAF规则。 HTTP请求检查哪些请求应被WAF阻止（以拦截攻击），哪些请求可以被跳过（以不阻止所有请求并避免误报）。 但是我们没有进行过多使用处理器资源的测试，研究以前的WAF程序集的日志表明，使用该规则的测试执行时间没有增加，并且很难怀疑没有足够的资源。
测试通过了，TeamCity在13:42开始自动部署更改。
水银
WAF规则解决了紧急消除威胁的问题，因此我们使用分布式键值对Quicksilver对其进行部署，Quicksilver可以在几秒钟内在全球范围内分布更改。 我们所有的客户在更改仪表板上或通过API的配置时都使用该技术，这正是由于有了它，我们才能以闪电般的速度响应更改。
我们讨论了一些关于Quicksilver的问题。 我们曾经将Kyoto Tycoon用作键值对的全球分布式存储库，但是它存在操作问题，并且我们编写了在180多个城市中复制的存储库。 现在，借助Quicksilver，我们可以发送客户端配置更改，更新WAF规则并分发由Cloudflare Workers中的客户端编写的JavaScript代码。
从仪表板上的按钮或调用API到进行配置更改，配置只需几秒钟即可遍历世界。 客户喜欢这种速度设置。 而且，Workers为他们提供了几乎即时的全局软件部署。 平均而言，Quicksilver每秒分发约350次更改。
而且Quicksilver的速度非常快。 平均而言，我们将2.29秒的百分位数提高到了世界各地的每台计算机。 通常速度不错。 毕竟，当您打开一个功能或清除缓存时，它几乎立即发生在任何地方。 通过Cloudflare Workers发送代码的速度相同。 Cloudflare承诺在适当的时间为其客户提供快速更新。
但是在这种情况下，速度对我们起到了欺骗作用，规则在几秒钟之内到处改变。 您可能已经注意到WAF代码使用Lua。 Cloudflare在生产环境中广泛使用Lua，我们已经 在WAF中 讨论了 Lua 的细节。 Lua WAF在内部使用PCRE，并应用回溯进行匹配。 它没有针对失控的表达式的防御机制。 在下文中，我将详细讨论这一点以及我们正在做什么。
在部署规则之前，一切都进行得很顺利：创建并批准了池请求，CI / CD管道编译并测试了代码，根据SOP发送了更改请求，该请求对部署和回滚进行了规范，并完成了部署。
CloudFare WAF部署流程
出了什么问题
正如我之前所说，我们每周都会部署数十个新的WAF规则，并且我们有许多保护系统可以防止此类部署带来的负面影响。 当出现问题时，通常是几种情况的组合。 如果仅找到一个原因，那么这当然可以使人平静，但并非总是如此。 这是共同导致我们的HTTP / HTTPS服务失败的原因。
- 工程师写了一个正则表达式，可能导致过多的回溯 。
- 在WAF重构之前几周，错误地删除了一个可以防止正则表达式占用过多处理器资源的工具-需要进行重构，以减少WAF消耗的资源。
- 正则表达式引擎不能保证复杂性。
- 测试套件无法显示过多的CPU消耗。
- SOP程序无需进行多步骤，即可在全球范围内部署非紧急规则更改。
- 回滚计划需要两次完整的WAF组装，这花费了很长时间。
- 第一个全局交通警报警报工作太迟了。
- 我们延迟了状态页面的更新。
- 由于崩溃，我们在访问系统时遇到了问题，并且解决方法还不够完善。
- SRE工程师无法访问某些系统，因为其凭据出于安全原因已过期。
- 我们的客户无法访问Cloudflare仪表板或API，因为他们要经过Cloudflare区域。
自上周四以来发生了什么变化
首先，我们完全停止了WAF发行版的所有工作，并执行以下操作：
- 重新引入针对我们删除的过多处理器资源的保护。 （完成）
- 手动检查WAF托管规则中的所有3868条规则，以发现并修复其他潜在的过度回溯的情况。 （验证完成）
- 我们在测试套件中包括对所有规则的性能分析。 （预计：7月19日）
- 我们切换到re2或Rust regex引擎-两者都在运行时提供了保证。 （预计：7月31日）
- 像Cloudflare中的其他软件一样，我们重写SOP以便分阶段部署规则，但同时，如果攻击已经开始，则可以紧急全局部署。
- 我们正在开发从Cloudflare区域紧急撤出Cloudflare仪表板和API的可能性。
- 我们正在自动更新Cloudflare状态页面。
从长远来看，我们将放弃我几年前写的Lua WAF。 我们将WAF迁移到新的防火墙系统 。 因此，WAF将更快，并获得额外的保护级别。
结论
此故障给我们和我们的客户带来麻烦。 我们迅速做出反应以纠正这种情况，现在我们正在研究导致失败的流程中的缺陷，并且我们正在进行更深的挖掘，以期将来通过使用新技术来保护自己免受正则表达式的潜在问题的影响。
我们为这次失败感到羞耻，并向客户表示歉意。 我们希望这些更改确保不会再次发生这种情况。
应用程序。 正则表达式回溯
要了解表达方式：
(?:(?:\"|'|\]|\}|\\|\d (?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\- |\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))
吞噬了所有处理器资源，您需要对标准正则表达式引擎的工作原理有所了解。 这里的问题是模式.*(?:.*=.*) 。 (?:和对应的一个)不是一个令人兴奋的组（也就是说，括号中的表达式被分组为一个表达式）。
在处理器资源过度消耗的情况下，此模式可以指定为.*.*=.* 。 因此，该模式看起来不必要地复杂。 但更重要的是，在现实世界中，要求引擎先匹配一个片段然后再匹配另一个片段的此类表达式（类似于WAF规则中的复杂表达式）可能会导致灾难性的回溯。 这就是为什么。
正则表达式中. 表示您需要匹配一个字符， .* -“贪婪地”匹配零个或多个字符，即捕获最多的字符，因此.*.*=.*表示匹配零个或多个字符，然后匹配零个或多个字符，查找文字字符=，匹配零个或多个字符。
取测试线x=x 。 它与表达式.*.*=.*. .*.*相匹配.*.*=.*. .*.* .*.*=.*. .*.*最多等号对应于第一个x （组中的一个.*对应于x ，第二个对应于零字符）。 .*之后=与最后一个x匹配。
为了进行这种比较，需要23个步骤。 第一组.* .*.*=.* “贪婪地”操作并匹配整行x=x 。 引擎移至下一组。 我们不再有要匹配的字符，因此第二组.*匹配零个字符（允许）。 然后，引擎转到=符号。 没有更多的字符（第一组.*使用整个表达式x=x ），不会发生匹配。
这里，正则表达式引擎返回到开头。 他进入第一组.*并将其 x= （而不是x=x ）进行比较，然后进行第二组.* 。 第二组.*映射到第二个x ，我们再也没有字符了。 当引擎达到= v .*.*=.* ，什么也没有发生。 然后他再次回溯。
这次，组.*仍与x=匹配，但第二组.*不再是x ，而是零个字符。 引擎尝试在模式.*.*=.*找到文字符号= ，但不会退出（毕竟，第一组已经占据了它.* 。）。 然后他再次回溯。
这次是第一个组.*仅取第一个x。 但是第二组.* “贪婪”捕获=x 。 已经猜测会发生什么？ 引擎尝试匹配文字= ，失败并进行下一个回溯。
.* x . .* = . , = , .* . . !
.* x , .* — , = = . .* x .
23 x=x . Perl Regexp::Debugger , , .
, x=x x=xx ? 33 . x=xxx ? 45. . x=x x=xxxxxxxxxxxxxxxxxxxx (20 x = ). 20 x = , 555 ! ( , x= 20 x , 4067 , , ).
x=xxxxxxxxxxxxxxxxxxxx :
, . , . , .*.*=.* ; ( ). , , foo=bar; 。
. x=x 90 , 23. . x= 20 x , 5353 . . Y .
, 5353 x=xxxxxxxxxxxxxxxxxxxx .*.*=.*;
«», «» , . .*?.*?=.*? , x=x 11 ( 23). x=xxxxxxxxxxxxxxxxxxxx . , ? .* , .
«» . .*.*=.*; .*?.*?=.*?; , . x=x 555 , x= 20 x — 5353.
, ( ) — . .
1968 , Programming Techniques: Regular expression search algorithm (« : »). , , , .
(Ken Thompson)
Bell Telephone Laboratories, Inc., -, -
. IBM 7094 . , . , .
, .
. . — .
. , . , .
, IBM 7094.
. — , . «·» . . . 2 , .
, ALGOL-60, IBM 7094. , .
. ⊕ .
1 . — a, b, c, S[i] NNODE.
NNODE , (. . 5)
.*.*=.* , , .
. 0 , 0, 3 , 1, 2 3. .* . 3 . = = . 4 . , .
, .*.*=.* , x=x . 0, . 1。
, . .
, (1 2), . 2。
. 2 , , x x=x . x , 1 1. x , 2 2.
x x=x - 1 2. 3 4, = .
= 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 .
.