TL;DR
This paper introduces INTERHORN, a novel solver for a specific type of logical formula called "recursion-free Horn clauses." INTERHORN tackles interpolation problems, crucial for approximating program states in software verification, by translating these problems into this Horn clause format. This work aims to provide a unified backend for various verification tools by offering a declarative way to specify and solve interpolation tasks.
What Problem Does This Paper Address?
Software verification tools often need to compute approximations of program states to prove properties like safety or termination. A key technique for this is "interpolation," which generates intermediate assertions that bridge gaps in a program's execution path or transitions. However, existing interpolation methods can be specialized and lack a unified approach. This paper addresses the need for a general-purpose interpolation solver that can handle a wide range of interpolation problems arising in software verification by representing them in a common, declarative format: recursion-free Horn clauses. This approach aims to simplify the integration of interpolation into diverse verification tools.
Methods
The core of INTERHORN's approach is to translate various interpolation problems into sets of recursion-free Horn clauses. These clauses involve literals that are either assertions in linear arithmetic or unknown relations, and can optionally include well-foundedness conditions.
The solving process for INTERHORN involves three main steps:
- Resolution: The input Horn clauses are resolved. Since the clauses are recursion-free, this process is guaranteed to terminate and produce an assertion involving only background theory constraints (like linear arithmetic).
- Validity Checking: The assertion obtained from resolution is checked for validity. If it's not valid, it means the original interpolation problem is unsatisfiable. If valid, a proof of validity is generated.
- Solution Construction: The proof of validity is used to construct the interpolants. This involves assigning interpretations to the unknown relations based on how they contributed to the proof.
For interpolation problems with well-foundedness conditions (e.g., for proving termination), INTERHORN introduces additional steps:
- It first obtains an under-approximation for the relation subject to the well-foundedness condition.
- Then, it attempts to find a well-founded relation that over-approximates this.
- Finally, it uses this well-founded over-approximation to construct a clause that replaces the well-foundedness condition with an approximation condition, allowing the standard solving procedure to proceed.
Datasets
Not discussed in the paper. The paper focuses on the formulation of interpolation problems as Horn clauses and the solving mechanism, rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Unified Representation: The paper demonstrates that a wide variety of interpolation problems (path, transition, nested, state/transition, well-founded) can be uniformly represented as recursion-free Horn clauses. This is a significant step towards a common backend for interpolation.
- Declarative Specification: By using Horn clauses, interpolation problems can be specified declaratively, making them easier to understand and integrate into existing verification frameworks.
- Leveraging Resolution: The core solving mechanism relies on the termination and expressiveness of resolution on recursion-free Horn clauses, which naturally leads to an assertion in the background theory.
- Proof-Guided Interpolant Synthesis: The interpolants are not just found but are synthesized by leveraging the proof of validity derived from the resolution process. This ensures soundness and completeness (for cases without well-foundedness).
- Handling Well-Foundedness: The paper presents a novel approach to incorporate well-foundedness conditions, which are crucial for termination proofs, by transforming them into an approximation problem solvable by the core INTERHORN engine.
Key Results
The paper presents INTERHORN as a solver that can handle various interpolation problems by translating them into recursion-free Horn clauses. It demonstrates how different interpolation scenarios, such as path, transition, nested, state/transition, and well-founded interpolation, can be formulated and solved. The system is described as sound and complete for clauses without well-foundedness conditions, and it provides an approach for handling well-foundedness conditions, albeit with a note on incompleteness in those cases due to reliance on ranking function synthesis. INTERHORN has already shown its practicability in a software verification competition.
Limitations and Future Work
- Incompleteness with Well-Foundedness: INTERHORN is noted to be incomplete when well-foundedness conditions are present, as it relies on the synthesis of linear ranking functions.
- Future Work: The authors suggest future development directions, including:
- Adding support for uninterpreted functions.
- Incorporating integer arithmetic.
- Exploring the relationship between interpolation and different fragments of recursion-free Horn clauses more deeply.
Summary updated