Hampi

A Solver for String Constraints



Hampi is a solver for string constraints. Hampi is designed for constraints generated by program analysis tools, automated bug finders, intelligent fuzzers.

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.

NEW: Hampi can now parse Perl-like regular expressions, eg: /^(:)([\w-]+)\("?'?(.*(\(.*\))?[^(]*)"?'?\)/. See the wiki page for documentation. Thanks to Devdatta Akhave for the contribution!

Hampi

Hampi code at Google Code
(download from SVN: svn checkout http://hampi.googlecode.com/svn/trunk/ hampi-read-only)

Documentation including examples, usage, formal grammar
MIT License
Mailing list for developers and users

Paper

Adam Kiezun, Vijay Ganesh, Philip J. Guo, Pieter Hooimeijer, Michael D. Ernst
HAMPI: A Solver For String Constraints
In ISSTA 2009: ACM International Symposium on Testing and Analysis, (Chicago, Illinois, USA), July 19-23, 2009.
ACM SIGSOFT Distinguished Paper Award

Experimental data and results (these are partial - there is much more experimental data in SVN)

Contributors

Adam Kiezun, project leader (Harvard Medical School/Brigham and Women's Hospital, Boston, USA)
Vijay Ganesh (MIT)
Philip Guo (Stanford University)
Pieter Hooimeijer (University of Virginia)
Devdatta Akhave (UC Berkeley)
Shay Artzi (IBM Research)
Michael D. Ernst (University of Washington)