阅读中文版本

Regex Catastrophic Backtracking — ReDoS Freezes the Server

Fix ReDoS by removing nested quantifiers, validating input length, and using atomic or possessive patterns and linear-time alternatives.

node -e "const r=/^(a+)+$/; const s='a'.repeat(30)+'!'; const t=Date.now(); r.test(s); console.log(Date.now()-t, 'ms')"

grep -rnE "\([^)]*[+*][^)]*\).*[+*]" src/ | head

Symptoms

This guide profiles the failure behind “Regex Catastrophic Backtracking — ReDoS Freezes the Server”. It walks through the observable symptoms, a reproducible diagnosis path, the underlying root cause, the concrete fix, and how to verify the change and prevent a regression.

Observed symptoms include:

• A request with a crafted long string pins the CPU at 100%
• Regex matching time grows exponentially with input length
• The service hangs on certain user input but is fine otherwise

Reproduce and Diagnose

Reproduce the failure in isolation before changing any code. Work through the checks below in order; each one narrows the search space.

Step 1: Find a worst-case input and time it

node -e "const r=/^(a+)+$/; const s='a'.repeat(30)+'!'; const t=Date.now(); r.test(s); console.log(Date.now()-t, 'ms')"

Time growing sharply with length confirms catastrophic backtracking.

Step 2: Audit nested quantifiers

grep -rnE "\([^)]*[+*][^)]*\).*[+*]" src/ | head

Patterns with a quantifier inside a group that is itself quantified are the usual culprits.

Likely contributors, in order of frequency:

• Nested quantifiers such as (a+)+ create exponentially many backtracking paths
• Overlapping alternations allow many equivalent matches
• No bound on input length lets an attacker supply a worst-case string

Root Cause

A backtracking engine explores every way a pattern can match. Nested quantifiers multiply those ways exponentially, so a well-chosen input makes matching time explode and consumes the CPU, denial-of-service style.

The Fix

Remove nested quantifiers, bound input length, use atomic groups or possessive quantifiers where supported, anchor patterns, and switch to a linear-time engine (RE2) for user-facing patterns.

Watch out: Simpler-looking patterns can still backtrack; test any user-facing regex against worst-case inputs.

// ❌ nested quantifier -> ReDoS
// const bad = /^(a+)+$/;

// ✅ no nested quantifier, anchored, bounded
const good = /^a+$/;
const bounded = (s) => s.length <= 1000 && good.test(s);

// validate length before matching user input
if (input.length > 255) throw new Error('input too long');

// or use a linear-time engine (RE2) for untrusted patterns

Verify and Prevent

Re-time the worst-case input and confirm it completes in bounded time; fuzz with long and adversarial strings to confirm no hang.

Once verified, add a regression test that reproduces the original symptom so the failure cannot silently return.

This class of failure is usually environmental rather than pure logic, so capture the exact command, the environment variables, and the working directory in your bug report. Reproduce it in the smallest possible script, then widen the scope only once the minimal case is understood. A short written checklist for this failure mode saves hours the next time it appears.