RFC-0105：規則運算式程式庫

RFC-0105：規則運算式程式庫
狀態	已接受
區域	一般
說明	限制 Fuchsia 中可用的規則運算式程式庫組合。
問題	77811
變更	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 則是在展開 a{10}b{10} 等建構後，規則運算式 NFA 的大小。不過，許多程式庫都包含擴充功能 (例如「反向參照」)，因而讓這個問題非常嚴重。其他程式庫則採用以指數方式最嚴重的回溯追蹤實作，即使模式未使用反向參照也一樣。這會將規則運算式轉換成向量，用於阻斷服務 (DoS) 攻擊：如果惡意使用者控制模式或字串要比對，使用者可能會觸發指數搜尋，進而消耗 CPU 並導致 DoS。詳情請參閱 Davis 等人、Russ Cox、V8 和維基百科。

截至 2021 年 4 月為止，Fuchsia 使用的規則運算式程式庫可能容易受到阻斷服務攻擊。以下討論 Cuchsia 支援的語言：

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 對記憶體用量設有限制，可避免 O(mn) 中的 m 字詞造成 DoS。自 2021 年 4 月起，這個程式庫已匯入 Fuchsia 的 //third_party，但沒有任何使用者。因此，Fuchsia 的 C 和 C++ 程式碼「可能」較容易受到規則運算式 DoS 攻擊。

Rust

Rust 的 regex Crate 不支援反向參照，可保證 O(mn) 時間比對、將 NFA 繫結至 RE2，因此不容易受到 DoS 攻擊。截至 2021 年 4 月，這是 Fuchsia 中 Rust 程式直接使用的規則運算式程式庫。

Rust 的 regex_automata 建立外掛程式可讓您建立任意 DFA，並且擁有最糟的指數時間和空間使用。截至 2021 年 4 月為止，Fuchsia 程式並未直接使用這個 Crate，但該 Crate 會透過其他 Crate (例如 bstr) 間接使用，也就是透過受限制的方式使用 regex_automata，因此能夠保證最糟的線性時間和常數空間。

查看

Go 的標準 regexp 套件以 RE2 為基礎，因此不受 DoS 影響。截至 2021 年 4 月為止，這是 Fuchsia 中 Go 程式使用的唯一規則運算式程式庫。

飛鏢

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。部署這個 Roller 並將 //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 應該不會對相關程式碼的問題造成問題。舉例來說，如果規則運算式是用於主機工具，或只用於開發人員工作流程的一部分，而開發人員工作流程並未提供，那麼 DoS 就會嚴重成為開發人員的惱人、不對安全性的疑慮，而授予例外狀況 MAY。

例外狀況列於許可清單中。每個許可清單「都必須」包含連結至這個 RFC 的留言，以便讀者提供適當背景資訊。如要申請例外狀況，您必須上傳 CL，修改適當的許可清單。CL 必須詳細解釋例外狀況的理由，且 CL 必須經 FEC 成員核准。許可清單分為兩種：

1. 我們的 clang-ddy 預先提交規則會在 Fuchsia 來源樹狀結構的未定位置中新增許可清單。系統會在預先提交規則的錯誤訊息中記錄許可清單的位置，以便執行一般的預先提交內容找到該位置。

2. 第三方程式庫例外狀況是由定義程式庫的 BUILD.gn 檔案中的一般 visibility 許可清單控管。

未經 FEC 成員的核准，新的規則運算式程式庫無法匯入 //third_party。匯入後，程式庫「必須」包含瀏覽權限許可清單，以及連結至這個 RFC 的註解。

效能

由於本提案會封鎖指數極差的程式庫，因此將對效能有正面影響。

程式碼大小

fxrev.dev/532721 會分析 ARM64 版本程式碼大小的預期變更。由於 Go 和 Rust 程式沒有任何變更，因此這些程式的程式碼大小不會改變。對 C++ 程式來說，增加程式碼大小取決於 RE2 採用靜態或動態連結方式。目前 Fuchsia 主機工具會以靜態方式連結，而目標程式則會依程式碼大小的影響而透過靜態或動態方式建立連結。使用靜態連結時，C++ 程式的大小會增加至少 180 KB。因為採用動態連結，RE2 共用資料庫的費用約為 350 KB。每個系統映像檔可以產生一次費用：在切換至 RE2 之後，使用 <regex.h> 的 C++ 程式將程式碼大小大約會有零變化，而使用 <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 開發歷史和動機。