hysryt
commented
4 years ago ReDoS
正規表現の不備をついたDos攻撃。
例えば (a+)+ という正規表現の場合 aaaab を対象の文字列としたとき処理時間が長くなる。
対象文字列のaを増やせば増やすほど処理時間は長くなる。
対象の文字を自由に指定できるサービスにおいて、正規表現に不備があるとReDoS攻撃が成立する。
開発者側で
- 正規表現を書き換える
- バックトラックの上限を設定する
などをすることで防ぐことができる。
バックトラック
正規表現エンジンの多くはこの手法で検索を行っている。
正規表現の検索では一文字ずつ一致するかどうかを確認しながら進んでいく。
+や*などの量指定子が含まれるとき、できるだけ長く一致することを優先して検索する。 一致しない場合は一致する文字長を一文字ずつ少なくして検索を繰り返す。一致しなかったときに再検索するために前の状態まで戻ることをバックトラックという。
バックトラックの発生が最小限になるように正規表現を書くことがパフォーマンスの向上につながる。