Z3 has been released as open source software under the MIT license! This is great news. Z3 is a good satisifiability modulo theories (SMT) solver / theorem prover from Microsoft Research. An SMT solver accepts a set of constraints (such as “a<5 and a>1”) and tries to produce values that satisfy all the constraints. A satisfiability (SAT) solver does this too, but SAT solvers can only work with boolean variables; SMT solvers can handle other types, such as integers. Here is a Z3 tutorial.
SMT solvers are basically lower-level tools that have many uses for building larger capabilities, because many problems require solving logical formulas to find a solution.
I am particularly interested in the use of SMT solvers to help prove that programs do something or do not do something. Why3 is a platform that lets you write programs and their specifications, and then calls out to various provers to try to determine if the claims are true. By itself Why3 only supports its WhyML language, but Why3 can be combined with other tools to prove statements in other languages. Those include C (using Frama-C and a plug-in), Java, and Ada. People have been able to prove tiny programs for decades, but scaling up to bigger programs in practice requires a lot of automation. I think this approach of combining many different tools, with different strengths, is very promising.
The more tools that are available to Why3, the more likely it will solve problems automatically. That’s because different tools use different heuristics and focus on different issues, resulting in different ones being good at different things. There are already several good SMT solvers available as OSS, including CVC4 and alt-ergo.
Now that Microsoft has released Z3 as OSS, there is yet another strong OSS SMT solver that tools like Why3 can use directly. In short, the collection of OSS SMT solvers has just become even stronger. There’s a standard for SMT solver inputs, the SMT-LIB format, so it’s not hard to take advantage of many SMT solvers. My hope is that this will be another step in making it easier to have strong confidence in software.
path: /oss | Current Weblog | permanent link to this entry