Denial of service from inefficient regular expressions

Description

ReDoS occurs when inefficient regular expressions cause excessive backtracking and sharply increasing match times. Java's java.util.regex engine uses backtracking. Nested quantifiers such as (...+)+ or (\w+)*, and repeated ambiguous alternatives such as (A|.)+, can take exponential time in the worst case. Crafted long input can occupy request threads and consume CPU. Java 9 and later mitigate some cases, but complex patterns can remain vulnerable.

Potential impact

• Unresponsive request threads and denial of service
• CPU exhaustion and depleted thread pools or request queues
• Increased latency and timeouts across the application
• Failures propagating to dependent services when isolation is inadequate

Remediation

• Rewrite ambiguous patterns by removing overlapping alternatives or using explicit character classes.
• Simplify nested repetitions such as (a+)+ or (\w+)* into a single repetition.
• Consider atomic groups (?>...) or possessive quantifiers such as *+, ++ and ?+ after checking that the accepted language remains correct.
• Enforce a maximum input length before matching.
• Consider an engine such as RE2J when linear-time matching is required, accounting for syntax differences.
• Enforce resource limits through an appropriate engine or process boundary. Interrupting a Java thread does not guarantee that regex execution stops.

Examples

Before

import java.util.regex.Pattern;

public class IdCheckerVulnerable {
    // Nested quantifiers: (\d+)+ can backtrack excessively on a mismatch
    private static final Pattern VULN = Pattern.compile("^(\\d+)+$");

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

After

import java.util.regex.Pattern;

public class IdCheckerSafe {
    private static final int MAX_LEN = 256; // Maximum input length
    // Option 1: remove the nested repetition
    private static final Pattern SAFE = Pattern.compile("^\\d+$");
    // Option 2: possessive quantifier "^(\\d++)$" prevents unnecessary backtracking

    public boolean isNumericId(String input) {
        if (input == null || input.length() > MAX_LEN) return false; // Bound the cost with a length limit
        return SAFE.matcher(input).matches();
    }
}

The original ^(\d+)+$ has a repeated group containing another repetition. A long nonmatching input, such as digits followed by a letter, can require many backtracking attempts. The revised ^\d+$ removes that ambiguity and caps the input length. Possessive quantifiers or atomic groups may further prevent unnecessary backtracking where their semantics fit the requirement.

References

• CWE-1333