Lessons · Regex · catastrophic backtracking
Patterns that never finish
Nested quantifiers like (a+)+ can backtrack exponentially on input that almost matches; a server hangs on one request.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
Real outages (Cloudflare 2019, Stack Overflow 2016) came from a regex on user input.
How to think about it
Avoid nested quantifiers over overlapping sets. Prefer negated classes ([^"]*) to .*?. Anchor. Test with a long almost-matching input.
Worked example
pattern: ^(\w+\s?)*$Nested: \w+ inside ( )*, both can absorb the same characters.
text: 'aaaa...aaa!' (30 a's then !)Millions of ways to split the a's, all tried before failing.
pattern: ^[\w\s]*$Same meaning, one quantifier, instant.
Your turn
Rewrite (\d+)+ safely.
\d
Test a pattern against real text
The trap
It works on your test strings. The dangerous input is the one that ALMOST matches and is long.
Practise catastrophic backtracking on HoneA question on it now, a coding challenge where there is one, and it is remembered for review. Free, no email needed.