| RFC-0105：正则表达式库 | |
|---|---|
| 状态 | 已接受 |
| 领域 |
|
| 说明 | 限制可在 Fuchsia 中使用的正则表达式库集。 |
| 问题 | |
| Gerrit 更改 | |
| 作者 | |
| 审核人 |
|
| 提交日期（年-月-日） | 2021-04-26 |
| 审核日期（年-月-日） | 2021-06-16 |
总结
此 RFC 提议禁止所有未明确保证相对于要匹配的字符串大小线性时间复杂度的正则表达式库。官方批准的库包括 RE2 (C++)、regex (Rust) 和 regexp (Go)。
设计初衷
众所周知，纯正则表达式可以在 O(mn) 时间内匹配，其中 n 是输入字符串的长度，m 是 a{10}b{10} 等结构被扩展后正则表达式的 NFA 的大小。不过，许多库都包含反向引用等扩展，从而使此问题最糟糕的指数化。其他库使用回溯实现，这种实现在最糟糕的情况下是指数级，即使该模式不使用反向引用。这会将正则表达式变成拒绝服务 (DoS) 攻击的矢量：如果恶意用户控制要匹配的格式或字符串，用户或许能够触发会耗尽 CPU 并引发 DoS 的指数搜索。如需进一步的讨论，请参阅 Davis 等人、Russ Cox、V8 和 维基百科。
从 2021 年 4 月起，Fuchsia 使用的正则表达式库可能容易受到拒绝服务攻击。以下是有关紫红色支持的每种语言的讨论：
C/C++
截至 2021 年 4 月，<regex> 有 38 次使用，该库不对时间或空间复杂性做出任何保证。默认情况下，<regex> 使用与 ECMA-262 相同的正则表达式语言，后者基于 PCRE 并支持反向引用（请参阅 Hron Martin 的第 3.5.5 节）。
截至 2021 年 4 月，6 种使用，<regex.h>这个库支持反向引用并使用回溯实现（请参阅 Hron Martin，第 3.5.7 节）。
Google 的 RE2 不支持反向引用，可保证相对于输入字符串的大小进行线性时间匹配。此外，RE2 具有可配置的内存用量限制，可防止 O(mn) 中的 m 字词导致 DoS。从 2021 年 4 月开始，此库已导入到 Fuchsia 的 //third_party 中，但没有用户。因此，Fuchsia 的 C 和 C++ 代码似乎可能容易受到正则表达式 DoS 攻击。
Rust
Rust 的正则表达式 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 月，这是 Go 程序在 Fuchsia 中使用的唯一正则表达式库。
Dart
Dart 的标准正则表达式库是基于 JavaScript 的正则表达式库构建的，因此它可能容易受到 DoS 攻击。
设计
为了避免 DoS 攻击，所有 Fuchsia 代码都必须使用以下某个库进行正则表达式解析和匹配：
- C++ 代码必须使用 RE2
- Rust 代码必须使用
regexcrate - Go 代码必须使用标准
regexp软件包
之所以选择这些获得批准的库，是因为它们都保证线性时间匹配。仅仅禁止回溯等功能是不够的，因为即使是纯正则表达式，在库中也可能具有病理行为，这些行为不能保证最糟糕的线性时间匹配。
我们不对 Dart 代码施加任何限制。Dart 的内置 RegExp 类使用回溯实现，该实现支持反向引用，但不保证线性时间匹配。我们曾考虑禁止在 Dart 程序中使用反向引用，但认为这种做法对于接收正则表达式作为用户输入的 Dart 程序来说不可行：此类程序必须解析并验证从用户收到的正则表达式，而且目前还没有广泛使用的库支持此功能。 此外，Dart 的 RegExp 实现基于 V8 的 Irregexp，即使在不包含反向引用的模式上也是如此。由于 Dart 不能用于核心系统服务，因此 DoS 就不太重要。
可以允许上述规则的例外情况。下面介绍了获取异常的过程。
实现
我们将按照为 //third_party/googletest 设定的模式为 RE2 库创建一个 Roller。系统将创建一个 //third_party/re2/OWNERS 文件，用于指定负责维护此 Roller 的人员。初始 OWNER 为 tombergan@google.com。部署此 roller 并将 //third_party/re2 更新到最新版本后，现有的 C++ 代码将从 <regex> 和 <regex.h> 移植到 RE2。Go、Rust 和 Dart 程序无需进行任何更改，因为这些程序已符合此 RFC 要求。
迁移完成后，系统会添加两种类型的规则：
将添加基于 clang-tidy 的提交前规则，以在 C++ 代码中禁止
<regex>和<regex.h>。将添加可见性规则，以防止 Fuchsia 程序导入 Rust 的
regex-automatacrate。目前在bstr中使用此 crate 会获得例外处理，因为bstr可保证最糟糕的线性时间和恒定空间。
异常
如果满足以下条件，则可视为例外情况：
有迫切的需求，例如需要与第三方库或工具兼容。
新导入的库可保证线性时间行为，或者，对于相关代码而言，DoS 显然不是问题。例如，如果将正则表达式用于主机工具或仅将其用于正式版 build 中未提供的开发者工作流，那么 DoS 最严重的会给开发者带来麻烦，不存在安全问题，可以允许例外情况。
许可名单中会记录例外情况。每个许可名单都必须包含一条指向该 RFC 的注释，以便读者了解相关背景信息。如需申请例外情况，您必须上传 CL 以修改相应的许可名单。CL 必须详细说明例外情况的理由，并且 CL 必须获得 FEC 成员的批准。许可名单有两种：
我们基于 clang-tidy 的提交前规则将在 Fuchsia 源代码树的待定位置有一个许可名单。许可名单的位置会记录在提交前规则的错误消息中，以便通过运行常规的提交前规则发现。
第三方库异常由定义库的 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 添加了一些次要功能，例如字符类交互和减法，以及 x 标志，这些功能在 RE2 中不可用。
向后兼容性
我已手动检查 <regex> 和 <regex.h> 的所有现有使用情况。在大多数情况下，正则表达式模式是编译时常量，可在 RE2 中按原样（或只需略微更改语法）在 RE2 中工作。在这种情况下，不存在向后兼容性问题。
我找到了三个允许用户指定正则表达式的程序：调试程序、fidlcat 和 perftest。为确保这些工具在这项更改后不会出现故障，我将这些工具的所有者添加为此 RFC 的审核者。
安全注意事项
此 RFC 将降低正则表达式用作 DoS 攻击的途径的可能性。
隐私注意事项
无。
测试
将运行现有测试。没有要测试的新功能。
文档
如上所述，提交前规则和可见性规则将链接到此 RFC，以便开发者了解其导入被拒绝的原因。新的第三方代码的审核者需要了解此 RFC，以告知审核者拒绝导入未获批准的正则表达式库。这包括直接包含 <regex> 或 <regex.h> 的 C++ 和 C 库。
缺点、替代方案和未知情况
请参阅“向后兼容性”。其他 C++、Rust 或 Go 库可以提供等效保证。我们分别选择 RE2、正则表达式和正则表达式，因为它们使用广泛，并已导入 Fuchsia 的 //third_party。
这些库的未来版本很有可能会引入非线性时间特征。由于这些库将线性时间匹配作为一项核心功能，我们认为这种情况不太可能发生，但如果发生这种情况，我们需要选择新的库。
早期技术和参考资料
请参阅动机部分中链接的参考资料，尤其是 Russ Cox 的文章，这些文章介绍了 Google 开发 RE2 的历史和动机。