ABC Tools

Regex Backtracking, Explained

After reading this you will know why a pattern like (a+)+b can hang a server, how to count the steps a backtracking engine takes, and how to spot and fix the shape that causes the explosion.

What backtracking is, with one hook

Most regex engines you use every day (Perl, Python's re, Java's java.util.regex, and JavaScript's RegExp) work by trying one possible match, and when it fails, undoing the last choice and trying the next. That undoing is backtracking. The engine keeps a stack of decision points so it can rewind.

For most patterns this is fast. The trouble starts when a pattern gives the engine many ways to match the same text, and the text does not match. Then the engine must try every combination before it can declare failure.

The classic hook is (a+)+b against a string of a characters that ends in something other than b, for example aaaaaaaaaaaaaaaaX. There is no b, so the match must fail. But before it can fail, the engine tries every way to divide the run of as between the inner a+ and the outer +. With 16 as that is 2^{16} = 65536 divisions. Add one a and the work doubles. This is catastrophic backtracking, and it is the mechanism behind real ReDoS (regular expression denial of service) outages.

When to reach for this tool

Use the visualizer when a regex is slow and you do not know why, when you want to prove to a teammate that a pattern is dangerous, or when you are learning how backtracking engines actually search. Feed it a suspect pattern and a non-matching input, then watch the step counter.

Do not use it as a compatibility checker for your production engine. The engine here supports a deliberate subset: literals, ., character classes like [abc] and [^a-z], groups, alternation with |, the quantifiers *, +, ?, and escapes like \d \w \s. It has no anchors, no backreferences, and no lazy quantifiers. That subset is enough to reproduce every classic catastrophic case, and leaving out backreferences keeps the engine honest about the pure backtracking cost.

Engines built on a DFA (RE2, Go's regexp, and grep) never backtrack. They track every possible state at once and run in time linear in the input length. The price is that they cannot support backreferences. If you control the engine choice, this is the safest fix for a ReDoS-prone pattern.

The math behind the explosion

The reason (a+)+b blows up is ambiguity. A run of n identical characters can be split among nested unbounded quantifiers in exponentially many ways. Think of it as choosing where to place dividers in a row of n items. Each gap between two as can either close the inner group or not, giving n-1 independent binary choices.

S(n) \approx C \cdot 2^{n}

Here S(n) is the number of steps the engine takes on an input of length n, C is a small constant that depends on the pattern and the engine's bookkeeping, and 2^{n} is the exponential growth. The key property is the ratio between consecutive lengths:

\frac{S(n+1)}{S(n)} \approx 2

Every extra character roughly doubles the work. That is the fingerprint of catastrophic backtracking. A pattern that runs in linear time would show S(n+1) - S(n) roughly constant instead. A quadratic pattern (a single unbounded quantifier followed by a failing literal, like a+b is not, but .*a.*a style constructions can be) grows like n^2, which is slow but survivable.

A worked example on the demo data

Counting steps for (a+)+b on aaaaaaaaaaaaaaaaX

Load the default pattern (a+)+b and the default input aaaaaaaaaaaaaaaaX (16 as then one X), then step through.

  1. The outer + runs the inner group at least once. The inner a+ greedily grabs all 16 as.
  2. The outer + tries to repeat, but the next character is X, not a, so the group cannot start again. The engine now needs b. It sees X. Failure.
  3. The engine backtracks: the inner a+ gives back one a (matching 15), letting the outer + run the inner group a second time to match the last a. Then it looks for b, sees X, fails again.
  4. Each new failure forces a different partition of the 16 as. There are 2^{15} ways to place dividers among 15 gaps, and the engine tries them all before giving up.

Run it and you will see the step counter climb past tens of thousands. Now delete one a so the input has 15. The step count roughly halves. Add two as back and it roughly quadruples. That doubling is the whole story.

The step count doubles with every extra character. At n = 20 the engine takes over a million steps to prove the match fails.

With (a+)+b and no trailing b, the step count is about 2^{n} for n input characters: 8 characters take about 256 steps, 16 take about 65536, and 24 take about 16 million.

Reading and interpreting the results

The visualizer shows four things at once: the current position in the pattern, the current position in the input, the depth of the backtrack stack, and a running step counter. Read them together.

A healthy run has a stack depth that stays shallow and a step counter that ends close to the input length. A dangerous run has a step counter that keeps climbing long after you would expect a decision, and a stack depth that grows and shrinks in waves as the engine explores partition after partition.

The plot mode is the fastest diagnosis. It measures steps against input length and draws the curve. A straight line means linear time and no problem. A curve that bends sharply upward, where each step to the right doubles the height, means exponential blowup. Trust the shape more than any single number.

The engine caps execution with a step budget. When the budget runs out the run aborts with a message instead of freezing your tab. An aborted run is not a bug in the tool: it is the tool telling you the pattern would have kept doubling. In production that same pattern would pin a CPU core until a timeout or a crash.

Common mistakes that create evil patterns

Three shapes cause almost every real ReDoS. Learn to see them.

Nested quantifiers
A quantifier inside a group that is itself quantified, like (a+)+ or (a*)*. The two levels can partition the same characters in exponentially many ways.
Overlapping alternation under a quantifier
Something like (a|a)+ or (a|ab)+, where two branches can match the same text. Each character multiplies the number of match paths.
Adjacent quantifiers on the same character class
A run like \d+\d+ or .*.* before a literal that fails. One quantifier can give characters to the other in many ways, which is quadratic on its own and worse when nested.

The fix is almost always to remove the ambiguity. Rewrite (a+)+b as a+b: it matches the same language and runs in linear time because there is only one way to consume the as. Where your engine supports them, atomic groups or possessive quantifiers stop the engine from giving characters back, which also kills the blowup. If you can switch engines, a DFA-based one removes the whole class of problem.

Related tools on this site

Backtracking is a search over a tree of choices, which puts it next to other structure and algorithm visualizers. If you liked stepping through an engine, the Data Structure Visualizer steps through trees, heaps and tries the same way. For a different flavor of exponential-versus-linear tradeoff, the Bloom Filter Playground shows how probabilistic structures trade accuracy for speed. And if your interest is the operational side, where a slow regex on one request drags down the whole service, the Tail Latency & Autoscaling Simulator shows how one slow path pushes p99 past a cliff.

Frequently asked questions

Why does the regex only get slow when the string does not match?

A successful match can stop at the first path that works. A failing match cannot stop until every path has been ruled out. With a catastrophic pattern the number of paths is exponential, so failure is where the cost lives. That is why attackers craft inputs that almost match.

Is (a+)+b slow in every language?

It is slow in every backtracking engine, which includes Perl, Python, Ruby, Java, .NET and JavaScript. It is fast in DFA-based engines like RE2, Go's regexp, and grep, which run in time linear in the input length. The tradeoff is that DFA engines drop backreferences.

How do I fix a pattern that blows up?

Remove the ambiguity. Collapse nested quantifiers ((a+)+ becomes a+), make overlapping alternation branches disjoint, and avoid two unbounded quantifiers competing for the same characters. If your engine supports atomic groups or possessive quantifiers, use them to forbid giving characters back.

Does the step count equal wall-clock time?

Not exactly, but it is proportional. Each step is a constant amount of work, so a run with 2^{20} steps takes roughly a thousand times as long as one with 2^{10} steps. The doubling in the step count is the doubling in time.

Is anything I paste sent to a server?

No. The engine runs entirely in your browser. Nothing you type or paste leaves your device, and the step budget stops any run before it can lock up the tab.

Try it yourself in the tool

Related tools

Bloom Filter Playground

Add items, watch bits light up, measure the false positive rate.

Cache Replacement Simulator

Animate FIFO, LRU, LFU, CLOCK, ARC and Bélády's OPT on any access sequence.

Consistent Hashing Ring

See why adding a server moves 1/N of the keys, not all of them.

Data Structure Visualizer

Watch BST, AVL, red-black trees, heaps, hash tables, tries and union-find work, step by step.

Digital Logic Gate Simulator

Build circuits from gates and flip-flops, wire them up, and watch the signals flow live.

Git Branching Sandbox

Type git commands and watch the commit DAG, branches and HEAD move — with levels, remotes, undo, and merge-vs-rebase contrast.