1. 導入：なぜこの技術Tipsが重要なのか
Javaで文字列処理を行う際、正規表現は非常に強力な武器です。しかし、不用意に書いた正規表現は、特定の入力によってCPU使用率を100%に張り付かせ、アプリケーションをフリーズさせる「Catastrophic Backtracking（壊滅的なバックトラック）」を引き起こす可能性があります。本稿では、この現象のメカニズムを理解し、実務で安全に正規表現を扱うための知見を共有します。
2. 基礎知識：バックトラックとは何か
正規表現エンジン（Javaのjava.util.regex）は、マッチングに失敗すると「一つ前の状態に戻って別の経路を試す」という再帰的な探索を行います。これがバックトラックです。
問題となるのは、量指定子（ や +）を重ねた「入れ子構造」です。例えば、(a+)+ のようなパターンに対し、一致しない長い文字列を入力すると、エンジンは可能なすべての組み合わせを網羅的に試そうとします。この組み合わせ数が指数関数的に増加し、計算が実質的に終わらなくなる現象がCatastrophic Backtrackingです。
3. 実装/解決策：危ないパターンを排除する
現場で避けるべき代表的なNGパターンは「曖昧な重複」です。
・NG例：(a+)+ や (.)
・解決策：
1. 量指定子を必要以上に重ねない。
2. 可能な限り「非貪欲（Lazy）量指定子（?, +?）」を使用する。
3. 可能な場合は、正規表現ではなく String.split() や indexOf() など、線形時間で動作する標準APIで代替する。
4. 複雑なパターンの場合、Possessive Quantifier（強欲量指定子：+ や ++）を使用して、バックトラックを抑制する。
4. サンプルプログラム：危険なコードと安全な代替案
以下は、バックトラックが発生しやすいケースと、それを安全に書き換えた例です。
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class RegexSafetyDemo {
public static void main(String[] args) {
// 危険なパターン：(a+)+ は入力が長くなると指数関数的に計算量が増加する
String dangerousRegex = "(a+)+";
String input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaab"; // 最後にマッチしない文字を入れる
// 安全なパターン：量指定子を重ねず、単一の量指定子で表現する
String safeRegex = "a+";
// 実行時間の計測（簡易的）
long start = System.currentTimeMillis();
Pattern pattern = Pattern.compile(dangerousRegex);
Matcher matcher = pattern.matcher(input);
// 非常に時間がかかる、あるいはフリーズする可能性があるため注意
System.out.println("マッチング開始...");
boolean found = matcher.find();
long end = System.currentTimeMillis();
System.out.println("結果: " + found + " / 処理時間: " + (end - start) + "ms");
}
}
5. 応用・注意点：現場で陥りやすいバグの回避
実務でさらに安全性を高めるためのポイントを3つ挙げます。
1. タイムアウトの実装: Javaの標準Matcherにはマッチングのタイムアウト機能がありません。外部ライブラリ（Google RE2/Jなど）の使用を検討するか、マッチング対象の文字列長に上限（バリデーション）を設けてください。
2. Named Groupsの活用: 複雑な正規表現になる場合は、Named Groups（(?
3. 入力の事前検証: 正規表現エンジンに渡す前に、String.length() であまりに長い文字列が来ていないかチェックするだけで、DoS攻撃に近い負荷を未然に防ぐことができます。
正規表現は便利ですが、常に「最悪のケース」を想定して設計することが、堅牢なJavaアプリケーションを支える鍵となります。
コメント