Closed Bug 909494 Opened 6 years ago Closed 6 years ago

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

Categories

(Core :: JavaScript Engine, defect, critical)

x86_64
Linux
defect
Not set
critical

Tracking

()

RESOLVED FIXED
mozilla26
Tracking Status
firefox23 --- wontfix
firefox24 + fixed
firefox25 + fixed
firefox26 + fixed
firefox-esr17 --- unaffected
b2g18 --- unaffected

People

(Reporter: decoder, Assigned: sunfish)

References

(Blocks 1 open bug)

Details

(4 keywords, Whiteboard: [jsbugmon:][adv-main24+])

Attachments

(4 files)

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]);
}
Whiteboard: [jsbugmon:update,bisect]
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.
Whiteboard: [jsbugmon:update,bisect] → [jsbugmon:bisect]
JSBugMon: Cannot process bug: Unable to automatically reproduce, please track manually.
Whiteboard: [jsbugmon:bisect] → [jsbugmon:]
Status: NEW → RESOLVED
Closed: 6 years ago
Resolution: --- → DUPLICATE
Duplicate of bug: 908867
Attached patch bug908867.patchSplinter Review
The "foo" function in the testcase doesn't actually reproduce the bug yet, but it will once some other range analysis enhancements land.
Attachment #797333 - Flags: review?(nicolas.b.pierron)
Status: RESOLVED → REOPENED
Resolution: DUPLICATE → ---
Duplicate of this bug: 908867
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.
Attachment #797333 - Flags: review?(nicolas.b.pierron) → review+
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.
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.
Bug 841666 landed on Firefox 22, so this likely affects 23 and 24 too.
Attached patch aurora.patchSplinter Review
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.
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?
Flags: needinfo?(mrosenberg)
Keywords: sec-high
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?
Flags: needinfo?
Attached patch beta.patchSplinter Review
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.
Attached patch release.patchSplinter Review
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.
(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.
(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?
(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
(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.
(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.
(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.
(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.
https://hg.mozilla.org/mozilla-central/rev/c0e80bbe50fb
https://hg.mozilla.org/mozilla-central/rev/b6412dc95e7f
Status: REOPENED → RESOLVED
Closed: 6 years ago6 years ago
Flags: needinfo?
QA Contact: general → sunfish
Resolution: --- → FIXED
Target Milestone: --- → mozilla26
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.
Attachment #797549 - Flags: approval-mozilla-aurora?
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.
Attachment #797580 - Flags: approval-mozilla-beta?
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.
Attachment #797586 - Flags: approval-mozilla-release?
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 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.
Attachment #797586 - Flags: approval-mozilla-release? → approval-mozilla-release-
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.
Attachment #797549 - Flags: sec-approval?
I created bug 911320 to track the patches which backport --ion-check-range-analysis and associated bug fixes to all the various branches.
Thanks. We should probably take this on Beta and Aurora.
Attachment #797549 - Flags: sec-approval? → sec-approval+
Do you want me to check the patch into Beta and Aurora now, or should I wait for the branch approvals?
Flags: needinfo?(abillings)
Please wait for specific branch approvals.
Flags: needinfo?(abillings)
Flags: needinfo?(release-mgmt)
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.
Attachment #797580 - Flags: approval-mozilla-beta? → approval-mozilla-beta+
Attachment #797549 - Flags: approval-mozilla-aurora? → approval-mozilla-aurora+
Flags: needinfo?(release-mgmt)
Assignee: general → sunfish
Blocks: 841666
Keywords: regression
Whiteboard: [jsbugmon:] → [jsbugmon:][adv-main24+]
Group: core-security
Clearing old needinfo.
Flags: needinfo?(marty.rosenberg)
You need to log in before you can comment on or make changes to this bug.