ReDoS: the innocent regex that can take down your API

There's a denial-of-service attack that requires no botnet, no traffic flood, and no exploit code. The attacker sends your API one short string, maybe thirty characters, and one of your CPU cores pins at 100% for a minute. A handful of requests later, your service is gone. The vulnerability was a regular expression, probably one validating an email address, and it was sitting in your codebase looking like the most harmless line in the file.

This is ReDoS, regular expression denial of service, and it's the vulnerability class with the best disguise in the business. SQL injection at least looks like string concatenation. A vulnerable regex looks like input validation. It is input validation. It's just validation with an exponential worst case that nobody priced in.

A regex that works perfectly

Here's the kind of pattern that ships every day. It validates emails, allowing dot- and dash-separated chunks before the @:

private static readonly Regex EmailPattern =
    new(@"^([a-zA-Z0-9]+[._-]?)*[a-zA-Z0-9]+@[a-zA-Z0-9-]+\.[a-zA-Z]{2,}$");

public bool IsValidEmail(string input) => EmailPattern.IsMatch(input);

Test it and it behaves. [email protected] matches. [email protected] matches. not an email is rejected instantly. It passes review, it passes every functional test you'll ever write for it, and it's a loaded gun.

The trigger is an input that almost matches. Feed it a run of letters with a poison character at the end, so the overall match must fail:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

Thirty as and a !. Here's what that costs, measured with Stopwatch on .NET's default regex engine:

Input	Time to return false
20 chars + !	61 ms
24 chars + !	922 ms
26 chars + !	3.6 s
28 chars + !	16.6 s
30 chars + !	58 s

Read the growth, not the numbers: every two extra characters roughly quadruples the time. That's an exponential curve, and it means no hardware upgrade saves you. At 35 characters you're into hours. The attacker controls the exponent with their keyboard.

Why it explodes

The culprit is the shape ([a-zA-Z0-9]+[._-]?)*: a group that can match one or more characters, with an optional separator, repeated zero or more times. The separator being optional is the killer detail, because it means a plain run of letters like aaaa can be carved up by that group in many different ways: one chunk of four, two chunks of two, a chunk of one and a chunk of three, and so on. The number of possible carvings grows exponentially with the length of the run.

While the input is matching, none of this matters; the engine finds one carving and moves on. But when the match fails at the end (our !, or a missing @), a backtracking engine doesn't just give up. It backtracks and dutifully tries every other carving, on the chance that a different split of aaaa would have let the rest succeed. None of them can. It checks anyway. That's the minute of CPU: an exhaustive tour of an exponential space, to conclude "no."

The pattern to fear is a quantifier inside a quantifier where the inner and outer can trade characters between them: (a+)*, (\w+\s?)*, (x+x+)+. If two different carvings can consume the same text, failure means trying all of them.

The .NET defenses, in the order you should reach for them

First, cap the input. No email is 200 characters. Length-check before the regex ever runs; exponential blowup needs runway, and you can simply not provide it.

Second, use the engine that can't backtrack. Since .NET 7 there's RegexOptions.NonBacktracking, which matches in time proportional to the input length, guaranteed, at the price of dropping backreferences and lookarounds:

private static readonly Regex EmailPattern =
    new(@"^([a-zA-Z0-9]+[._-]?)*[a-zA-Z0-9]+@[a-zA-Z0-9-]+\.[a-zA-Z]{2,}$",
        RegexOptions.NonBacktracking);

Same pattern, same 30-character attack string: microseconds. I fed the NonBacktracking engine a ten-thousand character poison input and it returned in 6 ms. The exponential cliff is not mitigated. It's gone, by construction.

Third, set a timeout as the backstop. Any regex that touches untrusted input should have a match timeout, so the worst case is a caught exception instead of a pinned core:

private static readonly Regex EmailPattern =
    new(pattern, RegexOptions.None, matchTimeout: TimeSpan.FromMilliseconds(100));

// A poison input now throws RegexMatchTimeoutException after ~100 ms.
// Catch it and treat the input as invalid; don't retry it.

And when you own the pattern, remove the ambiguity itself: ^[a-zA-Z0-9]+([._-][a-zA-Z0-9]+)*@ says the same thing as the original, but every character now has exactly one place to go, so there's nothing to backtrack over. Unambiguous patterns are fast even on the old engine.

Validation that fails your tests instead of your pager

The nasty property of ReDoS is the same one that runs through most security bugs: the vulnerable version is functionally correct. Every green test agrees the emails validate. The difference between the safe regex and the time bomb is invisible to a suite that only asks "does it work," because the answer is yes, right up until someone asks "does it work when I want to hurt you."

That adversarial question is exactly what Katabench's secure-coding track exists to ask. Every puzzle there hands you code that is functionally correct and quietly exploitable, a file download open to path traversal, a lookup that builds its SQL by string concatenation, and the grading runs two suites at once: functional tests that must stay green, and an adversarial suite that throws real attack payloads at your fix. Leave the hole in and the attack tests fail you, the same way production would, minus the incident review.

Fix it, resubmit, and watch the same payloads bounce off. Once an exploit has failed against code you hardened, patterns like the nested quantifier stop being trivia from a blog post and start being something your eyes snag on in review. The track lives on Pro, and the reflex transfers to every codebase you'll ever touch.