On Incorrectness Logic and Kleene Algebra with Top and Tests
This work provides a foundational equational framework for program verification, specifically enabling reasoning about incorrectness for while-like programs, which is incremental as it builds on existing KAT theory.
The paper tackled the problem of reasoning about program incorrectness using Kleene algebra with tests (KAT), showing that KAT cannot express incorrectness logic due to its inability to handle codomains, and addressed this by extending to TopKAT, which successfully expresses incorrectness triples and proves all rules sound.
Kleene algebra with tests (KAT) is a foundational equational framework for reasoning about programs, which has found applications in program transformations, networking and compiler optimizations, among many other areas. In his seminal work, Kozen proved that KAT subsumes propositional Hoare logic, showing that one can reason about the (partial) correctness of while programs by means of the equational theory of KAT. In this work, we investigate the support that KAT provides for reasoning about incorrectness, instead, as embodied by Ohearn's recently proposed incorrectness logic. We show that KAT cannot directly express incorrectness logic. The main reason for this limitation can be traced to the fact that KAT cannot express explicitly the notion of codomain, which is essential to express incorrectness triples. To address this issue, we study Kleene Algebra with Top and Tests (TopKAT), an extension of KAT with a top element. We show that TopKAT is powerful enough to express a codomain operation, to express incorrectness triples, and to prove all the rules of incorrectness logic sound. This shows that one can reason about the incorrectness of while-like programs by means of the equational theory of TopKAT.