Pathfinder: High-Resolution Control-Flow Attacks Exploiting the Conditional Branch Predictor
ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), April 2024.

Hosein Yavarzadeh, Archit Agarwal, Max Christman, Christina Garman, Daniel Genkin, Andrew Kwong, Daniel Moghimi, Deian Stefan, Kazem Taram, Dean Tullsen

[ Paper | bibtex | Teaser | Video | Slides]

TL;DR

In our prior research, Half&Half ( Paper | Video ), we completely reverse-engineered the intricate details of the conditional branch predictor (CBP) found in modern Intel processors. This involved dissecting the prediction tables, deciphering their indexing and tagging hash functions, examining associativity, size, and delving into the contents of each entry.

Building upon this foundation, our present study, Pathfinder, unveils two innovative side-channel attacks exploiting the CBP:

The first attack introduces an entirely novel approach within the branch predictor realm, enabling the leakage of crucial historical information pertaining to thousands of recently executed branch instructions.

The second attack unveils an exceptionally high-resolution Spectre-style exploit, capable of generating intricate patterns of mispredictions to steer the victim into executing a specific code path unintended by the programmer.

We demonstrate the implications of these attacks with two case studies: We demonstrate a speculative execution attack against AES that returns intermediate values at multiple steps to recover the AES key. We also steal secret images by capturing the complete control flow of libjpeg routines.

Background: Branch Prediction in Modern Intel CPUs

In our prior research, we discovered that the CBP within Modern Intel CPUs exhibits a TAGE-like structure. This entails a local base predictor, solely indexed by the branch address (PC), alongside a series of tagged global predictors. Each global predictor is 4-way set associative and indexed and tagged using a blend of global history geometric lengths (PHR) and the branch address (PC).

Original TAGE uses the Global History Register (GHR) to capture global correlations, updating it with each conditional branch. In contrast, Intel's CBPs employ the Path History Register (PHR), updated only for taken branches of any type. The PHR update involves shifting it left by two bits and XORing a 16-bit branch footprint with the lower 16 bits of the PHR.

To know more about the structure of the CBP within Intel CPUs, please refer to our Half&Half paper.

Attack Primitives Overview

Read PHR: Reading the PHR can be extremely powerful, because it reveals not just branch outcomes, but also the branch locations and the path that led to each branch. This study represents the first instance in the literature where we reveal the extraction of the PHR value by a malicious actor, enabling the reconstruction of the entire runtime control flow of any victim program.

Extended Read PHR: This primitive extends the Read PHR primitive by allowing the attacker to read more than 194 bits of the PHR. In fact, the attacker can read the complete branch history of the victim program. This is achieved by exploiting the PHTs as a side-channel to reconstruct the PHR beyond 194 bits.

Read PHT: This primitive extracts the saturating counter value of the PHT entry indexed by (PC, PHR). This counter value is crucial for understanding the prediction state of the branch predictor.

Write PHT: This primitive sets the PHT entry accessed by (PC, PHR) to the provided attacker_controlled value (taken or not). This can be used to manipulate the prediction state of the branch predictor.

Pathfinder

Capturing the PHR is distinct from capturing the runtime control flow of a target program, as the PHR is a complex combination of multiple addresses and target bits for each taken branch. Consequently, we introduce the Pathfinder tool, which, given a PHR outcome and an executable code(containing the victim function), constructs the runtime control flow graph of the victim function.

Pathfinder uses the angr binary analysis tool and an algorithm to identify all potential control flow paths matching the observed PHR values. While it's not guaranteed that there will always be a single path leading to the specific PHR, our extensive analysis has shown that ambiguous results are exceedingly rare due to the PHR’s size and complex update function.

Attack Results

We demonstrate the implications of these attacks with two case studies:

Speculative Execution Attack Against AES: We demonstrate a speculative execution attack against AES that returns intermediate values at multiple steps to recover the AES key.

Stealing Secret Images: We steal secret images by capturing the complete control flow of libjpeg routines.

Mitigations

We propose the following mitigations to protect against the attacks outlined in this paper:

Flushing the PHR: The most straightforward software-based solution for mitigating the Read PHR is to flush the PHR using 194 unconditional direct branches during context switching between different security domains. Because unconditional direct branches do not interact with the PHTs at all, this prevents the attacker from exploiting the PHTs as a side-channel to reconstruct the PHR beyond 194.

Randomizing the PHR: Less costly, we could add a small, non-deterministic number of random branches into the PHR during context switching. This randomization of the PHR value would prevent attackers from obtaining the same PHR upon repeated calls to the victim, significantly reducing the attacker's ability to read the PHR.

Flushing the PHTs during Context Switching.

Partitioning the PHTs between Different Security Domains.

Encrypting Index/Tag Hash Functions of the PHTs.

Responsible Disclosure

We communicated the security findings outlined in the paper to both Intel and AMD in November 2023. Intel has informed other affected hardware/software vendors about the issues. Intel has shared their plans to address the concerns raised in the paper through a Security Announcement, INTEL-2024-04-26-001-Pathfinder. AMD plans to address the concerns raised in the paper through a Security Bulletin, AMD-SB-7015.

Also, we have shared our findings with the Vulnerability Information and Coordination Environment (VINCE) and they have assigned a vulnerability case, Case VU#157097: Class of Attack Primitives Enable Data Exposure on High End Intel CPUs.