🤖 machine learning

Verification Modulo Tested Library Contracts

This paper presents a counterexample-guided learning framework implemented in the \vmtlc tool that automates the verification of client programs using complex libraries by synthesizing modular or contextual contracts that are both sufficient for proving client correctness and validated by a testing engine.

Original authors: Abhishek Uppar, Omar Muhammad, Sumanth Prabhu, Deepak D'Souza, Madhusudan P, Adithya Murali

Published 2026-04-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Abhishek Uppar, Omar Muhammad, Sumanth Prabhu, Deepak D'Souza, Madhusudan P, Adithya Murali

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 building a complex house (your Client Program). You don't want to build the entire house from scratch; instead, you want to use pre-made, high-quality bricks, windows, and doors from a massive factory (the Library).

The problem is: The factory is huge, complex, and nobody has written a perfect manual for every single brick. Checking every single brick to prove it's perfect would take forever and is practically impossible. However, you do need to be sure your house won't collapse.

This paper introduces a clever new way to verify your house without needing to inspect every single brick in the factory. They call it "Verification Modulo Tested Library Contracts."

Here is how it works, broken down into simple concepts:

1. The Old Way vs. The New Way

The Old Way (Strict Verification): You demand the factory give you a perfect, mathematically proven manual for every brick. You then check every brick against that manual before building.
- Problem: The factory is too big. The manual is too complex. You get stuck and can't build anything.
The New Way (VMTLC): You ask the factory for a "contract" (a promise) about what the bricks do. You then build your house assuming those promises are true. Finally, you hire a team of inspectors (a Testing Engine) to throw bricks at the factory's machines to see if they break the promises.
- The Deal: If the inspectors can't find a broken brick after throwing thousands of them, you assume the contract is good enough to build your house.

2. The "Magic" Loop: Guess, Check, and Improve

The paper describes a smart robot (an AI Synthesizer) that does the heavy lifting. It works in a loop, like a game of "Hot and Cold":

The Guess: The robot looks at your house blueprint and guesses a set of rules (contracts) for the factory bricks. It also guesses some safety rules for your house construction.
The Logic Check: A "Logic Brain" checks: "If these rules are true, does the house stay standing?"
The Stress Test: If the Logic Brain says "Yes," the robot sends the rules to the Inspector Team (the Tester). The inspectors try to break the factory using the new rules.
- Scenario A: The inspectors find a brick that breaks the rule! The robot takes that broken brick, learns from it, and makes the rule stronger.
- Scenario B: The inspectors try everything and can't break the rule.
The Result: If the inspectors can't break the rule, the robot says, "Okay, this contract is good enough. We verified the house!"

3. The Secret Weapon: "Contextual Contracts"

This is the paper's most creative idea.

Modular Contracts (The Strict Rule): "This brick must hold up any weight, in any weather, for any building." This is hard to prove.
Contextual Contracts (The Smart Rule): "This brick only needs to hold up this specific house in this specific weather."

The Analogy:
Imagine a library book.

A Modular Contract says: "This book must be readable by anyone, anywhere, in any language, even if the pages are torn." (Very hard to guarantee).
A Contextual Contract says: "Since you only read this book in a quiet library with good lighting, we only promise it's readable under those specific conditions."

Because the robot knows exactly how your house uses the bricks, it can write simpler, easier-to-prove rules. It doesn't need to worry about scenarios that will never happen in your specific house.

4. The Tools: ICE Learners and LLMs

How does the robot get so smart? It uses two main tools:

ICE Learners: Think of these as a student taking a test. If they get a question wrong, the teacher gives them a hint (a counterexample). The student learns from the hint and tries again. The paper uses a specific type of student that is good at generalizing (making broad rules from specific examples).
LLMs (Large Language Models): This is where they use AI like ChatGPT. They ask the AI to guess the rules based on the code. If the AI guesses wrong, the robot shows it the mistake, and the AI tries again. It's like having a very knowledgeable intern who is great at guessing but needs a little nudge to be perfect.

5. The Result: Dualis

The authors built a tool called Dualis (like a dual-sided mirror) to test this. They tried it on 43 real-world programs that use huge data libraries (like those used by Google and Facebook).

The Outcome: Traditional tools failed to verify almost all of them.
The Success: Dualis successfully verified most of them by using this "Test + Contract" approach. It found simple, smart rules that proved the houses were safe, even though it didn't check every single brick in the factory.

Summary

This paper solves a huge problem in software safety: How do we trust giant, complex libraries without spending a lifetime checking them?

The answer is: Don't check everything. Instead, let an AI guess the rules, let a robot stress-test those rules, and if the rules hold up under pressure, trust them. It's a pragmatic shift from "Prove it's perfect" to "Prove it works for this specific job, and test it until it breaks."

1. Problem Statement

The paper addresses the scalability bottleneck in formal verification of large software systems. Traditional automated verification requires proving both the client code and the complex libraries it uses, often necessitating difficult-to-synthesize inductive invariants and strong modular contracts for library methods.

The authors propose a pragmatic relaxation of this requirement: Verification Modulo Tested Library Contracts (VMTLC).

Goal: Automatically verify a smaller client program ( $C$ ) that utilizes a large, complex library ( $L$ ).
Constraint: Instead of formally verifying the library code, the system synthesizes contracts for the library methods and ensures these contracts are validated by a testing engine (fuzzing) rather than a theorem prover.
Core Challenge: Synthesize a set of library contracts ( $\Pi$ $Π$ ) and client invariants ( $I$ $I$ ) such that:
1. The client is formally proven correct assuming $\Pi$ .
2. A deterministic test generator cannot find any execution trace where the library violates $\Pi$ within a given resource bound.

2. Key Concept: Contextual Contracts

A major theoretical contribution is the introduction of Contextual Contracts.

Modular Contracts: Must hold for all possible states and inputs of the library, regardless of how the library is used. These are often complex and hard to synthesize.
Contextual Contracts: Only need to hold in the specific context of the client program. Since the client calls the library with specific preconditions (implicit in the client's logic), the contracts can be weaker (or stronger in specific ways) and significantly simpler.
- Example: If a client only inserts positive integers into a set, a modular contract might need to handle all integers. A contextual contract for the remove method can simply assert "returns a positive integer," which is sufficient for the client's proof but false for arbitrary library usage.

3. Methodology

The authors propose a Counterexample-Guided Abstraction Refinement (CEGAR) framework that simultaneously synthesizes client invariants and library contracts.

The Learning Framework

The system operates in an iterative loop involving three main components:

Generalizing CHC Solver: Solves Constrained Horn Clauses (CHCs) derived from the client program to find candidate invariants and contracts. Crucially, this solver must generalize (avoid overfitting) based on positive examples.
Test Generator: A fuzzing engine (implemented using AFL++) that attempts to falsify the synthesized library contracts.
- Modular Mode: Tests the library in isolation with arbitrary inputs.
- Contextual Mode: Tests the entire program (Client + Library) to see if the client's specific usage triggers a contract violation.
ICE Learner (Implication Counterexample): The core engine that learns from three types of feedback:
- Positive Examples: Test cases where the contract was violated (from the Test Generator).
- Negative Examples: Counterexamples from the CHC solver showing the current invariant/contract is invalid for the client logic.
- Implication Examples: Logical constraints ensuring the solution satisfies the CHC structure.

Algorithm Flow

Initialization: Start with empty positive examples.
Synthesis: The ICE Learner proposes a solution (invariants + contracts) that satisfies the CHCs and covers all current positive examples.
Testing: The Test Generator attempts to find a violation of the proposed contracts.
- If a violation is found, the test case is converted into a positive example and added to the learning set.
- The loop repeats, forcing the solver to generalize the contract to cover the new example.
Termination: The process stops when the solver finds a solution that satisfies the CHCs and the test generator cannot find any violations (returns "OK").

Learning Algorithms Evaluated

The paper evaluates three specific ICE learners:

HornICE: Uses decision tree learning over a fixed grammar (octagonal constraints).
LLM-based: Uses Large Language Models (Gemini v2.5 Pro) to propose contracts and invariants, treating the LLM as the hypothesis learner.
Hybrid (HornICE + LLM): Uses the LLM to generate atomic predicates/templates, which are then fed into HornICE to synthesize the final boolean combination.

4. Implementation: Dualis

The framework is implemented in a tool called Dualis (Python).

Verification Engine: Uses Z3 to check CHC validity.
Testing Engine: Uses AFL++ for fuzzing.
Benchmarks: Evaluated on 43 C++ client programs using real-world open-source libraries (Folly, Abseil, Android, SV-COMP). The libraries range from 100 to 3,000 lines of code.

5. Results and Evaluation

The evaluation focuses on four Research Questions (RQs):

RQ1 (Effectiveness): The framework successfully verified clients that state-of-the-art tools (like SeaHorn) could not.
- LLM-only performed best, solving 38/43 modular and 41/43 contextual benchmarks.
- HornICE solved fewer (19 modular, 21 contextual) due to limited grammar expressiveness.
- Contextual contracts were generally easier to synthesize and faster to verify than modular ones.
RQ2 (Simplicity): Contextual contracts were consistently smaller and less complex than modular contracts, confirming the theoretical advantage of context-aware synthesis.
RQ3 (Validity): All synthesized contracts were manually and automatically vetted. The tool found no violations in the synthesized specifications after extensive re-testing.
RQ4 (Generalization): Replacing the generalizing ICE solver with a standard solver (CVC5) drastically reduced success rates (dropping to 10 modular and 15 contextual), proving that generalization is critical to avoid overfitting to specific test cases.

Limitations & Safety:

The system can theoretically verify incorrect programs if the test generator fails to find a "rare" execution path that violates a spurious contract.
A mutant study showed that while modular contracts rejected all injected bugs, contextual contracts verified 11/30 buggy programs (due to the rarity of the bug path in the client context). However, the authors argue this is a trade-off for scalability and that effective testing mitigates this risk.

6. Significance

Scalability: VMTLC offers a new paradigm for verifying large codebases by shifting the burden of library correctness from formal proof to rigorous testing, a task where testing engines are highly effective.
Automation: It achieves full automation for client verification, including the synthesis of loop invariants and library contracts, without requiring human annotations.
Contextual Contracts: Introduces a new, simpler form of specification that leverages the client's usage patterns, making synthesis feasible where classical modular contracts fail.
LLM Integration: Demonstrates the practical utility of LLMs not just as code generators, but as formal reasoning components (ICE learners) within a rigorous verification loop, validated by solvers and testers.

In conclusion, the paper presents a robust framework that bridges the gap between the scalability of testing and the rigor of formal verification, enabling the verification of complex client-library interactions that were previously out of reach for automated tools.