872971 - There is an integer overflow condition in handling of regular expressions. (WTF::CrashOnOverflow::overflowed)

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Ahmad Moghimi]

Attachment: Proof of concept.

User Agent: Mozilla/5.0 (Windows NT 6.2; WOW64) AppleWebKit/537.31 (KHTML, like Gecko) Chrome/26.0.1410.64 Safari/537.31

Steps to reproduce:

I have done some fuzzing against regular expression parser. 


Actual results:

A reliable crash has occured.


Expected results:

The bug exist because of improper decision after checking some integer value. the regular expression parser check size of an integer value and in case of overflow it throw an INT3 excepton instead of handling the issue and crashes firefox. 
although it may not seem exploitable it is a DOS conditon and should be fixed.

Comment 1

[:Gijs (he/him)]

I can confirm this on a slightly older nightly (23), see eg. bp-aec0fde1-1005-4bc8-bdf5-1ea1e2130516 . Checking on latest nightly (24), see eg. bp-238dc461-bd05-462f-ab1e-9103b2130516

Comment 2

[Ahmad Moghimi]

I tested on latest release version firefox 21.0.1

Comment 3

[Frederik Braun [:freddy]]

This specific bug has been blogged about on http://blog.malerisch.net/2013/12/crashing-firefox-with-regular-expression.html

Comment 4

[Till Schneidereit [:till]]

This trivially reproduces in the shell, too:

/x{2147483648}x/.test('1');

Looking into it.

Comment 5

[Till Schneidereit [:till]]

As this is a bug in Yarr, this should also affect JSC/Safari. Interestingly, it only affects JSC. Safary happily displays the page, whereas JSC crashes as expected. No idea what's going on there.

Comment 6

[Frederik Braun [:freddy]]

Adding some security tags for tracking

Comment 7

[Till Schneidereit [:till]]

Attachment: disallow regexp quantifiers > 0x7fffffff.

By far the easiest fix is to just disallow quantifiers that would cause an overflow. They're so large that real use cases for them are inconceivable anyway.

Jandem, do you think this is ok, or do we have to fix the code generation in Yarr?

Comment 8

[David Bruant]

(In reply to Till Schneidereit [:till] from comment #7)
> Created attachment 8349398 [details] [diff] [review]
> disallow regexp quantifiers > 0x7fffffff.
> 
> By far the easiest fix is to just disallow quantifiers that would cause an
> overflow. They're so large that real use cases for them are inconceivable
> anyway.
Is it a deviation from the ES spec? If so, would it make sense to change the spec to take this practical aspect into account?

Comment 9

[Till Schneidereit [:till]]

(In reply to David Bruant from comment #8)
> Is it a deviation from the ES spec? If so, would it make sense to change the
> spec to take this practical aspect into account?

That's a good question. I think technically, it is a deviation. In section [21.2.2.5], step 2, the quantifier is specified as producing the values min and max, each being integers, or positive infinity.

However, practically speaking, this can't ever be of meaningful consequence: we throw an error because of allocation size overflow much earlier in string creation.

Another strategy would hence be to just clamp the values to [0,0x7fffffff]. We wouldn't ever throw a SyntaxError, and runtime behavior couldn't deviate from what it'd be for unclamped values, because we can't produce strings large enough for that to matter.

[21.2.2.5]: http://people.mozilla.org/~jorendorff/es6-draft.html#sec-term

Comment 10

[Till Schneidereit [:till]]

Attachment: clamp regexp quantifiers to INT_MAX

What it says on the tin

Comment 11

[Jan de Mooij [:jandem]]

Comment on attachment 8349450 [details] [diff] [review]
clamp regexp quantifiers to INT_MAX

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

Looks good.

Comment 12

[Tom S [:evilpie]]

I personally think throwing errors for stuff we can't handle is a lot better than clamping and waiting for stuff to fail during runtime. This case seems uncommon enough, seeing how this is apparently almost never hit unless you create a pattern like this on purpose. Of course we could do both in case that brings some safety advantages.

Comment 13

[Till Schneidereit [:till]]

remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/ff67c72677a6

(In reply to Tom Schuster [:evilpie] from comment #12)
> I personally think throwing errors for stuff we can't handle is a lot better
> than clamping and waiting for stuff to fail during runtime. This case seems
> uncommon enough, seeing how this is apparently almost never hit unless you
> create a pattern like this on purpose. Of course we could do both in case
> that brings some safety advantages.

The thing we can't handle is something completely different, though. I don't see how this could ever change our runtime behavior. Throwing an error, otoh, would create a visible spec deviation.

Comment 14

[André Bargull [:anba]]

(In reply to Till Schneidereit [:till] from comment #13)
> The thing we can't handle is something completely different, though. I don't
> see how this could ever change our runtime behavior. Throwing an error,
> otoh, would create a visible spec deviation.

The current fix still results in a visible spec violation when min > MAX_INT and max > MAX_INT and min > max. And integer overflows in JSC::Yarr::consumeNumber() already trigger user visible errors. (Beside the fact that the overflow check JSC::Yarr::consumeNumber() isn't actually correct...). See test cases js/src/tests/js1_5/Regress/regress-230216-2.js and js/src/jit-test/tests/basic/bug691299-regexp.js .

Comment 15

[Till Schneidereit [:till]]

(In reply to André Bargull from comment #14)
> (In reply to Till Schneidereit [:till] from comment #13)
> > The thing we can't handle is something completely different, though. I don't
> > see how this could ever change our runtime behavior. Throwing an error,
> > otoh, would create a visible spec deviation.
> 
> The current fix still results in a visible spec violation when min > MAX_INT
> and max > MAX_INT and min > max.

That's a fair point. Maybe we should check for this and make sure that the sign of min - max always stays the same, even when clamping.

> And integer overflows in
> JSC::Yarr::consumeNumber() already trigger user visible errors. (Beside the
> fact that the overflow check JSC::Yarr::consumeNumber() isn't actually
> correct...). See test cases js/src/tests/js1_5/Regress/regress-230216-2.js
> and js/src/jit-test/tests/basic/bug691299-regexp.js .

Can you elaborate? The tests still pass, and I don't know where user visible errors are triggered.

Comment 16

[André Bargull [:anba]]

There is already an error if the requested repeat count exceeds UINT_MAX, so it shouldn't really matter to lower the maximum from UINT_MAX to INT_MAX (`/.{42949672951}/` results in `SyntaxError: invalid quantifier`).

And concerning the invalid overflow check: `/.{107374182300}/` is accepted even though 107374182300 > UINT_MAX.

Comment 17

[Till Schneidereit [:till]]

(In reply to André Bargull from comment #16)
> There is already an error if the requested repeat count exceeds UINT_MAX, so
> it shouldn't really matter to lower the maximum from UINT_MAX to INT_MAX
> (`/.{42949672951}/` results in `SyntaxError: invalid quantifier`).

Ah, ok. Right, I agree that reducing the maximum wouldn't matter too much. But then, not visibly reducing it seems just as well to me.

> 
> And concerning the invalid overflow check: `/.{107374182300}/` is accepted
> even though 107374182300 > UINT_MAX.

It seems like the quantifiers aren't even used if they're not followed by some other token. That's why the other tests you mentioned didn't crash. I have no idea why that is, and, frankly, not too much motivation to look into it.

Comment 18

[Jeff Walden [:Waldo]]

(In reply to Till Schneidereit [:till] from comment #13)
> The thing we can't handle is something completely different, though. I don't
> see how this could ever change our runtime behavior. Throwing an error,
> otoh, would create a visible spec deviation.

We've been down this road before with Function.prototype.call: what happens if you pass an arguments object (array, typically) with .length really big?  Used to be we'd silently clamp the arguments used, with no notification to the developer.  But that actively breaks code (actually caused an intermittent orange, believe it or not!) -- and silently, in a way that can't reasonably be detected.

Regardless what the specs say (and note that some, like CSS, include explicit language permitting implementation-defined limits), we should throw exceptions (or early errors) when we hit implementation limits.  Predictable and understandable trump spec compliance in these extreme edge cases where something breaks no matter what you do.  Happily, because of our string length limits, we don't need to throw here, as the comments in the patch note.

Comment 19

[Till Schneidereit [:till]]

Bustage followup:
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/550257a8f82f

Comment 20

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/ff67c72677a6
https://hg.mozilla.org/mozilla-central/rev/550257a8f82f