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

Abstract

Strings are widely used in programs, especially in web applications. Integer data type occurs naturally in string-manipulating programs, and is frequently used to refer to lengths of, or positions in, strings. Analysis and testing of string-manipulating programs can be formulated as the path feasibility problem: given a symbolic execution path, does there exist an assignment to the inputs that yields a concrete execution that realizes this path? Such a problem can naturally be reformulated as a string constraint solving problem. Although state-of-the-art string constraint solvers usually provide support for both string and integer data types, they mainly resort to heuristics without completeness guarantees. 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 OSTRICH+. We evaluate the performance of OSTRICH+ on a wide range of existing and new benchmarks. The experimental results show that 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.

Introduction

In software verification and security analysis, symbolic execution is a cornerstone technique for identifying vulnerabilities such as Cross-Site Scripting (XSS). This process involves treating program inputs as symbols and constructing mathematical constraints to determine if a specific execution path—particularly one leading to a security exploit—is feasible.

Modern web applications rely heavily on complex string manipulations, including replaceAll, substring, and indexOf. These operations are frequently intertwined with integer logic, such as verifying if the length of a sanitized string remains within specific bounds. Mathematically, the combination of string concatenation and length functions is notoriously difficult, often leading to undecidability. Consequently, many existing solvers rely on heuristics that may time out or provide incomplete results when faced with complex, mixed-type constraints.

The OSTRICH+ Decision Procedure

This research introduces OSTRICH+, a decision procedure designed for "straight-line" programs (those represented in Single Static Assignment or SSA form). OSTRICH+ addresses the limitations of heuristic-based solvers by providing a complete and decidable framework for one of the most expressive string-integer constraint languages to date.

The procedure is built upon two primary innovations:

  1. Cost-Enriched Finite Automata (CEFA): While standard automata determine if a string belongs to a specific language, CEFAs extend this capability by adding "registers." These registers track integer values—such as string length or the specific position of a character—as the automaton processes the string. This allows the solver to directly link string content to integer variables within a unified model.
  2. Lazy Backward Reasoning: To manage the complexity of program paths, OSTRICH+ employs a backward reasoning strategy. It computes "pre-images," effectively working from the end of a path to determine what the input strings must have looked like to produce a given output. This approach avoids the exhaustive calculation of all possible solutions from the outset.

To mitigate the state-space explosion inherent in combining complex constraints, the authors integrated the nuXmv symbolic model checker. This integration allows the solver to navigate the massive number of possible states more efficiently.

Experimental Evaluation

The effectiveness of OSTRICH+ was evaluated against several major benchmarks, encompassing over 70,000 instances:

  • Transducer+: A new suite developed for this study that incorporates security-relevant integer properties (e.g., checking length changes after HTML escaping) into existing string benchmarks.
  • SLOG+: An adaptation of the SLOG suite, augmented with length and indexOf constraints.
  • PyEx: Over 25,000 instances derived from symbolic execution of Python programs.
  • Kaluza: A standard benchmark suite containing over 47,000 instances focused on string and length constraints.

Key Insights and Results

OSTRICH+ represents the first string decision procedure capable of handling both finite transducers (complex transformations like htmlEscape) and integer constraints simultaneously with a completeness guarantee. If a solution exists within the supported logic, OSTRICH+ is guaranteed to find it; if not, it will prove the path's infeasibility.

Despite the high theoretical complexity of the problem (NEXPSPACE), OSTRICH+ demonstrated competitive performance against state-of-the-art heuristic solvers like CVC4 and Z3-str3 on standard benchmarks. Notably, on the complex Transducer+ suite, OSTRICH+ solved 88 out of 94 instances within 30 seconds, while other solvers were either unable to process the transducer operations or timed out.

Conclusion and Future Work

OSTRICH+ identifies a "sweet spot" of decidability—a fragment of string-integer logic expressive enough for real-world applications yet restricted enough to remain theoretically sound. While the current procedure requires programs to be in a straight-line format and faces high worst-case complexity, it serves as a powerful proof-of-concept. Future work will focus on optimizing the implementation, potentially by using standard Non-deterministic Finite Automata (NFAs) for simpler constraints to further enhance execution speed.

Summary updated

Abstract

Strings are widely used in programs, especially in web applications. Integer data type occurs naturally in string-manipulating programs, and is frequently used to refer to lengths of, or positions in, strings. Analysis and testing of string-manipulating programs can be formulated as the path feasibility problem: given a symbolic execution path, does there exist an assignment to the inputs that yields a concrete execution that realizes this path? Such a problem can naturally be reformulated as a string constraint solving problem. Although state-of-the-art string constraint solvers usually provide support for both string and integer data types, they mainly resort to heuristics without completeness guarantees. 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 OSTRICH+. We evaluate the performance of OSTRICH+ on a wide range of existing and new benchmarks. The experimental results show that 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