About Kernel Documentation Linux Kernel Contact Linux Resources Linux Blog

Documentation / speculation.txt




Custom Search

Based on kernel version 4.16.1. Page generated on 2018-04-09 11:53 EST.

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

Information is copyright its respective author. All material is available from the Linux Kernel Source distributed under a GPL License. This page is provided as a free service by mjmwired.net.