Closed Bug 937793 Opened 7 years ago Closed 7 years ago

Assertion failure: getElementsHeader()->capacity >= getElementsHeader()->initializedLength, at jsobj.h:611 or Crash [@ fetchNextFreeArena]


(Core :: JavaScript Engine: JIT, defect)

Not set



Tracking Status
firefox26 --- unaffected
firefox27 + fixed
firefox28 + fixed
firefox29 + fixed
firefox-esr24 --- unaffected
b2g18 --- unaffected
b2g-v1.1hd --- unaffected
b2g-v1.2 --- unaffected
b2g-v1.3 --- fixed
b2g-v1.3T --- fixed
b2g-v1.4 --- fixed


(Reporter: decoder, Assigned: Waldo)



(Keywords: assertion, sec-critical, testcase)


(3 files)

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

for (var i = 0; i < 1e6; i++)
  (new Array(90, "1".prop)).sort();
Neither of those assertions sound good...
Keywords: sec-high
Waldo, could you look at this maybe?
Flags: needinfo?(jwalden+bmo)
Doesn't reproduce on trunk, does with the reported revision.  Array.prototype.sort's code looks fine, both on trunk and at the reported revision.

Running an affected shell, |b js::array_sort|, |c 1096| is fine, then a subsequent |c| hits js::array_sort with a bad |this|.

(gdb) r
Starting program: /home/jwalden/moz/slots/js/src/dbg/./js -e for\ \(var\ i\ =\ 0\;\ i\ \<\ 1e6\;\ i++\)\ \(new\ Array\(90,\ \"1\".prop\)\).sort\(\)\;

Breakpoint 2, js::array_sort (cx=0x1b44f10, argc=0, vp=0x1bcc038) at /home/jwalden/moz/slots/js/src/jsarray.cpp:1841
1841	    CallArgs args = CallArgsFromVp(argc, vp);
(gdb) c 1096
Will ignore next 1095 crossings of breakpoint 2.  Continuing.

Breakpoint 2, js::array_sort (cx=0x1b44f10, argc=0, vp=0x7fffffffa218) at /home/jwalden/moz/slots/js/src/jsarray.cpp:1841
1841	    CallArgs args = CallArgsFromVp(argc, vp);
(gdb) n 6
1857	    if (!obj)
(gdb) p obj->getElementsHeader()[0]
$1 = {flags = 0, initializedLength = 2, capacity = 2, length = 2, static VALUES_PER_HEADER = 2}
(gdb) c

Breakpoint 2, js::array_sort (cx=0x1b44f10, argc=0, vp=0x7fffffffa288) at /home/jwalden/moz/slots/js/src/jsarray.cpp:1841
1841	    CallArgs args = CallArgsFromVp(argc, vp);
(gdb) n 6
1857	    if (!obj)
(gdb) p obj->getElementsHeader()[0]
$2 = {flags = 0, initializedLength = 2, capacity = 0, length = 90, static VALUES_PER_HEADER = 2}

That 90 obviously derives from the 90 as first argument -- extremely rotten.  Restarting, |c 1096|, then |b js::jit::IonBuilder::inlineArray|, the template object's bizarro:

(gdb) p templateObject->getElementsHeader()[0]
$4 = {flags = 0, initializedLength = 0, capacity = 0, length = 90, static VALUES_PER_HEADER = 2}

Which explains the |90| in the broken object.  (|callInfo.argc()| being 2, feeding into MNewArray, explains the ultimate |initializedLength = 2|.)

Reasoning backwards from MXR hits for NewDenseUnallocatedArray (a signature used in rest array template-object creation) took me to js::jit::GetTemplateObjectForNative:

    if (native == js_Array) {
        size_t count = 0;
        if (args.hasDefined(1))
            count = args.length();
        else if (args.hasDefined(0) && args[0].isInt32() && args[0].toInt32() > 0)
            count = args[0].toInt32();
        res.set(NewDenseUnallocatedArray(cx, count, nullptr, TenuredObject));

(n > 1)-ary Array calls *always* create an n-ary array.  |args.hasDefined(1)| (and |args.hasDefined(0)| in a different way) is wrong -- that checks for the argument being provided, but it *also* checks for the argument not being |undefined|.  Doing only an args-length check should fix the bug.

But, hmm.  That line is in the current code as well as the old code.  So some other testcase likely breaks with the current tree -- will investigate to find one.  Good testcase!  (Incidentally, this is why I wouldn't have added isDefined() had I been sole arbiter, or if I'd had the time and motivation to really fight its addition.)
Assignee: general → jwalden+bmo
Component: JavaScript Engine → JavaScript Engine: JIT
Flags: needinfo?(jwalden+bmo)
Keywords: sec-highsec-critical
OS: Linux → All
Hardware: x86_64 → All
More testcases, ones that fail even on trunk:

  for (var i = 0; i < 1e6; i++)
    assertEq(typeof new Array(undefined, undefined, 1, 2, 3, 4).sort()[0],
             "bad, i: " + i);'

with Error: Assertion failed: got "undefined", expected "number": bad, i: 1097

  for (var i = 0; i < 1e6; i++)
    assertEq(new Array(undefined, undefined, 1, 2, 3, 4).length,
             "bad, i: " + i);

with Error: Assertion failed: got 0, expected 6: bad, i: 1097

  for (var i = 0; i < 1e6; i++)
    assertEq(new Array(0, undefined).length, 2, "bad, i: " + i);

with Error: Assertion failed: got 0, expected 2: bad, i: 1097

Note 1097 as the initial failing iteration, similar to the iteration count in comment 4.

I've identified the revision that introduced the problem here, and I've identified the revision that made comment 0's problem disappear.  Just making sure I understand everything before posting a patch...
Attached patch TestsSplinter Review
This was introduced by bug 922270, which introduced the faulty code for this in GetTemplateObjectForNative.

The original testcase here stopped producing errors when bug 936966 landed.  With that, the original testcase, which had been allocating inline, changed to allocation using a VM call.  Why?  The determination was previously based on whether the number of arguments passed to |new Array| (for the != 1 case) was greater than the number of slots in a 16-slot object, minus two for the inlined ObjectElements header an array would use.  |2 > 14| is false, so inlining occurred.

The change made the comparison be of the argument count, compared to the number of array slots *in the template object*.  The count math is still wrong.  But the |capacity >= initializedLength| assertion can no longer fail, because the initializedLength derives from the |new Array| argument count, while the capacity is determined by what NewDenseUnallocatedArray(..., 90 (or some other number), ...) chooses for capacity -- GuessArrayGCKind(90).  Enumerating the possibilities:

  n:     AllocKind:    capacity:     capacity >= initializedLength?
  0      OBJECT8       6             6 >= 2
  1-2    OBJECT4       2             2 >= 2
  3-6    OBJECT8       6             6 >= 2
  7-10   OBJECT12      10            10 >= 2
  11-14  OBJECT16      14            14 >= 2


  15+    OBJECT2       0             0 >= 2 !!!!!
is worrisome.  But in that case, |count() > arraySlots| and so shouldUseVM() and so the inline template object won't be used, so no worries there.

And with that: the reason for the initial bug is understood; the reason it disappeared is understood; and tests for the initial bug, tests for additional flavors, and tests for the initial bug that still fail with the intermediate change have been written.  So we're good.  Here are tests; patch to follow separately.
Attachment #8347797 - Flags: review?(bhackett1024)
Attached patch PatchSplinter Review
There's a little bit of cosmetic change here (make new Array() more explicitly use count = 0, and make the first-argument-is-int case include 0 because logically it does), but the guts of this are eliminating the hasDefined() calls.
Attachment #8347798 - Flags: review?(bhackett1024)
Blocks: 922270
Attachment #8347798 - Flags: review?(bhackett1024) → review+
Attachment #8347797 - Flags: review?(bhackett1024) → review+
Comment on attachment 8347798 [details] [diff] [review]

With bug 936966 landed, I think this might just be a correctness issue -- the created array would have the wrong length but wouldn't be internally inconsistent.  Without it...I'm having trouble holding all the different concepts in my head well enough to be sure this fixes every issue that bug 936966 fixed.  I think we should backport the fix in that bug, for belt-and-suspenders coverage here.

[Security approval request comment]
* How easily could an exploit be constructed based on the patch?
Not sure.  The security implications are semi-obvious here given it's arrays and lengths (see below).  I *think* a bad initializedLength that's also greater than the object's capacity lets you overwrite fields in adjacent objects in the arena, which seems something you could use to produce an exploit without horrible amounts of difficulty (if perhaps with some SpiderMonkey internals familiarity).

* Do comments in the patch, the check-in comment, or tests included in the patch paint a bulls-eye on the security problem?
If you look, and you understand what hasDefined() does differently from comparisons against length(), it's pretty obvious a user-defined value gets used, and by security-bug implication in obviously-wrong ways.  (I don't plan to land the tests til awhile after patch-landing, as usual.)

* Which older supported branches are affected by this flaw?  If not all supported branches, which bug introduced the flaw?
28, 27 (bug 922270 landed in 27)

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

* How likely is this patch to cause regressions; how much testing does it need?
These are the clear semantics of the language constructs, obviously correct, so I think it's pretty safe.  Any issues would likely be from an inconsistency between this code, and the MCallOptimize code, or the MIR code that uses this template object.  I did some looking around and didn't see any inconsistencies, so I think this is good.  (The only valuable testing here will be fuzz-testing; I see no reason why fuzz-testing after landing couldn't smoke out any issues that existed -- which isn't to say I think any will exist, just that the form of code here is likely to be in fuzzers but not really on the web, outside deliberate exploits.)
Attachment #8347798 - Flags: sec-approval?
Comment on attachment 8347798 [details] [diff] [review]

sec-approval+ for trunk.

Please make Aurora and Beta patches so we can avoid shipping this issue as well. If they are made soon, we should have no problem approving them.
Attachment #8347798 - Flags: sec-approval? → sec-approval+
Comment on attachment 8347798 [details] [diff] [review]

Patch applies painlessly to aurora/beta.

[Approval Request Comment]
Bug caused by (feature/regressing bug #): bug 922270
User impact if declined: wrong semantics, possibly worse things as well (but details unclear, see comment 8)
Testing completed (on m-c, etc.): landed on m-c, tested via the tests in this bug (which haven't landed, so as to ideally not give the game away)
Risk to taking this patch (and alternatives if risky): low, as the semantics of new Array(...) are easy to describe, and clearly correlate with what's in this patch
String or IDL/UUID changes made by this patch: N/A
Attachment #8347798 - Flags: approval-mozilla-beta?
Attachment #8347798 - Flags: approval-mozilla-aurora?
landed on central
Closed: 7 years ago
Flags: in-testsuite?
Resolution: --- → FIXED
JSBugMon: This bug has been automatically verified fixed.
Attachment #8347798 - Flags: approval-mozilla-beta?
Attachment #8347798 - Flags: approval-mozilla-beta+
Attachment #8347798 - Flags: approval-mozilla-aurora?
Attachment #8347798 - Flags: approval-mozilla-aurora+
And a few months later, seems like test-landing time to me:
Group: core-security
You need to log in before you can comment on or make changes to this bug.