Journal article

A Fresh Look at Zones and Octagons

Graeme Gange, Zequn Ma, Jorge A Navas, Peter Schachte, Harald Søndergaard, Peter J Stuckey

ACM Transactions on Programming Languages and Systems | Association for Computing Machinery (ACM) | Published : 2021


Zones and Octagons are popular abstract domains for static program analysis. They enable the automated discovery of simple numerical relations that hold between pairs of program variables. Both domains are well understood mathematically but the detailed implementation of static analyses based on these domains poses many interesting algorithmic challenges. In this article, we study the two abstract domains, their implementation and use. Utilizing improved data structures and algorithms for the manipulation of graphs that represent difference-bound constraints, we present fast implementations of both abstract domains, built around a common infrastructure. We compare the performance of these im..

View full abstract