Microsoft Releases New Regex Fuzzer

Microsoft has released a new fuzzing tool designed specifically to find mistakes in regular expressions in application code that could be vulnerable to attack. The SDL Regex Fuzzer identifies problematic lines that might cause an application to be susceptible to attacks that consume huge amounts of resources and cause denial-of-service conditions.

The new fuzzer is meant to be used specifically to find vulnerable regular expressions in application code that could lead to a special kind of attack known as a ReDoS. Microsoft officials say that as more and more applications are moved to cloud providers, attackers will begin to focus their attention on those applications in new and profitable ways.

“I’ve predicted before that as cloud computing gains wider adoption, we’ll start to see a significant increase in denial of service (DoS) attacks against those services. When you’re paying for the processor time, bandwidth and storage that your applications use, attacks that explicitly target and consume those resources can get very expensive very quickly, not to mention the costs of downtime for legitimate users. Attackers will shift from pursuing elusive privilege elevation vulnerabilities to simply blackmailing SaaS providers: pay me $10,000 or I’ll make your app consume $20,000 worth of server resources,” Microsoft’s Bryan Sullivan wrote in a blog post explaining the SDL Regex Fuzzer.

As Sullivan explains in an article on the problem from earlier this year, a small change to an input string can cause major problems for a regular expression engine.

“Here is where things get ‘interesting’ (as in horribly dangerous).
Instead of just checking that the next character after 5 is not the end
of the string, the engine treats the next character, 6, as a new capture
group and starts rechecking from there. Once that route fails, it backs
up to 1234 and then tries 56 as a separate capture group, then 5 and 6
each as separate capture groups. The end result is that the engine
actually ends up evaluating 32 different paths,” he wrote.

“If we now add just
one more numeric character to the evaluation string, the engine will
have to evaluate 64 paths—twice as many—to determine that it’s not a
match. This is an exponential increase in the amount of work being
performed by the regex engine. An attacker could provide a relatively
short input string—30 characters or so—and force the engine to process
hundreds of millions of paths, tying it up for hours or days.”

The new fuzzer is free to download.