Exploiting Inaccurate Branch History in Side-Channel Attacks

Exploiting Inaccurate Branch History in Side-Channel Attacks

Speakers: Yuhui Zhu, Santana School of Advanced Studies

Conference: USENIX Security

YouTube: https://www.youtube.com/watch?v=Lpw64_YRyMg

Overview

In this compelling talk from USENIX Security, Yuhui Zhu of the Santana School of Advanced Studies presents a groundbreaking analysis of modern processor Branch Prediction Units (BPUs), revealing new vulnerabilities that circumvent existing Spectre mitigations. The research, titled "Exploiting Inaccurate Branch History in Side-Channel Attacks," details how subtle, often undocumented, behaviors within BPUs can be manipulated to leak sensitive information, including arbitrary kernel memory. This work builds upon the understanding of prior Spectre attacks, particularly Spectre BHI, by demonstrating that current defenses are insufficient against more sophisticated forms of branch history manipulation.

The presentation highlights a systematic analysis of resource sharing and contention within BPUs, leading to the identification of novel mechanisms for Branch History Buffer (BHP) manipulation. Zhu introduces a series of new side-channel attacks, culminating in Chimera, a real-world eBPF exploit capable of extracting kernel data. This research is critical for the security community, as it uncovers a new attack surface in widely deployed ARM and other architectures, urging a re-evaluation of how branch prediction mechanisms are secured against speculative execution attacks.

Background

▶ Watch: Introduction and key contributions (0:00)

Modern microprocessors rely heavily on branch prediction to maintain high performance. When encountering a conditional or indirect branch, the processor speculatively executes a likely path before the actual branch outcome is known. The Branch Prediction Unit (BPU) is responsible for making these predictions, often using complex data structures like the Branch History Buffer (BHP) and the Indirect Branch Target Buffer (IBTB). The BHP stores a compact representation of recent branch outcomes, which is then used to index into the IBTB to predict the target address of indirect branches.

In 2022, the Spectre BHI (Branch History Injection) attack exposed a critical vulnerability in this prediction mechanism. Spectre BHI demonstrated that an attacker could inject a malicious branch history into the BHP, causing the BPU to mispredict an indirect branch in a victim's context. This misprediction would lead to the speculative execution of a gadget chosen by the attacker, allowing sensitive data to be exfiltrated via traditional cache side channels. The core of Spectre BHI was its ability to craft a specific, malicious branch history value in the attacker's own context, which would then interfere with the indexing and tagging functions of the BPU, forcing an incorrect prediction for a subsequent victim branch.

In response to Spectre BHI, processor vendors implemented mitigations, primarily focusing on BHP sanitization and isolation at privilege switches. The idea was to clear or compartmentalize the branch history when transitioning between user and kernel space, preventing a malicious user-space history from influencing kernel-mode predictions. These measures were widely believed to effectively prevent direct attacks on kernel branch history. However, the research presented in this talk reveals that many processors possess more intricate and less understood updating logic than the canonical models suggest. This complexity, the speaker demonstrates, creates new avenues for attackers to indirectly control branch history values, thereby bypassing the existing mitigations and opening the door to a new generation of speculative execution vulnerabilities.

Key Findings

▶ Watch: Bypassing mitigations via bias-free prediction (1:55)

The research presented by Yuhui Zhu delivers several critical findings that fundamentally challenge the efficacy of current Spectre BHI mitigations. At the heart of these discoveries is a systematic analysis of resource sharing and contention within modern Branch Prediction Units (BPUs), which exposed previously unknown mechanisms for manipulating the Branch History Buffer (BHP).

The primary contributions of this work include:

1. Identification of New BHP Manipulation Mechanisms: The talk details how, despite existing mitigations, subtle and often undocumented BPU behaviors allow attackers to indirectly control branch history values. This goes beyond direct injection and leverages the complex internal state management of the BPU.
2. Novel Side-Channel Attacks: Based on these new manipulation primitives, the researchers developed a series of novel side-channel attacks. These attacks exploit specific BPU features to either infer information about victim branches or to induce malicious speculative execution.
3. Exploitable Patterns: Two distinct categories of exploitable BPU behaviors were identified across various architectures:

• Bias-free branch prediction (on ARM Cortex A72): This feature, designed to optimize BHP usage, can be abused to reset branch status and force mispredictions.
• Early BHP updates / Branch History Speculation (BHS): A more widespread behavior observed across various processors where speculated branch outcomes are used to update the BHP, creating cascading effects and confusion due to eviction.

1. Chimera – A Real-World eBPF Exploit: The culmination of these findings is Chimera, a practical eBPF-based exploit that demonstrates arbitrary kernel memory leakage. This exploit leverages the identified BPU vulnerabilities to bypass eBPF program verification and construct non-architectural speculative execution paths.
2. Bypass of Existing Mitigations: The developed attacks, including Spectre BSC and Chimera, effectively bypass existing Spectre BHI mitigations, proving that the problem of branch history injection is far from resolved.

These findings underscore a significant gap in our understanding and mitigation strategies for speculative execution vulnerabilities, particularly concerning the intricate and often proprietary implementations of branch prediction logic in modern CPUs.

Technical Deep Dive

▶ Watch: Exploiting bias-free prediction through BST eviction (3:20)

The core of Yuhui Zhu's presentation lies in the detailed exposition of two distinct, yet equally potent, categories of BPU vulnerabilities. These mechanisms allow for the indirect manipulation of branch history, bypassing established Spectre BHI mitigations.

Bias-Free Branch Prediction Exploitation (ARM Cortex A72)

The first category of vulnerability identified is related to a feature termed bias-free branch prediction, specifically observed on the ARM Cortex A72 processor. This feature aims to optimize the Branch History Buffer (BHP) by not recording "biased branches"—those that consistently behave the same way (always taken or always not taken) regardless of the execution path. While seemingly a performance optimization, it introduces a critical side channel.

The mechanism relies on an extra Branch Status Table (BST). By default, branches are classified as biased. Only when the BST records a different outcome for a branch is it reclassified as non-biased and its history becomes relevant for prediction. The exploit hinges on the ability to manipulate this BST. If an attacker can evict a branch's entry from the BST, that branch is reset to its default "biased" status. This means its footprint will no longer be recorded in the BHP, even if it's a non-biased branch.

The attack uses a specific "trampoline snippet" involving two branches: BX evict and BX prime. These two branches are crafted to share the same BST entry due to address aliasing. BX prime is part of a trampoline that allows two distinct execution paths (Flow A and Flow B), normally differentiated by BX prime's footprint in the branch history.

The key insight is:

1. When BX evict executes, it evicts BX prime's BST entry.
2. Consequently, BX prime is reclassified as biased.
3. When the trampoline is executed with Flow A, the branch history is generated without BX prime's footprint (because it's considered biased).
4. This absence of BX prime's footprint causes the BPU to confuse Flow A with Flow B, leading to a misspeculation of the wrong target.

Testing on Cortex A72 revealed that indirect branches could always trigger this eviction, while conditional branches only caused eviction when they were taken. This leads to two significant attack possibilities:

• Bcope: A novel side-channel attack where an attacker monitors whether a victim branch (BX evict) was taken. By adapting the trampoline snippet, the victim branch's outcome is converted into BI prime's speculation behavior, which can be detected using classic cache side channels. This allows for sensitive information leakage based on control flow.
• Spectre BSC (Branch Status Control): This attack directly exploits the BST manipulation to hijack branch target prediction. By controlling the presence of BST entries, attackers can manipulate BHP values to induce malicious speculation. Spectre BSC was shown to bypass some existing Spectre mitigations on Cortex A72 and leak kernel data to user space. However, aggressive BPU flushing during user-space context switches was found to mitigate these specific issues on Cortex A72.

Early BHP Updates and Branch History Speculation (BHS)

The second, more pervasive category of vulnerability concerns early BHP updates, which lead to what the researchers term Branch History Speculation (BHS). Unlike the bias-free feature, this behavior was observed across all tested processors that did not incorporate the aggressive BPU flushing found in Cortex A72.

The problem arises from how BPUs manage speculation windows and update branch history. To prevent pipeline stalls and maintain accuracy in deeply cascaded speculative execution, processors will often use speculated branch outcomes to update the BHP. This means the BHP reflects not just architecturally confirmed branches, but also branches that are still speculative. This creates two critical problems:

1. Cascading Mis-training: A single Spectre v1-like mis-training event can have a cascading effect. Because the BHP uses speculated outcomes, subsequent branch predictions can be based on a malicious context derived from an initial, non-correlated mis-speculation. This amplifies the impact of an initial prediction error.
2. BTB PHT Eviction Confusion: Some BPUs use a Path History Register (PHR) instead of a standard BHP. The PHR typically records only the addresses of taken branches. When a branch is forgotten due to BTB (Branch Target Buffer) / PHT (Pattern History Table) eviction, the BPU might assume no branch instruction existed in that memory block. Consequently, the PHR is not updated. This creates a dangerous ambiguity: the generated PHR appears identical to a scenario where a branch existed but was not taken. The BPU cannot differentiate between a branch forgotten due to eviction and a branch that was known but not taken, leading to mispeculation of future branches.

These two issues form the basis of the Spectre BHS family of attacks. While these behaviors are widespread, AMD and Intel processors were found to have additional restrictions on kernel-mode indirect branch prediction, making it impossible to hijack these specific branches from user space using these primitives directly. The specific implementations of BHP and IBTB also partially limit the exploitable attack surface.

Fallback Prediction and the Chimera Attack

Even with these limitations, a critical corner case within the BHS scheme was identified: fallback prediction. Modern BPUs, such as those employing a Taken/Not Taken (TAC) scheme, are designed to handle situations where the indirect BTB cannot provide a prediction. This occurs, for example, when a branch is architecturally resolved within the speculation window, but its outcome does not match the BPU's expectation, causing the generated BHP to not match any records in the indirect BTB. In such cases, the BPU falls back to PC-based prediction, entirely ignoring the branch history.

This fallback mechanism, intended for robustness, becomes a powerful attack vector. By shuffling the BHP, an attacker can force this fallback prediction. This effectively truncates history-based speculation, allowing the BPU to create a non-existent execution path within the speculation window that would otherwise be prevented by history-based correlation.

This insight forms the foundation of the Chimera attack, a practical exploit targeting eBPF program verification. eBPF programs are subject to a stringent verifier that analyzes all possible execution paths to ensure safety (e.g., proper data types, memory access within allocated buffers). The verifier ensures that mutually exclusive code blocks (e.g., an if/else where branches depend on conditions) cannot appear in the same architectural path.

Chimera bypasses this by constructing a speculative gadget using incompatible, architecturally mutually exclusive blocks. The attack involves:

1. Inserting a BHP shuffle branch between these mutually exclusive blocks.
2. During training, this shuffle branch is always kept not taken.
3. During the attack, a speculation window is opened at the snippet's beginning.
4. Crucially, while other branches remain in a speculative state, only the BHP shuffle branch is allowed to resolve as taken within the speculation window.
5. Since this "taken" state for the shuffle branch never occurred during training, line 10 (the subsequent branch) is forced to use PC-based fallback prediction.
6. This enables the attacker to train the subsequent line of code separately, effectively bypassing the eBPF verifier's architectural path constraints and constructing a malicious speculative gadget.

The Chimera attack successfully conducted data leakage on all tested processors except the ARM Cortex A72 (which has the aggressive BPU flushing), achieving particularly high leakage rates on the Cortex A76. This demonstrates a robust and practical exploitation of these subtle BPU behaviors for arbitrary kernel memory leakage.

Demo / Proof of Concept

▶ Watch: New attack vector: Early BHP updates (Spectre BHS) (6:00)

The most compelling proof of concept presented in the talk is the Chimera attack, which leverages the identified vulnerabilities in branch history speculation and fallback prediction to bypass the stringent security checks of the eBPF verifier and achieve arbitrary kernel memory leakage.

The eBPF framework, widely used in Linux for extending kernel functionality, relies on a sophisticated verifier to ensure the safety and integrity of user-supplied programs. This verifier analyzes all possible architectural execution paths, validating aspects like data types, memory access boundaries, and register usage. For instance, it ensures that arithmetic operations are performed only on scalar values and memory accesses are confined to allocated buffers. Crucially, the verifier guarantees that mutually exclusive code blocks, designed to handle different data types or memory regions based on conditions, can never appear within the same architectural execution path. This prevents malicious code from operating on incompatible variables or accessing unauthorized memory.

The Chimera attack exploits the fallback prediction mechanism to circumvent these architectural guarantees. The core idea is to create a speculative execution path that is non-existent architecturally but can be forced into existence through BPU manipulation.

Here’s how the Chimera attack works:

1. Gadget Construction: The attacker crafts an eBPF snippet containing two architecturally mutually exclusive blocks of code. These blocks, if executed sequentially, would violate eBPF verification rules (e.g., one block manipulates a register as a pointer, the other as a scalar, or accesses an out-of-bounds memory region).
2. BHP Shuffle Branch Insertion: Between these two mutually exclusive blocks, a specially designed BHP shuffle branch is inserted. This branch is central to forcing the fallback prediction.
3. Training Phase: During an initial training phase, the shuffle branch is consistently trained to be not taken. This establishes a specific branch history pattern where the transition between the mutually exclusive blocks, via the shuffle branch being taken, is never observed by the BPU.
4. Attack Phase:

• The attacker opens a speculation window at the beginning of the eBPF snippet.
• Other branches within this window are kept in a speculative state.
• Crucially, only the BHP shuffle branch is allowed to resolve as taken within this speculation window. This is the critical manipulation step.
• Because the BPU has no prior history of the shuffle branch being taken in this context (due to the training), the subsequent branch prediction cannot rely on history-based indexing into the Indirect Branch Target Buffer (IBTB).
• Consequently, the BPU is forced to use PC-based fallback prediction for the next branch, effectively ignoring the established branch history.

1. Speculative Gadget Execution: By forcing fallback prediction, the attacker can then separately train the subsequent code block. This allows the BPU to speculatively execute a path that combines the two architecturally mutually exclusive blocks, creating a malicious speculative gadget. This gadget can then perform operations that would typically be prevented by the eBPF verifier, such as reading arbitrary kernel memory or manipulating data types incorrectly.

The researchers successfully demonstrated data leakage using the Chimera attack on all tested processors, with the exception of the ARM Cortex A72, which incorporates aggressive BPU flushing that inadvertently mitigates this specific attack vector. Notably, high leakage rates were achieved on the ARM Cortex A76, highlighting the practical viability and severity of this exploit in real-world scenarios. This proof of concept unequivocally demonstrates that indirect branch history manipulation and forced fallback prediction can be weaponized to bypass sophisticated security mechanisms like the eBPF verifier, leading to critical information disclosure.

Defensive Implications

▶ Watch: Spectre BHS applicability and limitations (7:50)

The findings presented in "Exploiting Inaccurate Branch History in Side-Channel Attacks" have profound implications for defenders and processor architects alike. The core message is clear: existing Spectre BHI mitigations, primarily focused on BHP sanitization and isolation at privilege switches, are insufficient. The nuanced, often undocumented, behaviors of modern Branch Prediction Units (BPUs) introduce new attack surfaces that require a re-evaluation of current security paradigms.

Here are the key defensive implications:

1. Rethink Branch Prediction Isolation: Vendors must move beyond simplistic sanitization. The discovery of bias-free branch prediction exploitation on Cortex A72 and early BHP updates across various architectures demonstrates that indirect manipulation of branch history is possible. More robust and comprehensive isolation mechanisms are needed for all BPU components (BHP, BST, PHR, IBTB) across privilege boundaries and potentially even between different user-space contexts.
2. Address Undocumented BPU Behaviors: The talk highlights how "more complex updating logic than the canonical model suggests" creates vulnerabilities. Processor designers need to meticulously document and analyze these intricate behaviors, especially how speculative state interacts with architectural state and how various BPU structures (like BST and PHR) are updated and managed. Any optimization that introduces ambiguity or allows for state manipulation across security domains should be scrutinized.
3. Enhanced eBPF Verification: The Chimera attack demonstrates that even highly secure frameworks like eBPF are vulnerable to speculative execution attacks that bypass architectural verification. The eBPF verifier, and similar sandboxing mechanisms, might need to incorporate an understanding of how BPU behaviors can create non-architectural execution paths. This could involve more conservative assumptions about branch outcomes during verification or hardware-assisted guarantees against such speculative bypasses.
4. Consider Aggressive BPU Flushing: While not a perfect solution, the observation that aggressive BPU flushing during user-space context switches on Cortex A72 mitigated some of the identified issues suggests that this approach might be a viable, albeit performance-impacting, mitigation for certain scenarios. However, it's crucial to understand the performance trade-offs and ensure such flushing is comprehensive enough to cover all relevant BPU state.
5. Mitigate Cascading Speculation Errors: The issue of early BHP updates leading to cascading mis-training, where a single speculative error can propagate and influence subsequent predictions, needs to be addressed. This might require mechanisms to invalidate speculative BHP entries when an earlier misprediction is detected, or to ensure that speculative outcomes do not influence the BHP in a way that can be abused.
6. Differentiate Branch Eviction from "Not Taken": The confusion arising from BTB PHT eviction and the Path History Register (PHR)'s inability to distinguish between a forgotten branch and a known but not taken branch is a subtle but critical design flaw. BPUs should be designed to maintain clear distinctions in their internal state to prevent misinterpretation and subsequent mispeculation.
7. Software-Based Countermeasures: While hardware changes are ideal, software mitigations (e.g., LFENCE instructions, RETPOLINE-like approaches) might need to be re-evaluated and potentially extended to cover these new classes of branch history manipulation, especially in sensitive code paths.

In essence, the research mandates a shift from merely preventing direct branch history injection to understanding and securing the entire lifecycle of branch prediction state, from speculative updates to complex eviction and fallback mechanisms, across all privilege levels.

Key Takeaways

• Existing Spectre BHI mitigations are incomplete: Current defenses, primarily focusing on BHP sanitization at privilege switches, fail to address subtle, undocumented BPU behaviors that allow indirect manipulation of branch history.
• Bias-free branch prediction is exploitable: On ARM Cortex A72, the Branch Status Table (BST), used for bias-free prediction, can be manipulated via eviction to reset branch status, enabling side-channel attacks (Bcope) and branch target hijacking (Spectre BSC).
• Early BHP updates create widespread vulnerabilities: Processors using speculative branch outcomes to update the BHP can suffer from cascading mis-training and confusion from Path History Register (PHR) eviction, leading to the Spectre BHS family of attacks.
• Fallback prediction is a powerful attack vector: When the IBTB fails to provide a prediction, BPUs resort to PC-based fallback prediction. Attackers can force this by shuffling the BHP, truncating history-based speculation and creating non-architectural execution paths.
• Chimera demonstrates practical kernel memory leakage: By exploiting fallback prediction, the Chimera attack bypasses eBPF program verification, enabling the construction of speculative gadgets that leak arbitrary kernel memory on various ARM processors (e.g., Cortex A76).
• Defenders must re-evaluate BPU security: A comprehensive approach is needed, focusing on robust isolation of all BPU components, addressing undocumented behaviors, and potentially enhancing sandboxing mechanisms like eBPF verifiers to account for speculative execution paths.

About the Speaker(s)

Yuhui Zhu is a researcher from the Santana School of Advanced Studies. In this presentation, Yuhui Zhu detailed their work on uncovering and exploiting complex, often undocumented, behaviors within modern processor Branch Prediction Units to bypass existing Spectre mitigations. Their research highlights significant vulnerabilities in how branch history is managed and updated, leading to novel side-channel attacks and practical kernel memory leakage exploits.