ReDoS
正規表現の計算量を爆発させる攻撃。
正規表現エンジンの多くはバックトラックと呼ばれる動作で文字がマッチするか確かめる。
これが時に指数関数的に計算量を増大させることになる。
有名というかよく挙げられる例は^(([a-zA-Z0-9])+)+$
繰り返しの中に分岐、繰り返しを同じ文字にマッチするように書くと計算量がO(2^n)になる。
O(2n)になるパターンも有りこちらは入力文字数がある程度大きくなると問題になることがある。
こちらのパターンは緩和策として入力文字数を制限することが有効かもしれない。
例
^(((0x(0|[1-9A-Fa-F][0-9A-Fa-f]*))|(([1-9][0-9]*)|0)),?)+$
カンマ区切りの10進数あるいは16進数をマッチしようとする例
111111111111111111111111111111111@をマッチさせようとすると処理に時間がかかる
^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$
メールアドレスかどうか確かめる
aaaaaaaaaaaaaaaaaaaaaaaa!などを与えると時間がかかる
^(([a-z])+.)+[A-Z]([a-z])+$
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!などを与えると時間がかかる
対策
制御できない正規表現(例えばユーザーに与えられたもの)を実行する場合は隔離された環境で実行するかre2など計算量の爆発しない正規表現エンジンを使用する。 バックトラックの回数を制限する(制限の可能なエンジンを使用する)。
自分で正規表現を書かない。
参考