박성범 Simon Park

A very concrete explanation of how CPU security vulnerabilities are exploited

Reading the Meltdown and Spectre papers

KO | EN

Last May, a new security vulnerability in Intel CPUs was reported. Called MDS (Microarchitectural Data Sampling), this vulnerability differs from the Meltdown and Spectre flaws reported in early 2018 in that it can leak private data from three buffers inside the CPU: line fill buffers, load ports, and store buffers. Before studying MDS, I decided, rather belatedly, to learn about Meltdown and Spectre first.

Meltdown

Meltdown: Reading Kernel Memory from User Space.

Meltdown is a vulnerability found in Intel processors. By exploiting a weakness in out-of-order execution, an attacker can access data they cannot and should not be able to access, then recover information through a side channel such as the cache.

Background

Before getting into out-of-order execution, it helps to understand the pipeline first. Broadly speaking, a processor handles an instruction in five stages.

  1. IF (Instruction Fetch): fetches a binary instruction from memory into the CPU.
  2. ID (Instruction Decode): determines what kind of instruction it is and puts the operands into registers.
  3. EX (Execute): performs the instruction’s computation on the data.
  4. MEM (Memory): accesses memory when necessary.
  5. WB (Write Back): writes the result back into a register.

At the hardware level, the processor’s datapath looks like this:

Processor datapath diagram.

Binary data is fetched from memory into the processor, the processor figures out what kind of instruction it is, and stores values in the appropriate registers. (A very concrete explanation of how computers read code briefly covered how computers read binary data.) If the instruction is a conditional branch, the processor checks whether the value in the register is true and jumps elsewhere. If it is not a branch, the ALU (Arithmetic Logic Unit) performs the computation. Then, depending on the instruction, the processor either fetches data from memory or writes data to memory. If the instruction does not need to access memory, the result is written back to a register.

If one instruction is in the ID stage, only the registers are active, while components such as memory and the ALU sit unused. Using only part of the processor is inefficient. While one instruction is in ID, another can be in IF, and yet another in EX. The pipeline is what makes this kind of parallel execution possible, and in the figure above it is represented by four green bars. The pipeline lets instructions in different stages running in parallel share data with one another.

Because of the pipeline, a processor can execute as many as five instructions at once in a single clock cycle.

+---+------+------+------+------+------+------+------+------+------+
| 1 |  IF  |  ID  |  EX  | MEM  |  WB  |                           |
+---+------+------+------+------+------+------+------+------+------+
| 2 |      |  IF  |  ID  |  EX  | MEM  |  WB  |                    |
+---+------+------+------+------+------+------+------+------+------+
| 3 |             |  IF  |  ID  |  EX  | MEM  |  WB  |             |
+---+------+------+------+------+------+------+------+------+------+
| 4 |                    |  IF  |  ID  |  EX  | MEM  |  WB  |      |
+---+------+------+------+------+------+------+------+------+------+
| 5 |                           |  IF  |  ID  |  EX  | MEM  |  WB  |
+---+------+------+------+------+------+------+------+------+------+

In the fifth clock cycle, instruction 1 is in WB, instruction 2 in MEM, instruction 3 in EX, instruction 4 in ID, and instruction 5 in IF. That is already quite efficient, but there are cases where performance drops.

1:  lw $t0, 0($sp)
2:  lw $t1, 4($sp)
3:  and $s1, $t0, $t1
4:  add $s2, $t0, $s1
5:  addi $s3, $t0, 20

Instruction 1 loads data from memory into $t0, and instructions 3, 4, and 5 use $t0, so they all depend on instruction 1. Meanwhile, instruction 3 also depends on instruction 2, which loads data from memory into $t1.

If the processor executed instructions strictly in order, 1, 2, 3, 4, 5 would be the correct sequence. But that introduces delays while data is being loaded from memory and while results are being written back to registers.

+---+------+------+------+------+------+------+------+------+------+------+------+------+------+
| 1 |  IF  |  ID  |  EX  | MEM  |  WB  |                                                       |
+---+------+------+------+------+------+------+------+------+------+------+------+------+------+
| 2 |      |  IF  |  ID  |  EX  | MEM  |  WB  |                                                |
+---+------+------+------+------+------+------+------+------+------+------+------+------+------+
| 3 |             |  IF  |  ID  |             |  EX  | MEM  |  WB  |                           |
+---+------+------+------+------+------+------+------+------+------+------+------+------+------+
| 4 |                                  |  IF  |  ID  |             |  EX  | MEM  |  WB  |      |
+---+------+------+------+------+------+------+------+------+------+------+------+------+------+
| 5 |                                                       |  IF  |  ID  |  EX  | MEM  |  WB  |
+---+------+------+------+------+------+------+------+------+------+------+------+------+------+

Instruction 5 depends on instruction 1, but not on the other instructions. So even if the execution order changes, the same result is guaranteed.

+---+------+------+------+------+------+------+------+------+------+------+------+
| 1 |  IF  |  ID  |  EX  | MEM  |  WB  |                                         |
+---+------+------+------+------+------+------+------+------+------+------+------+
| 2 |      |  IF  |  ID  |  EX  | MEM  |  WB  |                                  |
+---+------+------+------+------+------+------+------+------+------+------+------+
| 3 |             |  IF  |  ID  |             |  EX  | MEM  |  WB  |             |
+---+------+------+------+------+------+------+------+------+------+------+------+
| 5 |                                  |  IF  |  ID  |  EX  | MEM  |  WB  |      |
+---+------+------+------+------+------+------+------+------+------+------+------+
| 4 |                                         |  IF  |  ID  |  EX  | MEM  |  WB  |
+---+------+------+------+------+------+------+------+------+------+------+------+

Running them in the order 1, 2, 3, 5, 4 saves two clock cycles. This is how the processor reorders code for performance. Executing instructions in a reordered sequence is called out-of-order execution, and Intel also uses a superscalar technique that executes instructions without dependencies in the same clock cycle. In an n-way superscalar processor, for example, the IF stage can process n instructions at the same time within a single clock cycle.

Attack overview

At heart, a Meltdown attack works by getting code that should never execute to run out of order, then inferring private information from the data left in the cache.

A toy example

Here is a simple example that shows the vulnerability in out-of-order execution:

raise_exception();
// the line below is never reached
access(probe_array[data * 4096]);

data points to an inaccessible region of memory, and 4096 is the page size. The attacker multiplies data by the 4 KB page size so that the access lands on the base address of the datath page. (A page is a unit that divides a process into multiple chunks so memory can be used efficiently.) In other words, the attacker uses the probe_array array to attempt access to a region they are not allowed to touch.

Here, raise_exception always throws, so in theory access should never run. But because of out-of-order execution, access may run before raise_exception, allowing the code to touch memory it is not permitted to access.

Once the exception is raised, the processor rolls back the instructions it executed out of order, but by then the secret byte at data * 4096 is already in the cache. So if the attacker can find that cached secret byte, they can recover the data. (For more on caches, see A very concrete explanation of how a cache works.) The attacker then walks through every page in the process and measures the time it takes to access each one.

Graph of measured page access times.

If they access the base addresses 0 * 4096, 1 * 4096, 2 * 4096, …, 255 * 4096, one page will stand out with an unusually short access time because only that page is cached. That is the datath page the attacker is looking for, and it reveals the value of data. If the target value of data were 'A', the 65th page would have the shortest access time, because 65 is the decimal ASCII value of A.

An attack that flushes the cache and then reloads it to infer information is called a Flush+Reload attack. I skipped the flushing step above, but without clearing the cache first, it would have been impossible to tell which data belonged to the target.

Attack description

The core code of the Meltdown attack can be written in x86 assembly like this:

; rcx = kernel address, rbx = probe array
xor rax, rax
retry:
mov al, byte [rcx]
shl rax, 0xc
jz retry
mov rbx, qword [rbx + rax]

The rcx register holds a kernel memory address, and rbx holds the base address of the array used to find the secret byte.

  1. First, mov al, byte [rcx] loads a value from the kernel memory address in rcx and stores it in al, the low 8-bit subregister of rax. rax is a 64-bit general-purpose register in the x86 architecture, and al is its low 8-bit subregister. rax, often called the accumulator register, is commonly used to hold the results of arithmetic operations.
  2. In user mode, kernel memory cannot be accessed, so an exception is raised and the architectural result is rolled back. Once the exception occurs, the following instructions should not execute, but because of out-of-order execution they may in fact run.
  3. If the next instruction, shl rax, 0xc, runs out of order, it shifts the value in rax left by 0xc bits. That is equivalent to multiplying it by the page size, 4096 B (4 KB).
  4. Then mov rbx, qword [rbx + rax] adds the offset in rax to the base address held in rbx and loads the value from that address into rbx. Here rbx is serving as the base register for the probe array.
  5. That means the access touches the base address of the page indexed by the secret value in rax.
  6. Because an exception occurred, all of this will eventually be rolled back. In practice, though, the access has already brought that page into the L1 cache.
  7. As in the earlier example, the attacker scans all 256 pages and measures access time. The page indexed by rax is cached, so its access time is especially short. That tells the attacker the secret value in rax.

The Meltdown vulnerability is extremely serious because it lets user mode read kernel memory without authorization. Because it arises from an out-of-order execution technique used to improve performance, mitigating it inevitably costs performance. And because it exists at the processor level, addressing the root cause also requires changes in hardware design.

Spectre

Spectre Attacks: Exploiting Speculative Execution.

Spectre is a vulnerability found in Intel, AMD, and ARM processors, and the principle behind the attack is similar to Meltdown. When a computer executes a branch, it predicts which way the condition will go and starts executing accordingly, and of course sometimes that prediction is wrong. A Spectre attack takes advantage of those failures to access memory regions that should not be accessible from outside.

Background

Predicting the outcome of a branch is called branch prediction.

for (int i = 0; i < 10; i += 1) {
  result += 1;
}

printf("%d", result);

Each time through the loop, the processor has to decide whether i < 10 is true or false, and whether to execute the body or exit the loop. In this example the same outcome repeats again and again, so if the processor had to make that decision every time, performance would inevitably suffer.

Predicting the outcome of a branch and running instructions in advance can improve performance. This is called speculative execution. A simple way to do branch prediction is a BHT (Branch History Table), which is basically the idea of predicting the future from past history. If the previous prediction was “true” and it turned out to be correct, the processor predicts “true” again and executes the instructions. If the prediction failed, it predicts “false” and skips the instructions. When a prediction fails, the instructions that were executed in advance have to be rolled back.

Attack overview

A Spectre attack can exploit failures in branch prediction. The attacker accesses data belonging to another process through side channels such as cache memory. Normally one process cannot and must not access another process’s memory space, but a weakness in branch prediction makes it possible.

The first type of Spectre attack leaks data by getting a specific block of code to execute.

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

x is an arbitrary value controlled by the attacker, and they set it to an out-of-bounds value that lies beyond the array’s memory range. As a result, array1[x] reaches into memory that is not supposed to be accessible. The code then multiplies that by the page size, 4096, in order to read from separate pages in memory. Call the value the attacker is after, array1[x], the secret byte k.

But if you access disallowed memory directly, you get a segmentation fault. So the attacker does not execute this code path directly. Instead, they rely on branch prediction.

  1. Train the processor to predict that the condition in the if statement is true. (Repeat the case where the condition is true several times.)
  2. Now make the condition false so that branch prediction fails. In the program’s visible behavior, it looks as though the instructions inside the if block were not executed. In reality, speculative execution may already have run them.
  3. Because the prediction was wrong, the processor rolls those instructions back. No value is stored in y.
  4. Even though the instructions are canceled, the data at k * 4096 that they touched remains in the cache. Here k came from outside the allowed memory range, so the process should never have been able to obtain it.
  5. The attacker cannot read that data directly, so they use the cached state instead. They touch every element of array2 in a random order and measure the access times. A particularly fast access means that data is in the cache, which reveals k * 4096, the line cached by speculative execution. This is the same technique used in the Meltdown attack.

To carry out a Spectre attack, the attacker has to find a gadget inside the target process, a code block they can use, and they also need to know how virtual addresses map to physical addresses on the victim machine in order to choose an x that points to a specific memory address. So there are many reasons the attack is difficult to pull off in practice. Even so, it is unquestionably a serious vulnerability.

References