Kasper

Scanning for Generalized Transient Execution Gadgets in the Linux Kernel

TL;DR

We present Kasper, a transient (or speculative) execution gadget scanner. It uses taint analysis policies to model an attacker capable of exploiting arbitrary software/hardware vulnerabilities on a transient path. Namely, it models an attacker capable of controlling data (e.g., via memory massaging or value injection a la LVI), accessing secrets (e.g., via out-of-bounds or use-after-free accesses), and leaking these secrets (e.g., via cache-based, MDS-based, or port contention-based covert channels). As a result, Kasper discovered 1,379 previously unknown gadgets in the heavily-hardened Linux kernel. We confirm our findings by demonstrating an end-to-end proof-of-concept exploit for one of the gadgets found.

More details please!

I thought the Spectre/Meltdown/etc. thing was already fixed?
Far from it. Although certain vulnerabilities (e.g., Meltdown) can be mitigated fairly easily, this is not the case for others. In particular, Spectre-PHT (otherwise known as Spectre-V1)—which exploits the speculative execution that follows a mispredicted conditional branch—cannot be fully eradicated without crippling performance. Hence, we should only apply mitigations on a case-by-case basis to specific gadgets that can indeed be exploited by an attacker.

Spectre-PHT is so 2018! How difficult is it to find these gadgets, really?
The numbers aren’t so good. Our experiments show that because state-of-the-art gadget scanners rely on pattern-matching to approximate the presence of gadgets, they have a 99% false positive rate (i.e., almost all of the gadgets that they identify cannot actually lead to information disclosure) and up to a 33% false negative rate (i.e., they miss many vulnerable gadgets that should be protected).

Wait, I remember hearing about a bunch of other transient execution-related vulnerabilities (MDS, LVI, etc.). What about those?
Indeed, the problem goes much deeper than the traditional Spectre-PHT pattern (i.e., which exploits a cache-based covert channel), yet state-of-the-art gadget scanners stop here. However, in reality, attackers will exploit any instructions in the wake of any conditional branches, controllable by any means, which access secrets in arbitrary ways, and leak the secrets through any covert channel.

Okay, okay, I get it—this is a big problem! But how can you solve it?
We came up with a novel approach for finding vulnerable gadgets, which abstracts away all pattern-specific details and instead precisely models the essential steps of a Spectre-PHT attack. Around these steps, we use targeted taint analysis policies to generically model the effects of arbitrary hardware/software vulnerabilities on a transient path.

So what (who?) is Kasper?
Kasper is an implementation of our approach for the Linux kernel. (Not to be confused with Casper the Friendly Ghost)! It models the effects of all sorts of vulnerabilities on a transient path—i.e., memory errors, LVI, cache-based covert channels, MDS-based covert channels, and port contention-based covert channels. As a result, it finds gadgets well beyond the scope of existing approaches.

I thought the Linux kernel already has mitigations in place to protect against transient execution attacks. So did Kasper actually find any gadgets?
Yep, it found 1379 previously unknown gadgets.

Great, but are any of these gadgets actually interesting?
Although Kasper cannot guarantee that all the reported gadgets are fully exploitable, to demonstrate its usefulness, we came up with a proof-of-concept exploit for one of the gadgets that is pervasive throughout the codebase and non-trivial to mitigate.

Even more details please!!!

The key insight to our approach is that by generically modeling the vulnerabilities that an attacker can use in each step of a Spectre attack, we can precisely identify gadgets. The figure below demonstrates how the different components of our approach interact to identify a gadget in a system call handler.

An overview of Kasper.

In particular, we use: (1) speculative emulation to model transient execution, (2) vulnerability detectors to model various software and hardware vulnerabilities, (3) dynamic taint analysis to model the architectural and microarchitectural effects of such vulnerabilities, and (4) fuzzing to model the possible coverage of an attacker.

The figure below presents the workflow of Kasper, our generalized transient execution gadget scanner for the Linux kernel.


The workflow of Kasper and how we have implemented it for the Linux kernel.

First, we build the kernel with Kasper support by using a combination of runtime libraries and LLVM passes: to support dynamic taint analysis, we ported the userspace DFSan to the kernel; to support speculative emulation, we built a checkpoint-restore mechanism, which executes the mispredicted branch then reverts speculative operations at the end of the speculative window. Next, we use a modified version of syzkaller to fuzz the instrumented kernel and generate gadget reports. Finally, we aggregate gadget statistics that aid developers in applying mitigations.

Let’s see a gadget found by Kasper

To demonstrate the capabilities of Kasper, we’ll present a found gadget within the generic list iterator used all over the kernel.

Let’s take a look at the implementation of the list iterator list_for_each_entry.

In the Linux kernel the list struct is included within the struct that should form the list rather than the other way around. This allows the generic use of the list struct for any kind of list. A list always starts with a head element that is not included in an element struct and simply points to the first list element. In the iterator pos always refers to the element struct that can simply be used by the kernel developer. Since lists are circular the terminating condition is once &pos->member is equal to head. 

But on the transient path the processor might execute an additional iteration of the loop where &pos->member would be head. This will make pos an out-of-bounds pointer since unlike the list elements the head is not included within the elements struct.

Alright, but how does the gadget actually work?

A specific gadget found within the find_keyring_by_name function detected by Kasper looks like this:

Code slightly simplified for visualization reasons.

The list head is included within a struct user_namespace whereas the elements of the list are struct key elements. The memory access of keyring->user->uid in the additional loop iteration therefore uses struct user_namespace instead of a struct key.

keyring->user points to the projid_map of the user_namespace struct which Kasper knows is entirely attacker controllable. So on the transient path we can trick the processor into dereferencing an arbitrarily attacker controlled pointer.

This dereference leaves traces of the loaded value in CPU-internal buffers, which can be leaked by an attacker. We’ve done a proof-of-concept to verify such a signal is detectable from user space. Unless you disable SMT, an attacker can line up a code snippet reading data from CPU-internal buffers with the kernel unwillingly writing that secret data into the buffers on the other hyper thread.

Show me the Code

You can grab the code for Kasper at https://github.com/vusec/kasper.

Paper

Disclosure

We disclosed our findings to the Linux kernel and to Intel on February 11, 2021. We shared our paper, gadgets found, and patches for the discussed gadgets with the affected parties, who acknowledged our findings and agreed to a public disclosure date of January 25, 2022.

Frequently Asked Questions

Acknowledgements

We thank the anonymous reviewers for their valuable comments, Felix Goosens for verifying a signal on an LVI-MDS gadget, and Alexander Potapenko for developing KMSAN, which parts of KDFSAN are based on. This work was supported by the EU’s Horizon 2020 research and innovation programme under grant agreement No. 825377 (UNICORE), Intel Corporation through the Side Channel Vulnerability ISRA, the Netherlands Organisation for Scientific Research through projects “TROPICS”, “Theseus”, and “Intersect”, and EKZ through project “VeriPatch”. This paper reflects only the authors’ view. The funding agencies are not responsible for any use that may be made of the information it contains.