危険な正規表現

ホーム » Java » 危険な正規表現

ほんの数文字との一致評価で無限ループと思えるほどの猛烈な CPU 負荷を生み出す危険な正規表現が存在する。ふとした事で気付き、危うく Bug Parade に投稿するところだったその正規表現について考えてみる。

その危険な正規表現の一番単純で確実な表記はたったこれだけ。

(.*)*^

このポイントはグループの中が評価対象と一致する文字の繰り返しであること (. が確実)、それに加えて最終的に評価対象とは一致しない事 (このため最後に行頭一致 ^ を使用) である。何故これが膨大な負荷になるか、若干推測も入るが文字数の増加に対するグループ化パターンを考えてみよう。

"1"
  (1) → NG

"12"
  (1) (2) → NG
  (12) → NG

"123"
  (1) (2) (3) → NG
  (12) (3) → NG
  (1) (23) → NG
  (123) → NG

"1234"
  (1) (2) (3) (4) → NG
  (12) (3) (4) → NG
  (1) (23) (4) → NG
  (123) (4) → NG
  (1) (2) (34) → NG
  (12) (34) → NG
  (1) (234) → NG
  (1234) → NG

1 文字増えると評価の組み合わせパターンが 2 倍になる事が分かるだろうか。16 文字なら 65,536 パターン、32 文字なら 4,294,967,294 パターンの評価が必要となる。つまり評価対象の文字数を n とすると O(2ⁿ) という猛烈なオーダーで負荷が増えるのである。

実際に計測してみると文字数に対して倍々で増えてゆくのが分かるだろう。以下のグラフは Core 2 Duo T7200 2GHz で実行した時の Pattern#matches() から処理が戻るまでに要した時間である。25 文字前後という極めて現実的な文字数からかなり非現実的なコストとなるのが分かる。

さらにグループと繰り返しをネストする事で破壊力は増加する。どういった組み合わせでパターンを作っているかはよく分からないが、実験的に ((.*)*)*^ で O(4ⁿ)、(((.*)*)*)*^ で O(10ⁿ) 程度の増加が見られる。((((((.*)*)*)*)*)*)*^ などはもはや 3 文字以上は完全に無応答状態である。

またこれは Java 固有の問題ではなく正規表現の特性である。つまり正規表現を実装している別の言語や実装系でも発生する可能性が高い。賢い実装なら最後尾の不一致で早々に結論付けるのかも知れないが、^ ではなく A で、さらに部分一致など、表現が複雑化すれば対処のしようが無いのではないだろうか。

とにかくユーザに正規表現の入力を許しているようなシステムはこれが DoS 攻撃の手段となり得る事が分かるだろう。それどころか攻撃の意図は無くても同様の効果をもたらす類似パターンを書いてしまう事もあり得る。スパムメールやスパムコメントのフィルタリングに正規表現を許可しているシステムは無いだろうか。ああ、FC2 だ (笑)

ウチの正規表現確認ツールも考えたほうが良いかもしれないな…