Formalizing Counterexample-driven Refinement with Weakest Preconditions

To check a safety property of a program, it is sufficient to check the property on an abstraction that has more behaviors than the original program. If the safety property holds of the abstraction then it also holds of the original program. However, if the property does not hold of the abstraction along some trace t (a counterexample), it may or may not hold of the original program on trace t . If it can be proved that the property does not hold in the original program on trace t then it makes sense to refine the abstraction to eliminate the “spurious counterexample” t (rather than a report a known false negative to the user). The SLAM tool developed at Microsoft Research implements such an automated abstraction-refinement process. In this paper, we reformulate this process for a tiny while language using the concepts of weakest preconditions, bounded model checking and Craig interpolants. This representation of SLAM simplifies and distills the concepts of counterexample-driven refinement in a form that should be suitable for teaching the process in a few lectures of a graduate-level course.