Abstract Interpretation over Bitvectors
Abstract
Most critical applications, such as airplane and rocket controllers, need correctness guarantees. Usually these correctness guarantees can be described as safety properties in the form of assertions. Verifying an assertion amounts to showing that the assertion holds true for all possible runs of an application. Abstract interpretation is a method to automatically verify a program by soundly abstracting the concrete executions of the program to elements in an abstract domain, and checking the correctness guarantees using the abstraction. However, traditional abstract domains treat the machine integers as mathematical integers. As a result, the conclusions drawn from such an abstract interpretation are, in general, unsound. In other words, the assertions shown to be true by traditional abstract interpretation approaches might actually be false because the underlying point space does not faithfully model bit-vector arithmetic. This dissertation advances the field of abstract interpretation by providing sound abstraction techniques and abstract-domain frameworks that faithfully model bit-vector semantics. We focus on numerical abstract domains for bitvectors, which can provide equality and inequality invariants. The first part of the dissertation focuses on abstract domains capable of expressing bit-vector-sound equality invariants. The performance and precision of two equality domains is compared, and sound inter-conversion methods are provided. Furthermore, we generalize one of the equality domains to develop a new abstract-domain framework that is capable of expressing a certain class of disjunctions over bit-vector-sound equality constraints. This framework can be instantiated with any relational or non-relational base abstract domain over bitvectors. The second part of the dissertation focuses on abstract domains capable of expressing bit-vector-sound inequality invariants. We develop an abstract domain that is capable of expressing a certain class of bit-vectors.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2017
- Accession Number
- AD1165859
Entities
People
- Tushar Sharma
Organizations
- University of Wisconsin–Madison