災難性回溯（catastrophic backtracking）

多數時候 regex 匹配感覺是瞬間的，所以當某個樣式在稍長一點的輸入上突然卡住數秒、數分鐘、甚至永遠時，著實令人震驚。災難性回溯就是這個陷阱的名字：一台回溯式 regex 引擎在天文數字般多的嘗試匹配方式中迷了路，而事實上根本不存在匹配。

它發生在樣式允許同一段輸入以許多重疊的方式分配給重複運算子時，典型如巢狀或相鄰的量詞，例如 (a+)+ 或 (a|a)*。面對一長串 a 後接一個阻止最終匹配的字元，引擎先試一種把 a 分配給各重複的方式；那在結尾失敗；它退回再試另一種分配；那也失敗；而要嘗試的分配數目隨輸入長度呈指數成長。於是一個 30 字元的字串可能逼出約 2^30 次嘗試，凍結整個程式。引擎並沒有臭蟲；它忠實地探索著一棵恰好呈指數巨大的搜尋樹。

這對真實系統很重要：一個草率寫成、用來處理不可信輸入的樣式，會變成阻斷服務的弱點（常稱為 ReDoS），攻擊者送上一個短短精心構造的字串就能耗盡伺服器。誠實的說法是：這是回溯式引擎加上特定樣式的性質，而非正規語言本身的性質：以自動機為基礎的引擎（Thompson NFA 或 DFA，如 RE2 或 grep）在保證的線性時間內匹配同樣那些真正正規的樣式，且不可能發生災難性回溯。解法是避開有歧義的巢狀量詞、使用原子群組或佔有式量詞，或改用線性時間的引擎。