Static detection of DoS vulnerabilities in programs that use regular expressions という論文を眺めた
ReDoS が起きる (backtracking regexp engine で時間計算量が Ω(2**n) や Ω(n**2) や になってしまう) NFA の形が明確に書いてあった
指数関数的になるのが Fig.4 で、2乗になるのが Fig.6
指数関数的になるのは同じ状態にふたつ (以上) のループがついている形で、 2乗になるのはふたつのループが並んでいる形
たしかにそういう形ならそういう計算量になるだろうな、と思う
(また、そういう計算量になるのはそういう形が NFA に含まれているときだけ、とも書いてあるが、 こちらは簡単に納得できる話ではなく、証明は読んでいない)
論文にはそれだけじゃなくて、プログラムの外から与えられるデータが実際に正規表現とのマッチにたどりつけるかとかも がんばって解析している
[latest]