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> 是一个库，不对时间或空间复杂性做出任何保证。默认情况下，<regex> 使用与 ECMA-262 相同的正则表达式语言，该语言基于 PCRE 并支持回引用（请参阅 Hron Martin，第 3.5.5 节）。

截至 2021 年 4 月，<regex.h> 的使用次数为 6 次，该库支持回引用并使用回溯实现（请参阅 Hron Martin，第 3.5.7 节）。

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 创建功能允许创建任意 DFA，并且在最坏情况下，时间和空间用量呈指数级增长。自 2021 年 4 月起，Fuchsia 程序不会直接使用此 crate，但会通过其他 crate（例如 bstr）间接使用它，后者会以受限方式使用 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 攻击的风险较小。

我们可能会批准上述规则的例外情况。下文介绍了获取例外情况的流程。

实现

我们将按照为 //third_party/googletest 建立的模式为 RE2 库创建一个滚动器。系统会创建一个 //third_party/re2/OWNERS 文件，用于指定谁负责维护此滚筒。初始 OWNER 将为 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 中现有的此 crate 用法获得了例外情况。

异常

如果满足以下条件，我们可能会批准豁免：

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 语法的超集。这会根据 RE2 的语法对 Fuchsia 正则表达式进行标准化。Rust 的 regex 添加了一些次要功能，例如字符类交集和减法，以及 RE2 中不提供的 x 标志。

向后兼容性

我已手动检查 <regex> 和 <regex.h> 的所有现有用法。在大多数情况下，正则表达式模式是编译时常量，在 RE2 中会按原样（或稍微更改语法）运行。在这些情况下，不会出现向后兼容性问题。

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

安全注意事项

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

隐私注意事项

无。

测试

系统会运行现有测试。没有要测试的新功能。

文档

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

缺点、替代方案和未知情况

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

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

在先技术和参考文档

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