Machine-checked proofs for realizability checking algorithms

Andreas Katis, Andrew Gacek, Michael W. Whalen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


Virtual integration techniques focus on building architectural models of systems that can be analyzed early in the design cycle to try to lower cost, reduce risk, and improve quality of complex embedded systems. Given appropriate architectural descriptions, assume/guarantee contracts, and compositional reasoning rules, these techniques can be used to prove important safety properties about the architecture prior to system construction. For these proofs to be meaningful, each leaf-level component contract must be realizable; i.e., it is possible to construct a component such that for any input allowed by the contract assumptions, there is some output value that the component can produce that satisfies the contract guarantees. We have recently proposed (in [1]) a contract-based realizability checking algorithm for assume/guarantee contracts over infinite theories supported by SMT solvers such as linear integer/real arithmetic and uninterpreted functions. In that work, we used an SMT solver and an algorithm similar to k-induction to establish the realizability of a contract, and justified our approach via a hand proof. Given the central importance of realizability to our virtual integration approach, we wanted additional confidence that our approach was sound. This paper describes a complete formalization of the approach in the Coq proof and specification language. During formalization, we found several small mistakes and missing assumptions in our reasoning. Although these did not compromise the correctness of the algorithm used in the checking tools, they point to the value of machine-checked formalization. In addition, we believe this is the first machine-checked formalization for a realizability algorithm.

Original languageEnglish (US)
Title of host publicationVerified Software
Subtitle of host publicationTheories, Tools, and Experiments - 7th International Conference, VSTTE 2015, Revised Selected Papers
EditorsSanjit A. Seshia, Arie Gurfinkel
PublisherSpringer- Verlag
Number of pages14
ISBN (Print)9783319296128
StatePublished - Jan 1 2016
Event7th International Conference on Verified Software: Theories, Tools, and Experiments, VSTTE 2015 - San Francisco, United States
Duration: Jul 18 2015Jul 19 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference7th International Conference on Verified Software: Theories, Tools, and Experiments, VSTTE 2015
Country/TerritoryUnited States
CitySan Francisco

Bibliographical note

Publisher Copyright:
© Springer International Publishing Switzerland 2016.


Dive into the research topics of 'Machine-checked proofs for realizability checking algorithms'. Together they form a unique fingerprint.

Cite this