Reproduce “A Deductive System for Contract Satisfaction Proofs” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Arthur Correnson, Haoyi Zeng, Jana Hofmann

Researchers from CISPA Helmholtz Center, Harvard University, and MPI-SP developed a formal deductive system for proving hardware-software contract satisfaction, leveraging a novel alternating fixpoint-based relative bisimulation and parameterized coinduction. This system, formally verified in Rocq, provides a sound and complete framework for handling 4-ary asynchronous execution comparisons, demonstrated on speculative and out-of-order processor models.

Key insights

  • Contract satisfaction is a hyperproperty requiring 4-ary relational reasoning that compares two contract traces with two hardware traces, formalized as "relative trace equality".
  • Sound and complete verification of contract satisfaction for asynchronous systems necessitates a "relative bisimulation" defined by an alternating greatest and least fixpoint, addressing limitations of simpler bisimulations.
  • Parameterized Coinduction (Paco) provides a framework for modular and incremental construction of relational invariants, making complex 4-ary proofs tractable within interactive proof assistants.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.