Efficient and Complete FD-solving for extended array constraints

Quentin Plazar, Mathieu Acher, Sébastien Bardin, Arnaud GotliebIJCAI 2017 · DOI

TL;DR

This paper introduces a novel technique to efficiently and completely solve constraints involving arrays, even when array sizes are unknown or unbounded. By transforming complex array constraints into a simpler, equisatisfiable form, their method significantly outperforms existing finite-domain solvers and competes with state-of-the-art SMT solvers, particularly for smaller array sizes.

What Problem Does This Paper Address?

Automated reasoning and software verification heavily rely on handling data structures, with arrays being a fundamental component. Traditional finite-domain (FD) solvers struggle when constraints involve array indices and elements simultaneously, especially for arrays with unknown or unbounded sizes. Existing methods often fall back to brute-force search or are limited to fixed-size arrays, making them impractical for many real-world verification scenarios. This paper aims to bridge this gap by providing an efficient and complete FD-solving technique for extended array constraints, including those with unbounded sizes.

Methods

The core of the paper is a formula transformation technique called array reduction. This process converts a formula with potentially unbounded array constraints into an equisatisfiable formula using only fixed-size arrays, making it amenable to standard FD solvers. The transformation involves several key steps:

  1. Preprocessing (Purification): Rewriting literals to separate array operators from arithmetic operators and flattening array constraints.
  2. Size Constraint Elimination: Removing explicit size constraints by encoding their semantics into the arithmetic part of the formula.
  3. Index Reduction: Isolating array-based reasoning on indices from arithmetic reasoning by introducing "reduced indices." This step is crucial for handling unbounded arrays and involves adding consistency constraints to maintain equisatisfiability.
  4. Size Fixing: Assigning fixed sizes to arrays and defining domains for the reduced indices, enabling the use of standard FD techniques.

The authors also introduce a new global constraint, consistent, to efficiently propagate consistency between the original and reduced indices.

Datasets

Not discussed in the paper. The paper uses a benchmark of 2200 formulas derived from the SMT-COMP benchmark, specifically focusing on pure array formulas. These formulas were then augmented with size constraints of 10, 100, and 1000 to evaluate performance across different array sizes.

Key Insights and Ideas

  • Distinguished Array Cells: The insight that only array cells referenced by index expressions matter for satisfiability is key to handling unbounded arrays. By focusing on these "distinguished" cells, the problem can be reduced to a finite representation.
  • Equality-Based Reasoning: For pure array theory, the exact values of indices are less important than their (dis)equalities. This observation underpins the transformation's ability to abstract away specific index values.
  • Implicit Equality Encoding: The transformation implicitly encodes index (dis)equalities by bounding arrays to a size related to the number of index expressions and assigning indices within this bound. This allows for finite encoding and a reduced search space.
  • Proxying/Array Isolation: To handle extended array constraints (beyond pure array theory), the technique separates array-based reasoning from other constraints on indices by introducing proxy variables. This allows FD solvers to manage array aspects while other solvers handle arithmetic.

Key Results

The experimental evaluation demonstrates significant improvements:

  • Unbounded Arrays: Array reduction enables FD techniques to solve a large majority (526/550) of previously unsolvable unbounded array formulas.
  • Bounded Arrays: For fixed-size arrays, the technique provides a dramatic improvement, solving 2.5x to 6.5x more formulas compared to standard FD solvers, with larger improvements for larger array sizes.
  • FD vs. SMT: The augmented FD solvers (fd" and fdcc") compete favorably with state-of-the-art SMT solvers. They significantly outperform SMT on small array sizes (e.g., 536 vs. 463 formulas solved) and are only slightly inferior on larger or unbounded arrays (526 vs. 550 formulas solved).

Limitations and Future Work

  • Limitations: While the approach significantly improves performance, it doesn't eliminate the need for global reasoning in certain complex cases, as noted by the authors regarding fdcc's capabilities. The current implementation is limited to array and integer theories for SMT-LIB compatibility.
  • Future Work: The authors suggest that this work opens the door for automated constraint-based reasoning on a wider range of data structures. Future directions could involve extending the technique to handle more complex theories and data structures, and further optimizing the propagation of consistency constraints.

Summary updated

BibTeX
@inproceedings{plazar2017efficient,
  author = {Quentin Plazar and Mathieu Acher and Sébastien Bardin and Arnaud Gotlieb},
  title = {{Efficient and Complete FD-solving for extended array constraints}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/171},
}

Loading related content...

Figure