About STP

    STP is a constraint solver (also referred to as a decision procedure or automated prover) aimed at solving constraints generated by program analysis tools, theorem provers, automated bug finders, biology, cryptography, intelligent fuzzers and model checkers.  STP has been used in many research projects at Stanford, Berkeley, MIT, CMU and other universities. It is also being used at many companies such as NVIDIA, Apple, etc.

    The input to STP are formulas over the theory of bit-vectors and arrays. This theory captures most expressions from languages like C,C++,Java, Verilog etc. STP can tell if the input formula is satisfiable or not and if is, then it can also generate a variable assignment to satisfy the input formula. This output can then be used as the input to trigger a bug in a program or an input to trigger a fault in the VHDL system.
STP is based on the papers: A Decision Procedure for Bit-vectors and Arrays by Vijay Ganesh and David L. Dill. In Proceedings of the International Conference in Computer Aided Verification (CAV 2007), Berlin, Germany, July 2007 and EXE: Automatically Generating Inputs of Death by Cristian Cadar, Vijay Ganesh, Peter Pawlowski, Dawson Engler, David Dill. In Proceedings of ACM Conference on Computer and Communications Security 2006 (CCS 2006), Alexandria, Virginia, October, 2006

Download

The code is available on GitHub. Building the source from the tree should always work.

Help

If you have any issue building or using the system, please file an issue at the GitHub repository.
User group on google groups

Bindings

Authors

  • Project Founder: Dr. Vijay Ganesh, Assistant Professor, University of Waterloo, Ontario, Canada
  • Trevor Hansen, PhD Student, University of Melbourne, Australia
  • Maintainers: Ryan Govostes, Dan Liew, Mate Soos
Past contributors: Khoo Yit Phang, Ed Schwartz, Mike Katelman (PhD Student, University of Illinois, Urbana-Champaign, IL, USA), Philip Guo (Student, Stanford University, Stanford, CA, USA), David L. Dill (Professor, Stanford University, Stanford, CA, USA), Tim King (Student, Stanford University and NYU)
Please note that everyone working on the project is doing so out of hobby or as a way to help them in their work/study projects. Response times are pretty short but some delay is expected. Issues do get resolved but given the complexity of the system, it can take a while.

History

The STP constraint solver was written by Vijay Ganesh mostly in 2006 as part of his PhD thesis work at Stanford University under the supervision of Professor David L. Dill. Development froze in the second half of 2007 and most of 2008/2009. There was brief spurt of activity when Mike Katelman (University of Illinois, Urbana-Champaign) worked on the clausal normal form generation phase of STP while at NVIDIA during the summer of 2008. In spring of 2009 Trevor Hansen (University of Melbourne, Australia) took it upon himself to clean up parts of STP code, especially the SMTLIB parser. Vijay restarted work on STP in late summer/fall of 2009, aiming the solver at bio and crypto problems.