Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning

• DOI: 10.1145/3586045
• Publication Date: 2023-04-06T21:06:02Z
• Authors: Noam Zilberstein; Derek Dreyer; Alexandra Silva
• Keywords: FOS: Computer and information sciences; Computer Science - Logic in Computer Science; Computer Science - Programming Languages; 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology; Logic in Computer Science (cs.LO); Programming Languages (cs.PL)

Program logics for bug-finding (such as the recently introduced Incorrectness Logic) have framed correctness and incorrectness as dual concepts requiring different logical foundations. In this paper, we argue that a single unified theory can be used for both correctness and incorrectness reasoning. We present Outcome Logic (OL), a novel generalization of Hoare Logic that is both monadic (to capture computational effects) and monoidal (to reason about outcomes and reachability). OL expresses true positive bugs, while retaining correctness reasoning abilities as well. To formalize the applicability of OL to both correctness and incorrectness, we prove that any false OL specification can be disproven in OL itself. We also use our framework to reason about new types of incorrectness in nondeterministic and probabilistic programs. Given these advances, we advocate for OL as a new foundational theory of correctness and incorrectness.