Reproduce “The Octagon Abstract Domain” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Antoine Miné
Antoine Miné from École Normale Supérieure de Paris introduced the Octagon Abstract Domain, a new numerical abstract domain for static program analysis capable of representing invariants of the form "|x ± y| ≤ c". This domain offers O(n^2) memory and O(n^3) time complexity for its operations, providing an intermediate balance of precision and cost between interval and polyhedral analysis.
Key insights
- The "strong closure" algorithm provides a unique and canonical normal form for non-empty octagons, which is fundamental for precise equality/inclusion testing and for deriving saturation properties essential for other abstract operators.
- While the strong closure and emptiness test algorithms are proven correct and efficient for real/rational numbers, they are incomplete for integer variables within the O(n^3) framework due to implied non-integer bounds.
- The widening operator, crucial for ensuring termination in loops, functions optimally when its left argument is not strongly closed, a finding that contrasts with some previous approaches in abstract interpretation.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.