MiniZinc with Strings

Roberto Amadini, Pierre Flener, Justin Pearson, Joseph D. Scott, Peter J. Stuckey, Guido Tack

TL;DR

This paper introduces native string support to MiniZinc, the industry-standard constraint modeling language. By providing a way to decompose complex string operations into standard integer constraints, the authors enable traditional solvers to tackle string-heavy problems in software verification and security without requiring native string logic.

What Problem Does This Paper Address?

Strings are the backbone of modern computing, yet they are notoriously difficult to reason about in formal logic. In fields like software analysis, test-case generation, and web security (e.g., detecting SQL injection), researchers need to solve constraints over strings of unknown lengths.

While specialized "string solvers" exist, the broader Constraint Programming (CP) community has largely lacked a unified way to model these problems. Most CP solvers are designed for integers and real numbers. Before this paper, if you wanted to use a powerful CP solver like Gecode or Chuffed on a string problem, you had to manually translate every string operation into complex integer arrays—a tedious and error-prone process.

Methods

The authors propose a two-pronged extension to the MiniZinc ecosystem:

  1. Language Extension: They introduced var string as a first-class citizen in MiniZinc. This includes a library of standard functions: concatenation (++), length (str_len), sub-string selection, and even complex constraints like Regular Expression (DFA/NFA) membership and Global Cardinality (counting character occurrences).
  2. The $\mathcal{F}^{int}$ Transformation: This is the "magic" under the hood. For solvers that don't support strings, MiniZinc now includes a library that automatically "flattens" string variables into arrays of integers (representing ASCII codes).
  3. Padding & Length: Since MiniZinc arrays usually have fixed sizes, the authors use an "open-sequence" representation. A string is mapped to an array of length $L$ (the maximum possible length), an integer variable for the actual length, and "trailing zeros" to pad the unused space.
  4. Automata Tweaking: To handle regular expression constraints (DFAs) on these padded arrays, they developed a method to modify the automaton so it correctly ignores the padding characters.

Datasets

The authors evaluated their framework using:

  • The Norn Benchmark: A set of five challenging problems (anb_n, ChunkSplit, HammingDistance, Levenshtein, and StringReplace) commonly used to test SMT (Satisfiability Modulo Theories) solvers.
  • The Palindrome Problem: A custom optimization problem designed to find the minimum-length palindrome with specific character counts—a task that tests both string logic and optimization capabilities.

Key Insights and Ideas

  • "Model Once, Solve Anywhere": The core philosophy of MiniZinc is now extended to strings. A researcher can write one model and test it against a native string solver (like Gecode+S) or a high-performance integer solver (like Chuffed) without changing a line of code.
  • Decomposition is Viable: The paper proves that you don't necessarily need a dedicated string solver to be efficient. By decomposing strings into integer constraints, general-purpose solvers can leverage their advanced search heuristics (like "lazy clause generation") to solve string problems effectively.
  • The Flattening Bottleneck: The biggest "aha moment" is that the bottleneck isn't always the solving time, but the compilation time. Turning a single string constraint into thousands of integer constraints for a long string can result in massive FlatZinc files (e.g., jumping from 14 lines to 45,000 lines).

Key Results

  • Native vs. Decomposed: Gecode+S (which has native string support) was generally the fastest and most robust across the board.
  • Surprising Performance: On certain benchmarks like the Palindrome problem, solvers using the $\mathcal{F}^{int}$ decomposition (like Chuffed and iZplus) actually outperformed native solvers in search speed, even if they took longer to "flatten" the model initially.
  • Scalability: The framework successfully handled string lengths up to 1,000 characters, though performance degrades as the maximum bound increases due to the quadratic growth of some decomposed constraints.

Limitations and Future Work

  • Alphabet Constraints: Currently, the implementation is limited to the ASCII character set (0-127). Extending this to Unicode would significantly increase the complexity of the integer decomposition.
  • The "Length" Problem: The decomposition requires a fixed maximum length ($L$). If a problem requires truly unbounded strings, this approach might miss solutions or require iterative deepening of the bound.
  • Search Heuristics: The authors suggest that future work should focus on "string-aware" search heuristics—teaching the solver to branch on character frequencies or string-specific patterns rather than just treating them as generic integer arrays.

Summary updated

Abstract

Strings are extensively used in modern programming languages and constraints over strings of unknown length occur in a wide range of real-world applications such as software analysis and verification, testing, model checking, and web security. Nevertheless, practically no CP solver natively supports string constraints. We introduce string variables and a suitable set of string constraints as builtin features of the MiniZinc modelling language. Furthermore, we define an interpreter for converting a MiniZinc model with strings into a FlatZinc instance relying on only integer variables. This provides a user-friendly interface for modelling combinatorial problems with strings, and enables both string and non-string solvers to actually solve such problems.
BibTeX
@inproceedings{amadini2016minizinc,
  author = {Roberto Amadini and Pierre Flener and Justin Pearson and Joseph D. Scott and Peter J. Stuckey and Guido Tack},
  title = {{MiniZinc with Strings}},
  booktitle = {LOPSTR},
  year = {2016},
  doi = {10.1007/978-3-319-63139-4\_4},
}

Loading related content...

Figure