1325052 - Assertion failure: !elements[i].isMarkable(), at /home/andre/hg/mozilla-inbound/js/src/gc/Marking.cpp:1607

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[André Bargull [:anba]]

Test case:
---
Object.setPrototypeOf(Array.prototype, {
    get 0() {
        Object.setPrototypeOf(Array.prototype, Object.prototype);
        return "str";
    }
});

var array = [
/*hole*/,2,3,4,5,6,7,8,9,
10,11,12,13,14,15,16,17,18,19,
20,21,22,23,24,25,26,27,28,29,
30,31,32,33,34,35,36,37,38,39,
];

array.sort();

for (var i = 0; i < 10; ++i) gc();

print(array[array.length - 1]);
---

Triggers this assertion:
---
Assertion failure: !elements[i].isMarkable(), at /home/andre/hg/mozilla-inbound/js/src/gc/Marking.cpp:1607
---

Backtrace:
---
#0  0x000000000102b19f in ObjectDenseElementsMayBeMarkable(js::NativeObject*) (nobj=(js::NativeObject *) 0x7ffff198a190 [object Array])
    at /home/andre/hg/mozilla-inbound/js/src/gc/Marking.cpp:1607
#1  0x000000000102d5ab in js::TenuringTracer::traceObject(JSObject*) (this=0x7fffffffbf90, obj=(JSObject *) 0x7ffff198a190 [object Array])
    at /home/andre/hg/mozilla-inbound/js/src/gc/Marking.cpp:2460
#2  0x000000000102d489 in js::Nursery::collectToFixedPoint(js::TenuringTracer&, js::gc::TenureCountCache&) (this=0x7ffff6965b00, mover=..., tenureCounts=...)
    at /home/andre/hg/mozilla-inbound/js/src/gc/Marking.cpp:2427
#3  0x00000000010a5cac in js::Nursery::doCollection(JSRuntime*, JS::gcreason::Reason, js::gc::TenureCountCache&) (this=0x7ffff6965b00, rt=0x7ffff6965208, reason=JS::gcreason::API, tenureCounts=...) at /home/andre/hg/mozilla-inbound/js/src/gc/Nursery.cpp:721
#4  0x00000000010a5428 in js::Nursery::collect(JSRuntime*, JS::gcreason::Reason) (this=0x7ffff6965b00, rt=0x7ffff6965208, reason=JS::gcreason::API)
    at /home/andre/hg/mozilla-inbound/js/src/gc/Nursery.cpp:588
#5  0x0000000000a7594f in js::gc::GCRuntime::minorGC(JS::gcreason::Reason, js::gcstats::Phase) (this=0x7ffff6965aa8, reason=JS::gcreason::API, phase=js::gcstats::PHASE_EVICT_NURSERY) at /home/andre/hg/mozilla-inbound/js/src/jsgc.cpp:6566
#6  0x000000000095801d in js::gc::GCRuntime::evictNursery(JS::gcreason::Reason) (this=0x7ffff6965aa8, reason=JS::gcreason::API)
    at /home/andre/hg/mozilla-inbound/js/src/gc/GCRuntime.h:624
#7  0x0000000000a73f06 in js::gc::GCRuntime::gcCycle(bool, js::SliceBudget&, JS::gcreason::Reason) (this=0x7ffff6965aa8, nonincrementalByAPI=true, budget=..., reason=JS::gcreason::API) at /home/andre/hg/mozilla-inbound/js/src/jsgc.cpp:6123
#8  0x0000000000a74b3a in js::gc::GCRuntime::collect(bool, js::SliceBudget, JS::gcreason::Reason) (this=0x7ffff6965aa8, nonincrementalByAPI=true, budget=..., reason=JS::gcreason::API) at /home/andre/hg/mozilla-inbound/js/src/jsgc.cpp:6338
#9  0x0000000000a74e70 in js::gc::GCRuntime::gc(JSGCInvocationKind, JS::gcreason::Reason) (this=0x7ffff6965aa8, gckind=GC_NORMAL, reason=JS::gcreason::API)
    at /home/andre/hg/mozilla-inbound/js/src/jsgc.cpp:6399
#10 0x0000000000a7818f in JS::GCForReason(JSContext*, JSGCInvocationKind, JS::gcreason::Reason) (cx=0x7ffff6965000, gckind=GC_NORMAL, reason=JS::gcreason::API)
    at /home/andre/hg/mozilla-inbound/js/src/jsgc.cpp:7230
#11 0x0000000000928aff in GC(JSContext*, unsigned int, JS::Value*) (cx=0x7ffff6965000, argc=0, vp=0x7ffff1531090)
    at /home/andre/hg/mozilla-inbound/js/src/builtin/TestingFunctions.cpp:321
[...]
---


Caused by this line in js::array_sort [1]:
---
if (!InitArrayElements(cx, obj, 0, uint32_t(n), vec.begin(), ShouldUpdateTypes::DontUpdate))
---

We mustn't use the DontUpdate parameter to make sure the types are properly updated for the test case.

[1] https://dxr.mozilla.org/mozilla-central/rev/7083c0d30e75fc102c715887af9faec933e936f8/js/src/jsarray.cpp#2023

Comment 1

[André Bargull [:anba]]

Attachment: bug1325052.patch

The patch simply removes the faulty optimization. We may be able to keep this optimization if we add additional pre- and post-conditions to make sure it's not possible to introduce new types into the array's group, but this requires more work and for now I only want to make sure the bug gets fixed, because it seems to allow accessing strings/objects which were gc'ed.

(For example when I change "str" in #0 to |"abc".repeat(5).substring(2, 10);|, I get: 'Cannot access memory at address 0x4b4b4b4b4b4b4b4b'. And similar crashes when "str" is replaced with an object literal.)

Comment 2

[André Bargull [:anba]]

Attachment: bug1325052-testcase.patch

And a test case for this bug.

Comment 3

[Daniel Veditz [:dveditz]]

Jeff: what's the security implication and appropriate rating of this bug?

Comment 4

[Andrew McCreight [:mccr8]]

(In reply to Daniel Veditz [:dveditz] from comment #3)
> Jeff: what's the security implication and appropriate rating of this bug?

This sounds like it is a use-after-free.

Comment 5

[André Bargull [:anba]]

Does it make sense to request uplift for Aurora for this bug?

Comment 6

[Ryan VanderMeulen [:RyanVM]]

If older branches are affected, absolutely. How far back does this go? Note that since this is a sec-critical affecting more than trunk, you'll also need to request sec-approval on the patch prior to pushing it as well.
https://wiki.mozilla.org/Security/Bug_Approval_Process

Comment 7

[Jeff Walden [:Waldo]]

Yes, this should be fixed everywhere.

Comment 8

[André Bargull [:anba]]

(In reply to Ryan VanderMeulen [:RyanVM] from comment #6)
> If older branches are affected, absolutely. How far back does this go?

The test case should be reproducible starting with bug 1177515, but the underlying issue is even older.

Comment 9

[Ryan VanderMeulen [:RyanVM]]

Thanks, let's get the ball rolling on sec-approval ASAP then.

Comment 10

[André Bargull [:anba]]

Meh, I need to create a new patch, because the current patch regresses sorting int- or string-only arrays badly (~30-50% in a µ-benchmark sorting a 1024-element array without a comparator function).

Comment 11

[Jeff Walden [:Waldo]]

Perhaps only try to optimize if the array has dense initialized elements over the relevant range?  Poking directly at the slots should be safe in that setup and would fairly clearly not invoke arbitrary code, the ultimate transgression here.

Comment 12

[André Bargull [:anba]]

I'm currently testing with:
---
@@ -1960,2 +1960,3 @@ js::array_sort(JSContext* cx, unsigned a
         bool allInts = true;
+        bool extraIndexed = ObjectMayHaveExtraIndexedProperties(obj);
         RootedValue v(cx);
@@ -2022,3 +2023,6 @@ js::array_sort(JSContext* cx, unsigned a
 
-        if (!InitArrayElements(cx, obj, 0, uint32_t(n), vec.begin(), ShouldUpdateTypes::DontUpdate))
+        ShouldUpdateTypes updateTypes = extraIndexed || !(allStrings || allInts)
+                                        ? ShouldUpdateTypes::Update
+                                        : ShouldUpdateTypes::DontUpdate;
+        if (!InitArrayElements(cx, obj, 0, uint32_t(n), vec.begin(), updateTypes))
             return false;
---

I'm not quite sure whether or not I need the "!(allStrings || allInts)" part. I was thinking about side-effects when the array contains objects with toString/valueOf methods, like |[{toString(){print("side-effect?"); return ""}}, ""].sort()|, and if those side-effects can lead to problems when ShouldUpdateTypes::DontUpdate is used.

Comment 13

[Julien Cristau [:jcristau]]

tracking 51 and up for this sec-critical issue

Comment 14

[André Bargull [:anba]]

Attachment: bug1325052.patch

Updated patch to avoid performance regressions.

When `ObjectMayHaveExtraIndexedProperties(obj)` is false before entering the loop to collect the array elements, collecting the elements shouldn't be able to execute any user code. And if additionally `allStrings || allInts` is true, sorting shouldn't also be able to execute user code. Combining both conditions should ensure the ObjectGroup types don't change during the sort, which enables us to use ShouldUpdateTypes::DontUpdate for InitArrayElements.

Comment 15

[André Bargull [:anba]]

Attachment: bug1325052-testcase.patch

Same test case as before, but also added a comment to array_sort explaining when it's okay to use ShouldUpdateTypes::DontUpdate. It's probably safer to add the comment when the test case lands compared to adding it when fixing the sec-issue, right?

Comment 16

[Hannes Verschore [:h4writer]]

Pinging to get this moving. We don't have a lot of time left.

Comment 17

[Liz Henry (:lizzard Please n-i to RyanVM, jcristau, or pascal)]

I'm intending to start the 51 RC2 build later this afternoon. Is this urgent enough to potentially delay the 51 release? 
Note we usually do not want to land tests until we're ready to un-hide the bug.

Comment 18

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

Is this chemspill worthy? Would we make a new release just for this? 

Otherwise, it is a bad security bug with unreviewed patches six days before we go live on RC builds we're already making.

Comment 19

[Jeff Walden [:Waldo]]

Comment on attachment 8825848 [details] [diff] [review]
bug1325052-testcase.patch

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

Yeah, don't add the comment til the testcase can safely land.

::: js/src/jsarray.cpp
@@ +2021,5 @@
>              }
>          }
>  
> +        // We can omit the type update when neither collecting the elements
> +        // nor calling the default comparator can execute user code.

s/user code/a getter function that might execute user code/, perhaps.  Or something like that.  Just, be clearer about exactly what would/could cause user code to run.

Comment 20

[Jeff Walden [:Waldo]]

So, this is like any other sec-critical sort of thing.  If no one finds it and exploits it, it can remain unlanded arbitrarily long.  But we can't *know* that's the case, of course, or even guess with much certainty.

The interaction to trigger this isn't unusually intricate, so it's probably more worrisome leaving it unfixed, than (say) leaving an obscure GC issue unfixed.  But I have no idea whether that's worrisome enough that we *must* force this.

If timing is a super-issue, *probably* we can wait on it?  And the odds would be in our favor that it wouldn't be exploited during the extra delay to its being fixed in a dot release (whether as part of a set of patches that together motivate a dot release, or on its own -- the latter being a judgment call I really dunno about).  But there's no certainty to anything, other than that fixing early means less exposure for sure.

If we delay landing this, as per my usual practice, it's probably good to delay the landing for dot-release as absolutely far out as possible, so the window of exposure is minimized to the utmost.  This patch is safe enough that it doesn't need to have extra testing prior to release, to be confident in it, IMO.

Comment 21

[André Bargull [:anba]]

Attachment: bug1325052.patch

Updated patch to apply cleanly on inbound. No change in behaviour, carrying r+ from Waldo.

Comment 22

[André Bargull [:anba]]

Comment on attachment 8828356 [details] [diff] [review]
bug1325052.patch

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

- It shouldn't be too hard to figure out what went wrong when reviewing the patch, because it changes only a handful of lines. 


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

- No, comments and the test case for this bug are attached to a different patch.


Which older supported branches are affected by this flaw?
If not all supported branches, which bug introduced the flaw?

- All supported branches, the crash is reproducible starting with mozilla42 (comment #8).


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

- Patches for beta and aurora are the same as the one for central, patch for esr45 needs a small modification, but also mostly the same. All patches are low risk, because they only disable an optimization.


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

- It's unlikely to cause new regressions; no further testing apart from the test case should be needed.

Comment 23

[André Bargull [:anba]]

Attachment: bug1325052-testcase.patch (Do not land until all branches are fixed)

Updated per review comments.

Comment 24

[André Bargull [:anba]]

Attachment: bug1325052-aurora.patch (52)

Patch for Aurora.

Comment 25

[André Bargull [:anba]]

Attachment: bug1325052-beta.patch (51)

Patch for Beta.

Comment 26

[André Bargull [:anba]]

Attachment: bug1325052-esr45.patch

Patch for ESR45.

Comment 27

[André Bargull [:anba]]

(In reply to André Bargull from comment #26)
> Patch for ESR45.

The patch has a small modification to handle user-supplied comparators, because esr45 doesn't have the changes from bug 715181:
When a user-supplied comparator is present (`fval` is not null and the comparator wasn't matched by `MatchNumericComparator()`), we also disable the optimization and use "ShouldUpdateTypes::Update".

Comment 28

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

sec-approval for checkin on February 14, three weeks into the new cycle. I'm gating this a bit in because I'm worried about someone seeing the checkin and reverse engineering an exploit.

Comment 29

[Ryan VanderMeulen [:RyanVM]]

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

Comment 30

[Jeff Walden [:Waldo]]

Comment on attachment 8828373 [details] [diff] [review]
bug1325052-aurora.patch (52)

Approval Request Comment
[Feature/Bug causing the regression]: I *think* bug 638977 and cde201b0e581535ae5ae3160431eb31382593525, i.e. forever.

[User impact if declined]: sec-critical

[Is this code covered by automated tests?]: We have tests, but they aren't landed 'cause security, woo.

[Has the fix been verified in Nightly?]: Landed in nightly just an hour or so ago, presumably not verified yet.

[Needs manual test from QE? If yes, steps to reproduce]: Probably this should.  The testcase *may* work without any extra modifications, in older branches -- if it doesn't, try replacing the |Object.setPrototypeOf(<x>, <y>);| line with |<x>.__proto__ = <y>;| and see if that makes a functioning testcase.

[List of other uplifts needed for the feature/fix]: None.

[Is the change risky?]: [Why is the change risky/not risky?]:
The backports to everything but 45 look pretty straightforward.  There's some risk to them, in that maybe we could miss something about the logic of it.  But multiple of us have looked, and we think we're good -- and the risk seems manageable.

The backport to 45 is trickier, as comment 27 notes -- I did a look at it now and it looks fine, but it *really* would be nice to know the attached testcase is broken without the patch there, and is fixed with it.  The changes were not entirely trivial, and to be honest I probably would have gone with a fresh review of them.  But the backport does appear to be okay (and I guess this comment can be considered an r+ of the backport, if we want to dot our i's here).  Manual testing definitely appreciated!

[String changes made/needed]: N/A

Comment 31

[Jeff Walden [:Waldo]]

Comment on attachment 8828374 [details] [diff] [review]
bug1325052-beta.patch (51)

Approval Request Comment
See comment 30.

Comment 32

[Jeff Walden [:Waldo]]

Comment on attachment 8828375 [details] [diff] [review]
bug1325052-esr45.patch

[Approval Request Comment]
If this is not a sec:{high,crit} bug, please state case for ESR consideration: see comment 30.
User impact if declined: comment 30.
Fix Landed on Version: comment 30.
Risk to taking this patch (and alternatives if risky): For risks, see comment 30.  There are no real alternatives.
String or UUID changes made by this patch: N/A

Comment 33

[Jeff Walden [:Waldo]]

Comment on attachment 8828373 [details] [diff] [review]
bug1325052-aurora.patch (52)

o/~ Time keeps on slippin' into the future... o/~

Comment 34

[Jeff Walden [:Waldo]]

Comment on attachment 8828374 [details] [diff] [review]
bug1325052-beta.patch (51)

Word on the street is release-slip means this particular patch is no longer necessary/approvable/landable.

Comment 35

[Ryan VanderMeulen [:RyanVM]]

Comment on attachment 8828356 [details] [diff] [review]
bug1325052.patch

This applies cleanly to Aurora as-attached. However, it *did* require rebasing to land on trunk, so this patch will need to be applied as-is rather than trying to graft the commit that lands on m-c.

Comment 36

[Julien Cristau [:jcristau]]

Comment on attachment 8828356 [details] [diff] [review]
bug1325052.patch

sec-critical fix for aurora53

See comment 35 about aurora checkin.

Comment 37

[Julien Cristau [:jcristau]]

Comment on attachment 8828373 [details] [diff] [review]
bug1325052-aurora.patch (52)

sec-crit fix for beta52

Comment 38

[Carsten Book [:Tomcat]]

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

Comment 39

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/releases/mozilla-aurora/rev/7fe936056b729aa7ac36c439ed92c8bbe0ec5677

Comment 40

[Gerry Chang [:gchang]]

Comment on attachment 8828375 [details] [diff] [review]
bug1325052-esr45.patch

Fix a sec-critical. ESR45+.

Comment 41

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/releases/mozilla-beta/rev/2004932dea6e

Comment 42

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-esr52/rev/2004932dea6e
https://hg.mozilla.org/releases/mozilla-esr45/rev/886650fac531

Comment 43

[André Bargull [:anba]]

Attachment: bug1325052-testcase.patch

Rebased the test case to apply cleanly on inbound. Carrying r+.

Comment 44

[André Bargull [:anba]]

Check-in needed for:
- bug1325052-testcase.patch

Comment 45

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/472f2a2f55ad
Add test case for bug 1325052. r=Waldo

Comment 46

[Narcis Beleuzu [:NarcisB]]

https://hg.mozilla.org/mozilla-central/rev/472f2a2f55ad