Speculative execution

"Speculative computation" redirects here. Not to be confused with Speculative multithreading.

Speculative execution is an optimization technique where a computer system performs some task that may not be needed. Work is done before it is known whether it is actually needed, so as to prevent a delay that would have to be incurred by doing the work after it is known that it is needed. If it turns out the work was not needed after all, most changes made by the work are reverted and the results are ignored.

The objective is to provide more concurrency if extra resources are available. This approach is employed in a variety of areas, including branch prediction in pipelined processors, value prediction for exploiting value locality, prefetching memory and files, and optimistic concurrency control in database systems.

Overview

Modern pipelined microprocessors use speculative execution to reduce the cost of conditional branch instructions using schemes that predict the execution path of a program based on the history of branch executions. In order to improve performance and utilization of computer resources, instructions can be scheduled at a time when it has not yet been determined that the instructions will need to be executed, ahead of a branch.

Variants

Eager execution

See also: Eager evaluation

Eager execution is a form of speculative execution where both sides of the conditional branch are executed; however, the results are committed only if the predicate is true. With unlimited resources, eager execution (also known as oracle execution) would in theory provide the same performance as perfect branch prediction. With limited resources eager execution should be employed carefully since the number of resources needed grows exponentially with each level of branch executed eagerly.

Predictive execution

See also: Pipeline (computing)

Predictive execution is a form of speculative execution where some outcome is predicted and execution proceeds along the predicted path until the actual result is known. If the prediction is true, the predicted execution is allowed to commit, however if there is a misprediction, execution has to be unrolled and re-executed. Common forms of this include branch predictors, and memory dependence prediction. A generalized form is sometimes referred to as value prediction.

Lazy execution

Main article: Lazy evaluation

Lazy execution does not involve speculation. The incorporation of speculative execution into implementations of the Haskell programming language is a current research topic. Eager Haskell is designed around the idea of speculative execution. A 2003 PhD thesis made GHC support a kind of speculative execution with an abortion mechanism to back out in case of a bad choice called optimistic execution. It was deemed too complicated.

Security vulnerabilities

In June 2017, a team constituted of independent researchers, university research labs, and some of Google’s Project Zero members and cyberus technology discovered two security vulnerabilities enabled by the widespread use of speculative execution. The problem was also independently discovered by other researchers, at about the same time. The vulnerabilities were eventually made public in January 2018 , and were dubbed Meltdown and Spectre. They potentially allow malicious software to read otherwise protected memory on a computer system, gaining access to sensitive data such as passwords and encryption keys.

To make speculative execution as efficient as it can be, some combinations of operating system and underlying hardware let it touch data in the operating-system's private memory before it is actually needed. The vulnerabilities stem from the ability of a malicious program to then infer what this otherwise inaccessible data was, after the fact.

The more widely discussed of the two vulnerabilities, Meltdown, relies on certain hardware choices to read users' sensitive information, but can be addressed using software updates of the relevant computing platforms. Spectre, the lesser known and more difficult to apply of the two, makes it possible for a program to access data in a separate program running on the chip, and is far more difficult to fix with a single solution. While not ideal, the best general defences suggested involve detection on the one hand, and separation of running processes' cache activity from each other. The latter mitigation can carry a significant performance penalty on some architectures, and over particular workloads.

Both flaws work by performing an indexed load from memory. During this load, a first piece of data A (supposed to be off-limits) is read from memory, and then this piece of data is used to calculate the address of another piece of data B_A (accessible) to be read from memory as well. As A is off-limits, the processor ultimately cancels any direct effect of the operation on the registers and on memory once it notices that the read should not have been allowed. However, B_A is still present in the cache, and this condition can be detected by the attacker by reading B_A for all possible values of A, and observing which read operation performs noticeably faster than the others.

The difference between the flaws is the not allowed condition that is being bypassed and the means of doing so:

• In Meltdown, the attacker causes speculative execution to breach the protection boundary between a user program's memory space and a protected kernel page, by making speculative execution fetch an address into the cache. Modern Intel processors will execute such code, and then fetch and store the speculative results, leaving them in cache. Later on the exploitative code can measure what happened, either after a fault, or after preparing the original code as part of a memory transaction which will quell the fault. Some processors, such as AMD, are believed to be immune against this, as they perform the page accessibility test before executing the speculative read.
• In Spectre, the attacker does not rely on such fault mechanisms, and rather targets another user process in a more general way. Spectre relies on branch (mis)prediction to speculatively perform a fetch from an array cell, even though the preceding branch noticed that the fetch would go beyond the end of the array. It starts off by training the branch prediction machinery of the processor to make a faulty prediction, across a process boundary, and then manipulates the target process into executing part of its own code which actually touches the speculative branch. Once again, what it touched is leaked via a cache timing side channel. In this case a toy example and a JavaScript one are shown, which can be used to read the whole address space of the process manipulated to execute the relevant code.

It is thought only browsers which perform just-in-time compilation (JIT) of JavaScript are vulnerable against this way of using Spectre. However, all the modern browsers, including Chrome, Firefox, Safari and Edge employ a JIT engine. Furthermore, Spectre may also be used to leverage branch (mis)predictions in different ways, even if no scripting language is involved.

Google had originally planned a coordinated disclosure of the full Project Zero report on Tuesday January 9th, 2018, and said it had been working with both hardware and software companies to mitigate the risks over a number of months. The heightening speculation over the issue however seems to have forced an accelerated publicity schedule.

See also

• Out-of-order execution
• Slipstream (computer science)

External links

• "Speculative computation in Multilisp."