A Decision Procedure for Path Feasibility of String Manipulating Programs with Integer Data Type

Taolue Chen, Matthew Hague, Jinlong He, Denghang Hu, Anthony Widjaja Lin, Philipp Rümmer, Zhilin Wu

TL;DR

This paper introduces OSTRICH+, a new decision procedure for checking the feasibility of program paths that involve both complex string manipulations and integer data types. By utilizing a novel automata model called Cost-Enriched Finite Automata (CEFA), the authors provide a complete and decidable solver for one of the most expressive string-integer constraint languages to date.

What Problem Does This Paper Address?

In software verification and security analysis, "symbolic execution" is a popular technique used to find bugs like Cross-Site Scripting (XSS). This involves treating program inputs as symbols and building mathematical constraints to see if a specific "bad" path (like one leading to an exploit) is actually possible.

The challenge is that modern programs don't just concatenate strings; they use complex operations like replaceAll, substring, and indexOf, often mixing them with integer logic (e.g., checking if the length of a sanitized string is less than the original). Mathematically, combining string concatenation with length functions is a notorious "hard" problem that often leads to undecidability—meaning it's impossible to build a tool that is guaranteed to always give a correct "yes" or "no" answer. Most existing solvers rely on heuristics that can time out or give up on complex cases.

Methods

The authors propose a decision procedure for "straight-line" programs (those in Single Static Assignment or SSA form). Their approach centers on two main innovations:

  1. Cost-Enriched Finite Automata (CEFA): Standard automata just tell you if a string belongs to a language. CEFAs add "registers" that can track integer values (like length or the position of a character) as the automaton reads the string. This allows the solver to link string content directly to integer variables.
  2. Lazy Backward Reasoning: Instead of trying to calculate every possible solution from the start, OSTRICH+ works backward from the end of a program path. It computes "pre-images"—essentially asking, "What must the input strings have looked like to produce this specific output?"
  3. Integration with Model Checking: To handle the "state-space explosion" that happens when combining many complex constraints, the authors integrated the nuXmv symbolic model checker. This helps the solver efficiently navigate the massive number of possible states.

Datasets

The authors evaluated OSTRICH+ against several major benchmarks, including:

  • Transducer+: A new benchmark suite created for this paper. It adds security-relevant integer properties (like checking if a string's length changes after HTML escaping) to existing string-only benchmarks.
  • SLOG+: An adaptation of the SLOG suite, adding length and indexOf constraints.
  • PyEx: Over 25,000 instances derived from a symbolic execution tool for Python programs.
  • Kaluza: A massive, well-known benchmark (47,000+ instances) focused on string and length constraints.

Key Insights and Ideas

  • The "Sweet Spot" of Decidability: The authors identified a specific fragment of string-integer logic that is expressive enough for real-world web applications but restricted enough (via the SSA form) to remain theoretically decidable.
  • Decoupling Integers: A key trick in their CEFA model is keeping integer constraints "detached" from the core automaton transitions. This preserves the independence of different string variables, preventing the solver from getting bogged down in unnecessary dependencies.
  • Completeness Matters: Unlike many popular solvers (like CVC4 or Z3-str3) that use heuristics, OSTRICH+ provides a completeness guarantee for its supported logic. If a solution exists, it will find it; if not, it will prove it.

Key Results

  • First of its Kind: OSTRICH+ is the first string decision procedure capable of handling both finite transducers (complex transformations like htmlEscape) and integer constraints simultaneously with a completeness guarantee.
  • Competitive Performance: Despite the high theoretical complexity (NEXPSPACE), OSTRICH+ performed comparably to state-of-the-art heuristic solvers on standard benchmarks like Kaluza and PyEx.
  • Superiority on Complex Tasks: On the new Transducer+ suite, OSTRICH+ solved 88 out of 94 instances within 30 seconds (and all 94 with a longer timeout), while other solvers either timed out or were unable to process the transducer operations at all.

Limitations and Future Work

  • SSA Restriction: The current procedure requires the program to be in a "straight-line" format. It cannot directly handle complex loops or cycles in the constraints without further preprocessing.
  • Theoretical Complexity: The worst-case complexity is extremely high. While the "lazy" approach works well in practice, there are likely edge cases where the state space could still explode.
  • Optimization: The authors suggest that for simpler constraints, using standard NFAs (Nondeterministic Finite Automata) instead of the more complex CEFAs could provide a significant speed boost. They view the current implementation as a proof-of-concept that can be further engineered for speed.

Summary updated

Abstract

In this paper, we propose a decision procedure for a class of string-manipulating programs which includes not only a wide range of string operations such as concatenation, replaceAll, reverse, and finite transducers, but also those involving the integer data-type such as length, indexof, and substring. To the best of our knowledge, this represents one of the most expressive string constraint languages that is currently known to be decidable. Our decision procedure is based on a variant of cost register automata. We implement the decision procedure, giving rise to a new solver \(\text {OSTRICH+}\). We evaluate the performance of \(\text {OSTRICH+}\) on a wide range of existing and new benchmarks. The experimental results show that \(\text {OSTRICH+}\) is the first string decision procedure capable of tackling finite transducers and integer constraints, whilst its overall performance is comparable with the state-of-the-art string constraint solvers.
BibTeX
@inproceedings{chen2020decision,
  author = {Taolue Chen and Matthew Hague and Jinlong He and Denghang Hu and Anthony Widjaja Lin and Philipp Rümmer and Zhilin Wu},
  title = {{A Decision Procedure for Path Feasibility of String Manipulating Programs with Integer Data Type}},
  booktitle = {ATVA},
  year = {2020},
  url = {https://openreview.net/forum?id=iJcHMpXd5A},
}

Loading related content...

Figure