Benchmark — ReDoS
Stock RegExp vs re2js
ReDoS — regular-expression denial of service — is a class of bug where a regex with nested quantifiers takes time exponential in the input length. Any system that accepts user-defined regex (alert filters, log redaction rules, custom search patterns) is one accidentally-pathological pattern away from a stuck CPU. This page runs ten documented ReDoS patterns against stock JavaScript RegExp and against re2js (a pure-JS port of Google’s linear-time RE2 engine) so you can see the difference instead of having to take our word for it. For the long-form explanation of how we apply this in production, see How we built a no-ReDoS customer regex tokenizer.
Methodology
- ·Each cell runs in a fresh Web Worker so the main thread stays responsive when stock RegExp catastrophically backtracks.
- ·Hard 5-second timeout per cell. The page terminates the Worker and reports "TIMED OUT (>5000 ms)" for that cell, then moves on.
- ·Each pattern runs
3times per engine. We report the median, min, and max — single-shot microbenchmarks are too noisy to defend. - ·Inputs are 28–41 characters — just long enough to trigger the pathology. Re-tested empirically before we shipped the page.
- ·Results live in your browser. We don’t collect them. No telemetry, no opt-out toggle, no submit button.
Results
The page does not auto-run. Click below when you’re ready — the run takes about 30 seconds end-to-end, most of which is stock RegExp hitting the 5-second timeout on the worst patterns.
| Pattern | Stock RegExp | re2js | Verdict |
|---|---|---|---|
(a+)+$Nested quantifier — the engine tries every partition of the a-run between the inner and outer +. Exponential in input length. | -- | -- | · RegExp· re2js |
(a|aa)+$Alternation with overlap — both branches match the same input, so every position has two paths and the engine explores both. | -- | -- | · RegExp· re2js |
(.*a){25}$Bounded repetition with greedy .* — the engine backtracks across all 25 iterations looking for a way to satisfy $. | -- | -- | · RegExp· re2js |
^(([a-z])+.)+[A-Z]([a-z])+$The Cloudflare 2019-07-02 outage pattern — nested quantifiers in a "match any character" rule pinned every CPU in their fleet for 27 minutes. | -- | -- | · RegExp· re2js |
^([0-9]+)*$Number-validator gone wrong — `+ inside *` lets the engine partition the digit-run unboundedly when validation ultimately fails. | -- | -- | · RegExp· re2js |
^(([a-zA-Z]+)*)$String-validator gone wrong — same shape as the number case; nested + inside * over a character class explodes when the trailing anchor fails. | -- | -- | · RegExp· re2js |
(a*)*bStar inside star — the textbook Aho-Corasick exponential. No b in the input forces the engine to re-explore every partition. | -- | -- | · RegExp· re2js |
^(a|a?)+x$Alternative repetition — `a?` is a subset of `a`, so the two branches overlap; the engine retries every assignment when x is missing. | -- | -- | · RegExp· re2js |
CVE-style email validatorEmail-validator pattern shipped in real npm packages until CVEs were filed. Looks innocent; backtracks catastrophically on long inputs without a @. | -- | -- | · RegExp· re2js |
(?:.*?){10}xNon-greedy backtracking — lazy quantifier inside a counted repetition forces the engine to try every length expansion to find x. | -- | -- | · RegExp· re2js |
These are real measurements from your browser. Run on a different machine and you’ll get different numbers — but the relative differences will hold. Stock RegExp times grow exponentially with input length; re2js times grow linearly. The math doesn’t care which CPU you have.
The patterns on this page are sourced from documented ReDoS advisories (OWASP, the Cloudflare 2019-07-02 outage post-mortem, published CVEs against npm packages). The implementation in production is the same engine you see running here, in the same Worker harness, with the same timeout semantics.