Hacker News Reader

Comment by grepular | Hacker News Reader

ruby -e "'=XX===============================' =~ /X(.+)+X/"

Why does that hang in Ruby? In Perl it's fine...

Because Ruby uses PCRE, but Perl uses its own regex engine which handles cases like that a lot better. That pattern is rejected right away by Perl's engine because it sees that there isn't another X in that string:

    anchored "X" at 0 floating "X" at 2..2147483647 (checking floating) minlen 3 
    Guessing start of match in sv for REx "X(.+)+X" against "=XX==============================="
    Found floating substr "X" at offset 2...
    Contradicts anchored substr "X", trying floating at offset 3...
    Did not find floating substr "X"...
    Match rejected by optimizer

Changing the pattern to /X(.)X/ will cause Perl to do real work. But it'll complete it in 0.003s while Ruby will just hang.

I wrote an article a while back about the differences between PCRE and Perl's engine: http://use.perl.org/~avar/journal/33585

Thanks for the explanation

Well... basically, it sounds like Ruby's regex engine needs some work, hmm?

No, people should know better than to write regexes like /X(.+)+X/, with gratuitous doubly-nested "+" characters. :-) This code performs fine when written as /X(.+)X/, and it matches the same set of strings.

Regexp engines are subtle beasts, and there's a couple different ways to implement them (DFAs vs NFAs, simple engines vs lots of clever special cases, etc.). See O'Reilly's "Mastering Regular Expressions" for an exhaustive discussion.

Interesting. Any other recommendations on how to secure regex's that take in user input in Ruby/Rails?

First of all you should think hard before taking regexes from users. Even if you do it correctly you'll still (presumably) need to search over your entire dataset, instead of doing something more lightweight like rely on SQL indexes. Use it with care.

You should use a regex engine that's explicitly designed to take potentially hostile input. Like the Plan9 engine, or Google's re2 engine which powers Google Code Search.

You can also just use Ruby's dangerous PCRE engine if you do something like forking off another process with strict ulimits which executes the regex for you. Then you can just kill it if it starts running away with your resources. Look into how e.g. evaluation bots that work on the popular IRC channels on FreeNode are implemented. POE::Component::IRC::Plugin::Eval on the CPAN is a good example.

This assumes that PCRE doesn't still contain memory corruption flaws, despite not being heavily tested, and being in effect a programming language interpreter. Tavis Ormandy found a couple serious problems a few years ago.

I'd just scrub the hell out of strings before passing them to a regex engine.

Good advice, thanks you two!

Even if it does it's a pretty remote possibility that it'll be exploitable if you limit the input to say 100 bytes. Pretty hard to get a Perl or Ruby level program of that size to exploit some memory corruption at the C level.

It just seems to me that if Perl's regex engine handles this without a problem, and Ruby's implementation freaks out, something should be improved about the Ruby one.

Reply on news.ycombinator.com