  Satisfiability solvers are increasingly playing a key role in software
verification, with particularly effective use in the analysis of security
vulnerabilities. String processing is a key part of many software applications,
such as browsers and web servers. These applications are susceptible to attacks
through malicious data received over network. Automated tools for analyzing the
security of such applications, thus need to reason about strings. For
efficiency reasons, it is desirable to have a solver that treats strings as
first-class types. In this paper, we present some theories of strings that are
useful in a software security context and analyze the computational complexity
of the presented theories. We use this complexity analysis to motivate a
byte-blast approach which employs a Boolean encoding of the string constraints
to a corresponding Boolean satisfiability problem.
