| 1 | ===========
|
| 2 | Speculation
|
| 3 | ===========
|
| 4 |
|
| 5 | This document explains potential effects of speculation, and how undesirable
|
| 6 | effects can be mitigated portably using common APIs.
|
| 7 |
|
| 8 | ------------------------------------------------------------------------------
|
| 9 |
|
| 10 | To improve performance and minimize average latencies, many contemporary CPUs
|
| 11 | employ speculative execution techniques such as branch prediction, performing
|
| 12 | work which may be discarded at a later stage.
|
| 13 |
|
| 14 | Typically speculative execution cannot be observed from architectural state,
|
| 15 | such as the contents of registers. However, in some cases it is possible to
|
| 16 | observe its impact on microarchitectural state, such as the presence or
|
| 17 | absence of data in caches. Such state may form side-channels which can be
|
| 18 | observed to extract secret information.
|
| 19 |
|
| 20 | For example, in the presence of branch prediction, it is possible for bounds
|
| 21 | checks to be ignored by code which is speculatively executed. Consider the
|
| 22 | following code::
|
| 23 |
|
| 24 | int load_array(int *array, unsigned int index)
|
| 25 | {
|
| 26 | if (index >= MAX_ARRAY_ELEMS)
|
| 27 | return 0;
|
| 28 | else
|
| 29 | return array[index];
|
| 30 | }
|
| 31 |
|
| 32 | Which, on arm64, may be compiled to an assembly sequence such as::
|
| 33 |
|
| 34 | CMP <index>, #MAX_ARRAY_ELEMS
|
| 35 | B.LT less
|
| 36 | MOV <returnval>, #0
|
| 37 | RET
|
| 38 | less:
|
| 39 | LDR <returnval>, [<array>, <index>]
|
| 40 | RET
|
| 41 |
|
| 42 | It is possible that a CPU mis-predicts the conditional branch, and
|
| 43 | speculatively loads array[index], even if index >= MAX_ARRAY_ELEMS. This
|
| 44 | value will subsequently be discarded, but the speculated load may affect
|
| 45 | microarchitectural state which can be subsequently measured.
|
| 46 |
|
| 47 | More complex sequences involving multiple dependent memory accesses may
|
| 48 | result in sensitive information being leaked. Consider the following
|
| 49 | code, building on the prior example::
|
| 50 |
|
| 51 | int load_dependent_arrays(int *arr1, int *arr2, int index)
|
| 52 | {
|
| 53 | int val1, val2,
|
| 54 |
|
| 55 | val1 = load_array(arr1, index);
|
| 56 | val2 = load_array(arr2, val1);
|
| 57 |
|
| 58 | return val2;
|
| 59 | }
|
| 60 |
|
| 61 | Under speculation, the first call to load_array() may return the value
|
| 62 | of an out-of-bounds address, while the second call will influence
|
| 63 | microarchitectural state dependent on this value. This may provide an
|
| 64 | arbitrary read primitive.
|
| 65 |
|
| 66 | Mitigating speculation side-channels
|
| 67 | ====================================
|
| 68 |
|
| 69 | The kernel provides a generic API to ensure that bounds checks are
|
| 70 | respected even under speculation. Architectures which are affected by
|
| 71 | speculation-based side-channels are expected to implement these
|
| 72 | primitives.
|
| 73 |
|
| 74 | The array_index_nospec() helper in <linux/nospec.h> can be used to
|
| 75 | prevent information from being leaked via side-channels.
|
| 76 |
|
| 77 | A call to array_index_nospec(index, size) returns a sanitized index
|
| 78 | value that is bounded to [0, size) even under cpu speculation
|
| 79 | conditions.
|
| 80 |
|
| 81 | This can be used to protect the earlier load_array() example::
|
| 82 |
|
| 83 | int load_array(int *array, unsigned int index)
|
| 84 | {
|
| 85 | if (index >= MAX_ARRAY_ELEMS)
|
| 86 | return 0;
|
| 87 | else {
|
| 88 | index = array_index_nospec(index, MAX_ARRAY_ELEMS);
|
| 89 | return array[index];
|
| 90 | }
|
| 91 | }
|