One regex pinned CPU at 100%: catastrophic backtracking and ReDoS in Python

On a Monday morning our on-call got paged for the account service: p99 latency on POST /profile went from 80 ms to the 30-second gateway timeout, and CPU on every pod sat at 100%. Request volume was normal. The load balancer logs showed a handful of 504s, then the health checks started failing as each Gunicorn worker stopped answering:

[2026-09-07 08:14:52 +0000] [1] [CRITICAL] WORKER TIMEOUT (pid:27)
[2026-09-07 08:14:52 +0000] [27] [INFO] Worker exiting (pid: 27)
[2026-09-07 08:14:53 +0000] [1] [ERROR] Worker (pid:27) was sent SIGKILL! Perhaps out of memory?

Memory was flat, so the SIGKILL hint was a red herring. Something was burning CPU inside a request.

Reproducing it

We pulled the request bodies for the 504s from the gateway's sampled logs. All of them came from one client and set the display_name field to a long run of letters and spaces followed by a single exclamation mark. Replaying one against a local container reproduced the freeze every time.

What we ruled out

• Database contention. pg_stat_activity showed no long queries or lock waits during the incident.
• A deploy. The last deploy was four days earlier and had not touched the profile endpoint.
• Garbage collection or memory pressure. RSS was stable and the GC counters did not move.

Root cause

We attached py-spy to a stuck worker. Every dump we took, a few seconds apart, showed the same top frame:

py-spy dump --pid 27

Thread 27 (active): "MainThread"
    validate_display_name (account/validators.py:12)
    update_profile (account/views.py:58)

Line 12 is a single call to a compiled pattern's match method, which runs entirely in C, so py-spy shows the Python line that called it. The validator was a pattern someone had written to allow words separated by single spaces:

DISPLAY_NAME = re.compile(r"^([A-Za-z]+\s?)*$")

The group ([A-Za-z]+\s?) can match a run of letters in many different ways because the space is optional, and the outer * repeats that group. When the input almost matches and then fails at the end (the trailing !), the backtracking engine tries every way of splitting the letters between iterations before giving up. The number of splits doubles with every extra character. That is catastrophic backtracking, and when an attacker controls the input it is a regular expression denial of service (ReDoS).

What is happening under the hood

Python's re module, like the engines in Perl, PCRE, Java and JavaScript, is a backtracking matcher. It walks the pattern left to right, and whenever it has a choice (how many characters a + takes, whether \s? matches), it records a backtrack point. If the match later fails, it returns to the most recent choice and tries the next option.

For ^([A-Za-z]+\s?)*$ and the input aaaa!, the engine can match aaaa as one iteration, or aaa + a, or aa + aa, or a + a + a + a, and so on: 2^(n-1) ways for n letters. Every one of them reaches !, fails the $, and backtracks. With 30 letters that is over 500 million paths. There is nothing the engine can short-circuit, because each path looks different to it.

The shapes that cause this are well known:

Automaton-based engines such as RE2, Rust's regex crate and Go's regexp do not backtrack. They guarantee time linear in the input length, and in exchange they do not support backreferences or lookaround.

Environment

Minimal reproduction

import re
import time

pattern = re.compile(r"^([A-Za-z]+\s?)*$")

for n in (18, 20, 22, 24, 26):
    payload = "a" * n + "!"
    start = time.perf_counter()
    pattern.match(payload)
    print(n, f"{time.perf_counter() - start:.2f}s")

On a laptop this printed roughly 0.03s, 0.12s, 0.5s, 2.0s and 8.1s: each two extra characters multiply the time by four. A 40-character value would run for days.

Who is affected

Any code that runs a backtracking regex with an ambiguous quantifier on input the caller controls: form validators, log parsers fed user agents, URL routers, email and phone checks copied from old answers. Length limits help only a little, because exponential growth turns even 50 characters into minutes.

The fix

1. Remove the ambiguity. The intent was "words of letters, separated by single spaces". Written so each character can be consumed only one way:

-DISPLAY_NAME = re.compile(r"^([A-Za-z]+\s?)*$")
+DISPLAY_NAME = re.compile(r"^[A-Za-z]+(?: [A-Za-z]+)*$")

Now a space is mandatory between words, so there is exactly one way to split any input. The rewritten pattern fails "a" * 10000 + "!" in microseconds.

We also noticed the old pattern accepted an empty string and trailing spaces, which the product did not want, so the rewrite fixed two validation bugs at once.

2. Use atomic groups or possessive quantifiers where rewriting is hard. Since Python 3.11, re supports (?>...) and *+, ++, ?+. They discard backtrack points once a group has matched:

SLUG = re.compile(r"^(?>[a-z0-9]+-?)*$")

This is handy for patterns that are awkward to restructure, but it changes matching semantics, so we add tests for valid inputs whenever we use it.

3. Run untrusted patterns or inputs through RE2. For the log-search feature, where users supply their own patterns, we switched to Google's RE2 bindings:

import re2  # pip install google-re2

def safe_search(user_pattern: str, text: str) -> bool:
    try:
        compiled = re2.compile(user_pattern)
    except re2.error:
        raise ValueError("unsupported pattern")
    return compiled.search(text) is not None

Patterns with backreferences fail to compile, which we report as a validation error.

4. Bound the input before matching. The field already had a 255-character limit, but it was enforced after validation. We moved the length check first, so the regex never sees oversized input.

Alternatives and trade-offs

• The third-party regex module with a timeout. regex.match(pattern, text, timeout=0.05) raises TimeoutError. It works, but it turns a correctness problem into an error rate and still burns 50 ms of CPU per hostile request.
• Running validation in a subprocess with a deadline. Isolates the damage but costs a process per request. We only consider it for user-supplied patterns that RE2 cannot express.
• Dropping the regex. For simple checks, str.isalpha() on each word after split(" ") is clearer and has no backtracking at all. We did this in two other validators.

How to test the fix

A unit test that asserts both behaviour and a time budget on adversarial input:

import time
import pytest
from account.validators import DISPLAY_NAME

@pytest.mark.parametrize("value", ["Ada", "Ada Lovelace", "Grace Brewster Hopper"])
def test_accepts_names(value):
    assert DISPLAY_NAME.match(value)

@pytest.mark.parametrize("value", ["", "Ada ", " Ada", "Ada  Lovelace", "Ada!"])
def test_rejects_invalid(value):
    assert not DISPLAY_NAME.match(value)

def test_no_catastrophic_backtracking():
    hostile = "a" * 5000 + "!"
    start = time.perf_counter()
    DISPLAY_NAME.match(hostile)
    assert time.perf_counter() - start < 0.05

pytest tests/test_validators.py -q

Confirming in production

After deploying we replayed the captured payloads against a canary pod and watched CPU and latency:

for i in $(seq 1 50); do
  curl -s -o /dev/null -w '%{http_code} %{time_total}\n' \
    -X POST https://staging.example.com/profile \
    -H 'Content-Type: application/json' \
    -d "{\"display_name\": \"$(printf 'a%.0s' $(seq 1 60))!\"}"
done | sort | uniq -c

Every request returned 400 in under 20 ms, and container CPU stayed at baseline. In production the WORKER TIMEOUT log line has not appeared since, and p99 for the endpoint is back to 80 ms.

Regression guard

• CodeQL runs on every pull request with the default Python suite, which includes the py/redos and py/polynomial-redos queries. They flag exponential and polynomial patterns reachable from request data.
• Our review checklist asks for a linear-time justification on any new pattern with nested quantifiers.
• The time-budget test exists for every validator regex in the module.
• An alert fires if any Gunicorn worker logs WORKER TIMEOUT more than twice in five minutes.

Security implications

This was a denial-of-service vulnerability: one unauthenticated request per worker was enough to take a pod offline, and a few dozen requests took the whole service down. No data was exposed. The fix narrows what the field accepts, which also blocks some junk that had been stored in profiles, and RE2 removes the risk for the user-pattern feature entirely. We reviewed other services for the same validator (it had been copied twice) and fixed both copies.

Prevention checklist

• Never put a quantified group inside another quantifier when the inner part can match the same text more than one way.
• Check length before matching untrusted input.
• Use RE2 or another linear-time engine for user-supplied patterns.
• Keep CodeQL ReDoS queries enabled and treat their alerts as security bugs.
• Add a time-budget test with an almost-matching input for each validator.

References

• Python re module documentation (atomic groups, possessive quantifiers): https://docs.python.org/3/library/re.html
• OWASP: Regular expression Denial of Service: https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS
• CodeQL query help, inefficient regular expression: https://codeql.github.com/codeql-query-help/python/py-redos/
• RE2 syntax and guarantees: https://github.com/google/re2/wiki/Syntax
• google-re2 Python package: https://pypi.org/project/google-re2/