Abstract Counterexample-based Refinement for Powerset Domains

Roman Manevich, John Field, Thomas A. Henzinger, Ganesan Ramalingam, and Mooly Sagiv

Counterexample-guided abstraction refinement (CEGAR) is a powerful technique to scale automatic program analysis techniques to large programs. However, so far it has been used primarily for model checking in the context of predicate abstraction. We formalize CEGAR for general powerset domains. If a spurious abstract counterexample needs to be removed through abstraction refinement, there are often several choices, such as which program location(s) to refine, which abstract domain(s) to use at different locations, and which abstract values to compute. We define several plausible preference orderings on abstraction refinements, such as refining as "late" as possible and as "coarse" as possible. We present generic algorithms for finding refinements that are optimal with respect to the different preference orderings. We also compare the different orderings with respect to desirable properties, including the property if locally optimal refinements compose to a global optimum. Finally, we point out some difficulties with CEGAR for non-powerset domains.

In Program Analysis and Compilation: Theory and Practice, Lecture Notes in Computer Science 4444, Springer, 2007, pp. 273-292.

Download inofficial, sometimes updated PostScript / PDF document. © 2007 Springer.