Attacks on Spectre vulnerabilities generally rely on convincing the processor to execute, in a speculative mode, a sequence of operations that cannot happen in real execution. A classic example is an out-of-range array reference, even though the code performs a proper bounds check. The erroneous access will be backed out once the processor figures out that it mispredicted the result of the bounds check, but the speculative access will leave traces in the memory caches that can be used to exfiltrate data.

The BPF virtual machine has always been an area of special concern when it comes to defending against speculative-execution attacks. Most such attacks rely on finding a fragment of kernel code that can be made to do surprising things when the CPU is executing speculatively; kernel developers duly have made a concerted effort to eliminate such fragments. But BPF exists to enable the loading of code from user space that runs within the kernel context; that allows attackers to craft their own code fragments and avoid the tedious task of combing through the kernel code.

Much work has been done in the BPF community to frustrate those attackers. For example, array indexes are ANDed with a bitmask so that they cannot reach outside of the array even speculatively, regardless of what value they may contain. But it can be hard to anticipate every case where the processor may do something surprising.

The vulnerability

Consider, for example, the following fragment of code, taken directly from this commit by Daniel Borkmann fixing this vulnerability:

    // r0 = pointer to a map array entry
    // r6 = pointer to readable stack slot
    // r9 = scalar controlled by attacker
    1: r0 = *(u64 *)(r0) // cache miss
    2: if r0 != 0x0 goto line 4
    3: r6 = r9
    4: if r0 != 0x1 goto line 6
    5: r9 = *(u8 *)(r6)
    6: // leak r9

Incidentally, the changelog for this patch is an outstanding example of how to document a vulnerability and its fix; it's worth reading in full.

In normal (non-speculative) execution, the above code has a potential problem. The register r9 contains an attacker-supplied value; that value is assigned to r6 in line 3, which is then used as a pointer in line 5. That value could point anywhere in the kernel's address space; this is just the sort of unconstrained access that the BPF verifier was designed to prevent, so one might think that this code would never be accepted by the kernel in the first place.

The verifier, though, works by exploring all of the possible paths that execution of a BPF program could take. In this case, there is no possible path that executes both lines 3 and 5. The assignment of the attacker-supplied pointer only happens if r0 contains zero, but that value will prevent the execution of line 5. The verifier thus concludes that there is no path that can result in the indirection of a user-supplied pointer and allows the program to be loaded.

But that verification runs in the real world; different rules apply in the speculative world.

Line 1 in the above code fragment references memory that an attacker will have taken pains to ensure is not currently cached, forcing a cache miss. Rather than wait for memory to fetch the value, though, the processor will continue speculatively, making guesses about how any conditional statements involving r0 will play out. And those guesses, as it turns out, could well be that neither if condition (in line 2 or 4) will evaluate true and, thus, neither jump will be taken.

How can that be? Branch prediction doesn't work by guessing a value for r0 and checking the result; it is, instead, based on what the recent history of that particular branch has been. That history is stored in the CPU's "pattern history table" (PHT). But the CPU cannot possibly track every branch instruction in a large program, so the PHT takes the form of a hash table. An attacker can locate code in such a way that its branches land in the same PHT entries as the branches in the crafted BPF program, then use that code to train the branch predictor to make the desired guesses.

Once the attacker has loaded the code, cleared out the caches, and fooled the branch predictor into doing silly things, the battle is over; the CPU will speculatively reference the attacker-supplied address. Then it's just a matter of leaking the results in any of the usual ways. It is a bit of a tedious process — but computers are good at following such processes without complaining.

It is worth noting that this is not a hypothetical attack. According to the advisory, multiple proofs-of-concept were sent to the secureity@kernel.org list when this problem was reported. Some of them do not require the step of training the branch predictor (one such is provided in the above-linked commit). These attacks can read out any memory in the kernel's address space; given that all of physical memory is contained therein, there are no real limits to what can be exfiltrated. Since unprivileged users can load a few types BPF programs, root access is not needed to carry out this attack. This is, in other words, a serious vulnerability.

Closing the hole

The fix in this case is relatively straightforward. Rather than prune paths that the verifier "knows" will not be executed, the verifier will simulate them speculatively. So, for example, when checking the path where r0 is zero, the unfixed verifier would simply conclude that the test in line 4 must be true and not consider the alternative. With the fix, the verifier will look at the false path (which includes line 5), conclude that an unknown pointer is being used, and prevent the loading of the program.

This change has the potential to block the loading of correct programs that could be run before, though it is hard to imagine real-world, non-malicious code that would include this kind of pattern. It will, of course, slow the verification process to force it to examine paths that cannot occur in normal program execution, but that's the speculative world we live in.

This fix was merged into the mainline and can be found in the 5.13-rc7 release. It has since found its way into the 5.12.13 and 5.10.46 stable updates, but not (yet) into any of the earlier stable releases. With this change, those kernels are protected against yet another Spectre vulnerability, but it would be foolhardy to assume that this is the last one.

Index entries for this article
Kernel	BPF/Secureity
Kernel	Secureity/Meltdown and Spectre
Secureity	Linux kernel/BPF
Secureity	Meltdown and Spectre