非効率な正規表現によるサービス拒否

説明

ReDoSは、非効率な正規表現が過剰なバックトラッキングを起こし、照合時間が急増する問題です。Javaのjava.util.regexはバックトラッキングを使います。(...+)+や(\w+)*のような入れ子の量指定子、(A|.)+のような曖昧な選択肢の繰り返しは、最悪の場合に指数時間を要します。細工した長い入力でリクエストのスレッドやCPUを占有される可能性があります。Java 9以降には一部の緩和策がありますが、複雑なパターンでは危険が残ります。

想定される影響

リクエスト処理の応答停止やサービス拒否
CPU、スレッドプール、リクエストキューの枯渇
アプリケーション全体の遅延やタイムアウトの増加
障害の隔離が不十分な場合の依存サービスへの影響拡大

対処方法

重複する選択肢を除去するか、明確な文字クラスを使って曖昧さをなくしてください。
(a+)+や(\w+)*のような入れ子の繰り返しを単一の繰り返しに簡略化してください。
受け入れる文字列が変わらないか確認したうえで、アトミックグループ(?>...)や所有的量指定子*+、++、?+を検討してください。
照合前に入力の最大長を制限してください。
線形時間での照合が必要なら、構文の違いを考慮してRE2Jなどを検討してください。
実際に資源制限を強制できるエンジンやプロセス境界を使ってください。Javaのスレッド割り込みだけでは、正規表現の実行終了を保証できません。

例

変更前

java

import java.util.regex.Pattern;

public class IdCheckerVulnerable {
    // 入れ子の量指定子 (\d+)+ は不一致時に過剰なバックトラッキングを起こし得る
    private static final Pattern VULN = Pattern.compile("^(\\d+)+$");

    public boolean isNumericId(String input) {
        if (input == null) return false;
        return VULN.matcher(input).matches();
    }
}

変更後

java

import java.util.regex.Pattern;

public class IdCheckerSafe {
    private static final int MAX_LEN = 256; // 入力長の上限
    // 方法1: 入れ子の繰り返しを除去
    private static final Pattern SAFE = Pattern.compile("^\\d+$");
    // 方法2: 所有的量指定子 "^(\\d++)$" で不要なバックトラッキングを防ぐ

    public boolean isNumericId(String input) {
        if (input == null || input.length() > MAX_LEN) return false; // 長さの制限でコストを抑える
        return SAFE.matcher(input).matches();
    }
}

^(\d+)+$は、繰り返すグループの内部にも繰り返しがあります。長い数字列の末尾に文字を付けたような不一致入力では、多数の経路を試す可能性があります。変更後の^\d+$は曖昧さを除き、入力長にも上限を設けます。用途に合う場合は、所有的量指定子やアトミックグループで不要なバックトラッキングをさらに抑えられます。

参考資料

CWE-1333