How to Avoid Catastrophic Regex Backtracking
AIGClub TeamShare
Catastrophic backtracking is usually visible only on a near-matching or failing input that forces the engine to revisit many paths. A short successful sample can hide it.
Avoid nested or overlapping repetition such as (a+)+$ when untrusted input can grow. Replace ambiguous repetition with a narrower token rule or a small parser, anchor the intended field, cap input length and runtime, and test increasingly long non-matches in the exact production engine. A static warning is only a heuristic.
Practical steps
- Compare (a+)+$ on aaaaaaaa! with a linear rule such as ^a+$ when the field may contain only a characters. The exclamation mark forces the nested version to reconsider partitions.
- Increase the failing suffix sample gradually and measure elapsed time in the deployment engine. Set an input-length limit and an execution timeout where the platform supports one.
- Narrow tokens, make alternatives non-overlapping, anchor the field, or use step-by-step parsing when a regex has to model nested structure.
Boundaries and risks
The browser tester blocks a few recognizable nested-quantifier shapes and limits samples to 20,000 characters, but high-risk expressions exist outside those signatures. Passing the check does not prove ReDoS safety, and another engine can use a different matching algorithm.
Recommended workflow
Record the field's maximum length and expected alphabet, run a doubling series of adversarial non-matches, and compare timings before/after any rewrite. Review the calling path too: an otherwise moderate regex can become a service risk when applied repeatedly to large requests.
Frequently asked questions
- Does removing the outer + always fix (a+)+$?
- It fixes that exact nested repetition, but the replacement must still express the field contract. Add anchors, character limits, and near-miss tests rather than applying a mechanical rewrite.
- Can a browser warning certify a backend pattern as ReDoS-safe?
- No. The warning is a small signature check in a different possible engine. Measure the final pattern with production limits and adversarial inputs in the target runtime.
- What evidence should a performance review retain?
- Keep the exact pattern and flags, engine/version, input generator, lengths, elapsed times, timeout, and the threshold used to reject the expression.