正規表現はどのように機能するのか？（バックトラッキングとパフォーマンス）

すべての開発者は、メールの検証や文字列の解析のために、ある時点で 正規表現 (Regex) を使用したことがあるでしょう。

強力で便利なツールですが、たった1つの不適切に書かれた正規表現がサーバー全体をダウンさせる可能性があることをご存知でしたか？

この記事では、正規表現エンジンの内部メカニズムを探り、パフォーマンス問題の主な原因である バックトラッキング について説明します。

1. 正規表現エンジンの種類

正規表現エンジンは一般的に2つのカテゴリに分類されます。

1. DFA (決定性有限オートマトン): テキスト主導で高速ですが、後方参照などの高度な機能のサポートがありません。（例：awk、lex）
2. NFA (非決定性有限オートマトン): パターン主導で機能が豊富ですが、最悪のシナリオでは非常に遅くなる可能性があります。（例：Java、Python、Ruby、JavaScript、およびほとんどの現代言語）

私たちが使用するほとんどの言語は NFA エンジンを採用しています。そして、NFAの核心的なメカニズムが バックトラッキング です。

2. バックトラッキングとは何か？

バックトラッキングとは、正規表現エンジンが一致を見つけられなかった場合に、「戻って別のパスを試す」 プロセスです。

例えば、文字列 A...BC に対してパターン /A.*B/ をマッチさせてみましょう。

1. A にマッチします。（成功）
2. .* は貪欲（greedy）なので、文字列の残り（...BC）を最後まで消費します。
3. 次に B にマッチしようとしますが、文字列の終わりに達しているため失敗します。
4. バックトラッキングが発生: エンジンは .* に最後の文字（C）を諦めさせ（バックトラック）、再試行します。
5. まだ B ではないので、再度バックトラックします。
6. これが B を見つけるまで繰り返されます。

3. 大惨事：ReDoS

パターンが複雑で文字列が長い場合、バックトラッキングのステップ数は指数関数的に増加する可能性があります。

(a+)+（ネストされた量指定子）のようなパターンによって特定の入力の処理時間が爆発的に増加するこの現象は、ReDoS (Regular Expression Denial of Service) と呼ばれます。

攻撃者は、悪意のある文字列をサーバーに送信することでこれを悪用し、CPU使用率を100%に急上昇させ、サービス拒否を引き起こす可能性があります。

ReDoSを防ぐためのヒント

1. ネストされた量指定子を避ける: (a+)+ の代わりに a+ を使用します。
2. 怠惰な（Lazy）量指定子を使用する: .* の代わりに .*? を使用して、必要な分だけマッチさせます。
3. 具体的になる: .*（任意の文字）の代わりに、[^"]*（引用符以外の任意の文字）のような制限された範囲を使用します。

結論

正規表現は諸刃の剣です。

正しく使えば、数十行のコードを1行に変える魔法です。盲目的に使えば、時限爆弾になり得ます。

複雑な正規表現を書くときは、常にバックトラッキングの可能性を考慮し、パフォーマンステストを行う習慣をつけてください。