正則表達式效能優化：避免 ReDoS 與提升執行速度
正則表達式雖然強大，但如果撰寫不當，可能會導致嚴重的效能問題，甚至引發正則表達式拒絕服務攻擊（ReDoS）。本文將深入探討正則表達式的效能考量和最佳化策略。
什麼是 ReDoS？
ReDoS（Regular Expression Denial of Service）是一種利用正則表達式引擎的回溯機制，透過精心構造的輸入字串，使正則表達式的比對時間呈指數級增長的攻擊方式。
當正則表達式引擎遇到無法比對的情況時，會進行回溯（Backtracking）。某些正則表達式的回溯次數會隨著輸入長度呈指數成長，導致 CPU 資源耗盡。
危險的正則模式
| 危險模式 | 問題 | 安全替代 |
|---|---|---|
(a+)+ | 巢狀量詞 | a+ |
(a|a)+ | 交替中的重疊 | a+ |
(.*a){n} | 貪婪量詞回溯 | 限制重複次數 |
安全原則：避免使用巢狀量詞（如 (a+)+）和含重疊可能的交替模式。這些是最常見的 ReDoS 漏洞來源。
效能優化技巧
1. 使用非捕獲群組
當你只需要分組而不需要捕獲時，使用 (?:...) 代替 (...)。非捕獲群組不需要儲存比對結果，可以提升效能。
2. 使用原子群組或佔有型量詞
如果你的正則引擎支援，使用原子群組 (?>...) 或佔有型量詞 ++、*+ 可以防止不必要的回溯。
3. 錨定位置
盡可能使用 ^ 和 $ 錨定正則表達式的起止位置，減少引擎需要嘗試的起始位置數量。
4. 優先使用字元類別
使用 [abc] 代替 a|b|c。字元類別的比對效率遠高於交替。
5. 避免過度使用萬用字元
使用具體的字元類別（如 \d、\w）代替 .，可以減少不必要的比對嘗試。
效能測試方法
測試正則表達式效能時，應該使用不同長度和類型的輸入字串，特別是：
- 比對成功的正常字串
- 比對失敗的字串（回溯最多的情況）
- 超長字串
- 重複字元的字串（如 "aaaaaa..."）
測試你的正則效能
使用我們的工具測試你的正則表達式：
立即使用正則表達式測試工具 →結語
撰寫高效能的正則表達式不僅是效能優化的一環，更是安全性的基本要求。透過理解回溯機制和避免危險模式，你可以寫出既高效又安全的正則表達式。
參考文獻
- OWASP Foundation. "Regular expression Denial of Service - ReDoS." OWASP. https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS
- Cox, R. "Regular Expression Matching Can Be Simple And Fast." swtch.com, 2007. https://swtch.com/~rsc/regexp/regexp1.html
- Davis, J. et al. "The Impact of Regular Expression Denial of Service (ReDoS) in Practice." ACM ESEC/FSE, 2018.