Project

General

Profile

Actions

Backport #5149

closed

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

Added by gregory.mostizky (Gregory Mostizky) over 12 years ago. Updated almost 8 years ago.

Status:
Rejected
[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.


Files

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

Related issues 1 (0 open1 closed)

Has duplicate Ruby master - Bug #5322: URI.decode_www_form_component very slow with certain inputsClosed09/14/2011Actions

Updated by regularfry (Alex Young) over 12 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".

Updated by matmarex (Bartosz Dz) over 12 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.

Updated by regularfry (Alex Young) over 12 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.

Actions #4

Updated by naruse (Yui NARUSE) over 12 years ago

  • Tracker changed from Bug to Backport
  • Project changed from Ruby master 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.

Actions #5

Updated by naruse (Yui NARUSE) almost 8 years ago

  • Status changed from Assigned to Rejected
Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0