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