ほんの数文字との一致評価で無限ループと思えるほどの猛烈な 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) →
![危険な正規表現 - MOYO Laboratory](https://cdn-ak-scissors.b.st-hatena.com/image/square/b81354cce11a49cfebd236165eb21f26356e66ef/height=288;version=1;width=512/https%3A%2F%2Fblog-imgs-35.fc2.com%2Fm%2Fo%2Fy%2Fmoyolab%2Fmandelbrots.png)