💻 computer science

Access Hoare Logic

This paper introduces Access Hoare Logic, a novel formalism for reasoning about access control and security in computer programs, and establishes its soundness, completeness, and fundamental distinctions from both standard Hoare logic and incorrectness logic.

Original authors: Arnold Beckmann, Anton Setzer

Published 2026-04-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Arnold Beckmann, Anton Setzer

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 security guard at a high-tech hotel. Your job is to make sure that only the right people get into the right rooms.

For decades, computer scientists have used a famous method called Hoare Logic to check if computer programs work correctly. Think of Hoare Logic as a forward-looking detective. It asks: "If I start with this specific key (the pre-condition), will the door definitely open (the post-condition) when I run the program?"

If the answer is yes, the program is "correct." This works great for most software. But, the authors of this paper argue that for Access Control (security), this forward-looking approach misses the most important question.

The Problem: The "False Alarm" Trap

Let's say you have a program that opens a door.

Hoare Logic (Forward): "If the guest has a valid key, the door opens." (This is true).
The Security Flaw: What if the program is broken and opens the door regardless of whether the guest has a key?
- Hoare Logic might still say, "Well, if they did have a key, the door opened. So it's correct!"
- But as a security guard, you know that's a disaster. You need to know: "If the door opened, was it necessary that the guest had a valid key?"

This is the gap the paper fills. They introduce Access Hoare Logic (aHL).

The Solution: The "Backward Detective"

Access Hoare Logic is like a backward-looking detective. Instead of asking "What happens if I start here?", it asks: "If the door is open, what must have happened before?"

Standard Hoare Logic: "If I have a key, the door opens." (Sufficiency).
Access Hoare Logic: "If the door is open, I must have had a key." (Necessity).

In the world of security, we don't just want to know that a key can open the door; we need to guarantee that nothing else can open it. Access Hoare Logic forces the computer to prove that the "Open Door" state is impossible without the "Valid Key" state.

Real-World Analogies from the Paper

The authors use three examples to show why this backward thinking is crucial:

1. The Hotel Key Card (The "Ambiguous Code" Trap)

Imagine a hotel where your key card has two chips: an old one and a new one.

The Goal: When you swipe, the door opens, and the old chip is deactivated so the previous guest can't use it.
The Bug: The programmer wrote the code in a way that is ambiguous. One version of the code checks the key and then always opens the door, even if the key is wrong.
The Result:
- Hoare Logic says: "If the guest has the right key, the door opens." (True, so it passes).
- Access Hoare Logic says: "If the door opened, did the guest necessarily have the right key?" (No! The door opened even with a wrong key). FAIL.
- Analogy: It's like a bouncer who lets anyone in if they have a VIP pass, but also lets everyone in anyway. Hoare Logic checks if VIPs get in; Access Logic checks if only VIPs get in.

2. Bitcoin (The Digital Vault)

Bitcoin uses "scripts" to move money. To send money, you need a digital signature (a key) that matches a specific address.

The Goal: Ensure that money only moves if the correct signature is provided.
The Logic: Access Hoare Logic verifies that if the transaction succeeds (money moves), it is impossible that the wrong signature was used. It proves that the "Success" state requires the "Correct Signature" state.

3. The Master Key List (The Loop)

Imagine a program that checks a list of 1,000 keys to see if yours is on it.

The Goal: Grant access only if your key is in the list.
The Logic: Access Hoare Logic traces the program backward from the moment access is granted. It proves that for the program to reach the "Access Granted" state, it must have found your key in the list during the loop. If the loop had a bug that granted access by accident, Access Hoare Logic would catch it because the "Access Granted" state wouldn't be necessary for finding the key.

Why Not Just Use "Negation"?

You might think, "Can't we just flip the logic? Instead of 'If Key then Open', say 'If No Key then No Open'?"

The authors say: Yes, you can, but it's a nightmare.

The "Negation" Approach: It turns simple, clear math into confusing, double-negative riddles (like "It is not the case that the door is not open").
The "Direct" Approach: Access Hoare Logic gives us a new, clean set of rules specifically designed for security. It's like having a specialized screwdriver for security screws, rather than trying to use a hammer and twisting it until it breaks.

The Big Picture

This paper is essentially saying: "We have a great tool for building things (Hoare Logic), but we need a different tool for locking them up (Access Hoare Logic)."

Hoare Logic ensures your program does what you intend it to do.
Access Hoare Logic ensures your program does nothing you didn't intend it to do (specifically, it ensures no unauthorized access).

By using this "backward detective" approach, we can build more secure systems, from hotel doors to the billions of dollars in Bitcoin, ensuring that the only way to get in is to have the right key.

1. Problem Statement

Standard Hoare Logic is the foundational framework for verifying the correctness of computer programs. It operates on the principle of sufficiency: if a pre-condition $P$ holds before execution, and the program terminates, then the post-condition $Q$ will hold. Formally: $\{P\} C \{Q\}$ .

However, Access Security (e.g., access control, authentication, blockchain smart contracts) requires a fundamentally different logical guarantee. For a system to be access-secure, it must ensure that access is granted only if specific conditions were met prior to execution. This is a question of necessity, not just sufficiency.

The Gap: Standard Hoare logic cannot naturally express that a pre-condition is necessary for a post-condition to hold. For example, in a hotel key system, we need to prove that if a door is open (post-condition), the user must have possessed a valid key (pre-condition). Standard logic allows for "False" as a valid pre-condition (vacuously true), which is useless for security proofs where we need to ensure the pre-condition was actually satisfied.

2. Methodology

The authors propose Access Hoare Logic (aHl), a formalism that reverses the direction of reasoning found in standard Hoare logic.

Core Concept: The Access Hoare Triple

Instead of $\{P\} C \{Q\}$ , aHl uses the triple $\langle P \rangle C \langle Q \rangle$ .

Semantics: $\langle P \rangle C \langle Q \rangle$ is valid if and only if for all states $s, s'$ , if executing $C$ in state $s$ results in state $s'$ where $Q$ holds, then $P$ must have held in state $s$ .
Formal Definition: $\forall s, s'. [s \xrightarrow{C} s' \land Q(s') \implies P(s)]$ .
Logical Direction: It reasons backwards from the post-condition to the pre-condition. $P$ is a necessary condition for $Q$ .

The Calculus

The authors define a direct calculus for aHl with specific rules that differ from standard Hoare logic to accommodate the "necessity" requirement:

Assignment: $\langle P[E/V] \rangle V := E \langle P \rangle$ (Similar to Hoare, but interpreted as necessary).
Consequence Rule: This is the most significant deviation.
- Standard Hoare: We can strengthen the pre-condition and weaken the post-condition.
- Access Hoare: We can weaken the pre-condition and strengthen the post-condition.
- Reasoning: If $P_2 \implies P_1$ and $Q_2 \implies Q_1$ , and we know $Q_2$ implies $P_2$ , then $Q_1$ (a stronger condition) implies $P_1$ (a weaker condition).
Conditional & While Rules: The rules are adapted to use implications ( $B \to P$ ) rather than conjunctions ( $B \land P$ ) in the premises, reflecting the reverse flow of logic.

Relationship to Standard Logic

Negation Duality: The paper establishes that $\langle P \rangle C \langle Q \rangle$ is logically equivalent to $\{\neg P\} C \{\neg Q\}$ in classical logic.
Intuitionistic Logic: The authors argue against simply reducing aHl to standard Hoare logic via negation. Doing so introduces contrapositives (e.g., $\neg B \to \neg A$ ) which are difficult to handle in intuitionistic theorem provers (like Coq) and can break verifiability. They prove that aHl can be constructed directly using intuitionistic logic.

3. Key Contributions

Definition of Access Hoare Logic: A formal system specifically designed to reason about access security, distinguishing it from general program correctness.
Soundness and Completeness Proofs: The authors prove that their calculus is both sound (provable triples are valid) and complete (all valid triples are provable) with respect to the semantic definition.
Connection to Weakest/Strongest Preconditions:
- They define the Strongest Pre-condition for aHl ( $P_s$ ) as the set of states that can reach a post-condition $Q$ .
- They prove that for terminating programs, the Strongest Pre-condition in aHl coincides with the Weakest Pre-condition in standard Hoare logic.
- This provides a theoretical bridge: $P_s^{aHl} = P_w^{Hoare} \cap \text{TerminationSet}$ .
Distinction from Incorrectness Logic: The paper clarifies that while "Incorrectness Logic" (which uses under-approximation) is a reverse view of standard logic for forward transformers, aHl is the correct reverse view for backward transformers (access security).

4. Results and Examples

The paper validates the framework through three distinct examples:

Electronic Keys (Hotel System):
- Scenario: A door lock updates its key after a guest uses a card.
- Result: The authors show that a program with ambiguous parsing (where acc := true executes unconditionally) fails the aHl check because the pre-condition (having a valid key) is not necessary for the post-condition (door open). The correct parsing passes the check.
Bitcoin Smart Contracts:
- Scenario: Verifying the scriptPubKeyP2PKH locking script.
- Result: The logic proves that for the transaction to succeed (post-condition: stack top is true), the unlocking script must have provided a valid signature and public key hash (pre-condition). This formalizes the security guarantee of Bitcoin transactions.
Access Control Loop (CheckList):
- Scenario: Granting access if a key exists in a list.
- Result: A formal derivation using loop invariants demonstrates that access is granted only if the key was found in the list, proving the necessity of the search result.

5. Significance

Theoretical Advancement: It fills a gap in formal verification by providing a dedicated logic for access control, a critical area in security that standard correctness logic cannot adequately address.
Practical Application: The logic is directly applicable to modern security-critical domains, particularly Blockchain and Smart Contracts (e.g., Bitcoin, Ethereum), where ensuring that assets are only transferred if specific authorization conditions are met is paramount.
Tooling Implications: By providing a direct calculus that avoids the pitfalls of negation-based reductions, aHl enables the development of automated verification tools (like SPARK or Dafny extensions) that can verify access security using intuitionistic theorem provers without syntactic complexity.
Patent and Industry Impact: The authors note that this work has led to a patent on "Verifying Access Security of a Computer Program," indicating immediate potential for industrial application in verification condition generation.

In summary, Access Hoare Logic reorients formal verification from "what happens if I start here?" to "what must have been true for this to happen?", providing a rigorous mathematical foundation for securing computer systems against unauthorized access.