TL;DR
This paper introduces a novel semi-decision procedure for checking the unsatisfiability of a rich fragment of separation logic, including linked lists and negations. By leveraging abstract interpretation and a canonical abstraction domain of shape graphs, the method can prove unsatisfiability for formulas that were previously intractable for automated tools.
What Problem Does This Paper Address?
Reasoning about heap-allocated data structures in programs is crucial for software verification. Separation logic provides a powerful framework for this, allowing for localized reasoning about disjoint parts of the heap. However, existing automated tools for separation logic typically handle only limited fragments of the logic, often excluding features like linked lists, negations, or specific logical connectives. This paper tackles the challenge of developing an automated method that can handle a more expressive fragment of separation logic, specifically one that includes points-to assertions, acyclic list segments, logical connectives (AND, OR, separating conjunction, septraction), and importantly, negations at leaf nodes. This richer fragment allows for reasoning about more complex data structures and program behaviors, such as overlaid data structures and interference effects in concurrent programs.
Methods
The core of this paper's contribution is a semi-decision procedure for checking unsatisfiability, built upon the principles of abstract interpretation. The key idea is to use an abstract domain of shape graphs to overapproximate the set of possible program states (heap structures) that satisfy a given formula.
Here's a breakdown of the methodology:
- Canonical Abstraction Domain: The paper utilizes a canonical abstraction domain, inspired by Sagiv et al.'s work on shape analysis. This domain uses 3-valued logical structures to represent sets of concrete heap structures. These structures are essentially graphs where nodes represent individuals (memory locations or variables) and edges/predicates represent relationships. Summary individuals (represented by double-ruled borders) are used to abstract multiple concrete individuals, allowing for a finite representation of potentially infinite sets of states.
- Bottom-Up Evaluation: The semi-decision procedure works by performing a bottom-up evaluation of the separation logic formula. It computes an abstract value (a set of 3-valued structures) that overapproximates the set of satisfying models for each subformula.
- Semantic Reduction Operators: To improve the precision of the abstract representation, semantic reduction operators are employed. These operators refine the abstract structures by propagating definite values and removing infeasible states, effectively making the abstraction "tighter."
- Proof Rules: The paper defines specific proof rules for the logical connectives of the separation logic fragment. These rules dictate how to combine abstract values of subformulas to obtain the abstract value of the larger formula. Notably, logical AND is handled by a meet operation, and logical OR by a join operation. The handling of separating conjunction (
*) and septraction (-) involves introducing new domain predicates to demarcate heaplets and using specialized abstract values to capture disjointness constraints.
The novelty lies in the instantiation of this abstract interpretation framework to a richer separation logic fragment and the development of specific rules for its operators, particularly for handling linked lists and negations.
Datasets
The paper does not introduce new datasets. Instead, it evaluates its method on a set of formulas taken from the literature. These formulas are categorized into three groups:
- Group 1: A broad spectrum of formulas designed to test the procedure's capabilities.
- Group 2: Formulas generated by instantiating a template (
¬a ∧ emp ^ (a * b)) with various literals from the separation logic fragment. - Group 3: Formulas generated by instantiating another template (
emp^a^(b*(c-(emp^¬a)))) with literals.
These test cases are based on work by Hou et al. on Boolean separation logic, providing a benchmark for comparison.
Key Insights and Ideas
- Abstract Interpretation as a Decision Procedure Engine: The paper strongly advocates for using abstract interpretation machinery not just for program analysis but also as the core of decision procedures. This "Satisfiability Modulo Abstraction" (SMA) approach allows for reusing existing, robust abstract interpretation techniques to tackle complex logical satisfiability problems.
- Canonical Abstraction for Expressive Logic: The success in handling a richer fragment of separation logic demonstrates that canonical abstraction, while often associated with shape analysis, is a general-purpose method for abstracting complex data structures and can be adapted to various logical domains.
- Handling Negation and Linked Lists Together: A significant achievement is the ability to handle formulas with negations below separating conjunctions and in conjunction with linked list predicates. This is a capability that previous approaches struggled with.
- Model-Theoretic Approach: Unlike many proof-theoretic decision procedures, this method is model-theoretic. It works by constructing abstract models (shape graphs) that overapproximate the set of satisfying concrete models. If this overapproximation is empty, the formula is unsatisfiable.
- Residual Answers: The procedure can not only determine unsatisfiability but also provide a set of abstract models for satisfiable formulas. This "residual answer" capability is valuable for generating sound abstract transformers automatically.
Key Results
The experimental evaluation demonstrates the effectiveness of the proposed semi-decision procedure:
- Unsatisfiability Proofs: The procedure successfully proved unsatisfiability for a large number of formulas across all three test groups.
- Handling Previously Intractable Formulas: The paper highlights that many formulas in their test suite, particularly those involving linked lists and septraction, were beyond the capabilities of previously existing tools.
- Performance: For Group 1 formulas, the running time was often around one second (excluding TVLA's startup/shutdown time). For larger groups, the procedure was still efficient, with mean times for Group 2 and Group 3 being 0.56 and 0.12 seconds, respectively.
- Impact of Linked Lists: The presence of the
lspredicate significantly increased the number of structures needed to represent abstract values, leading to longer computation times for those specific formulas, but the procedure still managed to solve them.
Limitations and Future Work
- Negation Handling: While the paper handles negations at leaf nodes, extending it to handle general negation (e.g., negations below separating conjunctions) is noted as non-trivial. The abstract negation operation (
¬#) does not guarantee overapproximation of the models of the negated formula in all cases. - General Implications: Proving the validity of general implications (
φ1 ⇒ φ2) is also identified as a challenge. While the procedure can overapproximate models ofφ1andφ2separately, their conjunction (A1 ∧ A2) does not necessarily imply the implication. - Numeric Data: The current fragment does not support assertions about numeric-valued variables or fields. Extending the approach to handle these would require combining canonical abstraction with numeric abstractions.
- Separating Implication: The paper suggests that extending the technique to handle separating implication (
-*) alongside acyclic linked-list predicates is a promising future direction.
The authors believe their work is a significant step towards verification systems that can handle richer fragments of separation logic and automate the construction of program analysis tools.
Summary updated