Debug a regex that keeps causing catastrophic backtracking and freezing
Your regex runs forever. The pattern is the problem.
You paste a regex, run it against a long string, and the page just hangs. Or the log grows for minutes until something kills the process. Chances are you have run into catastrophic backtracking. The engine explores an exponential number of paths and never finishes. This is how to find the culprit and rewrite the pattern so it stops freezing.
Symptoms to look for
Catastrophic backtracking shows up in a few recognizable ways. Timeouts on inputs that look reasonable. CPU pinned at 100% for a single request. A regex that works on short samples but dies on longer ones. They all trace back to the same thing: the pattern keeps re-trying paths the engine has already walked.
Why it happens
- Nested quantifiers like
(a+)+$multiply the number of ways the engine can split a string. - Overlapping alternatives such as
(a|a)+re-test the same characters over and over. - Broad
.*followed by an anchor forces the engine to back off character by character. - The worst cases trigger on strings that almost match but fail at the very end.
How to fix it
Reproduce it safely
Do not debug this against production traffic. Build a small test harness instead.
import re, time pattern = r"(a+)+$" for n in [10, 20, 30, 40]: s = "a" * n + "b" t = time.time() try: re.match(pattern, s) except Exception as e: print(n, type(e).__name__) break print(n, round(time.time() - t, 4))Run it with progressively longer inputs. If the elapsed time jumps from milliseconds to seconds as
ngrows, that is exponential growth, and you have your proof.Where the engine supports it, set a timeout before you test so one bad pattern cannot hang your machine. Keep every test case short and controlled.
Isolate the failing segment
Once you can reproduce the freeze, start shrinking the pattern. Delete pieces until the slowdown disappears, then add the last piece back. The segment you just isolated is the one causing trouble.
Look for the usual suspects when you inspect it:
- Two quantifiers stacked on the same token, like
(x+)+or(x*)*. - Alternatives that overlap each other, like
(ab|a)+. - A
.*or.+before a required suffix or anchor. - A pattern that matches the empty string repeatedly, like
(a?)*.
Compare execution time as input length doubles. Exponential backtracking doubles or worse each time; linear patterns grow only slightly.
- Two quantifiers stacked on the same token, like
Rewrite the dangerous pattern
The fix is usually simpler than you expect. Remove the redundancy.
# Before: exponential backtracking pattern = r"(a+)+$" # After: same intent, linear behavior pattern = r"a+$"Nested quantifiers almost never do what you think they do. One quantifier usually expresses the same language without the explosion.
For patterns that need to match delimited content, replace a broad
.*with a delimiter-specific class:# Before: lazy .* still re-starts at every position pattern = r"<.*?>" # After: only characters that are not > are consumed pattern = r"<[^>]*>"When a bounded range works, use it.
a{1,10}gives the engine a fixed number of paths instead of an unbounded search.If the input is untrusted, a linear-time engine like RE2 is worth considering. Its feature set is smaller, but its runtime does not depend on input length.
Speed up diagnosis with RegexToolBox
Rather than guessing in your editor, paste the pattern into RegexToolBox and test it against a few sample strings. You can watch which part of the pattern matches what, compare the failing case against a working one, and iterate on the rewrite without touching your codebase.
Check what debugging and timeout features the tool exposes before you rely on them for a dangerous pattern. A run that hangs tells you just as much as one that finishes.
Prevent regressions
Once the pattern is fixed, do not stop at one happy-path test. Re-run the adversarial near-misses, the strings that almost matched before. Verify the rewrite in the exact engine your production code uses, not just in your test tool. Add execution limits or input-length caps where the app lets you. Fix it once and the same mistake will walk back in on the next pull request if nobody is watching.
The common pitfalls are easy to trip over:
- Testing only one example, usually the one that worked.
- Assuming a shorter pattern is always safer.
- Forgetting that engine behavior differs between languages.
- Treating a timeout as an input problem when the regex is the bottleneck.
Frequently asked questions
Why does my regex work on short strings but hang on long ones?
Because the number of paths the engine explores grows exponentially with input length. Short strings finish in microseconds, so the problem stays invisible until the input gets longer.
Is (a+)+$ the only pattern that causes this?
No. Any nested or repeated quantifier can, plus overlapping alternatives and broad .* before an anchor. The class of patterns is wider than one example.
Will a different regex engine fix it?
Sometimes. A linear-time engine like RE2 avoids backtracking entirely, but drops backreferences and some lookarounds. If you need those features, rewrite the pattern instead.
How do I know the rewrite is safe?
Test both matching and near-miss strings in the exact engine your application uses, and compare timing before and after. If the near-miss that used to hang now finishes, you are done.
Rule of thumb
Nested quantifiers and overlapping alternatives are the usual cause of a regex that freezes. Reproduce on short controlled inputs, isolate the failing segment, and rewrite it with a single quantifier or a character class. Then test the near-misses again in your real engine before you call it done.