Leaking Secrets through Modern Branch Predictors in the Speculative World

As end users are increasingly demanding higher performance from computer systems, processor vendors have been looking for every possible source of optimization and improvement in microarchitecture design. Modern processors heavily rely on speculation to offer high instruction level parallelism. Under speculation, the processor executes instructions based on certain predicted paths, which may potentially resolve to be the wrong executions (i.e., transient execution). As transient execution can defy program software semantics, the underlying speculation engine is carefully designed to ensure that executions of undesired instructions are squashed, and no architectural state changes are in effect for mis-speculation.

Recent advances in transient execution attacks have demonstrated the possibility of exploiting speculative execution to construct dangerous information leakage attacks. As the branch prediction unit (BPU) plays a key role in determining instructions to be fetched in the speculative path, it has been heavily exploited in these attacks to trigger mis-speculation. Particularly, in Spectre V1, the attacker can induce speculative access of unintended data through branch direction mistraining, which enables the later leakage of secrets through a microarchitecture side channel [1]. Although hardware-based side channels in the non-speculative domain are widely studied [2, 3, 4, 5, 6], transient execution attacks considerably empower these classical information leakage threats by expanding the attack surface to the speculative domain. While several system-level mitigation techniques are proposed [7, 8, 9], recent studies show that these techniques either are ineffective towards certain attack variants or rarely employed in userspace due to performance concerns [10, 5].

In this work, we demonstrate a new class of hardware-based information leakage that exploits BPU state updates within the speculative domain. Our key observation is that resolutions of conditional branch instruction in the speculative path (e.g., nested speculation) alter the states of branch pattern history—the pattern history table (PHT) in particular. More critically, these speculative updates of PHT states are not restored even after the squash of speculatively executed branches in modern processors. As branch instruction outcomes in the speculation domain can depend on data accessed in a domain beyond the programmer’s original intention, speculative branch execution can be potentially exploited to perform transient execution attacks in which the BPU is utilized as the secret transmitting hardware. We systematically explore the aforementioned security vulnerability and implement a new form of BPU side/covert channel in the speculative domain, which we term BranchSpectre. Similar to how Spectre fuels traditional cache timing channels, BranchSpectre reveals a more severe security concern for branch predictors with the attack manifestation in the speculative world as compared to prior BPU side channels [11, 12, 5]. Furthermore, BranchSpectre exhibits two unique characteristics distinctive from existing speculation-based exploits: (i) BranchSpectre completely relies on the BPU for transient execution triggering and speculation-domain secret transmission, minimizing the hardware footprint for attackers. It can bypass the bulk of existing defense techniques mostly targeting protection in the cache hierarchy [13, 14]; (ii) Different from Spectre attacks that depend on the relatively rare code gadget (e.g., memory access indirection [15]), BranchSpectre can utilize much simpler code patterns that are more commonly existing (e.g., branch whose conditional is based on a speculatively-loaded value). These enable even higher exploitability for BranchSpectre as the transient execution attack in real systems.

This article considerably extends our prior work [16] in the following aspects: i) We provide new insights about mode transitions and the PHT collision mechanism for hybrid branch predictor in commercial-off-the-shelf processors, which enable substantially higher efficiency in speculative secrets transmission. ii) We introduce a new variant of BranchSpectre side channel exploitation (i.e., BranchSpectre-v2) that chains arbitrary BranchSpectre gadgets through branch target poisoning, which further enhances the attack flexibility and capability over BranchSpectre-v1. iii) We conduct a comprehensive investigation of code patterns in commonly-used application binaries to quantify the existence of BranchSpectre gadgets and demonstrate a real-world BranchSpectre attack against OpenSSL on Intel processors. Our new findings further broaden the scope of the previous work and highlight the need for rethinking branch predictor designs that are secure in speculative executions. In summary, the key contributions are¹¹1Our PoC source is released at http://tiny.cc/hfgutz.:

• •

  We find that speculative update of PHT states in modern processors creates a new information leakage threat that can leverage branch predictors as the transmitting medium in the speculative domain.

• •

  We systematically explore the prediction mode transition in three recent generations of Intel processors and reverse-engineer the PHT collision mechanism under the history-based predictor. The discovery enables probing of the PHT state perturbations by an attacker with extremely high efficiency.

• •

  We present a novel transient execution attack framework–BranchSpectre–that enables information leakage through BPU in various forms: BranchSpectre-cc, an ultra-fast covert channel that achieves up to 1.3Mbps transmission bit rate; BranchSpectre-v1 and BranchSpectre-v2 side channels that leverage conditional branch mistraining and branch target poisoning respectively to induce speculative PHT update in nested speculation.

• •

  We perform extensive analysis on code bases of 10 popular open-source applications/libraries, which shows wider existence and stronger leakage capability of BranchSpectre gadgets in real systems. Further, our case study demonstrates a real-world BranchSpectre side channel on OpenSSL that achieves 97.3% bit accuracy.

• •

  We discuss potential speculation-secure branch predictor designs that can mitigate transient execution attacks exploiting modern branch predictors.

Similar to previously demonstrated transient execution attacks [10, 1], we assume the attacker can run a process on the same core with the victim. These two processes are running either on the same hardware context in a round-robin fashion or on individual virtual cores under simultaneous multi-threading. Since the PHT is a per-core structure, the victim’s perturbations on the PHT can potentially be observed by the attacker. The attacker process only has userspace privileges, and the pre-requisite of a malicious OS is not required. Further, we assume that the attacker has knowledge about the code/binary of the victim application and can trigger victim’s execution.

Speculative execution can be triggered by a multitude of on- and off-chip events with varying resolution window sizes. For instance, speculation induced by contention in functional units may be resolved within only a few cycles, while it can take thousands of cycles if triggered by a last-level cache (LLC) miss followed by a row-buffer conflict in memory [15]. As branches are one of the most common instructions in programs, multiple branch instructions may be encountered in the speculation path of a program. To avoid pipeline stall in the front-end, modern processors perform nested speculation where branch predictions continue to be made for branch instructions executed in the speculative path within a certain speculation window [25]. In case the earlier branch that triggers the speculation resolves and a misprediction is detected, the processor will squash all dependent instructions - including the subsequent branches that are fetched along the speculative path. Note that if a speculatively executed branch is resolved before it is squashed, the processor can potentially update the branch predictor’s states (e.g., PHT) based on its branch outcome.

The code example from Listing 1 shows why it may be beneficial to allow speculative PHT state updates. In this example, depending on the availability of bound and iterator, the inner branch (line 3) can be resolved very quickly. In contrast, the outer branch (line 1) remains unresolved for several iterations of the inner branch. In case the outer branch is predicted as not taken in the direction breaking out the loop, the inner branch may be executed for multiple iterations. Once the outer branch is resolved and the actual direction of the branch is known, the processor’s states are rolled back. If the PHT entry for the inner branch is not updated in the speculative path, the BPU would not be trained properly for predicting the loop behavior. For instance, the inner branch could be mostly $taken$ while the initial PHT state for the inner branch is in the $not\ taken$ state. In this case, the inner branch will continue to be mispredicted, leading to degraded performance if the entire speculation path turns to be useful. In contrast, if the PHT is allowed to update in the speculative path, the PHT entry will converge to $taken$ after a few iterations of the inner branch.

Based on the above discussion, we can see that updating the PHT based on nested speculation can bring potential performance benefits. However, once the dependent branch is resolved and the validity of the entire speculation is refuted, the processor needs to decide how to deal with those speculative PHT updates. In particular, the processor may choose to restore the PHT to the states before speculation started. This can annul the impact of speculation with respect to the PHT perturbations by speculative branch executions in the wrong path. However, prior academic studies have shown that recovering speculative updates of the PHT when mis-speculation is detected brings negligible performance advantage [26]. In order to figure out the PHT update mechanism in real processors, we design a microbenchmark that monitors the PHT perturbations for branch executions within mis-speculated paths. The core code snippet is shown in Listing 2 where a child branch $b_{c}$ can be speculatively executed when speculation is triggered by the parent branch $b_{p}$. The experiment performs the following steps:

We run this experiment on machines with three generations of Intel processors - Skylake, Coffee Lake and Cascade Lake. On each of the machines, we execute the aforementioned experiment 1000 times for each of the following configurations: 1) $b_{c}$ in step ➋ not taken, and $b_{c}$ in step ➌ taken; 2) $b_{c}$ in both step ➋ and ➌ are taken. Note that this can be easily setup by controlling the value of $control$. In Figure 3, we show the latency distributions for executing the code block line 4-5 in step ➌. As we can clearly see, the execution time of the $b_{c}$ in step ➌ is consistently shorter (i.e., correct prediction) if the outcome of branch $b_{c}$ is the same as the speculatively resolved outcome of that branch in ➋. In contrast, when the outcome of $b_{c}$ in step ➌ is different from step ➋, we observe longer execution time indicating a misprediction has occurred. These results evidently show that conditional branches resolved in transient execution do influence the branch prediction later on even after they are squashed. Based on the investigation results, we make the key observation that conditional branches executed on speculative path changes the PHT state when the branch outcome is resolved, and these alterations are not restored regardless of whether the branch is eventually committed or not. Moreover, such an observation is consistent across all processors we have evaluated. We note that the microarchitectural footprint in the BPU due to speculation can create a new avenue for transient execution attacks, essentially making it possible to exploit the BPU as the secret transmitting medium in the speculative domain. To the best of our knowledge, we are the first to investigate the exploitation of the PHT state changes in branch predictors for speculative branches in transient execution attacks. Note that while we mainly explore the speculation behavior of BPUs in Intel processors, our observation could also be applicable to chips from other vendors. Particularly, any processor that allows speculative updates of the PHT can be vulnerable to this exploitation.

In this section, we show the overview of the BranchSpectre attack design which performs information leakage by inferring secrets from BPU state updates in transient execution.

As discussed in Section 5, for a PHT entry with an $n$-bit saturating counter with $2^{n}$ possible values, there are 1 Strongly Taken state, $2^{n-1}-1$ Weakly Taken states, $2^{n-1}-1$ Weakly Not-taken state and 1 Strongly Not-taken state. Once a PHT collision is achieved, the attacker can infer secrets by observing the sequence of prediction outcomes made for a colliding branch. Specifically, to infer the outcome of a victim branch $b_{v}$ when executed speculatively, we first use a colliding branch $b_{a}$ from the attacker’s address space²²2Note that from this point, executing a target branch in the history-based predictor will implicitly mean that GHR is properly preset to ensure collision. to initialize the target PHT entry to a strong state. The attacker then triggers the execution of a victim’s branch $b_{v}$ speculatively. Finally, we execute $b_{a}$ again to infer the state of the PHT that has already been perturbed by the victim. If the outcome of $b_{v}$ is dependent on a secretive value (i.e., unintended secret), the attacker can reveal that value after the mis-speculation is corrected. Figure 7 shows a high-level implementation of the attack. Note that while we use side channel terminologies in this description, the same techniques can also be applied to covert channels. We now discuss how the attackers achieve each of these steps:

1. Step 1:

   PHT initialization for victim’s branch. The attacker has two goals in this stage. First, the attacker trains the PHT entry of the victim’s branch ($PHT_{t}$) so that it is pushed to a deterministic state (e.g., either ST or SN). For $n$-bit counters, this can be achieved by executing a branch $b_{a}$ in the attacker’s address space that is congruent to $b_{v}$ for $2^{n}-1$ times with the taken (or not taken) outcome. This means executions of $b_{a}$ $3$ and $7$ times for one-level and history-based predictor respectively. Second, the attack either mistrains the branch direction prediction (in case of a conditional branch) or poisons the target address (in case of an indirect jump) of the parent instruction $b_{v0}$ in the victim’s process. This will trigger transient execution of $b_{v0}$ in the path with the $b_{v}$ instruction. Finally, the attacker triggers the victim process execution and waits until $b_{v}$ is executed speculatively.

2. Step 2:

   Victim execution in speculative path. When the victim runs, branch $b_{v}$ will be first speculatively executed and later squashed. The attacker can control the speculation window for $b_{v0}$ to make the speculation sufficiently long so that $b_{v}$ is resolved first in the speculative path. $b_{v}$’s speculative resolution will alter the state of $PHT_{t}$ depending on certain conditionals (likely unintended data). Essentially, after victim’s execution, $PHT_{t}$ is tainted with the out-of-bound value.

3. Step 3:

   Infer secret by probing $\mathbf{PHT_{t}}$ state. In this step, the attacker aims to infer the secret value in the victim’s address space by probing the state of $PHT_{t}$. To do so, the attacker executes the branch $b_{a}$ that is congruent to $b_{v}$ with outcome in the opposite direction from Step 1. To observe the difference, the attacker executes $b_{a}$ for $2^{n-1}$ times and record the execution latency of $b_{a}$ execution.

Figure 8 demonstrates the generalized state transition of $PHT_{t}$ for $n$-bit counters after the attacker presets $PHT_{t}$ state to taken in Step 1. We can see that the value of $secret$ is directly correlated with the prediction of the $2^{n-1}th$ inference operation in Step 3. Particularly, if $b_{v}$ is resolved as not taken speculatively, the $2^{n-1}th$ branch of the attacker will be correctly predicted, otherwise, a misprediction would occur. The attacker can then infer the secret used as $b_{v}$’s conditional based on timing as shown in Figure 3. Similar PHT state diagrams can be generated for branches with not taken outcomes in Step 1 and taken outcomes in Step 3.

To demonstrate the information leakage threat with speculative PHT update, we investigate a covert channel where a trojan and a spy exploit transient branch execution to build a covert communication. We call it BranchSpectre-cc. Different from previous covert channel attacks in the non-speculative domain [12, 11, 5], covert channels using speculation can be more stealthy and remain undetected even with the presence of dynamic software analysis techniques [30].

To construct the BranchSpectre-cc attack, the spy first executes Step 1 from Section 6 and then waits for the trojan’s execution (Step 2) before inferring the secret in Step 3. The code gadget for trojan’s exploitation can be any value-dependent conditional branch executed in the speculative path. After activating certain branch prediction mode, the attacker needs to follow this sequence of actions: Spy initialization–preset the $PHT_{t}$ to the deterministic state by executing $b_{a}$ $\rightarrow$ Trojan training–execute the $b_{v}$ speculatively with conditional depending on sensitive data $\rightarrow$ Spy inference–infer the state of $PHT_{t}$ after trojan’s execution. Since the trojan and spy are colluding, a PHT collision between them can be achieved by simply using branches (both $b_{a}$ and $b_{v}$) with the same address (for one-level prediction) or by executing the same set of 12 taken branches to preset the GHR state before the execution of $b_{a}$ and $b_{v}$ (for history-based prediction). Figure 9 shows the communication protocol of the covert channel and illustrates how the trojan transmits bits ’010’. Figure 10 illustrates the latency traces observed by the spy corresponding to the $2^{n-1}$th execution in the inference phase for a snippet of 50-bit transmission. The spy observes a clear pattern differentiating bit ’0’ and bit ’1’.

There are several ways the transmission rate of the covert channel can be improved. A common optimization technique is to reuse the operation in the inference phase for one-bit transmission as initialization operation for the next bit. Specifically, we increase the number of branch executions in the inference phase to $2^{n}-1$. This way, at the end of the inference, the target PHT entry is already set to a strong state (the purpose of the initialization step for the next bit reception). Note that the spy infers the secret by observing the prediction from $2^{n-1}$th inference branch. We can thus improve the bit rate by removing spy’s initialization through alternating the PHT entry of $b_{a}$ between $ST$ and $SN$. We also perform speed-enhancing techniques particular to certain prediction mode. For instance, under one-level prediction, we can increase the bit rate by tuning bits transmitted between re-enforcements of the one-level predictor.

Figure 11 illustrates the raw transmission rate of BranchSpectre-cc and the corresponding error rate under each prediction mode. Specifically, with one-level predictor, it is observed the dominant bit rate improvement is due to coalescing multiple bits transmission for one randomization operation. The attacker can achieve a peak transmission rate of 131Kbps within 5% bit error rate (shown in Figure 11a). We find that further increasing bit rate will lead to considerable drop in bit accuracy due to transfer of the prediction mode. On the other hand, Figure 11b shows that under history-based prediction, the adversary can achieve up to 1.3Mbps with less than 4% bit error ratio, which is an order of magnitude faster than the one in one-level prediction mode. We note that BranchSpectre-cc with history-based predictor is considerably more efficient since it eliminates expensive additional operations for keeping the one-level predictor active. Compared to the existing BPU-based covert channel leveraging coarse-grained pattern history manipulations [11], BranchSpectre-cc exhibits much higher transmission rate due to precise control of collision on a single PHT entry in history-based prediction mode.

In this section, we demonstrate BranchSpectre side channels that enable inferring speculation-domain secrets from a victim process through branch predictor exploitation. To leverage this vulnerability, the attacker needs to find appropriate gadgets in the victim application. Particularly, BranchSpectre depends on the presence of two types of gadgets in the victim application: a trigger gadget to start mis-speculation and a transmitter gadget that perturbs a target PHT entry with the information of speculative secret.

Our proposed attack can manifest in ways similar to either Spectre V1 or V2, and we call our attacks BranchSpectre-v1 and BranchSpectre-v2 respectively. The BranchSpectre-v1 attack leverages a conditional branch to induce mis-speculation. Its speculative execution path that traverses the trigger gadget and transmitter gadget follows through the static control flow graph of the victim program. Differently, BranchSpectre-v2 harnesses branch target positioning as the triggering mechanism. The exploited path is driven by chaining the attack gadgets at potentially arbitrary locations. As a result, the speculative path in BranchSpectre-v2 is not constrained by the victim’s static control flow. Since the execution path in v2-type attack can manipulate instruction sequences throughout the entire address space, it provides the adversaries with higher attack flexibility as well as code gadget availability.