Regular expression denial of service

Description

ReDoS causes excessive regex backtracking to occupy CPU, delaying or stopping a service. It can arise when user input is interpreted directly as a pattern, or when an application uses an inefficient pattern such as nested quantifiers. An attacker can supply a pattern such as (a+)+$ or (.*)+, or a long input that is expensive to match, tying up request threads.

Potential impact

CPU exhaustion that delays or stops request handling
Worker-thread and connection-pool exhaustion while evaluations run
Increased latency, timeouts, scaling costs and missed availability targets

Remediation

Avoid treating user input as regex source. Select only reviewed fixed patterns, or treat input as ordinary text.
Use Pattern.quote(input) or Pattern.compile(input, Pattern.LITERAL) when metacharacters should have no meaning.
Avoid patterns that cause complex backtracking, including ambiguous nested repetition or problematic backreferences. Bound repetitions where appropriate, for example \d{1,6}.
Limit both pattern and subject length. Java thread interruption does not guarantee termination; use an engine or separate process that can enforce a hard limit when required.
Consider a non-backtracking engine such as RE2J, accounting for compatibility.
Precompile reviewed patterns for reuse. Avoid unnecessary dynamic compilation.
Use non-regex APIs such as String.indexOf or String.replace for simple literal operations.

Examples

Before

java

import org.springframework.web.bind.annotation.*;

@RestController
public class MaskController {
    // User-supplied regex can cause ReDoS
    @PostMapping("/mask")
    public String mask(@RequestParam String rx, @RequestBody String text) {
        // Example: rx = "(a+)+$", text = "aaaaaaaaaaaaaaaaaaaa!" causes costly backtracking
        return text.replaceAll(rx, "***");
    }
}

After

java

import org.springframework.web.bind.annotation.*;
import java.util.Set;
import java.util.regex.Pattern;

@RestController
public class SafeMaskController {
    // 1) Select only reviewed patterns
    private static final Set<String> ALLOW_PATTERNS = Set.of("[0-9]{1,6}", "[A-Za-z]+\"?");

    @PostMapping("/mask")
    public String mask(@RequestParam(required = false) String rx,
                       @RequestParam(defaultValue = "false") boolean literal,
                       @RequestBody String text) {
        if (text.length() > 10000 || (rx != null && rx.length() > 128)) {
            throw new IllegalArgumentException("input too long");
        }
        // Two approaches depending on the intended operation
        if (literal) {
            // 2) Treat input as literal text with Pattern.quote
            String keyword = rx == null ? "" : rx;
            if (keyword.isEmpty()) {
                throw new IllegalArgumentException("empty keyword");
            }
            Pattern p = Pattern.compile(Pattern.quote(keyword));
            return p.matcher(text).replaceAll("***");
        } else {
            // Use only an allowed pattern
            if (rx == null || !ALLOW_PATTERNS.contains(rx)) {
                throw new IllegalArgumentException("invalid pattern");
            }
            // Compile only a reviewed pattern
            Pattern p = Pattern.compile(rx);
            return p.matcher(text).replaceAll("***");
        }
    }
}

The first replaceAll() interprets the request value as regex source. The revised code separates literal search from selection of reviewed patterns and limits input sizes. Adjust these bounds for the application. Pattern.quote() neutralizes pattern syntax; it does not bound input or output size. Precompiling an inefficient pattern does not make it safe either.

References

CWE-1333