DEV Community

Cover image for ๐ŸŒ ReDoS: Find the Regex That Can Freeze Your API, Then Prove the Fix
Krishna Kumar
Krishna Kumar

Posted on

๐ŸŒ ReDoS: Find the Regex That Can Freeze Your API, Then Prove the Fix

Most input validation bugs let the wrong data in. This one lets the right data in just fine, and then takes the whole process down on the wrong data.

A single regular expression, written to check something boring like a URL slug, can take milliseconds on normal input and seconds, minutes or longer on a 30-character string built for it. That's Regular expression Denial of Service (ReDoS), catalogued as CWE-1333: Inefficient Regular Expression Complexity. In Node.js it's worse than "one slow request": a regex match runs on the event loop, so while it backtracks, nothing else in that process gets served.

This is a fix guide. We'll look at why some patterns blow up, how to find them in your code, how to prove one is actually exploitable (a linter warning isn't proof), and how to fix it in Python and Node with tests that keep it fixed.

Everything here runs locally against your own code. Never send ReDoS payloads to a system you don't own or aren't authorized to test: on a shared server, the "proof" is an outage.

Why a regex can take exponential time

Python's re, V8 (the engine behind Node.js and Chrome) and .NET's default engine are backtracking engines, like many others. When a match fails, the engine goes back and tries every other way the pattern could have matched the input so far before giving up.

For most patterns there are only a few other ways. The trouble starts when the pattern is ambiguous: when the same input can be split across the pattern in many different ways. OWASP's ReDoS page describes the shape: a repeated group, and inside that group either another repetition or an alternation whose options overlap. Its textbook examples:

(a+)+$
([a-zA-Z]+)*$
(a|aa)+$
(a|a?)+$
Enter fullscreen mode Exit fullscreen mode

Take (a+)+$ against aaaa!. The inner a+ and the outer + can share the four as as aaaa, aaa|a, aa|aa, a|a|a|a and so on. The ! makes the $ fail every time, so the engine tries every split before it can say "no match". The number of splits doubles with each extra a. The Node.js guide Don't Block the Event Loop puts it the same way: one more character can double the work.

There's a milder version too. CodeQL separates exponential cases (js/redos) from polynomial ones (js/polynomial-redos), where the time grows like nยฒ or nยณ. Its polynomial example is a whitespace trim, /^\s+|\s+$/g: harmless on short strings, slow on a very long run of spaces that doesn't end in a space. Polynomial cases need much longer input to hurt, but request bodies are often long.

What it looks like in real code

Here's a slug validator that looks reasonable:

^([a-z0-9]+-?)*$
Enter fullscreen mode Exit fullscreen mode

"Letters and digits, optionally followed by a dash, repeated." It matches my-first-post. But [a-z0-9]+ sits inside a *, and since the dash is optional, a run like aaaa can be split between the inner + and the outer * in many ways: the same nested-quantifier shape as (a+)+$.

The places this tends to hide:

  • Validators for slugs, usernames, emails, URLs, phone numbers and file names, especially ones written by hand.
  • Parsers that pull fields out of headers, user agents, log lines or Markdown with one big regex.
  • Trimming and cleanup of whitespace or punctuation (the polynomial kind).
  • Dependencies. The pattern doesn't have to be yours; a validation library or a parser in your node_modules counts too.

How to find candidates

Start with tools, then read what they flag.

Static rules. For JavaScript and TypeScript, eslint-plugin-regexp has regexp/no-super-linear-backtracking, which reports exponential and polynomial backtracking and is on in the plugin's recommended config. Its docs are honest that the detection is simple and won't catch every case. CodeQL has js/redos and js/polynomial-redos for JavaScript and py/redos and py/polynomial-redos for Python. The polynomial queries are path queries: they report a slow pattern only when uncontrolled input can reach it, which is closer to what you actually care about.

Reading by eye. Grep for patterns that have a quantifier right after a closing group, like )+, )* and ){, and look inside the group. The Node.js guide's rules of thumb are a good checklist:

  • Nested quantifiers like (a+)*.
  • Alternations whose options overlap, like (a|a)*.
  • Backreferences like (a.*)\1, which no engine can guarantee to run in linear time.

Every hit from either method is a lead. A linter knows the pattern can backtrack; it doesn't know whether attacker input reaches it, how long that input can be, or whether something upstream caps it. That's the next step.

Prove it before you file it (or fix it)

Proving a ReDoS has two parts: the pattern really is super-linear, and untrusted input can reach it at a length that hurts.

1. Time the pattern locally

Don't guess from the shape. Measure it. This probe runs each match in a child process with a 5-second budget, so a runaway pattern can't hang your terminal, and grows the input two characters at a time. The input is a run of characters the pattern accepts, followed by one it doesn't, which forces the engine to try every split:

# redos_probe.py - time one pattern against growing input, locally only
import multiprocessing as mp
import re
import sys
import time

def _match(pattern, text, out):
    start = time.perf_counter()
    re.match(pattern, text)
    out.put(time.perf_counter() - start)

def time_match(pattern, text, budget=5.0):
    out = mp.Queue()
    p = mp.Process(target=_match, args=(pattern, text, out))
    p.start()
    p.join(budget)
    if p.is_alive():          # still backtracking: kill it, report the timeout
        p.terminate()
        p.join()
        return None
    return out.get()

if __name__ == "__main__":
    pattern = sys.argv[1]
    for n in range(16, 31, 2):
        text = "a" * n + "!"   # almost matches, then fails at the last char
        t = time_match(pattern, text)
        print(f"n={n:>2}  " + ("timeout (>5s)" if t is None else f"{t * 1000:9.1f} ms"))
        if t is None:
            break
Enter fullscreen mode Exit fullscreen mode

Here's the slug pattern on my machine (Python 3.14):

$ python redos_probe.py '^([a-z0-9]+-?)*$'
n=16        7.8 ms
n=18       32.2 ms
n=20      114.4 ms
n=22      457.8 ms
n=24     2178.6 ms
n=26  timeout (>5s)
Enter fullscreen mode Exit fullscreen mode

Every two extra characters multiply the time by roughly four. That's the exponential signature: 27 characters of input, and a CPU core is busy for more than five seconds. Your absolute numbers will differ by machine; the curve is what matters. A linear pattern stays flat as n grows; a polynomial one climbs slowly and needs thousands of characters to show.

V8 is a backtracking engine too. The same pattern in Node 24 took 75 ms at n=20 and 1,218 ms at n=24 in my local run, and during that time the event loop serves nothing else.

Timing of the vulnerable slug regex versus the rewritten one as input length grows

2. Show that untrusted input reaches it

A slow pattern that only ever sees a config value isn't a vulnerability. Trace the data instead:

  • Where does the matched string come from? A path segment, query parameter, header or JSON field is attacker-controlled.
  • Is the length capped before the match, and how tightly? For an exponential pattern, even a short cap doesn't save you: the slug pattern above passed five seconds at 27 characters. For a polynomial one, a tight cap can be enough. A 1 MB body limit helps neither.
  • Does a framework or proxy cap it first? Check what URL and header length limits actually apply in your stack rather than assuming.

The clean way to prove reachability is a unit test that calls the same function your handler calls, with the hostile string, and measures it. That gives you a reproducible proof without ever pointing a payload at a running server. If you need to show it on a deployed instance, use a staging environment you own, one request, a small n, and a control request next to it.

Pattern timed, input path traced, length checked: now it's a finding, not a lint warning.

The fix

There are four ways to fix it, roughly in order of preference.

1. Remove the ambiguity

Rewrite the pattern so every input can be matched only one way. For the slug, require a dash between groups instead of making it optional:

^[a-z0-9]+(?:-[a-z0-9]+)*$
Enter fullscreen mode Exit fullscreen mode

Now each -[a-z0-9]+ group must start with a dash, so a run of letters can't be split between iterations. The same probe:

$ python redos_probe.py '^[a-z0-9]+(?:-[a-z0-9]+)*$'
n=16        0.2 ms
n=18        0.4 ms
n=20        0.2 ms
n=22        0.3 ms
n=24        0.2 ms
n=26        0.2 ms
n=28        0.2 ms
n=30        0.2 ms
Enter fullscreen mode Exit fullscreen mode

Note that this isn't exactly the same rule: the old pattern also accepted an empty string and a trailing dash (post-), and the new one rejects both. For slugs that's an improvement, but check what your callers rely on before you tighten a validator. CodeQL's guidance for both queries is the same idea: remove the ambiguity, or keep the input short enough that the complexity doesn't matter.

2. Tell the engine not to backtrack (Python 3.11+)

If you need to keep the exact behavior, Python 3.11 added atomic groups (?>...) and possessive quantifiers (*+, ++, ?+, {m,n}+). The re docs describe possessive quantifiers as matching as much as possible without leaving any backtracking points. Making the outer * possessive:

^(?:[a-z0-9]+-?)*+$
Enter fullscreen mode Exit fullscreen mode

This stayed under half a millisecond through n=30 in the probe. To check it didn't change behavior, I compared it with the original pattern on every string up to 7 characters built from a, 1, - and !: zero differences. Run a check like that whenever you change a validator this way. JavaScript regexes don't have possessive quantifiers or atomic groups, so in Node use the rewrite.

3. Use an engine that can't backtrack

Some engines guarantee linear time by design:

  • Go's regexp package is guaranteed to run in time linear in the size of the input.
  • RE2 gets the same property by leaving out constructs that are only known to be solvable with backtracking, such as backreferences and lookaround. The Node.js guide points to the node-re2 module for this, with a warning that it's not fully compatible with V8 regexes, so test for regressions.
  • .NET has RegexOptions.NonBacktracking, and for backtracking patterns Microsoft recommends always setting a match timeout, because by default there isn't one.
  • V8 has an experimental non-backtracking engine behind flags (--enable-experimental-regexp-engine adds a non-standard l flag). It's experimental, so I'd use it to check a pattern, not as a production fix.

Python's built-in re has no time limit option, so the rewrite, a possessive quantifier and a length cap are your main tools there.

4. Cap the length first

A length check before the regex puts a ceiling on the work. For polynomial patterns a tight cap can be enough on its own, which is the second half of CodeQL's recommendation. For exponential ones it isn't: 27 characters was enough above. So it's not a replacement for fixing the pattern, but it's cheap and it belongs in front of every validator anyway.

Make it stay fixed

The fix isn't done until a test would catch it coming back. In Python:

# test_slug.py - the fix, plus tests that prove it
import re
import time
import unittest

SLUG_RE = re.compile(r"[a-z0-9]+(?:-[a-z0-9]+)*")
MAX_SLUG = 64

def is_valid_slug(value: str) -> bool:
    if len(value) > MAX_SLUG:        # cheap length check before any regex
        return False
    return SLUG_RE.fullmatch(value) is not None

class SlugTests(unittest.TestCase):
    def test_accepts_normal_slugs(self):
        for ok in ["post", "my-first-post", "v2-release-notes"]:
            self.assertTrue(is_valid_slug(ok), ok)

    def test_rejects_bad_slugs(self):
        for bad in ["", "-post", "post-", "my--post", "Post", "a" * 65]:
            self.assertFalse(is_valid_slug(bad), bad)

    def test_hostile_input_stays_fast(self):
        hostile = "a" * 50_000 + "!"     # skips the length cap on purpose
        start = time.perf_counter()
        SLUG_RE.fullmatch(hostile)
        self.assertLess(time.perf_counter() - start, 0.1)

if __name__ == "__main__":
    unittest.main()
Enter fullscreen mode Exit fullscreen mode
$ python test_slug.py
...
----------------------------------------------------------------------
Ran 3 tests in 0.003s

OK
Enter fullscreen mode Exit fullscreen mode

The hostile test calls the regex directly, so it tests the pattern even if someone later raises the length cap. One caveat: if someone puts the vulnerable pattern back, this test won't fail. It will hang. Give your CI job a timeout so a hang counts as a failure.

The same thing in Node with the built-in test runner:

// slug.test.mjs - run with: node --test slug.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

const SLUG_RE = /^[a-z0-9]+(?:-[a-z0-9]+)*$/;
const MAX_SLUG = 64;

export function isValidSlug(value) {
  if (typeof value !== "string" || value.length > MAX_SLUG) return false;
  return SLUG_RE.test(value);
}

test("accepts and rejects the right slugs", () => {
  for (const ok of ["post", "my-first-post", "v2-release-notes"]) assert.ok(isValidSlug(ok), ok);
  for (const bad of ["", "-post", "post-", "my--post", "Post", "a".repeat(65)]) assert.ok(!isValidSlug(bad), bad);
});

test("hostile input stays fast", () => {
  const hostile = "a".repeat(50_000) + "!";
  const start = performance.now();
  SLUG_RE.test(hostile);
  assert.ok(performance.now() - start < 100);
});
Enter fullscreen mode Exit fullscreen mode

Both pass in my local run (Python 3.14, Node 24). Add the lint rule or CodeQL query to CI so new patterns get flagged, and keep the probe around for proving the ones it flags.

Try it yourself

All of this works on your own laptop, with nothing aimed at anyone else's server:

  1. Save redos_probe.py and run it on OWASP's four example patterns, then on the rewritten slug pattern. Watch one curve climb and the other stay flat.
  2. Grep your own codebase for )+, )* and ){ and run the probe on anything that has a quantifier inside the group.
  3. Add eslint-plugin-regexp to a JavaScript project, or run CodeQL's js/redos / py/redos queries on a repo you own, and prove or dismiss each hit with the probe and a trace of where the input comes from.
  4. Write the regression test before you change the pattern, and watch it time out on the old one (with a timeout set).

Conclusion

ReDoS isn't about exotic payloads. It's an ambiguous pattern, an input the pattern almost accepts, and an engine that tries every way to make it fit. Scanners and linters are good at spotting the shape, but a flagged pattern is a lead: prove it with a timing curve and a traced input path, fix the pattern itself, and leave a test behind so it stays fixed.

Further reading

I'm Krishna, a pentester and the founder of Xalgorix, an open-source AI pentester that only reports vulnerabilities it has actually exploited.


๐Ÿ” If this was useful, follow me for more hands-on web & API security write-ups.

๐Ÿ”— Connect with me on LinkedIn: https://www.linkedin.com/in/xalgord/

Top comments (0)