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. This deliberately simplified example appears to validate email-shaped input, 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. alice@example.com matches. bob.smith@company.io matches. not an email is rejected instantly. It passes the obvious functional tests, and it's a loaded gun. It is not a complete definition of valid email either; production validation should match the contract your system actually supports rather than pretending one regex implements every email standard.

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 in one observed run
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.

Exact timings depend on the runtime, CPU, and measurement setup. The useful evidence is the growth rate: adding two characters repeatedly multiplies the work instead of adding a roughly fixed amount. Reproduce that shape on the runtime you deploy before attaching a precise latency claim to a pattern.

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 to the domain contract. If your application accepts email addresses up to 254 characters, reject the 255th before invoking the regex. A username, route segment, or product code may have a much smaller legitimate maximum. Exponential blowup needs runway; do not accept an unbounded string when the business value is bounded.

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);

The same poison-input benchmark no longer shows the exponential cliff. That is the guarantee that matters: the work grows linearly with input length, not that one machine produced a particular stopwatch number. Microsoft's regular-expression options documentation documents both the linear-time guarantee and the unsupported constructs, including backreferences and lookarounds. Check compatibility before switching an existing pattern.

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]+)*@[a-zA-Z0-9-]+\.[a-zA-Z]{2,}$ expresses the same intended local-part shape, but every character now has one place to go, so there is nothing to backtrack over. Unambiguous patterns are fast even on the old engine.

Put the hostile shape in the test suite

Functional examples prove the language accepted by the regex. Add adversarial examples that prove the work is bounded too. Keep the timeout in the production regex so a failed performance assumption still terminates:

[Fact]
public void EmailPattern_RejectsPoisonInputWithinItsTimeout()
{
    var poison = new string('a', 10_000) + "!";

    Assert.False(EmailPattern.IsMatch(poison));
}

Run that test with the non-backtracking or rewritten pattern. Do not run an unbounded vulnerable regex in a test task and merely race it against Task.Delay; losing the race does not stop the CPU work. A regex timeout or the non-backtracking engine is the mechanism that actually bounds it.

Also review who controls the pattern. RegexOptions.NonBacktracking protects against expensive input for supported expressions; it does not make accepting arbitrary user-supplied patterns safe. Treat patterns as trusted configuration unless regex-as-a-service is deliberately part of the product and isolated accordingly.

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 C# secure coding exercises exist 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 guide explains the full catalog, and the track lives on Pro. The reflex transfers to every codebase you'll ever touch.