RFC-0105：正则表达式库

RFC-0105：正则表达式库
状态已接受
区域
  • 常规
说明

限制可在 Fuchsia 中使用的正则表达式库集。
问题
Gerrit 更改
作者
审核人
提交日期（年-月-日）2021-04-26
审核日期（年-月-日）2021-06-16

修改此 RFC

修改 RFC 元数据

摘要

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

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

Google 的 RE2 不支持反向引用 并保证相对于输入字符串大小的线性时间匹配。 此外，RE2 对内存使用量有可配置的限制，可防止 m 项在 O(mn) 中导致 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 create 允许创建任意 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 的担忧较少。

在满足上述规则的情况下，可以授予例外情况。下文介绍了获取例外情况的流程。

实现

我们将为 RE2 库创建一个滚动器，遵循为 //third_party/googletest 建立的模式。系统将创建一个 //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 的 语法超集。这会将 Fuchsia 正则表达式标准化为 RE2 的语法。Rust 的 regex 添加了一些次要功能，例如字符类交集和 减法，以及 x 标志，这些功能在 RE2 中不可用。

向后兼容性

我已手动检查了 <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 的历史和 设计初衷。