what fails in speculative execution that allows the read of memory out of bounds in Spectre vulnerability vs. normal CPU behaviour?

Question

Following google's Project zero blog entry for Spectre/Meltdown, there's this piece of code that exemplifies the attack:

struct array {
    unsigned long length;
    unsigned char data[];
};
struct array *arr1 = ...; /* small array */
struct array *arr2 = ...; /* array of size 0x400 */
/* >0x400 (OUT OF BOUNDS!) */
unsigned long untrusted_offset_from_caller = ...;
if (untrusted_offset_from_caller < arr1->length) {
    unsigned char value = arr1->data[untrusted_offset_from_caller];
    unsigned long index2 = ((value&1)*0x100)+0x200;
    if (index2 < arr2->length) {
        unsigned char value2 = arr2->data[index2];
    }
}

It is explained that the speculative execution followed by the CPU, will try to execute until

arr2->data[index2];

before reaching the condition

if (untrusted_offset_from_caller < arr1->length) {

that would prevent the access to a zone out memory of bounds.

My question is:

• what would have prevented access to that zone of memory in a normal execution if the code would have try to do so explicitly?

I suppose in some place the OS and/or cpu memory access checks should stop that and that the speculative exec simply jumps over that (?).

It seems that patching that (not actually made) check (if my previous guess is correct...) would not suffice or is not the correct approach, as it has already been stated that two other conditions are needed: flushing the branch predictor & take the full address of the branch instruction into account (it seems that CPUs don't do that nowadays), but:

• wouldn't the checks (if the answer to the first question is that additional checks are needed) or that 'flushing' impact in performance? and if so, has it been estimated how much? (when those supposed CPUs would/will be made).

Answer 1

Simplifying things a little, the problem is that something like

if (*p1) x = p2[256 * *p3];

may be processed as:

start loading *p1 into t1.
load *p3 into t2, and set t3 to 0 if it's a valid fetch, 1 otherwise.
load *(p2 + t2*256) into t4
wait for t1..t4 to be ready
if t1 was set, then...
  if t3 is set [access was invalid] then fire an invalid access trap.
  otherwise copy t4 into x.
discard t1..t4.

If reading *p1 yields a zero value, the fact that *p3 is invalid must not cause a trap (since code wouldn't actually ask to read *p3). For whatever reason the designers at Intel thought it was easier to delay checking the validity of the first memory read until after the fetched value was used to compute the address of another speculative read, than to have an invalid memory read immediately force the speculator to assume its prediction was wrong.

Note that the problem isn't that the processor speculatively fetches from *p3. The problem is that the processor makes use of that value without regard for whether it was legitimately acquired. While present attacks focus on using the fetched value to compute an address, and then using the cache to find out what address is fetched, the fundamental problem is that the data gets read and latched without regard for whether the access is legitimate. Any time a device physically fetches data that should be inaccessible will create a potential for side-channel attacks. The best way to prevent such attacks is to avoid having the device acquire such data in the first place.

Answer 2

The key concept is that no chip is obliged to precisely execute code according to the instructions. The obligation is instead that it must execute "as if" the code was precisely executed according to the instructions. All modern processors take advantage of this freedom.

In theory, the processor is free to execute any instruction speculatively at any time, as long as the end result is "as if" the instruction was never executed at all. This is used to increase performance, using idle parts of the chip to do speculative work, in the hopes that the effects of this instructions are needed.

In the Meltdown/Spectre bugs, it was revealed that such speculative execution is actually NOT "as if" it never happened. This speculation changed the state of the cache, loading data that might not otherwise be cached. This changes timings which Meltdown/Spectre leverage to read memory from places it was not supposed to read.

The key failure is that the chip is no longer operating "as if" it was following orders perfectly. It's marching slightly out of line. In a case like:

if (cursorIdx < cursors.size())
    y = buffer[cursors[cursorIdx]];

a programmer may expect that no memory from the buffer can be read. This is logical because the instructions written into the program demanded that the cursor array size check occur before the buffer read. As long as the chip operates "as if" it was following orders, you can prove that nobody should be able to observe a buffer read occurring before the size check. With this exploit, we see that an observer indeed can read from the buffer, and maybe even other memory outside of the bugger.

Thus, code which appeared to be safe, even against side-channel attacks, is suddenly very unsafe because it is no longer operating "as if" it was executed properly. The issue is not that the memory is being read speculatively. The processor was allowed to do that the whole time, and is still technically allowed to so. The issue is that this exploit demonstrates that such speculative reads are not "as if" they were never read, because we can observe whether they occurred. They now leak information about the memory-space which were not supposed to be leakable.

And yes, to answer your question, the fixes to this do indeed negatively impact performance. One of the reasons this exploit is such a big deal is that it is very difficult to resolve these fixes without performance impacts.

Answer 3

Starting in the late 1970s/early 1980s, CPUs started breaking down execution of instructions into a series of smaller steps, called "pipelined execution". For example, the CPU might be simultaneously reading one instruction from memory, executing a second, and storing the results from a third. Doing things this way makes for faster CPUs: by having multiple instructions in different stages of processing at the same time, a CPU can be many times faster for the same clock speed.

This runs into a problem when the instruction being executed is a branch (such as an "if" statement): which instruction is the "next" instruction that should be loaded from memory? The solution was branch prediction and speculative execution: the CPU makes an educated guess at which instruction is next, runs it, but doesn't make the results permanent until it knows if the guess was right or not. This speeds things up again, because the CPU doesn't need to wait for the results of a branch to be known unless it guesses wrong about which way the branch will go.

Modern CPUs are fast, memory access is slow, and pipelines are much longer than the simple three-stage pipe I described above. Looking at your code from a CPU's point of view while it's executing this line:

unsigned long untrusted_offset_from_caller = ...;

The CPU sees the two "if" statements coming up, and goes: "based on past experience, both these 'if' statements will turn out to be true. Therefore, I'll need to fetch arr1->data[untrusted_offset_from_caller] and arr2->data[index2] from memory."

if (untrusted_offset_from_caller < arr1->length) {
    unsigned char value = arr1->data[untrusted_offset_from_caller];
    unsigned long index2 = ((value&1)*0x100)+0x200;
    if (index2 < arr2->length) {
        unsigned char value2 = arr2->data[index2];
    }
}

It then proceeds to issue the memory requests and speculatively execute the code. Now, this time, it turns out that if (index2 < arr2->length) was false, and the CPU discards the work it did.

However, it doesn't discard all of it. Memory, registers, and the instruction pointer all show what you'd expect from the statement being false, but the preemptive fetch of arr2->data[index2] is still in the CPU's data cache. A program can figure this out by the fact that reading that part of memory is faster than normal, and can deduce what the value of arr1->data[untrusted_offset_from_caller] was.

Answer 4

"What would have prevented access to that zone of memory in a normal execution"? Nothing would have prevented it. But normally the address used would have been based on data that was legally available to the running code. So the data would be read speculatively, a cache line would be ejected, and this would tell us which byte was read, but it would be a byte that we had the right to know anyway. So nothing would have been revealed that was secret.

Here's my proposal for handling the situation given by the sample code (in hardware):

One read operation is no problem. So a simple method would be to allow only one speculative read operation. A second speculative read would have to wait until the first one is not speculative anymore.

First improvement: A speculative read that doesn't modify the cache (or leaks information in some other way) is fine. So we always allow one speculative read, and then we allow more reads as long as they don't eject a cache line (or otherwise leak information).

Second improvement: Further reads are fine as long as they don't have an address dependent on the first read. So we keep track of which registers were the result of a speculative read, and how this propagates, and allow further reads as long as the address is not based on a speculative read. This allows "if (x > 0) z = a [0] + a [1] + a [2];" to proceed.

Third improvement: We modify L1 cache so that any attempt of reading data belonging to another process will produce a cache miss. Now we know that if a read operation hits L1 cache, then we were allowed to read the data. Therefore we ignore all reads that were L1 cache hits.

Answer 5

I understand what circulosmeos is asking, this question is hanging in my mind, too: if reading unauthorized memory is not allowed in normal execution, why can it happen in speculative mode?

A logic expectation would be that it would fail in speculation, too, and make the speculative branch abort or such. Indeed the access error is registered, but only applied later if the code becomes "real".

My educated guess is that it was a choice to keep the design simpler and faster: if all effects of the speculative branch are discarded and not seen from the rest of the code, why bother to make the logic more complex than needed? Every transistor and every nanosecond count when designing such a beast.

The problem is that, due to cache, the assumptions were not exact: not all effects are reverted, and engineers failed to notice this fact, or were not aware that side-channel attacks can detect such effects, or did not realize that those effects can actually reveal memory contents if used in elaborate ways.

Answer 6

After carefully studying all the very useful replies, and to order all the info I've gathered, I make here a fast resume of the knowledge I've achieved that has served to me as a satisfactory answer.

First of all I'm very grateful to @cort-ammon comment:

"The key concept is that no chip is obliged to precisely execute code according to the instructions. The obligation is instead that it must execute "as if" the code was precisely executed according to the instructions. All modern processors take advantage of this freedom."

This concept is really necessary in order to understand why all these CPU features (as Branch Target Prediction, Speculative Execution and so on) have been implemented in the first place - and why they remain as good (and now we know: as dangerous!) as ever.

Now as for the question:

• what would have prevented access to that zone of memory in a normal execution if the code would have try to do so explicitly?

Nothing (As @immibis & @gnasher729 pointed out!): because this version of the Spectre vulnerability only allows to read data that the processor determines the process have access to.

There's no difference in the code from, for example, a read from a buffer overflow inside the same process memory space (See for example this code).

That is: the code indicated in the question is extracted from Variant 1: Bounds check bypass, in which the generic Proof of Concept (PoC) is shown. This PoC is used then in various ways: in order to use the code in Variant 1 for attacking the kernel, access to an eBPF bytecode interpreter is necessary, so that "Unprivileged userspace code can supply bytecode to the kernel". This is the characteristic (!) behaviour of eBPF ("extended Berkeley Packet Filter", a programmable feature of linux kernels) that the attack make full use of: this way the attack pass inaltered to the kernel, where it can read memory positions that it shouldn't (they'll be out of its supossed reserved memory, but in the same process space) without triggering any alarm - and it wouldn't even if the code were examined by the eBPF compiler (and it is not), because no direct out-of-bounds memory read is made at all.

But the PoC can also be used in Variant 2: Branch target injection in which that, with other tricks, force the CPU to make directed jumps in mis-speculated execution of other processes in order to gain read access to arbitrary virtual memory locations. This attack makes full use of the fact that the Branch Target Buffer (BTB) of some CPUs (at least Intel Haswell Xeon) only uses part of the full memory address to store branch prediction information. This is part of the fact that leads to the ability (attack) of one process to influence the Branch target predictor for another completely different process, thus bypassing userspace/kernel (and other) protections.

And now I understand where this partial memory address BTB fits in the answer that I pointed out to in my question, that stated that in order to protect a CPU from Spectre attacks:

"Branch predictor state must take the full address of the branch instruction into account (currently, to save space, only the low-order bits are used)." (@Mark)

As for the second question:

• wouldn't the checks (if the answer to the first question is that additional checks are needed) or that 'flushing' impact in performance? and if so, has it been estimated how much? (when those supposed CPUs would/will be made).

now that I'm aware of the internals of these attacks, and also of the internals of CPU optimizations (BTB, speculative exec...) the question seems to me less imperative: CPU designers will try to maintain the balance between performance and security... may be just that security was not in this balance before these attacks were made public (even though very promissing side-channel attacks were already known... but that's another story).

For example, as (again) @cort-ammon points:

"For example, I'm certain there's an Intel designer looking right now at whether the next generation CPUs can un-evict cache lines if a speculative read falls though to get them one step closer to "as if.""

Thanks again for all the answers.