hide
Free keywords:
-
Abstract:
Geometric heuristics for the quantifier elimination approach presented by Kapur
(2004) are investigated to automatically derive loop invariants expressing
weakly relational numerical properties (such as l ≤ x ≤ h or l ≤ \pm x
\pm y ≤q h) for imperative programs.
Such properties have been successfully used to analyze commercial software
consisting of hundreds of thousands of lines of code (using for example, the
Astrée tool based on abstract interpretation framework proposed by Cousot and
his group).
The main attraction of the proposed approach is its much lower
complexity in contrast to the abstract interpretation approach (O(n^2) in
contrast to O(n^4), where n is the number of variables) with the ability to
still generate invariants of comparable strength.
This approach has been generalized to consider disjunctive invariants of the
similar form, expressed using maximum function (such as \max(x+a,y+b,z+c,d)
≤ \max(x+e,y+f,z+g,h)), thus enabling automatic generation of a subclass of
disjunctive
invariants for imperative programs as well.
