664009 - (CVE-2011-2371) Array.reduceRight() info leak and potential code execution

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Daniel Veditz [:dveditz]]

Attachment: 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]]

Attachment: Leak testcase from PoC

Comment 2

[Daniel Veditz [:dveditz]]

Attachment: Crash testcase from PoC

Pulled the testcases out of the server code into standalone html files

Comment 3

[Daniel Veditz [:dveditz]]

Attachment: Leak testcase from PoC

Comment 4

[Jeff Walden [:Waldo]]

Attachment: 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]]

(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]]

> 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]]

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]]

(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]]

Attachment: minimal patch using jsuint (modular two's-complement += ftw)

Comment 10

[Jeff Walden [:Waldo]]

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]]

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 12

[Jeff Walden [:Waldo]]

http://hg.mozilla.org/releases/mozilla-1.9.2/rev/a4753322c165
http://hg.mozilla.org/releases/mozilla-2.0/rev/6f4d01073ef8
http://hg.mozilla.org/releases/mozilla-beta/rev/f1acd88f828e
http://hg.mozilla.org/releases/mozilla-aurora/rev/a0113e2614a2
http://hg.mozilla.org/mozilla-central/rev/8159c48ac8c7
http://hg.mozilla.org/partridge-in-a-pear-tree/rev/012345678901

Comment 14

[Daniel Veditz [:dveditz]]

Attachment: Leak POC (sometimes crashes)

Comment 15

[Daniel Veditz [:dveditz]]

Verified fixed in today's mozilla-central (7.0a1) build

Comment 16

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

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 18

[Raymond Forbes[:rforbes]]

rforbes-bugspam-for-setting-that-bounty-flag-20130719