Skip to content

Preventing Regex Denial of Service in Async Handlers

A regular expression with nested or overlapping quantifiers can take time exponential in the length of an input that almost matches — catastrophic backtracking. When such a pattern validates user input in a request handler, a short crafted string becomes a CPU-bound operation of seconds, and in an asyncio service the cost lands on the event loop. Measured on Python 3.14 with the textbook pattern ^(a+)+$ and inputs of a characters followed by !: matching took 28 ms for 21 characters, 114 ms for 23, 429 ms for 25 and 1,691 ms for 27 — roughly fourfold per two characters. Run directly in a coroutine, a 26-character input stalled the event loop for 773 ms. Moved to asyncio.to_thread, it stalled the loop for 795 ms anyway: Python's re engine holds the GIL while matching, so the thread could not run alongside the loop. A process pool kept loop lag at 1.1 ms. Rewriting the pattern with an atomic group (?>a+) or a possessive quantifier a++ — both available since Python 3.11 — made the same inputs match in 0.8–9 µs. This guide finds and fixes regexes that can stall an async service.

Prerequisites

1. See how fast backtracking grows

Time a vulnerable pattern against inputs that nearly match:

import re
import time

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

for n in (20, 22, 24, 26):
    s = "a" * n + "!"                        # the final "!" forces every split to be tried
    t = time.perf_counter()
    EVIL.match(s)
    print(n + 1, f"{(time.perf_counter() - t) * 1e3:.1f} ms")

Measured: 28.3, 114.1, 428.8 and 1,691.1 ms for inputs of 21, 23, 25 and 27 characters. The nested quantifier lets the engine split the run of as between the inner and outer + in exponentially many ways, and the trailing ! makes every split fail, so it tries them all. Real-world patterns that do this are less obvious: (\w+\s?)+$ for "words separated by spaces", (.*,)* for CSV-like fields, email and URL validators with optional groups. A 30-character input is enough to cost tens of seconds.

Verify: for each regex applied to user input, time it against long near-matching strings (a run of the repeated character class followed by one character that cannot match).

Time to fail ^(a+)+$ by input length 4 horizontal bars comparing 21 chars with the others. Time to fail ^(a+)+$ by input length 21 chars 28.3 ms 23 chars 114.1 ms 25 chars 428.8 ms 27 chars 1,691 ms Python 3.14 re; input 'a' * n + '!'. Atomic and possessive rewrites took 0.8-9 us at every length. Two more characters, four times the work.

2. Do not count on a thread to protect the loop

Offloading to a thread is the usual fix for blocking work, and it does not work here:

async def validate_on_loop(value: str) -> bool:
    return EVIL.match(value) is not None                              # stalls the loop

async def validate_in_thread(value: str) -> bool:
    return await asyncio.to_thread(EVIL.match, value) is not None     # stalls it too

Measured with a 26-character input: 773 ms maximum loop lag on the loop, 795 ms from the thread. Python's re module performs matching in C without releasing the GIL, so while the thread matches, the event loop's thread cannot run Python code at all. This is the difference between re and libraries such as bcrypt, which release the GIL and were safely offloaded to threads in hashing passwords without blocking the event loop. Before moving any CPU-heavy call to a thread, check whether it releases the GIL — measuring loop lag during the call is the quickest test.

Verify: loop lag during a slow regex call, run however you plan to run it in production, stays within budget.

3. Rewrite the pattern so it cannot backtrack

The robust fix is a pattern that does not have exponentially many ways to fail. Python 3.11 added atomic groups and possessive quantifiers, which commit to what they matched and never give it back:

EVIL       = re.compile(r"^(a+)+$")        # nested quantifiers: exponential
ATOMIC     = re.compile(r"^(?>a+)+$")      # atomic group: no backtracking into it
POSSESSIVE = re.compile(r"^(a++)+$")       # possessive quantifier: same effect
SIMPLE     = re.compile(r"^a{1,64}$")      # say what you mean, with a length bound

Measured on the same inputs: the atomic version took 3.5–9.0 µs and the possessive version 0.8–2.0 µs at every length, and the simplified ^a{1,64}$ 7.5 µs — against 1.7 seconds for the original at 27 characters. Often the nested quantifier was never needed: (a+)+ means the same as a+. Where the structure is real — words separated by single spaces — express it without overlap, for example ^\w+(?: \w+)*$, so that each character can be consumed in only one way.

Verify: each rewritten pattern accepts and rejects the same test corpus as the original, and matches near-miss inputs in microseconds.

The same 26-character input, five ways A grid of 5 rows by 3 columns. The same 26-character input, five ways approach match time event-loop lag on the event loop ~770 ms 773 ms stall asyncio.to_thread ~770 ms 795 ms stall (re holds the GIL) process pool 772 ms of a worker's CPU 1.1 ms atomic group (?>a+) 3.5-9 us none possessive a++ 0.8-2 us none Only a rewrite removes the cost; a process pool only moves it.

4. Bound input length before matching

Even a well-written pattern should not receive unbounded input, and for a vulnerable one the length limit is what keeps the cost finite:

from pydantic import BaseModel, Field, field_validator

USERNAME = re.compile(r"^[a-z0-9](?:[a-z0-9_-]{0,30}[a-z0-9])?$")


class Signup(BaseModel):
    username: str = Field(max_length=32)               # checked before the validator runs

    @field_validator("username")
    @classmethod
    def valid_username(cls, v: str) -> str:
        if not USERNAME.fullmatch(v):
            raise ValueError("invalid username")
        return v

With the measured growth rate, the original pattern stays under a millisecond only below about 16 characters; a length cap is a cheap second line of defence, not a substitute for fixing the pattern. Field length limits also bound other per-character costs — normalization, hashing, logging — and belong on every string a client controls, alongside the body-size limits in limiting request body size in ASGI apps.

Verify: every string field validated by a regex has a max_length that is enforced before the regex runs.

5. Isolate patterns you cannot rewrite

Sometimes the pattern is not yours — a configurable filter, a third-party validator, user-supplied search expressions. Run those in a process pool with a timeout, and treat a timeout as a rejection:

from concurrent.futures import ProcessPoolExecutor

REGEX_POOL = ProcessPoolExecutor(max_workers=2)


def _match(pattern: str, value: str) -> bool:
    return re.search(pattern, value) is not None


async def safe_match(pattern: str, value: str, budget: float = 0.1) -> bool:
    loop = asyncio.get_running_loop()
    try:
        async with asyncio.timeout(budget):
            return await loop.run_in_executor(REGEX_POOL, _match, pattern, value)
    except TimeoutError:
        log.warning("regex exceeded %.0f ms; rejecting input", budget * 1e3)
        return False

Measured: in a process pool the catastrophic match took its 772 ms in the worker while the event loop's lag stayed at 1.1 ms; with a 100 ms budget the handler got TimeoutError after 101 ms with 0.3 ms of loop lag. The worker process, however, keeps matching until it finishes — asyncio.timeout abandons the result, it cannot interrupt C code in another process — so the pool must be small and bounded, and a pathological pattern still occupies a worker. For untrusted patterns, an engine with linear-time guarantees, such as RE2 through its Python bindings, removes the problem by construction.

Verify: a known-catastrophic input to safe_match returns False within the budget, and the service's loop lag is unaffected.

How should this regex be made safe? A decision on Who controls the pattern with 4 outcomes. How should this regex be made safe? Who controls the pattern? you rewrite: atomic, possessive, no overlap microseconds you, any pattern cap input length first bounds the worst case a dependency or configuration process pool + timeout loop lag 1.1 ms users linear-time engine (RE2) no backtracking at all A thread does not help: re holds the GIL while matching.

Verification

Regex handling is safe when:

  • Every pattern applied to user input is tested against long near-matching strings.
  • Vulnerable patterns are rewritten without nested or overlapping quantifiers.
  • Inputs have length caps enforced before matching.
  • Patterns you cannot change run in a bounded process pool with a timeout, and user-supplied patterns use a linear-time engine.

Diagnostic Hook: log the duration of validation in request handlers and alert on any single validation over 10 ms. Regex blow-ups appear as rare, enormous outliers tied to specific inputs — invisible in averages, unmistakable in a maximum — and the logged input (truncated) points straight at the pattern.

Pitfalls & edge cases

  • Offloading re to a thread. Measured: the loop still stalled 795 ms.
  • Nested quantifiers. (a+)+ failed in 1.7 s on 27 characters.
  • Length caps as the only fix. They bound the damage; the pattern is still exponential.
  • Timeouts on process-pool matches. They return control, not the worker.

Frequently Asked Questions

What is regex denial of service (ReDoS)?

A regex with nested or overlapping quantifiers takes exponential time on inputs that nearly match; ^(a+)+$ took 1.7 s on 27 characters in testing. In an async service that time stalls the event loop for every request.

Does running a regex in asyncio.to_thread prevent blocking?

No: Python's re holds the GIL while matching, so a slow match in a thread stalled the event loop for 795 ms in testing. Rewrite the pattern, or use a process pool.

How do I make a Python regex safe from catastrophic backtracking?

Remove nested and overlapping quantifiers, or use atomic groups (?>...) and possessive quantifiers such as a++, available since Python 3.11; the rewritten pattern matched in microseconds. Cap input length as well.

How do I run user-supplied regexes safely?

Use a linear-time engine such as RE2, or run matches in a small process pool with a timeout and treat a timeout as a rejection.