|Regexploit - Put A Stop To Regular Expression DoS Attacks|
|Written by Nikos Vaggalis|
|Monday, 29 March 2021|
There's a new tool that can identify resource-hungry regular expressions that can be potentially exploited in launching ReDos attacks.
The findings on the performance side were that:
Due to differences in the underlying algorithms which the regex engines are based on, a match in some languages may require greater than linear time (polynomial or exponential in the worst case) in the length of the regex and the input string. These are called super-linear matches and some regex engines fall prey to this super-linear behavior while the wiser ones avoid it.
Thus regexes that fall into this super-linear category can be exploited by being fed specially crafted strings which would subsequently overload the host, i.e. web server, as in a DoS attack, eventually bringing it down to its knees.
So what can you do about it? Of course, craft your regexes correctly. However the problem is that by their very nature they're already so dense that they can't be adequately tested, plus the testing itself depends on the input data, which means that it could be data in a format that you hadn't predicted, one that causes the damage.
Another option, as revealed in "Can Regular Expressions Be Safely Reused Across Languages?", is to opt for Perl or PHP:
Similarly, PHP and Perl have a lower incidence of polynomial behavior than do the other Spencer engines. The differences between these two families can be attributed to a mix of defenses and optimizations.
So it seems that PHP and Perl, PHP probably because it utilizes the PCRE (Perl Compatible Regular Expressions) library, were the only ones that had explicit defenses against exponential time behavior.
Read that article to form a complete picture.
If you're not using one of those languages, or you don't want to depend on their runtime mechanisms for safeguarding but want to get to the source of the problem as soon as possible, then you can go for Regexploit, a tool that scans your code in order to locate those vulnerable regular expressions.
You enter regexes via stdin or through a file and Regexploit walks them through trying to find ambiguities and ways to make the regular expression not match, so that the regex engine has to backtrack. If the regex looks OK it will say “No ReDoS found”.
If you are able to extract regexes from other languages, they can be piped in and analysed.
Does it mean that it can work with any regex piped into it? That claim of uniformity reminds me of the very issue that "Can Regular Expressions Be Safely Reused Across Languages?" set out to discover. So I'll rephrase: "Can Regexploit Be Safely Reused Across Languages?" Does it support all regex dialects? For that I have to ask the makers. Doyensec.
Better leave that job to dedicated parsers.That aside, the next problematic area found was the mishandling of optional whitespace.
Installation is as simple as:
and can be invoked with passing it a regular expression on the stdin or pipe in a file:
So could Regexploit become part of your arsenal, if not completely replace it, against ReDoS? As the tool only supports NFA regex engines, there's just one extrayou need - use DFA like Go does and be completely safe.
or email your comment to: email@example.com
|Last Updated ( Monday, 29 March 2021 )|