Regular Expression DoS (ReDos)
之前 cloudflare 出現大規模 503 的事情 ，所以讓我再好好整理一下會發生 ReDos 的 發生原因。
RegEx (Regular Expression)
RegEx 是基於 有限狀態機 (FSM) 的字串比對方式
Malicious RegEx
ReDos 就是針對有缺陷的表示式來進行攻擊：像是 (a+)+ 這個表示式表示需要尋找多於一組的 (a+)， 其中每一組又有任意多個 a。正常來說需要建立一個狀態機：首先尋找多於一個 a 的子狀態、並重複尋找這個子狀態。
無論設計出哪種 模式 的正規表示法都有機會產生 ReDos：根本的問題在於當 regex 偵測條件但最後發現不符合 (reject) 時，會觸發 backtrack 並回朔前一個字元並持續比對。當在每一次比對時都在前面的 pattern 正確但最後不符合時就會處發。 像是 cloudflare 的例子中，使用到了 .(?:.=.*) 的表示式，當 input 為 x=xx 時，一開始的 .* 因為會盡力比對而將 4 個輸入值是為匹配成功，而下一個 .* 因為沒有字元可以匹配而產生 backtrack，接下來的 = 因為沒有匹配成功而再產生 backtrack。