Scaling Formal Verification via Assume Guarantee Contracts

459 concepts298 papers2 proposals

When we design complex systems—whether they are autonomous vehicles, distributed cryptographic protocols, or multi-threaded software—we naturally break them down into smaller, modular components. However, when we attempt to formally verify that these systems are safe, this modularity often vanishes. Traditional formal verification methods tend to be monolithic: they require analyzing the entire system's state space all at once.

This leads to the notorious state-space explosion problem. If Component A has $10^6$ states and Component B has $10^6$ states, their combined system doesn't have $10^6 + 10^6$ states; it has $10^{12}$ states. As more components are added, the state space grows exponentially, rendering automated verification computationally impossible.

To solve this, researchers use compositional verification, primarily driven by assume-guarantee reasoning (or contract-based design). The core intuition is simple: we should be able to verify a component in isolation by making mathematically rigorous assumptions about the environment it operates in. If every component fulfills its promises given its assumptions, we can deduce the safety of the entire system without ever building the massive, combined state space.


The Core Intuition: What is an Assume-Guarantee Contract?

In a monolithic verification setup, to prove that Component A is safe, you must simulate or mathematically evaluate how it interacts with the actual implementation of Component B.

In an assume-guarantee framework, we replace the concrete implementation of the environment with an abstract contract. A contract consists of two main parts:

  1. Assumptions ($A$): What the component expects from its environment (inputs, configuration, or behavior of neighboring subsystems).
  2. Guarantees ($G$): What the component promises to deliver, provided the assumptions hold true.
   [ Environment ] --( Satisfies Assumptions 'A' )--> [ Component ]
                                                            |
   [ Global System ] <-- ( Delivers Guarantees 'G' ) --------+

This framing shifts the verification burden. Instead of proving that the entire system works simultaneously, we prove two localized properties for each component:

  • Local Correctness: Under the assumption $A$, the component's internal logic guarantees $G$.
  • Interface Compatibility: The guarantees provided by one component logically imply the assumptions required by the next component ($G_A \implies A_B$).

As Anupam Datta et al. demonstrate in their work on Key Exchange Protocols: Security Definition, Proof Method and Applications, this sequential composition allows complex systems to be built like Lego blocks. If the security guarantees of a key exchange protocol precisely match the prerequisites of a subsequent session protocol, the entire pipeline is secure by design.


Why It Works: The Mathematics of Composition

How do we know that combining these local proofs actually guarantees global safety? The answer lies in formal composition theorems that treat contracts as algebraic objects.

Property Quotienting

One powerful mechanism for breaking down global properties is property quotienting, introduced by Jørgen H. Andersen in Compositional Safety Logics. Instead of changing the model of the system, quotienting transforms the logical formula itself.

If we have a global safety requirement $\phi$ for a parallel system $C_1 \parallel C_2$, we can "quotient" $\phi$ by the behavior of $C_1$. This yields a new, localized formula $\phi / C_1$ that represents exactly what $C_2$ must satisfy to ensure the global property holds. This shifts the complexity out of the state space and into the logical structure, allowing components to be verified completely independently.

Dominating Contracts

To make this practical for engineers, we need a way to merge multiple contracts into a single, unified contract for a larger subsystem. In Moving from Specifications to Contracts in Component-Based Design, Sebastian Bauer et al. formalize this using the concept of a dominating contract.

When two components are composed, their mutual assumptions must be reconciled. The dominating contract is mathematically defined as the strongest possible contract that safely encapsulates both sub-contracts while ensuring their internal dependencies are satisfied. This treats composition as a universal algebraic property, meaning that once the interface boundaries are proven compatible, the internal implementations can be completely ignored during high-level system analysis.


How It Scales Across Different Domains

The beauty of assume-guarantee contracts is that the underlying mechanism remains identical whether you are dealing with physical dynamics, software threads, or smart contracts.

1. Cyber-Physical Systems (CPS)

In systems that mix discrete software logic with continuous physical dynamics (like robotics or aerospace), monolithic verification is particularly brutal because continuous differential equations cannot be easily represented as finite states.

Xiangru Xu et al. applied contract-based design to autonomous driving features in Correctness Guarantees for the Composition of Lane Keeping and Adaptive Cruise Control. By establishing formal assumptions and guarantees regarding mutual disturbances, they proved that Lane Keeping and Adaptive Cruise Control could operate simultaneously without causing the vehicle to leave its lane or crash, managing the coupled physical dynamics through decentralized control boundaries.

Similarly, Andreas Müller et al. showed in Tactical contract composition for hybrid system component verification that breaking down train control systems into contract-governed components yields nearly a 20x speedup in verification time compared to monolithic approaches.

2. Concurrent Software and Threads

In multi-threaded software, the state space explodes because of the infinite possible interleavings of instructions across different threads.

Rupak Majumdar et al. tackled this in Thread-Modular Abstraction Refinement. Instead of tracking every possible way threads could interfere with each other, their framework analyzes each thread in total isolation. The behavior of all other threads is compressed into a set of environment assumptions. If a thread remains safe under those assumptions, and the other threads guarantee they won't violate those assumptions, the entire concurrent system is proven safe without ever exploring the combinatorial explosion of thread interleavings.

3. Decentralized Applications and Smart Contracts

In blockchain ecosystems, smart contracts frequently interact with untrusted, external code, leading to catastrophic vulnerabilities like reentrancy attacks.

In A Semantic Framework for the Security Analysis of Ethereum Smart Contracts, Ilya Grishchenko et al. demonstrate how global security invariants can be broken down into local properties like "code independence" and "effect independence." By verifying that individual functions respect these local boundaries, they can formally guarantee reentrancy protection across complex, multi-contract interactions without needing to analyze the global state of the entire blockchain network.


Conclusion

Assume-guarantee reasoning works because it honors the fundamental principle of computer science: abstraction. By replacing concrete, complex environments with mathematical contracts containing explicit assumptions and guarantees, compositional verification bypasses the state-space explosion problem. It transforms an intractable, exponential global problem into a series of localized, linear verification tasks, allowing formal methods to scale to real-world, industrial systems.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_compositional_verification_708f6fef,
  title = {compositional verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compositional-verification/rdr_708f6fefadc140078e2494fa223e6ede},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_compositional_verification_708f6fef_v1,
  title = {compositional verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compositional-verification/rdr_708f6fefadc140078e2494fa223e6ede/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake