### 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.

### License

BSD License

### Topics

- Computer science/Programming languages/Logics
- Computer science/Security

### Session Relational-Incorrectness-Logic

- RelationalIncorrectness

## Cite

×

Relational-Incorrectness-Logic-AFP

    @article{Relational-Incorrectness-Logic-AFP,
      author  = {Toby Murray},
      title   = {An Under-Approximate Relational Logic},
      journal = {Archive of Formal Proofs},
      month   = {March},
      year    = {2020},
      note    = {\url{https://isa-afp.org/entries/Relational-Incorrectness-Logic.html},
                 Formal proof development},
      ISSN    = {2150-914x},
    }

Download

## Download

× Download latest

Older releases:

- Sep 13, 2023 : Isabelle2023
- Oct 27, 2022 : Isabelle2022
- Dec 14, 2021 : Isabelle2021-1
- Feb 23, 2021 : Isabelle2021
- Apr 20, 2020 : Isabelle2020
- Mar 26, 2020 : Isabelle2019