Deep Differential Fuzzing of JavaScript Engines

Liam Wachter, Julian Gremminger

Supervised by: TT.-Prof. Dr. Christian Wressnegger, Dr. Flavio Toffalini, Prof. Dr. Mathias Payer

Motivation

• Easy to get a victim to execute JS code
• Long history of impactful vulnerabilities
• V8 is 2M+ lines of very complex undocumented code
• JS Engines are their own class of sofware
• With their own classes of bugs
• Even confusing -0.0 with +0.0 is enough for RCE [Röt18]

Overview

Traces

Execution traces even during JIT

Matching

Matching algorithm to compare traces

Dumpling

Differential Fuzzer using our bug oracle

V8 Bugs

Evaluation and 8 new V8 bugs

Background: Execution Tiers

Background: VM State

 0 : 01 0d e8 ff ff 1f LdaSmi.ExtraWide [536870888]
 6 : c5                Star0
 7 : 13 00             LdaConstant [0]
 9 : c2                Star3
10 : 2d f6 01 00       GetNamedProperty r3, [1], [0]
14 : c3                Star2
15 : 5e f7 f6 f9 02    CallProperty1 r2, r3, r0, [2]
20 : c4                Star1
21 : 2d f8 02 04       GetNamedProperty r1, [2], [4]
25 : c3                Star2
26 : 13 03             LdaConstant [3]
28 : c1                Star4
29 : 5f f7 f8 f5 f9 06 CallProperty2 r2, r1, r4, r0, [6]
35 : aa                Return
          

Background: JIT Compilation

Differential Fuzzing

Turn a program against its brothers and sisters

Turn a program against itself

Differentials

• Correct (speculative) optimization is hard
• Ignition and TurboFan code should have the same behavior
• Source of many security bugs in the past
• Differentials as better bug oracle in comparison to crashes

Differential JS Engine fuzzing until now

FuzzJIT [Wan+23]

"We disable the generation of complex statements such as function declarations, class declarations, try/catch statements, switch/case statements. We also avoid generating loop structures inside the function body of opt"

FuzzJIT [Wan+23]

• We, and more systematically [Sch+24], are not able to reproduce their coverage results
• A lot of false positives

function opt(opt_param){
const v3 = [128,128,-271414277];
v3[128] = -271414277;
const v5 = new Uint32Array(v3);
const v6 = v5.sort();
const v7 = [];
const v8 = v3.__proto__;
const v10 = ["16"];
const v11 = v7.push;
const v12 = Reflect.apply(v11,v8,v10);
const v15 = String.fromCharCode(528439.4995012311);
const v16 = String(v5);
return v16;
}
              

JIT-Picker [Ber+22]

                transitioning javascript builtin probe_state(
                js-implicit context: NativeContext, receiver: JSAny)(obj: JSAny): Undefined {

                let curVal: Smi = *NativeContextSlot(ContextSlot::FUZZILLI_HASH_INDEX);
                typeswitch (obj) {

                case (Null): {
                  curVal += 1;
                }
                case (True): {
                  curVal += 2;
                }
                case (False): {
                  curVal += 4;
                }
                case (Undefined): {
                  curVal += 8;
                }
                case (String): {
                  curVal += 16;
                }
                case (s: Smi): {
                  curVal += 32;
                  let doubleValue: float64 = SmiToFloat64(s);
                  if (Float64IsNaN(doubleValue)) {
                    doubleValue = 1.0;
                  }
                  const lWord: uint32 = data_view::Float64ExtractLowWord32(doubleValue);
                  const hWord: uint32 = data_view::Float64ExtractHighWord32(doubleValue);
                  curVal += SmiFromUint32(lWord);
                  curVal += SmiFromUint32(hWord);
                }
                case (n: HeapNumber): {
                  curVal += 32;
                  let doubleValue: float64 = Convert<float64>(n);
                  if (Float64IsNaN(doubleValue)) {
                    doubleValue = 1.0;
                  }
                  const lWord: uint32 = data_view::Float64ExtractLowWord32(doubleValue);
                  const hWord: uint32 = data_view::Float64ExtractHighWord32(doubleValue);
                  curVal += SmiFromUint32(lWord);
                  curVal += SmiFromUint32(hWord);
                }
                case (Object): {
                  curVal += 64;
                }
                }
              

• Probing inhibits optimizations
• Only a small subset of the state probed
• A lot of false positives

Approach

What key challenges did we address?

• Extract full execution state traces (dumps) at high frequency
• Dump comparability
• No influence on JS execution semantics
• Efficient matching of optimized and unoptimized dumps
• No false positives by design during matching

Dumpling

State Extraction: V8 modification

Differential Oracle: Fuzzilli extension

State Extraction

State Extraction: Dumpling mode - JIT

• State is spread accross machine registers and stack

• How do we get back to state comparable to interpreter execution?
• Where is state extraction possible?

• No influence on JS execution semantics and JIT compiler optimizations

How do we get back to state comparable to interpreter execution?

• Deoptimization back to interpreter code in case a deopt point is violated
• A mechanism must exist to restore interpreter state!

Where is state extraction possible?

function f(o1, o2) {
    return o1.a * o2.a;
}

• Possibility to restore interpreter state at deopt points
• Deopt points are naturally interesting probing positions

Insert hooks at deopt points to extract interpreter state

No influence on JIT compiler optimizations?

• Insert hooks at the last stage of the compilation pipeline
• Hooks are not observable by any compiler pass

Dumping during speculative JIT execution

1. Save state
2. Build VM state
3. Rematerialize escaped values
4. "Dump" VM state
5. Restore state and continue JIT execution

→ partial use of existing deopt mechanism

Embedded disassembler before it was cool

static constexpr int kCallBuiltinInstructionSize = 0x5;
static constexpr int kCallDeoptSize = 0x6;

static constexpr int kFromOffToJumpInstruction = kCallBuiltinInstructionSize + kCallDeoptSize;
char *deopt_jump_instruction = ((char *)(from_)) - kFromOffToJumpInstruction;

// near jmp 0x0f8_|offset|
DCHECK_EQ(*deopt_jump_instruction, 0x0f);
DCHECK_EQ((*(deopt_jump_instruction + 1)) & 0xf0, 0x80);

int deopt_rel_offset = *((unsigned int*)(deopt_jump_instruction + 2));
int deopt_offset = deopt_rel_offset + ((int)(from_ - compiled_code_->instruction_start() - kCallBuiltinInstructionSize));
deopt_exit_index_ = (deopt_offset - deopt_start_offset) / kEagerDeoptExitSize;

Maglev dumping

• Similar to the TurboFan approach
• Insert hook during lowering after each deopt point
• The hook implementation is shared between Maglev and TurboFan

State Extraction: Dumpling mode - Interpreter

• Optimized run reports dump locations to the fuzzer
• Hook bytecode execution and extract state at those dump locations

Interpreter dumping

void InterpreterAssembler::Dispatch() {
  Comment("========= Dispatch");
  DCHECK_IMPLIES(Bytecodes::MakesCallAlongCriticalPath(bytecode_), made_call_);
  DumplingHook(...);
  TNode<IntPtrT> target_offset = Advance();
  TNode<WordT> target_bytecode = LoadBytecode(target_offset);
  DispatchToBytecodeWithOptionalStarLookahead(target_bytecode);
}

IGNITION_HANDLER(Star, InterpreterAssembler) {
  TNode<Object> accumulator = GetAccumulator();
  StoreRegisterAtOperandIndex(accumulator, 0);
  Dispatch();
}

• Bytecode handlers are compiled by TurboFan (and not clang)
• Hook this compilation process to instrument each compiled bytecode handler
• Hook called on bytecode execution

Sparkplug

• Hooking similar to interpreter approach
• Baseline compiler
• No speculation, no feedback, no optimization
• Generates machine code

__ CodeEntry();
{
    RCS_BASELINE_SCOPE(Visit);
    Prologue();
    AddPosition();
    for (; !iterator_.done(); iterator_.Advance()) {
      DumplingHook(...);
      VisitSingleBytecode();
      AddPosition();
    }
}

void BaselineCompiler::VisitLdaZero() {
  __ Move(kInterpreterAccumulatorRegister,
          Smi::FromInt(0));
}

void BaselineAssembler::Move(
        interpreter::Register output, 
        Register source) {
  return __ movq(RegisterFrameOperand(output),
                 source);
}

State Serialization

-------TurboFan frame dump-------
pc: 7
acc: 13.37
a0: <Object>{
__proto__: <Class C7>{<String[1]: f>[enumerable]<JSArray>[]},
<String[1]: a>[configurable][enumerable]42(enum cache: 2),
<String[1]: f>[configurable][enumerable]13.37(enum cache: 0)
}
r0: -INFINITY
context: <ScriptContext[4]>
receiver: <JSGlobalProxy>
closure: <JSFunction f0>
Function ID: 27

• Invariant across execution tiers
• Fine-grained (-0.0 and 0.0)
• Concise to minimize transmission overhead

Differential Oracle

Differential Oracle

• No 1:1 mapping of dumps
• But: Any JIT dump must have an interpreter equivalent in the same function invocation

Fuzzilli Modification

• Differential executions
• Communication with V8 for used compilers and dump positions
• Differential oracle

Avoiding false positives

Obvious and less obvious non-deterministic allowed behavior in V8

Math.random();
Date.now();
performance.measure("");
performance.now();
...
        

Combination of mocking in V8 and JS to mitigate

+ Reexecuting on differential found

Evaluation: Research Questions

• How sensitive is the differential oracle of Dumpling?
• What overhead does our bug oracle introduce?
• Can Dumpling discover new bugs in V8?
• How do hyperparameters influence Dumpling?
• What is the cost to maintain Dumpling?

Evaluation: Research Questions

• How sensitive is the differential oracle of Dumpling?
• What overhead does our bug oracle introduce?
• Can Dumpling discover new bugs in V8?
• How do hyperparameters influence Dumpling?
• → Only minimal influence.
• What is the cost to maintain Dumpling?
• → Matter of minutes or less to bump V8 version.

Evaluation: Sensitivity

• The frequency at which probes are inserted in JIT compiled code
• Dumpling: Deoptimization points/returns to unoptimized code.
• JIT-Picker: A visible variable is queried with a small probaility
• FuzzJIT: One probe or zero probes per JS program.
• The subset of the JS execution state that is queried per probe
• Dumpling: The execution state of the bytecode VM.
• JIT-Picker: A single JS variable per probe.
• FuzzJIT: A single return value.
• The detail at which a probed state is compared
• Dumpling: Fine grained representation of the state.
• JIT-Picker: Only primitive values are considered.
• FuzzJIT: The returned values are compared in detail.

Evaluation: Sensitivity

Evaluation: Sensitivity

Evaluation: Overhead

Bugs

Found 8 new V8 bugs 🎉

Case Study

function A() {
    Object.defineProperty(this, "x", { writable: true, configurable: true, value: undefined });
}

class B extends A {
    x = {};
}

for (let i = 0; i < 100; i++) {
    new B();
}
        
        

Here not "visible", but already detectable by Dumpling

Other fuzzers would need to add

let b = new B();
console.log(b.propertyIsEnumerable("x"));
        
        

opt output: "true", unopt output: "false"

Discussion

• Porting Dumpling to other JS Engines
• Hardware Architecture
• Upstream Dumpling Mode
• Using Dumpling with other JS Fuzzers
• Incorporating Compiler Speculations
• Using Dumpling as Dataflow Coverage Feedback

Conclusion

Key Problem

Find differentials between JS engine execution tiers automatically

Dumpling

Extract VM states during runtime and compare between JIT and interpreter

Leveraging deoptimization points, a mechanism already implemented in JS engines

Result

Find bugs before they become "visible"

Alternative Conclusion

• Kill bug classes one at a time
• Read code, understand the risky areas
• Read code, bug oracle that lives of the land
• Good engineering, instead of fancy words in a paper
• Would a V8 rewrite in Rust help? No, not a lot!
• Stop fuzzing objdump
• Fuzzer evaluation hard to do for non-standard targets

Bibliography