{"schemaVersion":"1.0","type":"TechArticle","types":["Article","TechArticle"],"slug":"redos-explained-how-one-regular-expression-can-freeze-a-server-cae6v","url":"https://zyvop.com/redos-explained-how-one-regular-expression-can-freeze-a-server-cae6v","title":"ReDoS Explained: How One Regular Expression Can Freeze a Server","subtitle":"How catastrophic backtracking turns short inputs into server-wide outages—and how to detect, rewrite, and contain dangerous regexes.","tldr":"A valid regex can still take a server down. Learn how catastrophic backtracking causes exponential and quadratic slowdowns, what happened in the Stack Overflow and Cloudflare outages, and how to prevent ReDoS with safer patterns, linear-time engines, input limits, and timeouts.","keywords":["Denial of Service","Application Security","ReDoS","Regular Expressions","performance","IT Security"],"entities":["Arpan Singh","Denial of Service","Application Security","ReDoS","Regular Expressions","performance","IT Security","ZyVOP"],"keyTakeaways":["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."],"headings":["What ReDoS is","Backtracking, step by step","Measured: the time doubles with every extra letter","Slower, but still an outage: polynomial ReDoS","How to spot a dangerous regex","Where it bites","Fixes","1. Don’t use a regex for it","2. Use a linear-time engine for untrusted input","3. Rewrite the pattern","4. Use atomic groups or possessive quantifiers","5. Cap the input length","6. Add a timeout as the last defense","Measure it yourself","Wrapping up"],"outboundLinks":["https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS","https://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016","https://github.com/doyensec/regexploit","https://github.com/google/re2","https://docs.python.org/3/library/re.html"],"contentText":"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: flowchart TD begin[\"Match ^(a+)+$ against aaab\"] --&gt; w1[\"Groups: aaa\"] begin --&gt; w2[\"Groups: aa, a\"] begin --&gt; w3[\"Groups: a, aa\"] begin --&gt; w4[\"Groups: a, a, a\"] w1 --&gt; f1[\"$ fails on b\"] w2 --&gt; f2[\"$ fails on b\"] w3 --&gt; f3[\"$ fails on b\"] w4 --&gt; 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:#1a1a1aEvery 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 !: 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.51Even (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 flowchart LR attacker[\"Attacker sends a crafted string\"] --&gt; matcher[\"Server runs a regex on it\"] matcher --&gt; engine[\"The engine backtracks for seconds or hours\"] engine --&gt; cpu[\"One CPU core is pegged\"] cpu --&gt; stall[\"Other requests wait or time out\"] style engine fill:#fff4e0,stroke:#d08000,stroke-width:2px,color:#1a1a1aAny 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: flowchart TD untrusted{\"Does the regex run on untrusted input?\"} untrusted --&gt;|\"No\"| normal[\"Normal care is enough\"] untrusted --&gt;|\"Yes\"| plain{\"Can a string method or parser do the job?\"} plain --&gt;|\"Yes\"| strings[\"Use it, for example str.strip()\"] plain --&gt;|\"No\"| linear{\"Can you use a linear-time engine?\"} linear --&gt;|\"Yes\"| engine[\"Use RE2, Go, Rust or .NET NonBacktracking\"] linear --&gt;|\"No\"| harden[\"Rewrite the pattern, cap the input length, add a timeout\"] style engine fill:#e6f0fa,stroke:#2b7de0,stroke-width:2px,color:#1a1a1a1. 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: // 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 msOn 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: (?&gt;...) and a++. They stop the engine from backing up into a group once it has matched. ^(?&gt;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: trim = re.compile(r'^\\s+|(?&lt;!\\s)\\s+$') # 1.1 ms instead of 4.4 s on 32,000 spaces5. Cap the input length Check the length before you match. For quadratic patterns, a cap of 2,000 characters kept one call near 25 ms in my test. For exponential patterns the cap has to be tiny, since 24 letters already took 0.7 s, so combine it with another fix. 6. Add a timeout as the last defense Python’s built-in re has no timeout option (as of 3.12, the version I tested), and a running match can’t be interrupted from the same thread. One workaround is to run it in a separate process and kill that process: import multiprocessing, re def _worker(pattern, text, queue): queue.put(bool(re.match(pattern, text))) def safe_match(pattern, text, timeout=1.0): \"\"\"Run re.match in a separate process, and kill it if it takes too long.\"\"\" queue = multiprocessing.Queue() # on Windows and macOS, call this from code guarded by __main__ process = multiprocessing.Process(target=_worker, args=(pattern, text, queue)) process.start() process.join(timeout) if process.is_alive(): process.terminate() process.join() raise TimeoutError('regex took too long') return queue.get()With a 0.5-second limit, a 40-letter attack string raised TimeoutError after 0.52 seconds, and a harmless input returned in about 3 ms. Starting a process per call is slow, so use a worker pool in real code. Measure it yourself This script reproduces the first three tables. It takes about ten seconds: import re, time def timed(fn): start = time.perf_counter() fn() return time.perf_counter() - start # 1. nested quantifiers: the time roughly doubles with every extra letter print('letters seconds x previous') evil, previous = re.compile(r'^(a+)+$'), None for n in range(18, 27): seconds = timed(lambda: evil.match('a' * n + 'b')) print(f'{n:&gt;7} {seconds:&gt;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:&gt;6,} {seconds:&gt;14.3f} {f\"{seconds / previous:.2f}x\" if previous else \"\":&gt;12} {timed(lambda: text.strip()) * 1e6:&gt;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'^(?&gt;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.","contentHash":"sha256:b840b692b4e80d53c682796cbf01c8733738b08dea3ae22af54097c3fb651559","authorName":"Arpan Singh","authorUrl":"https://zyvop.com/author/arpan","authorSameAs":[],"category":"IT Security","tags":["Denial of Service","Application Security","ReDoS","Regular Expressions","performance"],"audience":"Software engineers and developers building applications with IT Security","tone":"Instructional, practical, code-first","readingTimeMinutes":8,"wordCount":2108,"faqs":null,"primaryTopic":"IT Security","publishedAt":"2026-11-17T03:25:35.852Z","updatedAt":"2026-11-17T03:25:35.852Z","canonicalUrl":"https://zyvop.com/redos-explained-how-one-regular-expression-can-freeze-a-server-cae6v"}