Lune

OOPSLA2020Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Static Inference of Regular Grammars for Ad Hoc Parsers cites Human-in-the-loop oracle learning for semantic bugs in string processing programs
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Human-in-the-loop oracle learning for semantic bugs in string processing programsCharaka Geethal Kapugama, Van-Thuan Pham, Aldeida Aleti, Marcel BöhmeISSTA 2022 · 10 citations
  2. Static Inference of Regular Grammars for Ad Hoc ParsersMichael Schröder, Jürgen CitoOOPSLA 2025 · 1 citation

Related papers

  1. Solving String Constraints with Lengths by StabilizationYu-Fang Chen, David Chocholatý, Vojtech Havlena, Lukás Holík et al.OOPSLA 2023 · 18 citations
  2. Solving String Split Constraints via Structural RelaxationRui Han, Ziheng Wang, Baoquan Cui, Yuhang Dong et al.ISSTA 2026
  3. 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
  4. Even Faster Conflicts and Lazier Reductions for String SolversAndres Nötzli, Andrew Reynolds, Haniel Barbosa, Clark W. Barrett et al.CAV 2022 · 13 citations
  5. String Solving with Stabilization and TransducersDavid Chocholatý, Vojtech Havlena, Lukás Holík, Juraj Síc et al.CAV 2026
Dusk over the sea between two cliffs drawn in fine vertical lines