Proving Data Structure Properties by Automatic Induction

Minh-Thai Trinh, Duc-Hiep Chu and Joxan Jaffar


Motivated by the vulnerability analysis of web programs which work on string inputs, we present S3, a new symbolic string solver. Our solver employs a new algorithm for a constraint language that is expressive enough for widespread applicability. Specifically, our language covers all the main string operations, such as those in JavaScript. The algorithm first makes use of a symbolic represen- tation so that membership in a set defined by a regular expression can be encoded as string equations. Secondly, there is a constraint- based generation of instances from these symbolic expressions so that the total number of instances can be limited. We evaluate S3 on a well-known set of practical benchmarks, demonstrating both its robustness (more definitive answers) and its efficiency (about 20 times faster) against the state-of-the-art.