eBPF Verifier는 무엇인가?

들어가며

eBPF에 대한 첫 번째 포스트에서 Verifier에 대한 정의와 역할을 간단히 짚어 보았다. 이번 포스트에선 조금 더 심층적으로 Verifier에 대해 다뤄 보려고 한다.

Verifier

eBPF Program이 Hook Point에 부착되어 실행되기 위해 컴파일 되기 전 단계에서 안전성을 검사하는 역할을 수행한다.

안전성이란 무엇인가?

Verifier는 Kernel Level에서 동작하는 eBPF Program이 Kernel에 악영향을 주지 않고 안전하게 동작하는지 검증하는 구성 요소다. 여기서 말하는 악영향이란 메모리 손상, 민감 정보 유출, 커널 충돌 또는 커널 정지/Deadlock 발생 등을 말한다.
Verifier는 프로그램이 갖는 가능한 모든 경우의 수를 수학적으로 검사한다. 허용되지 않는 상황은 다음과 같다.

• 프로그램이 항상 종료되는가? (무한 루프, 무한 재귀 등 금지)
• 프로그램이 허용된 영역 외 다른 임의의 메모리 영역을 읽는가? (민감 정보 접근)
• 네트워크 프로그램이 패킷 범위를 벗어난 다른 메모리에 접근하는가? (민감 정보 접근)
• 프로그램 간 Deadlock 발생 방지를 위해 보유하고 있는 Lock(Spin Lock)을 해제 하는가?
• 프로그램이 초기화 되지 않은 메모리에 대한 읽기를 수행하는가?

대표적으로 Verifier가 검사하는 항목의 예시이고 외에도 프로그램 유형별로 추가 규칙 등이 있다. 정리 해보면 작성된 eBPF Program이 Kernel Level의 안정성을 훼손할만한 동작을 가지고 있는지 검사하는 것이다.

Verifier의 분석 과정

앞서 Verifier는 프로그램이 갖는 가능한 모든 경우의 수를 수학적으로 검사한다고 했다. 이때 가장 먼저 하는 것이 eBPF Program 코드를 순회하면서 분기 명령어를 기반으로 Graph를 구성하는 것이다.
Graph 구성을 통해 Entry Point에서 시작해서 실행 흐름을 분석했을 때 어떤 경로로도 실행될 수 없다면 모두 거부한다. 예를 들어 return 뒤에 어떤 코드가 있다면 거부한다는 뜻이다.
실행될 수 없는 코드를 "Dead Code"라고 하는데 이들은 실행되지 않더라도 커널 메모리 공간을 차지하게 되는데, 해당 영역으로 Jump하여 악성 체인을 만들수도 있고, 커널의 다른 취약점을 이용하여 Code Reuse Attack과 같은 실행 흐름을 강제로 돌리는 공격을 수행할 수 있기 때문이다.

Code Reuse Attack

정상적인 코드 조각(Gadget)을 재조립하여 원하는 행위를 수행하도록 하는 공격 기법

다음으로 레지스터를 설정하여 명령어 순회를 통해 레지스터와 스택의 상태를 업데이트한다. 상태 정보에는 smax32(이 레지스터에 저장될 수 있는 가장 큰 32비트 정수)와 같은 정보가 포함된다. 해당 정보를 통해 Verifier는 조건 분기가 잘 실행되는지 여부를 검증할 수 있다.
Verifier는 분기 명령을 지날 때마다 현재 상태를 두 갈래로 나누고, 그중 하나의 분기 결과와 상태를 큐에 저장한 다음 상태를 업데이트 한다. 두 갈래로 나누는 이유는 결정론적 안정성 보장, 정밀한 범위 추적, 상태 폭발 방지를 위해서다.

• 결정론적 안정성 보장
  eBPF 프로그램은 어떤 경우에도 안전한 코드여야 한다. 프로그램 내 분기(if)는 런타임 입력 값에 따라 실행 경로를 결정하는데, Verifier가 동작하는 단계에선 입력값이 무엇인지 알 수 없기 때문에 조건이 참인 경우, 거짓인 경우 모두 독립적으로 가정하고 검증해야 한다.

• 정밀한 범위 추적
  분기문을 지나는 순간 레지스터가 가질 수 있는 값은 이전보다 좁아진다. 좁아진 범위 정보는 다음 명령어에서 메모리 주소를 계산할 때 해당 주소가 유효한 범위 내에 있는지 확인하는 근거가 된다.

• 상태 폭발 방지
  모든 경로를 나누면 경우의 수가 기하급수적으로 늘어나는 상태 폭발 문제가 발생하는데, 이때 큐에 저장된 다른 분기 정보를 검사한 결과 값을 통해 검사 상태와 동일하거나 더 타이트한 하위 집합인 상태가 확인되면 검사를 조기 종료시켜 효율성을 확보한다.

결론적으로 상태를 나누는 행위는 eBPF가 제공하는 런타임 오버헤드가 없는 안전성을 구현하기 위한 장치인 것이다.
또한 값뿐만 아니라 데이터 타입도 추적한다. 정수인지 Map 값에 대한 Pointer인지 검사하여 Context에서 offset을 역참조할 때마다 현재 프로그램 유형에 대해 허용 여부와 offset이 Context 범위 내에 있는지 확인한다.
이러한 유형 정보 검사를 통해 Helper 함수 호출 또는 일반적인 함수 호출에 올바른 매개변수가 전달되는지 확인한다.

Context

여기서 말하는 Context는 처리해야 할 데이터 구조체 포인터라고 생각하면 된다.

BTF(BPF Type Format)를 사용하여 Map 값에 타이머 또는 스핀락이 포함되어 있는지 확인할 수 있고, 올바른 매개변수가 KFunc에 전달되는지, BTF 함수가 실제 BPF 함수와 일치하는지 등도 검사한다.

SpinLock

스핀락은 Mutex, Semaphor와 같이 공유 자원에 대한 상호 배타를 위해 사용된다. 공유 자원에 대한 lock을 획득할 때까지 Thread가 멈추지 않고 루프를 돌며(busy-waiting) 재시도하는 동기화 기법이다.

Verifier가 검사를 수행하는 과정을 보면 꽤나 복잡하여 하드웨어 리소스를 많이 소모할거 같지만 상태를 저장할 수 있는 공간에 제한을 두어 Kernel Level에 안전성을 훼손하지 않으면서 검사를 한다. Kernel 버전 5.2까지 명령어 제한이 약 4,000개, 복잡도 제한이 약 128,000으로 제한됐지만 이후 버전에서 둘 다 100만까지 늘어났다.

Verifier 특징

• Tail Call을 활용한 검증 로직 분산 및 최적화
  Tail Call은 현재 실행 중인 eBPF 프로그램의 실행을 종료하고, 다른 eBPF 프로그램의 진입점으로 제어권을 넘긴다. 일반적인 함수 호출과 달리 복귀 주소를 스택에 쌓지 않으므로, 호출한 프로그램으로 되돌아오지 않는 일방향 점프 방식이다. 단일 프로그램에 적용되는 Verifier의 명령어 수 및 상태 분기 제한을 극복하기 위해 대규모 로직을 여러 프로그램으로 분할하여 로드할 수 있게 하여 전체 시스템의 검증 부하를 낮춘다.
  하지만 무한 루프 및 리소스 고갈 문제가 있을 수 있어 Tail Call 호출을 33회로 제한한다. 또한, Program Array Map을 참조하여 수행해서 호출 시점의 컨텍스트 타입이 대상 프로그램과 호환되는지를 확인한다.

• Dead Code 제거
  앞서 언급한 Dead Code로 발생할 수 있는 문제를 4.15 버전에서는 NOP 상태로 정의하여 실행 불가능한 상태로 만들었고, 5.1 버전에서는 성능 최적화도 고려해서 코드를 실제로 삭제하여 분기 구조를 단순화 했다. 하지만 이런 삭제와 분기 단순화 과정은 복잡하여 Verifier가 안전하다고 판단한 코드가 실제로 안전하지 않은 위치로 점프할 가능성이 존재했기 때문에 CAP_BPF, CAP_SYS_ADMIN과 같은 높은 권한이 있는 프로그램에만 이를 허용한다.

마치며

이번 포스트에선 eBPF Program이 컴파일 되기 전 단계인 검증하는 로직을 자세히 알아봤다. Map에 대한 동작은 이해하기 쉬웠는데 검증 로직을 담당하는 Verifier에 대해서 이해하는 데까지 많은 사전 지식이 필요했던거 같다.
다음 포스트에선 eBPF Function에 대해 더 심층적으로 알아보는 시간을 갖도록 하겠다.