리눅스 커널의 eBPF 검증기(verifier)는 사용자 제공 프로그램 실행 전 안전성을 보장하기 위해 추상 해석(abstract interpretation)을 사용합니다. 이는 각 레지스터를 여러 간격 도메인(interval domains)과 비트 단위 도메인(bitwise domain, 트라이스테이트 숫자/tristate numbers)으로 추적합니다. 조건부 분기점에서 추상 상태를 정제하는 과정은 도메인 전반에 걸쳐 상호 모순되는 제약 조건을 생성할 수 있으며, 이는 도달 불가능한 경로(unreachable path)를 나타냅니다.
그러나 검증기는 공집합($\bot$) 표현을 갖추지 못하여 이러한 도메인들이 빈 교차(empty intersection)를 가질 때 이를 감지할 수 없으며, 이로 인해 데드 경로를 분석하게 됩니다. 이러한 모순적인 상태를 도메인 축소(domain reduction) 또는 다운스트림 연산자(downstream operators)에 전달하는 것은 해당 연산자의 암묵적인 비공집합 전제 조건(non-emptiness precondition)을 위반하여, 도메인 불변성 위반(domain invariant violations)을 유발합니다. 이는 리눅스 커널에서 수년간 지속된 문제로, 운영 중단(production outages), 오탐지 거부(false rejections), 그리고 상태 폭발(state explosion)을 야기해 왔습니다.
본 논문은 eBPF 검증기의 추상 도메인 전반에 걸쳐 데드 브랜치를 가지치기하기 위한 건전하고 완전한(sound and complete) 상수 시간 빈도 확인(constant-time emptiness check)을 제시합니다. 우리는 간격과 비볼록 도메인이 개별 값을 스캔하지 않고 O(1) 시간에 교차하는지 테스트하는 일반적인 프레임워크인 추상 단계 함수(abstract step functions)를 도입합니다. 또한, 트라이스테이트 비트마스크를 만족하는 다음 정수로 점프하는, 형식적으로 검증된 상수 시간 연산자인 tnum_step을 개발했습니다. tnum_step을 사용하여, 분기점 정제 과정 중 모순적인 상태를 감지하고 도달 불가능한 브랜치를 즉시 가지치기하여 데드 브랜치 불변성 위반의 근본 원인을 제거하는 다중 도메인 빈도 확인 기능을 설계했습니다.
우리의 기술은 불변성 위반, 상태 폭발 및 오탐지 거부를 방지하는 동시에, Cilium과 같은 리눅스 커널 자가 테스트(selftests) 및 운영 제품군 전반에 걸쳐 무시할 수 있는 수준의 (1.48%) 오버헤드만을 발생시킵니다. 우리의 tnum_step 연산자는 메인라인 리눅스 커널로 상위 통합(upstreamed)되었습니다.