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. 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
Parameter
What it is
Values
Default
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
Quantity
What 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 · 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 · 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 · 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.
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 element
ReDoS 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
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.
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?
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.
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.
Pattern
Basis
Measured
R²
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 serviceFigure 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
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.
Examine the regular expression. Find .*(?:.*=.*) in the rule.
Three unbounded repetitions, nothing forcing a unique division between them.
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.
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.
Identify the threat. Fill in the threat model: who supplies the input,
through which entry point, and what resource is exhausted.
Propose controls. Choose mitigations and defend the choice against the
objective — including why a rate limit is not sufficient on its own.
Exercises
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.
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.
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?
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.
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.
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
Parameter
Meaning
Values
Default
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, fixed
250 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–log
Linear
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.
Expression
Used by
Why 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.
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.