Polynomial approximations of the relational semantics of imperative programs

We present a static analysis that approximates the relational semantics of imperative programs by systems of low-degree polynomial equalities. Our method is based on Abstract Interpretation in a lattice of polynomial pseudo ideals — finite-dimensional vector spaces of degree-bounded polynomials that are closed under degree-bounded products. For a fixed degree bound, the sizes of bases of pseudo ideals and the lengths of chains in the lattice of pseudo ideals are bounded by polynomials in the number of program variables. Despite the approximate nature of our analysis, for several programs taken from the literature on non-linear polynomial invariant generation our method produces results that are as precise as those produced by methods based on polynomial ideals and Gröbner bases.