We address the issue of automatic invariant synthesis for sequential programs manipulating singly-linked lists carrying data over infinite data domains. We define for that a framework based on abstract interpretation which combines a specific finite-range abstraction on the shape of the heap with an abstract domain on sequences of data, considered as a parameter of the approach. We instantiate our framework by introducing different abstractions on data sequences allowing to reason about various aspects such as their sizes, the sums or the multisets of their elements, or relations on their data at different (linearly ordered or successive) positions. To express the latter relations we define a new domain whose elements correspond to an expressive class of first order universally quantified formulas. We have implemented our techniques in an efficient prototype tool and we have shown that our approach is powerful enough to generate non-trivial invariants for a significant class of programs. We define µ 1 ⊔ M µ 2 to be the conjunction of atomic formulas that appear in both Saturate(µ 1 ) and Saturate(µ 2 ). The meet operator µ 1 ⊓ M µ 2 is defined to be the conjunction of atomic formulas that appear in Saturate(µ 1 ) or Saturate(µ 2 ). Since our abstract domain contains a finite number of elements, we may consider ∇ M = ⊔ M . Abstractions of k-heap graphs as in Figure 5 are called k-abstract heap graphs. In the following definition, we assume that for each node of a heap graph there exists a data word variable with the same name. Definition 3. A k-abstract heap over PVar, DVar, and a DW-domain A W is a tuple H = N, S,V, W where N, S,V are as in the definition of k-heap graphs, and W is an abstract value in A W over the data word variables N − {♯} and the data variables DVar. Next, we define the domain of k-abstract heap graphs parametrized by A W , denoted by A H (k, A W ). Two abstract heap graphs are isomorphic when their underlying graphs The lattice operators of this domain are obtained by applying the corresponding operators from A W between abstract values which belong to isomorphic abstract heap graphs. Thus, for any H = N, S,V, W and the abstract values such that they use the same variable for isomorphic nodes) and (2) for The join and the widening (meet, resp.) of two nonisomorphic abstract heap graphs is ⊤ W (⊥ W , resp.). Proposition 1. The entailment relation ⊑ H is sound, that is, H ⊑ H H ′ implies γ H ( H) ⊆ γ H ( H ′ ). Also, ⊔ H and ⊓ H are the least upper bound and greatest lower bound, respectively, and ∇ H is a widening operator. Proof: The properties of ⊑ H , ⊔ H , and ⊓ H , resp. follow directly from similar properties of ⊑ W , ⊔ W , and ⊓ W , resp. The proof for the widening operator relies on the fact that the heaps generated by the class of programs considered in Section 2 contain a bounded number of cut points [17]. 2 Notice that ⊑ H is not complete. That is, we can find two abstract heaps H and H ′ such that γ H ( H) ⊆ γ H ( H ′ ) does not imply H ⊑ H H ′ . Based on the Galois connection (α W , γ W ) we define the Galois connection (α H , γ H ) between the lattice of sets of k-heap graphs and A H (k, A W ). The value of α H for a set of isomorphic k-heap graphs S is the underlying graph of the input heap graphs together with a value in A W obtained by applying α W to The value of α H for a set of k-heap graphs containing at least two non-isomorphic heap graphs is ⊤ H . The concretization function γ H is defined using γ W in a similar manner. We define A HS (k, A W ) = L HS (k, A W ), ⊑ HS , ⊓ HS , ⊔ HS , ⊤ HS , ⊥ HS as a finite powerset domain corresponding to A H (k, A W ). Its elements are called k-abstract heap sets. Definition 4. A k-abstract heap set over PVar, DVar, and a DW-domain A W is a finite set of non-isomorphic k-abstract heap graphs over PVar, DVar, and A W . The operators associated to A HS (k, A W ) and its widening operator are obtained from those of A H (k, A W ) as usual [7]. The entailment relation ⊑ HS is the usual Hoare powerdomain partial order [1], that is, for any A H and A ′ H in A HS (k, A W ), A H ⊑ HS A ′ H iff for any H ∈ A H there exists H ′ ∈ A ′ H such that H ⊑ H H ′ . Let A H and A ′ H ∈ L HS . To make uniform the definitions of all operators of the abstract domain, we suppose that for any abstract heap N, S,V, W ∈ A H for which we can not find an isomorphic abstract heap in A ′ H we add to A ′ H the abstract heap (N, S,V, ⊥ W ) and vice-versa. Then, for any ‡ ∈ {⊔, ⊓, ∇} we define A H ‡ HS A ′ H to be the abstract heap set that contains for any two abstract heaps H = N, S,V, W ∈ A H and H . Also, ⊔ HS and ⊓ HS are the least upper bound and greatest lower bound, respectively, and ∇ HS is a widening operator. Proof: Directly from the properties of ⊑ H , ⊔ H , ⊓ H , and ∇ H . 2 As in the previous case, notice that ⊑ HS is not complete. The Galois connection (α HS , γ HS ) between the lattice of sets of k-heap graphs and A HS (k, A W ) is defined as follows. The abstraction function α HS applied to some set of k-heap graphs S returns a finite set of k-abstract heap graphs, one for each equivalence class of S with respect to the isomorphism relation. This k-abstract heap graph is defined by applying α H to the set of heap graphs in the equivalence class. The concretization function γ HS is a point-wise extension of γ H . The abstract postcondition operator on abstract heap sets corresponding to post k , denoted post # k , is obtained by replacing every concrete transformer F ∈ {sglt, isSglt, split, proj, updateFirst, concat} with its abstraction F # . For example, the abstract version of the procedure Uncover, denoted Uncover # , used in post # k (free(p), A H ) is given in Figure 6 . For any abstract heap graph H = N, S,V, W in the abstract heap set A H , Uncover # (A H , p) does one of the following:
Bouajjani et al. REF automatically synthesize invariants for list manipulating programs over infinite data domains using a graph representation of heap.
Invariant Synthesis for Programs Manipulating Lists with Unbounded Data
CAV
Computer Science