CertiStr: a certified string solver

Shuanglong Kan, Anthony Widjaja Lin, Philipp Rümmer, Micha Schrader

TL;DR

This paper introduces CertiStr, the first certified string solver for concatenation and regular constraints. By formally proving its correctness in Isabelle/HOL, CertiStr offers a trustworthy solution for string manipulation problems, a common source of bugs and security vulnerabilities in software.

What Problem Does This Paper Address?

String manipulation is ubiquitous in modern programming, powering everything from web applications to system utilities. However, the inherent complexity of string operations makes them a frequent source of bugs and security vulnerabilities, such as cross-site scripting (XSS). Existing string solvers, while powerful, are often highly complex and prone to subtle implementation errors, making it difficult to trust their results. This paper addresses the need for a verified string solver that guarantees correctness, thereby increasing confidence in its outputs for critical applications.

Methods

CertiStr employs a forward-propagation algorithm to solve string constraints. This algorithm iteratively refines symbolic representations of regular constraints (symbolic automata) to detect contradictions or prove satisfiability. A key innovation is the development of a certified library for symbolic Non-deterministic Finite Automata (s-NFAs). These s-NFAs allow transition labels to be sets of characters, making them more efficient for handling large alphabets. The entire implementation, including the forward-propagation algorithm and the s-NFA library, has been formally proven correct in the Isabelle/HOL proof assistant. This ensures that the generated OCaml code is a faithful and correct implementation of the verified abstract algorithms.

Datasets

The paper evaluates CertiStr against the Kaluza benchmark, a standard benchmark for string solvers, containing approximately 38,000 string constraints.

Key Insights and Ideas

  • The Need for Trustworthy String Solvers: The paper highlights that string manipulation is a significant source of software bugs and security vulnerabilities, and existing solvers, despite their sophistication, often lack formal verification, making their results untrustworthy.
  • Formal Verification as a Solution: By using a proof assistant like Isabelle/HOL, CertiStr provides a rigorous guarantee of correctness, addressing the trust deficit in string solvers.
  • Symbolic Automata for Efficiency: The use of symbolic NFAs (s-NFAs) with character intervals as transition labels is crucial for handling the large alphabets common in string processing and for achieving practical efficiency.
  • Forward-Propagation as a Core Algorithm: The paper demonstrates that a relatively simple forward-propagation algorithm, when implemented correctly and combined with automata theory, can be surprisingly effective.
  • The "Tree Property" for Completeness: CertiStr can definitively prove satisfiability only for constraints satisfying a "tree property" (related to the acyclicity of the variable dependency graph). For other constraints, it may return "unknown," indicating that the forward-propagation alone is insufficient.

Key Results

CertiStr was evaluated on the Kaluza benchmark, with 80.4% of the tests falling within its supported fragment. Of these, CertiStr successfully solved 83.5% (returning "sat" or "unsat") within a 60-second time limit. The solver demonstrated high efficiency, terminating within 60 seconds for 98% of the tested constraints. While less efficient than highly optimized, unverified solvers like CVC4 on certain complex cases, CertiStr's verified nature provides a strong guarantee of correctness. The development effort involved approximately one person-year of work.

Limitations and Future Work

The paper acknowledges that CertiStr's completeness is limited to string constraints satisfying the "tree property." For constraints that do not satisfy this property, CertiStr may return "unknown." The authors also note that CertiStr can experience state and transition explosion for very complex constraints with many concatenations, leading to timeouts.

Future work includes:

  • Supporting more string operations, such as string replacement and capture groups, to increase applicability.
  • Verifying the front-end of CertiStr, which handles parsing and desugaring of string constraints.
  • Further optimizing the solver, potentially by improving language intersection and concatenation operations and implementing NFA minimization, while ensuring these optimizations are also formally verified.

Summary updated

Abstract

Theories over strings are among the most heavily researched logical theories in the SMT community in the past decade, owing to the error-prone nature of string manipulations, which often leads to security vulnerabilities (e.g. cross-site scripting and code injection). The majority of the existing decision procedures and solvers for these theories are themselves intricate; they are complicated algorithmically, and also have to deal with a very rich vocabulary of operations. This has led to a plethora of bugs in implementation, which have for instance been discovered through fuzzing. In this paper, we present CertiStr, a certified implementation of a string constraint solver for the theory of strings with concatenation and regular constraints. CertiStr aims to solve string constraints using a forward-propagation algorithm based on symbolic representations of regular constraints as symbolic automata, which returns three results: sat, unsat, and unknown, and is guaranteed to terminate for the string constraints whose concatenation dependencies are acyclic. The implementation has been developed and proven correct in Isabelle/HOL, through which an effective solver in OCaml was generated. We demonstrate the effectiveness and efficiency of CertiStr against the standard Kaluza benchmark, in which 80.4% tests are in the string constraint fragment of CertiStr. Of these 80.4% tests, CertiStr can solve 83.5% (i.e. CertiStr returns sat or unsat) within 60s.
BibTeX
@inproceedings{kan2022certistr,
  author = {Shuanglong Kan and Anthony Widjaja Lin and Philipp Rümmer and Micha Schrader},
  title = {{CertiStr: a certified string solver}},
  booktitle = {CPP},
  year = {2022},
  doi = {10.1145/3497775.3503691},
}
Figure