[Owasp-leaders] Method for statically detecting Regex's subject to Regex DOS?

Achim achim at owasp.org
Mon Nov 9 21:39:56 UTC 2015

Hi Dave,

when talking about ReDoS you need to be aware that such a problem
may occour for a specific regex with a special payload (string) on
a particlar platform. This means that not every touple (regex, payload)
causes a DoS on all platforms.

"platform" here means the implementation of a regex engine in a 
programing language or tool.

Said this, it's obvious, somehow, that it's not simple to write
  a) complete list with malicious regex
  b) complete list with malicious payloads
it's the combination executed in a specific engine, sometimes even
the version of the engine counts.

An incomplete example of a) and b) can be found in
https://github.com/EnDe/ReDoS/  (see ReDoS.txt).
The tool itself (benchmark.html) tries to demonstrate the problem in
JavaScript. It partially gives an answer to your question:
	"regexs ... are (or might be) subject to ReDos"

For example the payload ooooooooooooooooooooooooooooooooops crashes
most browsers with Regex  ^(o+)+$  or  (.*o){65} . But they are not
at all a problem in perl.

So your question 
	"validating a regex to determine if its vulnerable or not"
needs to be answered per engine. And hence the validation function
needs to be executed unless a combination is known to be malicious.

Hope this helps

On 09.11.2015 16:01, Dave Wichers wrote:
> OWASP has this article, which is great:
> https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDo
> S
> And wikipedia has a good article too: https://en.wikipedia.org/wiki/ReDoS
> But, it unfortunately they only describe the problem and don¹t describe
> how to fix it.
> There is another good article on the subject linked from wikipedia:
> https://msdn.microsoft.com/en-au/magazine/ff646973.aspx
> But it too just describes the problem (very well), and then describes
> fuzzing as a technique that might be able to detect these problems.
> What I¹m looking for (which I¹m not sure exists), is some way of
> validating a regex to determine if its vulnerable or not, ideally with a
> static check (like use of a Regex). If we could figure out a way (and it
> doesn¹t have to be perfect), developers could use it to validate user
> supplied data before constructing regex¹s out of them (which I¹ve seen in
> real apps, and why I¹m asking). And static analysis tools (like maybe
> FindSecBugs or SonarQube) could also validate statically constructed
> regexs and warn the developers that the regexs they are building into
> their apps are (or might be) subject to ReDos.
> I suspect this problem is Œtoo hard¹ for a simple regex. I see there is a
> tool written here: http://www.cs.bham.ac.uk/~hxt/research/rxxr.shtml that
> people could use to detect ReDox is arbitrary regexs. I wonder if we could
> come up with a simple white list regex that prevents regexdos while
> allowing most of the types of regexs people would want to build.
> Any suggestions out there? (that we can then update our OWASP article
> with)?
> Thanks, Dave

More information about the OWASP-Leaders mailing list