Co-Founder & CTO of Superhuman. Programmer, Blogger, Speaker, Dancer.
At Superhuman, we make the fastest email experience in the world. We must therefore process massive amounts of text very rapidly. We need to find links, validate emails, parse invitations, and much more.
Most programmers process text with regular expressions. And rightly so: regular expressions are concise yet powerful.
But many programmers have also encountered the dark side of regular expressions. When regular expressions go wrong, they go devastatingly wrong.
Superhuman automatically converts email addresses into mailto: links.
In this case, we defined an email address as any string that matches this regular expression:
. You can read this as: “0 or more of any character except @, then an @ sign, then 0 or more of any character except @”.
But while reading the formal specification of email addresses, we found some that did not match our regular expression. For example, if the username is quoted then it can also contain an @ sign. Consider
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.
It turns out that we had accidentally become vulnerable to regular expression denial of service (ReDoS).
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 /[^@]*@[^@]*/
This state machine has 3 states:
. 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
In state, the machine will match any character except
B, and remain in state
@. At the end of the string, the machine transitions to state
If the machine encountered ansign 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:
Example state machine for
Do you see the problem?
It’s not obvious, but we introduced non-determinism. In state
, if the machine sees
it has a choice: treat it as
and transition to state
, or treat it as
and stay in state
any character except @
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, everycharacter 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!
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.
We turned to academia, and found that identifying ReDoS is still a relatively new area of research. One paper, however, was particularly useful. In “Static Analysis for Regular Expression Exponential Runtime via Substructural Logics”, the authors describe a beautiful theoretical approach to this problem. They also provide a tool to test regular expressions. It works like this:
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.
With regex.rip, you can create regexes with confidence. You can test your regexes so that users don’t have to. And best of all, you can avoid catastrophic downtime that you would otherwise only see in production.
At Superhuman we’re rebuilding the email experience for web & mobile. Think vim / Sublime for email: blazingly fast and visually gorgeous.