ReDoS: catastrophic backtracking in a regex input check

This is a scripted Python and curl experiment with downloadable source and responses. No AI agent or model ran the test.

What ReDoS is and what the fixture covers

CWE-1333 lists ReDoS and "catastrophic backtracking" as names for one weakness: a regular expression whose worst-case cost is inefficient and possibly exponential. CWE says backtracking becomes a weakness when the number of possible attempts is exponential in the input length, the input can fail to match, and the input can be long enough. OWASP describes the same attack as a regex denial of service that hangs a program for a very long time.

The fixture is a display-name check. A name is a run of word characters, optionally separated by whitespace, and the vulnerable pattern is ^(\w+\s?)*$. The outer * repeats a group, and the group itself repeats \w+. A run of n letters can be cut into groups in 2^(n-1) ways. When the input ends in a character the pattern rejects, such as !, the engine tries those cuts before it reports failure. That count matches the doubling per letter that we measured.

• Target: two short-lived HTTP servers on 127.0.0.1, started by the runner on OS-assigned ports.
• Requests: GET /validate?name=... only. Inputs are runs of the letter a plus fixed demo names.
• Limits on the test itself: the longest attack input has 26 letters plus !. Every curl call has a hard 8 second limit, and the ladder stops climbing if one request takes longer than 4 seconds.
• Server design: one thread. A slow match blocks the requests queued behind it, which is how a small server is taken down by one request.

The vulnerable mode is intentionally insecure. Only run this against the servers the script starts. The Acceptable Use Policy describes authorized use. This article gives no permission to send crafted input to any other system.

Run the ReDoS experiment

Download fixture.py and verify.py into one directory. You need Python 3.9 or later and curl. The code uses only the standard library. Inspect the source, then run:

python3 verify.py --output rerun

The output directory must be new. The runner starts each mode in turn, sends 34 real curl requests (32 cases plus the two attack requests of the collateral test) with --noproxy '*' and the hard time limit, saves every raw response and stops the servers. One extra check times the fixed pattern in-process.

Our run on 11 November 2026 (recorded 09:58 UTC) used fixture version 1.0.0, Python 3.15.2 and curl 8.7.1 on Darwin arm64. It exited with {"cases": 32, "claims": 5, "passed": true, "failures": []}. Passing means every case returned its expected status and five timing claims held. Versions, commands and source SHA-256 hashes are in results.json.

Timings vary by machine and by run. Your absolute numbers will differ from ours. The pattern to look for is the growth from one step to the next.

Observed timings: catastrophic backtracking against the fix

Each attack input is n letters followed by !. The pattern cannot match it, so the answer is always 400. The table shows the status, the total time curl measured, and the time the server reported for the regex match in the X-Regex-Ms header.

In vulnerable mode each step of two letters multiplied the regex time by between 3.9 and 4.2. The fixed server answered every step in about 6 to 7 ms, almost all of it curl and loopback overhead, with 0.001 to 0.002 ms spent in the regex.

The collateral test sent a valid name, Ada Lovelace, 0.2 seconds after starting a 24-letter attack request. In vulnerable mode that valid request took 567.5 ms, against 7.9 ms when sent alone. In fixed mode it took 9.0 ms, against 7.1 ms alone. The attacker's input never has to be accepted to cause the delay.

Controls show that the fix did not break normal use. Cells show the status each mode returned.

Two rows changed on purpose. The fixed pattern allows only a single space between words, so the tab-separated name that vulnerable mode accepted is now rejected. The length cap rejects a valid 65-letter name. Check both changes against real names before you ship something like this.

Verify a ReDoS finding before you report it

A slow response alone does not show ReDoS, because a busy host or a cold cache also produces one. Three observations together do: time grows steeply as one input gets longer, the same-length inputs that match stay fast, and the time is spent in the regex. This is the command for the 26-letter request, using the recorded vulnerable port:

curl --noproxy '*' --silent --show-error --include --http1.1 \
  --connect-timeout 1 --max-time 8 --get \
  --data-urlencode 'name=aaaaaaaaaaaaaaaaaaaaaaaaaa!' \
  http://127.0.0.1:50025/validate

The recorded response contains these values, with some headers omitted:

HTTP/1.0 400 Bad Request
X-Regex-Ms: 3119.118

{"length": 27, "valid": false}

The server reports 3119.118 ms inside the match, so the delay is not network time. The valid 26-letter name returned 200 in 6.1 ms, which shows that length alone does not cause it. Repeating the request at 16, 18, 20, 22 and 24 letters gave the growth in the table. Together they verify catastrophic backtracking in this fixture.

A report should state the endpoint, the parameter, the pattern if you have the source, the input shape, the measured times at three or more lengths, the control that stays fast, and the worst case you allowed yourself. Keep the worst case small. You do not need a ten-minute hang to prove the point. The same positive and negative control habit appears in our API authorization testing write-up, and the timing attack post covers measuring response time with a stated method.

Rewrite the pattern, cap the input, retest

Fixed mode applies two changes from the same fixture.py. The first is a pattern in which each input has only one way to match. Words are separated by exactly one space, so the engine has no alternative cuts to try. The second is a length cap checked before the regex runs:

FIXED_PATTERN = re.compile(r"^\w+(?: \w+)*$")
MAX_LENGTH = 64

if fixed and len(name) > MAX_LENGTH:
    return self.reply(413, {"error": "name_too_long", "max_length": MAX_LENGTH})

CWE-1333 rates removing nested quantifiers and avoiding backtracking as highly effective, and limiting input length as moderately effective. The cap here is a second layer. The runner also timed the fixed pattern alone, with no cap, on a 50,001-character attack input: it rejected the input in 0.817 ms in-process.

The retest repeated every case against a fresh server in fixed mode on port 50085. All six attack lengths returned 400 in 6.2 to 6.9 ms, the 1,000-character attack returned 413 without reaching the regex, and the attack at the cap (63 letters plus !) returned 400 with 0.002 ms spent in the match. Valid names still returned 200.

The fixture is also on GitHub: web-security-fixtures.

Inspect the evidence bundle

• Machine-readable results: all cases and claims with expected and observed values, timings, versions and hashes.
• Exact recorded curl commands: the ports refer to the finished run.
• SHA-256 manifest: an integrity check, not independent attestation.
• Fixture instructions and limitations, server source and verification source.

All inputs are synthetic. The raw responses include dates and server headers. No production credentials or customer data were involved.

What this experiment does not cover

One toy pattern in one regex engine, on one machine, in one run per input. We did not test other languages, other engines, other vulnerable shapes such as overlapping alternation, or polynomial rather than exponential cases. We did not test a multi-threaded or multi-process server, where a request ties up one worker instead of the whole process. We did not test a match timeout or an engine that guarantees linear time. Python 3.15.2 is the only version we ran, so the absolute times will not carry over.

The experiment also does not show that a length cap is enough on its own. A pattern with polynomial backtracking can still hurt inside the cap. It does not show how an attacker would find a vulnerable pattern in a real application. The fixed pattern ends in $, which in Python also matches before a final newline, so a name ending in a newline passes it. The recorded run did not test that. re.fullmatch closes the gap. Request-count limits such as those in our API rate limiting experiment count requests, and here a single request is the problem.

Excession Labs runs this kind of input-handling test in its security assessments.