Since Spectre and Meltdown, the pioneers of speculative execution attacks, got famous in early 2018, the usage of the speculative vector has risen to new heights.
Defensively (new mitigation), and offensively (new vulnerabilities). Speculative execution attacks use side effects caused by incorrect CPU speculation for leaking information (info leak) from the attacked program.
V1 Spectre attacks, which take advantage of mis-speculation of branch conditional commands, are usually displayed using an example of bypassing check bounds of access to an array using speculative execution. But it turns out that many factors perceived Spectre as being restricted to bypassing check bounds only. So, the protections applied in the Linux kernel only protect arrays access.
In general, however, a v1 Spectre attack can use any kind of branch conditional mis-speculation which causes the victim to run code incorrectly.
In this article, we will review the results of our joint research, in which we researched the vulnerability of Linux to another v1 Spectre attack vector called speculative type confusion, where the mis-speculation of the conditional branch is used to make the attacked run code with variables of the wrong type and by that cause info leak.
We found that the Linux eBPF mechanism can be used to produce speculative confusion type actively; That the compiler can create such vulnerabilities as a result of innocent optimizations, and that is reflected in the inheritance mechanism in the kernel.
The original article was published in Symposium– Security USENIX august 2021.
Speculative Execution
To understand what Spectre is, we first need to understand what speculative execution is. Speculative execution is a mechanism that allows the CPU significant performance improvement.
The CPU reads commands from the RAM at a very high rate, and when it encounters a branch, it needs to calculate it to know how to proceed to the next command.
To not stop the frontend (the component in the CPU that reads commands from the RAM), and allow it constant progress, the frontend performs a prediction of the branch result and continues to call and run commands speculatively by this prediction.
After completing the calculation of the branch result, if it turns out that the prediction was wrong, the CPU will perform a rollback to commands in the wrong branch and all the commands executed after it, and then performs the correct branch and continue to read and run the commands in the correct path of the program.
We emphasize that speculation is an optimization designed to improve performance. The programmer is not exposed to these realization details at the abstract level.
The vulnerability of Spectre is that the rollback of commands executed after a false prediction is not perfect, and such commands leave behind “scratches” that can be identified, as will be seen immediately.
Array Bounds Check Bypass
In the following code:
A check is performed in order to validate that x, the offset in the array1 is valid.
If it is valid, the array is accessed, and then use the value as an index for another array.
When executing the gadget above multiple times with valid x values, the CPU “learns” that in most cases the predicate value is true.
Executing this gadget when array1_len is not in cache will open a speculation window, Where the CPU will continue to run commands speculatively based on the branch prediction. Because the CPU “learned” that most times x is valid, he will enter the branch.
Meaning, if we choose x=secret_ptr-array1, speculative access to secret will be performed – even if x is invalid. If the speculation window is “wide” enough to also use the secret value as an index for array2, this value will load into the cache and CPU.
Later, when the CPU realizes that the prediction was wrong and will make a rollback, it won’t clean up the value from the cache. In result, the speculative execution will leave scratches that can be noticed by the cache side channel.
Spectre’s original article from 2018 defined Spectre in general as any exploitation of conditional misprediction branch, when the attack described above was cited there as a concrete example of an attack. Despite this general definition, the vulnerability was only partly understood by many in the security community, like it’s limited only to bounds check bypass.
For evidence, the large number of studies and methods that offer protections against v1 Spectre attacks that were published defend from this type of attack only.
But in practice, there are code gadgets of other types than the one described above which consists of spectre vulnerability – for example; speculative type confusion, as described in the next part.
Speculative Type Confusion
The next function, written in C, uses an inheritance mechanism. The argument is a pointer to base, and the function concludes the type of “hidden” object at runtime, based on the value in the type field.
If an attacker causes an execution with a non TYPE1 object, while the first branch is trained to predict TYPE1, the gadget will leak 28 bits wide value (potentially a secret value), stored in the actually passed object.
Speculative Type Confusion in eBPF
Extended Berkeley Packet Filter is a mechanism in the Linux kernel that allows a user with low privileges to run logics as part of the kernel, for example, packet-processing or system call monitoring.
To enable this, the mechanism relies on a security model that exposes the user code to well-defined capabilities, for example, access to a restricted area in the RAM or using a limited set of functions.
The mechanism verifies this while loading the code using static verification. The verifier simulates all possible flow control in the loaded code, and makes sure that they sustain certain features and do not violate other features.
As of the time of our research, it turned out that the verifier did not simulate speculative flows and this is where the vulnerability that we found lays (and which closed after our report) In particular, we were able to load the following gadget:
Why can this code be used as a Spectre v1 gadget?
It’s a part of the eBPF code that went through verification.
In this execution flow, register r0 has a valid address for the array, register r6 has a valid address for the stack and the r9 register has an arbitrary value controlled by the attacker.
If you can train both branches, the first (A) to predict r0==0 and the second (B) to predict r0==1, The flow refers to a value controlled by the attacker as an address In the RAM, thus obtaining a gadget as we demonstrated earlier that allows for arbitrary memory reading from the address space of the kernel.
We note that there are some significant challenges left, which we solve in the article:
- Training the two branches – because they are mutual exclusive, deterministic execution of one will hurt the training of the other, and therefore must be trained in a special way.
- Dealing with the fact that the channel cover “transmits” the secret value while the kernel is running, but the attacker who wants to “receive” the value is restricted to running in space user.
Speculative Type Confusion – Non Attacker Introduced
In the previous section we showed how to artificially produce a gadget that allows speculative type confusion, but is it possible to find such without engineering them? It turns out that there is a possibility that the compiler will produce this type of gadget.
Let’s take a look at the next example:
On the left, you can see a code in C, and on the right, it’s the compilation product by GCC (version 4.8.2 with O1 flag). In this example, the variable x is controlled by the attacker.
Note that the compiler overrides the rsi register (the p argument) with the content of rdi (variable x), because it allows using the same command for foo at the end of the function.
In addition, the compiler fears that the assignment to q may change predicate (if q points to predicate), so it performs another test to predicate in the second if block.
An attacker that attacks both branches so both will predict “not taken” will be able to get the Spectre gadget as described above.
How to find such vulnerabilities ?
To find potential vulnerabilities of this kind, we performed a static analysis in a linux binary (5.4.11).
We have chosen to focus on finding such a gadget without dealing with the questions of whether and how it can be used (there are many ways for use, change setup may affect the ability to use a gadget, future change may turn a gadget usable.)
We used radare2 to perform static analysis and triton for taint tracking and symbolic execution. Radare2 is a reverse engineering tool, which allows static and dynamic analysis of code binary code. We chose to use it to load the linux kernel into the RAM and extract the call stack of the analyzed functions.
Triton allows taint analysis and symbolic execution.
It works by taking a snippet of code, “taining” a variable and executing it.
The code symbolically checks how the taint drips to other variables (from this we can conclude potential values of variables).
We analyzed syscalls, because they have a well-defined interface and the arguments can be marked as controlled by the attacker. Looking at every possible execution path
(under speculative execution, hence that any direction of branch is taken into account)
of the syscalls reading, we are looking for a command that accesses the RAM from an unsafe address (controlled by the user) in one path, and also accesses to a safe address (controlled by the kernel) in another path.
Such a combination indicates that the command is used to load from the memory in a nominal way (the kernel accesses it in a deterministic manner).
But a speculative execution can be produced in a way that the address is derived from an attacker controlled variable.
It should be noted that the analysis is incomplete (complete – finds all the relevant commands) and also not sound (sound- any command that is found can indeed be used for speculative loading from a memory address controlled by the attacker), due to computational
limitations and the ability to simulate the kernel memory and its functions.
Therefore, we performed a manual verification of the results.
Results
One of the interesting results we found, is a pattern resulting from space optimization,
as illustrated in the following code:
In this syscall, there is an optional argument (can be set to NULL) that points to the RAM in the address space of the user.
At the beginning of the function, there is a check if the user intended to use this argument (provided a value that is not NULL.) If it is NULL, pass the argument as it is (rdi register).
If it is initialized, it is copied to the kernel memory, and overrides the rdi in the value of the new pointer. For optimization, the rdi register is reused.
Training this branch not to override rdi (predict that the value is NULL) followed by an attack with a non-NULL value may cause information to leak from the kernel.
The function f will be called from an address that the attacker controls.
Let us note that the branch in question compares a value found in a register, and this makes it difficult to produce a sufficient window of speculation for the attack.
In practice, CPU behavior appears to depend on previous branches in the pipeline, and under certain conditions, you can enlarge the speculation window. More details are in the article.
As an appetizer we will include the inheritance mechanisms in the Linux kernel:
Because the kernel code is written in C, and the language does not support inheritance, linux developers introduced several mechanisms for implementing the mechanism.
The equivalent to class in C is a struct, and the inheritance is implemented in one of two ways:
- Using a pointer from the parent object to the child object, which converted to the child object depending on the context.
- Including the parent object at the beginning of the child object memory, so that a pointer to the child object is also a pointer to the object from which it is inherited.
- Using inclusion the same way as above, but in a specific offset in the child object.
The offset will be calculated by the container_of macro.
Is it possible to find speculative type confusion gadgets from derived from this implementation? Can we find two functions that implements the same interface (virtual function) for two different objects, that answers these conditions:
- The first function reading from memory and has a side channel to read it from.
The memory is read from the address stored in the object. - In an object of the second inheritance implementation (overload) the value address controlled by the attacker is in the same offset of the parent.
If we find such a pair, will it be possible to use it – to train it so that the speculative code of the first object will call for the second object?
How we used smatch (static analysis infrastructure for C) to scan the kernel code and what our findings were – in the article.
Mitigation
Unlike the array bounds check bypass, speculative type confusion does not have a well-defined structure that can be identified easily – therefore manual mitigation is impossible.
Checking the relevant compilers (gcc, llvm, msvc, icc,) all seem to produce a vulnerable gadgets as above. Except for gcc, all major compilers offer automatic mitigation flag against v1 Spectre.
In llvm, mitigation named SLH was used (speculative load hardening), which blocks usage of gadgets of this type hermetically.
msvc (Microsoft ) and icc (Intel) support full mitigation (blocking this gadget), however, they recommend using mitigation based on identifying vulnerable patterns.
This mitigation does not identify a gadget of the type described above, indicating a misunderstanding of v1 spectre.
The gcc approach is that a developer will use a barrier to prevent speculation in places where there is danger, meaning he will have to manually identify where to use his mitigation.
This approach does not make sense, because the v1 Spectre gadget can be created during compilation without the developer being aware of it.
However, this has a serious impact on performance, as can be seen in the following graph:
Summary
We showed how another vector of v1 spectre is present in the linux kernel, firstly as a result of an attack, and secondly as a compilation product, and thirdly as a result of nominal use of inheritance mechanisms in linux.
The relevant gadget does not have a well-defined structure and can be created as a result of random code changes and optimizations of the compiler.
This makes a mitigation approach that identifies vulnerable patterns or manual access impossible, and requires further research regarding a solution that will provide protection with minimal performance cost. Specifically, the existing approach in the linux kernel and possibly other systems as well needs to be examined.
About The Authors
Ofek Kirzner holds a master’s degree in computer science under the guidance of Adam Morrison, at Tel Aviv University. Today he leads the field of quantum infrastructure at Classiq, a company that deals with software for quantum computers.
Adam Morrison is a faculty member at the School of Computer Science at Tel Aviv University. His research topics are security and performance of computer systems, from the level of micro-architecture through the operating system to algorithms. His work won the Intel Hardware Security Academic Award, several Best Paper awards, and was picked as Top Picks by IEEE Micro magazine.
This writeup was originally published in digital whisper.
Comments are closed