ReDoS in Python: catastrophic backtracking in re and how to find it at runtime

Regular expression denial of service (ReDoS) in Python happens because the re module matches by backtracking: when a pattern can split the same text in many ways and the match finally does not succeed, the engine tries every split before giving up, and the work can double with each extra character. A short string sent to a validator can then hold a CPU core for seconds or minutes. The dependable fixes are to remove the ambiguity from the pattern, cap the input length, or use an engine that does not backtrack; and because the cost depends on the input as much as the pattern, the most reliable way to find it is to measure matches as they run.

The weakness is CWE-1333: Inefficient Regular Expression Complexity. OWASP's ReDoS page is a good general introduction.

One pattern, measured

The textbook example is a quantifier inside a quantifier over the same characters:

import re
import time

PATTERN = re.compile(r"^(a+)+$")

for n in range(18, 25):
    text = "a" * n + "!"
    start = time.perf_counter()
    PATTERN.fullmatch(text)
    print(n, round(time.perf_counter() - start, 3))

We ran this on Python 3.9 on a 2.5 GHz Xeon server. The output:

Each extra character roughly doubles the time. At that rate a few dozen characters is minutes, and the input is still shorter than most email addresses. Your numbers will differ by machine and Python version; the doubling will not.

Why it happens: (a+)+ can divide a run of a characters into groups in exponentially many ways. While the match can succeed, the engine finds one way and stops. The trailing ! guarantees no way succeeds, so the engine works through all of them. Two things are needed together: an ambiguous pattern, and an input that almost matches and then does not.

The three shapes to look for

Most vulnerable patterns in real code are one of these:

1. Nested quantifiers: (a+)+, (\w+\s?)*, ([a-z0-9]+)*. The inner and outer repeat can both absorb the same character.
2. Overlapping alternation under a repeat: (a|aa)+, (\d|\d\d)+, (.|\s)*. Two branches match the same text.
3. Adjacent repeats that overlap: \d+\d+, .*.*=, \s*\s*$. This shape is polynomial, not exponential, so it takes a longer input to hurt, and it is common in hand-written parsers for headers and logs.

The patterns do not look dangerous, and they often arrive from a search result for "email regex". They also live in dependencies. Django fixed CVE-2023-36053, a potential ReDoS in EmailValidator and URLValidator "via a very large number of domain name labels of emails and URLs", in its 3 July 2023 security release. NVD scores it 7.5 (High). Validators are the natural home for this bug: they run on untrusted input by definition, usually before authentication.

When the client supplies the pattern

A second form needs no flawed pattern in your code at all:

import re


def search_notes(notes, user_pattern: str):
    matcher = re.compile(user_pattern)
    return [note for note in notes if matcher.search(note)]

A "search with regex" box hands the client the engine. They can supply (a+)+$ themselves and choose the text to run it on. If the pattern is used as a filter (an allow rule, a routing rule), they can also write one that quietly accepts what the check was meant to reject. Compile only patterns you wrote. Where users need matching, offer literal substring search (re.escape(user_text) turns their input into a literal) or a small grammar of your own.

Fixes that work

Remove the ambiguity. Most nested quantifiers were never needed. ^(a+)+$ matches the same strings as ^a+$, which runs in linear time. For the email-style case, ^[a-zA-Z0-9]+@example\.com$ replaces ^([a-zA-Z0-9]+)+@example\.com$.

Cap the length before matching. An exponential pattern on 12 characters is harmless. A length check is one line, runs in constant time, and protects patterns you have not audited:

import re

USERNAME = re.compile(r"^[a-z0-9]+(?:[._-][a-z0-9]+)*$")
MAX_USERNAME = 64


def valid_username(value: str) -> bool:
    return len(value) <= MAX_USERNAME and USERNAME.fullmatch(value) is not None

Use possessive quantifiers or atomic groups on Python 3.11 and later. Python 3.11 added atomic grouping (?>...) and possessive quantifiers such as *+ and ++ (What's New in Python 3.11). Both tell the engine not to give back what a group has matched, which removes the backtracking: ^(?>a+)+$ and ^(a++)+$ both reject the input above immediately. They change what the pattern matches in some cases, so re-run your tests.

Use an engine that does not backtrack. RE2 guarantees matching time linear in the input size, and has Python bindings published as google-re2. The trade is features: it has no backreferences and no lookaround. For user-supplied patterns it is the option that removes the risk by construction.

Know what re does not have. The standard library's re has no timeout argument. The third-party regex module does: its matching functions accept timeout= in seconds. A timeout turns a hang into an exception, which is a useful backstop and not a substitute for fixing the pattern, since each timed-out request still burned its full allowance of CPU.

Why review alone has a hard time

Reading a pattern tells you whether it is ambiguous. It does not tell you whether an attacker's text reaches it, how long that text may be, or whether the pattern is anchored by code around it. Static pattern analysers are worth running, and they report candidates: patterns that could blow up on some input. Many candidates never see untrusted input, and some real cases are in patterns built at runtime or compiled inside a library.

Fuzzing has the opposite limit. A ReDoS input returns the correct answer, slowly. Nothing crashes, so a coverage-guided fuzzer has no failure to report unless you add a time budget to the harness yourself.

Finding it with a test

You can add that time budget in a few lines. This helper pumps a string, times the match at two sizes, and reports the growth:

import re
import time


def growth_ratio(pattern: str, unit: str, suffix: str, small: int = 12, big: int = 18) -> float:
    compiled = re.compile(pattern)

    def timed(count: int) -> float:
        text = unit * count + suffix
        start = time.perf_counter()
        compiled.fullmatch(text)
        return max(time.perf_counter() - start, 1e-7)

    return timed(big) / timed(small)


def test_username_pattern_is_not_exponential():
    ratio = growth_ratio(r"^[a-z0-9]+(?:[._-][a-z0-9]+)*$", "a", "!")
    assert ratio < 20

A linear pattern gives a ratio near the ratio of the sizes (here 1.5, plus noise). An exponential one gives a ratio in the dozens or more for six extra characters. Keep the sizes small so a vulnerable pattern fails the test quickly. The limit of this approach is that you choose the unit and the suffix: it confirms a suspicion about a pattern you already picked out.

Finding it at runtime

The complementary approach is to watch real matches. es-python, the EyalSec Python runtime, follows untrusted data through the program as it runs and checks it at the operation itself, which for this class is the match. It reports in two layers (what the event looks like):

• A base event (re match, re search, re compile and related labels) when untrusted data reaches the regex engine, as the text or as the pattern. This is the inventory: every place a client's string meets a regex, including patterns compiled inside dependencies.
• A separate redos event only when a match actually backtracked heavily over untrusted input. es-python counts the engine's steps and reports when the count crosses both an absolute threshold and a steps-per-character threshold. The second threshold is what separates real super-linear backtracking from an ordinary scan of a large string.

So a redos event says the work did blow up, on this pattern, with this input, at this call path. The pattern itself is shown in the event's Regex line (event detail).

Three things to know when reading these events. The redos impact tag always travels with a regex bypass tag, because one regex event can be either finding: a pattern that hangs, or a pattern used as a filter that an attacker loosened. Both are graded low, and you decide which the call site is; if the regex validates or filters, read it as a bypass first. Second, a pattern whose blow-up sits entirely inside a single bounded repeat is not counted, so the redos event covers the common nested-quantifier shape, not every possible one. Third, it reports what ran: a vulnerable pattern that no request or test exercised produces nothing, which is why this pairs well with running your test suite under it. Under a Raise rule the match is stopped with an error. The model is on How EyalSec works and cost on pricing.

Checklist

• Search for nested quantifiers, overlapping alternations and adjacent overlapping repeats.
• Cap input length before every regex that runs on client data.
• Never compile a client-supplied pattern with re; escape it or use a linear-time engine.
• On Python 3.11 and later, consider possessive quantifiers where backtracking is not needed.
• Add a growth test for patterns on the request path.
• Keep frameworks current: validator patterns get fixed upstream.

If you want to see which regex calls on your own services receive untrusted input, and which ones blow up, you can book a live demo.