Regular Expression Denial of Service

An adversary choosing the input, not the engineer choosing the workload.

Teach with MAGE
ECE 30861 · Act III
Security Engineering

Engineering problem How much does a matching cost grow when the adversary, not the engineer, chooses the input?

On 2 July 2019 one regular expression in a new firewall rule exhausted CPU across Cloudflare's network and took its core proxy, CDN and WAF down globally for about 27 minutes. Three years earlier a single post containing a long run of spaces took Stack Overflow down for about 34 minutes. No request in either incident was large. The cost was in the matching, and both patterns are in the apparatus below.

Background

A regular expression describes a set of strings. A backtracking matcher — the kind built into JavaScript, Java, Python and PCRE — decides whether one string is in that set by searching. It commits to one way of lining the pattern up against the input, and when that way fails it returns to its last choice point and tries the next. The search is why these engines can offer backreferences and lookaround. It is also where the cost lives.

A choice point appears whenever the pattern does not determine how much input a repetition consumes. Put two unbounded repetitions in sequence — .* then \s+ — with nothing between them that forces a boundary, and a run of n characters can be divided between them in many ways. Nest one repetition inside another, as in (a+)+, and the number of divisions stops growing like a polynomial and starts doubling with every extra character.

A failing match is the expensive case. A match that succeeds may stop at the first division that works. A match that cannot succeed has to rule out every division before it may report failure. So an attack string has three parts: a prefix that reaches the ambiguous region, a pump that repeats and gives the ambiguity something to divide, and a suffix that makes the whole match fail. The number of pumps is the only number an attacker needs to turn up.

How fast the work grows is the complexity class of the pattern, and it follows from how many ambiguous repetitions precede a character the input does not supply. Two gives quadratic cost, three cubic, four quartic; a nested repetition gives exponential. That is the generalisation worth keeping: ReDoS is not "a slow regular expression". It is a pattern whose cost grows superlinearly in the input, and the rate is a property of the pattern together with the engine that runs it. An automaton-based engine — RE2, Go's regexp, the Rust regex crate — matches in time linear in the input and would measure every pattern on this page as linear.

You read a growth rate off a chart by choosing the axes. On a linear axis a quadratic curve and an exponential one both merely look steep. On a logarithmic y axis an exponential series straightens into a line, because each extra character multiplies the work by a constant. On log–log a polynomial series straightens, and its slope is the exponent: a slope near 2 is quadratic, near 3 cubic.

One last distinction, and it is the one that makes this a security exercise rather than a performance one. A performance model assumes a workload the engineer chose. Here the engineer chose the expression and the adversary chose the input — and the two inputs that differ by a factor of a thousand in cost differ in nothing an engineer controls.

Model

Figure 1: how input structure becomes matching cost The model runs left to right in three stages. Stage one is the input, drawn as three parts: a prefix, a pump repeated n times, and a suffix that makes the match fail. Stage two is the matcher's choice: the pattern's unbounded repetitions can divide the pumped run in many ways, and five such divisions of a four-character run are enumerated as pairs of bars — four and none, three and one, two and two, one and three, none and four. Each is marked as a candidate the matcher may be obliged to try, and a note states that the suffix can be consumed by neither repetition, so no division can succeed and every one must be ruled out before failure may be reported. Stage three is the cost, given as a ladder of closed forms against the number of ambiguous repetitions in the pattern: one repetition costs on the order of n, two n squared, three n cubed, four n to the fourth, and a nested repetition two to the n. The measured degree for each shipped pattern is in Table 2 and on the pattern control itself. This is a conceptual representation of possible backtracking paths, not a literal trace of any JavaScript regular-expression engine. 1 · THE INPUT — what the adversary supplies prefix pump × n suffix one number to turn up: n the suffix is what makes the match FAIL 2 · THE MATCHER’S CHOICE — ways to divide the pumped run 4 + 0 3 + 1 2 + 2 1 + 3 0 + 4 first repetition  |  second repetition n = 4 gives 5 divisions; n = 8 gives 9. EVERY division must be ruled out before FAILURE may be reported. A match that SUCCEEDS rules out none. 3 · THE COST — set by how many repetitions are ambiguous 1 rep → n  ·  2 → n²  ·  3 → n³  ·  4 → n⁴  ·  nested → 2ⁿ linear · quadratic · cubic · quartic · exponential MEASURED degrees: Table 2 A conceptual representation of possible backtracking paths, NOT a literal engine trace.
Figure 1. Input structure becomes matching cost in three steps. The adversary sets n; the pattern sets how many ways the pumped run can be divided; the number of ambiguous repetitions sets the degree. The three controls in the apparatus are the pattern, the input shape, and n.

Table 1 — Model parameters

ParameterWhat it is ValuesDefault
Pattern The expression under test. The options span complexity classes, and two are the expressions from real outages. 6 patterns · linear to exponential Two unbounded repetitions
Input shape Which string the pattern runs against — an attack shape, or a benign control on the same pattern. 2–3 shapes per pattern Whitespace run, then a non-space
Pumps n How many times the pumped core repeats. The x-axis of both charts. tens to tens of thousands, by pattern 16,000

The execution budget is fixed at 250 ms with a 400 ms hard deadline, and the time axis changes what you can read off a chart rather than what was measured. Neither is an engineering parameter; both sit beside Run. The full parameter reference is in Further investigation.

Table 2 — Observed quantities

QuantityWhat it reports Plane
Time per match Wall-clock milliseconds for one execution at the largest measured n. measured
Observed growth The fitted exponent on log–log, or the per-character multiplier on semi-log. This is the complexity class, measured. measured
Where it stopped The pump count at which the budget or the deadline ended the climb — the number a length cap would have to beat. measured
Modelled work Units of work the closed form predicts at the same n. Derived, never measured. model

The measured degrees this page ships were measured, not assumed. Each pattern's control states its own fitted degree and the range it was fitted over; the method is in Further investigation. Where a published complexity label and the measurement disagree, the page reports the measurement.

Assumptions you need in order to predict

  • A failing match is the expensive case. A match that succeeds can stop at the first success; one that cannot must exhaust the alternatives before reporting failure.
  • Every attack shape fails by construction, so two configurations of the same pattern differ in how much work was done, not in what answer was reached.
  • The backtracking diagram is a model, not a trace: it enumerates candidates a matcher could be obliged to consider.
  • The page measures your browser, not a server. Timings come from a real execution in a Web Worker on this machine — and a real execution on a shared CPU varies from run to run. There is no seed to fix.

Illustrative measurement; the demonstration uses the browser's native JavaScript regular-expression engine, whose behaviour may differ from the engine used in the Cloudflare incident. It does not reproduce Cloudflare's production behaviour: V8, SpiderMonkey and JavaScriptCore do not agree with each other. What it reproduces is the same class of algorithmic vulnerability.

Experiment

Method — predict, run, explain

  1. 1 · Predict Read the pattern and count its ambiguous repetitions. Write down the degree you expect and what you expect the cost to do when n doubles. Commit to it before you run anything — the prediction is the part the measurement grades.
  2. 2 · Run Load the baseline, change the one parameter the experiment names, and run both configurations. Switch the time axis to log–log and read the slope.
  3. 3 · Explain Account for the difference from the structure of the pattern and the input, not from the numbers. Then answer the experiment's engineering question.

Run each configuration twice. The page reports the spread between runs, and the point of seeing it is to learn which of your readings survives it: the time does not, the growth does.

Experiment 1 — the adversary's variable

Baseline
Pattern Two unbounded repetitions, input Ordinary prose, n = 16,000, linear axis. That is baseline 1.
Change
The input shape only: Ordinary prose → Whitespace run, then a non-space.
Hold constant
The pattern, n, the execution budget, the time axis.
Predict
The expression is identical and so is the deployment. Does the cost change at all? If it does, by what factor at n = 16,000, and what degree will the growth fit?
Measure
Time per match, observed growth, and where the run stopped — for both shapes.
Explain
Nothing an engineer controls differed between the two runs. Who changed the cost, and what does that make this — a performance finding or a security one?

Experiment 2 — the complexity class is the pattern's

Baseline
Pattern Two unbounded repetitions, input Whitespace run, n = 16,000. That is baseline 2, the quadratic case.
Change
The pattern only, holding the input adversarial throughout: quadratic → Stack Overflow 2016 → Cloudflare 2019 → Cloudflare, whole group → Nested quantifier. Baselines 2, 5, 6 load three of them.
Hold constant
That the input is an attack shape, the budget, the axis mode, the predict-first discipline. Note that n cannot be held: each class reaches the budget at a different n, which is itself a result.
Predict
Count the ambiguous repetitions in each pattern and predict each degree before running. Then predict the pump count at which each one first exceeds 250 ms.
Measure
The observed growth for each pattern, against the degree printed on its control; and where each run stopped.
Explain
State the rule connecting the count of ambiguous repetitions to the degree. Then say what that rule costs you at the exponential pattern, where the ladder runs in tens of characters rather than tens of thousands.

Experiment 3 — what the engineer can change

Baseline
Baseline 2 — the quadratic pattern on the whitespace attack shape at n = 16,000.
Change
The pattern to Forced division (baseline 4), which decides exactly the same question on byte-identical input.
Hold constant
The input shape and every byte of the input, n, the budget, the axis.
Predict
Does the replacement cost less? Does it still reach the same verdict? And does it change the degree, or only the constant?
Measure
Time per match and observed growth for both patterns, plus the match result for each — the two must agree, or the replacement is a different question cheaply answered.
Explain
Name the construct that removed the cost. Then say what the engineer had to establish before shipping it, and compare that obligation against the one a length cap imposes.

Baselines 1 and 2 run the same pattern on different inputs, so the only thing that changes is what the adversary supplies. Baselines 2 and 4 run different patterns on byte-identical input, so the only thing that changes is what the engineer wrote. Holding one variable fixed at a time is what makes each comparison an experiment rather than an anecdote.

Interactive apparatus — controls

—

—

—

Time axis Download HTML

Run selected walks the pump ladder from its shortest input upward, stopping at the first value that exceeds the budget. Where it stops differs between browsers and machines, and that is part of the lesson. One trial at the largest n skips the climb and runs the top of the ladder directly. On the linear patterns that still finishes in well under a millisecond — which is the comparison. On a pathological one it blows past the deadline, and you can watch the page destroy the worker and carry on.

idle

Results

Measured — this run, this machine

—

Time per match

run the experiment to measure it

Measured — this run, this machine

—

Observed growth

at least three measured points are needed before any fit is worth reporting

Measured — this run, this machine

—

Where it stopped

run the experiment to find it

Modelled — derived from the closed form, never measured

—

Modelled work

—

Measured in this browser's own RegExp engine — no model involved
No experiment has been run yet.
Configuration n Input length Match Executions Time per execution Outcome

Explain the differences from the structure of the patterns, not from the numbers. The numbers are what happened on this machine, in this browser, on this run. Why they differ is a property of the patterns and the inputs.

The input under test

—

Generated input

—

Input length
—
Match result
—

Interpretation

The threat model

The measurements above are a performance observation. What makes this a security finding is that the expensive input is chosen by someone else. Name the elements:

Model elementReDoS example

A threat is a possible course of harmful action; a vulnerability is the weakness that may let it succeed; an attack is an attempt to exploit that weakness. Here the vulnerability is superlinear matching, the threat is resource exhaustion, and the attack is one HTTP request carrying a long run of spaces.

Choose a mitigation

The security objective is bound computation per request. Select what you would do, then read how the selection is judged against that objective.

Questions to answer before you leave

  1. You measured a degree for each pattern. State the rule that predicts it from the pattern's text, and name one pattern in your own code that the rule would flag.
  2. A length cap is a control with a number in it. Give the number that bounds the quadratic pattern to under a millisecond, and the number that bounds the exponential one. Which of the two is a cap a product could ship?
  3. The page destroys the worker at a deadline. Say what that protects and what it does not, and then say which of the two the server-side analogue protects.
  4. Your two runs of the same configuration gave different times. Which of your three measured quantities should you quote to a colleague, and which should you not?

The engineering question to leave with

What input can an adversary control, and what resource can it exhaust?

Asked of every component that accepts input from outside the trust boundary, this question finds algorithmic complexity vulnerabilities well beyond regular expressions: parsers, decompressors, hash tables, sorting, image decoders, and anything whose cost depends on the shape of its input rather than only on its size.

Further investigation

Everything below is reference or extension. None of it is needed to run the three experiments.

Why the work grows — the backtracking model, enumerated
This is a conceptual model of backtracking, not a trace of your engine. It enumerates candidates a backtracking matcher could be obliged to consider. The actual engine may optimise some away, order them differently, or never attempt them at all — and V8, SpiderMonkey, and JavaScriptCore do not agree with each other about which. So treat the diagram as a prediction to be compared against the measurements above, never as a picture of what happened. Learning to hold a model and an observation apart, and to notice when they disagree, is the point of the exercise. It is the same distinction the Performance Knee simulator draws between an analytical prediction and a simulated run.

—

Modelled candidates, across the whole ladder

Derived from the closed form — no measurement involved

A logarithmic vertical axis, always: the counts span too many orders of magnitude for a linear one to show anything. The linear patterns sit almost on the floor. Compare the shape of these curves against the measured chart above — agreement supports the model, and disagreement is a finding about the engine's optimisations rather than an error to hide.

How the shipped complexity classes were measured — and one label that did not survive

Every degree the pattern control prints is empirical. The method, so a later reader can refute it rather than trust it: build the pattern's own attack shape at each pump count on its ladder; discard a compile and a 20 ms tier-up pass; time each length until it has accumulated at least 8 ms of samples; fit log(time) against log(length) over the points above 50 microseconds and read the slope. The figures and ranges are in MEASURED_CLASSES in the engine, and a self-test asserts that the class each pattern advertises is the class that was measured.

Measured in V8 (Node 24 / Chromium) on Apple silicon, 5 November 2026. A different engine will answer differently, and an automaton-based engine would answer “linear” for every row.
PatternBasis MeasuredR² Fitted over

Two cautions the table carries. A degree is an asymptotic property approached from below, so a fit over a short range reads low — the cubic pattern measures 2.98 and the quartic 3.92. And a complexity class belongs to the pattern together with the engine: these are backtracking figures, and the matching strategy is as much a part of the result as the pattern is.

One label did not survive the measurement. The Cloudflare pattern is widely described as costing more than it does. Measured here, the fragment the postmortem names — .*(?:.*=.*) — is cubic (degree 2.98), and the whole trailing group with its leading punctuation repetition restored is quartic (3.92). Neither is quintic. A quintic pattern in this family certainly exists — it takes five ambiguous repetitions, as in ^.*.*.*.*.*!$, which measured 4.35 over the range it survives — but that is not the Cloudflare expression. The page prints what it measured.

And one input shape did not survive it either. The Stack Overflow pattern measured linear on the first input tried — a whitespace run at the very start of the string. That is not an engine optimisation: the pattern's first branch, ^[\s‌]+, matches a leading run immediately, so the match succeeds and the expensive second branch is never reached. The outage needed the run in the middle of a post. Both shapes ship, because the pair is the lesson: the same pattern and the same characters, and the cost depends on where they sit.

Execution budget and isolation — why a worker is not enough
Budget per experiment
—
Hard deadline, then the worker is destroyed
—
Workers created this session
0
Experiments terminated
0
Interface frames rendered
0

The match runs in a Web Worker, on its own thread, so the interface stays responsive while the engine is occupied. Watch the frame counter during an expensive run: it keeps climbing.

A worker does not make an expensive regular expression interruptible. There is no way to ask a matching engine to stop. So the page keeps a wall-clock timer the matching thread cannot block, and when a run overruns the deadline the page destroys the worker and creates a fresh one for the next experiment. Destroying it is the only available remedy, and the counters record how often it was needed.

Note what this does and does not buy. Moving the computation into a worker protects the interface; it does nothing to make the regular expression efficient. The same holds for the server-side analogue in the mitigation list: isolating the match bounds the damage, not the cost.

The threat model, drawn — from a crafted input to an unavailable service
Figure 2: the attack path — from a crafted input to an unavailable service A path runs through six stages. An attacker, outside the system boundary, sends a crafted input. It crosses into the system at a public API, which accepts input the attacker controls. The input reaches a regular-expression matcher, which spends excessive computation on it. That exhausts the CPU of the process, and the service becomes unavailable to everyone. The last three stages are drawn in the failure colour and outlined heavily, and each is also labelled in words. A dashed boundary encloses the public API, the matcher, the CPU and the service, and is labelled the system under attack; the attacker is outside it, and the only thing crossing the boundary is the input. A note reads that the attacker supplies no privilege and no volume — only the shape of one string. System under attack Attacker no privilege crafted input Public API accepts attacker-controlled input Regex matcher excessive computation CPU exhausted one core, then the process Service unavailable to every other user The attacker supplies neither privilege nor volume — only the SHAPE of one string.
Figure 2. The threat model. Availability is the asset, the attacker's capability is one crafted string over a public interface, and the vulnerability is algorithmic — it lives in how the matcher searches, not in a missing check.
The engineering case, in detail

The required reading is Cloudflare's own postmortem of the 2 July 2019 outage, “Details of the Cloudflare outage on July 2, 2019”, and Stack Overflow's “Outage postmortem — July 20, 2016”. They supply the real engineering cases; the apparatus supplies a real measurement of the same class of algorithmic vulnerability, on this machine.

Two accuracy constraints this page refuses to smooth away

  • The Cloudflare outage was not an attack. The pathological rule was written and deployed by Cloudflare itself; no adversary was involved. The underlying algorithmic weakness is nevertheless exploitable as a denial-of-service vulnerability, which is why it belongs in a security lecture rather than only a performance one.
  • The page does not reproduce either incident's production behaviour. It runs the patterns from both, in a different engine, on a different machine.

The expression, before the outcome

Work through the construct before reading what happened. The Cloudflare postmortem identifies this fragment inside the much larger rule:

.*(?:.*=.*)

Three unbounded repetitions and one mandatory =. When the overall match fails, the engine must try the ways of dividing the text among them before it can conclude failure. Predict which inputs are expensive, and what degree, before you run anything.

Using this in class — the intended sequence, and the exercises
  1. Read the Cloudflare postmortem. A real outage, at a company whose core competence is operating this kind of infrastructure. Establish that the question matters before introducing any synthetic expression.
  2. Examine the regular expression. Find .*(?:.*=.*) in the rule. Three unbounded repetitions, nothing forcing a unique division between them.
  3. Predict. Which inputs are expensive, and what degree? Commit to an answer before measuring. The prediction is the part that is graded by the measurement.
  4. Run the demonstration. Baselines 1 and 2 first, because they isolate the adversary's variable. Then 3, for what a nested quantifier costs. Then 4, which is the fix, on byte-identical input to 2. Baselines 5 and 6 are the two real incidents.
  5. Identify the threat. Fill in the threat model: who supplies the input, through which entry point, and what resource is exhausted.
  6. Propose controls. Choose mitigations and defend the choice against the objective — including why a rate limit is not sufficient on its own.

Exercises

  1. Baselines 1 and 2 run the same pattern. Baseline 1 is fast. Explain the difference using the structure of /^.*\s+$/ and the structure of the two inputs — not the measured numbers.
  2. Set the time axis to log–log and read the slope of baseline 2. What value would you expect from n(n+1)/2, and does your run agree? If it does not, name a reason that is about the engine rather than about the expression.
  3. Baseline 3 runs out of budget somewhere in the twenties. Each extra character doubles the modelled work. If a service capped its input at 100 characters, would that cap bound the cost for baseline 3? For baseline 2?
  4. Baseline 4 decides exactly the same question as baseline 2 on exactly the same bytes. Read both expressions and say which construct removed the cost.
  5. Load the Stack Overflow pattern and run its two input shapes — the run in the middle, then the run at the very start. The characters are the same. Explain the cost difference from the pattern's two branches.
  6. The page runs the match in a worker and destroys it at a deadline. Name what that protects and what it does not. Then say which of the two the server-side analogue protects.
Model reference — the patterns, the parameters, and what this does not establish

What it measures

Each configuration runs one curated regular expression against generated inputs of increasing pump count, using the browser's own RegExp engine, and reports the measured execution time. Nothing here plots a theoretical complexity curve and calls it a measurement: the numbers come from running the matcher. The model of why the numbers grow is reported separately and labelled as a model.

The full parameter reference

ParameterMeaning ValuesDefault What changing it does
Pattern Which expression is under test 6, spanning linear to exponential Two unbounded repetitions Changes the complexity class — the rate at which cost grows with n
Input shape Which generated string the pattern runs against, attack or benign 2–3 per pattern Whitespace run, then a non-space Decides whether the engine may stop early or must exhaust the alternatives
Pumps n How many times the pumped core repeats by pattern: 12–28 to 500–28,000 16,000 Sets how far up the cost curve the run climbs
Execution budget Deadline after which a trial is abandoned and its worker destroyed 250 ms, fixed250 ms Not adjustable — it is what keeps a pathological run from freezing the page
Time axis How the measured chart is scaled Linear · Log y · Log–logLinear Changes what you can read off the chart, not what was measured

The curated expressions

Fixed, curated patterns. The page executes no user-supplied expression.
ExpressionUsed byWhy this one

Correctness of the curated patterns

A demonstration that mis-states what its expressions mean teaches the wrong thing, so the match behaviour is pinned rather than asserted in prose. Each expression is checked against a table of small inputs; every input shape declares the answer it expects and a self-test checks that declaration against the real regex; and the safe alternative is checked for exact language equivalence with the pathological expression by exhaustive enumeration of short strings — the claim “same decision, far less work” is only worth making if it is true.

Reproducibility, and what this does not establish

There is no seed, because nothing here is random: the inputs are built from one integer and the patterns are fixed. What varies is the machine. A timing is one sample of a shared CPU under a browser, so the same configuration run twice gives two different numbers, and the page reports the spread between runs rather than presenting the latest as the answer. Read the growth, which survives the spread; do not read a two-run range as a confidence interval. The demonstration does not establish what any pattern would cost in another engine, in a server runtime, or under load — only that the class of vulnerability is real and measurable here.

Licence: teaching materials © James C. Davis, CC BY 4.0. The page issues no network request of any kind; the Download HTML control hands you this same file.

Self-tests

The engine carries its own suite so the instrument can be checked in the room it is being used in. The repository's Node suite under course/interactive/redos/tests/ extracts this page's engine script element and evaluates it, so the tested code and the shipped code are the same text.