개요
eBPF프로그램의 안정성은 두 가지 단계를 통해서 확보된다.
첫번째로는 DAG체크를 통해서 루프를 허용하지 않는 것이며, CFG체크이다. CFG는 도달할 수 없는 코드가 eBPF에 있는지를 검사한다.
두번째 단계는 첫번째 Instruction에서 모든 가능한 경로를 탐색하는 것이다. 이는 모든 명령어를 실제 가상의 Verifier내부에서 시뮬레이션 하여서 레지스터와 스택에 어떠한 변화가 있는지를 검사하는 것이다.
모든 프로그램의 시작은 레지스터 R1이 Context에 대한 포인터를 가지는 것 부터 시작한다. R1은 시작시점에 BPF register type으로 매핑된다. 만약 정적 검사기가 명령어가 R2=R1처럼 R2에 복사되는 것을 발견하면 그 후 R2는 R1과 같은 타입 (여기서는 PTR_TO_CTX)를 가지게 된다. 만약 R3=R1+R2이면 R3는 SCALAR_VALUE를 가지게 된다. 이는 두개의 포인터의 합은 Invalid한 포인터를 만들기 때문이다. (만약 포인터 연산을 허용하지 않는 Unprivilege eBPF에서는 이러한 연산 자체가 Reject되는 이유가 된다.)
레지스터의 연산에는 다음과 같은 주요한 규칙들이 있다.
- 만약 레지스터가 쓰여지지 않으면 읽을 수 없다. (즉 쓰레기 값을 읽는 것을 허용하지 않는다.)
- Helper function이후에 R1-R5는 unreadable로 마킹되며 R0는 리턴값을 가지고 있다.
- R6-R9는 Calle save 레지스터로 Helper function이후에도 보존된다.
- load/store 명령어는 PTR_TO_CTX, PTR_TO_MAP, PTR_TO_STACK에 대해서 만 동작하며 offset과 alignment체크를 수행한다.
- 모든 R1레지스터는 프로그램 시작 시점에서 PTR_TO_CTX으로 시작한다. (즉 struct bpf_context)
- Stack에 Spill된 레지스터는 추적되며, Invalid한 접근을 막는다.
- Helper function에 전달되는 레지스터는 커널이 선언한 타입과 같은 타입이어야 한다.
BPF_register_type
모든 eBPF레지스터는 다음중 하나의 Type으로 Mapping되게 된다. 모든 접근 하지 레지스터 혹은 Helper function call이후의 R1-R5레지스터는 NOT_INIT으로 매핑된다. 레지스터 타입은 다음중하나의 값을 가진다.
NOT_INIT = 0, /* nothing was written into register */
SCALAR_VALUE, /* reg doesn't contain a valid pointer */
PTR_TO_CTX, /* reg points to bpf_context */
CONST_PTR_TO_MAP, /* reg points to struct bpf_map */
PTR_TO_MAP_VALUE, /* reg points to map element value */
PTR_TO_MAP_KEY, /* reg points to a map element key */
PTR_TO_STACK, /* reg == frame_pointer + offset */
PTR_TO_PACKET_META, /* skb->data - meta_len */
PTR_TO_PACKET, /* reg points to skb->data */
PTR_TO_PACKET_END, /* skb->data + headlen */
PTR_TO_FLOW_KEYS, /* reg points to bpf_flow_keys */
PTR_TO_SOCKET, /* reg points to struct bpf_sock */
PTR_TO_SOCK_COMMON, /* reg points to sock_common */
PTR_TO_TCP_SOCK, /* reg points to struct tcp_sock */
PTR_TO_TP_BUFFER, /* reg points to a writable raw tp's buffer */
PTR_TO_XDP_SOCK, /* reg points to struct xdp_sock */
PTR_TO_BTF_ID,
/* PTR_TO_BTF_ID_OR_NULL points to a kernel struct that has not
* been checked for null. Used primarily to inform the verifier
* an explicit null check is required for this struct.
*/
PTR_TO_MEM, /* reg points to valid memory region */
PTR_TO_BUF, /* reg points to a read/write buffer */
PTR_TO_FUNC, /* reg points to a bpf program function */
/* Extended reg_types. */
PTR_TO_MAP_VALUE_OR_NULL = PTR_MAYBE_NULL | PTR_TO_MAP_VALUE,
PTR_TO_SOCKET_OR_NULL = PTR_MAYBE_NULL | PTR_TO_SOCKET,
PTR_TO_SOCK_COMMON_OR_NULL = PTR_MAYBE_NULL | PTR_TO_SOCK_COMMON,
PTR_TO_TCP_SOCK_OR_NULL = PTR_MAYBE_NULL | PTR_TO_TCP_SOCK,
PTR_TO_BTF_ID_OR_NULL = PTR_MAYBE_NULL | PTR_TO_BTF_ID,
포인터는 Offset + Base로 구성되며 Static하게 정해진 범위가 있다. Static verifier는 이러한 범위를 추적하면서 현재 포인터 접근이 Valid한 접근인지를 계속 추적해준다. SCALAR_VALUE또한 Range가 정해지는데, 이는 스칼라 값이 레지스터의 가능한 범위내에서 Overflow와 같은 일이 일어나는 것을 막기 위해서이다. 정리하면 각 변수 값은 다음과 같은 정보가 추적된다.
- Offset과 Base (포인터에 한하여)
- 포인터가 NULL값을 가질 수 있는지 (포인터에 한하여) - OR_NULL이 바로 이 정보이다.
- Unsigned으로서의 Max, Min (스칼라 값에 한하여)
- Signed으로서의 Max, Min (스칼라 값에 한하여)
- Verifier가 추적하는 알수있는 비트들 (스칼라 값에 한하여). 이는 변수 추적에 활용된다. 예를 들어서, 어떤 변수의 아래 2 비트를 1로 매핑하면 Verfiier는 이 두 비트가 1에 해당하는 값을 가지고 있음을 추적한다. 이를 통해서 통제할 수 있는 접근과 통제할 수 없는 접근을 추적한다.
예를 들어서 브랜치 명령어(IF > 8)를 만났다고 해보자. 그럼 정적 검사기는 8보다 크다고 선언된 브랜치의 부분에서는 MIN값이 9가 되고 아닌 브랜치에서는 MAX값이 8이 된다. 이를 정보를 내부 브랜치에서 정적 검사기는 더 다양한 정보를 가지고 이 변수를 테스트 할 수 있다. 예를 들어서 포인터 + 스칼라가 있다고 해보자. MIN이 8보다 작은 브랜치 내부에서는 아무리 포인터가 크더라도 Base + offset은 Base + 8이 넘을 수 없다. 이를 통해서 Valid한 접근인지를 파악하는 것이다.
이외에도 PTR_PACKET이나 MAP처럼 특정 ID정보를 가지고(메타데이터) 접근의 Valid를 평가하는 로직이 Static verifier에는 마련되어 있다.
Pruning
정적 검사기는 모든 가능한 경로를 탐색하지는 않는다. 정적 검사에 소요되는 시간을 줄이기 위해서, 만약 현재 검사할려고 하는 레지스터나 스택의 상태가 전에 검사한 같은 명령어의 정보와 비교하여 전의 정보가 subset인 경우에는, 그러한 경로의 탐색은 Pruning(가지치기) 된다.
Register liveness tracking
레지스터와 스택의 상태를 추적하면서, 현재있는 상태가 Valid한지를 체크하는데, 이때 만약 사용되지 않은 스택이나 레지스터의 부분이 있으면 계속 추적할 필요가 없을 것이다. 따라서 사용되지 않는 레지스터나 스택의 Slot은 Cache된 State에서 삭제되어서, Pruning에서 Subset으로 이용하는데 사용되지 않는다.