Surprise: A Small Change Leads to Big Results for Computer Security

Modern computer software makes heavy use of branches.  A conditional branch instruction is used every time the next instructions you want to execute depend on the value of some data. It is common that 10 to 20 percent of all instructions executed are conditional branches.  Modern processors include a branch predictor in the front end of the pipeline to predict the outcome of these conditional branches, allowing the processor to continue to execute at full speed without stalling until the outcome of the branch is known, much later in the pipeline.

In all modern processors, though, the branch predictor is shared between all executing threads and processes, leading to critical security vulnerabilities.  These can be used by an attacker to observe the outcome of any branch in a targeted program—and learn about the data that controls the branch.  Even worse, certain Spectre attacks start with the attacker inserting data into the branch predictor so that they can learn private information that is stored in their memory.

Despite the fact that no prior work had fully deciphered these predictors, even those introduced more than 12 years ago, the researchers were able to fully reverse engineer the structure, sizes, and lookup functions of these predictors.  The Intel branch predictor is made up of four tables, and the hash functions used to look up the predictions are composed from an enormous amount of data, using information gleaned from the last (up to) 194 taken branches.  As a result, these lookup functions are extremely complex, making the most surprising result of this analysis the discovery that the branch predictor can be split into two parts simply by varying a single bit of the branch address.

“With a small change in how we generate code we can now run two threads together on the same processor core, and it is impossible to leak data through the branch predictor, or to induce mispredicts to launch a Spectre attack,” said Hosein Yavarzadeh, a UC San Diego Computer Science and Engineering (CSE) PhD student and lead author of the paper.

“This result was actually quite a surprise, in part because the indexing functions for these tables are so complex, and it seemed astronomically unlikely that a single bit would be isolated in such a way that it is not combined with any other bits” said CSE Professor Dean Tullsen.  “We would have been excited to find out that Intel planned to do something like this intentionally for future processors.  It was shocking to find out that this feature is already in every major processor from Intel going back 10-plus years, with no-one knowing about it, or for the very few that did, not realizing the implications for security.”

Purdue University professor and CSE alumnus Kazem Taram said that the conditional branch predictor is arguably the most challenging component of the branch predictor to reverse-engineer, and so the details of it have been a mystery for both security and performance researchers. “With Half&Half, now we have a clearer picture of the functionality and detailed structure of branch predictors that were kept secret for decades,” he said.

CSE postdoctoral researcher and alumnus Shravan Narayan, who will soon be a professor at the University of Texas, and CSE Associate Professor Deian Stefan also contributed to this research.

Previously, the best-known software techniques for providing conditional branch isolation between threads incurred 50 to 100 percent performance overhead.  With the Half&Half approach, the same protection against security leakage through the branch predictor can be achieved with a simple change to compiler code generation that costs 2 to 5 percent performance.