How to Use a Regex Railroad Diagram to Detect ReDoS in Complex Patterns

Your production server just hit 100% CPU, and it started with one regex

It is 2:47 in the morning and the checkout service is timing out. You SSH in, run top, and see a single Node.js process pinning one core. No memory leak, no runaway loop in application logic. Just one regular expression match sitting there, chewing through CPU cycles.

The line is a name validator:

validator.isMatch(userInput, /^(\w+\s?)+$/)

Forty-two characters. It is meant to accept one or more words separated by optional single spaces. Instead it took down a service handling thousands of transactions an hour, because a user pasted a long string that did not match.

That is ReDoS — regular expression denial of service. This article is about catching it before production does, using the one view that makes the failure mode obvious: a railroad diagram. I ran the pattern above against real inputs on the same JavaScript engine this site's debugger uses, and the numbers are below.

Why a complex pattern hides an explosion

Most regex engines, including the one in every browser and in Node, use backtracking. When a match fails, the engine does not give up — it rewinds and tries a different way of dividing the input among the pattern's parts.

That works fine until a pattern has more than one way to divide the same text. In (\w+\s?)+ there are two nested variable-length quantifiers: \w+ inside a group that is itself repeated by +. Feed the engine a string of word characters followed by one character that cannot be matched, and it will try every possible split of those characters between the inner \w+ repetitions before concluding that the whole match fails. The number of splits grows exponentially with the length of the input.

The pattern is not wrong about what it accepts. It is wrong about how many ways it will try to get there. Nothing in the source text says that. A railroad diagram does.

What a railroad diagram actually shows you

A railroad diagram is drawn directly from the parsed syntax tree of the pattern, not from its characters. Each node type becomes a shape:

- A sequence is a row of boxes connected by arrows, read left to right. - An alternation is a set of parallel branches that split and rejoin. - A repetition is the atom it repeats with its quantifier written beside it — *, +, ?, {3}, {2,} or {2,5} — plus a separate mark when the quantifier is lazy. - A group is a labeled container, and the label tells you which kind it is: a capture group shows its number or name, a non-capturing group shows ?:, and lookarounds show ?=, ?!, ?<= or ?<!.

This is what makes the diagram worth the screen space. Reading (\w+\s?)+ character by character, the nested quantifier is two symbols, + and +, separated by a parenthesis. Reading it as a diagram, it is a repetition whose contents are themselves a repetition. The structure is the same information, but one form makes the relationship visible and the other does not.

Reading the visual signature of a nested quantifier

Look for a loop that contains a loop. Not a loop that follows another loop — those are sequential and harmless — but a repetition box whose inner content is itself a repetition box.

(\w+\s?)+ draws as a repetition wrapping a group, and inside that group \w+ is another repetition. Two levels of "one or more" stacked on the same stretch of input is the entire vulnerability. The engine has to decide where the inner repetition stops and the outer one continues, and on failure it tries every combination.

Once you have seen the shape, three variants become easy to recognize:

- Loop in loop. (\w+\s?)+, (a+)+, ([a-z]+)*. - Ring with two arms reaching the same place. (a|aa)+ — a repeated alternation whose branches can both consume an a. - Ring with an empty gap. (a|)+ — a repeated alternation where one branch can match nothing at all, so the repetition can spin without consuming input.

The three shapes the detector flags

The debugger on this site does not rely on you spotting the shape by eye. Alongside the diagram it runs a static check over the parsed tree and reports three specific constructions, each with the reason attached:

- Nested quantifier — an unbounded repetition contains another variable-length repetition, so the engine retries exponentially many splits on long input. - Alternation with an empty branch — an unbounded repetition contains an alternation where a branch can match empty, which leaves an infinite backtracking surface. - Overlapping alternation branches — two branches of a repeated alternation can start with the same character, so the engine must try both orders whenever the overall match fails.

The distinction matters because the fixes differ. A nested quantifier usually needs the inner repetition removed or the outer one anchored. Overlapping branches need the alternation disambiguated. An empty branch needs a guard. The diagram tells you which one you have; the detector names it.

Measured: how fast it degrades

These are real timings, taken on the same V8 engine that runs the debugger and that will run your server. The input is a string of a characters followed by a single !, which forces a full failure. Each figure is the fastest of five runs after warm-up, in milliseconds:

Both nested-quantifier patterns multiply their cost by almost exactly 4.00 for every two characters added. That ratio is the signature of exponential backtracking: double the input, square the work. Twenty-six characters of input costs 286 milliseconds; twenty-eight costs 1,154. At 100 characters the pattern did not return before the measurement process had to be stopped.

The overlapping-alternation pattern, (a|aa)+, is also exponential but with a much smaller base — 3.42 ms at 26 characters rather than 286. It is still a vulnerability, just one that needs a longer input to bite, and it is the case that a purely visual review is most likely to wave through.

The last column is the rewritten pattern, and it is flat at the resolution of the timer all the way to 2,000 characters, where it runs in 0.0044 ms. Removing the ambiguity did not make the pattern merely faster; it changed its complexity class.

Fixing the pattern

The measured table above compares the vulnerable pattern with ^\w+(?:\s+\w+)*$, which accepts the same shape of input without offering the engine multiple ways to split it. Instead of repeating a group that ends in an optional space, it requires a word, then zero or more "whitespace followed by a word" pairs. There is exactly one way to divide the text, so failure is discovered once rather than explored.

Two semantic notes before you swap it in. The rewritten pattern does not accept a trailing space, so trim the input first. And it accepts two or more spaces between words, where the original allowed at most one — a widening of the accepted language rather than a narrowing, so it will not reject anything the old pattern accepted on that count.

If you cannot restructure the pattern, be aware of what JavaScript does not offer. There are no possessive quantifiers and no atomic groups, so the advice you will find in older references — "use (?>...)" or "use a++" — cannot be typed into a JavaScript regex at all. The closest available workaround is to emulate an atomic group with a lookahead and a backreference: (?=(a+))\1 captures a run of a characters without consuming them and then re-matches exactly that text, which denies the engine the chance to try a shorter split. It works, it is hard to read, and it is a last resort after structural fixes have been considered.

Why the debugger also cuts execution off

Static detection has a blind spot: whether a given pattern is slow depends on the input, and the input is written by users. So the debugger on this site does not stop at analysis. Execution has a 100 millisecond budget, and when the text being tested is longer than 5,000 characters it first probes with the opening 2,000 characters. Breach the budget and the run is halted rather than allowed to finish, with a panel explaining that the pattern and input combination shows exponential backtracking.

That behavior is worth copying. A pattern that is merely suspicious is a code review comment; a pattern that is confirmed slow on real input is a production incident. Your own code can implement the same circuit breaker by timing the match and refusing the request when it exceeds a fixed budget, rather than trusting that the regex was reviewed.

A checklist before you ship a pattern

- Draw the diagram and look for a loop whose contents are another loop. - Check every repeated alternation for branches that can start with the same character, and for branches that can match empty. - If a pattern failed review, fix the structure rather than reaching for lookaround tricks. - Time the pattern against a long non-matching input — the failure case is the expensive one, not the success case. - Keep a runtime budget on any pattern you apply to user-supplied text, so a missed case degrades one request instead of the whole service.

The 2:47 AM incident did not happen because someone wrote a regex without thinking. It happened because the pattern looked reasonable in text and the failure mode is invisible in that form. A railroad diagram is not a guarantee, but it turns a class of bug that is normally found in production into one that is found while you are still looking at the editor.