Formal verification of cache systems using refinement relations

A formal verification method for concurrent systems is presented. The technique shows a correspondence between automata representing an implementation and specification behavior. The correspondence is called a refinement relation, and is particularly well-suited for theorem-provers. Since the method does not rely on enumerating all the states, it can be applied to systems with an infinite or unknown number of states. This substantially expands the class of hardware designs that can be formally verified. The method is illustrated by proving the consistency of a concurrent, non-deterministic model of cache memory. The proof is carried out using the HOL (higher-order logic) theorem-prover