Relational program logics in decomposed style
Lennart Beringer · 2010
Suppose you have developed a Hoare logic for your favorite programming language. You have justified the logic by defining an operational model of the language and constructing a soundness proof that interprets triples as partial correctness assertions. Now you want to interpret program analyses, validate security properties such as noninterference, or justify program transformations. You observe that all these properties are relational: they are naturally phrased over pairs of executions, for programs that are either identical or closely related. Is your program logic up to the task? This article shows how to formally decompose terminationinsensitive relational program logics into judgements from unary logics. We develop relational predicate transformers, present laws that govern their decomposition along the phrase structure, and relate them to their unary counterparts. We apply our findings to justify variants of Benton’s Relational Hoare Logic (RHL) for a language with objects, extend the logics to auxiliary state, derive a noninterference analysis in the style of Banerjee-Naumann, and develop relational interpretations of separation logic. As related executions do not have to refer to the same program syntax or employ the same notion of state, decomposition can in principle be applied to cross-language verification problems, as long as suitable one-execution logics exist.