title: "HAMPI: A Solver for String Constraints"
authors: Adam Kiezun, Vijay Ganesh, Philip J. Guo, Pieter Hooimeijer, Michael D. Ernst
venue: International Symposium on Software Testing and Analysis (ISSTA)
year: 2009
footer: "<font color=\"#AA0000\">ACM SIGSOFT Distinguished Paper Award, ISSTA 10-Year Impact Paper Award</font>"

tweet: HAMPI is a constraint solver for strings that makes automatic bug-finding tools more efficient

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, if any, effective and sufficiently expressive
  off-the-shelf solvers for string constraints generated by analysis
  techniques for string-manipulating programs.<br/><br/>We designed and
  implemented HAMPI, a solver for string constraints over bounded string
  variables. HAMPI constraints express membership in regular languages
  and bounded 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.<br/><br/>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 <a href="http://people.csail.mit.edu/akiezun/hampi/">http://people.csail.mit.edu/akiezun/hampi/</a>.

bibtex: >
  @inproceedings{KiezunHampi2009,
   author = {Kiezun, Adam and Ganesh, Vijay and Guo, Philip J. and Hooimeijer, Pieter and Ernst, Michael D.},
   title = {{HAMPI}: A Solver for String Constraints},
   booktitle = {Proceedings of the Eighteenth International Symposium on Software Testing and Analysis},
   series = {ISSTA '09},
   year = {2009},
   isbn = {978-1-60558-338-9},
   location = {Chicago, IL, USA},
   pages = {105--116},
   numpages = {12},
   url = {http://doi.acm.org/10.1145/1572272.1572286},
   doi = {10.1145/1572272.1572286},
   acmid = {1572286},
   publisher = {ACM},
   address = {New York, NY, USA},
   keywords = {context-free languages, regular languages, string constraints},
  }