ほんの数文字との一致評価で無限ループと思えるほどの猛烈な 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) →