| 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 和 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 還可設定記憶體使用量上限，避免 O(mn) 中的 m 字詞造成 DoS。截至 2021 年 4 月，這個程式庫已匯入 Fuchsia 的 //third_party，但沒有使用者。因此，Fuchsia 的 C 和 C++ 程式碼「可能」會受到規則運算式 DoS 攻擊。
荒漠油廠
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 的標準 regexp 套件是以 RE2 為基礎，因此不易受到 DoS 攻擊。截至 2021 年 4 月，這是 Fuchsia 中 Go 程式唯一使用的規則運算式程式庫。
Dart
Dart 的標準 RegExp 程式庫是建立在 JavaScript 的 RegExp 程式庫上，因此可能會受到 DoS 攻擊。
設計
為避免 DoS 攻擊，所有 Fuchsia 程式碼都必須使用下列其中一個程式庫，以便進行規則運算式剖析和比對：
- C++ 程式碼必須使用 RE2
- Rust 程式碼必須使用
regexcrate - Go 程式碼必須使用標準
regexp套件
我們選擇這些已核准的程式庫，是因為這些程式庫都保證線性時間比對。僅禁止回溯等功能是不夠的，因為即使是純規則運算式，在無法保證最壞情況下以線性時間比對的程式庫中，也可能會出現病態行為。
我們不會對 Dart 程式碼設下任何限制。Dart 內建的 RegExp 類別會使用回溯實作，可支援回溯參照，但無法保證線性時間比對。我們曾考慮禁止在 Dart 程式中使用回溯參照，但決定這對接收使用者輸入的規則運算式做為輸入內容的 Dart 程式而言，是不可行的：這類程式必須剖析及驗證從使用者收到的規則運算式，而目前沒有任何廣泛使用的程式庫支援這項操作。此外，Dart 的 RegExp 實作方式是以 V8 的 Irregexp 為基礎，即使是不含回溯參照的模式，也可能會發生指數爆炸。由於 Dart 無法用於核心系統服務，因此不必擔心 DoS 問題。
上述規則可能會例外處理。以下說明取得例外狀況的程序。
實作
我們將按照 //third_party/googletest 建立的模式，為 RE2 程式庫建立滾動器。系統會建立 //third_party/re2/OWNERS 檔案，指定負責維護此輪替工作的人員。初始擁有者會是 tombergan@google.com。部署此測試版並將 //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 對問題程式碼而言並非問題。舉例來說，如果規則運算式是在主機工具中使用，或是只用於開發人員工作流程 (而非正式版版本)，那麼 DoS 頂多會造成開發人員困擾，而非安全性問題，因此可以核准例外狀況。
例外狀況會記載在許可清單中。每個許可清單都必須包含連結至此 RFC 的註解，以便讀者瞭解相關背景。如要申請例外狀況，您必須上傳 CL 來修改適當的許可清單。CL 必須提供例外狀況的詳細原因，且必須獲得 FEC 成員核准。允許清單分為兩種：
我們的 clang-tidy 型提交前規則會在 Fuchsia 來源樹狀結構中的 TBD 位置建立許可清單。允許清單的位置會記錄在預先提交規則的錯誤訊息中，因此只要執行一般預先提交作業，即可找到該清單。
第三方程式庫例外狀況是由定義程式庫的 BUILD.gn 檔案中的一般
visibility許可清單控制。
未經 FEC 成員核准，就無法將新的規則運算式程式庫匯入 //third_party。匯入後，程式庫必須包含可見度許可清單，以及連結至此 RFC 的註解。
成效
由於這項提案禁止使用最糟糕的指數時間程式庫，因此對效能有正面影響。
程式碼大小
fxrev.dev/532721 會分析 ARM64 版本的程式碼大小預期變更。由於 Go 和 Rust 程式沒有任何變更，因此這些程式的程式碼大小也不會改變。針對 C++ 程式，程式碼大小的增加量取決於 RE2 是透過靜態還是動態方式連結。目前，Fuchsia 主機工具會以靜態方式連結，而目標程式則會根據程式碼大小影響，以靜態或動態方式連結。使用靜態連結後，C++ 程式的大小會增加至少 180 KB。透過動態連結，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。為確保這些工具不會在變更後發生問題，我會將這些工具的擁有者加入此 RFC 的審查人員。
安全性考量
這項 RFC 將降低規則運算式用於 DoS 攻擊的可能性。
隱私權注意事項
無。
測試
系統會執行現有的測試。沒有要測試的新功能。
說明文件
如上所述，提交前和顯示規則會連結至此 RFC，讓開發人員瞭解匯入作業遭拒的原因。新第三方程式碼的審查人員必須瞭解此 RFC，才能拒絕匯入未核准的規則運算式程式庫。包括直接包含 <regex> 或 <regex.h> 的 C++ 和 C 程式庫。
缺點、替代方案和未知事項
請參閱「回溯相容性」。其他 C++、Rust 或 Go 程式庫可能會提供同等保證。我們選擇 RE2、正規表示式和正規表達式，是因為這些工具已廣泛使用，且已匯入 Fuchsia 的 //third_party。
這些程式庫日後的版本可能會引入非線性時間功能，但風險不大。由於這些程式庫宣傳線性時間比對為核心功能，我們認為這種情況不太可能發生，但如果發生，我們就需要選取新的程式庫。
既有技術與參考資料
請參閱動機部分的參考資料，特別是 Russ Cox 的文章，其中介紹了 Google 開發 RE2 的歷史和動機。