Formalizing the Linux eBPF Core ISA: A Mechanized Operational Semantics and Its Real-World Applications
Open Access
- 1 October 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (OOPSLA2) , 62-90
Abstract
This paper presents a mechanized formal semantics for the Linux eBPF instruction set architecture (ISA). We develop a small-step semantics in Rocq that faithfully formalizes all 153 sequential in-kernel instructions of the eBPF ISA. The semantics is fully executable and has been validated against the official Linux eBPF test suite. This extensive testing revealed inconsistencies in our original formalization. Using this semantics, we have designed, implemented, and verified the soundness of the bit-level abstract domain employed by the Linux eBPF verifier. Our semantics also complements the existing Linux eBPF documentation by providing a rigorous formal specification. During the formalization process, we have discovered previously unknown bugs in the Linux eBPF implementation, and developed new verifier optimizations; the corresponding kernel patches have been upstreamed.Keywords
Funding Information
- ZJNSF Major Program (LD24F020013)
- Zhejiang Pioneer (Jianbing) Project (2024C01032)
- NSFC (62502431)
- NSFC (62532012)
- National Science Foundation (62572427)
- Zhejiang Key Laboratory Project (2024E10001)
- Fundamental Research Funds for the Central Universities of China (226-2024-00140)
This publication has 29 references indexed in Scilit:
- Structural Operational Semantics for Functional and Security Verification of Pipelined Processors2025
- End-to-End Mechanized Proof of a JIT-Accelerated eBPF Virtual Machine for IoT2024
- Verifying the Verifier: eBPF Range Analysis Verification2023
- End-to-End Mechanized Proof of an eBPF Virtual Machine for Micro-controllers2022
- Relaxed virtual memory in Armv8-A2022
- Synthesizing JIT Compilers for In-Kernel DSLs2020
- The Lean Theorem Prover (System Description)2015
- Validating Register Allocation and Spilling2010
- Z3: An Efficient SMT Solver2008
- Isabelle/HOL2002