Meltdown and Spectre, visually

Today, January 9th, was supposed to be the day. It was the coordinated disclosure date for Meltdown and Spectre, and the plan fell apart about a week early. Over the holidays people noticed a suspiciously rushed set of Linux kernel patches for something called page table isolation, The Register ran a story on the 2nd saying there was an Intel bug underneath it, and on the 3rd Google’s Project Zero went ahead and published Reading privileged memory with a side-channel, with the two academic papers going up the same day. Since then everyone has been patching, and most of the people I’ve talked to this week are patching something they couldn’t explain to you.

A little over five years ago I wrote about branch prediction and the sorted array question. That post ended with the CPU guessing which way a branch goes, and throwing the work away if it guessed wrong. Meltdown and Spectre are both about what “throwing it away” actually leaves behind. So this is the sequel, and I’ve drawn pictures again because that’s the only way I really understood it myself.

Speculation, again

A modern CPU doesn’t wait. When it hits a branch whose condition isn’t known yet, it guesses and keeps going. When an instruction is waiting on a slow memory load, it looks further down the instruction stream for work that doesn’t depend on that load and does that in the meantime. A current Intel core can have a couple of hundred instructions in flight at once, executed out of order, and then retired in the original order, which is the point where their results become official.

If the guess was wrong, or an instruction turns out to have been illegal, everything after it gets squashed before it retires. Registers go back to what they were. As far as your program can tell, nothing happened. That’s the contract, and the CPU keeps it: the architectural state is always correct.

The problem is everything that isn’t architectural state. Speculatively executed instructions still do real work in the real hardware, and the biggest piece of hardware they touch is the cache. If a squashed instruction loaded something from memory, that cache line is now sitting in L1, and nobody rolls that back. Until this week most people (me included) would have called that harmless, because what’s the cache going to tell you?

Reading the cache with a stopwatch

Quite a lot, it turns out, if you can time a memory access. A load that hits L1 takes a handful of cycles. A load that goes all the way to DRAM takes a couple of hundred. That difference is enormous and easy to measure, even with a fairly coarse timer.

So set up an array of 256 slots, one per possible byte value, each slot on its own 4 KB page.* Flush the whole array out of the cache. Then get the CPU, somehow, to touch slot number S, where S is a byte you’re not supposed to know. Afterwards, read every slot and time each read:

This trick is called Flush+Reload. Cache timing attacks like it have been around for over a decade, mostly used to pull crypto keys out of a neighboring process or VM. The new part is the “get the CPU to touch slot S” part, and that’s where speculation comes in.

Meltdown

Every mainstream OS maps the kernel’s memory into every process’s address space. The kernel pages are marked supervisor-only, so user code can’t read them, but they’re there, because it means a system call doesn’t need to switch page tables. That’s been the design forever, and for good performance reasons.

On the affected Intel chips, when user code loads from a kernel address, the permission check doesn’t block the load in time. The load does eventually fault, but only when it retires. Before that, the value has already been handed to the instructions after it, which are executing speculatively. So:

Then you catch the fault (or suppress it, there are ways), time the probe array, and you’ve read one byte of kernel memory. Repeat. The Meltdown paper reports reading kernel memory at hundreds of kilobytes per second, and on Linux the kernel maps all of physical memory, so “kernel memory” means pretty much everything on the machine, including other processes.

The fix is KPTI, kernel page table isolation, which is what those rushed Linux patches were. It’s based on KAISER, a design the Graz team behind Meltdown published last year for a different reason (hardening KASLR). While user code runs, the kernel is simply not mapped, apart from a tiny trampoline. Every system call and interrupt now switches page tables on the way in and out. On CPUs with PCID the TLB doesn’t have to be fully flushed on each switch, which helps a lot. Without it, each syscall costs you a TLB flush.

So the cost of the patch is roughly proportional to how often you cross into the kernel. Early reports range from barely measurable to 30%, and that range is mostly just a range of workloads. A game or a video encode barely enters the kernel. A database or a busy network proxy enters it constantly. Windows and macOS have their own versions of the same fix. AMD says its chips aren’t affected by Meltdown, because they do the permission check before handing the value on. Some ARM cores are.

Spectre

Meltdown is a CPU bug with a patch. Spectre is worse, because it’s closer to how speculation is supposed to work.

Instead of breaking a permission check, Spectre gets the victim to speculatively run its own code in a way that reads its own secrets, then leaves the result in the cache for you. The first variant, bounds check bypass, looks like this in the paper:

if (x < array1_size)
    y = array2[array1[x] * 4096];

That’s perfectly correct code. Now call it a few hundred times with valid values of x. The branch predictor (fancier than the two-bit counter from my 2012 post, but the same idea) learns that this check passes. Then call it with an x that’s way out of bounds, at a moment when array1_size isn’t in the cache, so the comparison takes a couple of hundred cycles to resolve. The CPU doesn’t wait. It predicts “in bounds”, reads array1[x], which is whatever byte lives at that address in the process, and loads the corresponding slot of array2. Then the comparison finally resolves, the CPU says oops and squashes all of it, and the slot of array2 is warm in the cache.

Why would an attacker be able to call code in your process with values they pick? Because that’s what a web browser is. JavaScript from any web page is attacker-supplied code running in the same process as your other tabs’ data, behind a bounds check the JIT inserted. The Spectre paper does this from JavaScript. The browsers’ immediate answer is to take away the stopwatch: Firefox 57.0.4 shipped on the 4th with performance.now() cut to 20μs precision and SharedArrayBuffer turned off (you can build a very good timer out of it), and Chrome has announced similar changes. That makes the attack slower and noisier, which buys everyone some time.

The second variant, branch target injection, goes after indirect branches: function pointers, virtual calls, the jmp [rax] kind of thing. The predictor for where an indirect branch goes is shared in ways it shouldn’t be, so an attacker can train it to send the victim’s indirect jump, speculatively, to a “gadget” of the attacker’s choosing somewhere in the victim’s own code. Project Zero used this to read host memory from inside a KVM guest, which is the one that should worry anyone on shared cloud hardware. The fixes are microcode updates that add new controls over the predictor, and a compiler trick from Google called retpoline, which replaces indirect jumps with a return-based sequence that makes the CPU speculate into a harmless little loop instead of wherever the attacker trained it to go. I think it’s one of the cleverest bits of code I’ve seen in a while.

There’s no single fix for variant 1, though. Every bounds check that guards a secret-dependent load is potentially a gadget, and the mitigations are things like putting a serializing instruction after the check or masking the index so that even a mispredicted path can’t go out of range. That’s compiler and code-review work, spread across every piece of software that runs untrusted input, and it’s going to take years.

A small aside about side channels

The last level of the Stripe CTF back in 2012 was a side channel, and I remember being delighted by it. The password server was split into chunk servers, and you couldn’t see any of its answers, but you could see the port numbers of the connections it made back to you. The gap between consecutive ports told you how many chunk servers it had talked to, which told you how many chunks of your guess were right. Its designer would have told you the system leaked nothing, and by his definition he’d have been right. The port numbers were just a fact about the machine that nobody had considered part of the interface.

Meltdown and Spectre are the same kind of thing at a much lower level, with the cache playing the part of the port numbers, and I suspect we’re going to spend a good part of this year finding out how many other bits of the chip can play it too.

What I’m patching, in order

For what it’s worth, this is my order for anything I’m responsible for: browsers first, since that’s where untrusted code runs on every machine you own; then OS patches everywhere, starting with anything that runs other people’s code (CI runners, shared hosts); then confirming with the cloud providers that their hypervisors are done, which the big ones say they mostly are; then microcode and BIOS updates as the vendors ship them, carefully, because those are the scary ones to roll out. And before patching the database boxes, take a baseline of CPU and latency so you can see what the KPTI cost actually is for you, rather than arguing about other people’s benchmarks.

* The 4096 is there so that each possible byte value lands on a different page. If the slots were adjacent, the hardware prefetcher would pull in neighbors and smear the result.