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

RESOLVED FIXED in mozilla29

Status

()

Core
JavaScript Engine
RESOLVED FIXED
4 years ago
4 years ago

People

(Reporter: Ahmad Moghimi, Assigned: till)

Tracking

(4 keywords)

Trunk
mozilla29
crash, csectype-dos, sec-low, testcase
Points:
---
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

(crash signature)

Attachments

(2 attachments, 1 obsolete attachment)

(Reporter)

Description

4 years ago
Created attachment 750358 [details]
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.

Updated

4 years ago
Assignee: nobody → general
Component: Untriaged → JavaScript Engine
Keywords: crash, testcase
Product: Firefox → Core
Version: 21 Branch → Trunk

Comment 1

4 years ago
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
Status: UNCONFIRMED → NEW
Crash Signature: [@ WTF::CrashOnOverflow::overflowed() ]
Ever confirmed: true

Updated

4 years ago
Crash Signature: [@ WTF::CrashOnOverflow::overflowed() ] → [@ WTF::CrashOnOverflow::overflowed()]
OS: Windows 8 → All
Hardware: x86_64 → All
(Reporter)

Comment 2

4 years ago
I tested on latest release version firefox 21.0.1
Summary: There is an integer overflow condition in handling of regular expressions. → There is an integer overflow condition in handling of regular expressions. (WTF::CrashOnOverflow::overflowed)
This specific bug has been blogged about on http://blog.malerisch.net/2013/12/crashing-firefox-with-regular-expression.html
(Assignee)

Comment 4

4 years ago
This trivially reproduces in the shell, too:

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

Looking into it.
(Assignee)

Comment 5

4 years ago
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.
Adding some security tags for tracking
Keywords: csectype-dos, sec-low
(Assignee)

Comment 7

4 years ago
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.

Jandem, do you think this is ok, or do we have to fix the code generation in Yarr?
Attachment #8349398 - Flags: review?(jdemooij)
(Assignee)

Updated

4 years ago
Assignee: general → till
Status: NEW → ASSIGNED

Comment 8

4 years ago
(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?
(Assignee)

Comment 9

4 years ago
(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
(Assignee)

Comment 10

4 years ago
Created attachment 8349450 [details] [diff] [review]
clamp regexp quantifiers to INT_MAX

What it says on the tin
Attachment #8349450 - Flags: review?(jdemooij)
(Assignee)

Updated

4 years ago
Attachment #8349398 - Attachment is obsolete: true
Attachment #8349398 - Flags: review?(jdemooij)
Comment on attachment 8349450 [details] [diff] [review]
clamp regexp quantifiers to INT_MAX

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

Looks good.
Attachment #8349450 - Flags: review?(jdemooij) → review+
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.
(Assignee)

Comment 13

4 years ago
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

4 years ago
(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 .
(Assignee)

Comment 15

4 years ago
(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

4 years ago
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.
(Assignee)

Comment 17

4 years ago
(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.
(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.
(Assignee)

Comment 19

4 years ago
Bustage followup:
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/550257a8f82f
https://hg.mozilla.org/mozilla-central/rev/ff67c72677a6
https://hg.mozilla.org/mozilla-central/rev/550257a8f82f
Status: ASSIGNED → RESOLVED
Last Resolved: 4 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla29
You need to log in before you can comment on or make changes to this bug.