💻 computer science

A Program Logic for Abstract (Hyper)Properties

This paper introduces APPL, a unifying Hoare-style logic grounded in a flexible semantic framework that subsumes standard, incorrectness, and hyper logics while providing sound and relatively complete proof systems for both concrete and abstract program properties.

Original authors: Paolo Baldan, Roberto Bruni, Francesco Ranzato, Diletta Rigo

Published 2026-04-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Paolo Baldan, Roberto Bruni, Francesco Ranzato, Diletta Rigo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to figure out what happens when a computer program runs. Sometimes you want to know, "Will this program definitely do the right thing?" (Correctness). Other times, you want to know, "Can I prove this program is broken?" (Incorrectness). And sometimes, you need to compare two different runs of the same program to see if they behave consistently (Hyperproperties).

For decades, detectives (computer scientists) have used different rulebooks (logics) for each of these jobs. But these rulebooks were often incompatible, like trying to use a map of London to navigate Tokyo.

This paper introduces APPL (Abstract Program Property Logic), a "Universal Translator" for program logic. It's a single, flexible framework that can act as any of these rulebooks, depending on how you set it up.

Here is the breakdown using everyday analogies:

1. The Core Idea: The "Shape-Shifting" Rulebook

Think of APPL as a Lego set.

Standard Hoare Logic (checking for correctness) is like building a castle. You want to be sure every brick is in the right place.
Incorrectness Logic (finding bugs) is like building a demolition crew. You want to find a specific path where the castle falls apart.
Hyperproperties (comparing runs) is like comparing two identical castles built at the same time to see if they look exactly the same.

APPL provides the same set of Lego bricks (the logic rules) for all three. You just change the instruction manual (the mathematical "lattice" and "basis") to tell the bricks how to snap together for your specific job.

2. The Secret Sauce: The "Basis" and the "Join"

To understand how APPL works, imagine you are describing a messy room.

The Lattice: This is the whole room, containing every possible state of messiness.
The Basis: These are the "atomic" pieces of the mess. Maybe it's just individual socks, or maybe it's piles of clothes.
The Join (The "Glue"): This is how you combine descriptions.

The Innovation:
In old logic systems, the "glue" was rigid. If you had two piles of clothes, you just mashed them together into one big pile.
In APPL, the "glue" is flexible.

Sometimes, you want to mash them together (standard logic).
Sometimes, you want to keep them separate to see the difference (hyperproperties).
Sometimes, you want to look at the absence of clothes to prove a bug (incorrectness).

The paper introduces a special "monoidal operator" (a fancy math term for a flexible glue) that doesn't force things to merge if they shouldn't. This allows the logic to be incredibly precise.

3. The "Join" Rule: The Magic of Splitting

The most important rule in this new system is called the (join) rule.

The Analogy: The Detective's Whiteboard
Imagine a detective trying to solve a case where a suspect could have taken three different paths.

Old Logic: The detective looks at the average of all three paths. "Well, Path A went left, Path B went right, so the average is 'straight ahead'." This loses information.
APPL Logic: The detective uses the (join) rule. They say, "Let's look at Path A, Path B, and Path C separately on my whiteboard, and then combine the conclusions."

This is crucial for Hyperproperties. If you want to prove that two runs of a program never leak a secret, you can't just average them. You have to track them individually. APPL's (join) rule allows the logic to split the problem into smaller, manageable pieces, solve them, and then stitch the answers back together without losing the "who did what" details.

4. Abstraction: The "Blurry Lens"

Often, we don't need to know the exact state of every variable (e.g., is the number exactly 42?). We just need to know if it's "positive" or "negative." This is called Abstraction.

The Problem: If you use a blurry lens (abstraction) with old logic, you might lose too much detail. You might think a path is safe when it's actually dangerous because the blur merged two different scenarios.
The APPL Solution: APPL treats the choice of the "blurry lens" as a fundamental part of the logic. It ensures that even if you are looking through a lens, your conclusions are still sound (you won't make a false claim) and complete (you won't miss a real possibility) if the lens is chosen correctly.

It's like saying: "I can prove this bridge is safe even if I only look at it through a foggy window, provided I know exactly how the fog distorts the view."

5. Why This Matters

Before this paper, if you wanted to switch from "checking for bugs" to "checking for security leaks between runs," you had to learn a completely new language and set of rules.

APPL unifies them.

It explains why some logics work and others don't.
It shows that the difference between "finding a bug" and "proving safety" is just a matter of flipping a switch in the mathematical foundation.
It gives us a new toolkit to handle Hyperproperties (comparing multiple runs), which is becoming essential for modern security (like ensuring a program doesn't leak passwords based on how long it takes to run).

Summary

Think of APPL as a Swiss Army Knife for Program Verification.

It has a blade for Correctness (cutting out bugs).
It has a screwdriver for Incorrectness (unscrewing the logic to find the flaw).
It has a magnifying glass for Hyperproperties (zooming in on multiple runs).

The genius of the paper is showing that these aren't three different tools; they are just three different ways of holding the same tool. By understanding the underlying "glue" (the monoidal operator) and the "pieces" (the basis), we can build a logic that is precise, flexible, and powerful enough to handle the most complex software challenges of today.

1. Problem Statement

The landscape of program logics has fragmented into specialized systems for different reasoning modalities:

Correctness: Classical Hoare logic (over-approximation).
Incorrectness: Incorrectness logic (under-approximation to find bugs).
Hyperproperties: Logics relating multiple execution traces (e.g., non-interference, determinism).
Abstraction: Logics operating on abstract domains (e.g., intervals, polyhedra).

Existing unifying frameworks often fail to systematically integrate abstraction (in the sense of Abstract Interpretation) with these diverse modalities. Specifically, handling logical disjunction (joining properties) in abstract domains is notoriously difficult, often leading to unsoundness or incompleteness. Furthermore, there is a lack of a single semantic foundation that can simultaneously capture standard state properties, hyperproperties, and abstract properties while allowing for both over- and under-approximation.

2. Methodology and Semantic Framework

The authors introduce APPL (Abstract Program Property Logic), a unifying Hoare-style logic grounded in a novel semantic framework based on Interpretation Monoids.

A. The Semantic Model

The core of the framework is an Interpretation Monoid $(D, \sqsubseteq, \oplus, B)$ , where:

$D$ (Domain): A complete lattice representing the semantic domain.
$\sqsubseteq$ (Order): The lattice order (can be subset inclusion for over-approximation or superset inclusion for under-approximation).
$B$ (Basis): A join-generating basis for $D$ . Crucially, the semantics of commands are first defined on $B$ and then extended to the full lattice $D$ via additivity (joins).
$\oplus$ (Monoidal Operator): An infinitary operator interpreting nondeterministic choice.
- Key Innovation: $\oplus$ $\oplus$ is not required to coincide with the lattice join ( $\sqcup$ $⊔$ ) nor to be idempotent. This flexibility allows the framework to model:
  - Standard collecting semantics ( $\oplus = \cup$ ).
  - Hyperproperties (Cartesian product-like operations).
  - Incorrectness logic (where $\oplus$ differs from the lattice join).

B. Command Semantics

Commands are defined as a Kleene Algebra with Tests (KAT). The semantics $[\![r]\!]$ is constructed by:

Defining semantics for elementary commands on the basis $B$ .
Extending to the full lattice $D$ via the unique additive extension (join extension).
This approach generalizes the derivation of collecting and abstract semantics, ensuring that the full semantics is additive on dense subsets of the basis.

C. The Logic (APPL)

APPL uses triples $\langle h \rangle r \langle k \rangle$ , where $h, k$ are assertions in a language $L \subseteq D$ .

Soundness: A triple is valid if $[\![r]\!]h \sqsubseteq k$ .
Key Inference Rule (Join): The system includes a (join) rule that allows deriving a property for a precondition $h$ $h$ by analyzing a dense family of preconditions $\{h_i\}$ ${h_{i}}$ covering $h$ $h$ .
- This rule is crucial for hyperproperties and disjunctive abstractions.
- It relies on the concept of density: a set $X$ is dense if it "properly covers" the basis elements below the join.

3. Key Contributions

A. Unification of Logics

By instantiating the parameters $(D, \sqsubseteq, \oplus, B)$ , APPL recovers several major logics as specific instances:

Classical Hoare Logic: $D = \wp(\Sigma)$ , $\sqsubseteq = \subseteq$ , $\oplus = \cup$ .
Incorrectness Logic: $D = \wp(\Sigma)$ , $\sqsubseteq = \supseteq$ (reversed order), $\oplus = \cup$ .
Hyper Hoare Logic: $D = \wp(\wp(\Sigma))$ , with a specific hyper-monoidal operator $\oplus$ (Cartesian product of sets).
Abstract Logics: $D$ is an abstract domain (e.g., Intervals), with $\oplus$ defined as the abstract join.

B. Principled Abstraction

The paper establishes that restricting the assertion language $L$ to an abstract domain is a form of abstraction.

Soundness: The abstract logic is always sound.
Completeness: The logic is relatively complete if the property language is expressive.
Abstract Completeness: If the abstract domain is complete with respect to the monoidal operator $\oplus$ (in the sense of Abstract Interpretation), the abstract logic is relatively complete with respect to the induced abstract semantics.
Role of Basis: The choice of the join basis $B$ controls the precision. Using a finer basis (e.g., irreducible elements) allows for more precise disjunctive reasoning (e.g., distinguishing branches in a conditional) compared to the standard inductive abstract semantics.

C. Handling Hyperproperties

The framework provides a principled way to abstract hyperproperties. It introduces:

Down-closed Hyperproperties: An abstraction where hyperproperties are closed under subsets.
Pointwise Abstraction: Applying an abstraction map pointwise to elements of a hyperproperty.
Intervals of Hyperproperties: A product domain combining concrete under-approximation and abstract over-approximation, allowing for joint reasoning about reachability and safety.

4. Results and Theoretical Findings

Soundness and Relative Completeness: The proof system is proven sound by construction. It is relatively complete whenever the assertion language is sufficiently expressive.
The Necessity of the (Join) Rule:
- In standard Hoare logic (over a powerset lattice), the (join) rule is redundant because the basis is the whole domain.
- In Hyper Logics and Abstract Logics with disjunctive reasoning, the (join) rule is indispensable for completeness. It corresponds to the (Exist) rule in Hyper Hoare Logic, allowing the separation of traces or branches.
Precision of Abstract Semantics: The paper demonstrates that defining semantics via an irreducible basis (e.g., singletons for intervals) yields a strictly finer semantics than the standard inductive abstract semantics.
- Example: For the program if x!=0 then x:=x-1 else x:=x+1; assert(x=0), standard interval analysis fails to prove unreachability (resulting in $[0,0]$ ). The APPL logic with an irreducible basis correctly derives $\emptyset$ by splitting the interval $[-1, 1]$ into $[-1, -1]$ and $[1, 1]$ before applying the conditional.
Completeness of Abstraction: The paper proves that if the abstraction is complete for the monoidal operator $\oplus$ , the abstract logic is complete with respect to the abstract semantics.

5. Significance

Theoretical Unification: APPL provides the first unified framework that seamlessly integrates correctness, incorrectness, hyperproperties, and abstraction under a single algebraic structure (Interpretation Monoids).
Solving the Disjunction Problem: It offers a principled solution to the difficulty of handling disjunction in abstract domains. By explicitly separating the lattice join (used for approximation) from the monoidal operator (used for nondeterminism), and utilizing the (join) rule with dense bases, it enables precise disjunctive reasoning without sacrificing soundness.
Foundation for Hyperproperty Abstraction: The paper addresses the "infancy" of static analysis for hyperproperties by providing a systematic method to abstract them, covering both existing and novel abstraction strategies (like down-closed and pointwise abstractions).
Practical Implications: The framework suggests that the choice of basis in abstract interpretation is not merely a technical detail but a fundamental parameter for controlling precision. It opens the door for dynamic basis adaptation (similar to trace partitioning) to improve analysis precision.

In conclusion, this work establishes a robust algebraic foundation for program logics, demonstrating that by carefully structuring the semantic domain and the interpretation of nondeterminism, one can unify diverse reasoning paradigms and systematically handle the complexities of abstraction and hyperproperties.