Relative Completeness of Abstraction Refinement for Software Model Checking

Automated methods for an undecidable class of verification problems cannot be complete (terminate for every correct program). We therefore consider a new kind of quality measure for such methods, which is completeness relative to a (powerful but unrealistic) oracle-based method. More precisely, we ask whether an often implemented method known as “software model checking with abstraction refinement” is complete relative to fixpoint iteration with “oracle-guided” widening. We show that whenever backward fixpoint iteration with oracle-guided widening succeeds in proving a property j (for some sequence of widenings determined by the oracle) then software model checking with a particular form of backward refinement will succeed in proving j . Intuitively, this means that the use of fixpoint iteration over abstractions and a particular backwards refinement of the abstractions has the effect of exploring the entire statespace of all possible sequences of widenings.