  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.
