You write a regex pattern to validate a token. Something simple. You test it with real input, it works perfectly, you ship it, and you move on to the next ticket. Weeks later your app grinds to a halt under what looks like a tiny amount of traffic. No memory leak. No database lock. No obvious culprit in your logs. Just one thread, pinned at 100% CPU, doing absolutely nothing useful.

The cause was sitting in your code the whole time. It was that regex.

This is one of the sneakier bugs a backend developer can write, because it doesn't fail the way bugs normally fail. It doesn't throw an exception. It doesn't return the wrong value. It just runs forever on a tiny, perfectly ordinary-looking string. And if you're validating anything user-submitted, alphanumeric tokens, CSV fields, tracking IDs, usernames, you have probably written a version of this exact mistake without knowing it.

The setup: a regex that looks completely reasonable

Say you're validating tokens submitted by users. Something like a tracking ID or an alphanumeric code. You want to allow letters, numbers, and underscores, and you want the whole string to match from start to end. A natural first attempt looks like this:

import re

# Looks safe, but the nested '+' and '*' create exponential paths

VULNERABLE_REGEX = re.compile(r"^([a-zA-Z0-9_]+)*$")

def validate_token(user_input: str) -> bool:
    return bool(VULNERABLE_REGEX.match(user_input))

If you test this with valid tokens, it works instantly. Feed it user_123_abc and you get a clean True in microseconds. Everything looks fine. It passes code review. It passes your test suite. It ships.

The problem only shows up when someone sends a string that is almost valid but not quite, something like thirty or forty valid characters followed by a single invalid one at the very end. At that point, the regex engine doesn't just fail quickly. It tries to fail in every possible way before giving up, and the number of ways grows exponentially with the length of the input.

Why this happens: nested quantifiers are ambiguous

The root issue is the structure ([a-zA-Z0-9_]+). You have a repetition group (+) nested inside another repetition group (). To the engine, this creates massive ambiguity about how to split the string into pieces. A run of twenty valid characters could be read as one big group of twenty, or two groups of ten, or four groups of five, or twenty groups of one, and so on. There are an enormous number of equally valid ways to partition that run.

As long as the entire string matches, the engine doesn't care which partition it used, so it picks one and moves on instantly. But the moment something downstream fails to match, like that final invalid character, the engine has to go back and try every other partition of the string before it can conclude that none of them work either. That backtracking process is where the exponential blow-up happens.

This is called Regular Expression Denial of Service, or ReDoS, and it's one of the few bug classes where a single request from a single user can take down an entire server thread with nothing but a moderately sized string.

The professional impact: this is a denial-of-service vector, not a quirky edge case

It's tempting to file this away as a theoretical concern, but the impact is very real and very practical:

A malicious actor doesn't need a sophisticated exploit. They just need to find one input field in your application backed by a vulnerable regex, and send a crafted string of thirty to fifty characters. That's it. The regex engine will burn 100% of a CPU core trying to resolve the match, and because most web frameworks process requests on a limited pool of threads or within a single event loop, that one request can block everything else behind it.

Send a handful of these requests in parallel, and you can exhaust your entire application's available threads or event-loop cycles. The service becomes completely unresponsive to legitimate users, not because your database is slow, not because you're under heavy genuine traffic, but because of one badly shaped regular expression doing busywork that produces no useful output at all.

In a cloud environment, this gets worse before it gets better. Your monitoring sees CPU usage spike and, doing exactly what it's designed to do, triggers auto-scaling. You spin up more instances to handle the "load." The attacker's strings hit those instances too. You're now paying for compute capacity to process malicious garbage, and your bill goes up at the same rate your service goes down.

The fix: stop the engine from backtracking

There are two complementary strategies here, and the strongest approach uses both.

Option A: Linearize the pattern. In a lot of cases, the nested quantifier isn't even doing anything useful. If you actually walk through what ([a-zA-Z0-9_]+)* is trying to express, you'll often find it's logically identical to a much simpler pattern with no nesting at all:

import re

# Linearize: remove the nested duplication entirely

CLEAN_REGEX = re.compile(r"^[a-zA-Z0-9_]*$")

This matches exactly the same set of strings as the vulnerable version, but it does so in linear time. There's no ambiguity for the engine to resolve, so there's nothing to backtrack into.

Option B: Use possessive quantifiers (Python 3.11+). If your pattern genuinely needs the grouping structure for some other reason, modern Python gives you a tool that removes the ambiguity directly. A possessive quantifier, written with ++, tells the engine that once a group has matched, it should never backtrack into that match later. If the overall pattern eventually fails, the engine fails immediately instead of trying every other way to split the string.

import re

# Possessive quantifier: once matched, the group is locked and won't backtrack

MODERN_SAFE_REGEX = re.compile(r"^([a-zA-Z0-9_]+)++$")

def validate_token_safe(user_input: str) -> bool:
    return bool(MODERN_SAFE_REGEX.match(user_input))

This converts the pattern's worst-case behavior from exponential to predictable and linear, while keeping the original group structure intact if you need it for something like capturing.

Defense in depth: length limits and timeouts

Fixing the regex itself is the most important step, but it shouldn't be the only line of defense. Two cheap additions make the difference between "fixed" and "actually hardened":

Cap the input length before you ever touch the regex engine.

MAX_TOKEN_LENGTH = 128

def validate_token_safe(user_input: str) -> bool:
    if len(user_input) > MAX_TOKEN_LENGTH:
        return False

    return bool(MODERN_SAFE_REGEX.match(user_input))

Even a vulnerable regex becomes far less dangerous when it's only ever fed strings under, say, 128 characters. Exponential growth is exponential, but it still takes a meaningful string length before the slowdown becomes severe. A hard cap upstream buys you a real safety margin even if a vulnerable pattern slips through review somewhere else.

For systems where the stakes are higher, use a regex engine with an explicit timeout. Python's built-in re module doesn't support timeouts natively, but the third-party regex package does:

import regex

SAFE_REGEX = regex.compile(
    r"^[a-zA-Z0-9_]*$",
    timeout=0.05
)

With a timeout in place, even a pathological input that somehow gets past your other defenses can only burn CPU for a bounded amount of time before the match attempt is aborted. This turns a potential full outage into, at worst, a single failed request.

The takeaway

Every regular expression that processes input coming from outside your system, a user, an API client, an uploaded file, is a potential denial-of-service vector, and most of the time it looks completely harmless until someone goes looking for the right input to break it.

🔴 Going Live: 5 Real Exploits, Straight From Code Crimes

SQL injection. Broken access control. A password reset bypass that takes one single character. And more, walked through live, straight out of my upcoming book, Code Crimes.

📅 July 18, 2026 · 7:00 PM (WAT)
📍 Facebook Live · Free to attend
👉 https://facebook.com/share/1DtgRk8WLH

A few habits make this risk manageable:

Avoid nesting one repetition group inside another unless you've specifically checked whether the nesting is even necessary. Often it isn't, and a flatter pattern does the same job in linear time.

Set a hard length limit on any input before it reaches a regex, regardless of how confident you are in the pattern itself. It costs you one line of code and removes an entire category of worst-case behavior.

If you're on Python 3.11 or later and genuinely need grouping, reach for possessive quantifiers or atomic groups rather than ordinary backtracking groups.

For anything security-sensitive, consider an engine that supports a hard timeout, so a single bad match attempt can never become a single bad outage.

And test for this deliberately. Don't just test your regex against valid input, that will always look fast. Test it against long, almost-valid strings that fail right at the very end. If your matching time grows faster than linearly as you lengthen that input, you've found a ReDoS bug before an attacker did.