gotchajavascriptCritical
Catastrophic backtracking (ReDoS) — regex denial of service
Viewed 0 times
ReDoScatastrophic backtrackingregex denial of servicenested quantifiersafe regex
node
Problem
Certain regex patterns cause exponential backtracking on crafted input, hanging the event loop for seconds or minutes. A pattern like /^(a+)+$/ tested against 'aaaaaaaaab' can take minutes to fail.
Solution
Avoid nested quantifiers on the same character class such as (a+)+ or (a). Use a linear-time regex library like re2 via node-re2 for untrusted input. Audit patterns with safe-regex or recheck.
const bad = /^(a+)+$/; // VULNERABLE
const safe = /^a+$/; // SAFE
const bad = /^(a+)+$/; // VULNERABLE
const safe = /^a+$/; // SAFE
Why
When a greedy group can match the same substring in multiple ways, the engine explores every combination on failure, leading to O(2^n) time.
Gotchas
- ReDoS is a real attack vector — never run user-supplied regex on user-supplied input
- The vulnerability is invisible from small inputs — test with long adversarial strings
- Node.js has no built-in timeout for regex execution
Code Snippets
ReDoS vulnerable pattern and safe alternative
// DANGEROUS — exponential on 'aaaaaaaaab'
const vulnerable = /^(a+)+$/;
// Use node-re2 for untrusted input
import RE2 from 're2';
const safe = new RE2('^a+$'); // linear time guaranteedRevisions (0)
No revisions yet.