Project

General

Profile

Backport #5149

Specific combination of regexp and string causes 100% CPU and doesn't recover

Added by gregory.mostizky (Gregory Mostizky) about 7 years ago. Updated over 2 years ago.

Status:
Rejected
Priority:
Normal
[ruby-core:38725]

Description

Specific combination of regexp and string can cause ruby process to hang with 100% CPU.

Reproducing (in irb):
/\A(?:%\h\h|[%]+)*\z/ =~ "199542328.1312293792.1.1.utmcsr%3Dgoogle%7Cutmccn%"
(above hangs indefinably with 100% cpu)
/\A(?:%\h\h|[%]+)*\z/ =~ "199542328.1312293792.1.1.utmcsr%3Dgoogle%7Cutmccn"
(same but without % at the end returns succesfully)

The code in question is found in Rack:Utils (v1.3.2, not used in v1.2.1) and can basically "kill" any server process (happened to us in production on a thin machine after we upgraded to newer rack). The above bug means that it is very easy to perform DoS on affected ruby server.

uri.patch (416 Bytes) uri.patch regularfry (Alex Young), 08/03/2011 01:15 AM

Related issues

Has duplicate Ruby trunk - Bug #5322: URI.decode_www_form_component very slow with certain inputsClosed2011-09-14

History

#1 [ruby-core:38726] Updated by regularfry (Alex Young) about 7 years ago

I'd disagree with the location of this bug. I've had a quick look, and while this doesn't look like a Ruby bug, perhaps it ought to be. The regex as given:

/\A(?:%\h\h|[^%]+)*\z/

does not appear in Rack, but does appear in lib/ruby/1.9.1/uri/common.rb (line 778 in -p290). Rack has this:

/\A(?:%[0-9a-fA-F]{2}|[^%])*\z/

This would not appear to suffer from the same exponential behaviour as that in URI, while apparently validating the same strings. Perhaps the appropriate substitution should be made in uri/common.rb? Patch untested, but "looks right".

#2 [ruby-core:38727] Updated by matmarex (Bartosz Dz) about 7 years ago

No, this is a buggy regex - a case of catastrophic backtracking. http://www.regular-expressions.info/catastrophic.html

Removing the "+" after [%] fixes it.

This is because both this "+" is greedy and the "*" at the end are greedy, so Ruby tries to match as many "[%]"s as possible, and then to match the result as many times as possible; obviously it fails (since the next character is the percent sign), then it backtracks to one less character, and tries to match this; then again, and again. Number of repetitions skyrockets and boom, everything hangs while Ruby tries hard to backtrack and backtrack.

#3 [ruby-core:38728] Updated by regularfry (Alex Young) about 7 years ago

Bartosz Dz wrote:

No, this is a buggy regex

Yes. The buggy regex is in Ruby's stdlib. My trivial patch (which I now realise I managed to mess up the file paths on, apologies for that) fixes it in the manner you describe.

#4 Updated by naruse (Yui NARUSE) about 7 years ago

  • Tracker changed from Bug to Backport
  • Project changed from Ruby trunk to Backport192
  • Status changed from Open to Assigned
  • Assignee set to yugui (Yuki Sonoda)

It is already fixed in trunk and 1.9.3, please backport r32622 and r32631 to 1.9.2.

#5 Updated by naruse (Yui NARUSE) over 2 years ago

  • Status changed from Assigned to Rejected

Also available in: Atom PDF