--- title: "ReDoS Explained: How One Regular Expression Can Freeze a Server" author: "Arpan Singh" published: "2026-11-17T03:25:35.852Z" updated: "2026-11-17T03:25:35.852Z" url: "https://zyvop.com/redos-explained-how-one-regular-expression-can-freeze-a-server-cae6v" canonical: "https://zyvop.com/redos-explained-how-one-regular-expression-can-freeze-a-server-cae6v" tags: ["Denial of Service","Application Security","ReDoS","Regular Expressions","performance"] --- # ReDoS Explained: How One Regular Expression Can Freeze a Server How catastrophic backtracking turns short inputs into server-wide outages—and how to detect, rewrite, and contain dangerous regexes. ![Cover image]() _Why some regexes take twice as long with every extra character, how that took down Stack Overflow and Cloudflare, and the fixes that work, from_ `str.strip()` _to linear-time engines._ Two famous outages had nothing to do with failed hardware or a break-in. On July 20, 2016, Stack Overflow went down because of a regex that trimmed whitespace. On July 2, 2019, a single regex in a firewall rule pushed CPUs to 100% across Cloudflare’s network for 27 minutes. Both were ReDoS, short for Regular expression Denial of Service. The regex was valid and gave correct answers. It just took far too long on one kind of input. This post shows why, with measured timings that double with every extra character. Then it covers how to spot a dangerous pattern and the fixes that work. ## What ReDoS is Most regex engines, including the ones in Python, JavaScript, Java, PCRE and .NET by default, work by backtracking. They try one way to match the pattern. If that fails, they back up and try the next way. This is fast in the normal case. It becomes a problem when a pattern can match the same text in many different ways and the overall match then fails. The engine has to try every way before it can say no. [OWASP]() calls such a pattern an “evil regex”: a group with repetition that contains more repetition, or alternatives that overlap. Its examples include `(a+)+$` and `(a|aa)+$`. ## Backtracking, step by step Take `^(a+)+$` and the string `aaab`. The `+` inside the group and the `+` outside it can split the three a’s in several ways: ```mermaid flowchart TD begin["Match ^(a+)+$ against aaab"] --> w1["Groups: aaa"] begin --> w2["Groups: aa, a"] begin --> w3["Groups: a, aa"] begin --> w4["Groups: a, a, a"] w1 --> f1["$ fails on b"] w2 --> f2["$ fails on b"] w3 --> f3["$ fails on b"] w4 --> f4["$ fails on b"] style f1 fill:#fff4e0,stroke:#d08000,stroke-width:2px,color:#1a1a1a style f2 fill:#fff4e0,stroke:#d08000,stroke-width:2px,color:#1a1a1a style f3 fill:#fff4e0,stroke:#d08000,stroke-width:2px,color:#1a1a1a style f4 fill:#fff4e0,stroke:#d08000,stroke-width:2px,color:#1a1a1a ``` Every split fails, because the `$` can’t match the `b`. With 3 letters there are 4 ways. With n letters there are 2^(n−1), so each extra letter doubles the work. A matching input such as `aaaa` is fast, because the first split succeeds. An attack needs a string that almost matches and then fails at the end. ## Measured: the time doubles with every extra letter I timed `^(a+)+$` against N letters followed by a `b`, in Python and in Node (V8). Each row adds one letter: | Letters | Python | × previous | Node (V8) | | --- | --- | --- | --- | | 20 | 0.042 s | 2.00× | 0.045 s | | 21 | 0.086 s | 2.03× | 0.105 s | | 22 | 0.180 s | 2.08× | 0.188 s | | 23 | 0.374 s | 2.09× | 0.468 s | | 24 | 0.741 s | 1.98× | 0.755 s | | 25 | 1.396 s | 1.88× | 1.457 s | | 26 | 2.935 s | 2.10× | 3.284 s | | 27 | 5.753 s | 1.96× | 6.437 s | | 28 | 11.189 s | 1.95× | not run | From 18 letters upward, each extra letter multiplied the time by about 2, in both languages. Extending that doubling beyond what I ran gives these estimates: | Letters | Estimated time | | --- | --- | | 30 | about 45 seconds | | 32 | about 3 minutes | | 36 | about 48 minutes | | 40 | about 13 hours | | 50 | about 1.5 years | | 60 | about 1,500 years | Forty characters is a short username, and one request is enough to occupy a core for hours. Real patterns hide this shape. OWASP lists an email-validation regex taken from a public regex library. A normal address validates instantly. But with the input `aaaa…!`, my tests took 1.0 s at 24 letters and 4.3 s at 26, doubling with every letter just like the example above. ## Slower, but still an outage: polynomial ReDoS Stack Overflow’s regex wasn’t exponential. According to [its post-mortem](), a regex that trimmed whitespace met a post with about 20,000 consecutive whitespace characters. Trimming sounds harmless, but a pattern like `^\s+|\s+$` rescans the whole run of spaces from every starting position. That makes the time grow with the square of the input. Doubling the length quadruples the time. I measured it on the string `a`, then N spaces, then `b`: | Spaces | Regex | × previous | `str.strip()` | | --- | --- | --- | --- | | 2,000 | 0.025 s | n/a | 2 µs | | 4,000 | 0.086 s | 3.5× | 2 µs | | 8,000 | 0.275 s | 3.2× | 1 µs | | 16,000 | 1.17 s | 4.3× | 1 µs | | 32,000 | 4.49 s | 3.8× | 1 µs | At exactly 20,000 spaces, one trim took 1.74 seconds, against 1.7 microseconds for `str.strip()`. Send enough of those requests and every worker is busy trimming. Adjacent quantifiers over the same characters, such as `^a*a*$`, show the same quadratic growth. It was 4.0× slower per doubling in my test. ## How to spot a dangerous regex Look for these shapes, especially in patterns that run on user input: - **A quantified group that contains a quantifier**, such as `(a+)+` or `(\w+\s?)*`. - **Alternatives that overlap**, such as `(a|a)+` or `(a|aa)+`. - **Adjacent quantifiers over the same characters**, such as `a*a*`, or an unanchored `\s+$`. Here is how the OWASP examples behaved on N letters followed by `!`: ```sql pattern 20 letters 24 letters growth per extra letter ^(a+)+$ 42 ms 740 ms x2.05 ^(a*)*$ 66 ms 1,074 ms x2.01 ^(a|a)+$ 87 ms 1,412 ms x2.01 ^([a-zA-Z]+)*$ 49 ms 791 ms x2.01 ^(a|a?)+$ 364 ms 5,881 ms x2.00 ^(a|aa)+$ 1.6 ms 8.2 ms x1.51 ``` Even `(a|aa)+`, which grows more slowly, is still exponential. Static analyzers such as Doyensec’s [regexploit]() can flag many of these automatically. ## Where it bites ```mermaid flowchart LR attacker["Attacker sends a crafted string"] --> matcher["Server runs a regex on it"] matcher --> engine["The engine backtracks for seconds or hours"] engine --> cpu["One CPU core is pegged"] cpu --> stall["Other requests wait or time out"] style engine fill:#fff4e0,stroke:#d08000,stroke-width:2px,color:#1a1a1a ``` Any code that matches a regex against text a user controls is exposed: - **Validators** for emails, URLs and usernames. - **Parsers** for headers, Markdown and log lines. - **Filters** such as the firewall rule in Cloudflare’s outage. - **Search boxes that accept regex patterns.** If users supply the pattern itself, they can supply an evil one. OWASP calls this ReDoS via regex injection. A single-threaded runtime such as Node stalls every request while one match runs. A multi-threaded server loses one thread per attack request until the pool is empty. ## Fixes Use the first option that fits your case: ```mermaid flowchart TD untrusted{"Does the regex run on untrusted input?"} untrusted -->|"No"| normal["Normal care is enough"] untrusted -->|"Yes"| plain{"Can a string method or parser do the job?"} plain -->|"Yes"| strings["Use it, for example str.strip()"] plain -->|"No"| linear{"Can you use a linear-time engine?"} linear -->|"Yes"| engine["Use RE2, Go, Rust or .NET NonBacktracking"] linear -->|"No"| harden["Rewrite the pattern, cap the input length, add a timeout"] style engine fill:#e6f0fa,stroke:#2b7de0,stroke-width:2px,color:#1a1a1a ``` ### 1\. Don’t use a regex for it Stack Overflow’s post-mortem says it fixed the outage by replacing the regex with a substring function. For trimming, Python’s `str.strip()` took about a microsecond on the same 20,000 spaces that took the regex 1.74 seconds. ### 2\. Use a linear-time engine for untrusted input Google’s [RE2]() matches in time proportional to the input length, whatever the pattern. Go’s `regexp` and Rust’s `regex` follow the same design, and .NET 7 and later offer a `NonBacktracking` option. Cloudflare said it would move its firewall to engines with this guarantee. The trade-off is that these engines don’t support backreferences or lookarounds. Node can try this too. V8 has an experimental linear engine behind a flag, selected with the regex flag `l`: ```javascript // node --enable-experimental-regexp-engine demo.js const text = 'a'.repeat(1_000_000) + 'b'; console.log(new RegExp('^(a+)+$', 'l').test(text)); // false, in about 85 ms ``` On the same pattern, V8’s default engine needed 2.9 seconds for just 26 letters. The linear engine handled a million letters in 85 ms. It is experimental, so don’t depend on it in production. ### 3\. Rewrite the pattern Remove nesting and overlap, so each character can match in only one way. `^(a+)+$` accepts exactly the same strings as `^a+$`, and the rewrite took 11 ms on a million-letter attack string. ### 4\. Use atomic groups or possessive quantifiers Python 3.11 added [both](): `(?>...)` and `a++`. They stop the engine from backing up into a group once it has matched. `^(?>a+)+$` and `^(a++)+$` each finished a million letters in 0.4 ms. They aren’t a cure-all. On the whitespace trim, a possessive version only cut the time from 4.4 s to 1.5 s, because every start position still rescans the run. The real fix is to start only at the beginning of a run: ```python trim = re.compile(r'^\s+|(?7} {seconds:>9.3f} {f"{seconds / previous:.2f}x" if previous else ""}') previous = seconds # 2. the Stack Overflow pattern: the time roughly quadruples when the input doubles trim, previous = re.compile(r'^\s+|\s+$'), None print('\nspaces regex seconds x previous str.strip() microseconds') for n in (2000, 4000, 8000, 16000): text = 'a' + ' ' * n + 'b' seconds = timed(lambda: trim.sub('', text)) print(f'{n:>6,} {seconds:>14.3f} {f"{seconds / previous:.2f}x" if previous else "":>12} {timed(lambda: text.strip()) * 1e6:>14.1f}') previous = seconds # 3. the fixes on a million-letter attack string attack = 'a' * 1_000_000 + 'b' print('\nfixed patterns on 1,000,000 letters') for pattern in (r'^a+$', r'^(?>a+)+$', r'^(a++)+$'): rx = re.compile(pattern) print(f'{pattern:12} {timed(lambda: rx.match(attack)) * 1000:8.1f} ms') ``` Timings vary from machine to machine. My sandbox is a shared VM, and a re-run of this script was up to twice as fast as the tables above. The ratios held, at about 2× per letter and about 4× per doubling, and those are the numbers to look for on your machine. ## Wrapping up ReDoS is a reminder that a regex isn’t a single operation. It’s a small program, and on the wrong input it can take exponential or quadratic time. Keep untrusted input away from backtracking engines where you can, rewrite patterns so each character can match only one way, and cap the length. Then test every regex that touches user input with long, almost-matching strings before an attacker does.