Gradual Exact Logic Unifying Hoare Logic and Incorrectness Logic via Gradual Verification

Conrad Zimmerman, Jenna DiVincenzo · 2024

Read Gradual Exact Logic Unifying Hoare Logic and Incorrectness Logic via Gradual Verification by Conrad Zimmerman, Jenna DiVincenzo (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-00339.txt.

Introduction

Conrad Zimmerman and Jenna DiVincenzo unify program logics in two thousand twenty four. Gradual verification blends static checks with runtime checks smoothly. It was built before on overapproximating logics like Hoare logic. Underapproximating logics, such as incorrectness logic, find real bugs instead.

They define gradual exact logic from exact logic directly. Static verification inside gradual verification links to both logic families. Hoare logic and incorrectness logic both restate in the new terms. Gradual verification itself also falls out of the definition. Tools may now serve verification and bug finding together.

Catalog record

CREATORConrad Zimmerman, Jenna DiVincenzo
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-00339

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Gradual Exact Logic Unifying Hoare Logic and Incorrectness Logic via Gradual Verification Conrad Zimmerman, Jenna DiVincenzo Abstract . Previously, gradual verification has been developed using overapproximating logics such as Hoare logic. We show that the static verification component of gradual verification is also connected to underapproximating logics like incorrectness logic. To do this, we use a novel definition of gradual verification and a novel gradualization of exact logic ( Maksimovic et al., 2023 ) which we call gradual exact logic . Further, we show that Hoare logic, incorrectness logic, and gradual verification can be defined in terms of gradual exact logic. We hope that this connection can be used to develop tools and techniques that apply to both gradual verification and bug-finding. For example, we envision that techniques defined in terms of exact logic can be directly applied to verification, bug-finding, and gradual verification, using the principles of gradual typing ( Garcia et al., 2016 ) . 1. Overview Incorrectness logic ( O’Hearn, 2020 ) has been recently developed as a formal basis for “true bug-finding” and has been applied in industrial-strength tools ( Le et al., 2022 ) . Deductions in this logic prove reachability, which enables bug-finding tools to prove the existence of an invalid state while selectively exploring the possible paths. At the same time, gradual verification (GV) ( Bader et al., 2018 ) addresses the complexity of traditional static verification. Gradually verified programs may contain imprecise specifications —logical formulas annotated to indicate that they contain only a partial specification of behavior. A gradual verifier checks the imprecise specifications using static verification where it can and run-time checks (i.e. dynamic verification) elsewhere. These run-time checks can be exercised, e.g. with testing, giving the programmer confidence that their code will not enter a state that violates their partial specifications. Using gradual verification, programmers can incrementally verify a program, incrementally learn verification constructs, and safely guard unverified components. More recent work ( Zilberstein et al., 2023 ; Maksimovic et al., 2023 ; Lööw et al., 2024 ) has produced logics and tools that unify over-approximating (OX) logic, often used in verification, and under-approximating (UX) logics including IL. In this paper, we propose another unification of OX and UX logics that we derive using the principles of gradual verification. The resulting characterization of IL demonstrates a previously unexplored connection between GV and IL. 1.1. Hoare logic A triple in Hoare logic (HL) ( Hoare, 1969 ) is denoted \{P\}~C~\{Q\} . ( P,Q refer to logical specifications; C refers to a program statement.) Semantically, the triple is valid if, for every state \sigma\in P (i.e., P is true of \sigma ), when \sigma\stackrel{{\scriptstyle C}}{{\to}}\sigma^{\prime} (i.e., executing C results in \sigma^{\prime} ), then \sigma^{\prime}\in Q : P Q \overset{C}{\longrightarrow} Thus HL is an overapproximating (OX) logic—the postcondition Q overapproximates the states that are reachable from P ; precisely, Q\supseteq\{\sigma^{\prime}\mid\exists\sigma\in P:\sigma\overset{C}{\to}\sigma^{\prime}\} . HL is a formal foundation for program verification precisely because the postcondition is true in all ending states. 1.2. Incorrectness logic A triple in incorrectness logic (IL) ( O’Hearn, 2020 ) is denoted [P]~C~[Q] 1 1 1 IL triples often include a specification for error states, but we omit error handling to simplify the comparison with other logics. . Semantically, the triple is valid if, for every \sigma^{\prime}\in Q , there is some \sigma\in P such that \sigma\overset{C}{\to}\sigma^{\prime} : P Q \stackrel{{\scriptstyle C}}{{\longrightarrow}} Thus IL is an underapproximating (UX) logic—the postcondition Q underapproximates the states that are reachable from P ; precisely, Q\subseteq\{\sigma^{\prime}\mid\exists\sigma\in P:\sigma\overset{C}{\to}\sigma^{\prime}\} . Interpreting Q as a specification of a bug, IL is a logic for finding bugs since a valid triple indicates that the bug is reachable. 1.3. Gradual verification Gradual verification (GV) ( Bader et al., 2018 ) reduces the burden of static verification by allowing incomplete ( imprecise ) specifications. A gradual verifier may make optimistic assumptions when verifying imprecisely-specified code. Typically, the final program is elaborated to check these assumptions at run-time. However, in this work we focus solely on the static verification component of GV so that we can compare its logic with HL and IL. We denote imprecise triples by \{\textnormal{{?}}\wedge P\}~C~\{Q\} . Intuitively, this triple is valid if there is some P^{\prime}\Rightarrow P such that \{P^{\prime}\}~C~\{Q\} is valid in HL. One can think of ? as representing the additional assumptions introduced by P^{\prime} . For example, the following imprecise triple is valid: \{{\color[rgb]{0.75,0,0.25}\textnormal{{?}}}\wedge\top\}~x\coloneq x+1~\{x>0\} This follows from the validity of \{{\color[rgb]{0.75,0,0.25}x\geq 0}\wedge\top\}~x\coloneq x+1~\{x>0\}. That is, the postcondition is ensured when assuming x\geq 0 . However, the assumptions must be plausible; formally, P^{\prime} (and thus P ) must be satisfiable (i.e., P^{\prime}\not\equiv\bot ). Otherwise, all imprecise triples would be vacuously valid by taking P^{\prime}\equiv\bot . With this in mind, GV can be stated as a reachability problem—semantically, \{\textnormal{{?}}\wedge P\}~C~\{Q\} is valid if there exists some states \sigma and \sigma^{\prime} such that \sigma\in P , \sigma\overset{C}{\to}\sigma^{\prime} , and \sigma^{\prime}\in Q : P Q \stackrel{{\scriptstyle C}}{{\longrightarrow}} By contrapositive, the triple is invalid (i.e., static verification will error) if it is never possible for C to ensure Q , given P . By comparing this diagram with those in § 1.1 and § 1.2 , we can deduce that HL and IL triples are valid imprecise triples, except for vacuous cases where P\equiv\bot in HL or Q\equiv\bot in IL. Our semantic definition of validity is equivalent to the previous definition which uses Hoare triples: Let P^{\prime} be a formula that represents \sigma as specifically as possible, then (intuitively) \{P^{\prime}\}~C~\{Q\} is valid since \sigma\overset{C}{\to}\sigma^{\prime} and \sigma^{\prime}\in Q . But, we can also define valid imprecise triples in terms of IL— \{\textnormal{{?}}\wedge P\}~C~\{Q\} is valid if [P]~C~[Q^{\prime}] is valid for some Q^{\prime}\Rightarrow Q . In § 2.5 we will prove these definitions equivalent. 2. Formal foundations We will now sketch our formal definitions and results. See the appendices for the full statements and proofs. (1) We define gradual exact logic —a consistent lifting ( Garcia et al., 2016 ) of exact logic ( Maksimovic et al., 2023 ) . (2) We show that HL, IL, and GV can be characterized by gradual exact logic. (3) We show that GV contains OX and UX deductions. (4) We show that, for imprecise specifications, GV can be equivalently defined using OX or UX logics. 2.1. Exact logic Exact logic (EL) ( Maksimovic et al., 2023 ) is the intersection of HL and IL: an EL triple (P)~C~(Q) is valid if \{P\}~C~\{Q\} and [P]~C~[Q] are both valid. Deductions are thus exact —they can neither under- or overapproximate behavior (see Appendix E for rules). 2.2. Gradual exact logic We further define gradual exact logic ( \widetilde{\text{EL}} ) as a consistent lifting ( Garcia et al., 2016 ) of EL. First, some definitions: Formula denotes all formulas in FOL with arithmetic; we call these precise . SatFormula denotes all satisfiable formulas. An imprecise formula is of the form \textnormal{{?}}\wedge P where P\in\textsc{Formula} . A gradual formula \widetilde{P}\in\widetilde{\textsc{F}}\textsc{ormula} can be either precise or imprecise. The concretization \gamma:\widetilde{\textsc{F}}\textsc{ormula}\to\mathcal{P}(\textsc{Formula}) interprets a gradual formulas as sets of precise formulas: \gamma(\textnormal{{?}}\wedge P)=\{P^{\prime}\in\textsc{SatFormula}\mid P^{\prime}\Rightarrow P\},\quad\gamma(P)=\{P\} Let \vdash(P)~C~(Q) denote a valid EL triple. Deductions in \widetilde{\text{EL}} , denoted \mathrel{\widetilde{\vdash}}(\widetilde{P})~C~(\widetilde{Q}) , are defined as a consistent lifting of EL deductions ( Section

Read the complete text