953013 - Regexp groups can overflow some counter

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[homakov]

User Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_9_0) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/31.0.1650.63 Safari/537.36

Steps to reproduce:

info http://homakov.blogspot.com/2013/12/regexp-groups-overflow-in-ff.html



z=Array(999999).join('a');
console.log(/^([\w])+$/.test(z),z.length);
//true 999998

z=Array(999999+1).join('a');
console.log(/^([\w])+$/.test(z),z.length);
//false 999999


Actual results:

returns false


Expected results:

should raise an exception

Comment 1

[Frederik Braun [:freddy]]

Thank you for filing this, Egor!
I haven't come to a conclusion of how this should be rated security-wise, but I will make sure this gets a bit more attention from the other security team members.

My assumption that this is at most sec-moderate or at most sec-low, do you agree?
I am failing to find a good scenario in which this bug is truly harmful.

Comment 2

[homakov]

So far all scenarios are solely theoretical. Say, you are trying to find does some HTML contain <tags> and you for some reason put them in pockets. For 1mln+ pockets it will say - "no HTML here" and it won't be sanitized :)
sec-low is alright

Comment 3

[homakov]

*does some string contain HTML <tags>

Comment 4

[Frederik Braun [:freddy]]

I don't think this bug needs to be hidden as it is based on a long-since public blog post. *unhide*

Comment 5

[Till Schneidereit [:till]]

Attachment: throw exceptions for uncorrectly-interpreted regular expressions instead of treating them as non-matching

What's going on here is that Yarr contains mechanisms for dealing with runtime errors in the interpreter, but doesn't really use them.

In this case, there's a check in Yarr::Interpreter::matchDisjunction that causes a bailout if more than 999999 pattern matches are detected. The bailout bubbles up to Interpreter::interpret, but there, it's quite simply ignored.

To address this, I introduced a sentinel value for the output just like one exists for failed matches. In RegExpShared::execute[MatchOnly], the output is checked for this sentinel value. If it's encountered, an error is reported and RegExpRunStatus_Error returned. The error message is very generic, but I think it's strictly better than the current situation.

Mostly, the error message is generic because this works for aborts because of a failing JS_CHECK_OPERATION_LIMIT(), too. I briefly verified by restricting the regexp tested here to a very short runtime, and I get the expected shell exit. I have a hard time coming up with a separate expression that would run long enough in an opt shell, too, though. (Where "long enough" is more than a second, but ideally much longer: the test would timout very quickly, so test suite runtime isn't an issue.) Suggestions welcome.

Comment 6

[Till Schneidereit [:till]]

Attachment: throw exceptions for uncorrectly-interpreted regular expressions instead of treating them as non-matching.

Once more, with test included

Comment 7

[Jan de Mooij [:jandem]]

Comment on attachment 8357375 [details] [diff] [review]
throw exceptions for uncorrectly-interpreted regular expressions instead of treating them as non-matching.

Review of attachment 8357375 [details] [diff] [review]:
-----------------------------------------------------------------

Looks good.

Comment 8

[Till Schneidereit [:till]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/9ecbd1ca14e2

Comment 9

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/9ecbd1ca14e2

Comment 10

[Hannes Verschore [:h4writer]]

Reported upstream, since yarr also has this behaviour in webkit:
https://bugs.webkit.org/show_bug.cgi?id=130399