Relational Abstract Domain of Weighted Hexagons

AbstractWe propose a new numerical abstract domain for static analysis by abstract interpretation, the domain of Weighted Hexagons. It is capable of expressing interval constraints and relational invariants of the form x⩽a⋅y, where x and y are variables and a denotes a non-negative constant. This kind of domain is useful in analysis of safety for array accesses when multiplication is used (e.g. in guarding formulæ or in access expressions). We provide all standard abstract domain operations, including widening operator, as well as a graph-based algorithm for checking satisfiability and computing normal form for elements of the domain. All described operations are performed in O(n3) time. Expressiveness of this domain lies between the Pentagons by Logozzo and Fähndrich and the Two Variables Per Inequality by Simon, King and Howe