Regular Expression Denial of Service (ReDoS): Catastrophic backtracking mechanics and safe regex engines.

Catastrophic Backtracking in NFA Regex Engines

Most programming languages (JavaScript, Python, Java) use Non-Deterministic Finite Automaton (NFA) regex engines. When an evil regular expression contains nested overlapping quantifiers, matching against an input that almost matches causes the engine to evaluate an exponential number of permutations ($O(2^N)$).

Evil Regex: ^(a+)+$

Input: "aaaaaaaaaaaaaaaaaaaaaaaaaaaa!" (28 'a' characters followed by '!')
The engine attempts all combinations of grouping the 'a's:
- Step 1: (28 'a's) -> fails on '!'
- Step 2: (27 'a's) + (1 'a') -> fails on '!'
- Step 3: (26 'a's) + (2 'a's) -> fails on '!'
... Total evaluations: 2^28 = 268,435,456 steps!
Result: Single CPU core pinned at 100% for minutes, freezing the Node.js Event Loop!

Identifying Vulnerable Regex Patterns

Avoid nested quantifiers with ambiguity:

• (a+)+
• (x+x+)+y
• ([a-zA-Z]+)*

Production Solutions

1. Use Linear-Time Deterministic Finite Automaton (DFA) Engines: Google's RE2 engine guarantees execution time linear to input length ($O(N)$), mathematically preventing ReDoS.

import RE2 from 're2';

const safeRegex = new RE2('^(a+)+$'); // Safe from catastrophic backtracking!

2. Set Regex Execution Timeouts: Always enforce timeout limits on dynamic user-supplied regexes.