eBPF verifier

두 단계 안전성 분석과 레지스터 호출 규약

`eBPF verifier`는 eBPF 프로그램의 안전성을 두 단계로 판정합니다. 첫 단계는 DAG 검사와 그 밖의 CFG 검증을 수행하여 loop를 허용하지 않고 도달할 수 없는 instruction을 찾아냅니다. classic BPF checker는 도달 불가능한 instruction을 허용하지만 eBPF verifier는 이를 거부합니다.

두 번째 단계는 첫 instruction에서 시작해 가능한 모든 실행 경로를 따라 내려가며 각 instruction의 실행을 모의하고 register와 stack 상태가 어떻게 바뀌는지 관찰합니다.

프로그램 시작 시 `R1`은 context pointer를 담고 형식은 `PTR_TO_CTX`입니다. `R2=R1`을 실행하면 `R2`도 `PTR_TO_CTX`가 되어 식의 오른쪽에서 사용할 수 있습니다. 반면 `R2=R1+R1`처럼 유효한 pointer 두 개를 더하면 유효한 pointer가 아니므로 `R2`는 `SCALAR_VALUE`가 됩니다. `secure` mode에서는 kernel address가 비특권 사용자에게 노출되지 않도록 모든 pointer arithmetic을 거부합니다.

한 번도 쓰지 않은 register는 읽을 수 없습니다. 다음 프로그램은 시작 시 읽을 수 없는 `R2`를 `R0`으로 옮기므로 거부됩니다.

bpf_mov R0 = R2
bpf_exit

kernel function을 호출하고 나면 `R1-R5`는 읽을 수 없는 상태로 초기화되고 `R0`은 그 function의 return type을 갖습니다. `R6-R9`는 callee-saved이므로 호출을 지나서도 상태가 보존됩니다.

bpf_mov R6 = 1
bpf_call foo
bpf_mov R0 = R6
bpf_exit

따라서 위 프로그램은 올바릅니다. `R6` 대신 `R1`을 사용했다면 호출 뒤의 `R1`은 읽을 수 없으므로 거부됩니다.

메모리 접근, stack 초기화와 function prototype

load/store instruction은 `PTR_TO_CTX`, `PTR_TO_MAP`, `PTR_TO_STACK`처럼 유효한 pointer 형식의 register를 사용할 때만 허용되며, 접근 범위와 alignment도 검사합니다. 다음 예에서 `R1`은 scalar `1`일 뿐 유효한 pointer가 아니므로 `bpf_xadd` 실행 시 거부됩니다.

bpf_mov R1 = 1
bpf_mov R2 = 2
bpf_xadd *(u32 *)(R1 + 3) += R2
bpf_exit

처음의 `R1`은 일반적인 `struct bpf_context`를 가리키는 `PTR_TO_CTX`입니다. verifier별 callback은 eBPF 프로그램이 context 구조체에서 지정된 크기와 alignment를 만족하는 특정 field에만 접근하도록 제한합니다.

다음 instruction은 `R6 + 8` 주소에서 32-bit word를 읽어 `R0`에 저장하려는 동작입니다.

bpf_ld R0 = *(u32 *)(R6 + 8)

`R6=PTR_TO_CTX`라면 verifier는 `is_valid_access()` callback을 통해 offset 8에서 4 bytes를 읽을 수 있는지 확인하고, 허용되지 않으면 프로그램을 거부합니다. `R6=PTR_TO_STACK`이라면 접근은 정렬되어야 하고 stack 범위 `[-MAX_BPF_STACK, 0)` 안에 있어야 합니다. 예의 양수 offset 8은 stack 범위를 벗어나므로 검증에 실패합니다.

verifier는 eBPF 프로그램이 먼저 쓴 stack data만 읽도록 허용합니다. classic BPF verifier도 `M[0-15]` memory slot에 대해 비슷한 검사를 합니다.

bpf_ld R0 = *(u32 *)(R10 - 4)
bpf_exit

위 프로그램에서 read-only `R10`은 올바른 `PTR_TO_STACK`이고 `R10 - 4`도 stack 범위 안이지만, 그 위치에 먼저 store한 적이 없으므로 프로그램은 유효하지 않습니다.

callee-saved register `R6-R9` 네 개만으로 부족할 수 있으므로 pointer register를 stack에 spill하고 다시 fill하는 동작도 형식 정보를 유지하며 추적합니다.

허용되는 function call은 `bpf_verifier_ops->get_func_proto()`로 맞춤 설정합니다. eBPF verifier는 register가 argument constraint와 일치하는지 검사하고 호출 뒤 `R0`을 function의 return type으로 설정합니다.

function call은 eBPF 기능을 확장하는 주된 수단입니다. socket filter와 tracing filter는 서로 완전히 다른 function 집합을 허용할 수 있습니다. eBPF 프로그램에 function을 공개할 때는 안전성을 면밀히 검토해야 하며, verifier는 유효한 argument로만 호출된다는 점을 보장합니다.

classic BPF의 seccomp와 socket filter는 보안 제약이 달라 seccomp가 classic BPF verifier 뒤에 별도의 seccomp verifier를 실행하는 두 단계 방식을 사용합니다. eBPF에서는 모든 사용 사례가 설정 가능한 verifier 하나를 공유합니다. 구현 세부 사항은 `kernel/bpf/verifier.c`에 있습니다.

struct bpf_reg_state와 pointer 형식

eBPF 프로그램의 안전성을 판정하려면 verifier가 각 register와 각 stack slot에 들어갈 수 있는 값의 범위를 추적해야 합니다. `include/linux/bpf_verifier.h`의 `struct bpf_reg_state`는 scalar와 pointer 값 추적을 하나로 통합합니다.

각 register 상태의 형식은 아직 쓰지 않은 `NOT_INIT`, pointer로 쓸 수 없는 값인 `SCALAR_VALUE`, 또는 base를 설명하는 pointer 형식 가운데 하나입니다.

`PTR_TO_SOCKET`은 reference-counted이므로 프로그램이 끝나기 전에 socket release function으로 reference를 반드시 해제해야 합니다.

고정·가변 offset, 경계와 tnum

pointer arithmetic 결과로 pointer가 base에서 떨어질 수 있으므로 verifier는 offset을 `fixed offset`과 `variable offset` 두 부분으로 추적합니다. immediate operand처럼 정확히 아는 값을 더하면 fixed offset에 반영하고, 정확히 알 수 없는 값을 더하면 variable offset에 반영합니다. `SCALAR_VALUE`도 register의 가능한 값 범위를 나타내기 위해 variable offset을 사용합니다.

verifier가 variable offset에 대해 유지하는 정보는 다음과 같습니다.

• unsigned minimum과 maximum
• signed minimum과 maximum
• 각 bit의 알려짐 여부를 나타내는 `tnum`: u64 `mask`와 u64 `value`

`tnum`에서 mask의 1 bit는 값이 알려지지 않았음을, value의 1 bit는 그 bit가 1임을 뜻합니다. 0으로 알려진 bit는 mask와 value 모두 0이며 같은 bit가 양쪽에서 동시에 1이어서는 안 됩니다.

memory에서 byte 하나를 읽으면 register 상위 56 bits는 0이고 하위 8 bits는 알 수 없으므로 `tnum (0x0; 0xff)`로 표현합니다. 여기에 `0x40`을 OR하면 `(0x40; 0xbf)`, 다시 1을 더하면 carry 가능성 때문에 `(0x0; 0x1ff)`가 됩니다.

register 상태는 arithmetic뿐 아니라 conditional branch에서도 정제됩니다. `SCALAR_VALUE > 8` 비교의 true branch에서는 `umin_value=9`, false branch에서는 `umax_value=8`이 됩니다. `BPF_JSGT`나 `BPF_JSGE` 같은 signed compare는 signed minimum/maximum을 갱신합니다.

signed와 unsigned bound 정보는 결합할 수 있습니다. 값을 먼저 `< 8`로 검사하고 이어서 `s> 4`로 검사하면 sign boundary를 넘을 수 없으므로 verifier는 동시에 `> 4`와 `s< 8`임을 결론 내립니다.

공유 id, alignment와 socket reference

variable offset을 가진 `PTR_TO_PACKET`에는 같은 variable offset을 공유하는 모든 pointer에 공통인 `id`가 있습니다. packet range 검사에서 이 관계가 중요합니다.

packet pointer register A에 변수를 더하고 이를 B에 복사한 다음 A에 상수 4를 더하면 A와 B는 같은 `id`를 공유하지만 A의 fixed offset은 `+4`입니다. A가 `PTR_TO_PACKET_END`보다 작은지 검사해 통과하면 B에는 최소 4 bytes의 안전 범위가 있다고 알 수 있습니다.

`PTR_TO_MAP_VALUE_OR_NULL`에서도 map lookup이 반환한 pointer의 모든 복사본이 같은 `id`를 공유합니다. 한 복사본이 non-NULL로 확인되면 모든 복사본이 `PTR_TO_MAP_VALUE`로 바뀔 수 있습니다.

추적 정보는 range뿐 아니라 pointer access alignment를 강제하는 데도 쓰입니다. 많은 시스템에서 packet pointer는 4-byte alignment에서 2 bytes 뒤에 있습니다. Ethernet header를 건너뛰도록 14 bytes를 더하고 IHL을 읽어 `IHL * 4`를 더하면 variable offset은 어떤 n에 대해 `4n+2`입니다. 여기에 `NET_IP_ALIGN` 2 bytes를 더하면 4-byte aligned가 되어 word 크기 접근이 안전합니다.

`PTR_TO_SOCKET`과 `PTR_TO_SOCKET_OR_NULL`도 socket lookup 반환값의 모든 복사본에 공통 `id`를 사용합니다. map value의 NULL 정제와 비슷하지만 pointer의 reference도 추적합니다. `PTR_TO_SOCKET`은 대응하는 `struct sock` reference를 암시하므로 reference leak을 막으려면 반드시 NULL 검사하고, non-NULL 경로에서는 유효한 reference를 socket release function에 넘겨야 합니다.

직접 packet 접근과 기본 range 검사

`cls_bpf`와 `act_bpf` 프로그램에서 verifier는 `skb->data`와 `skb->data_end` pointer를 통한 packet data 직접 접근을 허용합니다.

1:  r4 = *(u32 *)(r1 +80)  /* load skb->data_end */
2:  r3 = *(u32 *)(r1 +76)  /* load skb->data */
3:  r5 = r3
4:  r5 += 14
5:  if r5 > r4 goto pc+16
R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
6:  r0 = *(u16 *)(r3 +12) /* access 12 and 13 bytes of the packet */

instruction #5의 `if (skb->data + 14 > skb->data_end) goto err` 검사를 통과해 fall-through한 경우 `skb->data`를 가리키는 `R3`에서 최소 14 bytes를 직접 읽을 수 있습니다. verifier는 이를 `R3=pkt(id=0,off=0,r=14)`로 표시하므로 #6의 2-byte load는 안전합니다.

• `id=0`: register에 추가 변수를 더하지 않았습니다.
• `off=0`: 추가 상수를 더하지 않았습니다.
• `r=14`: `[R3, R3 + 14)` byte 범위를 안전하게 접근할 수 있습니다.

`R5=pkt(id=0,off=14,r=14)`도 packet data를 가리키지만 상수 14가 추가되어 현재 위치는 `skb->data + 14`입니다. 접근 가능 범위는 `[R5, R5 + 14 - 14)`, 즉 0 bytes입니다.

가변 packet offset과 scalar 범위 전파

더 복잡한 packet 접근은 다음과 같은 상태 변화를 만듭니다.

R0=inv1 R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
6:  r0 = *(u8 *)(r3 +7) /* load 7th byte from the packet */
7:  r4 = *(u8 *)(r3 +12)
8:  r4 *= 14
9:  r3 = *(u32 *)(r1 +76) /* load skb->data */
10:  r3 += r4
11:  r2 = r1
12:  r2 <<= 48
13:  r2 >>= 48
14:  r3 += r2
15:  r2 = r3
16:  r2 += 8
17:  r1 = *(u32 *)(r1 +80) /* load skb->data_end */
18:  if r2 > r1 goto pc+2
R0=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R1=pkt_end R2=pkt(id=2,off=8,r=8) R3=pkt(id=2,off=0,r=8) R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)) R5=pkt(id=0,off=14,r=14) R10=fp
19:  r1 = *(u8 *)(r3 +4)

`R3=pkt(id=2,off=0,r=8)`에서 `id=2`는 `r3 += rX` instruction을 두 번 보았다는 뜻입니다. 따라서 `R3`는 packet 안의 어떤 가변 offset을 가리킵니다. 프로그램이 instruction #18에서 `if (r3 + 8 > r1) goto err`를 검사했으므로 안전 범위는 `[R3, R3 + 8)`입니다.

verifier는 packet register에 `add`와 `sub`만 허용합니다. 다른 연산을 하면 register 상태가 `SCALAR_VALUE`로 바뀌어 직접 packet 접근에 더는 사용할 수 없습니다.

`r3 += rX`가 overflow하여 원래 `skb->data`보다 작은 주소가 될 수 있으므로 verifier는 이를 방지해야 합니다. `rX`가 16-bit보다 큰 값이면 이후 `r3`와 `skb->data_end`의 bounds check에서 range 정보를 얻지 않으며, 그 pointer로 읽으려 하면 `invalid access to packet` 오류가 납니다.

instruction #7의 byte load 뒤 `R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff))`입니다. 상위 56 bits는 0이고 하위 8 bits는 알 수 없다는 뜻입니다. `r4 *= 14` 뒤에는 최대값이 3570이고 14가 짝수이므로 최하위 bit가 0인 `R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe))`가 됩니다.

마찬가지로 `r2 >>= 48`은 sign extension을 하지 않으므로 `R2=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff))`를 만듭니다. 이 계산은 `adjust_reg_min_max_vals()`에 구현되어 있으며 pointer와 scalar를 더할 때는 `adjust_ptr_min_max_vals()`, scalar끼리 연산할 때는 `adjust_scalar_min_max_vals()`를 호출합니다.

일반 C 코드로 작성하는 직접 packet 접근

이 범위 추적의 결과로 BPF 프로그램 작성자는 다음처럼 일반 C 코드로 packet에 직접 접근할 수 있습니다.

void *data = (void *)(long)skb->data;
void *data_end = (void *)(long)skb->data_end;
struct eth_hdr *eth = data;
struct iphdr *iph = data + sizeof(*eth);
struct udphdr *udp = data + sizeof(*eth) + sizeof(*iph);

if (data + sizeof(*eth) + sizeof(*iph) + sizeof(*udp) > data_end)
        return 0;
if (eth->h_proto != htons(ETH_P_IP))
        return 0;
if (iph->protocol != IPPROTO_UDP || iph->ihl != 5)
        return 0;
if (udp->dest == 53 || udp->source == 9)
        ...;

프로그램은 Ethernet, IP, UDP header 전체가 `data_end` 안에 있는지 먼저 확인한 뒤 protocol과 field를 읽습니다. 이 방식은 `LD_ABS` instruction을 사용하는 것보다 프로그램을 작성하기 쉽고 실행도 훨씬 빠릅니다.

상태 포함 관계를 이용한 경로 pruning

verifier는 실제로 프로그램의 모든 가능한 경로를 끝까지 걷지 않습니다. 새 branch를 분석할 때 같은 instruction에서 이전에 만난 모든 상태를 살펴보고, 그 가운데 하나가 현재 상태를 subset으로 포함하면 branch를 `prune`합니다. 이전의 더 일반적인 상태가 승인되었다면 현재 상태도 승인될 수 있기 때문입니다.

예를 들어 이전 상태의 `r1`이 packet pointer였고 현재 상태의 `r1`이 적어도 같은 alignment 제약을 가지면서 안전 range가 같거나 더 길다면 현재 `r1`도 안전합니다. 이전 상태에서 `r2`가 `NOT_INIT`이었다면 그 지점 이후 어떤 경로에서도 `r2`를 사용할 수 없었으므로 현재 `r2`의 어떤 값도, 다른 `NOT_INIT`도 안전합니다. 이 검사는 `regsafe()`에 구현되어 있습니다.

pruning은 register뿐 아니라 stack과 stack에 spill된 register까지 고려합니다. branch를 prune하려면 모두 안전해야 하며 전체 상태 비교는 `states_equal()`에 구현되어 있습니다.

register와 stack slot liveness 추적

state pruning을 효과적으로 만들기 위해 각 register와 stack slot의 liveness를 추적합니다. 핵심은 프로그램 exit에 도달할 때까지 이후 실행에서 실제로 쓰이는 register와 stack slot을 알아내는 것입니다. 한 번도 사용되지 않은 항목은 cached state에서 제거할 수 있어 더 많은 상태가 같은 cached state와 동등해집니다.

0: call bpf_get_prandom_u32()
1: r1 = 0
2: if r0 == 0 goto +1
3: r0 = 1
--- checkpoint ---
4: r0 = r1
5: exit

instruction #4에 state cache entry를 만들었다고 가정합니다. 아래에서 이런 entry를 `checkpoint`라고도 합니다. verifier는 이 instruction에 `r0=1, r1=0` 또는 `r0=0, r1=0` 두 상태 가운데 하나로 도달할 수 있습니다.

• `r0 = 1, r1 = 0`
• `r0 = 0, r1 = 0`

그러나 검증을 성공적으로 끝내는 데 중요한 값은 `r1`뿐입니다. liveness tracking algorithm은 이 사실을 찾아 `r0`의 차이를 무시하고 두 상태가 실제로 동등하다고 판정하는 것이 목표입니다.

기본 verifier 오류: 도달성, 초기화와 stack 범위

다음 예들은 잘못된 eBPF 프로그램과 verifier log에 나타나는 오류 메시지입니다.

첫 프로그램은 첫 `BPF_EXIT_INSN()` 뒤에 도달할 수 없는 두 번째 exit instruction을 두므로 `unreachable insn 1`로 거부됩니다.

static struct bpf_insn prog[] = {
BPF_EXIT_INSN(),
BPF_EXIT_INSN(),
};

unreachable insn 1

다음 프로그램은 초기화하지 않은 `BPF_REG_2`를 읽으므로 `R2 !read_ok`가 발생합니다.

BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
BPF_EXIT_INSN(),

0: (bf) r0 = r2
R2 !read_ok

다음 프로그램은 `R2`만 초기화하고 program return value인 `R0`을 설정하지 않은 채 exit하여 `R0 !read_ok`로 거부됩니다.

BPF_MOV64_REG(BPF_REG_2, BPF_REG_1),
BPF_EXIT_INSN(),

0: (bf) r2 = r1
1: (95) exit
R0 !read_ok

다음 store는 frame pointer `R10`의 양수 offset `+8`에 8 bytes를 쓰므로 stack 범위를 벗어나 `invalid stack off=8 size=8`이 발생합니다.

BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0),
BPF_EXIT_INSN(),

0: (7a) *(u64 *)(r10 +8) = 0
invalid stack off=8 size=8

간접 stack read와 잘못된 map fd

다음 프로그램은 `R10 - 8`의 주소를 `map_lookup_elem()` key argument로 넘기지만 그 8-byte stack 영역을 먼저 초기화하지 않았습니다. helper가 stack을 간접 읽으려 하므로 `invalid indirect read from stack off -8+0 size 8`로 거부됩니다.

BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_EXIT_INSN(),

0: (bf) r2 = r10
1: (07) r2 += -8
2: (b7) r1 = 0x0
3: (85) call 1
invalid indirect read from stack off -8+0 size 8

이어지는 프로그램은 stack key를 먼저 0으로 초기화하지만 `map_fd=0`이 유효한 `bpf_map`을 가리키지 않습니다. 따라서 helper call에서 `fd 0 is not pointing to valid bpf_map` 오류가 납니다.

BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_EXIT_INSN(),

0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 0x0
4: (85) call 1
fd 0 is not pointing to valid bpf_map

map lookup의 NULL 검사와 alignment 오류

`map_lookup_elem()`은 `PTR_TO_MAP_VALUE_OR_NULL`을 반환합니다. 다음 프로그램은 반환값이 `NULL`인지 검사하지 않고 `R0`을 통해 바로 map element에 쓰므로 `R0 invalid mem access 'map_value_or_null'`로 거부됩니다.

BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
BPF_EXIT_INSN(),

0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 0x0
4: (85) call 1
5: (7a) *(u64 *)(r0 +0) = 0
R0 invalid mem access 'map_value_or_null'

다음 프로그램은 반환값의 NULL 검사는 올바르게 수행하지만 8-byte store를 map value의 offset 4에서 시작합니다. 8-byte alignment를 만족하지 않아 `misaligned access off 4 size 8` 오류가 납니다.

BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
BPF_EXIT_INSN(),

0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 1
4: (85) call 1
5: (15) if r0 == 0x0 goto pc+1
 R0=map_ptr R10=fp
6: (7a) *(u64 *)(r0 +4) = 0
misaligned access off 4 size 8

branch마다 달라지는 pointer 형식

다음 프로그램은 `map_lookup_elem()` 반환값을 NULL과 비교한 뒤 non-NULL branch에서는 정렬된 offset 0에 올바르게 접근합니다. 그러나 NULL branch에서도 `R0`을 address로 사용해 store합니다.

BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
BPF_EXIT_INSN(),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1),
BPF_EXIT_INSN(),

0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 1
4: (85) call 1
5: (15) if r0 == 0x0 goto pc+2
 R0=map_ptr R10=fp
6: (7a) *(u64 *)(r0 +0) = 0
7: (95) exit

from 5 to 8: R0=imm0 R10=fp
8: (7a) *(u64 *)(r0 +0) = 1
R0 invalid mem access 'imm'

instruction #5의 한 경로에서 `R0=map_ptr`이므로 #6의 store는 안전합니다. 반대 경로에서는 `R0=imm0`인데 #8에서 이를 memory pointer로 사용하므로 `R0 invalid mem access 'imm'`로 거부됩니다. verifier는 모든 branch가 안전해야 프로그램 전체를 승인합니다.

socket lookup reference 누수

다음 프로그램은 `bpf_sk_lookup_tcp()`으로 socket reference를 얻은 뒤 반환 pointer를 NULL 검사하거나 release하지 않고 `R0=0`으로 덮어씁니다. verifier는 allocation instruction #7에서 만든 reference id 1이 해제되지 않았음을 보고합니다.

BPF_MOV64_IMM(BPF_REG_2, 0),
BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_MOV64_IMM(BPF_REG_3, 4),
BPF_MOV64_IMM(BPF_REG_4, 0),
BPF_MOV64_IMM(BPF_REG_5, 0),
BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN(),

0: (b7) r2 = 0
1: (63) *(u32 *)(r10 -8) = r2
2: (bf) r2 = r10
3: (07) r2 += -8
4: (b7) r3 = 4
5: (b7) r4 = 0
6: (b7) r5 = 0
7: (85) call bpf_sk_lookup_tcp#65
8: (b7) r0 = 0
9: (95) exit
Unreleased reference id=1, alloc_insn=7

마지막 프로그램도 socket lookup 반환값을 NULL 검사하지 않고 release하지 않은 채 exit합니다. 반환 pointer를 덮어쓰지 않았더라도 살아 있는 reference가 program end까지 남으므로 같은 `Unreleased reference id=1, alloc_insn=7` 오류가 발생합니다.

BPF_MOV64_IMM(BPF_REG_2, 0),
BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_MOV64_IMM(BPF_REG_3, 4),
BPF_MOV64_IMM(BPF_REG_4, 0),
BPF_MOV64_IMM(BPF_REG_5, 0),
BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
BPF_EXIT_INSN(),

0: (b7) r2 = 0
1: (63) *(u32 *)(r10 -8) = r2
2: (bf) r2 = r10
3: (07) r2 += -8
4: (b7) r3 = 4
5: (b7) r4 = 0
6: (b7) r5 = 0
7: (85) call bpf_sk_lookup_tcp#65
8: (95) exit
Unreleased reference id=1, alloc_insn=7

`PTR_TO_SOCKET_OR_NULL`은 먼저 NULL 검사를 거쳐야 하며, non-NULL 경로에서는 대응하는 socket release function을 호출해 reference를 정확히 한 번 해제해야 합니다.