Documentation/staging/speculation.rst

0001 ===========
0002 Speculation
0003 ===========
0004
0005 This document explains potential effects of speculation, and how undesirable
0006 effects can be mitigated portably using common APIs.
0007
0008 ------------------------------------------------------------------------------
0009
0010 To improve performance and minimize average latencies, many contemporary CPUs
0011 employ speculative execution techniques such as branch prediction, performing
0012 work which may be discarded at a later stage.
0013
0014 Typically speculative execution cannot be observed from architectural state,
0015 such as the contents of registers. However, in some cases it is possible to
0016 observe its impact on microarchitectural state, such as the presence or
0017 absence of data in caches. Such state may form side-channels which can be
0018 observed to extract secret information.
0019
0020 For example, in the presence of branch prediction, it is possible for bounds
0021 checks to be ignored by code which is speculatively executed. Consider the
0022 following code::
0023
0024         int load_array(int *array, unsigned int index)
0025         {
0026                 if (index >= MAX_ARRAY_ELEMS)
0027                         return 0;
0028                 else
0029                         return array[index];
0030         }
0031
0032 Which, on arm64, may be compiled to an assembly sequence such as::
0033
0034         CMP     <index>, #MAX_ARRAY_ELEMS
0035         B.LT    less
0036         MOV     <returnval>, #0
0037         RET
0038   less:
0039         LDR     <returnval>, [<array>, <index>]
0040         RET
0041
0042 It is possible that a CPU mis-predicts the conditional branch, and
0043 speculatively loads array[index], even if index >= MAX_ARRAY_ELEMS. This
0044 value will subsequently be discarded, but the speculated load may affect
0045 microarchitectural state which can be subsequently measured.
0046
0047 More complex sequences involving multiple dependent memory accesses may
0048 result in sensitive information being leaked. Consider the following
0049 code, building on the prior example::
0050
0051         int load_dependent_arrays(int *arr1, int *arr2, int index)
0052         {
0053                 int val1, val2,
0054
0055                 val1 = load_array(arr1, index);
0056                 val2 = load_array(arr2, val1);
0057
0058                 return val2;
0059         }
0060
0061 Under speculation, the first call to load_array() may return the value
0062 of an out-of-bounds address, while the second call will influence
0063 microarchitectural state dependent on this value. This may provide an
0064 arbitrary read primitive.
0065
0066 ====================================
0067 Mitigating speculation side-channels
0068 ====================================
0069
0070 The kernel provides a generic API to ensure that bounds checks are
0071 respected even under speculation. Architectures which are affected by
0072 speculation-based side-channels are expected to implement these
0073 primitives.
0074
0075 The array_index_nospec() helper in <linux/nospec.h> can be used to
0076 prevent information from being leaked via side-channels.
0077
0078 A call to array_index_nospec(index, size) returns a sanitized index
0079 value that is bounded to [0, size) even under cpu speculation
0080 conditions.
0081
0082 This can be used to protect the earlier load_array() example::
0083
0084         int load_array(int *array, unsigned int index)
0085         {
0086                 if (index >= MAX_ARRAY_ELEMS)
0087                         return 0;
0088                 else {
0089                         index = array_index_nospec(index, MAX_ARRAY_ELEMS);
0090                         return array[index];
0091                 }
0092         }