Regex 本身已經十分複雜, 但不知道大家有沒有想過, 它的解析引擎和處理機制又是如何實作的呢? 一般來講, Regular Expression 的解析引擎可以分為三種, 一種叫做 DFA (Deterministic Finite Automation, 決定性有限自動機制), 另一種叫做 NFA (Nondeterministic Finite Automation, 非決定性有限自動機制), 還有一種叫做 POSIX NFA。.Net 採用了傳統的 NFA 引擎, 使得它既能兼顧速度與功能, 但缺點就是由於傳統 NFA 只接受它找到的第一個相符比對，它也可能讓其它比對無法被找到 (POSIX NFA 雖然可以找到, 但速度緩慢)...
Regex 本身已經十分複雜, 但不知道大家有沒有想過, 它的解析引擎和處理機制又是如何實作的呢? 一般來講, Regular Expression 的解析引擎可以分為三種, 一種叫做 DFA (Deterministic Finite Automation, 決定性有限自動機制), 另一種叫做 NFA (Nondeterministic Finite Automation, 非決定性有限自動機制), 還有一種叫做 POSIX NFA。.Net 採用了傳統的 NFA 引擎, 使得它既能兼顧速度與功能, 但缺點就是由於傳統 NFA 只接受它找到的第一個相符比對，它也可能讓其它比對無法被找到 (POSIX NFA 雖然可以找到, 但速度緩慢)。
此外, 由於 NFA 引擎採用的是窮盡比對回溯演算法, 在最壞的情況, 如果解析路徑規劃出現問題, 它有可能會重複比對已經比對過的字串。而且, 它的比對時間是依照受測字串的長度而呈指數 (exponential) 方式倍增的。Bryan Sullivan 在 2010 五月號 MSDN 雜誌上寫了一篇專文「Regular Expression Denial of Service Attacks and Defenses」, 在文章中演示了幾個不同的樣式寫法, 其中有些寫法可能會導致比對作業變得意外地冗長。
他舉例, 以下的樣式可以用來比對輸入的字串是否全部為數字:
^\d+$ 或 ^(\d+)$
如果輸入字串為 "123456X", 那麼 .Net 的 Regex 引擎會把這個字串拆解成 6 個子路徑 (如果忽略最後那個不符合樣式的 "X" 的話), 也就是內部會比對六次 (123456, 12345, 1234, 123, 12, 1)。
但是, 如果你因學藝不精 (或暗藏禍心) 而把樣式稍為改變如下:
^(\d+)+$
那麼, 恭喜, 對同一個受測字串 "123456X" 而言, 需比對的子路徑數目會立刻暴增到 32 個 (2 的 6-1 次方)。而且, 如果受測字串變成 "1234567X" (多了一個字), 子路徑數目會變成 64 個 (2 的 7-1 次方)。; 如果變成 "12345678X" (多了兩個字), 子路徑數目會變成 128 個 (2 的 8-1 次方)。, ..., 依此類推。換句話說, 子路徑數目與受測字串的長度之間是呈指數方式倍增的。
萬一受測字串是一個很長的字串, 那麼由於子路徑的數目太大, 那麼結果不外乎兩種, 一種是因運算時間太久而狀似當機, 另一種則是使得系統發生 Stack Overflow 錯誤。
別以為需要非常長的字串才會發生這種問題, 我算過, 一個僅含 30 個字元的字串就會產生 536,870,912 個子路徑。我把上述樣式丟給 Expresso (順便餵給它 "123456789012345678901234567890X" 作為受測字串), 按下 Run Match 按鈕之後, 花了 296 秒才終於運算結束。
相對的, 如果我們採用第一種樣式, 那麼對於 "123456789012345678901234567890X" 這個完全相同的字串, 它產生的子路徑只有 30 個, 瞬間即可完成比對 (在 Expresso 中花費時間是 0.002 秒)。
在 Bryan Sullivan 的文章中, 他認為有問題的 Regex 樣式有可能會變成遭受 DoS (Denial of Service) 攻擊的弱點; 我認同這一點。一般來講, 對於一個具有風險意識的網站設計者而言, 他/她會在 Client 端跟 Server 端都做相同的輸入驗證。換句話說, 我們在 Client 端以 JavaScript 做過輸入驗證之後, 會在 Server 再重複做一次輸入驗證, 而且通常都使用相同的 Regex 樣式。駭客一旦獲知 JavaScript 程式中的 Regex 樣式, 自然可以推斷 Server 端必定也使用相同的 Regex 樣式。
那麼, 如果駭客看出你所採用的 Regex 樣式具有易遭受 DoS 攻擊的「特質」, 那麼他/她有可能會利用這個弱點, 發動潛伏於各地的跳板, 對你的網站輸入特定的字串樣式, 接著就等著 Server 因忙於運算那些無意義的 Regex 比對而自動癱瘓。
當然, 我個人還未聽說有什麼網站遭到過 Regex DoS 攻擊。但無可否認的, 這確實是個潛在的風險。
像 ^(\d+)+$ 這種具有風險的樣式, 其主要的問題在於它使得 Regex 解析引擎產生額外的、重複的、無意義的解析子路徑, 並從而造成根本不需要的冗長運算。Bryan Sullivan 也同時列出了幾個不當的 Regex 樣式:
^(\d+)*$
^(\d*)*$
^(\d+|\s+)*$
^(\d|\d\d)+$
^(\d|\d?)+$
以上幾個樣式其實都指向同一個問題。不過我建議大家不要因此以為只有長得像上述幾個範例的樣式才會出問題; 或許我們在設計樣式的時候就應該多留意其邏輯是否合理, 如此才能避免類似問題的發生。例如, 我們最好能在後端程式中加上受測字串的長度限制。例如, 電話號碼若最長只有十碼, 那麼你就把超過十碼的字串踢掉(當然, 要在送去做 Regex 運算之前就得先踢掉, 而不是之後); 我們最好把這種防呆動作養成習慣。
註: 從 .Net 4.5 之後 Regex 類別在建構式中加入了一個 TimeSpan 型別的選擇性參數, 可以設定運算 timeout 時間。詳情請參考「[Regex] .Net 4.5 中新增的 Regex 建構式參數」一文。
