[ruby-core:31673] [Bug #3679] pathological regular expressions and exponential computation time

Bug #3679: pathological regular expressions and exponential computation time
http://redmine.ruby-lang.org/issues/show/3679

Author: Jamie Heilman
Status: Open, Priority: Normal
Category: core
ruby -v: ruby 1.9.2dev (2010-07-11 revision 28618) [x86_64-linux]

$ time ruby -e '"a" * 25 + "b" =~ /(?:a|a)+\z/'

real    0m6.686s
user    0m6.683s
sys     0m0.000s
$ time ruby -e '"a" * 26 + "b" =~ /(?:a|a)+\z/'

real    0m13.366s
user    0m13.319s
sys     0m0.037s
$ time ruby -e '"a" * 27 + "b" =~ /(?:a|a)+\z/'

real    0m26.712s
user    0m26.698s
sys     0m0.000s
$ time ruby -e '"a" * 17 + "b" =~ /(?:a|a|a)+\z/'

real    0m18.016s
user    0m18.005s
sys     0m0.000s
$ time ruby -e '"a" * 18 + "b" =~ /(?:a|a|a)+\z/'

real    0m54.049s
user    0m53.996s
sys     0m0.017s

this will pretty much hold true for any range of characters "a" provided the character(s) "b" are outside of that range, and you can tease this into using insane amounts of processing time by increasing the amount of overlap in the regular expression, iow:
$ time ruby -e '"ab" * 14 + "c" =~ /(?:[ab]|[ab])+\z/'

real    0m53.834s
user    0m53.780s
sys     0m0.020s


I ran into this due to some input validation code that was Regexp.union()'ing together various character classes carelessly and ending up with some overlap, the net effect of which was that certain invalid inputs were causing cpu exhaustion and application outages.  This would appear to affect both ruby 1.9 and 1.8 ... I didn't test further back.


----------------------------------------
http://redmine.ruby-lang.org