Spectre
Despite the cute logo, Spectre is a serious security vulnerability that affects most CPUs, including Intel and AMD. The vulnerability arises from the interactions between two common CPU features: speculative execution and data caching. A malicious program can exploit the vulnerability to read data it normally does not have access to, including the memory of other programs and even the operating system. For example, one tab in your browser could exploit Spectre to read the data on other tabs you have open, and thereby access sensitive information like your emails or your bank info. Furthermore, the recent trend towards cloud computing also introduces many risks. Cloud providers typically run many applications on the same server. Even if you trust the website safe.com, their database could be running on the same server as a program owned by attacker.com. Virtualization theoretically prevents attacker.com's program from reading safe.com's database, but a malicious program can exploit the Spectre vulnerability to circumvent that barrier. Spectre is quite difficult to exploit and there have been no known attacks in the wild, but the idea that your data could be accessed by any program running on the same computer is a bit frightening!
In this blog post, I hope to explain what speculative execution and data caching are, describe how they give rise to the Spectre vulnerability, and provide a proof-of-concept of Spectre variant 2. To understand the main ideas of the vulnerability, you should not need much prior knowledge about computer architecture, but it would be helpful to have some programming experience.
Speculative Execution
At a high level, the job of the CPU is to execute instructions. There are a couple different types of instructions, including arithmetic, memory, and control flow:
- Arithmetic operations manipulate data in the CPU's registers, and can be performed very quickly (~1ns).
- Memory operations (i.e. reads and writes to RAM) take much longer (~100ns).
- Typically the CPU will execute instructions sequentially, but control flow operations can make the CPU jump to a different instruction. The instruction to jump to can be specified directly as an address or indirectly using a register that contains the address.
A conditional branch is a type of control flow operation that only changes the control flow if a provided condition is true. If false, the CPU continues executing the next instruction in sequential order as normal. A conditional branch introduces two code paths, each representing a sequence of instructions that the CPU could execute, corresponding to whether the branch is taken or not.
When the CPU encounters a conditional branch, it might take a while before it knows which of the two paths to take. For example, the result of the conditional expression could depend on a value in memory, which takes a long time to read. The CPU could stall (do nothing) as it waits for the result to become available, but this would waste a lot of CPU cycles. Instead, many processors guess whether the branch is taken or not, and continue executing the code path based on this speculated value. This optimization is known as speculative execution. If the guess turns out to be incorrect, then the processor must revert all of the speculatively executed instructions and switch to the correct code path. In most cases, the CPUs branch predictor is very good at predicting the outcome of conditional branches (>95% accuracy), so the benefits of correct guesses far outweigh the costs of incorrect ones.
Typically, the branch predictor will look at the recent history of a branch to predict whether or not it will be taken. If a branch has been taken a majority of the time, it is likely it will be taken again. Thus, a branch predictor makes decisions the opposite of how Robert Frost would:
"Two paths diverged in a branch, and I—
I took the one more traveled by,
And that has made all the difference."
Data Caching
As mentioned in the previous section, reading and writing data in main memory (RAM) has high latency. Computer architects thus incorporate levels of caches between the CPU and RAM to speed up memory operations. A cache is a piece of memory that is faster to access but smaller in capacity than main memory. According to this gist, data on the closest cache can be accessed two orders of magnitude faster than data on main memory. Caches typically try to hold data that is most frequently accessed by the CPU, in order to provide the most performance benefit.
Spectre
(The name of the vulnerability comes from "speculative execution." Also, that's why the ghost is holding a branch in the logo.)
From a security perspective, speculative execution should seem worrisome, because the CPU is executing instructions that it is not supposed to. CPU designers have taken great care to ensure that mis-speculated instructions are rolled back correctly. In other words, the effects of instructions that are executed as a result of incorrect speculation should not be observable. This is to guarantee that speculative execution does not affect the correctness of a program.
While mis-speculated instructions are guaranteed to not affect the state of the system, such as the contents of memory, they can affect micro-architectural state, such as the contents of the caches. Specifically, speculative reads bring data from main memory into the cache, even if the read is later rolled back. At first glance, this should not be an issue, because the presence of the data in the cache only affects the latency of future accesses to that data, but not the value of the data.
However, the amount of time it takes to read a memory location is observable. Furthermore, whether or not some data is cached can be used to infer information about speculatively executed instructions. This is the backbone of the Spectre vulnerability: an attacker can exploit speculative execution to run unpermitted instructions, and then can use cache timing info as a side channel to infer the effects of those instructions.
Let's look at a toy example of how Spectre could be used to read secret data:
char *data = "safe string"; // length is 11
char *secret = "my password";
void function(int index, bool channel[256]) {
if (index < 11) {
channel[data[index]] = true;
}
}
Suppose a victim exposes this function to the public. The user provides an index and a boolean array. If the index is within the bounds of the string data, then that character will be written to channel. For example, if index=0, then data[83] will be set to true because the ascii code of 's' is 83.
Ordinarily, it would be impossible to discover the contents of the string secret using this function, because the code checks to make sure that index is within the bounds of data on line 4. However, an attacker can read the secret using Spectre:
- The attacker calls the function several times with a value of
indexless than 11, so it will pass the bounds check. - The attacker calls the function with
index=11. The branch predictor will predict that the condition on line 4 is true based on recent history, so the CPU will start executing line 5, though it will realize its mistake at some point. - Once the function returns, the attacker can scan the elements of
channelto determine which element is cached. The index of the cached element will bedata[11] = secret[0]. - By repeating this approach, the attacker will be able to read the entire secret!
Note that this is a very contrived example. In real life, the attack is very hard to pull off for a number of reasons. The attacker needs to locate a callable function in the victim that does something similar to the one listed above. The attacker must also poison the branch predictor successfully, which is non-trivial because modern branch predictors are very complicated.
Spectre Variant 2 Proof of Concept
There are many variants of the Spectre vulnerability. Appendix C of the Spectre paper is a program that demonstrates variant 1 of the Spectre vulnerability. Variant 1 poisons the branch predictor, which predicts whether a branch is taken or not, while variant 2 poisons the branch target predictor, which predicts the destination of an indirect branch.
I wrote a very similar program that demonstrates variant 2, you can check it out at this Github repo.
References
The Spectre website has good introductory information. The research paper and Google Project Zero blog describe the vulnerability in much more technical detail.