Assume-guarantee Refinement Between Different Time Scales

Thomas A. Henzinger, Shaz Qadeer, and Sriram K. Rajamani

Refinement checking is used to verify implementations against more abstract specifications. Assume-guarantee reasoning is used to decompose refinement proofs in order to avoid state-space explosion. In previous approaches, specifications are forced to operate on the same time scale as the implementation. This may lead to unnatural specifications and inefficiencies in verification. We introduce a novel methodology for decomposing refinement proofs of temporally abstract specifications, which specify implementation requirements only at certain sampling instances in time. Our new assume-guarantee rule allows separate refinement maps for specifying functionality and timing. We present the theory for the correctness of our methodology, and illustrate it using a simple example. Support for sampling and the generalized assume-guarantee rule have been implemented in the model checker Mocha and successfully applied to verify the VGI multiprocessor dataflow chip with 6 million transistors.

Proceedings of the 11th International Conference on Computer-Aided Verification (CAV), Lecture Notes in Computer Science 1633, Springer, 1999, pp. 208-221.

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