RFC-0105：正则表达式库

RFC-0105：正则表达式库
状态	已接受
区域	常规
说明	限制可在 Fuchsia 中使用的正则表达式库集。
问题	77811
Gerrit 更改	521301
作者	tombergan@google.com
审核人	cpu@google.com shayba@google.com phosek@google.com vbelliard@google.com brettw@google.com maruel@google.com pascallouis@google.com
提交日期（年-月-日）	2021-04-26
审核日期（年-月-日）	2021-06-16

摘要

此 RFC 建议禁止所有无法明确保证时间复杂度与要匹配的字符串大小成线性比例关系的正则表达式库。官方认可的库包括 RE2 (C++)、regex (Rust) 和 regexp (Go)。

设计初衷

众所周知，纯正则表达式可以在 O(mn) 时间内匹配，其中 n 是输入字符串的长度，m 是正则表达式的 NFA 在 a{10}b{10} 等构造展开后的大小。不过，许多库都包含扩展功能，例如反向引用，这使得此问题的最坏情况为指数级。其他库使用回溯实现，即使模式不使用反向引用，最坏情况下的时间复杂度也是指数级的。这会将正则表达式转换为拒绝服务 (DoS) 攻击的向量：如果恶意用户控制要匹配的模式或字符串，则该用户可能能够触发指数搜索，从而耗尽 CPU 并导致 DoS。如需进一步讨论，请参阅 Davis 等人、Russ Cox、V8 和 Wikipedia。

截至 2021 年 4 月，Fuchsia 使用的正则表达式库可能容易受到拒绝服务攻击。以下是针对每种 Fuchsia 支持的语言的讨论：

C/C++

截至 2021 年 4 月，<regex>（一个不保证时间或空间复杂度的库）有 38 个用途。默认情况下，<regex> 使用与 ECMA-262 相同的正则表达式语言，该语言基于 PCRE 并支持反向引用（请参阅 Hron Martin，第 3.5.5 节）。

截至 2021 年 4 月，<regex.h>（一种支持反向引用的库，使用回溯实现；请参阅 Hron Martin，第 3.5.7 节）有 6 个用途。

Google 的 RE2 不支持反向引用，并保证相对于输入字符串大小的线性时间匹配。 此外，RE2 对内存用量设置了可配置的上限，可防止 O(mn) 中的 m 字词导致 DoS。截至 2021 年 4 月，此库已导入 Fuchsia 的 //third_party，但尚无用户。因此，Fuchsia 的 C 和 C++ 代码可能容易受到正则表达式 DoS 攻击。

Rust

Rust 的 regex crate 不支持反向引用，它保证了 O(mn) 时间匹配，它像 RE2 一样限制了 NFA，因此不会受到 DoS 攻击。截至 2021 年 4 月，这是 Fuchsia 中 Rust 程序直接使用的唯一正则表达式库。

Rust 的 regex_automata crate 允许创建任意 DFA，但最坏情况下的时间和空间使用量为指数级。截至 2021 年 4 月，Fuchsia 程序不会直接使用此 crate，但会通过其他 crate（例如 bstr）间接使用此 crate，后者以受限方式使用 regex_automata，以便保证最坏情况下的线性时间和恒定空间。

Go

Go 的标准 regexp 软件包基于 RE2，因此不会受到 DoS 攻击。截至 2021 年 4 月，这是 Fuchsia 中 Go 程序使用的唯一正则表达式库。

Dart

Dart 的标准 RegExp 库基于 JavaScript 的 RegExp 库构建，因此可能容易受到 DoS 攻击。

设计

为避免 DoS 攻击，所有 Fuchsia 代码都必须使用以下库之一进行正则表达式解析和匹配：

• C++ 代码必须使用 RE2
• Rust 代码必须使用 regex crate
• Go 代码必须使用标准 regexp 软件包

之所以选择这些许可的库，是因为它们都能保证线性时间匹配。仅仅禁止回溯等功能是不够的，因为即使是纯正则表达式，在无法保证最坏情况下的线性时间匹配的库中，也可能存在病态行为。

我们对 Dart 代码没有任何限制。Dart 的内置 RegExp 类使用回溯实现，该实现支持反向引用，但不保证线性时间匹配。我们曾考虑禁止在 Dart 程序中使用反向引用，但最终认为对于将正则表达式作为用户输入的 Dart 程序而言，这样做是不可行的：此类程序需要解析并验证从用户处收到的正则表达式，但目前还没有广泛使用的库支持此功能。此外，Dart 的 RegExp 实现基于 V8 的 Irregexp，即使是不包含反向引用的模式，也可能会出现指数级爆炸式增长。由于 Dart 无法用于核心系统服务，因此 DoS 问题的严重程度有所降低。

上述规则可能会有例外情况。下面介绍了获取例外情况的流程。

实现

我们将为 RE2 库创建一个滚动更新器，遵循为 //third_party/googletest 建立的模式。系统将创建一个 //third_party/re2/OWNERS 文件，用于指定负责维护相应滚动更新的人员。初始所有者将为 tombergan@google.com。此滚动更新部署完毕且 //third_party/re2 更新到最新版本后，现有的 C++ 代码将从 <regex> 和 <regex.h> 移植到 RE2。Go、Rust 和 Dart 程序无需进行任何更改，因为它们已符合此 RFC。

完成该迁移后，系统会添加两种类型的规则：

1. 将添加基于 clang-tidy 的预提交规则，以禁止在 C++ 代码中使用 <regex> 和 <regex.h>。

2. 将添加一项可见性规则，以防止 Fuchsia 程序导入 Rust 的 regex-automata crate。bstr 中对此箱的现有使用情况授予了例外，因为 bstr 保证了最坏情况下的线性时间和恒定空间。

异常

如果满足以下条件，可以允许例外情况：

1. 存在迫切需求，例如需要与第三方库或工具兼容。

2. 新导入的库保证了线性时间行为，或者，可以证明 DoS 对于相关代码不是问题。例如，如果正则表达式仅在主机工具中使用，或者仅作为生产 build 中不可用的开发者工作流的一部分使用，那么 DoS 最多只会给开发者带来困扰，而不会造成安全问题，因此可以授予例外情况。

许可名单中记录了例外情况。每个许可名单都必须包含指向此 RFC 的注释，以便读者了解适当的背景信息。如需申请例外情况，您必须上传 CL 以修改相应的许可名单。CL 必须详细说明例外情况的理由，并且 CL 必须获得 FEC 成员的批准。许可名单有两种：

1. 我们基于 clang-tidy 的预提交规则将在 Fuchsia 源代码树中的待定位置设置许可名单。许可名单的位置将记录在预提交规则的错误消息中，因此可以通过运行正常的预提交来发现。

2. 第三方库例外情况由定义相应库的 BUILD.gn 文件中的普通 visibility 许可名单控制。

未经 FEC 成员批准，无法将新的正则表达式库导入到 //third_party。导入后，库必须包含一个可见性许可名单，以及一个指向此 RFC 的注释。

性能

由于此提案禁止使用最坏情况下的指数时间库，因此会对性能产生积极影响。

代码大小

fxrev.dev/532721 分析了 ARM64 build 的预期代码大小变化。由于 Go 和 Rust 程序没有变化，因此这些程序的代码大小也不会发生变化。对于 C++ 程序，代码大小的增加取决于 RE2 是静态链接还是动态链接。目前，Fuchsia 主机工具以静态方式链接，而目标程序则以静态或动态方式链接，具体取决于代码大小影响。如果采用静态链接，C++ 程序的大小至少会增加 180KB。使用动态链接时，RE2 共享库大约需要 350 KB。此费用在每个系统映像中只需支付一次：使用 <regex.h> 的 C++ 程序在切换到 RE2 后，代码大小几乎不会发生变化；而使用 <regex> 的 C++ 程序在切换到 RE2 后，代码大小应该会变小，因为 std::regex 大量使用模板，而 RE2 不使用模板。

工效学设计

此提案将使 Fuchsia 平台上的正则表达式语言更加统一。例如，当前的 C++ 工具和服务可能通过 <regex> 支持反向引用，而 Rust 和 Go 工具和服务则不支持。此提案实施后，任何系统工具或服务都不再支持反向引用（用 Dart 编写的工具除外）。

此外，RE2 和 Go 的 regexp 支持完全相同的正则表达式语法，而 Rust 的 regex 基于 RE2，支持 RE2 语法的超集。这会将 Fuchsia 正则表达式标准化为 RE2 的语法。Rust 的 regex 添加了一些次要功能，例如字符类交集和差集，以及 RE2 中没有的 x 标志。

向后兼容性

我已手动检查了 <regex> 和 <regex.h> 的所有现有用法。在大多数情况下，正则表达式模式都是编译时常量，可以在 RE2 中按原样使用（或稍作语法更改）。在这些情况下，无需担心向后兼容性问题。

我只找到了三个允许用户指定正则表达式的程序：调试器、fidlcat 和 perftest。为确保这些工具在此更改后不会出现故障，我会将这些工具的 OWNER 添加为此 RFC 的审核者。

安全注意事项

此 RFC 将降低正则表达式被用作 DoS 攻击载体的可能性。

隐私注意事项

无。

测试

系统将运行现有测试。没有可测试的新功能。

文档

如上所述，预提交和可见性规则将链接到此 RFC，以便开发者了解其导入被拒绝的原因。新第三方代码的审核者需要了解此 RFC，以便他们知道要拒绝导入未经批准的正则表达式库。这包括直接包含 <regex> 或 <regex.h> 的 C++ 和 C 库。

缺点、替代方案和未知因素

请参阅“后向兼容性”。其他 C++、Rust 或 Go 库可能提供同等保证。我们之所以选择 RE2、regex 和 regexp（分别），是因为它们被广泛使用，并且已导入到 Fuchsia 的 //third_party 中。

未来版本的这些库可能会引入非线性时间功能，但风险很小。由于这些库将线性时间匹配作为核心功能进行宣传，因此我们认为这种情况不太可能发生，但如果发生，我们将需要选择新的库。

在先技术和参考资料

请参阅“动机”部分中链接的参考资料，尤其是 Russ Cox 的文章，其中介绍了 Google 开发 RE2 的历史和动机。