An Under-Approximate Relational Logic

Title:	An Under-Approximate Relational Logic
Author:	Toby Murray
Submission date:	2020-03-12
Abstract:	Recently, authors have proposed under-approximate logics for reasoning about programs. So far, all such logics have been confined to reasoning about individual program behaviours. Yet there exist many over-approximate relational logics for reasoning about pairs of programs and relating their behaviours. We present the first under-approximate relational logic, for the simple imperative language IMP. We prove our logic is both sound and complete. Additionally, we show how reasoning in this logic can be decomposed into non-relational reasoning in an under-approximate Hoare logic, mirroring Beringer’s result for over-approximate relational logics. We illustrate the application of our logic on some small examples in which we provably demonstrate the presence of insecurity.
BibTeX:	@article{Relational-Incorrectness-Logic-AFP, author = {Toby Murray}, title = {An Under-Approximate Relational Logic}, journal = {Archive of Formal Proofs}, month = mar, year = 2020, note = {\url{http://isa-afp.org/entries/Relational-Incorrectness-Logic.html}, Formal proof development}, ISSN = {2150-914x}, }
License:	BSD License
Status: [ok]	This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.