909494 - Crash with SIGTRAP with ParallelArray and --ion-check-range-analysis

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, critical)

Description

[Christian Holler (:decoder)]

The following testcase crashes on mozilla-central revision 4887845b1142 (threadsafe build, run with --fuzzing-safe --ion-check-range-analysis):


assertArraySeqParResultsEq(range(0, 1024), "filter", function(e, i) { return (i % (1.1)) != 0; });
function range(n, m) {
  var result = [];
  for (var i = n; i < m; i++)
    result.push(i);
  return result;
}
function assertArraySeqParResultsEq(arr, op, func) {
  arr[op].apply(arr, [func]);
}

Comment 1

[Dan Gohman [:sunfish]]

This bug is very similar to bug 908867. In this case, it's the rhs being "decimal" that's causing the problem. Both will be fixed in the same patch, as soon as I get approval to submit it.

Comment 2

[Christian Holler (:decoder)]

JSBugMon: Cannot process bug: Unable to automatically reproduce, please track manually.

Comment 4

[Dan Gohman [:sunfish]]

Attachment: bug908867.patch

The "foo" function in the testcase doesn't actually reproduce the bug yet, but it will once some other range analysis enhancements land.

Comment 6

[Nicolas B. Pierron [:nbp]]

Inherit tracking flags from Bug 908867.

Comment 7

[Nicolas B. Pierron [:nbp]]

Comment on attachment 797333 [details] [diff] [review]
bug908867.patch

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

Be aware that this is changing a line introduce in Gecko 25, as part of Bug 897747, as opposed to what the tracking flags inherited from Bug 908867 mention.

As you will have to backport you should land the test case separately once the patch landed on both inbound & aurora.

Comment 8

[Nicolas B. Pierron [:nbp]]

In fact, I think the bug might even come from Bug 841666 which accepted the specialization of MMod compute range with doubles without paying attention to the bounds of the range previously made on Integers.

Comment 9

[Dan Gohman [:sunfish]]

Fix on trunk:
https://hg.mozilla.org/integration/mozilla-inbound/rev/b6412dc95e7f

Testcase on trunk:
https://hg.mozilla.org/integration/mozilla-inbound/rev/c0e80bbe50fb

Comment 10

[Al Billings [:abillings]]

This should not have been landed with a security rating followed by sec-approval since this affects multiple branches. Please see https://wiki.mozilla.org/Security/Bug_Approval_Process for the process for security bugs.

We definitely shouldn't have landed any tests at this time.

Comment 11

[Gary Kwong [:gkw] [:nth10sd]]

Bug 841666 landed on Firefox 22, so this likely affects 23 and 24 too.

Comment 12

[Dan Gohman [:sunfish]]

Attachment: aurora.patch

I apologize for my mistake. I will take more care to follow the process in the future.

Attached is a patch which contains the fix for aurora. I'll backport the fix to firefox23 and firefox24 next and attach the patches to this bug. I'll wait for further instructions before checking anything in.

Comment 13

[Nicolas B. Pierron [:nbp]]

The risk seems to be that we could have a off-by-less-than-one which can be scale to any magnitude with a multiplication and later truncated to get an offset.

Hopefully, (I really feel released by reading the code carefully) there is no way that we would remove a bound check around an array if we have a modulo as an operand of the array.  So this bug cannot be sec-critical.

Marty: Can you confirm that I read the code correctly?

Comment 14

[Dan Gohman [:sunfish]]

The patch that introduced the --ion-check-range-analysis flag also included fixes for several pre-existing range analysis bugs, at least one of which goes back to 6688ede89a36 (bug 699883). Is it important to backport these other fixes as well?

Comment 15

[Dan Gohman [:sunfish]]

Attachment: beta.patch

This is the backport to mozilla-beta. I also fixed the "1-a" expression, to make the code work more like the code on trunk.

Comment 16

[Dan Gohman [:sunfish]]

Attachment: release.patch

Here's the mozilla-release patch. It's the same as the mozilla-beta patch except that in mozilla-release, the "ion" directory has not yet been renamed to "jit", and some of the patch context is different.

Comment 17

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #14)
> The patch that introduced the --ion-check-range-analysis flag also included
> fixes for several pre-existing range analysis bugs, at least one of which
> goes back to 6688ede89a36 (bug 699883). Is it important to backport these
> other fixes as well?

I think we should consider any patch which manipulate operations which can be interpreted in a LinearSum, as they are used for removing bound checks.

So probably any fix on range analysis of MAdd, MSub and MMul.

Comment 18

[Dan Gohman [:sunfish]]

(In reply to Nicolas B. Pierron [:nbp] from comment #17)
> (In reply to Dan Gohman [:sunfish] from comment #14)
> > The patch that introduced the --ion-check-range-analysis flag also included
> > fixes for several pre-existing range analysis bugs, at least one of which
> > goes back to 6688ede89a36 (bug 699883). Is it important to backport these
> > other fixes as well?
> 
> I think we should consider any patch which manipulate operations which can
> be interpreted in a LinearSum, as they are used for removing bound checks.
> 
> So probably any fix on range analysis of MAdd, MSub and MMul.

The ranges of MAdd, MSub, and MMul are computed in terms of the ranges of their operands, which could be any operator, so if the range analysis for those operators matters, doesn't that mean that any operator matters?

Comment 19

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #18)
> (In reply to Nicolas B. Pierron [:nbp] from comment #17)
> > (In reply to Dan Gohman [:sunfish] from comment #14)
> > > The patch that introduced the --ion-check-range-analysis flag also included
> > > fixes for several pre-existing range analysis bugs, at least one of which
> > > goes back to 6688ede89a36 (bug 699883). Is it important to backport these
> > > other fixes as well?
> > 
> > I think we should consider any patch which manipulate operations which can
> > be interpreted in a LinearSum, as they are used for removing bound checks.
> > 
> > So probably any fix on range analysis of MAdd, MSub and MMul.
> 
> The ranges of MAdd, MSub, and MMul are computed in terms of the ranges of
> their operands, which could be any operator, so if the range analysis for
> those operators matters, doesn't that mean that any operator matters?

The only case that I see so far would be to get through the lowering of MBoundsCheckLower [0] which is created by tryHoistBoundsCheck[1], which use jit::ExtractLinearSum [2], which expects to see MAdd, MSub and constants (not even MMul).

[0] http://dxr.mozilla.org/mozilla-central/source/js/src/jit/Lowering.cpp#l2001
    http://dxr.mozilla.org/mozilla-central/source/js/src/jit/MIR.cpp#l2213
[1] http://dxr.mozilla.org/mozilla-central/source/js/src/jit/RangeAnalysis.cpp#l1530
[2] http://dxr.mozilla.org/mozilla-central/source/js/src/jit/IonAnalysis.cpp#l1105

Comment 20

[Dan Gohman [:sunfish]]

(In reply to Nicolas B. Pierron [:nbp] from comment #19)
> The only case that I see so far would be to get through the lowering of
> MBoundsCheckLower [0] which is created by tryHoistBoundsCheck[1], which use
> jit::ExtractLinearSum [2], which expects to see MAdd, MSub and constants
> (not even MMul).

Ah, and it doesn't appear to actually use the range() from the MAdd or MSub; it just uses the symbolicLower() and symbolicUpper(). And the "range()->lower() < minimum_" check in MBoundsCheckLower::fallible() [0] is actually unreachable, because MBoundsCheckLower objects are never assigned a range. Tricky.

However, mozilla-aurora for example has the MinMaxD optimization which disables a NaN check if range analysis says the operands aren't NaN [1]. Looking at that code with this bug in mind, it seems like it could theoretically be subverted to significant ends.

[0] http://dxr.mozilla.org/mozilla-central/source/js/src/jit/MIR.cpp#l2213
[1] http://dxr.mozilla.org/mozilla-central/source/js/src/jit/shared/CodeGenerator-x86-shared.cpp#l385

I'm not familiar with all of the ways range analysis is used, so I don't know that there aren't other problems too. Consequently, I went and created backported patches of the dynamic range checking (--ion-check-range-analysis) to mozilla-aurora, mozilla-beta, and mozilla-release, and patches backporting all the fixes for bugs that the checking turns up on jit_tests.py and jstests.py, for each of those trees. Let me know if you'd like me to attach these patches to this bug.

Comment 21

[Marty Rosenberg [:mjrosenb]]

(In reply to Nicolas B. Pierron [:nbp] from comment #13)
> The risk seems to be that we could have a off-by-less-than-one which can be
> scale to any magnitude with a multiplication and later truncated to get an
> offset.
> 
> Hopefully, (I really feel released by reading the code carefully) there is
> no way that we would remove a bound check around an array if we have a
> modulo as an operand of the array.  So this bug cannot be sec-critical.
> 
> Marty: Can you confirm that I read the code correctly?

Yes, we can get an arbitrary amount above the range that we've calculated, but we can only get a double range.  Won't we need to have an explicit conversion to integer? I don't see any range calculation for a double -> integer conversion.

Comment 22

[Nicolas B. Pierron [:nbp]]

(In reply to Marty Rosenberg [:mjrosenb] from comment #21)
> (In reply to Nicolas B. Pierron [:nbp] from comment #13)
> > The risk seems to be that we could have a off-by-less-than-one which can be
> > scale to any magnitude with a multiplication and later truncated to get an
> > offset.
> > 
> > Hopefully, (I really feel released by reading the code carefully) there is
> > no way that we would remove a bound check around an array if we have a
> > modulo as an operand of the array.  So this bug cannot be sec-critical.
> > 
> > Marty: Can you confirm that I read the code correctly?
> 
> Yes, we can get an arbitrary amount above the range that we've calculated,
> but we can only get a double range.  Won't we need to have an explicit
> conversion to integer? I don't see any range calculation for a double ->
> integer conversion.

Yes, we would need a truncate before writing to / reading from any array.  My worry is about removing bounds check.  If we are ever able to remove a bound check, then we can overflow or underflow the buffer (which would be a way easier exploit).

One of the thing I was thinking of something like:

  arr[((-1 % 0.5) * 2 * 8) | 0] = 0x7fffffff; // map all memory in this array

But hopefully this case is not supported as described in comment 19.

Comment 23

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #15)
> Created attachment 797580 [details] [diff] [review]
> beta.patch

If your patches are ready, you should ask for approval.  Look at the attachement details.

Comment 24

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/c0e80bbe50fb
https://hg.mozilla.org/mozilla-central/rev/b6412dc95e7f

Comment 25

[Dan Gohman [:sunfish]]

Comment on attachment 797549 [details] [diff] [review]
aurora.patch

[Approval Request Comment]
Bug caused by (feature/regressing bug #): 909494
User impact if declined: See bug 909494
Testing completed (on m-c, etc.): The patch is green on m-c.
Risk to taking this patch (and alternatives if risky):

It seems low. The patch is small and simple, and there are no known complications.

String or IDL/UUID changes made by this patch:

None.

Comment 26

[Dan Gohman [:sunfish]]

Comment on attachment 797580 [details] [diff] [review]
beta.patch

[Approval Request Comment]
Bug caused by (feature/regressing bug #): 909494
User impact if declined: See bug 909494
Testing completed (on m-c, etc.): The patch is green on m-c.
Risk to taking this patch (and alternatives if risky): 

It seems low. The patch is small and simple, and there are no known complications.

String or IDL/UUID changes made by this patch:

None.

Comment 27

[Dan Gohman [:sunfish]]

Comment on attachment 797586 [details] [diff] [review]
release.patch

[Approval Request Comment]
Regression caused by (bug #): 909494
User impact if declined: See bug 909494
Testing completed (on m-c, etc.): The patch is green on m-c.
Risk to taking this patch (and alternatives if risky):

It seems low. The patch is small and simple, and there are no known complications.

String or IDL/UUID changes made by this patch:

None.

Comment 28

[Al Billings [:abillings]]

This is a security bug that is rated "sec-high" that affects more than trunk. Before branches can be approved, someone needs to mark this sec-approval? and fill out the template.

Just because this got checked in incorrectly without sec-approval doesn't mean we shouldn't still answer the questions. It helps us determine whether to take it on branches (though, since it is public, effectively, I'm inclined to do so).

Comment 29

[Al Billings [:abillings]]

Comment on attachment 797586 [details] [diff] [review]
release.patch

We're not going to take this on release branch. 

The question right now is Aurora and Beta.

Comment 30

[Dan Gohman [:sunfish]]

Comment on attachment 797549 [details] [diff] [review]
aurora.patch

[Security approval request comment]
How easily could an exploit be constructed based on the patch?

It's not trivial. The available testcases don't trigger the bug in release builds, as they rely on the --ion-check-range-analysis debug flag. A few different people have looked at this bug and have not been able to construct a testcase which actually exploits the bug. That doesn't necessarily mean it's impossible, of course.

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

The bug itself is pretty obvious in the patch, but it takes some creativity to connect the bug with the right circumstances to make this security-relevant.

Which older supported branches are affected by this flaw?

Releases back to Firefox 23 contain the bug.

If not all supported branches, which bug introduced the flaw?

The flaw was introduced in bug 841666.

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

Yes. Attached to bug 909494 are backports for all affected branches.

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

It is very unlikely to cause regressions. The patch is small and uncomplicated, and probably does not need any testing beyond what would be done for any patch.

Comment 31

[Dan Gohman [:sunfish]]

I created bug 911320 to track the patches which backport --ion-check-range-analysis and associated bug fixes to all the various branches.

Comment 32

[Al Billings [:abillings]]

Thanks. We should probably take this on Beta and Aurora.

Comment 33

[Dan Gohman [:sunfish]]

Do you want me to check the patch into Beta and Aurora now, or should I wait for the branch approvals?

Comment 34

[Al Billings [:abillings]]

Please wait for specific branch approvals.

Comment 35

[bhavana bajaj [:bajaj]]

Comment on attachment 797580 [details] [diff] [review]
beta.patch

Given the cat is out the bag already, and the looks safe and contained.

Also discussed with :nbp and confirmed this area has enough tests, so approving on branches.If there is anyways QA can help in additional verification please add verifyme with more details.

Comment 36

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-aurora/rev/9dd5f0e7f716
https://hg.mozilla.org/releases/mozilla-beta/rev/2a52a96cb0c6

Comment 37

[Sean Stangl [:sstangl]]

Clearing old needinfo.