Coupling policy iteration with semi-definite relaxation to compute accurate numerical invariants in static analysis

摘要

We introduce a new domain for finding precise numerical invariants ofprograms by abstract interpretation. This domain, which consists of level setsof non-linear functions, generalizes the domain of linear "templates"introduced by Manna, Sankaranarayanan, and Sipma. In the case of quadratictemplates, we use Shor's semi-definite relaxation to derive computable yetprecise abstractions of semantic functionals, and we show that the abstractfixpoint equation can be solved accurately by coupling policy iteration andsemi-definite programming. We demonstrate the interest of our approach on aseries of examples (filters, integration schemes) including a degenerate one(symplectic scheme).