Abstract Domains of Affine Relations

Matt Elder, Junghee Lim, Tushar Sharma, Tycho Andersen, and Thomas Reps
University of Wisconsin

This paper considers some known abstract domains for affine-relation analysis (ARA), along with several variants, and studies how they relate to each other. We show that the abstract domains of Müller-Olm/Seidl (MOS) and King/Søndergaard (KS) are, in general, incomparable, but give sound interconversion methods. We also show that the methods of King and Søndergaard can be applied without bit-blasting—while still using a bit-precise concrete semantics.

(Click here to access the paper: PDF; Extended version with proofs (TR-1691); (c) Springer-Verlag.)