How regex engines backtrack, and what regex can't parse

On 2026-10-27 three advisories came out on the same day, all with the same root cause. Symfony’s HeaderUtils::split() (GHSA-r925-mgvr-h9cc, CVE-2026-108082) ^{[1] [4]} could be made to burn close to a second of CPU on a single Cache-Control header. Two Datadog tracers, dd-trace (GHSA-x94g-w73q-hpcw) ^[3] and dd-trace-py (GHSA-3633-r77q-h3v3) ^[2], shipped a default query-string obfuscation pattern that, in their words, “can exhibit excessive backtracking”. Different vendors and different languages, but each one a regex that took a wrong turn and then dutifully tried every other turn too.

Good excuse to open the thing up. Not the “never use .*” folklore, but what a backtracking engine does step by step, how to see the blow-up coming by reading a pattern, what you lose by switching to a linear-time engine, and the kind of input no regex in any engine can handle.

Depth-first, with a stack #

A regex compiles to something like a little program. The engine moves a cursor through the input, and at every choice point (an alternation a|b, a quantifier x*, an optional x?) it takes one branch and pushes the others on a stack. When the branch fails further on, it pops the stack, rewinds the cursor and tries the next option. That’s backtracking: a depth-first search through every way the pattern could match.

When the match succeeds, the engine stops at the first success, so usually it’s cheap. When it fails, the engine has to prove that no path works, and that means trying all of them. Failure is where you pay. With an ambiguous pattern and an input that almost matches, that can take exponential time ^[5].

The classic example:

^(a+)+$

against aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!, n letters a and then a bang. The inner a+ can take any number of as, and the outer + can chop the run into any number of groups. A run of n letters splits into consecutive non-empty groups in 2^(n-1) ways: each of the n-1 gaps is either a cut or not. The ! makes $ fail, so the engine tries every split before giving up. At 30 letters that’s about 5 × 10^8 paths, and every extra letter doubles it.

You can watch it happen with the standard library:

import re, time

for n in range(18, 27, 2):
    s = "a" * n + "!"
    t = time.perf_counter()
    re.match(r"^(a+)+$", s)
    print(n, round(time.perf_counter() - t, 3))

Two more letters, about four times the time. That curve is the entire attack.

Ambiguity, in three flavours #

“Catastrophic backtracking” covers a few recognisable shapes, and they all come from ambiguity: the engine has more than one way to carve up the same substring.

People underestimate the last row. Two adjacent .* on a failing input cost O(n^2), three cost O(n^3). Not exponential, sure. But on a 100 KB header n^2 is 10^10 steps, and that’s an outage too.

Symfony’s bug is the first shape in disguise. The advisory describes a token alternative that also matched whitespace, followed by a (?<!\s) lookbehind, all inside an outer repetition. Put a run of whitespace in front of a separator and the engine can share it out among the iterations in exponentially many ways, and it tried every one before settling. The advisory puts one request at close to a second of CPU, with no authentication needed, because HeaderBag calls the parser whenever a Request is built.

And the attack input is just a run of spaces in a header. A WAF rule hunting for SQL keywords won’t blink at it, and one connection can send it over and over.

Reading a pattern for trouble #

You don’t need a fuzzer for a first pass. Look at the pattern and ask:

• Is there a quantifier on a group that itself contains a quantifier? (x+)+, (x*)*, (x+)*. Suspicious until proven otherwise.
• Under a repetition, can two branches match the same character? (a|a?)+, (\w|\d)+, ([a-z]|\w)*. Overlapping branches give the engine a choice at every character.
• Can the next token also match what the previous quantifier was eating? \s*,?\s* is fine; \s*\s* isn’t. An optional separator that shares characters with its neighbours creates the same ambiguity.

Then test with the right input, which is a failing one: a long run of the ambiguous character with something at the very end that forces a mismatch. Inputs that match come back fast and tell you nothing.

The regex tester works for this. Feed a suspect pattern 25 copies of the ambiguous character plus one that can’t match, and see whether it stalls. Add two more and check whether the time quadruples. If it does, you’ve got an exponential pattern.

Past eyeballing, automate it: run the pattern on failing inputs of increasing length and fit the growth curve. Anything worse than linear gets rewritten.

Fixing the pattern #

To get rid of ambiguity, take away the choice.

Make the branches disjoint. (\w|\d)+ is just \w+. And rather than a token class that also matches whitespace plus a guard against whitespace, leave whitespace out of the token class in the first place.

Collapse nested quantifiers. (a+)+ matches exactly what a+ matches. Nested quantifiers are almost always accidents.

Where your engine has them, use atomic groups or possessive quantifiers. (?>a+)+ and a++ stop the engine from giving characters back, which deletes the alternative paths. PCRE, Java and PHP have both; Python got them in 3.11. JavaScript has neither, but a lookahead plus a backreference emulates an atomic group: (?=(a+))\1.

Cap the length before the regex runs. A length check turns n^2 into a constant. It’s cheap, and when you can’t touch the pattern it’s the first thing to do.

And keep it off the hot path. The Datadog advisories say the obfuscation pattern runs synchronously while URL metadata is recorded, so a slow match stalls the request itself. Their workaround is to override the pattern with a fixed one through the DD_TRACE_OBFUSCATION_QUERY_STRING_REGEXP environment variable. I’d also cap the query string length in front of anything that inspects it.

Linear-time engines, and what they give up #

Or you stop backtracking entirely. RE2 ^[7], and Go’s regexp and Rust’s regex crate which work the same way, compile the pattern to a finite automaton and simulate it. Rather than picking one branch and rewinding when it fails, the engine tracks the set of states it could be in and moves them all forward together, one input character at a time. That set never holds more than m states (m being the pattern size), so matching is O(m × n) for every possible input. A lazily built DFA caches the state sets to make it fast.

No input, however hostile, makes (a+)+$ slow there. What you pay is features: anything that needs to remember what it matched earlier, or to peek around the current position.

Backreferences are the interesting gap. (\w+) \1 matches a repeated word ^[6], and that language isn’t regular, so no finite automaton can recognise it. Matching regexes with backreferences is NP-complete, which is why no engine can offer that feature and a polynomial bound at once. If you need (?<!\s), either rewrite the pattern without it or stay on a backtracking engine and accept the risk.

A Go or Rust service is safe from this particular bug, by the way, but not from a quadratic loop you wrote around the regex, or from a huge pattern compiled from user input. Compile time and memory grow with m, and “linear” means linear in m times n.

What no regex can do #

No amount of engine tuning gets around this one. A regular expression in the formal sense describes a regular language: something a machine with a fixed, finite memory can recognise. A finite automaton has no stack, so it can’t count to an unbounded depth.

So it can’t tell whether parentheses balance. (()()) is fine and (() isn’t, and telling them apart means remembering how many are open, a number with no upper limit. The pumping lemma makes that precise. For any regular language there’s a length p beyond which a string has a middle part you can repeat and stay in the language. Take k ( followed by k ). Pump the opening run and the counts no longer match, even though the pumped string would have to stay in the language. Contradiction: balanced parentheses aren’t regular.

HTML has the same problem plus a lot of mess. Pairing each closing div with the right opening one needs a stack, so HTML is context-free at best. Real HTML is worse than that: optional end tags, attributes containing >, comments, script bodies, CDATA, and error recovery that browsers only agree on because the spec defines a state machine for it.

Perl, PCRE and friends added recursion and backreferences, so some of them technically can match balanced structure, (\((?:[^()]|(?1))*\)) for parentheses. That just means the formal limit applies to regular expressions, and the extended engines step past it by giving up the guarantees above. It doesn’t make a regex a decent HTML parser. Injection bugs live in the gap between what your pattern accepts and what the browser actually does.

Use a parser instead. For HTML, one that follows the spec’s tokenizer and tree builder, and for sanitising, an allow-list sanitizer built on top of one. For JSON, a JSON parser; the JSON formatter answers “is this valid?” properly. For URLs, a URL parser; the URL tool shows how a real one splits scheme, host and query.

For anything deeply nested, use a recursive-descent or generated parser, with an explicit depth limit. Symfony’s other advisory that day (GHSA-2v3c-qxhr-7vpv) is the mirror image of the regex bug: a hand-written YAML lexer that recursed once per bracket and crashed on deep nesting. Give a parser nesting and it recurses, so cap the depth.

Regex is great for flat patterns inside a token: checking a slug, pulling a version number out of a line, splitting on a delimiter. If the structure is a sequence, use a regex. If it’s a tree, use a parser.

The short version #

The regex that bites you is rarely one you wrote. In all three of these advisories it was a default pattern in a tracing library or a header parser deep inside a framework, running on input the attacker fully controls. Read the patterns you depend on the way you’d read a loop, and ask what the worst input costs.