Abstract
We present a novel length-aware solving algorithm for the quantifier-free first-order theory over regex membership predicate and linear arithmetic over string length. We implement and evaluate this algorithm and related heuristics in the Z3 theorem prover. A crucial insight that underpins our algorithm is that real-world instances contain a wealth of information about upper and lower bounds on lengths of strings under constraints, and such information can be used very effectively to simplify operations on automata representing regular expressions. Additionally, we present a number of novel general heuristics, such as the prefix/suffix method, that can be used in conjunction with a variety of regex solving algorithms, making them more efficient. We showcase the power of our algorithm and heuristics via an extensive empirical evaluation over a large and diverse benchmark of 57,256 regex-heavy instances, almost 75% of which are derived from industrial applications or contributed by other solver developers. Our solver outperforms five other state-of-the-art string solvers, namely, CVC4, OSTRICH, Z3seq, Z3str3, and Z3-Trau, over this benchmark, in particular achieving a 2.4x speedup over CVC4, 4.4x speedup over Z3seq, 6.4x speedup over Z3-Trau, 9.1x speedup over Z3str3, and 13x speedup over OSTRICH.
Introduction
In modern software analysis—ranging from security vulnerability scanning to symbolic execution—string constraints are ubiquitous. Developers frequently use regular expressions (regex) to validate inputs, but verifying that these inputs also satisfy specific length requirements (e.g., "a password must match this regex AND be exactly 12 characters long") is computationally expensive.
The core challenge lies in the "theory of strings." While checking if a string matches a regex is standard, combining that with linear integer arithmetic over string lengths creates a difficult search space. Traditional solvers often rely on converting regexes into finite automata and performing expensive operations like intersections. These operations can "blow up" in complexity, leading to timeouts or memory exhaustion. Furthermore, the most expressive versions of these theories are actually undecidable, meaning no algorithm can solve every possible instance. This paper introduces Z3str3RE, a solver designed to mitigate these issues through length-aware heuristics and lazy automata operations.
The Z3str3RE Approach: Length-Awareness
Z3str3RE is integrated into the Z3 theorem prover and treats string length as a primary tool for pruning the search space rather than an afterthought. The solver functions as a bridge between a regex engine and an integer arithmetic solver, passing refined bounds back and forth to narrow down solutions. Key techniques include:
1. Length Abstraction
Before building a complex automaton, the solver derives length constraints directly from the regex syntax. For example, if a string must match (abc)*, the solver immediately knows its length must be a multiple of three ($len(s) = 3n$). By extracting this information early, the solver can avoid the "automata explosion" that plagues other solvers.
2. Lazy Automata Operations
Instead of intersecting multiple automata upfront—a quadratic-time operation—Z3str3RE delays these operations as long as possible. It uses simpler length checks to prove unsatisfiability (UNSAT) first, only performing heavy automata construction when necessary.
3. The Prefix/Suffix Heuristic
This is a fast syntactic check. If one constraint dictates a string must start with 'a' and another says it must start with 'b', the solver can declare the constraints unsatisfiable instantly without ever constructing an automaton. This structural inspection often replaces expensive state-machine intersections.
4. Shortest/Longest Path Refinement
The solver uses the physical structure of the automata to tighten the bounds on string length variables. By calculating the shortest and longest paths through an automaton, the solver provides the underlying arithmetic solver with tighter constraints, accelerating the search for a valid length.
Empirical Evaluation
The authors evaluated Z3str3RE against a massive suite of 57,256 instances, many of which are "regex-heavy." The benchmarks include:
- AutomatArk: Nearly 20,000 real-world regex queries.
- RegEx-Collected: Over 22,000 instances from established security and analysis suites like AppScan and Kaluza.
- StringFuzz: Approximately 15,000 instances, including those derived from industrial security policies at Amazon Web Services (AWS), designed to be particularly difficult for solvers.
Performance Results
Z3str3RE emerged as the clear leader across all tested benchmarks, outperforming five other major solvers (CVC4, OSTRICH, Z3seq, Z3str3, and Z3-Trau).
- Speed: It achieved a 2.4x speedup over CVC4 and a 13x speedup over OSTRICH.
- Efficiency: It solved the highest number of instances (56,159) and recorded the fewest timeouts.
- Reliability: Unlike some competitors, Z3str3RE produced zero soundness errors or program crashes, making it a robust choice for industrial applications.
Conclusion and Future Work
Z3str3RE demonstrates that length is a powerful filter, not just a constraint. While the solver is complete for the theory of regex membership and length arithmetic ($T_{LRE}$), adding features like string-to-number conversion (str.to_int) alongside concatenation can make the theory undecidable. Z3str3RE currently handles these via heuristics, but cannot guarantee a solution in all such cases. Future work involves extending these length-aware heuristics to more expressive functions like indexof and substr, which are common in web application code but remain difficult for current solvers to reason about efficiently.
Summary updated