추측 실행과 side-channel 완화

추측 실행과 관찰 가능한 흔적

이 문서는 추측 실행이 만들 수 있는 영향과 공통 API를 이용해 바람직하지 않은 영향을 이식성 있게 완화하는 방법을 설명한다.

현대 CPU는 평균 latency를 줄이고 성능을 높이기 위해 branch prediction 같은 speculative execution 기법을 사용한다. CPU는 나중에 폐기될 수도 있는 작업을 미리 수행한다.

추측 실행 결과는 보통 register 내용 같은 architectural state에서는 관찰되지 않는다. 그러나 cache에 data가 있거나 없는 상태처럼 microarchitectural state에 남은 영향은 관찰될 수 있다. 이런 상태는 secret 정보를 추출할 수 있는 side-channel이 될 수 있다.

===========
Speculation
===========

This document explains potential effects of speculation, and how undesirable
effects can be mitigated portably using common APIs.

------------------------------------------------------------------------------

To improve performance and minimize average latencies, many contemporary CPUs
employ speculative execution techniques such as branch prediction, performing
work which may be discarded at a later stage.

Typically speculative execution cannot be observed from architectural state,
such as the contents of registers. However, in some cases it is possible to
observe its impact on microarchitectural state, such as the presence or
absence of data in caches. Such state may form side-channels which can be
observed to extract secret information.

경계 검사 우회의 예

branch prediction이 존재하면 추측 실행되는 code가 bounds check를 통과한 것처럼 실행될 수 있다. 예제 `load_array()`는 정상 실행에서는 `index >= MAX_ARRAY_ELEMS`이면 0을 반환하고 그렇지 않을 때만 `array[index]`를 읽는다.

arm64 assembly 예에서는 `CMP`로 index를 상한과 비교하고 `B.LT`로 `less` label에 분기한다. 범위를 벗어나면 0을 반환하며, 범위 안이면 `LDR`로 배열 원소를 읽는다.

CPU가 conditional branch를 잘못 예측하면 `index >= MAX_ARRAY_ELEMS`인 경우에도 `array[index]`를 추측적으로 load할 수 있다. 이 값은 이후 폐기되지만 load가 바꾼 cache 등의 microarchitectural state는 나중에 측정할 수 있다.

For example, in the presence of branch prediction, it is possible for bounds
checks to be ignored by code which is speculatively executed. Consider the
following code::

	int load_array(int *array, unsigned int index)
	{
		if (index >= MAX_ARRAY_ELEMS)
			return 0;
		else
			return array[index];
	}

Which, on arm64, may be compiled to an assembly sequence such as::

	CMP	<index>, #MAX_ARRAY_ELEMS
	B.LT	less
	MOV	<returnval>, #0
	RET
  less:
	LDR	<returnval>, [<array>, <index>]
	RET

It is possible that a CPU mis-predicts the conditional branch, and
speculatively loads array[index], even if index >= MAX_ARRAY_ELEMS. This
value will subsequently be discarded, but the speculated load may affect
microarchitectural state which can be subsequently measured.

의존 memory access와 임의 읽기 primitive

서로 의존하는 memory access가 여러 단계로 이어지면 민감한 정보가 유출될 수 있다. `load_dependent_arrays()`는 먼저 `load_array(arr1, index)`로 `val1`을 얻고, 그 값을 두 번째 `load_array(arr2, val1)`의 index로 사용해 `val2`를 반환한다.

추측 실행에서 첫 번째 호출이 범위 밖 address의 값을 반환하면 두 번째 호출은 그 비밀 값에 따라 다른 microarchitectural state를 만든다. 공격자는 이 차이를 측정해 arbitrary read primitive를 구성할 수 있다.

More complex sequences involving multiple dependent memory accesses may
result in sensitive information being leaked. Consider the following
code, building on the prior example::

	int load_dependent_arrays(int *arr1, int *arr2, int index)
	{
		int val1, val2,

		val1 = load_array(arr1, index);
		val2 = load_array(arr2, val1);

		return val2;
	}

Under speculation, the first call to load_array() may return the value
of an out-of-bounds address, while the second call will influence
microarchitectural state dependent on this value. This may provide an
arbitrary read primitive.

array_index_nospec로 index 정화

kernel은 추측 실행 중에도 bounds check가 존중되도록 하는 generic API를 제공한다. speculation 기반 side-channel의 영향을 받는 architecture는 이 primitive를 구현해야 한다.

`<linux/nospec.h>`의 `array_index_nospec()` helper는 side-channel을 통한 정보 유출을 막는 데 사용한다. `array_index_nospec(index, size)`는 CPU가 추측 실행 중이더라도 `[0, size)` 안으로 제한된 정화된 index를 반환한다.

보호된 `load_array()`는 일반 bounds check 뒤의 `else`에서 `index = array_index_nospec(index, MAX_ARRAY_ELEMS)`를 수행한 다음 배열을 읽는다. 정상 control flow 검사와 speculation barrier 성격의 index 정화를 함께 적용하는 패턴이다.

Mitigating speculation side-channels
====================================

The kernel provides a generic API to ensure that bounds checks are
respected even under speculation. Architectures which are affected by
speculation-based side-channels are expected to implement these
primitives.

The array_index_nospec() helper in <linux/nospec.h> can be used to
prevent information from being leaked via side-channels.

A call to array_index_nospec(index, size) returns a sanitized index
value that is bounded to [0, size) even under cpu speculation
conditions.

This can be used to protect the earlier load_array() example::

	int load_array(int *array, unsigned int index)
	{
		if (index >= MAX_ARRAY_ELEMS)
			return 0;
		else {
			index = array_index_nospec(index, MAX_ARRAY_ELEMS);
			return array[index];
		}
	}