Regular expression denial of service (ReDoS) attack test results

Platform test results

Platform	ReDoS?	Details
C# 3.5	Yes	[ Source ] [ Results ]
IronPython 2.6	Yes	[ Source ] [ Results ]
Java for Windows	Yes	[ Source ] [ Results ]
JavaScript (Rhino)	Yes	[ Source ] [ Results ]
JavaScript (WSH 5.7)	Yes	[ Source ] [ Results ]
Perl 5.10.1	No	[ Source ] [ Results ]
PHP 5.3.2	No	[ Source ] [ Results ]
PHP 5.3.2 (with mb_ereg)	Yes	[ Source ] [ Results ]
Python 2.6 for Windows	Yes	[ Source ] [ Results ]

This Web page provides test results to understand which software platforms have problems with regular expression denial-of-service (ReDoS) attacks. A ReDoS attack becomes possible in an application which uses a poorly written regular expression to validate user inputs. An improperly written regular expression has an exponential run time when given a non-matching string. User-supplied character strings as short as 30 characters can cause problems with a regular expression which has not been properly coded.

The ReDoS problem is particularly acute for Web applications which run on Web servers and other network servers which use regular expressions for input validation. In the real world, the ReDoS problem appears to show up most often in regular expressions used to validate email addresses.

The following is a simple example of a regular expression which can cause a denial of service attack:

^(a+)+$

The test string "aaaaaaaaaaaaaaaaaaaaaaa!" (23 a's followed by an exclaimation point) will typically take 1 second to execute with a regular expression matcher that suffers from the ReDoS problem. Increasing the number of "a" characters in a test string to 44 will drive up the execution time to more than 1 million seconds which is approximately 277 hours.

Test results and full source code are available for platforms using the C#, Java, JavaScript, Perl, PHP, and Python programming languages at this Web page. All testing was done under Windows Vista. Test programs are written in a generic fashion to run on other implementations. The test programs can also be easily translated to other programming languages which support regular expressions.

In addition, an online version for testing the JavaScript engine of a Web browser is available here Note: This test page can be a bit slow to load as the ReDoS test is executed.

The following WikiPedia article provides more information about the ReDoS attack problem:

http://en.wikipedia.org/wiki/Regular_expression_Denial_of_Service_-_ReDoS

Author: Richard M. Smith

Please send comments, questions, suggestions, etc. to info@computerbytesman.com