937697 - Dangerous crash on Heap, possibly near [@ js::jit::CharCodeAt]

Status: VERIFIED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Christian Holler (:decoder)]

The following testcase crashes on mozilla-central revision 581d180a37f3 (run with --fuzzing-safe):


while (true) {
  foo("0");
}
function foo(s) {
  s.charAt(0);
  Number(s.charAt(-2147483648));
}

Comment 1

[Christian Holler (:decoder)]

Crash trace:

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff7dfc0ac in ?? ()
#0  0x00007ffff7dfc0ac in ?? ()
#1  0xfff9000000000000 in ?? ()
#2  0x00007ffff7e150a7 in ?? ()
#3  0x0000000000000000 in ?? ()
rbx     0xf6a00630      140737331070512
rdx     0x80000000      2147483648
=> 0x7ffff7dfc0ac:      movzwl (%rbx,%rdx,2),%ebx
   0x7ffff7dfc0b0:      cmp    $0x100,%ebx


Assuming at least sec-high, possibly a bounds issue.

Comment 2

[Christian Holler (:decoder)]

JSBugMon: Bisection requested, failed due to error (try manually).

Comment 3

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

(after fixing some harness failures)

autoBisect shows this is probably related to the following changeset:

The first bad revision is:
changeset:   http://hg.mozilla.org/mozilla-central/rev/4473d84c6ab6
user:        Boris Zbarsky
date:        Thu Sep 12 11:08:21 2013 -0500
summary:     Bug 899296 - Restore bytecode-level constant folding in lazily compiled functions. r=jorendorff.

Boris, is bug 899296 a likely regressor?

Comment 4

[Boris Zbarsky [:bzbarsky]]

It's possible, at least, yes....  That said, I don't know enough about this stuff to be able to debug this usefully on a short timeframe.  Jason, do you have time to deal with this one?

Comment 5

[Jason Orendorff [:jorendorff]]

The changeset reveals a bug in Ion.

TryEliminateBoundsCheck ends up combining these two bounds checks:

(gdb) p dominating->minimum()
$49 = 0
(gdb) p dominating->maximum()
$50 = 0
(gdb) p sumA
$51 = {
  term = 0x0, 
  constant = 0
}
(gdb) p dominated->minimum()
$52 = 0
(gdb) p dominated->maximum()
$53 = 0
(gdb) p sumB
$54 = {
  term = 0x0, 
  constant = -2147483648
}

So far, this makes sense. We have two charAt calls and two bounds checks.

This code in TryEliminateBoundsCheck, at least, is wrong:

    int32_t newMinimum, newMaximum;
    if (!SafeSub(Min(minimumA, minimumB), sumA.constant, &newMinimum) ||
        !SafeSub(Max(maximumA, maximumB), sumA.constant, &newMaximum))
    {
        return false;
    }

The new min and max are computed to permit the union of both ranges rather than the intersection. But the code before this, that computes minimumA and friends, is buggy too.

I suspect this bug could be easily used to read arbitrary memory on 32-bit platforms. -->sec-critical.

All this code was contributed by sunfish.

Comment 6

[Nicolas B. Pierron [:nbp]]

(In reply to Jason Orendorff [:jorendorff] from comment #5)
> The changeset reveals a bug in Ion.
> 
> TryEliminateBoundsCheck ends up combining these two bounds checks:
> 
> (gdb) p dominating->minimum()
> $49 = 0
> (gdb) p dominating->maximum()
> $50 = 0
> (gdb) p sumA
> $51 = {
>   term = 0x0, 
>   constant = 0
> }
> (gdb) p dominated->minimum()
> $52 = 0
> (gdb) p dominated->maximum()
> $53 = 0
> (gdb) p sumB
> $54 = {
>   term = 0x0, 
>   constant = -2147483648
> }
> 
> So far, this makes sense. We have two charAt calls and two bounds checks.
> 
> This code in TryEliminateBoundsCheck, at least, is wrong:
> 
>     int32_t newMinimum, newMaximum;
>     if (!SafeSub(Min(minimumA, minimumB), sumA.constant, &newMinimum) ||
>         !SafeSub(Max(maximumA, maximumB), sumA.constant, &newMaximum))
>     {
>         return false;
>     }
> 
> The new min and max are computed to permit the union of both ranges rather
> than the intersection. But the code before this, that computes minimumA and
> friends, is buggy too.

Ok, I think the problem is caused by the fact that we have 2 constants, and we think the index is the same because both terms are equal.  One easy way to fix this issue would be to check that the sumA.term is not NULL.

Comment 7

[Jason Orendorff [:jorendorff]]

I don't understand why computing the union of the two ranges, rather than the intersection, is OK.

Comment 8

[Nicolas B. Pierron [:nbp]]

(In reply to Jason Orendorff [:jorendorff] from comment #7)
> I don't understand why computing the union of the two ranges, rather than
> the intersection, is OK.

In this case it is not ok, because one of the assumption is not verified (same index).

Otherwise it is ok, because we are looking for the union of all bound checks and fail on the first out-of bound.

Let's take an example to illustrate why we want an union and not an intersection:

    x[i] = x[i + 1] - x[i - 1];

  will produce 3 bound checks:
    bail if i + 0  < 0 || i + 0  > x.length
    bail if i + 1  < 0 || i + 1  > x.length
    bail if i + -1 < 0 || i + -1 > x.length

  Note that "i + -1 >= 0" implies "i + 0 >= 0" and "i + 1 >= 0".
  Which means that if we bail with "i + -1 < 0" first, then we can ensure that we will not bail because of neither "i + 0 < 0" nor "i + 1 < 0"
  And the same thing for the other condition.

  So we can summarize the 3 previous bound checks by:

    bail if i + -1 < 0 || i + 1 > x.length

which is the min of the minimums and the max of the maximums.

Note: we should probably at this example on top of the merging logic to make this clear.

In the current test case we have no "i", and the linear sum is only composed of a constant index.  This merging logic attempt to merge:

  (A) bail if 0 + 0 < 0 || 0 + 0 > x.length
  (B) bail if -21… + 0 < 0 || -21… + 0 > x.length

into to:

  (A) bail if 0 + -21… < 0 || 0 + 0 > x.length

which by the way sounds correct.
So I guess the problem might be in the way we encode the bound check.

Comment 9

[Nicolas B. Pierron [:nbp]]

(In reply to Nicolas B. Pierron [:nbp] from comment #8)
> Note: we should probably at this example on top of the merging logic to make
> this clear.

s/at/add/

Comment 10

[Dan Gohman [:sunfish]]

(In reply to Jason Orendorff [:jorendorff] from comment #5)
> This code in TryEliminateBoundsCheck, at least, is wrong:
> 
>     int32_t newMinimum, newMaximum;
>     if (!SafeSub(Min(minimumA, minimumB), sumA.constant, &newMinimum) ||
>         !SafeSub(Max(maximumA, maximumB), sumA.constant, &newMaximum))
>     {
>         return false;
>     }
> 
> The new min and max are computed to permit the union of both ranges rather
> than the intersection. But the code before this, that computes minimumA and
> friends, is buggy too.

This code, including the code that computes minimumA and friends, was introduced in 4e74ada3a64f for bug 719541.

Comment 11

[Jason Orendorff [:jorendorff]]

(In reply to Dan Gohman [:sunfish] from comment #10)
> This code, including the code that computes minimumA and friends, was
> introduced in 4e74ada3a64f for bug 719541.

You're right, of course. Sorry, Dan.

Thanks for the explanation, nbp. I was reading the semantics of MBoundsCheck incorrectly.

But now I'm not sure there's anything wrong in this function after all.  We start with two bounds checks

            index        min       index        max
    bail if 0           + 0 < 0 || 0           + 0 >= length
    bail if -2147483648 + 0 < 0 || -2147483648 + 0 >= length

These are merged into a single bounds check

           idx  min                index        max
    bail if 0 + -2147483648 < 0 || 0           + 0 >= length

This bounds check can't succeed, but that's the correct outcome.

Now I tend to suspect CodeGenerator::visitBoundsCheckRange(LBoundsCheckRange *lir).
Here's the code we're emitting, comments added:

[Codegen] instruction BoundsCheckRange
[Codegen] xorl       %edx, %edx
// If the minimum and maximum differ then do an underflow check first.
[Codegen] addl       $0x80000000, %edx
[Codegen] Encoding 2 of resume point 0x103b03800's operands starting from 0
[Codegen] jo         ((205))
// Bail if index + min < 0 (signed comparison)  <--- THE CODE HERE LOOKS WRONG
[Codegen] subl       $0x80000000, %edx
[Codegen] testl      %edx, %edx
[Codegen] jl         ((219))
// Bail if index + max >= length (signed comparison).
// max is 0 so there's no addl instruction + overflow check here.
[Codegen] cmpl       %edx, %eax
[Codegen] jbe        ((227))

My x86-64 is terrifically bad, so I should stop here.

Comment 12

[Jan de Mooij [:jandem]]

Attachment: Patch

BoundsCheckRange bug. If the SafeSub overflows, we will restore |temp| before doing the < 0 check.

I think this goes back all the way to bug 719541, so all Firefox versions with Ion are affected. Not sure why we're only seeing this now, but I think it's an edge case: SafeSub(max, min) has to overflow and the checks that follow have to succeed.

Comment 13

[Jan de Mooij [:jandem]]

(In reply to Jason Orendorff [:jorendorff] from comment #11)
> // Bail if index + min < 0 (signed comparison)  <--- THE CODE HERE LOOKS
> WRONG
> [Codegen] subl       $0x80000000, %edx
> [Codegen] testl      %edx, %edx
> [Codegen] jl         ((219))

FWIW, you were right, with my patch we emit the subl after the testl/jl instead of before it.

Comment 14

[Jan de Mooij [:jandem]]

Comment on attachment 8339812 [details] [diff] [review]
Patch

[Security approval request comment]
> How easily could an exploit be constructed based on the patch?
Not trivial but it's possible with some work.

> Do comments in the patch, the check-in comment, or tests included in the patch paint a bulls-eye on the security problem?
No.

> Which older supported branches are affected by this flaw?
Firefox 18+.

> If not all supported branches, which bug introduced the flaw?
Bug 719541.

> Do you have backports for the affected branches? If not, how different, hard to create, and risky will they be?
Should apply to older branches.

> How likely is this patch to cause regressions; how much testing does it need?
Unlikely to cause regressions.

Comment 15

[Al Billings [:abillings - ex-MoCo]]

Just saw this because of holiday. Since we ship in a week, this cannot really go in right now. I'm going to suggest landing it two weeks after we ship, on 12/23 (if you'll be around). Will you be able to land it on affected branches then?

Comment 16

[Al Billings [:abillings - ex-MoCo]]

Comment on attachment 8339812 [details] [diff] [review]
Patch

sec-approval+ for December 23 or later checkin (for next cycle). When it goes in, you should nominate it for affected branches as well and we should get it in there.

Comment 17

[Jan de Mooij [:jandem]]

(In reply to Al Billings [:abillings] from comment #15)
> I'm going to suggest landing it two weeks after we
> ship, on 12/23 (if you'll be around). Will you be able to land it on
> affected branches then?

Sure, I should have time to push this then. Setting needinfo so that I don't forget about this.

Comment 18

[Jan de Mooij [:jandem]]

(In reply to Al Billings [:abillings] from comment #16)
> sec-approval+ for December 23 or later checkin (for next cycle). When it
> goes in, you should nominate it for affected branches as well and we should
> get it in there.

https://hg.mozilla.org/integration/mozilla-inbound/rev/c3f75843aed0

Comment 19

[Jan de Mooij [:jandem]]

Comment on attachment 8339812 [details] [diff] [review]
Patch

[Approval Request Comment]
Bug caused by (feature/regressing bug #): Bug 719541.
User impact if declined: Security bugs.
Testing completed (on m-c, etc.): On m-i.
Risk to taking this patch (and alternatives if risky): Very low.
String or IDL/UUID changes made by this patch: None.

[Approval Request Comment]
User impact if declined: Security bugs.
Fix Landed on Version: Just landed on m-i, will likely be backported to 27.
Risk to taking this patch (and alternatives if risky): Very low.
String or UUID changes made by this patch: None.

Comment 20

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/c3f75843aed0

Comment 21

[Christian Holler (:decoder)]

JSBugMon: This bug has been automatically verified fixed.

Comment 22

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-aurora/rev/fea79cd5d6ee
https://hg.mozilla.org/releases/mozilla-beta/rev/ec83301af0dc

Comment 23

[Jason Smith [:jsmith]]

koi+ for sec-critical bug

Comment 24

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-b2g26_v1_2/rev/f10ae92f5fe3
https://hg.mozilla.org/releases/mozilla-esr24/rev/c3146389f8ec

Comment 25

[chris hofmann]

is this one sec-critical or sec-high?  its marked as both.