Name
Abstract | ||
|---|---|---|
Many automatic testing, analysis, and verification techniques for programs can be effectively reduced to a constraint generation phase followed by a constraint-solving phase. This separation of concerns often leads to more effective and maintainable tools. The increasing efficiency of off-the-shelf constraint solvers makes this approach even more compelling. However, there are few effective and sufficiently expressive off-the-shelf solvers for string constraints generated by analysis techniques for string-manipulating programs. We designed and implemented Hampi, a solver for string constraints over fixed-size string variables. Hampi constraints express membership in regular languages and fixed-size context-free languages. Hampi constraints may contain context-free-language definitions, regular language definitions and operations, and the membership predicate. Given a set of constraints, Hampi outputs a string that satisfies all the constraints, or reports that the constraints are unsatisfiable. Hampi is expressive and efficient, and can be successfully applied to testing and analysis of real programs. Our experiments use Hampi in: static and dynamic analyses for finding SQL injection vulnerabilities in Web applications; automated bug finding in C programs using systematic testing; and compare Hampi with another string solver. Hampi's source code, documentation, and the experimental data are available at http://people.csail.mit.edu/akiezun/hampi. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1572272.1572286 | ISSTA |
Keywords | Field | DocType |
automated bug finding,string solver,systematic testing,dynamic analysis,analysis technique,string constraint,fixed-size string variable,constraint generation phase,automatic testing,hampi constraint,regular language,regular languages,context free languages | Context-free language,Programming language,Source code,Computer science,Separation of concerns,Theoretical computer science,Solver,Web application,Regular language,Predicate (grammar),SQL injection | Conference |
Citations | PageRank | References |
143 | 5.01 | 33 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Adam Kiezun | 1 | 566 | 27.47 |
| Vijay Ganesh | 2 | 1563 | 94.66 |
| Philip J. Guo | 3 | 1882 | 86.27 |
| Pieter Hooimeijer | 4 | 598 | 26.19 |
| Michael D. Ernst | 5 | 6629 | 347.51 |