Inter-theory dependency analysis for SMT string solvers
Minh-Thai Trinh, Duc-Hiep Chu, Joxan Jaffar
Abstract
Solvers in the framework of Satisfiability Modulo Theories (SMT) have been widely successful in practice. Recently there has been an increasing interest in solvers for string constraints to address security issues in web programming, for example. To be practically useful, the solvers need to support an expressive constraint language over unbounded strings, and in particular, over string lengths. Satisfiability checking for these formulas, especially in the SMT context, is very hard; it is generally undecidable for a rich fragment. In this paper, we propose a form of dependency analysis for a rich fragment of string constraints including high-level operations such as length, contains to deal with their inter-theory interaction so as to solve them more efficiently. We implement our dependency analysis in the string theory of the Z3 solver to obtain a new one, called S3N. Finally, we demonstrate the superior performance of S3N over state-of-the-art string solvers such as Z3str3, CVC4, S3P, and Z3 on several large industrial-strength benchmarks.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers2
Related papers
- Solving String Constraints with Lengths by StabilizationYu-Fang Chen, David Chocholatý, Vojtech Havlena, Lukás Holík et al.OOPSLA 2023 · 18 citations
- Solving String Split Constraints via Structural RelaxationRui Han, Ziheng Wang, Baoquan Cui, Yuhang Dong et al.ISSTA 2026
- An SMT Solver for Regular Expressions and Linear Arithmetic over String LengthMurphy Berzish, Mitja Kulczynski, Federico Mora, Florin Manea et al.CAV 2021 · 37 citations
- Even Faster Conflicts and Lazier Reductions for String SolversAndres Nötzli, Andrew Reynolds, Haniel Barbosa, Clark W. Barrett et al.CAV 2022 · 13 citations
- String Solving with Stabilization and TransducersDavid Chocholatý, Vojtech Havlena, Lukás Holík, Juraj Síc et al.CAV 2026
