  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.
