大约 9 年前，Cloudflare 还是一家小公司，我没有为它工作，我只是一个客户。 启动 Cloudflare 一个月后，我收到一条通知，我的网站 DNS 似乎不起作用。 Cloudflare 已更改为 ，并且 DNS 损坏。
我立即写信给 Matthew Prince，标题是“我的 DNS 在哪里？”，他发回了一份充满技术细节的长回复（），对此我的回复是：
作者：约翰·格雷厄姆-卡明
日期：7年2010月9日 14:XNUMX
主题：回复：我的 DNS 在哪里？
致：马修·普林斯很酷的报告，谢谢。 如果有问题我一定会打电话。 一旦您收集了所有技术信息，可能值得写一篇关于此的文章。 我认为人们会喜欢一个开放而诚实的故事。 特别是如果您附上图表来显示自发布以来流量的增长情况。
我的网站有良好的监控，每次失败我都会收到一条短信。 监控显示故障发生时间为13:03:07至14:04:12。 每五分钟进行一次测试。
我相信你会明白的。 您确定您在欧洲不需要自己的人吗？ 🙂
他回答：
作者：马修·普林斯
日期：7年2010月9日 57:XNUMX
主题：回复：我的 DNS 在哪里？
致：约翰·格雷厄姆-卡明谢谢。 我们回复了所有来信的人。 我现在正在去办公室的路上，我们将在博客上写一些东西，或者在我们的公告板上钉上官方帖子。 我完全同意，诚实就是一切。
现在 Cloudflare 是一家非常大的公司，我为它工作，现在我必须公开写下我们的错误、其后果和我们的行动。
2 月 XNUMX 日活动
2 月 XNUMX 日，我们在 WAF 托管规则中推出了一项新规则，因此 在全球 Cloudflare 网络上处理 HTTP/HTTPS 流量的每个处理器核心上。 我们不断改进 WAF 的托管规则，以应对新的漏洞和威胁。 以五月为例，我们匆匆忙忙 以防范 SharePoint 中的严重漏洞。 我们 WAF 的重点是能够在全球范围内快速部署规则。
不幸的是，上周四的更新包含一个正则表达式，在回溯上浪费了太多的 HTTP/HTTPS CPU 资源。 我们的核心代理、CDN 和 WAF 功能因此受到影响。 该图显示，我们网络中的服务器上用于服务 HTTP/HTTPS 流量的处理器资源几乎达到 100%。
事件期间某一地点的 CPU 使用率
因此，我们的客户（以及我们客户的客户）最终在 Cloudflare 域上出现 502 错误页面。 502 错误是由 Cloudflare 前端 Web 服务器生成的，这些服务器仍然具有可用核心，但无法与处理 HTTP/HTTPS 流量的进程进行通信。
我们知道这给我们的客户带来了多少不便。 我们感到非常羞愧。 而这次失败让我们无法有效处理该事件。
如果您是这些顾客之一，您可能会感到害怕、愤怒和不安。 此外，我们还没有 。 CPU 消耗过高是由于一项 WAF 规则使用了措辞不当的正则表达式，导致过度回溯。 愧疚的表情是这样的： (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
虽然这本身就很有趣（我将在下面更详细地讨论它），但 Cloudflare 服务停机 27 分钟不仅仅是因为正则表达式错误。 我们花了一段时间来描述导致失败的事件顺序，因此我们反应缓慢。 在文章的最后，我将用正则表达式描述回溯并告诉您如何处理它。
发生了什么事
让我们按顺序开始吧。 这里的所有时间均采用 UTC 时间。
下午13点42分，防火墙团队的工程师对检测规则做了一个小改动 使用自动过程。 因此，创建了变更请求票。 我们通过 Jira 管理此类票证（下面的屏幕截图）。
3分钟后，出现PagerDuty的第一页，报告WAF出现问题。 这是一项综合测试，用于测试 Cloudflare 之外的 WAF（我们有数百个）的功能以监控正常运行。 紧随其后的是有关其他 Cloudflare 端到端服务测试失败、全球流量问题、广泛的 502 错误以及来自我们位于世界各地城市的存在点 (PoP) 的大量报告的警报页面，这些报告表明存在缺陷CPU 资源。
我收到了几条这样的警报，然后愤然离开了会议，在我走向谈判桌的路上，我们的解决方案开发部门负责人说我们已经损失了 80% 的流量。 我跑去找我们的 SRE 工程师，他们已经在解决这个问题了。 起初我们以为这是某种未知的攻击。
Cloudflare SRE 工程师分散在世界各地，全天候监控情况。 通常，这些警报会通知您范围有限的特定本地问题，在内部仪表板上进行跟踪，并每天多次解决。 但这些页面和通知表明事情确实很严重，SRE 工程师立即宣布严重级别 P0 并联系管理和系统工程师。
那时我们伦敦的工程师正在主厅听讲座。 讲座不得不中断，大家聚集在一个大会议室里，并召集了更多的专家。 这不是 SRE 可以自行处理的典型问题。 迫切需要合适的专家参与。
14:00，我们确定问题出在WAF上，没有发生攻击。 性能团队提取了 CPU 数据，很明显 WAF 是罪魁祸首。 另一位员工使用 strace 证实了这一理论。 还有人在日志中看到WAF有问题。 下午 14:02，当有人提议使用全局终止（Global Kill）时，整个团队来找我，这是 Cloudflare 中内置的一种机制，可以在全球范围内关闭一个组件。
我们如何为 WAF 进行全球杀戮是一个不同的故事。 事情没那么简单。 我们使用我们自己的产品，并且由于我们的服务 不起作用，我们无法进行身份验证并登录到内部控制面板（当一切都修复后，我们了解到，由于安全功能，如果内部控制面板未用于特定用途，该功能会禁用凭据，一些团队成员就会失去访问权限）很久）。
我们无法访问内部服务，例如 Jira 或构建系统。 我们需要一个我们很少使用的解决机制（这也需要解决）。 最终，一名工程师于 14:07 成功禁用了 WAF，并于 14:09 各地的流量和 CPU 水平恢复正常。 Cloudflare 的其余保护机制正常工作。
然后我们开始恢复WAF。 这种情况不同寻常，因此我们在一个城市使用单独的流量进行了负面测试（询问自己更改是否真的是问题）和正面测试（确保回滚有效），从那里转移付费客户。
14点52分，我们确信我们理解了原因并进行了更正，并再次启用了WAF。
Cloudflare 的工作原理
Cloudflare 拥有一支致力于管理 WAF 规则的工程师团队。 他们努力提高检测率、减少误报并在新威胁出现时快速响应。 在过去 60 天内，已处理 476 个针对 WAF 托管规则的更改请求（平均每 3 小时 XNUMX 个）。
这一特定的更改需要在模拟模式下部署，其中真实的客户端流量通过规则，但不会阻止任何内容。 我们使用这种模式来测试规则的有效性并测量误报率和漏报率。 但即使在模拟模式下，规则也必须实际执行，在这种情况下，规则包含消耗太多处理器资源的正则表达式。
正如您从上面的变更请求中看到的，我们有一个部署计划、一个回滚计划以及指向此类部署的内部标准操作程序 (SOP) 的链接。 用于更改规则的 SOP 允许其在全球范围内发布。 实际上，在 Cloudflare，事情的处理方式完全不同，SOP 规定我们首先将用于测试和内部使用的软件发送到内部存在点 (PoP)（我们的员工使用），然后发送给少数客户一个偏僻的地方，然后到大量的客户，然后才到整个世界。
这就是它的样子。 我们通过 BitBucket 在内部使用 git。 负责变更的工程师提交代码，该代码构建到 TeamCity 中，构建通过后，将分配审阅者。 一旦拉取请求获得批准，就会组装代码并（再次）运行一系列测试。
如果构建和测试成功完成，则会在 Jira 中创建变更请求，并且相应的经理或领导必须批准变更。 批准后，部署到所谓的“PoP 动物园”：DOG、PIG 和 （狗、猪和金丝雀）。
DOG PoP 是一个 Cloudflare PoP（与我们其他城市一样），仅供 Cloudflare 员工使用。 供内部使用的 PoP 允许您在客户流量开始流入解决方案之前发现问题。 有用的东西。
如果 DOG 测试成功，代码将进入 PIG（豚鼠）阶段。 这就是 Cloudflare PoP，少量免费客户流量通过新代码流动。
如果一切顺利，代码将进入 Canary。 我们在世界不同地区拥有三个金丝雀 PoP。 其中，付费和免费客户端的流量都会通过新代码，这是最后一次错误检查。
Cloudflare 的软件发布流程
如果代码在 Canary 中没问题，我们就会发布它。 经历所有阶段 - DOG、PIG、Canary、整个世界 - 需要几个小时或几天，具体取决于代码更改。 由于 Cloudflare 网络和客户的多样性，我们在向全球所有客户发布代码之前会对其进行彻底测试。 但WAF并没有专门遵循这个流程，因为需要快速响应威胁。
WAF 威胁
在过去的几年中，常见应用程序中的威胁显着增加。 这是由于软件测试工具的可用性更高。 例如，我们最近写过 ).
来源：
通常，会创建概念验证并立即在 Github 上发布，以便维护应用程序的团队可以快速测试它并确保它得到充分的保护。 因此，Cloudflare 需要能够尽快响应新的攻击，以便客户有机会修复他们的软件。
Cloudflare 快速响应的一个很好的例子是 XNUMX 月份部署的 SharePoint 漏洞保护（）。 几乎在发布公告后不久，我们就注意到在客户的 SharePoint 安装中存在大量利用该漏洞的尝试。 我们的人员不断监控新威胁并编写规则来保护我们的客户。
周四引发问题的规则原本是为了防止跨站脚本（XSS）。 近年来，此类攻击也变得更加频繁。
来源：
更改 WAF 托管规则的标准程序是在全球部署之前进行持续集成 (CI) 测试。 上周四我们做到了这一点并推出了规则。 下午 13:31，一名工程师提交了一份已批准的带有更改的拉取请求。
13:37，TeamCity 收集了规则，进行了测试并获得批准。 WAF测试套件测试WAF的核心功能，由大量针对各个功能的单元测试组成。 经过单元测试，我们使用大量的HTTP请求测试了WAF的规则。 HTTP 请求检查 WAF 应阻止哪些请求（以拦截攻击）以及允许哪些请求通过（以免阻止所有内容并避免误报）。 但我们没有测试CPU使用率是否过高，并且检查之前WAF构建的日志显示规则测试执行时间并没有增加，很难怀疑资源不足。
测试通过，TeamCity 于下午 13:42 开始自动部署更改。
水银
WAF 规则专注于即时威胁补救，因此我们使用 Quicksilver 的分布式键值存储来部署它们，该存储可以在几秒钟内将更改传播到全球。 我们所有的客户在仪表板或通过 API 更改配置时都使用这项技术，正是有了它，我们才能以闪电般的速度响应变化。
我们还没有过多谈论快银。 之前我们用过 作为一个全球分布式的键值对存储，但它存在运营问题，我们编写了自己的存储，并在 180 多个城市进行了复制。 我们现在使用 Quicksilver 将配置更改推送到客户端、更新 WAF 规则并将客户端编写的 JavaScript 代码分发到 Cloudflare Workers。
从点击仪表板上的按钮或调用 API 到在全球范围内进行配置更改，只需几秒钟。 客户喜欢这种设置速度。 Workers 为他们提供了几乎即时的全球软件部署。 平均而言，Quicksilver 每秒传播约 350 次更改。
而且快银的速度非常快。 平均而言，我们实现了将更改传播到全球每台计算机的第 99 个百分位数为 2,29 秒。 速度通常是一件好事。 毕竟，当您启用某个功能或清除缓存时，它几乎会立即发生并且无处不在。 通过 Cloudflare Workers 发送代码的速度相同。 Cloudflare 向客户承诺在适当的时间快速更新。
但在这种情况下，速度给我们开了一个残酷的玩笑，几秒钟的时间里规则就变了。 您可能已经注意到WAF代码使用Lua。 Cloudflare 在生产和细节方面广泛使用 Lua 我们 。 Lua WAF 使用 内部并应用回溯进行匹配。 它没有机制来防止表达式失控。 下面我将详细讨论这一点以及我们正在采取的措施。
在部署规则之前，一切都很顺利：拉取请求已创建并获得批准，CI/CD 管道收集并测试代码，根据管理部署和回滚的 SOP 提交变更请求，然后部署完成。
Cloudflare WAF 部署流程
出了什么问题
正如我所说，我们每周部署数十条新的 WAF 规则，并且我们有许多系统来防止此类部署的负面后果。 当出现问题时，通常是多种情况同时发生的。 如果你只找到一个原因，这当然会令人放心，但事实并非总是如此。 这些都是共同导致我们的HTTP/HTTPS服务失败的原因。
- 工程师编写了一个正则表达式，可能会导致过多的结果 .
- 几周前的 WAF 重构中，一个原本可以防止正则表达式浪费过多 CPU 的功能被错误地删除了——重构是为了让 WAF 消耗更少的资源。
- 正则表达式引擎没有复杂性保证。
- 测试套件无法检测到 CPU 消耗过多。
- SOP 允许在全球范围内推出非紧急规则更改，而无需执行多步骤流程。
- 回滚计划需要运行完整的 WAF 构建两次，这需要很长时间。
- 关于全球交通问题的第一个警报触发得太晚了。
- 我们花了一些时间来更新状态页面。
- 由于故障，我们在访问系统时遇到了问题，而且旁路程序也没有很好地建立。
- SRE 工程师无法访问某些系统，因为他们的凭据由于安全原因而过期。
- 我们的客户无法访问 Cloudflare 仪表板或 API，因为他们要经过 Cloudflare 区域。
自上周四以来发生了什么变化
首先，我们完全停止了 WAF 版本的所有工作，并正在执行以下操作：
- 我们正在重新引入已删除的 CPU 过度使用保护。 （准备好）
- 手动检查 WAF 托管规则中的所有 3868 条规则，以查找并纠正其他潜在的过度回溯情况。 （验证完成）
- 我们在测试集中包含所有规则的性能分析。 （预计：19 月 XNUMX 日）
- 切换到正则表达式引擎 или - 两者都提供运行时保证。 （预计：31 月 XNUMX 日）
- 我们正在重写 SOP，以分阶段部署规则，就像 Cloudflare 中的其他软件一样，但同时能够在攻击已经开始时紧急进行全球部署。
- 我们正在开发从 Cloudflare 区域紧急删除 Cloudflare 仪表板和 API 的功能。
- 自动页面更新 .
从长远来看，我们正在远离我几年前编写的 Lua WAF。 将 WAF 移至 。 这样，WAF 将更快并获得更高级别的保护。
结论
这次故障给我们和我们的客户带来了麻烦。 我们迅速采取行动纠正了这种情况，现在正在解决导致崩溃的流程中的缺陷，并进行更深入的挖掘，以防止将来在迁移到新技术时出现正则表达式的潜在问题。
我们对这次中断感到非常尴尬，并向我们的客户致歉。 我们希望这些改变能够确保类似的事情不再发生。
应用。 回溯正则表达式
要理解如何表达：
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))占用了所有的CPU资源，你需要了解一点标准正则表达式引擎是如何工作的。 这里的问题是模式 .*(?:.*=.*). (?: 以及相应的 ) 是非捕获组（即，括号中的表达式被分组为单个表达式）。
在CPU消耗过多的情况下，这种模式可以描述为 .*.*=.*。 在这种形式下，图案看起来不必要地复杂。 但更重要的是，在现实世界中，要求引擎匹配一个片段后跟另一个片段的表达式（如 WAF 规则中的复杂表达式）可能会导致灾难性的回溯。 这就是原因。
在正则表达式中 . 意味着你需要匹配一个字符， .* - “贪婪地”匹配零个或多个字符，即捕获最多的字符，以便 .*.*=.* 表示匹配零个或多个字符，然后匹配零个或多个字符，找到字面=字符，匹配零个或多个字符。
我们来测试一下线 x=x。 它对应于表达式 .*.*=.*. .*.* 在等号与第一个等号匹配之前 x （其中一组 .* 对应于 x，第二个 - 零字符）。 .* after = 最后匹配 x.
此比较需要 23 个步骤。 第一组 .* в .*.*=.* 贪婪地行动并匹配整个字符串 x=x。 引擎移至下一组 .*。 我们没有更多的字符可以匹配，所以第二组 .* 匹配零个字符（这是允许的）。 然后发动机移动到标志处 =。 没有更多符号（第一组 .* 使用了整个表达式 x=x)，不会发生比较。
然后正则表达式引擎返回到开头。 他进入第一组 .* 并比较它 с x= （而不是 x=x），然后进行第二组 .*。 第二组 .* 与第二个相比 x，我们又没有剩下任何字符了。 当引擎再次到达 = в .*.*=.*，没有任何作用。 然后他又退缩了。
这次的团 .* 仍然匹配 x=，但第二组 .* 不再 x和零个字符。 引擎正在尝试查找文字字符 = 在图案中 .*.*=.*，但是就是不出来（毕竟第一组已经占领了 .*）。 然后他又退缩了。
这次是第一组 .* 只取第一个 x。 但第二组 .* “贪婪”地捕捉 =x。 你已经猜到会发生什么了吗？ 引擎尝试匹配文字 =，失败并再次回溯。
第一组 .* 仍然匹配第一个 x... 第二 .* 只需要 =。 当然，引擎无法匹配字面意思 =，因为第二组已经这样做了 .*。 又再一次回溯。 我们正在尝试匹配一个由三个字符组成的字符串！
结果，第一组 .* 仅匹配第一个 x第二 .* - 零个字符，引擎最终匹配文字 = 在表达上 с = 排队。 接下来是最后一组 .* 与上一个相比 x.
23步仅用于 x=x。 观看有关使用 Perl 的短视频 ，它显示了步骤和回溯是如何发生的。
这已经是很多工作了，但是如果相反呢？ 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 年 Kent Thompson 写了一篇文章以来，这个问题的解决方案就已为人所知 （“编程方法：正则表达式搜索算法”）。 本文描述了一种机制，允许您将正则表达式转换为非确定性有限状态机，并且在非确定性有限状态机中状态更改后，使用执行时间线性依赖于匹配字符串的算法。
编程方法
正则表达式搜索算法
肯·汤普森
贝尔电话实验室公司，新泽西州默里山它描述了一种在文本中搜索特定字符串的方法，并讨论了该方法以编译器形式的实现。 编译器将正则表达式作为源代码，并生成 IBM 7094 程序作为目标代码。 目标程序以搜索文本的形式获取输入，并在每次文本字符串与给定正则表达式匹配时发出信号。 文章提供了示例、问题和解决方案。
算法
如果部分成功的搜索未能产生结果，以前的搜索算法会导致回溯。在编译模式下，该算法不适用于符号。 它将指令传递给编译后的代码。 执行速度非常快 - 将数据传递到当前列表的顶部后，它会自动搜索正则表达式中所有可能的连续字符。
编译和搜索算法作为上下文搜索包含在分时文本编辑器中。 当然，这远非此类搜索程序的唯一应用。 例如，该算法的一个变体被用作汇编器表中的符号搜索。
假设读者熟悉正则表达式和 IBM 7094 计算机编程语言。编译器
编译器由并行运行的三个阶段组成。 第一阶段是语法过滤，只允许语法正确的正则表达式通过。 此步骤还插入“·”运算符来匹配正则表达式。 第二步，将正则表达式转换为后缀形式。 在第三阶段，创建目标代码。 前两个阶段是显而易见的，我们不会详细讨论它们。
Thompson 的文章没有讨论非确定性有限状态机，但它确实很好地解释了线性时间算法，并提出了一个为 IBM 60 生成汇编语言代码的 ALGOL-7094 程序。实现很棘手，但想法非常简单。
当前搜索路径。 它由一个 ⊕ 图标表示，具有一个输入和两个输出。
图 1 显示了转换正则表达式示例时第三编译步骤的功能。 示例中的前三个字符是 a、b、c，每个字符创建一个堆栈条目 S[i] 和一个 NNODE 字段。NNODE 到现有代码以在单个堆栈条目中生成结果正则表达式（参见图 5）
这就是正则表达式的样子 .*.*=.*，如果你把它想象成汤普森文章中的图片。
在图中。 0从0开始有3个状态，从状态1、2、3开始有XNUMX个周期。这XNUMX个周期对应XNUMX个 .* 在正则表达式中。 3 个带点的椭圆对应 XNUMX 个符号。 带标志的椭圆形 = 匹配文字字符 =。 状态 4 是最终状态。 如果我们到达它，那么正则表达式就匹配了。
看看这样的状态图如何用于正则表达式匹配 .*.*=.*，我们将查看字符串匹配 x=x。 程序从状态0开始，如图所示。 1.
为了使该算法起作用，状态机必须同时处于多个状态。 非确定性有限机器将同时进行所有可能的转换。
在它有时间读取输入数据之前，它会进入第一个状态（1 和 2），如图 2 所示。 XNUMX.
在图中。 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.
该算法线性依赖于输入字符串的大小。
来源： habr.com