Documentation/staging/speculation.rst

   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 ====================================
  67 Mitigating speculation side-channels
  68 ====================================
  69
  70 The kernel provides a generic API to ensure that bounds checks are
  71 respected even under speculation. Architectures which are affected by
  72 speculation-based side-channels are expected to implement these
  73 primitives.
  74
  75 The array_index_nospec() helper in <linux/nospec.h> can be used to
  76 prevent information from being leaked via side-channels.
  77
  78 A call to array_index_nospec(index, size) returns a sanitized index
  79 value that is bounded to [0, size) even under cpu speculation
  80 conditions.
  81
  82 This can be used to protect the earlier load_array() example::
  83
  84         int load_array(int *array, unsigned int index)
  85         {
  86                 if (index >= MAX_ARRAY_ELEMS)
  87                         return 0;
  88                 else {
  89                         index = array_index_nospec(index, MAX_ARRAY_ELEMS);
  90                         return array[index];
  91                 }
  92         }