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

Mon Nov 9 15:01:47 UTC 2015

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