A Regex Is Untrusted Code That Does Not Look Like Code

Every product eventually ships a text box where the user types a pattern. A log-alerting rule. A redaction filter for support tickets. A URL-routing rule. A "match my invoice numbers" field in an import wizard. Nobody reviews these in a pull request, because they are one line long, they live in a form, and they look like configuration. They are not configuration. A regular expression handed to a backtracking engine is a program, and one particular shape of that program is a CPU bomb with a one-line source file.

What makes it worse than an ordinary slow endpoint is what happens around it. In a single-threaded event loop, a match that runs for forty seconds is not a slow request — it is the whole process, gone, not answering anything. In CPython the match holds the GIL, so every other thread in that process stops too, including your metrics exporter. Meanwhile the kernel is still accepting connections on the listening socket, so a TCP-level health check connects, succeeds, and reports green, and for a while your dashboard will cheerfully insist the instance is fine while it enumerates the partitions of a string of a's.

Where the exponential actually comes from

A backtracking engine does not build an automaton. It walks the pattern against the input making choices, and when a choice leads to a dead end it rewinds to the most recent decision point and takes the next option. A greedy quantifier like a-plus first grabs as much as it can, then gives characters back one at a time as the rest of the pattern demands them. That is the whole algorithm, and for essentially every pattern a human writes deliberately it is fast and fine.

Now take the pattern ^(a+)+$ and feed it twenty-two a's followed by an X. The outer plus repeats the group; the inner plus decides how many a's each repetition consumes. So a candidate match is a way of cutting the run of a's into one or more non-empty pieces: one piece of twenty-two, or twenty-one and one, or one and twenty-one, or seven and three and twelve. Between each adjacent pair of a's the engine independently chooses to cut or not, so there are two-to-the-twenty-first such cuttings — about two million.

Greedy ordering means the engine tries the single piece of twenty-two first. It reaches the X, needs the end-of-string anchor, and fails. And now the anchor does the damage: it is the thing that says "no" rather than "never mind, try the next start position", so the engine is obliged to back up and try the next cutting, and the next, until it has exhausted all two million. Only then may it honestly report no match. Add one more a and you double the number of cuttings. Twenty-two a's is milliseconds. Thirty is long enough to notice. Forty-five is long enough that you will have redeployed before it finishes.

Two details in that paragraph are the whole phenomenon. The first is that failure, not success, is the expensive case: a match that succeeds stops at the first candidate that works, which is why these patterns behave beautifully against every example their author tested. The second is that deleting the leading caret makes it worse rather than better, because the engine then repeats the entire doomed search from each successive start offset.

The other shapes, and the one that reaches production

^(a|a)*$ is the same disease with different symptoms. Every a can be consumed by either branch of the alternation, so there are two-to-the-n paths through the input and all of them have to be eliminated. You rarely see that literal pattern. You see alternations whose branches overlap on real input — a protocol matcher where one branch is a prefix of another, a number matcher where the integer and decimal cases both accept the same leading digits.

The CSV and header-parsing shape, (\s*,\s*)*, is nastier than it looks, because \s* can match the empty string. A run of whitespace sitting between two commas can be divided between the trailing \s* of one repetition and the leading \s* of the next in many ways, and an engine with nothing better to do will try them.

But the pattern that actually causes production incidents is none of these, because nobody types (a+)+ into a form. It is a validator, written in good faith, copied off a search result, and it has roughly this shape: a local part, an at sign, one-or-more dot-terminated domain labels, and then — the problem — a bracketed letter class with a {2,4} repetition, itself wrapped in a plus, anchored to the end of the string for the TLD. Two nested quantifiers, both individually benign-looking. A run of letters at the end can be split into chunks of two, three or four in exponentially many ways, and the end anchor forces the engine to try all of them before it can conclude that the address is invalid.

So the payload is not a regex. The payload is an email address. Something like someone@example. followed by forty-odd letters and an exclamation mark. It does not look malicious — it looks like a typo. It arrives in your signup form, your invite endpoint, your CSV importer, and it is unauthenticated, because validating an email address is the thing you do before you have a user. Run the demo below and watch where the curve turns: the input that costs a full second is around sixty characters long, which is an unremarkable length for an email address and comfortably under any cap you would plausibly put on that field.

Two different bugs share the name

ReDoS gets used for two situations that need different defences, and most teams only have the first one in their threat model.

The first is a malicious pattern: the user supplies the regex. Your rule editor, your redaction config, your routing DSL. Here the untrusted thing is code and you know it, so the defences are about what you let the pattern be and where you let it run.

The second is a malicious input: the regex is yours. Hardcoded, reviewed, in a file somebody owns — and the attacker supplies the string it runs against. No pattern API, no text box, no feature flag. Just a validator in a request handler, doing exactly what it was written to do.

The second is far more common and produces more incidents, precisely because the first one makes somebody nervous. A pattern field in a UI gets a design discussion and a code review. A validation regex gets merged in a four-line diff titled "fix email validation", and the reviewer's job in that diff is to check whether the regex accepts the right addresses, not whether it terminates.

• The user supplies the pattern. You need preemption and a resource ceiling, because you cannot statically decide whether an arbitrary pattern is safe. A pattern lint catches the famous shapes and misses the rest, so treat a clean lint as "no obvious footgun", never as a proof.
• The user supplies the input. You need to audit your own patterns, which is genuinely tractable: there is a finite number of them and they are all in your repository. Grep for a quantifier applied to a group that itself contains a quantifier, and for alternations whose branches can match the same text.
• Both at once — tenants write patterns and your pipeline feeds them other people's data. This is the case that actually deserves a VM, and it is the smallest of the four.
• Neither, you think. Check your dependencies. A markdown renderer, a user-agent parser, a URL normaliser, a date-format guesser and a log formatter all ship regexes you have never read, running against input you do not control. ReDoS advisories against popular libraries are a steady drip, not an anomaly.

# redos_demo.py -- run it. It takes a handful of seconds. Do not raise the
# ranges much: the whole point is that the curve is exponential and your
# patience is not.
import re, time


def timed(rx, s):
    t0 = time.perf_counter()
    rx.match(s)                      # the result is irrelevant; the time is the point
    return time.perf_counter() - t0


# ---------------------------------------------------------------- the textbook
# A quantified group inside a quantifier, anchored at both ends. The trailing
# anchor is what makes it expensive: it forbids "give up and slide along" and
# demands "prove that NO cutting of this input works".
EXPONENTIAL = re.compile(r"^(a+)+$")

print("^(a+)+$  against n a's followed by one X")
for n in range(16, 26):
    # Without the X the first greedy attempt succeeds and this returns in
    # microseconds. The X is the entire attack.
    print(f"  n={n:>2}  {timed(EXPONENTIAL, 'a' * n + 'X'):9.4f}s")


# ------------------------------------------------- the one that actually ships
# Nobody types (a+)+ into a form. They paste this, off a search result, into a
# signup handler. Two nested quantifiers; the killer is ([a-zA-Z]{2,4})+ for
# the TLD, because a run of letters can be cut into chunks of 2, 3 or 4 in
# exponentially many ways and the $ forces the engine to try all of them.
EMAIL = re.compile(r"^[\w.+-]+@([\w-]+\.)+([a-zA-Z]{2,4})+$")

print("naive email validator  against an INVALID address")
for n in range(30, 49, 3):
    # This is not a payload. It is a typo: a long run of letters where a TLD
    # should be, then one character that cannot be part of one.
    bad = "someone@example." + "a" * n + "!"
    print(f"  len={len(bad):>3}  {timed(EMAIL, bad):9.4f}s")

# Two things to notice in that second table. The cost roughly doubles every two
# characters. And the input that costs you a full second is around sixty
# characters long -- an entirely ordinary length for an email address, and
# comfortably under any length cap you would plausibly put on an email field.

Backtracking engines, and the ones that refuse to

The structural fix is to stop using an engine that can backtrack at all.

Backtracking engines — PCRE and PCRE2, Python's re, JavaScript's RegExp, java.util.regex, Ruby's Regexp, .NET in its default mode — explore the search tree by trial and rewind. That is precisely what lets them support backreferences and lookaround, because both require remembering and re-examining decisions already made. It is also exactly what creates the exponential. The feature and the vulnerability are the same mechanism viewed from two directions.

Finite-automata engines — RE2, Rust's regex crate, Go's regexp package — compile the pattern into an automaton and simulate it, tracking the set of states the input could have reached so far. Each input character is processed once, at a cost bounded by the size of the compiled pattern. That is linear in the input, and no pattern and no input changes it. The guarantee is not a heuristic or a configured limit; it is a property of the algorithm, which is a categorically different kind of promise.

The price is the features that need backtracking. No backreferences, no lookahead, no lookbehind. If your pattern DSL exposes lookahead to customers then you have chosen a backtracking engine, whether or not you framed it as a choice, and you now own the consequences of that choice. If it does not, switching engines is the highest-leverage change available to you — and if you write Go or Rust, you have already made it by accident and should know that you did.

Limits and memoisation: useful, and not guarantees

Several engines have grown mitigations short of changing algorithm, and they are worth using and worth not trusting. PCRE2 exposes match and backtracking depth limits, so you can bound the work and get an error instead of a hang. .NET added a non-backtracking matching mode and a per-match timeout. Recent Ruby grew a global regex timeout and a memoisation optimisation that makes a large class of previously-exponential patterns linear. Python grew atomic groups and possessive quantifiers, which let you write a pattern that structurally cannot backtrack into a group.

Two caveats, and they are the load-bearing part. A limit is a cap, not a guarantee: it converts an unbounded hang into a bounded burn, and the bound is whatever you set multiplied by however many times per request you run the match. And memoisation helps the cases it covers without changing the worst case for every pattern. Every sentence in the previous paragraph is version-dependent and some of it changed in the last two releases of the runtime you are using. Check your runtime's current documentation rather than trusting a blog post about it — including this one.

import re

# Three ways to stop the email case being a liability, in the order you should
# reach for them.

# 1. FIX THE PATTERN. The blowup came from {2,4} nested inside a +. A TLD is
#    ONE run of letters, not a sequence of chunks -- so say that.
SAFE = re.compile(r"^[\w.+-]+@([\w-]+\.)+[a-zA-Z]{2,24}$")
#    Every quantifier now applies to a single element and nothing nests.
#    Most real ReDoS findings are this: the pattern was simply wrong, and the
#    exponential was a symptom of the wrongness rather than a separate bug.

# 2. FORBID BACKTRACKING where you genuinely cannot restructure. An atomic
#    group says "once you have matched this, you may never give any of it
#    back", which severs the branch the engine would otherwise explore. Python
#    grew (?>...) and the possessive *+ / ++ forms in 3.11; check your version.
try:
    ATOMIC = re.compile(r"^[\w.+-]+@([\w-]+\.)+(?>([a-zA-Z]{2,4})+)$")
except re.error:
    ATOMIC = SAFE                     # no atomic groups on this interpreter
#    That IS linear -- it stays in the microseconds at two hundred characters.
#    But read the caveat, because it is the whole catch: committing to the
#    greedy choice changes what the pattern ACCEPTS. The original matches a
#    five-letter TLD by cutting it 2+3; the atomic version takes 4, fails,
#    refuses to re-cut, and rejects the address. Atomic grouping is a surgical
#    tool for a pattern you cannot rewrite, not a blanket safety wrapper.

# 3. CHANGE ENGINE. google-re2 exposes RE2 to Python with a familiar surface
#    and a linear-time guarantee: no input makes it superlinear, there is no
#    timeout to tune and no limit to set.
try:
    import re2
except ImportError:
    re2 = None

if re2 is not None:
    LINEAR = re2.compile(r"^[\w.+-]+@([\w-]+\.)+[a-zA-Z]{2,24}$")

    # The useful side effect: RE2 REFUSES backreferences and lookaround,
    # because those are the features that require backtracking. The list of
    # patterns it rejects is free static analysis of your most dangerous
    # patterns. Treat the rejection list as a finding, not as an obstacle.
    for p in [r"(\w+)\s+\1", r"foo(?=bar)", r"(?<!a)b"]:
        try:
            re2.compile(p)
            print(f"RE2 accepts {p!r}")
        except Exception as exc:
            print(f"RE2 refuses {p!r}: {exc}")
else:
    LINEAR = SAFE

Why the mitigations you already have do not fire

• A request timeout is a promise about when you will stop waiting, not about when the work stops. Your framework's thirty-second deadline fires on a timer in the event loop. The event loop is not running. It is inside the regex engine, in C, and it did not leave a forwarding address.
• A SIGALRM watchdog in Python generally does not interrupt a match in progress. CPython runs signal handlers between bytecode instructions, and a long match is one bytecode's worth of C. The handler fires when the match returns, which is precisely the moment you stopped needing it. Verify against your interpreter version, but do not design around it firing.
• The GIL makes it worse rather than better: Python's re does not release it while matching, so one bad match in one thread stops every other thread in the process — your readiness handler, your metrics scrape, your graceful-shutdown logic.
• A setTimeout race in Node is not a timeout. There is no second thread for it to run on. Nothing you scheduled will run until the match returns.
• A thread pool or a worker pool converts one stuck process into N stuck processes on a schedule set by your retry policy. If the input came off a queue and the worker is killed without acknowledging the message, the broker redelivers it and it eats the next worker too. That is how one malformed record takes out a fleet rather than a pod.
• An input length cap is the mitigation most often recommended and most often misunderstood — see immediately below.

The length cap, correctly understood

Capping input length is good advice applied with the wrong intuition. The intuition is that cost grows with length, so a cap bounds cost. True — but the bound you get depends entirely on which blowup you have, and the two cases behave oppositely.

For a polynomial pattern, where cost is proportional to the square or cube of the input length — the classic being an unanchored whitespace-plus-dollar run over a long stretch of spaces — a cap works beautifully. At two hundred characters, n-squared is forty thousand steps. That is nothing, and you are done.

For an exponential pattern, a two-hundred-character cap buys you nothing whatsoever, because the pattern detonates long before two hundred. The email validator in the demo above crosses a second somewhere in the low sixties of characters. To cap your way out of an exponential you would need a limit in the low tens of characters, which for most fields is not a cap, it is a redesign of the field.

And the per-field cap is not the quantity that matters. The quantity that matters is cost per request, and a request can carry many fields, a JSON array, a CSV with ten thousand rows, or a batch endpoint someone added last quarter. Ten thousand inputs each costing two milliseconds — each one comfortably under every cap you set — is twenty seconds of one core, requestable repeatedly, for free, by anyone.

If you must run arbitrary patterns, you need preemption

Now the case where none of the above is available to you. The pattern is supplied by a user, your product has to accept it, and the patterns must behave exactly like PCRE because that is what your docs promised and what your customers' existing rules assume. You cannot switch to RE2, because RE2 will reject a chunk of their patterns outright and "your saved rules stopped compiling" is a worse incident than the one you are preventing. You cannot audit the patterns, because there are thousands and they change daily. You cannot time out the match, because nothing in the process is awake to do it.

What is left is preemption from the outside, and preemption needs a thing with a boundary that something else can destroy without its cooperation. There are two useful versions of that, and the cheaper one is the right first answer for most people.

A separate process with an rlimit — start here

Fork a child, set RLIMIT_CPU and RLIMIT_AS, compile and run the pattern there, and read the answer back over a pipe. When the CPU limit is reached the kernel sends SIGXCPU and then SIGKILL, and it does this without the process's cooperation, which is the entire point. The kernel is not inside the match waiting politely for a safe moment.

This costs about a day, needs no new infrastructure, and eliminates the availability failure completely. For most products it is the correct answer and you should stop reading here. It is cheap, boring and well understood, and the parts of the problem it does not solve may genuinely not be in your threat model.

What it does not give you, stated plainly: a memory ceiling that bites before the host notices — RLIMIT_AS helps per child, but a pool of such children can still collectively exhaust the machine, and the kernel's OOM killer does not read your org chart when it picks a victim. Isolation of anything other than CPU and address space, so a hostile pattern that is really a hostile program still runs as your service user on your filesystem. And no clean way to attribute the burn to the tenant who caused it, which matters the moment someone asks why the compute bill moved.

A microVM, when pattern evaluation is a product surface

A VM earns its place when three things are true at once. Pattern evaluation is something you sell rather than an internal detail, so its reliability is a product property with a support queue attached. You need a hard memory ceiling as well as a CPU one, because a pattern can allocate as well as spin. And you want the CPU actually burned attributed to the tenant who caused it instead of smeared across your fleet average.

On PandaStack that is one sandbox per evaluation. The guest has its own kernel, so a pattern — or the interpreter you are running it in, or a memory-safety bug in that interpreter — cannot reach a neighbour's data by any path that does not go through the hypervisor's deliberately minimal device model. Its memory ceiling is a wall rather than an accounting convention. Killing it is a kill call that does not negotiate with the regex engine. And because every create is a snapshot restore — p50 179 ms, p99 203 ms — the per-evaluation cost is low enough that "a fresh VM per rule validation" is something you can do in a form handler rather than something you draw in an architecture diagram and never build.

Now the honest scoping, because this is a post on a vendor's blog and you should discount accordingly. For the large majority of applications reading this, the right answer is: switch to a linear-time engine where you can, fix the nested quantifier where you cannot, cap your input lengths, and go home. That is a sprint, and it removes the entire class of failure. The sandbox is for the narrower case where the engine is not yours to change, because the users' patterns have to keep meaning what they meant yesterday. If you do not have that constraint, do not buy a platform to solve a problem a dependency bump solves.

import json
from pandastack import Sandbox

# Evaluate a TENANT-SUPPLIED pattern against a tenant-supplied corpus inside a
# throwaway microVM: hard wall-clock kill, hard memory ceiling, and the CPU
# actually burned attributed to the tenant who asked for it.
#
# Sizing note, because it trips people up: cpu= and memory_mb= on create are
# IGNORED whenever the template has a baked snapshot. Firecracker cannot change
# vCPU or RAM at snapshot restore, so the agent overrides the request to the
# baked values -- code-interpreter is baked at 2 GiB and 8 burst vCPU. The
# memory wall is the template's, not the request's.

PROBE = r"""
import json, re, resource, sys, time

# Belt, inside the guest: at 5 CPU-seconds the kernel sends SIGXCPU and at 6 it
# sends SIGKILL, whether or not the regex engine ever intended to return. The
# VM is braces.
resource.setrlimit(resource.RLIMIT_CPU, (5, 6))
resource.setrlimit(resource.RLIMIT_AS, (1 << 30, 1 << 30))     # 1 GiB

BUDGET = 0.05            # seconds per input before we call the rule too slow

pattern = open("/work/pattern.txt").read().rstrip("\n")
try:
    rx = re.compile(pattern)
except re.error as exc:
    print(json.dumps({"verdict": "invalid", "detail": str(exc)}))
    sys.exit(0)

worst, worst_index = 0.0, None
for i, line in enumerate(open("/work/corpus.txt", errors="replace")):
    t0 = time.perf_counter()
    rx.search(line)
    dt = time.perf_counter() - t0
    if dt > worst:
        worst, worst_index = dt, i

print(json.dumps({
    "verdict": "slow" if worst > BUDGET else "ok",
    "worst_seconds": round(worst, 4),
    "worst_input_index": worst_index,
}))
"""


def check_rule(tenant: str, pattern: str, corpus: str) -> dict:
    sbx = Sandbox.create(
        template="code-interpreter",
        metadata={"tenant": tenant, "purpose": "regex-rule-validation"},
        ttl_seconds=120,                 # IDLE timeout, not a walltime budget
    )
    try:
        sbx.filesystem.write("/work/pattern.txt", pattern)
        sbx.filesystem.write("/work/corpus.txt", corpus)
        sbx.filesystem.write("/work/probe.py", PROBE)

        # Bound the command in the SHELL. `timeout -s KILL` escalates to
        # SIGKILL, and SIGKILL is not something a backtracking engine gets to
        # decline. (Do not reach for exec(timeout_seconds=N) with a large N --
        # one-shot exec has no server-side deadline today. The shell's own
        # timeout does, and exec_stream honours its timeout_seconds.)
        result = sbx.exec("timeout -s KILL 20 python3 /work/probe.py")

        # Whichever ceiling trips first wins, and the exit code tells you which.
        # 152 = 128 + SIGXCPU: the in-guest RLIMIT_CPU fired, so the pattern
        # burned 5 CPU-seconds on one input. 137 = 128 + SIGKILL: the shell's
        # wall-clock timeout fired. For a pathological pattern you will usually
        # see 152, because CPU time and wall time are the same thing here.
        if result.exit_code in (137, 152):
            return {"verdict": "killed", "detail": f"signalled, exit {result.exit_code}"}
        if result.exit_code != 0:
            # RLIMIT_AS tripped, or the probe died some other way.
            return {"verdict": "resource_exhausted", "detail": result.stderr[-400:]}
        return json.loads(result.stdout)
    finally:
        # The VM dies here regardless of what the regex engine was doing, which
        # is the only sentence in this file that is actually a guarantee.
        sbx.kill()


print(check_rule(
    tenant="acme",
    pattern=r"^([a-zA-Z]{2,4})+$",
    corpus="\n".join("a" * n + "!" for n in range(20, 60)),
))
# {'verdict': 'killed', 'detail': 'signalled, exit 152'}
#
# The tenant gets a form validation error naming the input that was slow. You
# get a few CPU-seconds on your bill -- CPU is metered on active CPU-seconds
# actually burned at $0.054 per vCPU-hour, memory on committed GiB-hours at
# $0.0162 -- tagged `tenant=acme` by the metadata, instead of an incident.

Four answers, compared

The canonical story, and the health check that lied

The best-known instance of this is Cloudflare's July 2019 outage, and I am going to describe it only in general terms: a regular expression deployed in a managed WAF ruleset contained a pattern with catastrophic backtracking, it was pushed globally, CPU went to one hundred per cent across the fleet, and proxying went down worldwide. They published a detailed post-mortem within days and it is genuinely excellent. Go and read theirs rather than trusting my paraphrase — how the rule reached production and what they changed afterwards is the useful half, and a summary is exactly the kind of thing that gets subtly wrong in retelling.

What generalises is the second-order failure, and it is the part people skip past. A process spending one hundred per cent of its CPU inside a regex engine is not dead. It holds its listening socket, so a TCP health check connects and reports green. It is present in service discovery. It has not crashed, so nothing restarts it and nothing pages. An HTTP readiness probe will eventually time out and mark the instance unhealthy — which, in the middle of a fleet-wide event, means your orchestrator starts removing capacity from a fleet that is already struggling, and the replacement comes up, receives the same traffic and the same rules, and joins the pile.

The operational lesson is cheap to act on. Make at least one health signal something that cannot be satisfied by a process that has stopped executing your code: a counter that must advance between scrapes, a request that must complete with a fresh timestamp in the body, a queue depth that must move. Anything other than "the socket accepted".

A regex is a program. A backtracking engine is an interpreter for it. The only thing separating this from the other untrusted code in your system is that it fits on one line, so nobody asked for a review.

What to do about it this week

1. Grep your own repository for the shape, not for the word. A quantifier applied to a group that itself contains a quantifier, and alternations whose branches can match the same text. Start with validators, because that is where copied patterns live, and with anything anchored to the end of the string.
2. Then check your dependencies. A markdown renderer, a user-agent parser, a URL normaliser and a date-format guesser are all regex machines running against input you do not control. At minimum, find out whether anything in your tree has an open ReDoS advisory.
3. Find out concretely what your runtime offers — a timeout, a match limit, a non-backtracking mode, atomic groups — and then write a test asserting the pathological case terminates inside a budget, so CI tells you when an upgrade removes it.
4. Switch to a linear-time engine anywhere you can, and treat the patterns it refuses to compile as a list of your most dangerous patterns rather than as an obstacle. That refusal is free static analysis you did not have to write.
5. Cap input length, knowing whether you are capping a polynomial case or pretending to cap an exponential one. Then cap cost per request as well as per field, because a batch endpoint multiplies every per-field number you just reasoned about.
6. If users supply patterns, run them somewhere you can kill from outside. A forked child with RLIMIT_CPU is the right first move and it is a day of work. Reach for a VM when evaluation is a product surface, when you need a memory ceiling too, and when you want the burn billed to the tenant who caused it.
7. Validate a pattern at save time against a sample of that tenant's own data, inside the killable thing, and turn a slow result into a form error. "Line 4,812 of your sample took 8.2 seconds and the budget is 50 ms" is a feature. The identical fact discovered at ingest is an incident.
8. Fix at least one health check so that it cannot be satisfied by a process which has stopped executing your code.

The reason this bug keeps happening after two decades of being thoroughly documented is not that it is hard. It is that it does not look like what it is. Nobody feels like they are shipping a code-execution feature when they add a pattern field to a settings page, and nobody feels like they are shipping a denial-of-service vector when they paste an email validator off the internet into a signup handler. The fix is mostly not a platform. It is noticing that the one-line thing in the text box is code, and then treating it the way you treat the rest of the code you did not write.