Last Comment Bug 664009 - (CVE-2011-2371) Array.reduceRight() info leak and potential code execution
(CVE-2011-2371)
: Array.reduceRight() info leak and potential code execution
Status: VERIFIED FIXED
[sg:critical?]
: verified1.9.2
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: All All
: -- normal (vote)
: ---
Assigned To: Brendan Eich [:brendan]
:
Mentors:
: 883605 (view as bug list)
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2011-06-13 16:06 PDT by Daniel Veditz [:dveditz]
Modified: 2014-09-04 17:12 PDT (History)
12 users (show)
rforbes: sec‑bounty+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---
+
fixed
+
fixed
+
fixed
.x-fixed
.18+
.18-fixed


Attachments
ruby server PoC (8.82 KB, text/plain)
2011-06-13 16:06 PDT, Daniel Veditz [:dveditz]
no flags Details
Leak testcase from PoC (684 bytes, text/html)
2011-06-13 16:12 PDT, Daniel Veditz [:dveditz]
no flags Details
Crash testcase from PoC (709 bytes, text/html)
2011-06-13 16:13 PDT, Daniel Veditz [:dveditz]
no flags Details
Leak testcase from PoC (684 bytes, text/html)
2011-06-13 16:22 PDT, Daniel Veditz [:dveditz]
no flags Details
Potential deliberately-very-minimal patch (1.00 KB, patch)
2011-06-13 18:12 PDT, Jeff Walden [:Waldo] (remove +bmo to email)
no flags Details | Diff | Review
minimal patch using jsuint (modular two's-complement += ftw) (1.26 KB, patch)
2011-06-13 21:52 PDT, Brendan Eich [:brendan]
jwalden+bmo: review+
christian: approval‑mozilla‑aurora+
christian: approval‑mozilla‑beta+
christian: approval2.0+
christian: approval1.9.2.18+
Details | Diff | Review
Leak POC (sometimes crashes) (715 bytes, text/html)
2011-06-15 12:58 PDT, Daniel Veditz [:dveditz]
no flags Details

Description Daniel Veditz [:dveditz] 2011-06-13 16:06:09 PDT
Created attachment 539035 [details]
ruby server PoC

Chris Rohlf and Yan Ivnitskiy are giving a talk at BlackHat 2011 on the security risks of JIT engines.
https://www.blackhat.com/html/bh-us-11/bh-us-11-briefings.html#Rohlf

The have provided a Ruby Sinatra server PoC and the following details:

=begin

Mozilla Firefox 4.0.1 Array.reduceRight() Vulnerability

Firefox 4.0.1 contains an integer overflow that can lead to an information leak
and arbitrary code execution.

Quick Reproduction Steps:

1. Create an Array object
2. Set Array object length to MAX_UINT-1
3. Call reduceRight(Function()) on new Array

When the reduceRight method is called on an Array object instance execution
transferred to array_extra() in jsarray.cpp. This function first determines
if the argument passed to the method is a callable object (such as a function)
that will be called for each element of the array. If this test passes then
the following code is executed:

1. line 2740 jsarray.cpp reads in the Array.length property to an unsigned
   integer: 
    ...
    jsuint length;
    if (!js_GetLengthProperty(cx, obj, &length))
        return JS_FALSE;
    ...

2. line 2767 jsarray.cpp start, end and step are initialized but reversed
   if the method called is reduceRight(). These variables are all signed integers
    ...
    jsint start = 0, end = length, step = 1;

    switch (mode) {
      case REDUCE_RIGHT:
        start = length - 1, end = -1, step = -1;
    ...

3. A call to GetElement is made on line 2784. Below is the function prototype
   for the GetElement function:
    ...
    GetElement(JSContext *cx, JSObject *obj, jsdouble index, JSBool *hole, Value *vp)
    ...
   
    This first call to GetElement can be avoided by providing >= 2 arguments
    to the reduceRight() call.

    The call to GetElement on line 2839 is the call we want to reach. This call
    lies within a giant for loop that iterates over each element of the array
    calling the Javascript callback provided as the first argument to reduceRight()

4. Now that a controllable signed index value is passed into GetElement
   the following if statement is executed:
    ...
    JS_ASSERT(index >= 0); // <- NOT EXECUTED UNLESS DEBUG BUILD
    if (obj->isDenseArray() && index < obj->getDenseArrayCapacity() &&
        !(*vp = obj->getDenseArrayElement(uint32(index))).isMagic(JS_ARRAY_HOLE)) {
        *hole = JS_FALSE;
        return JS_TRUE;
    }
    ...

    - The call to obj->isDenseArray() should succeed.
    - The return value of obj->getDenseArrayCapacity() should return 16
    - The call to '*vp = obj->getDenseArrayElement(uint32(index))).isMagic(JS_ARRAY_HOLE)'
      boils down to a call to getSlot(index) on line 334 of jsobjinlines.h
      This getSlot(index) call is on 686 of jsobj.h basically executes:

        obj->slots[attacker_controlled_index]

    - The *vp pointer now points out of bounds from the obj->slots array. If this
      doesn't point to a mapped page then the process will crash. If the page is
      mapped then we read this value and return it as the value of that location
      in the array.

    - *vp is actually a Value class instance which contains a jsval_layout union, which
      means our leaked Value may be interpreted as an Integer, String or Object value.

    Continuing down the vulnerable code path...

    5. Back in array_extra() the following code is executed

    ...
    for (jsint i = start; i != end; i += step) {
        JSBool hole;
        ok = JS_CHECK_OPERATION_LIMIT(cx) &&
            GetElement(cx, obj, i, &hole, tvr.addr()); // line 2839 of jsarray.cpp (shown in #4)
    ...
        uintN argi = 0;
        if (REDUCE_MODE(mode))              // setup the arguments to reduceRight()
            session[argi++] = *vp;          // prev
        session[argi++] = tvr.value();      // current (our information leak)
        session[argi++] = Int32Value(i);    // index
        session[argi]   = objv;             // array

        /* Do the call. */
        ok = session.invoke(cx);            // invoke the javascript callback
    ...

    - So now in our reduceRight() callback function we have a leaked value (current)

    - Code execution is possible via heap spray. We simply spray a bunch of fake
      Value's tagged as type JSVAL_TYPE_OBJECT and control their asPtr and ptr members
      which will lead to all sorts of exploitable conditions.

Below is a working ruby Sinatra server that will demonstrate a reliable information leak and
somewhat reliable code execution.

When run under 32bit linux this POC should leak many libxul pointers stored just beneath
the obj->slots[] array in memory. Heres the output of GDB that proves code execution is possible.
Once the Value is controlled by the attacker in the reduceRight callback we trigger a method
off the object such as setting an element and execution is transferred to the JIT'd SetElem
method which calls obj->setProperty()

(gdb) bt 5
#0  0x070c0c0c in ?? ()
#1  0x01e76af4 in setProperty (f=...) at /builds/slave/rel-2.0-lnx-bld/build/js/src/jsobj.h:1232
#2  js::mjit::stubs::SetElem<0> (f=...)
    at /builds/slave/rel-2.0-lnx-bld/build/js/src/methodjit/StubCalls.cpp:567
#3  0x08cf3b4a in ?? ()
#4  0x01daf61a in js::mjit::EnterMethodJIT (cx=0xb1178680, fp=0xb2eff0c0, code=0x8cf3a10, 
    stackLimit=0xb2f8baf0) at /builds/slave/rel-2.0-lnx-bld/build/js/src/methodjit/MethodJIT.cpp:749
(More stack frames follow...)
(gdb) i r
eax            0xb1178680   -1323858304
ecx            0x1  1
edx            0x70c0c0c    118230028
ebx            0x22827b4    36186036
esp            0xbfe67e6c   0xbfe67e6c
ebp            0xbfe67ec0   0xbfe67ec0
esi            0xb2eff108   -1292898040
edi            0xc0c0c0c    202116108
eip            0x70c0c0c    0x70c0c0c
eflags         0x210206 [ PF IF RF ID ]
cs             0x73 115
ss             0x7b 123
ds             0x7b 123
es             0x7b 123
fs             0x0  0
gs             0x33 51

Disassembly of SetElement once edx is controlled:

0x1e76ac8 <js::mjit::stubs::SetElem<0>(js::VMFrame&)+152>:   mov    0x64(%edx),%edx <- edx = 0x0c0c0c0c
0x1e76acb <js::mjit::stubs::SetElem<0>(js::VMFrame&)+155>:   test   %edx,%edx       <- edx = 0x070c0c0c 
0x1e76acd <js::mjit::stubs::SetElem<0>(js::VMFrame&)+157>:   je     0x1e76b88 <js::mjit::stubs::SetElem<0>(js::VMFrame&)+344>
0x1e76ad3 <js::mjit::stubs::SetElem<0>(js::VMFrame&)+163>:   lea    0x28(%esp),%eax
0x1e76ad7 <js::mjit::stubs::SetElem<0>(js::VMFrame&)+167>:   mov    %eax,0xc(%esp)
0x1e76adb <js::mjit::stubs::SetElem<0>(js::VMFrame&)+171>:   mov    0x20(%esp),%eax
0x1e76adf <js::mjit::stubs::SetElem<0>(js::VMFrame&)+175>:   movl   $0x0,0x10(%esp)
0x1e76ae7 <js::mjit::stubs::SetElem<0>(js::VMFrame&)+183>:   mov    %ecx,0x8(%esp)
0x1e76aeb <js::mjit::stubs::SetElem<0>(js::VMFrame&)+187>:   mov    %edi,0x4(%esp)
0x1e76aef <js::mjit::stubs::SetElem<0>(js::VMFrame&)+191>:   mov    %eax,(%esp)
0x1e76af2 <js::mjit::stubs::SetElem<0>(js::VMFrame&)+194>:   call   *%edx    <- call 0x070c0c0c (setProperty)

This vulnerability was discovered and researched by Chris Rohlf of Matasano Security.

** This has only been tested on 32bit Ubuntu 11.04 with Firefox 4.0.1 **

=end
Comment 1 Daniel Veditz [:dveditz] 2011-06-13 16:12:01 PDT
Created attachment 539039 [details]
Leak testcase from PoC
Comment 2 Daniel Veditz [:dveditz] 2011-06-13 16:13:31 PDT
Created attachment 539040 [details]
Crash testcase from PoC

Pulled the testcases out of the server code into standalone html files
Comment 3 Daniel Veditz [:dveditz] 2011-06-13 16:22:01 PDT
Created attachment 539041 [details]
Leak testcase from PoC
Comment 4 Jeff Walden [:Waldo] (remove +bmo to email) 2011-06-13 18:12:54 PDT
Created attachment 539075 [details] [diff] [review]
Potential deliberately-very-minimal patch

I'm not fully convinced this is a complete fix.  But if it is, it's probably as minimal as you'll get.  Outside stable-release tunnel vision, I think the array extras would be clearer, and the fix would be simpler to verify, if the extras didn't share a single heavily mode-conditioned implementation (with the reduces as an arguable sub-mode, even).  Maybe for trunk, after the core problem is fixed.
Comment 5 Brendan Eich [:brendan] 2011-06-13 21:25:29 PDT
(In reply to comment #4)
> Created attachment 539075 [details] [diff] [review] [review]
> Potential deliberately-very-minimal patch
> 
> I'm not fully convinced this is a complete fix.

The regression was introduced by the patch for bug 465980. Right?

That is, only with that bug's patch was GetElement (GetArrayElement in that bug's patch) able to use a negative index. The diff excerpt from that patch:

-GetArrayElement(JSContext *cx, JSObject *obj, jsuint index, JSBool *hole,
+GetArrayElement(JSContext *cx, JSObject *obj, jsdouble index, JSBool *hole,
                 jsval *vp)
 {
     jsid id;
     JSObject *obj2;
     JSProperty *prop;
+    JSBool ok;
+    JSTempValueRooter tvr;
+    jsval idval;
 
+    JS_ASSERT(index >= 0);
     if (OBJ_IS_DENSE_ARRAY(cx, obj) && index < ARRAY_DENSE_LENGTH(obj) &&
-        (*vp = obj->dslots[index]) != JSVAL_HOLE) {
+        (*vp = obj->dslots[(jsuint) index]) != JSVAL_HOLE) {

With jsuint index, the index < ARRAY_DENSE_LENGTH(obj) would be false, saving the day.

> But if it is, it's probably as minimal as you'll get.

There's no reason to use uint64 here.

> Outside stable-release tunnel vision, I think the
> array extras would be clearer, and the fix would be simpler to verify, if
> the extras didn't share a single heavily mode-conditioned implementation
> (with the reduces as an arguable sub-mode, even).  Maybe for trunk, after
> the core problem is fixed.

Yes, please file -- good idea. The old code sharing here is complex and costly: it puts the extra tests inside the loop, rather than customizing the loop for each case without any tests anywhere. Common helpers for the bulky stuff common code sequences, inline if profiling says yes.

/be
Comment 6 Brendan Eich [:brendan] 2011-06-13 21:34:09 PDT
> Common helpers for the bulky stuff common code sequences

"common to all code sequences", or "common to all cases", I meant.

The big loop must keep i within [0, UINT32_MAX] no matter what, so the minimal fix is to make start, end, and i all jsuint (keep step jsint).

/be
Comment 7 Daniel Veditz [:dveditz] 2011-06-13 21:41:36 PDT
I apparently fail at testcases (working on getting sinatra installed to try the original PoC) but Jeff points out that the error is clearly visible in the assertion (debug build/shell required) given by

new Array(Math.pow(2, 32) - 1).reduceRight(function() { }, {}, {}, {})
Comment 8 Brendan Eich [:brendan] 2011-06-13 21:48:24 PDT
(In reply to comment #6)
> The big loop must keep i within [0, UINT32_MAX] no matter what, so the
> minimal fix is to make start, end, and i all jsuint (keep step jsint).

(In reply to comment #7)
> new Array(Math.pow(2, 32) - 1).reduceRight(function() { }, {}, {}, {})

Does not assert, just takes too long, with the proposed comment 6 fix.

/be
Comment 9 Brendan Eich [:brendan] 2011-06-13 21:52:44 PDT
Created attachment 539120 [details] [diff] [review]
minimal patch using jsuint (modular two's-complement += ftw)
Comment 10 Jeff Walden [:Waldo] (remove +bmo to email) 2011-06-14 14:39:31 PDT
Comment on attachment 539120 [details] [diff] [review]
minimal patch using jsuint (modular two's-complement += ftw)

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

I liked uint64 more because the sentinel value wasn't a valid array index, but |length - 1| won't be UINT32_MAX because if |length == 0|, we either throw (if argc is 0 or 1) or never get an element out, so the sentinel doesn't actually overlap the used value space.  I think this code's more confusing than it needs to be, but I think it's correct.
Comment 11 Cameron Kaiser [:spectre] 2011-06-14 16:17:54 PDT
Comment on attachment 539120 [details] [diff] [review]
minimal patch using jsuint (modular two's-complement += ftw)

Applies cleanly to mozilla-2.0; asking for approval.
Comment 14 Daniel Veditz [:dveditz] 2011-06-15 12:58:47 PDT
Created attachment 539628 [details]
Leak POC (sometimes crashes)
Comment 15 Daniel Veditz [:dveditz] 2011-06-15 14:09:54 PDT
Verified fixed in today's mozilla-central (7.0a1) build
Comment 16 [On PTO until 6/29] 2011-06-16 17:36:13 PDT
Verified this in build 1 and build 2 ( Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2.18) Gecko/20110614 Firefox/3.6.18) of 1.9.2.18. It was crashing pretty reliably in 1.9.2.18 build 1 and this behavior is gone in build 2.
Comment 17 Andrew McCreight (PTO-ish through 6-29) [:mccr8] 2013-06-17 17:22:47 PDT
*** Bug 883605 has been marked as a duplicate of this bug. ***
Comment 18 Raymond Forbes[:rforbes] 2013-07-19 18:40:48 PDT
rforbes-bugspam-for-setting-that-bounty-flag-20130719

Note You need to log in before you can comment on or make changes to this bug.