Combining Axiomatic Models for Refinement Proofs
This work offers a foundational framework for combining refinement proofs with axiomatic logics, benefiting verification researchers and practitioners by clarifying the relationship between these formal methods.
The paper provides a uniform account of several axiomatic program logics and shows how simulation relations transfer safety properties between specifications and implementations, reducing simulation obligations to triples in standard logics. The approach is illustrated on a concurrent counter example.
Refinement proofs verify an implementation by showing that its behaviours are subsumed by a simpler specification, on which safety properties are easier to establish. We study how such proofs interact with the axiomatic program logics used to verify the specification. We first give a uniform account of Hoare, Incorrectness, Lisbon, and Necessary-Preconditions logic, classified by the direction in which each constrains a transition and by whether it over- or under-approximates its target set. We then show that simulation relations transfer state-based safety properties: a forward simulation carries a Hoare (inductive) invariant of the specification to one of the implementations, and forward and backward simulations both carry ordinary invariants, via the pre-image of the relation. Finally, we characterize, within these logics, when a relation is a simulation, forward simulations by the validity of Hoare or Lisbon triples, backward simulations by Necessary-Preconditions or Incorrectness triples, so that the simulation obligation reduces to a triple in an off-the-shelf functional logic. We illustrate the development with a concurrent counter, transporting a safety bound from an atomic sequential specification to a Left--Right implementation through an intermediate nondeterministic-concurrent counter, with a forward simulation on one side and a backward simulation on the other.