ReDoS: A Quiet Denial-of-Service Risk

Regular expression denial of service (ReDoS) often gets classified as a low-severity issue — but it can still bring down a server if an unauthenticated attacker can reach the vulnerable code. The tricky part is that these bugs don't come from careless coding. They come from an obscure edge case in the regex engine itself, which makes them easy to introduce by accident and confusing to fix by hand.

Fortunately, automated detection has gotten much better. CodeQL queries bundled with code scanning since 2017, with improvements in 2021, have caught ReDoS in JavaScript, Python, Java, C#, and Ruby codebases. The manual part is still up to you. Over time, patterns have emerged that make the fixes much more predictable — sometimes by changing just a single metacharacter.

The Backtracking Problem

The core issue is that many popular languages, including Python and JavaScript, use backtracking implementations for regexes. If the input doesn't match, the engine tries every possible path through the pattern. When choices like | and repetitions like + are combined, the search tree can blow up to exponential size.

Consider a pattern like (a+)+$. On an input of "aaaaab," the engine can't quickly reject it. Each outer + iteration splits the inner a+ repeatedly, and the engine explores many impossible partitions before failing. The runtime balloons exponentially with input length.

Some languages dodge this entirely. Go and Rust use linear-time engines. So does Google's RE2 library for C++. Java (from version 9) and Ruby (from 3.2.0) made changes to mitigate the worst behavior.

Fixing a ReDoS, Step by Step

A typical example from Airbnb's streamalert project shows how these patterns look and how to fix them. The vulnerable regex was a parser for graph definitions, around 77 characters of dense logic.

Reproduce Before You Think

Start with a proof-of-concept that actually triggers the slowdown. A key detail: the bug fires when the input does not match, forcing the engine to exhaust the search. But if your string happens to match quickly, the PoC won't hang. Appending an unusual character, like %, to a borderline-valid input forces a mismatch and exposes the exponential behavior.

Shrink the Regex

79 characters of dense regex is too much to reason about directly. Strip everything that isn't necessary to trigger the bug. Safe operations include:

  • Deleting optional sections like X? or X*.
  • Replacing X+ with X.
  • Splitting alternations like X|Y into just one side.
  • Shrinking character classes from [a-z0-9] to [ab].

After each simplification, re-run the PoC to verify the ReDoS is still present.

Applying that to the streamalert regex exposed this core culprit:

(y[yx]+)+

On a string like "yxyxyxyxyxyx," this inner group has many valid parses: (yx)(yx)(yx), (yxyx)(yxyx), and so on. That's the ambiguity that fuels exponential backtracking.

Rewrite for a Single Parse

The key observation: the inner segment y[yx]+ already matches any string starting with y and followed by a mix of x and y. The outer + adds nothing but ambiguity — it doesn't expand the set of accepted strings at all. Removing it fixes the ReDoS and preserves the regex's behavior.

Apply the same fix to the original pattern: remove the outer + that was wrapping that repeated inner group.

Verify With a Fuzzer

Regexes are famously hard to test manually. It's worth setting up an automated differential test. With Python, the atheris fuzzer can constantly compare your old and new patterns against random inputs, checking that both always go to the same match/no-match outcome.

A basic harness just needs to call regex_old.fullmatch(s) and regex_new.fullmatch(s) on the same inputs and flag any difference. Atheris will find counterexamples quickly for most basic divergences; leave it running for a few hours to be confident nothing subtle slipped in. If your pattern is complex, increase -max_len so the fuzzer can generate longer inputs that exercise the full grammar.

One note from experience: similar vulnerable URL regexes circulate through many repositories, under slightly different names. The same structural fix works across them all — trim redundancy, not matching power.

How a shared URL regex spread ReDoS across projects

While auditing open source projects for ReDoS vulnerabilities, we kept encountering the same vulnerable regex in unrelated codebases. The pattern in question is a large regex used for parsing URLs, and it appears in projects like validators, textacy, and dparse. The origin is clear: many of these regexes carry a comment pointing to a shared source.

# source: https://gist.github.com/dperini/729294

The regex in that gist no longer has a ReDoS, but its revision history shows it did until 2018-09-12. Many projects still rely on older, vulnerable copies. That is unsurprising given how widely the pattern has been shared—a Stack Overflow answer from 2012 helped spread it.

Two mistakes in reporting the issue

When we reported this vulnerability to affected projects in 2021, we made two errors. First, we never checked the latest version of the gist regex. Had we done so, we would have seen the fix and could have advised projects to upgrade instead of patching old code. Second, we assumed the regex was too large and complex to fix. In reality, removing just two + characters resolves the ReDoS. Since discovering this, we have submitted corrections via pull requests to textacy and validators.

Fixing the URL validator ReDoS

The repair process follows the same reduction steps described earlier. Although the full regex is intimidating, large sections can be eliminated quickly. Using textacy as an example, the vulnerability triggers with a long input string:

http://0.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00…

Once a standalone proof of concept is built, unrelated segments—such as lines 56-69 of the source—can be dropped. After a few reduction rounds, the PoC becomes far more manageable:

import re
url_regex = re.compile(
    r"http://"
    r"("
    # host name
    r"(([0-9]-?)*[0-9]+)"
    # domain name
    r"(\.([0-9]-?)*[0-9]+)*"
    # TLD identifier
    r"[a-z]"
    r")",
    flags=re.IGNORECASE
)
url_regex.fullmatch("http://0" + ".00" * 100)

Further reduction reveals the root cause: two + quantifiers that create the catastrophic backtracking path:

# host name
r"(?:(?:[a-z\u00a1-\uffff0-9]-?)*[a-z\u00a1-\uffff0-9]+)"
# domain name
r"(?:\.(?:[a-z\u00a1-\uffff0-9]-?)*[a-z\u00a1-\uffff0-9]+)*"

After several hours of fuzzing to confirm the fix, the pull request was merged.

Why ReDoS persists

ReDoS is an avoidable vulnerability class. Deterministic finite automaton theory has been well understood since the 1940s, so exponential regex matching is an engineering choice, not an inevitability. Ruby 3.2.0 is one example of a language improving its regex engine to curb such issues. Code scanning tools can detect ReDoS, which should help drive it out of practice. If your project is affected, the reduction and repair steps outlined here should let you resolve it quickly.