Decomposing refinement proofs using assume-guarantee reasoning

Henzinger TA, Qadeer S, Rajamani S. 2000. Decomposing refinement proofs using assume-guarantee reasoning. Proceedings of the 13th International Conference on Computer Aided Design. ICCAD: Computer-Aided Design, 245–252.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Author
Henzinger, Thomas AISTA ; Qadeer, Shaz; Rajamani, Sriram
Abstract
Model-checking algorithms can be used to verify, formally and automatically, if a low-level description of a design conforms with a high-level description. However, for designs with very large state spaces, prior to the application of an algorithm, the refinement-checking task needs to be decomposed into subtasks of manageable complexity. It is natural to decompose the task following the component structure of the design. However, an individual component often does not satisfy its requirements unless the component is put into the right context, which constrains the inputs to the component. Thus, in order to verify each component individually, we need to make assumptions about its inputs, which are provided by the other components of the design. This reasoning is circular: component A is verified under the assumption that context B behaves correctly, and symmetrically, B is verified assuming the correctness of A. The assume-guarantee paradigm provides a systematic theory and methodology for ensuring the soundness of the circular style of postulating and discharging assumptions in component-based reasoning.We give a tutorial introduction to the assume-guarantee paradigm for decomposing refinement-checking tasks. To illustrate the method, we step in detail through the formal verification of a processor pipeline against an instruction set architecture. In this example, the verification of a three-stage pipeline is broken up into three subtasks, one for each stage of the pipeline.
Publishing Year
Date Published
2000-01-01
Proceedings Title
Proceedings of the 13th International Conference on Computer Aided Design
Page
245 - 252
Conference
ICCAD: Computer-Aided Design
Conference Location
San Jose, CA, United States of America
Conference Date
2000-11-05 – 2000-11-09
ISBN
IST-REx-ID

Cite this

Henzinger TA, Qadeer S, Rajamani S. Decomposing refinement proofs using assume-guarantee reasoning. In: Proceedings of the 13th International Conference on Computer Aided Design. IEEE; 2000:245-252. doi:10.1109/ICCAD.2000.896481
Henzinger, T. A., Qadeer, S., & Rajamani, S. (2000). Decomposing refinement proofs using assume-guarantee reasoning. In Proceedings of the 13th International Conference on Computer Aided Design (pp. 245–252). San Jose, CA, United States of America: IEEE. https://doi.org/10.1109/ICCAD.2000.896481
Henzinger, Thomas A, Shaz Qadeer, and Sriram Rajamani. “Decomposing Refinement Proofs Using Assume-Guarantee Reasoning.” In Proceedings of the 13th International Conference on Computer Aided Design, 245–52. IEEE, 2000. https://doi.org/10.1109/ICCAD.2000.896481.
T. A. Henzinger, S. Qadeer, and S. Rajamani, “Decomposing refinement proofs using assume-guarantee reasoning,” in Proceedings of the 13th International Conference on Computer Aided Design, San Jose, CA, United States of America, 2000, pp. 245–252.
Henzinger TA, Qadeer S, Rajamani S. 2000. Decomposing refinement proofs using assume-guarantee reasoning. Proceedings of the 13th International Conference on Computer Aided Design. ICCAD: Computer-Aided Design, 245–252.
Henzinger, Thomas A., et al. “Decomposing Refinement Proofs Using Assume-Guarantee Reasoning.” Proceedings of the 13th International Conference on Computer Aided Design, IEEE, 2000, pp. 245–52, doi:10.1109/ICCAD.2000.896481.

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search