How We Eliminated Regular Expression Denial of Service and How You Can Too
But many programmers have also encountered the dark side of regular expressions. When regular expressions go wrong, they go devastatingly wrong.
The Dark side of Regular Expressions
Superhuman automatically converts email addresses into mailto: links.
. You can read this as: “0 or more of any character except @, then an @ sign, then 0 or more of any character except @”.
Now you might be thinking: “That’s crazy! Who would do that?!” But when you deal with user data, the unexpected happens all the time. Imagine you have 1 million users, and that each user has 50,000 emails. Between them, this is 50 billion emails. Even if it only happens once in every billion emails, that could still easily be 50 times!
Wanting to do the right thing, we naïvely changed our regular expression to
. This is exactly the same as before, but also allows the username to contain 0 or more quoted sections.
It only took a few days before we received an email saying: “Please help! Superhuman is using 100% CPU and not responding…”
We could see that the problem started after we changed this regular expression, and we could see that Superhuman broke on one email in particular. In some cases, the CPU would lock up for days.
Regular Expression Denial of Service
Theoretically, a regular expression is equivalent to a state machine that matches one character at a time. The state machine for our first email matcher looks like this:
Example state machine for /[^@]*@[^@]*/
. The machine starts in state
. While here, the machine will match any character except
and remain in state
. If it encounters an
sign, the machine will transition to state
, the machine will match any character except
, and remain in state
. At the end of the string, the machine transitions to state
If the machine encountered an
sign while in state
, it would error as there are no matching transitions. The error would show that the string did not match the regular expression.
So what changed when we updated our regular expression? The state machine for our second email matcher looks like this:
Do you see the problem?
, if the machine sees
it has a choice: treat it as
and transition to state
, or treat it as
any character except @
and stay in state
In the worst case, the state machine has to try every single possible combination of options before it can determine that there is no match. And the number of options very quickly becomes huge. In our example, every
character doubles the number of possibilities. Our regular expression can therefore take O(2ⁿ) attempts to match, where n is the length of the string.
If you don’t believe me, open your browser console and type:
let regex = /("[^"]*"|[^@])*@([^@]*)/
t = performance.now()
console.log(performance.now() - t) // about 3 seconds.
character doubles the time required. This 40 character string takes about 3 seconds on a high-end MacBook Pro. A similar string of just 64 characters will take more than 2 years — assuming you don’t run out of battery in the meantime!
- If our regular expression is run against a valid email address, it will not backtrack and it will run very quickly.
- If our regular expression is run against the vast majority of common input, it will backtrack a little and it will still run quickly.
- If our regular expression is run against a very specific pattern, it will backtrack catastrophically and may never end.
In other words, ReDoS manifests only in specific conditions, is catastrophic when it does, and — worst of all — cannot be caught by traditional testing as the conditions needed to trigger it are rare.
- Compile the regular expression into a state machine.
- Look for ambiguity within the loops of the state machine execution graph.
- Run a bounded search of the execution graph to determine if these ambiguities can be triggered in a loop. If so, this would indicate a ReDoS vulnerability.
A brilliant side effect of this strategy is that it generates an example string that will trigger ReDoS. This can be extremely useful for debugging, as you can see which parts of the regular expression are triggered.
At Superhuman we’re rebuilding the email experience for web & mobile. Think vim / Sublime for email: blazingly fast and visually gorgeous.