Writing Truly Memory Safe JIT Compilers

How to kill off a top source of browser exploits

Last month the V8 team published an excellent blog post on what they call the V8 Sandbox. This isn’t a sandbox for your JavaScript code — it’s intended to mitigate browser exploits caused by bugs in the JIT compiler itself. That’s important work because they report that most Chrome exploits start with a V8 memory safety bug.

V8 is written in C++, so it may seem like these are the sort of bugs you’d expect from working in a memory-unsafe language. Unfortunately the situation is more complex. Why? The team explain:

There is a catch: V8 vulnerabilities are rarely “classic” memory corruption bugs (use-after-frees, out-of-bounds accesses, etc.) but instead subtle logic issues which can in turn be exploited to corrupt memory. As such, existing memory safety solutions are, for the most part, not applicable to V8. In particular, neither switching to a memory safe language, such as Rust, nor using current or future hardware memory safety features, such as memory tagging, can help with the security challenges faced by V8 today.

They give an example bug that can cause memory corruption without the engine itself containing any normal memory safety problems, as VM intrinsics or JIT compiled machine code itself may accidentally rely on invalid assumptions about memory.

It would be nice if there was a rigorous approach to writing language runtimes that eliminated such bugs by design.

GraalVM has a JavaScript engine called GraalJS. It’s written in Java using the Truffle language framework. Its peak performance is competitive with V8 and on a few benchmarks (such as ray tracing) is actually faster!

Although being written in Java does improve memory safety, we just saw that rewriting V8 in a safe language wouldn’t help with the types of bugs V8 is trying to solve and so we would intuitively expect that GraalJS must suffer from the same classes of bugs. Yet, it doesn’t. Let’s take a look at why not. Along the way we’ll explore the first Futamura projection, the core theoretical idea underpinning Truffle.

All fast language VMs work the same way. A program is loaded from disk into in-memory data structures representing the program, either an abstract syntax tree or byte code. The program starts running in an interpreter. Parts are soon discovered to be hot spots, i.e. the program spends much more time there than in other parts. Those hot spots are passed to a just-in-time compiler that converts them to optimized machine code, and execution then jumps back and forth between the interpreter and the collection of compiled program fragments. This gives a big performance boost.

This architecture is standard — both the JVM and V8 use it — but viewed from a security perspective the design has a flaw: it’s error prone. The language semantics are implemented twice, once for the interpreter and again for the JIT compiler. It’s critical not only that both places are fully correct but also that they exactly match. Otherwise, the VM becomes exploitable.

Truffle is a Java library that helps you build advanced, high performance language runtimes. VMs built using the Truffle framework operate in a fundamentally different way to conventional VMs, one that not only makes them much easier to write but which also eliminates memory safety bugs by design. It all starts with you writing an interpreter for your language in Java. This doesn’t mean compiling your target language to JVM bytecode — in fact bytecode won’t feature anywhere in this story. You just write an ordinary interpreter. Because the interpreter’s code is garbage collected and bounds-checked, malicious user code can’t use memory safety bugs to exploit it.

If you think about conventional Java then this may sound quite slow — isn’t Java itself interpreted until it gets JIT compiled? Are we … interpreting an interpreter? Fortunately not because you can ship your Truffle-based language runtime as a native executable, meaning it’s compiled ahead of time to fully native code using the Graal compiler (from which the wider umbrella project takes its name).

So at the start of the user’s program their JavaScript is running in a regular interpreter shipped as a normal executable binary or DLL, but which still benefits from the safety properties of a Java program. Soon some methods get hot. At this point something unconventional happens. The Truffle framework is keeping track of which functions are hot for you and will decide to schedule JIT compilations. But unlike in a conventional VM design, you don’t write your own JIT compiler. Instead your user’s code is automatically compiled by the same general-purpose Graal compiler that was used to convert your interpreter to native code, and execution will start automatically switching back and forth between the interpreter and compiled functions. This is possible thanks to an unusual technique called partial evaluation (or the first Futamura projection).

Professor Yoshihiko Futamura

You might not have encountered Futamura projections or partial evaluation before, so what is this strange sounding thing?

The core idea is to automatically transform the code of your interpreter to create individual JIT compiled user methods. Instead of needing to carefully implement the language semantics in two places (interpreter and hand-crafted JIT), it’s sufficient to implement it just once. As the interpreter is memory safe and the transform preserves interpreter semantics, the compiled version of the user’s code is guaranteed to match the interpreter’s behavior and is therefore also automatically memory safe. This makes it much harder to slip up and write an exploitable VM.

There are several tricks that make this possible. The most important is a new form of constant-ness, added to Java using annotations. In normal programming a variable is either mutable or immutable. An immutable variable is marked with a special keyword such asfinal or const and must be set only once, at the declaration site. Constants are great for compilers because they can be folded, meaning that references to them can be replaced with their value. Consider the following bit of code:

class Example {
    private static final int A = 1;
    private static final int B = 2;

    static int answer() {
        return A - B;
    }

    static String doSomething() {
        if (answer() < 0) 
            return "OK" 
        else 
            throw new IllegalStateException();
    }
}

It’s easy to see the answer() method will always return the same number. A good compiler will substitute 1 and 2 into the expression yielding return 1 — 2 and pre-compute the answer. Then it will inline any calls to answer (i.e. copy/paste the implementation into the call site), substituting those with -1 and thus removing the call overhead as well. That in turn may trigger even more constant folding, such as in the doSomething method where the compiler will prove that the exception can never be thrown and delete it entirely. Having done that, doSomething can also be optimized out by simply replacing it with “OK”, and so on.

That’s neat, but every compiler can do that … as long as the constant values are known at compile time. Truffle changes that by introducing a third kind of const-ness called compilation final. If in your interpreter implementation you declare a variable like this:

@CompilationFinal private int a = 1;

then it will change its const-ness depending on when it’s being accessed. From inside your interpreter, it’s mutable. You will use such variables to implement your interpreter. They’ll be set when you load your user’s program and maybe also whilst it runs. Once a function in the user’s script becomes hot, Truffle will work together with the Graal compiler to recompile the parts of the interpreter corresponding to the user’s code, and this time awill be treated as if it was a constant, i.e. the same as the literal value 1.

This works for any kind of data, including complex objects. Consider the following highly simplified pseudocode:

import com.oracle.truffle.api.nodes.Node;

class JavaScriptFunction extends Node {
    @CompilationFinal Node[] statements;

    Object execute() {
        for (var statement : statements) statement.execute();
    } 
}

This is the sort of class you might find in a typical abstract syntax tree interpreter. The statements array is marked compilation-final. When the program is first loaded we can initialize the array with objects representing the different things a user’s JavaScript function is doing, because it’s mutable. Now imagine that the function represented by this object gets hot. Truffle will start a special compilation of the execute() method in which Graal is told that the this pointer should be treated implicitly as compilation-final. Because the object is treated as constant, so can this.statements also be treated as constant. It’ll be substituted with the exact contents of a specific JavaScriptFunction object on the interpreter heap enabling the compiler to unroll the loop inside execute, transforming it to look like this:

Object execute() {
    this.statements[0].execute();
    this.statements[1].execute();
    this.statements[2].execute();
}

Here Node is a superclass and execute() is virtual, but that doesn’t matter. Because the list is compilation-final the individual objects in the list are also constant folded, so the execute method can be de-virtualized (resolved to whatever concrete type it really is) and then inlined as well.

And on and on we go. At the end the compiler generates a native function which matches the semantics of the user’s JavaScript (or Python or C++ or whatever language we’re implementing). Invocations of the specific JavaScriptFunction.execute() method that were compiled are diverted, so when the interpreter invokes it, there will be a transition from interpreter to native code and back. If your interpreter realizes it needs to change a @CompilationFinal field, for example because the program changes its behavior and invalidates an optimistic assumption you made, that's absolutely fine. Truffle will let you do that and "deoptimizes" the program back to the interpreter for you. Deoptimization (tech talk) is an advanced technique that's normally very hard to implement securely, as it means mapping the optimized CPU state back to the interpreter state and once again, any mistakes can be exploitable (you may be seeing a theme here). But you don’t have to write any of this. It’s all done for you by Truffle.

Why does this work?

It might not be obvious why partial evaluation actually makes things faster.

Interpreters are slow because they have to make a lot of decisions. The user’s program could do anything, so interpreters must constantly check for many possibilities to find out what the program is trying to do at that exact moment. Because branches and memory loads are difficult for the CPU to execute quickly, the whole program ends up being slow. This technique of compiling an interpreter with enhanced constant folding eliminates branches and loads. On top of this, Truffle builds an API that makes it easy to implement advanced optimizations and features for JavaScript or indeed, for any other language you have an interpreter for. For example, it offers a simple API for using assumptions — a way to JIT compile code that executes faster by not including code for handling edge cases. If such an edge case is hit then the compiled code can be thrown away and regenerated to take into account that the edge case was observed.

Recompilation

Above we briefly mentioned “recompilation”, but glossed over how that’s possible. We said the interpreter is just native code, right?

When the interpreter was compiled ahead of time with the native-image in preparation for shipping to the user’s computer, the Graal compiler recognized that it was compiling a Truffle-using program. Graal and Truffle are co-developed, so although they can be used independently, when used together they recognize each other and collaborate.

Graal changes its behavior in a couple of ways when it notices it’s compiling a Truffle language ahead-of-time. Firstly, it adds a copy of itself to the output program. Interpreter methods are then discovered by doing a static analysis of the program and then stored in the resulting executable, but with a twist: they’re stored more than once. One version is directly executable machine code. That’s your regular generic interpreter. Another is a carefully encoded form of Graal’s intermediate representation (or IR). An IR is sort of half way between the source code you write and the machine code that eventually executes (Graal’s IR is an object graph). Graal also compiles in a garbage collector, either the advanced and mature G1 collector (if you use Oracle GraalVM) or a simpler GC written in pure Java (if you use the GraalVM Community Edition).

When a user function gets hot, Truffle looks up the embedded IR for the “execute a user function” node and partially evaluates it. The evaluation is interleaved with the parsing of the graph IR to ensure that the process is as efficient as possible — if something won’t be executed because constant folding already proved it can’t be reached it won’t even be decoded or seen by the compiler. This also ensures that memory usage during the compile is kept low.

My only friend, the end

And that’s it! That’s how an entire class of subtle safety bugs is eliminated in GraalJS: because the semantics of the language are defined by the memory-safe interpreter and then partially evaluated, the generated machine code is also memory safe by construction.

What about the V8 sandbox that the original blog post is about? Expressing pointers as offsets from a heap base is a great idea that’s already used in GraalVM natively compiled binaries. However this is done for performance, as the other memory safety mechanisms mean there’s no need for mitigating heap overwrites.

None of the above is in any way specific to JavaScript, and nor are Truffle’s benefits limited to security and performance. In fact Truffle automatically adds many other features to your language, such as debugging (through Chrome Debugger’s wire protocol), language interop with both Java/Kotlin/etc and any other Truffle language, a fast regular expression engine, a fast foreign function interface, profiling tools, heap snapshotting and much more. Truffle has been used to build over 30 language VMs for dozens of languages, including languages you wouldn’t expect to have such features such as the recent Pkl configuration language from Apple.

If this article has whetted your appetite to learn more, take a look at the documentation or this tech talk on how it all works.