本頁面由 Cloud Translation API 翻譯而成。

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

編輯 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 月，<regex> 程式庫有 38 種用途，但該程式庫無法保證時間或空間複雜度。根據預設，<regex> 使用的規則運算式語言與 ECMA-262 相同，以 PCRE 為基礎，並支援反向參照 (請參閱 Hron Martin 的第 3.5.5 節)。

截至 2021 年 4 月，<regex.h> 程式庫有 6 種用途，支援反向參照並使用回溯實作 (請參閱 Hron Martin 的第 3.5.7 節)。

Google 的 RE2 不支援反向參照，且保證與輸入字串大小相關的線性時間比對。此外，RE2 的記憶體用量可設定上限，避免 m 字詞在 O(mn) 中造成 DoS 攻擊。自 2021 年 4 月起，這個程式庫已匯入 Fuchsia 的 //third_party，但沒有任何使用者。因此，Fuchsia 的 C 和 C++ 程式碼可能容易受到規則運算式 DoS 攻擊。

荒漠油廠

Rust 的 regex Crate 不支援反向參照，可保證 O(mn) 時間比對，並限制 NFA，與 RE2 相同，因此不會受到 DoS 攻擊。自 2021 年 4 月起，這是 Fuchsia 中 Rust 程式直接使用的唯一規則運算式程式庫。

Rust 的 regex_automata 建立功能可建立任意 DFA，最糟的情況是時間和空間用量呈指數成長。自 2021 年 4 月起，Fuchsia 程式不會直接使用這個 Crate，但會透過其他 Crate 間接使用，例如 bstr，這類 Crate 會以受限方式使用 regex_automata，確保最差情況下的線性時間和常數空間。

查看

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 程式庫建立 Roller，遵循為 //third_party/googletest 建立的模式。系統會建立 //third_party/re2/OWNERS 檔案，指定負責維護這個滾輪的人員。初始 OWNER 為 tombergan@google.com。部署這項捲動器並將 //third_party/re2 更新至最新版本後，現有的 C++ 程式碼會從 <regex> 和 <regex.h> 移植到 RE2。Go、Rust 和 Dart 程式已符合這項 RFC 規定，因此不需要進行任何變更。

遷移作業完成後，系統會新增兩類規則：

系統會新增以 clang-tidy 為基礎的預先提交規則，禁止在 C++ 程式碼中使用 <regex> 和 <regex.h>。
系統會新增瀏覽權限規則，防止 Fuchsia 程式匯入 Rust 的 regex-automata Crate。由於 bstr 保證最差情況下的線性時間和常數空間，因此系統會為 bstr 中這個 Crate 的現有用法授予例外狀況。

例外狀況

如果符合下列條件，我們「可能」會核發例外狀況：

有迫切需求，例如需要與第三方程式庫或工具相容。
新匯入的程式庫可確保線性時間行為，或者，可證明 DoS 不是相關程式碼的問題。舉例來說，如果正規運算式用於主機工具，或僅做為開發人員工作流程的一部分，且無法在正式版中提供，則 DoS 最多只會造成開發人員困擾，不會造成安全疑慮，因此可能獲准例外。

例外狀況會記錄在允許清單中。每個許可清單都必須包含連結至這項 RFC 的註解，讓讀者瞭解適當的背景資訊。如要申請例外情況，請務必上傳 CL，修改適當的允許清單。CL「必須」詳細說明例外狀況的理由，且 CL「必須」獲得 FEC 成員核准。許可清單分為兩種：

我們以 clang-tidy 為基礎的預先提交規則，會在 Fuchsia 來源樹狀結構中待定的位置，建立允許清單。許可清單的位置會記錄在預先提交規則的錯誤訊息中，因此執行一般預先提交時，即可發現許可清單。
第三方程式庫例外狀況是由 BUILD.gn 檔案中定義程式庫的普通 visibility 允許清單控管。

如要將新的規則運算式程式庫匯入 //third_party，必須先獲得 FEC 成員核准。匯入後，程式庫「必須」包含可見度許可清單，以及連結至這項 RFC 的註解。

效能

由於這項提案禁止使用最糟情況下呈指數時間的程式庫，因此將對效能產生正面影響。

程式碼大小

fxrev.dev/532721 會分析 ARM64 建構版本中預期的程式碼大小變化。由於 Go 和 Rust 程式沒有任何變更，這些程式的程式碼大小也不會變更。如果是 C++ 程式，程式碼大小的增幅取決於 RE2 是靜態還是動態連結。目前 Fuchsia 主機工具是靜態連結，而目標程式則視程式碼大小影響，以靜態或動態方式連結。使用靜態連結時，C++ 程式的大小至少會增加 180 KB。使用動態連結時，RE2 共用程式庫的費用約為 350 KB。這項費用是針對每個系統映像檔支付一次：改用 RE2 後，使用 <regex.h> 的 C++ 程式碼大小大致不會有變化，而使用 <regex> 的 C++ 程式碼大小則會縮減，因為 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。為確保這些工具在變更後不會中斷，我會將這些工具的擁有者新增為這項 RFC 的審查人員。

安全性考量

這項 RFC 可降低正規運算式做為 DoS 攻擊媒介的可能性。

隱私權注意事項

無。

測試

系統會執行現有測試。目前沒有可測試的新功能。

說明文件

如上所述，預先提交和可見度規則會連結至這份 RFC，讓開發人員瞭解匯入遭拒的原因。新第三方程式碼的審查人員必須瞭解這項 RFC，才能拒絕匯入未獲核准的規則運算式程式庫。包括直接加入 <regex> 或 <regex.h> 的 C++ 和 C 程式庫。

缺點、替代方案和未知事項

請參閱「回溯相容性」。其他 C++、Rust 或 Go 程式庫可能提供同等保證。我們選擇 RE2、regex 和 regexp (依序) 是因為這些項目廣泛使用，且已匯入 Fuchsia 的 //third_party。

這些程式庫的未來版本可能會導入非線性時間功能，因此存在輕微風險。由於這些程式庫會將線性時間比對宣傳為核心功能，我們認為不太可能發生這種情況，但如果真的發生，我們就必須選取新的程式庫。

既有技術和參考資料

請參閱動機章節中連結的參考資料，尤其是 Russ Cox 的文章，這些文章說明瞭 Google 開發 RE2 的歷史和動機。