Abstract This paper proposes an automated method to check the correctness of range analysis used in the Linux kernel ’s eBPF verifier. We provide the specification of soundness for range analysis performed by the eBPF verifier. We automatically generate verification conditions that encode the operation of the eBPF verifier directly from the Linux kernel ’s C source code and check it against our specification. When we discover instances where the eBPF verifier is unsound, we propose a method to generate an eBPF program that demonstrates the mismatch between the abstract and the concrete semantics. Our prototype automatically checks the soundness of 16 versions of the eBPF verifier in the Linux kernel versions ranging from 4.14 to 5.19. In this process, we have discovered new bugs in older versions and proved the soundness of range analysis in the latest version of the Linux kernel.

Extended Berkeley Packet Filter (BPF) is a language and run-time system that allows non-superusers to extend the Linux and Windows operating systems by downloading user code into the kernel. To ensure that user code is safe to run in kernel context, BPF relies on a static analyzer that proves properties about the code, such as bounded memory access and the absence of operations that crash. The BPF static analyzer checks safety using abstract interpretation with several abstract domains. Among these, the domain of tnums (tristate numbers) is a key domain used to reason about the bitwise uncertainty in program values. This paper formally specifies the tnum abstract domain and its arithmetic operators. We provide the first proofs of soundness and optimality of the abstract arithmetic operators for tnum addition and subtraction used in the BPF analyzer. Further, we describe a novel sound algorithm for multiplication of tnums that is more precise and efficient (runs 33% faster on average) than the Linux kernel’s algorithm. Our tnum multiplication is now merged in the Linux kernel.

Trusted Applications (TAs) written for Trusted Execution Environments (TEEs) using ARM TrustZone are currently written in C; there is limited support for higher-level languages. This leads to common manual memory management problems like buffer overflow and use-after-free. Higher-level languages, which have managed runtimes, allow for automated memory management, the benefits of which are widely accepted. To allow for automated memory management of TAs, we need to have a runtime that handles allocation and garbage collection (GC). However, having the entire allocator and GC in the secure world would increase the Trusted Computing Base (TCB) of the secure world. We propose TrustGC, a mechanism to partition garbage collection and allocation between the secure world and the normal world. TrustGC allows for automated memory management of TAs by leveraging the help of a GC partly running in the normal world.