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.
Introduction
String manipulation is the backbone of modern web applications, but it is notoriously error-prone. Mistakes in how strings are concatenated or filtered often lead to critical security vulnerabilities like Cross-Site Scripting (XSS) and SQL injection. To catch these bugs, developers use Satisfiability Modulo Theories (SMT) solvers—tools that check if a set of string constraints can ever be met. However, existing high-performance string solvers (like Z3 or CVC4) are incredibly complex, making them prone to implementation bugs. CertiStr addresses this by providing a certified solver, where the implementation itself is proven to follow its logical specification in the Isabelle/HOL proof assistant, eliminating the risk of internal logic errors.
Methodology and Architecture
CertiStr is built upon a two-pronged approach: a forward-propagation algorithm and a novel certified library for symbolic automata. Unlike the complex backtracking searches common in other solvers, CertiStr starts with known regular expression constraints and "pushes" them through string equations (e.g., $x = y + z$) to derive new constraints.
To handle large alphabets like Unicode efficiently, CertiStr implements Symbolic Non-deterministic Finite Automata (s-NFAs). In s-NFAs, transitions are labeled with sets of characters (represented as intervals) rather than single characters. The entire core logic was developed in Isabelle/HOL, ensuring soundness (unsat results are mathematically impossible to satisfy) and termination for acyclic constraints. The verified logic is then exported to executable OCaml code.
Key Insights: The Tree Property
A significant contribution of this work is the identification of the "tree property" for completeness. The authors proved that if string variables are structured like a tree—where each variable appears at most once on the right-hand side of an equation—forward propagation is sufficient to guarantee satisfiability. This provides a clear boundary for when the solver's "sat" result can be fully trusted.
Evaluation and Results
The authors evaluated CertiStr against the Kaluza benchmark, the gold standard for string solver evaluation, which contains roughly 47,284 test cases.
- Effectiveness: CertiStr solved 83.5% of the supported Kaluza tests (returning either
satorunsat). Supported tests accounted for 80.4% of the total benchmark. - Efficiency: Despite the overhead of formal verification, CertiStr is remarkably fast. 98% of the tests were completed within a 60-second timeout, with an average time of 1.87 seconds per test.
- Reliability: Unlike unverified solvers, CertiStr's results for
unsatare backed by machine-checked proofs, making it a reliable tool for security-critical applications.
Conclusion and Future Work
CertiStr demonstrates that simplicity, when combined with formal verification, can be highly competitive. It currently focuses on concatenation and regular expressions, but future work aims to extend the solver to support string replacement and capture groups. By providing a certified "source of truth," CertiStr represents a significant step forward in the reliability of SMT-based security analysis.
Summary updated