ReDoS Regex Debugger: Stop 10-Second Login Form Hangs

A passing test suite tells you nothing about ReDoS

Correctness testing and safety testing are different activities that happen to use the same tool. A pattern can match every valid address, reject every invalid one, and still be unusable against a crafted input, because the tests you ran were short and the input you eventually receive will be long.

That gap is the whole vulnerability. Catastrophic backtracking is not a wrong answer; it is a correct answer that takes exponentially longer to produce as the input grows. Nothing about a green test run detects it, because a green test run uses eleven characters.

The three shapes a static analyzer looks for

A regex debugger that inspects the parsed pattern rather than only running it can flag the structural causes. There are three, and they are worth knowing by name because each has a different fix.

• Nested quantifier. An unbounded repetition contains another variable-length repetition, as in (a+)+. The engine cannot know which inner repetition should absorb which characters, so on failure it retries every possible split.
• Alternation with an empty branch. An unbounded repetition contains an alternation where one branch can match nothing, as in (a|)+. A branch that can match empty gives the engine a path that consumes nothing and can be taken again, which makes the number of distinct paths unbounded rather than merely large.
• Overlapping alternation branches. Two branches of a repeated alternation can begin with the same character, as in (a|aa)+. On failure the engine has to try both orderings at every position.

All three share one precondition: the outer repetition must be unbounded. Change + to a bounded {1,3} and the exponential surface collapses, because the engine can enumerate the possibilities. That single observation is why "just cap the repetition" is often the cheapest safe edit.

Measurement: the doubling signature

Static flags are a hypothesis. The confirmation is a timing curve, and the curve has a very specific shape. Here is a genuinely vulnerable pattern, /(a+)+$/, tested against a string of n a-characters followed by a b that forces the match to fail:

Read the last column. Each additional character doubles the work, which is the fingerprint of 2^n. Extrapolate honestly: 35 characters reaches roughly 4.5 minutes, and 40 characters reaches about 2.4 hours. A login form that accepts an email address will happily pass 40 characters to a validator, and a 40-character input is not an attack string — it is a normal typo.

A safe rewrite of the same intent, /(a+)$/, processed 100,000 characters in about 2.8 seconds in the same environment. The vulnerable version could not finish 31. That difference, not the flag, is the finding.

Anchors are not a mitigation

Adding ^ and $ is often recommended as defensive practice, and it does not do what people expect. Measured at an input length of 22 characters, /(a+)+$/ took 34 ms while /^(a+)+$/ took 247 ms — the anchored form was about seven times slower, because anchoring removes the engine's ability to abandon a starting position early.

The correction is not "never anchor". Anchoring is still right for validation, since you usually want to reject a partial match. The correction is that anchoring constrains where a match may begin and says nothing about how many ways the interior can be decomposed. If the interior is ambiguous, the ambiguity is the problem, and only removing it helps.

Four rewrites that remove the ambiguity

• (a+)+$ becomes a+$. The outer repetition was never doing anything: repeating a repetition that already matches greedily adds paths without adding language.
• (\w+\s?)*$ becomes \w+(?:\s\w+)*$. The original allows every combination of "word, optional space" to tile the input; moving the space inside a non-capturing group that must be followed by a word removes the ambiguity.
• (a|aa)+$ becomes a+$. When one branch is a prefix of another, the shorter branch is redundant.
• (a|)+$ becomes a*$. An empty branch inside an unbounded repetition means "this can repeat forever consuming nothing"; deleting it and using * on the outside expresses the same intent without the loop.

When the ambiguity genuinely cannot be collapsed — usually inside a large third-party pattern — the usual substitute in JavaScript is the lookahead emulation of an atomic group: (?=(a+))\1 matches the same text as an atomic group would by committing to the longest match before the engine can backtrack into it. This matters because JavaScript has no possessive quantifiers and no atomic-group syntax, so advice that says "use (?>...)" does not apply to a browser-side tool. You have to emulate it or restructure.

Where the static flag over-reports

Overlapping alternation branches are the weakest of the three signals, and honesty about that is more useful than a clean-looking report. Measured against the same generated input, /(a|aa)+$/ took 10 ms at 22 characters, 11 ms at 28 and 42 ms at 31 — growing, but nowhere near the doubling curve, because modern engines recognize and optimize some simple alternation forms.

The flag is still worth acting on. It identifies a pattern whose safety depends on an implementation detail rather than on the pattern's own structure, and that guarantee disappears the moment the code runs on a different engine — a mobile browser, an older runtime, a server-side validator in a language with a simpler backtracker. The correct reading of a static flag is "measure this and decide", not "this is broken" and not "the analyzer is wrong".

A triage loop you can run in a couple of minutes

• Paste the pattern into a client-side debugger so the parse tree and any structural flags are visible without sending the pattern anywhere.
• Generate the adversarial input: a long run of the character the ambiguous subexpression accepts, followed by one character that makes the overall match fail.
• Time it at two or three lengths and check for doubling.
• Apply the smallest rewrite that removes the ambiguity, then re-time the same inputs.
• Confirm the rewritten pattern still matches the original valid samples before it ships.

The last step is the one that gets skipped, and it is the one that turns a security fix into a production incident. Removing an ambiguity removes language; sometimes it removes input you were relying on. A pattern that is fast and wrong is not an improvement over a pattern that is slow and correct, and the debugger shows both results side by side, which is the only reason it is worth running the loop at all.