How to Find and Fix Regular Expression Denial of Service (ReDoS) in Python

A regular expression, or regex, is a compact pattern that describes a set of strings. Nearly every application uses regexes to check what strangers type: is this a valid username, is this a quoted string, does this comment end with stray spaces. Most of the time a regex answers in microseconds. For certain patterns, though, an input only a few dozen characters long can keep the matching engine busy for minutes, and an attacker who knows or guesses which patterns you use can send exactly that input. The bug is called regular expression denial of service, or ReDoS. OWASP describes it as an attack that “exploits the fact that most Regular Expression implementations may reach extreme situations that cause them to work very slowly (exponentially related to input size).”

This is not a textbook curiosity. Cloudflare’s postmortem of its July 2, 2019 outage says the CPU exhaustion “was caused by a single WAF rule that contained a poorly written regular expression that ended up creating excessive backtracking.” The post’s author, John Graham-Cumming, recalls being told “we had lost 80% of our traffic” while the team worked the incident. The postmortem also explains why the firewall could not protect itself: its Lua WAF uses PCRE internally, and “it uses backtracking for matching and has no mechanism to protect against a runaway expression.”

In this tutorial you will build a small lab where you can watch ReDoS happen and then stop it. Along the way you will:

• measure a tiny pattern whose running time doubles with every extra character, plus three realistic input validators that fail in two different ways (exponential and quadratic);
• freeze a live FastAPI service with a single 29-character request, and see that even an endpoint with no regex in it stops answering;
• learn why a thread timeout and a length limit are not enough, and which tools really contain the damage;
• write a failing test, run a scanner, fix each pattern, and prove with an exhaustive comparison what changed and what did not.

Prerequisites

• Python 3.11 or newer. Atomic groups and possessive quantifiers, which Step 8 uses, arrived in Python 3.11. I built and ran everything on Python 3.13.14 on Windows 11, and the commands note where macOS or Linux differ.
• A terminal and a scratch folder. The code in this tutorial is deliberately vulnerable, so keep it out of any real project. You do not need regex expertise; the short symbol list below covers everything used here.
• About two minutes of patient CPU time. Several steps deliberately run for many seconds so you can feel the problem. All timings in this tutorial come from one machine, so treat the ratios between rows as the lesson and the absolute seconds as illustration.

The regex symbols you will meet

• ^ and $ anchor a pattern to the start and the end of the text.
• + means one or more of the thing before it, * means zero or more, and ? means optional.
• [a-z0-9] matches one character from a set, and [^"] matches any single character except a double quote.
• (...) groups part of a pattern, and (?:...) groups it without remembering what it matched.
• | means “or”, \s matches a whitespace character, . matches any character except a newline, and \\ matches one literal backslash.

Create a scratch folder, then create and activate a virtual environment and install the packages:

python -m venv .venv
.venv\Scripts\activate           # on macOS or Linux: source .venv/bin/activate
pip install fastapi uvicorn requests pytest regex regexploit
pip install google-re2           # optional, only used in Step 9

These are the versions I used: FastAPI 0.141.1, uvicorn 0.54.0, requests 2.34.2, pytest 9.1.1, regex 2026.9.29 and regexploit 1.0.0. The google-re2 package installed from a prebuilt wheel, so no compiler was needed on my Windows machine.

What ReDoS is, in plain language

Python’s re module matches text by trying one way to satisfy the pattern and, when a later part fails, backtracking: backing up to an earlier decision and trying the next option. The documentation uses a small example: matching a*a against aaaa, the a* first takes all four letters, then has to give one back so the final a has something to match. That retry is cheap when there is only one decision to revisit.

It becomes a problem when a pattern gives the engine many equally good ways to carve up the same text and the overall match then fails. To be sure it has not missed a way to succeed, the engine must try every carving. That is catastrophic backtracking, and when an attacker chooses the input it is the whole of ReDoS. Two ingredients make it possible. The input must be able to fail (often because its last character is wrong), and the pattern must be ambiguous. OWASP lists the recipe for ambiguity: a “Grouping with repetition” that contains either another repetition or an “Alternation with overlapping”.

How bad it gets depends on the shape of the ambiguity. When every extra character doubles the work, the growth is exponential: 30 characters can take a thousand times longer than 20. When the work grows with the square of the input, so that doubling the input makes matching four times slower, the growth is quadratic. Exponential bugs need only tiny inputs. Quadratic bugs need bigger inputs, but bigger inputs are easy to send. This tutorial reproduces both.

Step 1: Build a stopwatch that cannot hang

Measuring a regex that might never finish takes some care. If you time it inside your own script, a runaway match freezes the script, and Step 5 shows that you cannot interrupt it from a thread either. So the helper below runs every measurement in a child process that it is able to kill. Save this as timing.py:

"""Measure how long a regex (or a function) takes, without ever hanging the lab.

Every measurement runs in a child process, so a runaway can simply be killed.
"""
import json
import os
import subprocess
import sys

HERE = os.path.dirname(os.path.abspath(__file__))

CHILD = """
import importlib, json, re, sys, time
job = json.load(sys.stdin)
text = job["prefix"] + job["unit"] * job["n"] + job["suffix"]
if job["kind"] == "pattern":
    target = re.compile(job["target"]).search
else:
    module_name, function_name = job["target"].split(":")
    target = getattr(importlib.import_module(module_name), function_name)
start = time.perf_counter()
target(text)
print(time.perf_counter() - start)
"""


def kill_tree(process):
    """Kill the child and anything it started (a Windows venv python.exe is a launcher)."""
    if sys.platform == "win32":
        subprocess.run(["taskkill", "/PID", str(process.pid), "/T", "/F"], capture_output=True)
    else:
        process.kill()


def run_job(kind, target, prefix, unit, n, suffix, timeout):
    job = {"kind": kind, "target": target, "prefix": prefix, "unit": unit, "n": n, "suffix": suffix}
    child = subprocess.Popen(
        [sys.executable, "-c", CHILD],
        stdin=subprocess.PIPE,
        stdout=subprocess.PIPE,
        stderr=subprocess.PIPE,
        text=True,
        cwd=HERE,
    )
    try:
        out, err = child.communicate(json.dumps(job), timeout=timeout)
    except subprocess.TimeoutExpired:
        kill_tree(child)
        child.communicate()
        return None
    if child.returncode != 0:
        raise RuntimeError(err.strip())
    return float(out.strip())


def seconds_to_search(pattern, prefix, unit, n, suffix, timeout=10.0):
    """Seconds re.search takes on prefix + unit * n + suffix, or None if it hits the timeout."""
    return run_job("pattern", pattern, prefix, unit, n, suffix, timeout)


def seconds_to_call(target, prefix, unit, n, suffix, timeout=10.0):
    """Same, for a function named like 'validators:is_valid_username'."""
    return run_job("function", target, prefix, unit, n, suffix, timeout)

What the code does

The CHILD string is a tiny program. It reads a job from standard input, builds the hostile text as prefix + unit * n + suffix (for example, 28 letters a followed by !), and prints how many seconds the match took. Building the text inside the child avoids pushing million-character strings through a command line. The function seconds_to_search times re.search for a pattern, and seconds_to_call times a function that lives in a module of your own (you will use it in Step 6). If the child does not finish before timeout, the helper kills it and returns None.

Gotcha on Windows. A virtual environment’s python.exe can be a small launcher that starts the real interpreter as a child process. On my machine it was: the process ID that subprocess.Popen reported (17876) was different from the one the child printed for itself with os.getpid() (16792). Killing only the launcher would leave the real interpreter running, still burning CPU on the hostile match, so kill_tree uses taskkill /T to end the whole tree. On macOS and Linux a plain process.kill() is enough.

Check your work. The next step calls this helper, so if it works there, it works here. After any run that ends in “gave up”, look for stray python processes in your task manager or with ps. I checked after every run in this tutorial and none were left behind.

Step 2: Watch a tiny pattern double its work with every letter

Start with the textbook example, ^(a+)+$. Read it aloud: from the start of the text, one or more groups, each group being one or more letters a, all the way to the end. The hostile input is a run of a characters followed by a single !. The ! guarantees that the match fails, so the engine has to rule out every possible way of splitting the letters among the groups before it can give up.

How many ways are there? The function ways_to_split below counts them by brute force, and the script then times the real match for longer and longer inputs. Save it as step2_exponential.py and run it:

"""Step 2: watch a tiny pattern double its work with every extra letter."""
from timing import seconds_to_search


def ways_to_split(n):
    """How many ways can (a+)+ carve n letters into one or more non-empty groups?"""
    if n == 0:
        return 1
    return sum(ways_to_split(n - k) for k in range(1, n + 1))


print("letters  ways to split  2 ** (letters - 1)")
for n in range(1, 9):
    print(f"{n:>7}  {ways_to_split(n):>13}  {2 ** (n - 1):>18}")

print()
print("length  seconds  growth  ways to split")
previous = None
for n in range(18, 29, 2):
    seconds = seconds_to_search(r"^(a+)+$", "", "a", n, "!", timeout=30)
    growth = f"x{seconds / previous:.1f}" if previous else ""
    print(f"{n:>6}  {seconds:7.4f}  {growth:>6}  {2 ** (n - 1):>13,}")
    previous = seconds

letters  ways to split  2 ** (letters - 1)
      1              1                   1
      2              2                   2
      3              4                   4
      4              8                   8
      5             16                  16
      6             32                  32
      7             64                  64
      8            128                 128

length  seconds  growth  ways to split
    18   0.0054                131,072
    20   0.0215    x4.0        524,288
    22   0.0850    x3.9      2,097,152
    24   0.3442    x4.0      8,388,608
    26   1.3411    x3.9     33,554,432
    28   5.7245    x4.3    134,217,728

What just happened

The first table shows that the number of ways to split n letters into groups is exactly 2 ** (n - 1); the recursion checked it by brute force for up to eight letters. Each extra letter doubles the number of ways. The second table shows the engine doing that much extra work: every time the length goes up by two, the time goes up by about four (the growth column), which is the same as doubling per letter. At 28 letters the match took 5.7 seconds. If the doubling kept going, 40 letters would take about 6.5 hours; I did not run that experiment.

Now the most important observation. The script step2_valid_input.py times the same 28 letters twice, once as they are and once with the trailing !:

"""Step 2 check: the very same letters finish instantly when the match succeeds."""
from timing import seconds_to_search

matching = seconds_to_search(r"^(a+)+$", "", "a", 28, "")
failing = seconds_to_search(r"^(a+)+$", "", "a", 28, "!")
print(f"28 letters, the match succeeds:  {matching:.6f}s")
print(f"28 letters, the match fails:     {failing:.6f}s")

28 letters, the match succeeds:  0.000001s
28 letters, the match fails:     5.568981s

When the text matches, the engine succeeds on its first attempt in about a microsecond. When the match fails, the same letters take more than five seconds. That asymmetry is why ReDoS survives normal testing: every valid username you try is fast, and only hostile text finds the bug.

Step 3: Meet three realistic bugs

Nobody writes (a+)+ on purpose. Real ReDoS bugs hide in patterns that look reasonable. Imagine the first draft of a small signup service. Save this as validators.py:

"""Input validators for a small signup service (the vulnerable first draft)."""
import re

USERNAME_RE = re.compile(r"^([a-z0-9]+[._-]?)+$")
QUOTED_RE = re.compile(r'^"(\\.|[^"])*"$')
TRAILING_WS_RE = re.compile(r"\s+$")


def is_valid_username(value: str) -> bool:
    """Letters and digits, optionally separated by single dots, underscores or hyphens."""
    return USERNAME_RE.match(value) is not None


def is_quoted_string(value: str) -> bool:
    """A double-quoted string in which a backslash escapes the next character."""
    return QUOTED_RE.match(value) is not None


def strip_trailing_whitespace(value: str) -> str:
    """Remove whitespace at the end of a comment or bio field."""
    return TRAILING_WS_RE.sub("", value)

Each of the three patterns is broken in its own way:

• USERNAME_RE: nested repetition. The intent is “letters and digits, optionally separated by a dot, underscore or hyphen”. But [a-z0-9]+ sits inside a group that is itself repeated with +, exactly the shape from Step 2, so a run of letters can be split among the group’s repetitions in a huge number of ways.
• QUOTED_RE: overlapping alternatives. The intent is a double-quoted string in which a backslash escapes the next character. The alternative \\. reads a backslash plus any character. The alternative [^"] reads any character except a quote, and that includes a backslash. So a backslash can be read two ways, and the number of ways to read a run of backslashes grows like the Fibonacci sequence, about 1.6 times bigger with each extra backslash. The hostile input is an opening quote, a run of backslashes and no closing quote.
• TRAILING_WS_RE: repeated rescanning. Removing trailing whitespace with \s+$ looks harmless, but re.sub tries the pattern at every starting position. Inside a long run of spaces followed by a visible character, each start scans to the end of the run and fails at $, and there are as many starts as there are spaces.

Now measure all three. The script step3_three_shapes.py uses the stopwatch from Step 1 and stops a case if the child runs longer than 20 seconds:

"""Step 3: measure the three patterns from validators.py against hostile input."""
from timing import seconds_to_search

LIMIT = 20  # seconds before we kill the child process

CASES = [
    ("username (exponential)", r"^([a-z0-9]+[._-]?)+$", "", "a", "!",
     [20, 22, 24, 26, 28, 30], "+2 characters"),
    ("quoted string (exponential)", r'^"(\\.|[^"])*"$', '"', "\\", "",
     [28, 32, 36, 40], "+4 characters"),
    ("trailing whitespace (quadratic)", r"\s+$", "", " ", "x",
     [2500, 5000, 10000, 20000, 40000], "doubling the length"),
]

for name, pattern, prefix, unit, suffix, sizes, step in CASES:
    print(f"{name}   pattern: {pattern}")
    previous = None
    for n in sizes:
        seconds = seconds_to_search(pattern, prefix, unit, n, suffix, timeout=LIMIT)
        if seconds is None:
            print(f"   n={n:>6}  gave up after {LIMIT}s")
            break
        growth = f"x{seconds / previous:.1f} per step ({step})" if previous else ""
        print(f"   n={n:>6}  {seconds:8.4f}s  {growth}")
        previous = seconds
    print()

username (exponential)   pattern: ^([a-z0-9]+[._-]?)+$
   n=    20    0.0360s
   n=    22    0.1404s  x3.9 per step (+2 characters)
   n=    24    0.5648s  x4.0 per step (+2 characters)
   n=    26    2.2607s  x4.0 per step (+2 characters)
   n=    28    9.8225s  x4.3 per step (+2 characters)
   n=    30  gave up after 20s

quoted string (exponential)   pattern: ^"(\\.|[^"])*"$
   n=    28    0.0341s
   n=    32    0.2323s  x6.8 per step (+4 characters)
   n=    36    1.5950s  x6.9 per step (+4 characters)
   n=    40   12.4057s  x7.8 per step (+4 characters)

trailing whitespace (quadratic)   pattern: \s+$
   n=  2500    0.0118s
   n=  5000    0.0479s  x4.0 per step (doubling the length)
   n= 10000    0.1895s  x4.0 per step (doubling the length)
   n= 20000    0.7580s  x4.0 per step (doubling the length)
   n= 40000    3.0997s  x4.1 per step (doubling the length)

How to read the tables

• Username: each step adds two characters and multiplies the time by about four, so the time doubles per character, like Step 2. At 28 characters the check took 9.8 seconds, and at 30 the child was still running after 20 seconds and was killed.
• Quoted string: each step adds four characters and multiplies the time by about seven (6.8 and 6.9 in the first two rows), which works out to roughly 1.6 per character, the Fibonacci rate. At 40 characters the check took 12.4 seconds.
• Trailing whitespace: each step doubles the input length and multiplies the time by four, the signature of quadratic growth. A 40,000-character comment took 3.1 seconds, and the attacker does not need a botnet to send 40 kilobytes.

The last row of the quoted-string table is a little worse than the pattern predicts. Timings this long are noisy, which is one more reason to trust ratios over individual numbers.

Step 4: See one request freeze a whole service

A slow function is one problem. A slow function inside a web server is a bigger one, because a server has other visitors. Build a tiny signup API around the validators. Save this as app.py:

"""A tiny signup API that validates usernames with validators.py."""
from fastapi import FastAPI

from validators import is_valid_username

app = FastAPI()


@app.get("/health")
def health():
    return {"status": "ok"}


@app.get("/usernames/check")
def check_username(name: str):
    return {"valid": is_valid_username(name)}

The endpoint /health does no regex work at all. It is the sort of route a load balancer or an uptime monitor polls. Next comes a script that starts the server, measures a health check while the server is idle, sends one hostile username, and measures the health check again while that request is still being processed. Save it as freeze_demo.py and run it:

"""Step 4: show one hostile request freezing a perfectly healthy endpoint."""
import subprocess
import sys
import threading
import time

import requests

BASE = "http://127.0.0.1:8765"
ATTACK = "a" * 28 + "!"


def timed_get(path, **params):
    started = time.perf_counter()
    requests.get(BASE + path, params=params, timeout=120)
    return time.perf_counter() - started


def wait_until_up():
    for _ in range(100):
        try:
            requests.get(BASE + "/health", timeout=1)
            return
        except requests.ConnectionError:
            time.sleep(0.1)
    raise RuntimeError("the server did not start")


def stop(server):
    if sys.platform == "win32":  # a venv's python.exe is a launcher, so kill its child too
        subprocess.run(["taskkill", "/PID", str(server.pid), "/T", "/F"], capture_output=True)
    else:
        server.terminate()
    server.wait()


server = subprocess.Popen(
    [sys.executable, "-m", "uvicorn", "app:app", "--port", "8765", "--log-level", "warning"]
)
try:
    wait_until_up()
    print(f"health check while idle:        {timed_get('/health') * 1000:8.1f} ms")

    attack = {}
    attacker = threading.Thread(
        target=lambda: attack.update(seconds=timed_get("/usernames/check", name=ATTACK))
    )
    attacker.start()
    time.sleep(0.5)  # give the hostile request a head start
    print(f"health check during the attack: {timed_get('/health') * 1000:8.1f} ms")
    attacker.join()
    print(f"the attack request itself took: {attack['seconds'] * 1000:8.1f} ms")
    print(f"health check after the attack:  {timed_get('/health') * 1000:8.1f} ms")
finally:
    stop(server)

health check while idle:             2.6 ms
health check during the attack:   9321.9 ms
the attack request itself took:   9822.0 ms
health check after the attack:       3.6 ms

What just happened

The health check answered in milliseconds while the server was idle, then waited more than nine seconds while a single 29-character username was being validated, and recovered as soon as the hostile request finished. Nothing about /health is slow, yet it froze for as long as the attack lasted.

The Python glossary explains part of the reason: it contrasts free threading with “the global interpreter lock which allows only one thread to execute Python bytecode at a time”. The measurements here show that the regex engine keeps that lock for the entire match, so every other thread in the process has to wait. I inferred that from these experiments rather than from a documented guarantee, so treat it as observed behavior of CPython 3.13 on this machine. By that arithmetic, one hostile request every ten seconds would keep this process permanently busy.

A note on the stop() helper: it uses taskkill on Windows for the same launcher reason as in Step 1, and terminate() elsewhere. Check your work: the idle and after numbers should be milliseconds, and the middle number should be close to the time the attack request itself took.

Step 5: Try the obvious safety nets

Before rewriting anything, it is worth seeing why the first ideas most developers reach for do not work. The script below tries three of them against hostile input, and the fourth, a length limit, can be judged from the measurements we already have. The script also prints the signature of re.match, so you can see for yourself that the standard library offers no timeout parameter. Save it as step5_safety_nets.py and run it:

"""Step 5: the safety nets that look reasonable, and what they actually do."""
import inspect
import re
import threading
import time

import regex

from timing import seconds_to_search

print("re.match signature:", inspect.signature(re.match))
print()

# 1. Run the match in a worker thread and stop waiting after half a second.
worker = threading.Thread(target=re.match, args=(r"^(a+)+$", "a" * 27 + "!"))
started = time.perf_counter()
worker.start()
worker.join(timeout=0.5)
print(f"thread:  join(timeout=0.5) returned after {time.perf_counter() - started:.2f}s")
worker.join()

# 2. Run the match in a child process and kill the process at the deadline.
started = time.perf_counter()
result = seconds_to_search(r"^(a+)+$", "", "a", 27, "!", timeout=0.5)
print(f"process: gave up after {time.perf_counter() - started:.2f}s, result: {result}")

# 3. The third-party regex module accepts a timeout argument.
started = time.perf_counter()
try:
    regex.match(r'^"(\\.|[^"])*"$', '"' + "\\" * 60, timeout=0.5)
except TimeoutError as error:
    print(f"regex:   TimeoutError({error}) after {time.perf_counter() - started:.2f}s")

# 4. The same module on the username attack: it never needed the timeout.
started = time.perf_counter()
regex.match(r"^([a-z0-9]+[._-]?)+$", "a" * 40 + "!", timeout=0.5)
print(f"regex:   username attack returned in {time.perf_counter() - started:.4f}s")

re.match signature: (pattern, string, flags=0)

thread:  join(timeout=0.5) returned after 2.60s
process: gave up after 0.64s, result: None
regex:   TimeoutError(regex timed out) after 0.50s
regex:   username attack returned in 0.0003s

Net 1: a thread with a timeout

The main thread asked join for a 0.5-second wait and got 2.6 seconds, which is roughly how long the match itself takes. Python has no supported way to kill a thread from outside, and here the waiting thread could not even wake up on time, which is consistent with the match holding the interpreter lock as in Step 4. A thread gives you nothing.

Net 2: a length limit

Limits are worth having, since they also cap memory and bandwidth, but they do not repair an exponential pattern. Step 3 measured 9.8 seconds at 28 characters for the username pattern, so a 32-character limit would still allow the 30-character input that did not finish in 20 seconds. Limits work better against quadratic bugs: in Step 3 a 2,500-character trailing-whitespace input took about 12 milliseconds, and a limit that small is often reasonable for a comment or a bio.

Net 3: a separate process

The child ran the hostile match and was killed at the deadline, and the parent had its answer (None) after 0.64 seconds, a little over the 0.5 second limit. This works, and it needs no change to the pattern. But starting a whole interpreter for each check is far heavier than a regex call, so reserve it for cases where you cannot change the pattern, such as regexes supplied by your users.

Net 4: the regex module

The third-party regex package documents the feature directly: “The matching methods and functions support timeouts. The timeout (in seconds) applies to the entire operation”. In the run above, regex.match(..., timeout=0.5) raised TimeoutError after 0.50 seconds on the quoted-string attack. Now look at the last line: the same module answered the username attack in 0.0003 seconds, with no timeout needed. Its own matching logic avoided the blow-up for that pattern, and I did not investigate why. Do not let a friendlier engine hide a bug that you will meet again in another one, such as the PCRE library inside Cloudflare’s firewall.

A timeout from any of these mechanisms limits the damage. None of them removes the defect. Removing it is the job of the next steps.

Step 6: Write the failing test first

A fix you cannot test will regress. So before touching validators.py, write a test that fails today. The test below runs each validator on hostile input through seconds_to_call, gives it a time budget, and kills it after three seconds if it is still running. It also contains ordinary tests that pin down which usernames, quoted strings and comments the validators accept now, so that a fix cannot quietly change behavior. Save it as test_regex_safety.py:

"""Regression tests: every validator must stay fast on hostile input."""
import pytest

import validators
from timing import seconds_to_call

BUDGET = 0.25  # seconds; a healthy validator answers in milliseconds
KILL_AFTER = 3.0  # seconds; a runaway is killed here and the test fails

HOSTILE = {
    "username": ("validators:is_valid_username", "", "a", 5_000, "!"),
    "quoted": ("validators:is_quoted_string", '"', "\\", 5_000, ""),
    "trailing_whitespace": ("validators:strip_trailing_whitespace", "", " ", 100_000, "x"),
}


@pytest.mark.parametrize("name", HOSTILE)
def test_hostile_input_finishes_quickly(name):
    target, prefix, unit, n, suffix = HOSTILE[name]
    seconds = seconds_to_call(target, prefix, unit, n, suffix, timeout=KILL_AFTER)
    assert seconds is not None, f"{target} was still running after {KILL_AFTER}s"
    assert seconds < BUDGET, f"{target} took {seconds:.3f}s"


@pytest.mark.parametrize("name", ["alice", "bob_smith-2", "a.b", "abc-"])
def test_usernames_that_must_stay_valid(name):
    assert validators.is_valid_username(name)


@pytest.mark.parametrize("name", ["", "-bob", "a--b", "Bob", "bob!"])
def test_usernames_that_must_stay_invalid(name):
    assert not validators.is_valid_username(name)


@pytest.mark.parametrize("text", ['""', '"hello"', '"say \\"hi\\""', '"back\\\\slash"'])
def test_quoted_strings_that_must_stay_valid(text):
    assert validators.is_quoted_string(text)


@pytest.mark.parametrize("text", ["hello", '"unterminated', '"a"b"'])
def test_quoted_strings_that_must_stay_invalid(text):
    assert not validators.is_quoted_string(text)


def test_trailing_whitespace_is_removed():
    assert validators.strip_trailing_whitespace("hello \t\n") == "hello"
    assert validators.strip_trailing_whitespace(" keep the front") == " keep the front"

Run it against the vulnerable validators.py:

python -m pytest -q -rf --tb=no test_regex_safety.py

FFF................. [100%]
===== short test summary info =====
FAILED test_regex_safety.py::test_hostile_input_finishes_quickly[username] - AssertionError: validators:is_valid_username was still running after 3.0s
FAILED test_regex_safety.py::test_hostile_input_finishes_quickly[quoted] - AssertionError: validators:is_quoted_string was still running after 3.0s
FAILED test_regex_safety.py::test_hostile_input_finishes_quickly[trailing_whitespace] - AssertionError: validators:strip_trailing_whitespace was still running after 3.0s
3 failed, 17 passed in 9.34s

(I trimmed the decorative padding that pytest adds around its banner lines.) Three tests fail, all for the same reason: each hostile input was still running after three seconds and was killed. The 17 ordinary tests pass, and they are the safety net for the fix. Each of the three failures used the full three seconds, which is why the run took about nine seconds.

Step 7: Let a scanner look for the next one

Tests only catch the hostile inputs you thought of. A static analyzer reads the pattern itself and reasons about how it can backtrack. regexploit, from Doyensec, describes itself as a tool to “Find regular expressions which are vulnerable to ReDoS (Regular Expression Denial of Service)”, and it can scan Python source. You installed it at the start. Run it on the vulnerable validators.py:

regexploit-py validators.py

Vulnerable regex in validators.py #4
Pattern: ^([a-z0-9]+[._-]?)+$
Context: USERNAME_RE = re.compile(r"^([a-z0-9]+[._-]?)+$")
---
Redos(starriness=11, prefix_sequence=SEQ{  }, redos_sequence=SEQ{ [[a-z],[0-9]]{1+}{1+} $[[a-z],[0-9]] }, repeated_character=[[a-z],[0-9]], killer=[^[a-z],[0-9]])
Worst-case complexity: 11 (exponential)
Repeated character: [[a-z],[0-9]]
Final character to cause backtracking: [^[a-z],[0-9]]
Example: '0' * 3456 + 'A'

Processed 3 regexes

(The real output draws the complexity as a row of star emoji. I replaced them with the number so the block copies cleanly.)

What the scanner found, and what it missed

It found the username pattern, called it exponential, and even proposed an attack string. That is useful. But it processed three regexes and reported one. It said nothing about the quoted-string pattern, which the stopwatch measured as exponential, or about the trailing-whitespace pattern, which is quadratic. Its README says that, for exploitability, cubic complexity or higher is typically required unless truly giant strings are allowed as input. That fits its silence about a quadratic pattern, although I did not confirm that this is the reason. For the quoted-string pattern I did not find out why it was missed.

The lesson is that a scanner is a fast first filter that finds some real bugs, while your own hostile-input tests catch others. Use both, and never treat a clean scanner report as proof.

Step 8: Fix the patterns and prove nothing else changed

The principle is the same for all three bugs: make sure every character of the input can be matched in only one way. When there is a single way to read the text, a failure is discovered in one pass and there is nothing to backtrack through.

The rewrites

• Username. Say what you mean: one or more letters or digits, then any number of (a separator followed by one or more letters or digits), then an optional trailing separator. That is ^[a-z0-9]+(?:[._-][a-z0-9]+)*[._-]?$. A separator now has to appear between runs of letters, so a run can no longer be split into pieces.
• Quoted string. Make the alternatives disjoint by taking the backslash out of the second one: ^"(?:\\.|[^"\\])*"$. A backslash can now only start an escape pair.
• Trailing whitespace. Skip the regex: str.rstrip() does the job in a single pass. If you must use a regex, a lookbehind such as (?<!\s)\s+$ makes a match start only at the beginning of a whitespace run, so each run is scanned once.

The other tool: possessive quantifiers and atomic groups

Python 3.11 added a second way to stop the engine from backing up. The 3.11 release notes say “Atomic grouping ((?>...)) and possessive quantifiers (*+, ++, ?+, {m,n}+) are now supported in regular expressions.” The re documentation explains that possessive quantifiers “do not allow back-tracking when the expression following it fails to match”, and that “x*+, x++ and x?+ are equivalent to (?>x*), (?>x+) and (?>x?) correspondingly.” Once a possessive quantifier has taken its text, it keeps it, so the engine has nothing to retry. The username pattern becomes ^(?:[a-z0-9]++[._-]?+)++$ and the quoted-string pattern becomes ^"(?:\\.|[^"])*+"$.

Now compare every pattern with its rewrites using the same stopwatch. Save this as step8_fixed_patterns.py:

"""Step 8: rewrite each vulnerable pattern and re-measure with the same attacks."""
import time

from timing import seconds_to_search

LIMIT = 15  # seconds before we kill the child process


def show(label, pattern, prefix, unit, n, suffix):
    seconds = seconds_to_search(pattern, prefix, unit, n, suffix, timeout=LIMIT)
    took = f"{seconds:8.4f}s" if seconds is not None else f"gave up after {LIMIT}s"
    print(f"   {label:<24} n={n:>9,}  {took}")


print("username")
show("original", r"^([a-z0-9]+[._-]?)+$", "", "a", 28, "!")
show("rewrite", r"^[a-z0-9]+(?:[._-][a-z0-9]+)*[._-]?$", "", "a", 1_000_000, "!")
show("possessive quantifiers", r"^(?:[a-z0-9]++[._-]?+)++$", "", "a", 1_000_000, "!")

print("quoted string")
show("original", r'^"(\\.|[^"])*"$', '"', "\\", 40, "")
show("rewrite", r'^"(?:\\.|[^"\\])*"$', '"', "\\", 1_000_000, "")
show("possessive quantifier", r'^"(?:\\.|[^"])*+"$', '"', "\\", 1_000_000, "")

print("trailing whitespace")
show("original", r"\s+$", "", " ", 40_000, "x")
show("possessive quantifier", r"\s++$", "", " ", 20_000, "x")
show("possessive quantifier", r"\s++$", "", " ", 40_000, "x")
show("lookbehind", r"(?<!\s)\s+$", "", " ", 1_000_000, "x")
text = " " * 1_000_000 + "x"
started = time.perf_counter()
text.rstrip()
print(f"   {'str.rstrip()':<24} n={1_000_000:>9,}  {time.perf_counter() - started:8.6f}s")

username
   original                 n=       28   10.2150s
   rewrite                  n=1,000,000    0.0204s
   possessive quantifiers   n=1,000,000    0.0008s
quoted string
   original                 n=       40   12.5166s
   rewrite                  n=1,000,000    0.0918s
   possessive quantifier    n=1,000,000    0.0026s
trailing whitespace
   original                 n=   40,000    3.0883s
   possessive quantifier    n=   20,000    0.1817s
   possessive quantifier    n=   40,000    0.7294s
   lookbehind               n=1,000,000    0.0096s
   str.rstrip()             n=1,000,000  0.000005s

What just happened

• The username rewrite handled a million characters in 0.02 seconds, on an input about 35,000 times longer than the one that took the original 10 seconds. The possessive version took under a thousandth of a second.
• The quoted-string rewrite and the possessive version handled a million backslashes in 0.09 and 0.003 seconds.
• The possessive \s++$ is about four times faster than the original at 40,000 characters (0.73 seconds against 3.1), but it is still quadratic: doubling the input from 20,000 to 40,000 characters multiplied its time by about four. Possessive quantifiers remove the backing up, not the repeated scanning from every start position. The lookbehind and rstrip() remove the rescanning. So “possessive” is not a universal cure.

Gotcha: the scanner cannot read possessive quantifiers. With regexploit 1.0.0, a file containing one of these new patterns makes the scanner crash instead of report. This short file, possessive_example.py, is enough:

import re

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

Running regexploit-py possessive_example.py ends with this last line of its traceback:

AttributeError: 'SreOpParser' object has no attribute 'from_POSSESSIVE_REPEAT'

The traceback shows that the tool’s parser has no handler for the operation Python uses for possessive repeats. That is a reason to prefer an unambiguous rewrite over a possessive quantifier when you can: the rewrite works on every engine and with every tool, while the possessive form ties you to Python 3.11 and to scanners that may not understand it. It also hides the ambiguity instead of removing it.

Prove that behavior did not change

A faster pattern is worthless if it accepts different input. Because these patterns are small, you can compare them exhaustively: generate every string up to a given length over a small alphabet that contains each kind of character the pattern cares about, and compare the old and new patterns on every one. This is a small cousin of the technique in how to use differential testing to safely replace legacy code. Running the original patterns here is safe, because at these string lengths the exponential cost is negligible. Save this as step8_differential.py:

"""Step 8: check that each rewrite accepts and rejects the same strings as the original."""
import itertools
import re


def every_string(alphabet, max_length):
    for length in range(max_length + 1):
        for chars in itertools.product(alphabet, repeat=length):
            yield "".join(chars)


def compare(name, old, new, alphabet, max_length):
    only_old, only_new, total = [], [], 0
    for text in every_string(alphabet, max_length):
        total += 1
        in_old, in_new = old.match(text) is not None, new.match(text) is not None
        if in_old and not in_new:
            only_old.append(text)
        elif in_new and not in_old:
            only_new.append(text)
    print(f"{name}: {total:,} strings checked")
    print(f"   accepted only by the first pattern:  {len(only_old):>5,}   {'   '.join(only_old[:4])}")
    print(f"   accepted only by the second pattern: {len(only_new):>5,}   {'   '.join(only_new[:4])}")


username_old = re.compile(r"^([a-z0-9]+[._-]?)+$")
compare("username, original vs rewrite", username_old,
        re.compile(r"^[a-z0-9]+(?:[._-][a-z0-9]+)*[._-]?$"), "a1.-!", 8)
compare("username, original vs possessive", username_old,
        re.compile(r"^(?:[a-z0-9]++[._-]?+)++$"), "a1.-!", 8)

quoted_old = re.compile(r'^"(\\.|[^"])*"$')
quoted_new = re.compile(r'^"(?:\\.|[^"\\])*"$')
compare("quoted, original vs rewrite", quoted_old, quoted_new, '"\\a', 10)
compare("quoted, rewrite vs possessive", quoted_new, re.compile(r'^"(?:\\.|[^"])*+"$'), '"\\a', 10)

trailing_old = re.compile(r"\s+$")
strings = list(every_string(" \t\nx", 8))
different = [t for t in strings if trailing_old.sub("", t) != t.rstrip()]
print(f"trailing whitespace, \\s+$ vs str.rstrip(): {len(strings):,} strings checked")
print(f"   results that differ: {len(different)}")

username, original vs rewrite: 488,281 strings checked
   accepted only by the first pattern:      0
   accepted only by the second pattern:     0
username, original vs possessive: 488,281 strings checked
   accepted only by the first pattern:      0
   accepted only by the second pattern:     0
quoted, original vs rewrite: 88,573 strings checked
   accepted only by the first pattern:    787   "\"   "a\"   "\"\"   "\\""
   accepted only by the second pattern:     0
quoted, rewrite vs possessive: 88,573 strings checked
   accepted only by the first pattern:      0
   accepted only by the second pattern:     0
trailing whitespace, \s+$ vs str.rstrip(): 87,381 strings checked
   results that differ: 0

Reading the comparison

• Username: the alphabet a1.-! holds a letter, a digit, two separators and one character the pattern rejects. Across 488,281 strings of up to eight characters, neither the rewrite nor the possessive version differs from the original in either direction.
• Quoted string: 787 strings are accepted only by the original, and none only by the rewrite. Look at the examples. The string "\" is an opening quote, a backslash and a closing quote. The original accepts it by reading the backslash as an ordinary character. The rewrite rejects it, because a backslash is an escape, and here its escape would swallow the closing quote. The string "\\"" shows how ambiguous the original was: it accepts it by reading the first backslash as ordinary and the second as an escape for the following quote, while the rewrite reads the two backslashes as one escaped backslash, sees the string close, and rejects the stray quote left over. For a parser that treats a backslash as an escape, the rewrite’s answers are the correct ones. It is still a behavior change, so decide it on purpose. The possessive version and the rewrite agree on all 88,573 strings.
• Trailing whitespace: \s+$ and str.rstrip() give identical results on all 87,381 strings built from a space, a tab, a newline and the letter x.

The caveat is that an exhaustive comparison of short strings over a small alphabet is strong evidence, not a proof.

Apply the fix

First keep a copy of the old file (copy validators.py validators_v1.py on Windows, cp validators.py validators_v1.py elsewhere) in case you want to rerun earlier steps against it. Then replace the contents of validators.py with the fixed version:

"""Input validators for a small signup service (the fixed version)."""
import re

# Each character can be matched in only one way, so a failure is found in a single pass.
USERNAME_RE = re.compile(r"^[a-z0-9]+(?:[._-][a-z0-9]+)*[._-]?$")
# A backslash now starts an escape pair or is rejected; it can no longer be either.
QUOTED_RE = re.compile(r'^"(?:\\.|[^"\\])*"$')


def is_valid_username(value: str) -> bool:
    """Letters and digits, optionally separated by single dots, underscores or hyphens."""
    return USERNAME_RE.match(value) is not None


def is_quoted_string(value: str) -> bool:
    """A double-quoted string in which a backslash escapes the next character."""
    return QUOTED_RE.match(value) is not None


def strip_trailing_whitespace(value: str) -> str:
    """Remove whitespace at the end of a comment or bio field (no regex needed)."""
    return value.rstrip()

Two details deserve a mention. The username pattern still accepts a trailing separator such as abc-, because the original did and the test suite pins it down; tightening that is a product decision for another day. And TRAILING_WS_RE is gone entirely, because the best regex is sometimes no regex. Run the tests again:

python -m pytest -q test_regex_safety.py

.................... [100%]
20 passed in 0.18s

The same 20 tests now all pass, including the three hostile-input tests that failed in Step 6.

Step 9 (optional): Switch to an engine with a guarantee

Rewriting patterns fixes the ones you know about. Some teams go further and change the engine. The RE2 library from Google was “designed and implemented with an explicit goal of being able to handle regular expressions from untrusted users without risk”, and its README says “One of its primary guarantees is that the match time is linear in the length of the input string.” Cloudflare’s postmortem lists “Switching to either the re2 or Rust regex engine which both have run-time guarantees” among the fixes it planned. The Python package is google-re2, imported as re2. Save this as step9_re2.py:

"""Step 9 (optional): a linear-time engine. Install it first with: pip install google-re2"""
import time

import re2

started = time.perf_counter()
result = re2.search(r"^(a+)+$", "a" * 100_000 + "!")
print(f"re2 on the classic attack, 100,000 characters: {result} in {time.perf_counter() - started:.4f}s")

for pattern in [r"(?=a)a", r"(a)\1"]:
    try:
        re2.compile(pattern)
    except re2.error as error:
        print(f"re2 refuses {pattern!r}: {error.args[0].decode()}")

re2 on the classic attack, 100,000 characters: None in 0.0002s
re2 refuses '(?=a)a': invalid perl operator: (?=
re2 refuses '(a)\\1': invalid escape sequence: \1

The classic attack, at 100,000 letters (more than 3,500 times longer than the 28 letters that took 5.7 seconds in Step 2), returned in 0.0002 seconds. The price of the guarantee is a smaller feature set. The README says “backreferences and look-around assertions are not supported”, and the two refusals above show that at compile time. The library also writes RE2’s own error messages to standard error, which I did not include in the output above.

Step 10: Confirm everything works end to end

Run the loop one more time against the fixed code. First the freeze demo, with the same hostile request as in Step 4:

python freeze_demo.py

health check while idle:            18.2 ms
health check during the attack:     13.0 ms
the attack request itself took:      3.0 ms
health check after the attack:      15.6 ms

The hostile request now takes 3 milliseconds instead of 9.8 seconds, and the health check during the attack answers in 13 milliseconds. (Single-request timings vary a little from run to run; the first number was 2.5 milliseconds in an earlier run of the same script.) Then run the scanner on the fixed file, which contains no possessive quantifiers:

regexploit-py validators.py

Processed 2 regexes

It processed both remaining regexes and reported nothing, and the tests from Step 8 already showed 20 passed.

The mistakes to avoid

• Testing only with valid input. Step 2 showed the same letters finishing in a microsecond or taking five seconds, depending on one trailing character.
• Relying on a length limit for exponential patterns. Thirty characters were enough to defeat the username check.
• Relying on a thread timeout. It returned only after the match did.
• Trusting a friendlier engine. The regex module shrugged off the username attack and still timed out on the quoted-string one.
• Rewriting without comparing behavior. The quoted-string rewrite changed what is accepted, and only the exhaustive comparison showed how.
• Treating a clean scanner report as proof. The scanner found one of three real problems.
• Believing possessive quantifiers cure everything. The quadratic pattern stayed quadratic.

Audit your own code

1. Search your project for re.compile(, re.match(, re.search(, re.sub(, re.findall( and any web framework validators that take a pattern.
2. For each pattern that touches text a user can influence, look for the three shapes from Step 3: a repeated group that contains a repetition, alternatives that can match the same text, and a repeated character class followed by an anchor such as $.
3. Cap input lengths before matching, add a hostile-input test for each pattern like the one in Step 6, and run a scanner in CI as a first filter.
4. If you must accept patterns from users, run them in a separate process with a deadline (Step 5) or in a linear-time engine (Step 9).

Next steps

ReDoS belongs to a family of bugs in which text that a stranger controls crosses into something that interprets it. This site has tutorials on several relatives: preventing server-side request forgery, preventing SQL injection with parameterized queries, stopping XSS with a Content Security Policy, preventing path traversal in file downloads and archive extraction, and preventing argument injection in a Windows URI protocol handler. If you build scanners that run regexes over files you did not write, like the one in detecting npm packages that hide malware in runtime code, the hostile-input test from Step 6 is worth adding to them. And the freeze in Step 4 is a cousin of the failure covered in how to build a bulkhead in Python, where one slow piece of work starves healthy work that shares its threads.

One more validator gotcha, unrelated to speed, is worth knowing about. The Python documentation says $ “Matches the end of the string or just before the newline at the end of the string”. So a validator built on ^...$ and re.match also accepts text with a trailing newline. I checked: re.match(r"^[a-z]+$", "bob\n") matches, while re.fullmatch(r"[a-z]+", "bob\n") does not. The fixed is_valid_username from this tutorial returns True for "alice\n" for the same reason. When you adapt the code for real use, switch the validators to re.fullmatch and add a test for it.