The Hidden Performance Bomb in Your Regex
Imagine you are searching for a specific word in a book. You start at page 1, read forward, and if you reach the end without finding it, you give up. That is linear — fast. Now imagine a different strategy: you try every possible combination of pages to read in every possible order. That is exponential — catastrophically slow.
Standard regex engines use backtracking: when a match attempt fails, the engine rewinds and tries a different path. For most patterns on most inputs, this is fast. But certain pattern-and-input combinations cause the engine to explore an exponentially large number of paths before concluding there is no match. This is Catastrophic Backtracking, also called a ReDoS (Regular Expression Denial of Service) vulnerability.
How Backtracking Works (and Fails)
Consider this pattern matching a quoted string: ".*"
Feed it a string with a missing closing quote: "This string never closes
The engine's steps:
- Matches
"at position 0. .*greedily matches the entire remaining string (25 characters).- Looks for
". Not found at end of string. - Backtracks:
.*gives up one character. Checks for". Not found. - Backtracks again. Checks for
". Not found. - Repeats for every character in the string.
For a 25-character string, this is 25 steps — still fast. But with nested quantifiers, the complexity becomes exponential. The classic ReDoS pattern:
Pattern: (a+)+b
String: aaaaaaaaaaaaaaaaaaaaaaaaaaac (20 a's followed by c)
The outer + and inner + create overlapping ways to partition the a characters. For 20 as, the engine explores over 1 million paths before failing. At 30 as, it exceeds 1 billion. A single crafted HTTP request containing a long string can pin a CPU core at 100% for minutes.
The Solution: Atomic Groups (?>...)
An atomic group tells the engine: "Once you have matched this group, commit to it. Never backtrack into it, even if the overall match fails."
Standard group: (a+) — engine can re-enter and give up characters
Atomic group: (?>a+) — once matched, the group is locked
Rewriting the dangerous pattern:
Dangerous: (a+)+b
Safe: (?>a+)+b
With the atomic group, when (?>a+) matches all the as, it locks that match. If b is not found, the engine fails immediately rather than exploring alternative partitions.
Practical example — safe quoted string matching:
Dangerous: ".*"
Safer: "(?>.*)"
If the closing quote is missing, (?>.*)" fails in O(n) time rather than O(n²).
Possessive Quantifiers: Shorthand for Atomic Groups
Many engines support possessive quantifiers as a cleaner syntax for the same concept:
| Standard | Atomic Group Equivalent | Possessive |
|---|---|---|
\w+ |
(?>\w+) |
\w++ |
\d* |
(?>\d*) |
\d*+ |
[a-z]+ |
(?>[a-z]+) |
[a-z]++ |
The ++ suffix means "match as much as possible and never give any back."
Pattern: \w++@\w++\.\w++
This matches an email address. If any component fails, the engine does not backtrack into the word characters — it fails immediately.
Engine Support for Atomic Groups
| Engine | Atomic Groups | Possessive Quantifiers |
|---|---|---|
| PCRE / PHP | ✅ | ✅ |
| Java | ✅ | ✅ |
Python re |
❌ | ❌ |
Python regex module |
✅ | ✅ |
| JavaScript | ❌ | ❌ |
Go regexp |
❌ (RE2 — immune by design) | ❌ |
Go's regexp package uses the RE2 algorithm, which guarantees linear-time matching by construction. It achieves this by not supporting backtracking features at all — including atomic groups, lookarounds, and backreferences. The trade-off is that some patterns expressible in PCRE cannot be written in RE2. For most operational use cases, this is an acceptable constraint and a significant safety advantage.
When to Apply Atomic Groups
Apply atomic groups when:
- You have nested quantifiers:
(\w+)+,(\d+\s*)+,([a-z]+[0-9]*)+ - You are matching against untrusted input: API request bodies, log lines from external systems, user-supplied search strings
- The pattern must fail fast on non-matching input: A pattern that takes 10ms on matching input but 10 seconds on non-matching input is a latency time bomb
A quick test: if your pattern contains a quantifier inside another quantifier and the characters they match overlap, you have a potential ReDoS. Rewrite with atomic groups or possessive quantifiers.
ReDoS is a real production incident category. Interviewers at companies running high-traffic services sometimes ask: "How would you audit a codebase for ReDoS vulnerabilities?" A strong answer covers three points: (1) statically scan for nested quantifiers with overlapping character classes using a tool like vuln-regex-detector or manual review; (2) test suspicious patterns against long non-matching strings and measure execution time; (3) prefer RE2-based engines (Go's regexp, Google's RE2 library) for any regex applied to untrusted input, accepting the trade-off of losing backreferences and lookbehinds.