Sound, Precise, and Fast Abstract Interpretation with Tristate Numbers
Authors:
- 2 April 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 254-265
Abstract
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.Keywords
All Related Versions
Funding Information
- National Science Foundation
This publication has 22 references indexed in Scilit:
- RockSalt2012
- A Method for Symbolic Computation of Abstract Operations2012
- Testing Static Analyzers with Randomly Generated Programs2012
- A few billion lines of code laterCommunications of the ACM, 2010
- Verification of device drivers and intelligent controllers2007
- Deriving abstract transfer functions for analyzing embedded softwareACM SIGPLAN Notices, 2006
- The octagon abstract domainHigher-Order and Symbolic Computation, 2006
- Symbolic Implementation of the Best Transformer2004
- Abstract Interpretation Based Formal Methods and Future Challenges2001
- A generalized theory of bit vector data flow analysisACM Transactions on Programming Languages and Systems, 1994