Regex Denial of Service
So today at work I found out about the possibility of exploitable regular expressions. The basic premise, from what I understood, is that one could craft a string that, when matched against a vulnerable regex, could drain a lot of processing power and even make an application hang, effectively performing a DoS. More information here.
My goal is to fix the vulnerable regex we currently have. We're using Java so I'm pretty sure that's the PCRE flavor:
(?=http)\d*\w*\S*(?:\.xsd)
My number one question is: is there a way to algorithmically fix this regex without any knowledge about the strings it's going to be tested against?
By fix, I mean replace it with an equivalent invulnerable regex, which matches all strings that the other does, and doesn't match any the other doesn't. From what I read online, that is possible (at least at times), even though extremely technical.
My second question is: if there's no way to automatically fix it, is there a way to at least check for equivalence between regular expressions? That must be possible.
I will intentionally provide no examples, because I'm not after a regex, I'm after some sort of regex modifier that can mitigate such a vulnerability without knowledge about the strings that are going to be tested.
Posted Jun 30, 2022, 8:35 PM UTC · edited
The answer seems to be "no". Here is a PhD thesis from 2020 that summarizes (in a well organized, readable format, IMO) what was known at the time about regex DoS and how to deal with it. It appears to be pretty thorough. Automated transformation of regexes is does not appear to be mentioned.
So if there is any research into automated fixes, then it is like to be very recent; work is only just beginning, if it is happening at all.
I wouldn't say that. There is research on regex equivalence, but it generally deals with regexes in the strict mathematical sense, with alternation ("|") and Kleene star ("*") being the only operators. PCRE adds all kinds of stuff that can be difficult to analyze. I don't think it is known that PCRE equivalence is decidable. Frankly, I doubt it is.
So I'm afraid that the automated solutions you are looking for are not going to happen. :-( There are tools available for automated detection of problematic regexes. You may wish to look into those; however both false positives and false negatives are known to happen.
P.S. I know you said you're not looking for help with any particular regex. However, if the regex example you give is one that is actually used in your code, then you should know that you probably have a bug.
The
(?=...)syntax is non-consuming, so it and the characters after it must match the same text. But\dcannot match thehcharacter, so your\d*will never match anything but the empty string. That suggests a bug.But if the regex is actually correct, then that means we can remove the
\d*.And we can simplify further.
\wmatches any word character, and\Smatches any non-whitespace character. But no word character is whitespace, so\w*\S*matches the same strings as\S*alone.Lastly, the
httpin the string that is matched cannot overlap with the\.xsd, so thehttpmatcher in the regex might as well consume its text.Putting all that together, we get that your regex -- assuming it is actually correct, which I doubt -- matches the same strings as:
FWIW, this revised regex will probably not exhibit superlinear matching behavior.
This pretty much solves the thread.
I didn't actually know what positive lookahead was exactly, but I understand now that it's completely unnecessary here and that it actually barely does what we actually want. I can see that the regex you provided is equivalent to the faulty one, but optimized.
I now see why my assumption about the existence of a algorithm that does this was incorrect.
Thank you very much for the thorough explanation. I forget these regexes engines are more permissive than the ones I learned in class :)