The form had a field for an email address,
and a pattern that checked it.
Somebody wrote the pattern years ago.
It had groups inside groups,
a plus inside a plus,
and it passed every test
anyone had thought to give it.
Then a request arrived
with an address about fifty characters long
that almost matched
and failed at the very last character.
One worker thread went to full load.
It stayed there for forty seconds.
The next request like it
took the second thread.
Here is what happened inside.
Most regular expression engines
work by trying a path,
and when it fails,
stepping back
and trying another.
For a plainly written pattern
there are only a few paths to try.
For a pattern where
the same characters can be claimed
by more than one part of it,
a repeated group that repeats inside itself,
the number of ways to split the input
roughly doubles with every extra character.
Twenty characters is a blink.
Thirty is a pause.
Fifty is longer than your timeout,
if you have one.
And the engine tries every split
before it admits the answer is no.
A matching input is fast.
The slow one is the input
that nearly matches,
which is exactly why it never shows up
in tests written with
one good example and one bad one.
The pattern looks innocent
because it is short.
Its cost is not in its length.
It is in its shape.
So treat a regular expression
as code that runs on untrusted input,
because that is what it is.
Cap the length of the input
before the pattern sees it.
An email address
does not need two thousand characters.
Look for the dangerous shape.
A quantifier on a group
that already holds a quantifier.
Two alternatives
that can match the same text.
Rewrite them so each character
has one place to go.
Where you can,
use an engine that guarantees linear time,
one that simply refuses
the features that need backtracking.
Put a time limit on matching
where your language allows it.
Then add one test
that feeds the pattern
a long string that almost fits,
and fails if it takes
more than a few milliseconds.
The input that hurts you
will not look like an attack.
It will look like a typo
from somebody in a hurry.
– Serguey Asael Shinder
Top comments (0)