CVC4 is an efficient open-source automatic theorem prover for satisfiability modulo theories (SMT) problems. It can be used to prove the validity (or, dually, the satisfiability) of first-order formulas in a large number of built-in logical theories and their combination.
CVC4 is the fourth in the Cooperating Validity Checker family of tools (CVC, CVC Lite, CVC3) but does not directly incorporate code from any previous version. A joint project of NYU and U Iowa, CVC4 aims to support the features of CVC3 and SMT-LIBv2 while optimizing the design of the core system architecture and decision procedures to take advantage of recent engineering and algorithmic advances.
CVC4 is intended to be an open and extensible SMT engine, and it can be used as a stand-alone tool or as a library, with essentially no limit on its use for research or commercial purposes (see license).
The fourth stable release of CVC4 (version 1.3) has been officially released. It is available for download (as are nightly development builds) via the links below.
CVC4 works with a version of first-order logic with polymorphic types and has a wide variety of features including:
- several built-in base theories: rational and integer linear arithmetic, arrays, tuples, records, inductive data types, bit-vectors, strings, and equality over uninterpreted function symbols;
- support for quantifiers;
- an interactive text-based interface;
- a rich C++ API for embedding in other systems;
- model generation abilities.
Official CVC4 binaries can be downloaded from our build pages:
- Linux 64-bit: optimized | debug
- Windows 32-bit: optimized | debug
- Debian packages
- Mac installers
- MacPorts (see instructions on setup)
Distribution source code and API documentation are from the same site as the binaries, and our source repository is hosted at GitHub. For instructions on how to build CVC4 from source, please see the build instructions.
Please send all bug reports to firstname.lastname@example.org, or use the CVC4 Bugzilla tracker. If you have a question, a feature request, or would like to contribute in some way, please contact one of the project leaders. The CVC-USERS list is for users of CVC3 and CVC4. We will make periodic announcements to this list and users are also encouraged to use it for discussion.
If you are a CVC4 user with an interesting application, and you would like to share your experience with other CVC4 users, we encourage you to write a description in our designated open wiki page.
History of CVC
The Cooperating Validity Checker series has a long history. The Stanford Validity Checker (SVC) came first in 1996, incorporating theories and its own SAT solver. Its successor, the Cooperating Validity Checker (CVC), had a more optimized internal design, produced proofs, used the Chaff SAT solver, and featured a number of usability enhancements. Its name comes from the cooperative nature of decision procedures in Nelson-Oppen theory combination, which share amongst each other equalities between shared terms. CVC Lite, first made available in 2003, was a rewrite of CVC that attempted to make CVC more flexible (hence the “lite”) while extending the feature set: CVC Lite supported quantifiers where its predecessors did not. CVC3 was a major overhaul of portions of CVC Lite: it added better decision procedure implementations, added support for using MiniSat in the core, and had generally better performance.
CVC4 is the new version, the fifth generation of this validity checker line that is now celebrating sixteen years of heritage. It represents a complete re-evaluation of the core architecture to be both performant and to serve as a cutting-edge research vehicle for the next several years. Rather than taking CVC3 and redesigning problem parts, we’ve taken a clean-room approach, starting from scratch. Before using any designs from CVC3, we have thoroughly scrutinized, vetted, and updated them. Many parts of CVC4 bear only a superficial resemblance, if any, to their correspondent in CVC3.
However, CVC4 is fundamentally similar to CVC3 and many other modern SMT solvers: it is a DPLL(T) solver, with a SAT solver at its core and a delegation path to different decision procedure implementations, each in charge of solving formulas in some background theory.
The re-evaluation and ground-up rewrite was necessitated, we felt, by the performance characteristics of CVC3. CVC3 has many useful features, but some core aspects of the design led to high memory use, and the use of heavyweight computation (where more nimble engineering approaches could suffice) makes CVC3 a much slower prover than other tools. As these designs are central to CVC3, a new version was preferable to a selective re-engineering, which would have ballooned in short order.
CVC4 is supported in part by the following organizations:
- The Air Force Office of Scientific Research (award FA9550-09-1-0596)
- The Defense Advanced Research Projects Agency (award FA8750-13-2-0241)
- Intel Corporation
- The National Science Foundation (grants 0644299, 0914956, 1049495, 1228768, 1320583, 1347900)
- The Semiconductor Research Corporation (tasks 1850.001, 1850.002)
Any opinions, findings and conclusions or recommendations expressed in this site are those of the authors and do not necessarily reflect the views of the organizations listed above.