A Program Logic for Abstract (Hyper)Properties
Paolo Baldan, Roberto Bruni, Francesco Ranzato, Diletta Rigo · 2026
Read A Program Logic for Abstract (Hyper)Properties by Paolo Baldan, Roberto Bruni, Francesco Ranzato, Diletta Rigo (2026) 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-2601-20370.txt.
Introduction
Paolo Baldan, Roberto Bruni, Francesco Ranzato, and Diletta Rigo introduce APPL, a program logic for abstract properties. Program logics are rule systems for proving facts about code. APPL is a unifying Hoare-style logic that subsumes standard Hoare logic, incorrectness logic, and several forms of hyper Hoare logic.
The logic is parameterized by an abstract domain, which sets how properties are approximated. One framework then covers many existing logics and new ones built from fresh abstractions. A common base could simplify the design of verifiers that must prove both correctness and security properties of programs.
Catalog record
| CREATOR | Paolo Baldan, Roberto Bruni, Francesco Ranzato, Diletta Rigo |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-20370
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Program Logic for Abstract (Hyper)Properties Paolo Baldan, Roberto Bruni, Francesco Ranzato, Diletta Rigo Abstract . We introduce APPL (Abstract Program Property Logic), a unifying Hoare-style logic that subsumes standard Hoare logic, incorrectness logic, and several variants of Hyper Hoare logic. APPL provides a principled foundation for abstract program logics parameterised by an abstract domain, encompassing both existing and novel abstractions of properties and hyperproperties. The logic is grounded in a semantic framework where the meaning of commands is first defined on a lattice basis and then extended to the full lattice via additivity. Crucially, nondeterministic choice is interpreted by a monoidal operator that need not be idempotent nor coincide with the lattice join. This flexibility allows the framework to capture collecting semantics, various classes of abstract semantics, and hypersemantics. The APPL proof system is sound, and it is relatively complete whenever the property language is sufficiently expressive. When the property language is restricted to an abstract domain, the result is a sound abstract deduction system based on best correct approximations. Relative completeness with respect to a corresponding abstract semantics is recovered provided the abstract domain is complete, in the sense of abstract interpretation, for the monoidal operator. † † ccs: Theory of computation Logic and verification † † ccs: Theory of computation Abstraction † † ccs: Theory of computation Programming logic † † ccs: Theory of computation Semantics and reasoning † † ccs: Theory of computation Program analysis † † ccs: Theory of computation Hoare logic † † ccs: Theory of computation Abstraction † † ccs: Theory of computation Program reasoning 1. Introduction Since the seminal work of Hoare ( Hoare69 ) , program logics have constituted a cornerstone of formal reasoning about program properties. The underlying idea is simple yet effective: Hoare’s logical system for partial correctness formalizes assertions of the form \langle\mathit{pre}\rangle\,\mathsf{code}\,\langle\mathit{post}\rangle, meaning that, starting from any state satisfying the precondition \mathit{pre} , if the program execution terminates, it will reach a state satisfying the postcondition \mathit{post} . The properties of the elementary operations invoked by a program provide the axioms of the logic, while syntax-directed rules enable the compositional derivation of properties for compound programs. A crucial component of the framework is the ability to reason via approximation by strengthening preconditions and weakening postconditions. Consequently, classical Hoare logic reasons about over-approximations of program behaviour and is designed to establish program correctness , that is, to prove the absence of undesirable behaviours. In recent years, logics based on under-approximation have garnered significant attention, following the work of O’Hearn on incorrectness logic ( OHearn20 ) . These logics aim to prove program incorrectness by witnessing the presence of actual bugs rather than certifying their absence. This shift in perspective has spurred the development of various new systems, focusing either exclusively on incorrectness reasoning ( RDB:LRAPB ; RaadVO24 ) or on combining correctness and incorrectness within unified frameworks ( ZDS:OL ; BGGR21 ; BruniGGR23 ; AscariBG25 ) . The landscape of program logics has expanded further with the growing interest in hyperproperties , as they relate multiple execution traces of the same program. Hyperproperties arise naturally in the analysis of determinism, non-interference, and other security-related concerns. This domain has given rise to dedicated logics and semantic frameworks, including ( MP:HSFF ; MP:VBSCH ; DM:HHL ; CousotW25 ; ZhangZK024 ; MastroeniP19 ) . The Problem. Given the proliferation of program logics, several authors have sought to bring order to this “zoo,” by developing either systematic taxonomies ( VerschtK25 ; AscariBGL25 ; Cousot24 ; MP:HSFF ) or unifying frameworks that recover multiple logics as instances ( ZDS:OL ; Zil:toplas ; CousotW25 ) . However, most approaches either neglect abstraction (of properties or hyperproperties) or address it only marginally. Notable exceptions include ( Cousot24 ; CousotW25 ) , which promote a calculational approach to logic design from semantic definitions, and ( MP:HSFF ; DM:HHL ) , which focus on the definition and abstraction of hypersemantics. In this work, we address the challenge of devising a single program logic that simultaneously captures many reasoning modalities—correctness, incorrectness, and hyperproperty reasoning—while systematically integrating abstraction in the sense of abstract interpretation ( CC77 ; cousot21 ) . Main Contributions. Our core programming language is a Kleene Algebra with Tests (KAT) ( KozenKAT ) , parametric in the choice of elementary commands. The semantics is defined over an interpretation monoid (D,\sqsubseteq,\oplus,\operatorname{B}) , comprising a complete lattice (D,\sqsubseteq) equipped with a distinguished basis \operatorname{B} that generates D via joins, and an infinitary monoidal operator \oplus satisfying specific distributivity properties with respect to lattice joins. Crucially, non-deterministic choice is interpreted via this monoidal operator \oplus , which is notably not required to coincide with the lattice join and need not be idempotent. Command semantics are first defined on the lattice basis \operatorname{B} and then extended to the full lattice D by additivity. This structure subsumes collecting semantics, a wide range of abstract semantics, and several forms of hypersemantics. Within this framework, we introduce a Hoare-style logic, denoted APPL (Abstract Program Property Logic). Its assertions range over a chosen subset of the semantic lattice, which serves as the property language. The proof system supports the derivation of judgments of the form \vdash\langle h\rangle\ \mathsf{r}\ \langle k\rangle , where \mathsf{r} is a program and h,k are behavioural properties. As in standard Hoare logic, such a judgment expresses that whenever execution starts in a configuration satisfying the precondition h , the postcondition k is an admissible approximation (according to the lattice order) of the configurations reachable after executing \mathsf{r} . The logic is sound by construction and is relatively complete whenever the property language is sufficiently expressive, in particular, when it is extensional , namely, it contains all elements of the interpretation monoid. By suitably instantiating the parameters of the framework—the complete lattice D , the monoidal operator \oplus , and the basis \operatorname{B} —we recover several well-known logics. Classical Hoare logic is obtained by taking D=\wp({\mathit{States}}) ordered by subset inclusion, with \oplus=\cup and an arbitrary basis. Hyper Hoare logics in the style of Dardinier and Müller ( DM:HHL ) arise by setting D=\wp({\wp({\mathit{States}})}) ordered by inclusion, with a suitable hyperproperty operation \oplus , and a basis of irreducible hypersets \{X\} , for X\in\wp({\mathit{States}}) . As a further instance, incorrectness logic in the style of O’Hearn ( OHearn20 ) is recovered by adopting the standard powerset lattice but reversing the order, that is, taking (\wp({\mathit{States}}),\supseteq) , and using the entire \wp({\mathit{States}}) as the basis. Furthermore, our framework accommodates various abstract domains, yielding Hoare-style logics for abstract semantics, a problem highlighted by Cousot et al. ( CCLB:AIFR ) for its inherent difficulty. In our setting, the choice of the join basis (which is irrelevant for standard Hoare logic) plays a pivotal role in controlling the degree of approximation in the abstract domain. A key insight of our approach is that restricting the logical language \mathcal{L} constitutes a form of abstraction. If the strongest postcondition for a given precondition h and program \mathsf{r} is not expressible in \mathcal{L} , soundness ensures that only an over-approximation (a sound abstraction) is derived. When \mathcal{L} corresponds to an abstract domain A , this yields a deduction system grounded in best correct approximations as defined in abstract interpretation