이전 장에서는 eBPF에 대해 배웠습니다. 이번 장에서는 사용자가 전달한 BPF 프로그램을 안전하고 빠르게 실행하기 위한 검증기와 JIT에 대해 설명합니다.

검증기

먼저 eBPF의 검증기에 대해 배워봅시다. 검증기의 소스 코드는 리눅스 커널의 kernel/bpf/verifier.c에 작성되어 있습니다.
검증기는 명령을 하나씩 체크하고, 모든 분기 대상을 exit 명령까지 추적합니다. 검증은 크게 두 단계(First Pass, Second Pass)로 나뉩니다.

첫 번째 단계의 체크에서는 깊이 우선 탐색(DFS)을 통해 프로그램이 방향성 비순환 그래프(DAG; Directed Acyclic Graph)임을 보장합니다. DAG란 루프가 없는 방향성 그래프를 말합니다.
이 체크에 의해 다음과 같은 프로그램은 거부됩니다.

  • BPF_MAXINSNS를 초과하는 명령이 존재하는 경우[1]
  • 루프 흐름이 존재하는 경우
  • 도달 불가능한 명령이 존재하는 경우
  • 범위를 벗어나거나 부정한 점프가 존재하는 경우

두 번째 단계의 체크에서는 다시 모든 경로를 탐색합니다. 이때 레지스터 값에 대해 타입이나 범위를 추적합니다.
이 체크에 의해 예를 들어 다음과 같은 프로그램은 거부됩니다.

  • 초기화되지 않은 레지스터 사용
  • 커널 공간 포인터의 return
  • 커널 공간 포인터를 BPF 맵에 쓰기
  • 부정한 포인터 읽기/쓰기

첫 번째 단계 체크

DAG 체크는 check_cfg 함수에 구현되어 있습니다. 알고리즘 자체는 재귀 호출을 사용하지 않는 깊이 우선 탐색입니다.
check_cfg는 프로그램의 처음부터 깊이 우선 탐색 요령으로 명령을 살펴봅니다. 현재 보고 있는 명령에 대해 visit_insn이 호출되고, 이 함수에서 분기 대상이 스택에 push됩니다. 탐색용 스택으로의 push는 push_insn에서 정의되어 있으며, 이 안에 범위 밖으로의 점프와 폐로(cycle) 검출이 포함되어 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
	if (w < 0 || w >= env->prog->len) {
		verbose_linfo(env, t, "%d: ", t);
		verbose(env, "jump out of range from insn %d to %d\n", t, w);
		return -EINVAL;
	}
...

	} else if ((insn_state[w] & 0xF0) == DISCOVERED) {
		if (loop_ok && env->bpf_capable)
			return DONE_EXPLORING;
		verbose_linfo(env, t, "%d: ", t);
		verbose_linfo(env, w, "%d: ", w);
		verbose(env, "back-edge from insn %d to %d\n", t, w);
		return -EINVAL;

또한 visit_insn은 한 번에 반드시 하나의 경로만 push합니다. (또는 DONE_EXPLORING으로 그 명령의 분기 대상이 모두 탐색 종료되었음을 알립니다.) 예를 들어 BPF_JEQ와 같이 조건 분기가 있는 경우, visit_insn은 첫 번째 분기 대상만 push합니다. 깊이 우선 탐색이므로, 그 분기 대상의 탐색이 모두 종료되면 다시 BPF_JEQ로 돌아옵니다. 그러면 BPF_JEQ에 대해 다시 visit_insn이 호출되고, 이번에는 다른 한쪽의 분기 대상이 push됩니다. 또한 그쪽의 탐색이 종료되면 BPF_JEQ에 대해 3번째 visit_insn이 호출되고, 거기서 DONE_EXPLORING이 반환되어 BPF_JEQ가 스택에서 pop됩니다.

늑대군

조건 분기에서 한 번에 양쪽 경로를 push하지 않거나, 명령을 꺼낼 때 pop하지 않는 등 일견 비효율적으로 보이지만, 이상을 감지했을 때 깔끔한 스택 트레이스를 출력하기 위한 고안이구나.

예를 들어, 다음과 같은 프로그램은 모두 첫 번째 단계의 체크 기구에 의해 거부됩니다.

1
2
3
4
5
6
// 도달 불가능한 명령이 있음
struct bpf_insn insns[] = {
  BPF_EXIT_INSN(),
  BPF_MOV64_IMM(BPF_REG_0, 0),
  BPF_EXIT_INSN(),
};
1
2
3
4
5
6
// 범위 밖으로의 점프가 있음
struct bpf_insn insns[] = {
  BPF_JMP_IMM(BPF_JA, 0, 0, 2),
  BPF_MOV64_IMM(BPF_REG_0, 0),
  BPF_EXIT_INSN(),
};
1
2
3
4
5
6
// 루프가 있음
struct bpf_insn insns[] = {
  BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 123, -1), // jmp if r0 != 123
  BPF_MOV64_IMM(BPF_REG_0, 0),
  BPF_EXIT_INSN(),
};

비록 음의 방향으로의 점프가 있어도, 루프하지 않으면 문제 없습니다.

1
2
3
4
5
6
7
struct bpf_insn insns[] = {
  BPF_MOV64_IMM(BPF_REG_0, 0),
  BPF_JMP_IMM(BPF_JA, 0, 0, 1), // jmp to JEQ
  BPF_JMP_IMM(BPF_JA, 0, 0, 1), // jmp to MOV64
  BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, -2), // jmp to JA(1) if R0==0
  BPF_EXIT_INSN(),
};

두 번째 단계 체크

eBPF에서 검증기 버그 중 가장 중요한 것은 두 번째 단계의 체크입니다.
두 번째 단계의 체크는 주로 do_check 함수에 정의되어 있으며, 레지스터의 타입, 값의 범위, 구체적인 값이나 오프셋을 추적합니다.

타입 추적

검증기는 레지스터의 값이 어떤 종류의 값인지를 bpf_reg_state 구조체에 유지하고 있습니다. 예를 들어 다음과 같은 명령을 생각해 봅시다.

1
2
BPF_MOV64_REG(BPF_REG_0, BPF_REG_10)
BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, -8)

첫 번째 명령에서는 스택 포인터를 R0에 대입하고 있습니다. 이때 R0은 PTR_TO_STACK이라는 타입이 됩니다. 다음 명령에서는 R0에서 8만큼 빼지만, 아직 스택 범위 내를 가리키고 있기 때문에 PTR_TO_STACK 상태 그대로입니다. 이 외에도 포인터와 포인터의 덧셈은 상수 취급이 되는 등, 명령의 종류와 레지스터의 타입, 값의 범위 등에 따라 새로운 타입은 달라집니다.
타입 추적은 부정한 프로그램을 조사하는 데 필수적입니다. 예를 들어 스칼라 값을 포인터로서 메모리에서 데이터를 로드/스토어할 수 있게 되면, 임의 주소 읽기/쓰기가 되어 버립니다. 또한 컨텍스트를 받는 헬퍼 함수에 BPF 맵 등 자유롭게 조작할 수 있는 포인터를 지정할 수 있게 되면 가짜 컨텍스트를 사용하게 할 수 있습니다.
레지스터의 타입(enum bpf_reg_type)으로는 예를 들어 다음과 같은 타입이 정의되어 있습니다.

타입 의미
NOT_INIT 초기화되지 않음
SCALAR_VALUE 상수 등 일반적인 값
PTR_TO_CTX 컨텍스트(BPF 프로그램의 호출 인자)에 대한 포인터
CONST_PTR_TO_MAP BPF 맵에 대한 포인터
PTR_TO_MAP_VALUE BPF 맵 값에 대한 포인터
PTR_TO_MAP_KEY BPF 맵 키에 대한 포인터
PTR_TO_STACK BPF 스택에 대한 포인터
PTR_TO_MEM 유효한 메모리 영역에 대한 포인터
PTR_TO_FUNC BPF 함수에 대한 포인터

레지스터의 초기 상태는 init_reg_state 함수에 정의됩니다.

상수 추적

검증기에서는 레지스터의 상수를 추적하고 있습니다. 값은 구간을 사용한 추상화로 추적됩니다. 즉, 각 레지스터에 대해 그 시점에서 레지스터가 가질 수 있는 '최솟값’과 '최댓값’을 기록하고 있습니다.
예를 들어 R0 += R1 (BPF_ADD) 시점에 R0과 R1이 각각 [10, 20], [-2, 2]를 가질 수 있는 경우, 연산(추상 해석) 후의 R0 값은 [8, 22]가 됩니다.
연산에 관한 이 동작은 adjust_reg_min_max_vals 함수와 adjust_scalar_min_max_vals 함수에 정의되어 있습니다.

늑대군

구체적인 값을 알 수 없는 해석 과정에서는 값을 추상적인 범위로 추측하는 경우가 많아. 건전(sound)한 기법으로 추상화하지 않으면 해석 결과가 틀릴 수 있어.

값의 범위 추적을 위해 검증기는 각 레지스터에 대해 다음과 같은 값을 유지/추적하고 있습니다.

변수 의미
umin_value, umax_value 64-bit 부호 없는 정수로 해석했을 때의 최소/최대값
smin_value, smax_value 64-bit 부호 있는 정수로 해석했을 때의 최소/최대값
u32_min_value, u32_max_value 32-bit 부호 없는 정수로 해석했을 때의 최소/최대값
s32_min_value, s32_max_value 32-bit 부호 있는 정수로 해석했을 때의 최소/최대값
var_off 레지스터 내 각 비트 정보(구체적인 값이 판명된 비트)

var_off는 tnum이라 불리는 구조체로 mask와 value를 가집니다. mask는 값이 불분명한 비트의 위치가 1로 되어 있습니다. value는 판명된 위치의 값입니다.
예를 들어 BPF 맵에서 취득한 64비트 값은 처음 모든 비트가 불분명하므로 var_off는

1
(mask=0xffffffffffffffff; value=0x0)

가 됩니다. 이 레지스터에 대해 0xffff0000을 AND하면, 0과 AND한 곳은 0이 된다는 것을 알 수 있으므로

1
(mask=0xffff0000; value=0x0)

가 됩니다. 게다가 0x12345를 더하면 하위 16비트는 알 수 있으므로

1
(mask=0x1ffff0000; value=0x2345)

가 됩니다. 올림(carry) 가능성을 고려하여 mask 비트가 하나 늘어난 것에 주의하십시오. 이 시점에서의 umin_value, umax_value, u32_min_value, u32_max_value는 각각 0x1ffff0000, 0x1ffff2345, 0xffff0000, 0xffff2345입니다.

그럼 구체적인 구현을 살펴봅시다. BPF_ADD의 경우 다음과 같이 레지스터가 갱신됩니다.

1
2
3
4
5
case BPF_ADD:
	scalar32_min_max_add(dst_reg, &src_reg);
	scalar_min_max_add(dst_reg, &src_reg);
	dst_reg->var_off = tnum_add(dst_reg->var_off, src_reg.var_off);
	break;

scalar_min_max_add에서는 다음과 같이 정수 오버플로우 등도 고려한 범위 계산이 구현되어 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static void scalar_min_max_add(struct bpf_reg_state *dst_reg,
			       struct bpf_reg_state *src_reg)
{
	s64 smin_val = src_reg->smin_value;
	s64 smax_val = src_reg->smax_value;
	u64 umin_val = src_reg->umin_value;
	u64 umax_val = src_reg->umax_value;

	if (signed_add_overflows(dst_reg->smin_value, smin_val) ||
	    signed_add_overflows(dst_reg->smax_value, smax_val)) {
		dst_reg->smin_value = S64_MIN;
		dst_reg->smax_value = S64_MAX;
	} else {
		dst_reg->smin_value += smin_val;
		dst_reg->smax_value += smax_val;
	}
	if (dst_reg->umin_value + umin_val < umin_val ||
	    dst_reg->umax_value + umax_val < umax_val) {
		dst_reg->umin_value = 0;
		dst_reg->umax_value = U64_MAX;
	} else {
		dst_reg->umin_value += umin_val;
		dst_reg->umax_value += umax_val;
	}
}

곱셈/나눗셈이나 논리/산술 시프트 등 모든 연산에 대해 이러한 갱신 처리가 구현되어 있습니다. 계산된 값의 범위는 스택이나 컨텍스트 등의 메모리 접근에서 오프셋이 범위 내에 들어있는지 확인하는 데 사용됩니다.
예를 들어 스택 범위 체크는 check_stack_access_within_bounds에 정의되어 있습니다. 즉치(immediate value)의 경우 등 값이 상수라고 알려진 경우는 일반적인 오프셋 체크를 합니다.

1
2
3
4
5
6
if (tnum_is_const(reg->var_off)) {
	min_off = reg->var_off.value + off;
	if (access_size > 0)
		max_off = min_off + access_size - 1;
	else
		max_off = min_off;

한편 구체적인 값을 모르는 경우는 오프셋이 취할 수 있는 최솟값/최댓값을 확인합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
} else {
	if (reg->smax_value >= BPF_MAX_VAR_OFF ||
	    reg->smin_value <= -BPF_MAX_VAR_OFF) {
		verbose(env, "invalid unbounded variable-offset%s stack R%d\n",
			err_extra, regno);
		return -EACCES;
	}
	min_off = reg->smin_value + off;
	if (access_size > 0)
		max_off = reg->smax_value + off + access_size - 1;
	else
		max_off = min_off;
}

그리고 그 값들을 사용하여 범위 체크를 하고 있습니다.

1
2
3
err = check_stack_slot_within_bounds(min_off, state, type);
if (!err)
	err = check_stack_slot_within_bounds(max_off, state, type);

이와 같이 레지스터나 변수 값의 범위를 추적하는 기법은 BPF 이외에도, 최적화/고속화가 요구되는 JIT에서 빈번하게 사용됩니다.

늑대군

실행 속도 향상을 위해 가능한 한 사전에 보안 체크를 끝마치고 있는 거구나.

다음과 같은 프로그램은 모두 두 번째 단계의 체크 기구에 의해 거부됩니다.

1
2
3
4
5
// 초기화되지 않은 레지스터 사용
struct bpf_insn insns[] = {
  BPF_MOV64_REG(BPF_REG_0, BPF_REG_5),
  BPF_EXIT_INSN(),
};
1
2
3
4
5
// 커널 공간 포인터 릭
struct bpf_insn insns[] = {
  BPF_MOV64_REG(BPF_REG_0, BPF_REG_1),
  BPF_EXIT_INSN(),
};

추상화된 값이 상수가 되지 않는 예를 생각해 봅시다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int mapfd = map_create(0x10, 1);

struct bpf_insn insns[] = {
  BPF_ST_MEM(BPF_DW, BPF_REG_FP, -0x08, 0),      // key=0
  // arg1: mapfd
  BPF_LD_MAP_FD(BPF_REG_ARG1, mapfd),
  // arg2: key pointer
  BPF_MOV64_REG(BPF_REG_ARG2, BPF_REG_FP),
  BPF_ALU64_IMM(BPF_ADD, BPF_REG_ARG2, -8),
  // map_lookup_elem(mapfd, &key)
  BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
  // jmp if success (R0 != NULL)
  BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
  BPF_EXIT_INSN(), // exit on failure

  BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_0, 0),   // R6 = arr[0]
  BPF_MOV64_REG(BPF_REG_7, BPF_REG_0),            // R7 = &arr[0]

  BPF_ALU64_IMM(BPF_AND, BPF_REG_6, 0b0111),    // R6 &= 0b0111
  BPF_ALU64_REG(BPF_ADD, BPF_REG_7, BPF_REG_6), // R7 += R6
  BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_7, 0), // R0 = [R7]
  BPF_EXIT_INSN(),
};

먼저 값의 크기가 0x10인 BPF 맵을 준비합니다. BPF 프로그램의 첫 번째 블록에서는 BPF 맵의 첫 번째 값과 그 포인터를 각각 R6, R7에 대입합니다. (map_lookup_elem의 반환값 R0은 두 번째 인자의 인덱스로 지정한 요소에 대한 포인터입니다. NULL을 반환할 가능성이 있으므로 조건 분기로 NULL을 제거하고 있습니다.)
마지막 블록에서 포인터 R7에 R6의 값을 더하고 있습니다. R6은 BPF 맵에서 가져온 값이므로 임의의 값을 취할 수 있습니다. 그러나 BPF_AND로 0b0111과 AND를 취하고 있으므로, 이 시점에서 R6이 취할 수 있는 값은 [0, 7]이 됩니다. 이번 BPF 맵 값의 크기는 0x10으로 했으므로, 값 포인터의 처음부터 7을 더해 거기서 BPF_LDX_MEM(BPF_DW)으로 8바이트 취득해도 문제 없습니다. 따라서 이 BPF 프로그램은 검증기를 통과할 수 있습니다.
그러나 BPF_AND 값을 0b1111 등으로 하면 검증기가 프로그램을 거부하는 것을 알 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
...
11: (0f) r7 += r6
 R0=map_value(id=0,off=0,ks=4,vs=16,imm=0) R6_w=invP(id=0,umax_value=15,var_off=(0x0; 0xf)) R7_w=map_value(id=0,off=0,ks=4,vs=16,umax_value=15,var_off=(0x0; 0xf)) R10=fp0 fp-8=mmmmmmmm
12: R0=map_value(id=0,off=0,ks=4,vs=16,imm=0) R6_w=invP(id=0,umax_value=15,var_off=(0x0; 0xf)) R7_w=map_value(id=0,off=0,ks=4,vs=16,umax_value=15,var_off=(0x0; 0xf)) R10=fp0 fp-8=mmmmmmmm
12: (79) r0 = *(u64 *)(r7 +0)
 R0_w=map_value(id=0,off=0,ks=4,vs=16,imm=0) R6_w=invP(id=0,umax_value=15,var_off=(0x0; 0xf)) R7_w=map_value(id=0,off=0,ks=4,vs=16,umax_value=15,var_off=(0x0; 0xf)) R10=fp0 fp-8=mmmmmmmm
invalid access to map value, value_size=16 off=15 size=8
R7 max value is outside of the allowed memory range
processed 12 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1

bpf(BPF_PROG_LOAD): Permission denied

값의 크기가 16인데 최대 오프셋은 15이고, 거기서 8바이트를 취득하려고 하고 있어서 범위 밖 참조가 일어나기 때문입니다.
또한 일부 명령은 값 추적을 지원하지 않습니다. 예를 들어 BPF_NEG를 통과하면 반드시 unbound가 되기 때문에, 다음 프로그램은 (실제로는 문제 없지만) 검증기에 의해 거부됩니다.

1
2
3
4
5
BPF_ALU64_IMM(BPF_AND, BPF_REG_6, 0b0111),    // R6 &= 0b0111
BPF_ALU64_IMM(BPF_NEG, BPF_REG_6, 0),         // R6 = -R6 (추가)
BPF_ALU64_IMM(BPF_NEG, BPF_REG_6, 0),         // R6 = -R6 (추가)
BPF_ALU64_REG(BPF_ADD, BPF_REG_7, BPF_REG_6), // R7 += R6
BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_7, 0), // R0 = [R7]

이처럼 두 번째 단계의 체크에서는 레지스터를 따라가며 메모리 접근이나 레지스터 사용 시 정의되지 않은 동작(undefined behavior)이 일어나지 않음을 보장하고 있습니다. 반대로 말하면, 이 체크가 잘못되어 있으면 메모리 접근에서 범위 밖 참조를 일으킬 수 있다는 뜻입니다. 구체적인 기법은 다음 장에서 설명합니다.

ALU sanitation

지금까지 설명한 타입 체크/범위 추적이 검증기의 역할이지만, eBPF를 악용하는 공격이 늘어났기 때문에 최근에는 새로 ALU sanitation이라는 완화 기구가 도입되었습니다.
검증기의 실수로 인해 공격이 발생하는 원인은 범위 밖 참조를 일으킬 수 있기 때문입니다. 예를 들어 아래 그림과 같이 검증기가 0이라고 추측하고 있는데 실제 값이 32인 ‘망가진’ 레지스터가 생겼다고 가정합시다. 공격자는 그림과 같이 크기 8인 값을 4개 가진 맵의 포인터에 망가진 값을 더합니다. 검증기는 값을 0이라고 생각하고 있으므로 합산 후에도 맵의 선두를 가리킨 상태 그대로라고 생각하지만, 실제로는 범위 밖을 가리키고 있습니다. 이 상태에서 R1으로부터 값을 로드하면 검증기에서 탐지되지 않고 범위 밖 참조가 가능합니다.

추측 값 오류로 인한 범위 밖 참조

이러한 검증기 오류로 인한 범위 밖 참조를 해결하기 위해 ALU sanitation이라는 완화 기구가 2019년에 도입되었습니다.[2]

eBPF에서는 포인터에 대해서는 스칼라 값의 덧셈/뺄셈만이 연산으로 허용됩니다. ALU sanitation에서는 포인터와 스칼라 값의 덧셈/뺄셈에서 스칼라 값 쪽이 상수라고 알려져 있을 때, 그것을 상수 연산 BPF_ALUxx_IMM으로 다시 씁니다. 예를 들어 R1이 맵 포인터이고 R2가 추측 값 0, 실제 값 1인 스칼라 값을 가진 레지스터라고 합시다. 이때

1
BPF_ALU64_REG(BPF_ADD, BPF_REG_1, BPF_REG_2)

은 검증기가 R2를 상수 0이라고 생각하기 때문에

1
BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 0)

으로 변경됩니다. 이 패치는 원래 Spectre라는 사이드 채널 공격을 막기 위해 도입된 것이지만, 검증기 버그를 악용하는 공격에도 효과가 있습니다.

또한 스칼라 쪽이 상수가 아닌 경우는 alu_limit라는 값을 이용하여 명령이 패치됩니다.
alu_limit은 '그 포인터에서 최대로 얼마만큼의 값을 더하고 뺄 수 있는가’를 나타내는 수치입니다. 예를 들어 크기 0x10인 맵 요소의 처음부터 2바이트 째를 가리키고 있고, BPF_ADD에 의한 스칼라 값과의 덧셈이 발생하는 경우 alu_limit은 0xe가 됩니다. 앞서와 마찬가지로

1
BPF_ALU64_REG(BPF_ADD, BPF_REG_1, BPF_REG2)

라는 명령을 생각합니다. ALU sanitation에서는 이 명령이 다음과 같이 패치됩니다. (BPF_REG_AX는 보조 레지스터입니다.)

1
2
3
4
5
6
BPF_MOV32_IMM(BPF_REG_AX, aux->alu_limit),
BPF_ALU64_REG(BPF_SUB, BPF_REG_AX, off_reg),
BPF_ALU64_REG(BPF_OR, BPF_REG_AX, off_reg),
BPF_ALU64_IMM(BPF_NEG, BPF_REG_AX, 0),
BPF_ALU64_IMM(BPF_ARSH, BPF_REG_AX, 63),
BPF_ALU64_REG(BPF_AND, BPF_REG_AX, off_reg),

앞서와 마찬가지로 크기 0x10의 맵 요소의 처음부터 2바이트 째를 가리키고 있는 레지스터 R1에 대한 스칼라 값 R2의 덧셈을 생각합니다. 스칼라 값 R2가 alu_limit인 0xe를 초과하고 있음에도 불구하고, 무언가 버그로 인해 검증기가 탐지하지 못하고 있다고 합시다. 예를 들어 다음과 같은 명령열이 생성됩니다.

1
2
3
4
5
6
BPF_MOV32_IMM(BPF_REG_AX, 0xe),
BPF_ALU64_REG(BPF_SUB, BPF_REG_AX, BPF_REG_R2),
BPF_ALU64_REG(BPF_OR, BPF_REG_AX, BPF_REG_R2),
BPF_ALU64_IMM(BPF_NEG, BPF_REG_AX, 0),
BPF_ALU64_IMM(BPF_ARSH, BPF_REG_AX, 63),
BPF_ALU64_REG(BPF_AND, BPF_REG_AX, BPF_REG_R2),

먼저 처음 2개 명령에서 0xe-R2를 계산합니다. R2가 범위 내인 경우는 양수 또는 0이 되지만, 범위 밖인 경우는 음수가 됩니다. 다음 OR 명령에서는 AX와 R2가 다른 부호를 가질 경우 최상위 비트가 1이 됩니다. 즉, 범위 밖 참조가 일어날 때는 이 시점에서 최상위 비트가 1이 되어 있을 것입니다.
그 후 NEG로 부호를 반전시키고 산술 시프트로 64비트 시프트합니다. 범위 밖 참조가 일어나는 경우는 AX에 0이, 그렇지 않으면 AX에 0xffffffffffffffff이 들어갑니다. 마지막으로 R2와 AX의 AND를 취하고, 이것이 최종적으로 사용되는 오프셋이 됩니다.

이 조작에 의해 만일 범위 밖 참조가 발생하는 상황이 되면 포인터에 0이 더해지게 됩니다.

각 조작의 가능 여부

두 번째 단계의 체크에 의해 금지되어 있는 처리를 대략적으로 정리하면 다음과 같습니다.

  • 레지스터
    • R10(FP)에 쓰기
    • 초기화되지 않은 레지스터 읽기
  • 컨텍스트
    • 컨텍스트 범위 밖 읽기/쓰기
    • check_ctx_accesses 중의 컨텍스트에 대응하는 코드가 허용하지 않는 읽기/쓰기
  • BPF 맵
    • 데이터 범위 밖 읽기/쓰기
    • 포인터 쓰기
  • 스택
    • 스택 범위 밖 읽기/쓰기
    • 초기화되지 않은 영역 읽기
    • 8바이트(32-bit라면 4바이트)로 정렬되지 않은(가능성이 있는) 읽기/쓰기
    • 포인터의 하위 32비트(BPF_W) 등 부분적인 읽기/쓰기
  • 메모리 전반
    • NULL 포인터를 가질 가능성이 있는 포인터의 읽기/쓰기
  • 함수
    • 정의와 다른 타입/값의 인자 전달

맵에 값을 쓰면 쓰기 대상의 추적 범위는 소멸합니다. 한편 스택에는 포인터를 쓸 수 있는 데다, 쓴 값의 범위나 타입을 기억해 줍니다. 그 대가로 스택에는 512바이트의 크기 제한이 있고 정렬되지 않은 오프셋에 대한 쓰기나 사용자 공간에서의 읽기/쓰기는 불가능합니다.

JIT (Just-In-Time compiler)

검증기를 통과한 BPF 프로그램은 어떠한 입력으로 실행해도 안전하다는 것이 (검증기가 올바르다는 가정 하에) 보장되어 있습니다. 따라서 JIT 컴파일러는 주어진 명령을 CPU에 맞는 기계어로 직접 변환하게 됩니다.
CPU마다 기계어는 다르기 때문에 JIT 코드는 arch 디렉토리 하위에 작성되어 있습니다. x86-64의 경우 arch/x86/net/bpf_jit_comp.c 안의 do_jit 함수에 기술되어 있습니다.
예를 들어 곱셈(BPF_MUL)을 기계어로 변환하는 코드는 다음과 같이 되어 있습니다.

1
2
3
4
5
6
7
8
case BPF_ALU | BPF_MUL | BPF_X:
case BPF_ALU64 | BPF_MUL | BPF_X:
	maybe_emit_mod(&prog, src_reg, dst_reg,
		       BPF_CLASS(insn->code) == BPF_ALU64);

	/* imul dst_reg, src_reg */
	EMIT3(0x0F, 0xAF, add_2reg(0xC0, src_reg, dst_reg));
	break;

0x0F, 0xAF가 imul 명령에 대응하는 명령 코드가 됩니다.

늑대군

검증기가 올바르더라도 JIT에서 생성되는 코드가 검증기와 다른 동작을 하면 그것도 악용 가능(exploitable)할 것 같네.

여기까지 exploit에 필요한 eBPF 내부 구조를 대략 설명했습니다. 다음 장에서는 실제로 검증기 버그를 이용하여 권한 상승을 해보겠습니다.

다음 처리가 검증기에 허용되는지 조사해 보세요. 거부될 경우, 그것이 가능하면 보안상 무엇이 문제가 되는지 설명해 보세요.
(1) 포인터끼리의 비교
(2) 포인터와 포인터의 뺄셈
(3) 스택에 포인터 값 쓰기
(4) BPF 맵에 포인터 값 쓰기
(5) 범위 내이지만 정렬되지 않은 스택 주소 읽기/쓰기

  1. 명령 수에 대해서는 다른 체크가 있는 check_cfg 이전에 체크됩니다. ↩︎

  2. ALU sanitation은 구현에 버그가 있어서 2021년에 수정되었습니다. ↩︎