SMT Solvers and Program Verification
Abstract
A SAT solver answers questions about true and false. Programs talk about integers, arrays, pointers, and bit patterns. A satisfiability modulo theories (SMT) solver joins the two: a Boolean search engine in the middle, and around it specialized procedures that know arithmetic or memory. The combination was worked out at Stanford in 1979 for a program verifier, spent twenty years inside research tools at DEC, and became infrastructure after 2007, when Microsoft’s Z3 made it fast enough to run a billion times. The same solver that proves a device driver correct is used to generate the malformed files that crash a parser.
Proof Obligations
The idea of proving programs correct is as old as programming. Robert Floyd in 1967 and Tony Hoare in 1969 showed how to attach logical assertions to a program so that its correctness reduces to a list of formulas, each of which must be valid. A tool can generate that list mechanically. The difficulty moved to the formulas: someone, or something, had to prove them, and there were hundreds per page of code.
The formulas are not hard mathematics. They are long and shallow, and they mix vocabularies. One line may say that an index is less than an array’s length, that two pointers are equal, and that a function applied to equal arguments gives equal results. Decision procedures existed for each fragment alone: linear arithmetic, equality, arrays. None handled the mixture.
Cooperating Procedures
Greg Nelson and Derek Oppen, at Stanford’s Artificial Intelligence Laboratory, were building the prover for a Pascal verifier. In October 1979 they published “Simplification by Cooperating Decision Procedures” in the ACM Transactions on Programming Languages and Systems. Their method lets each specialized procedure keep its own formulas and exchange only equalities between shared variables with the others, until one of them finds a contradiction or none has anything left to say. Robert Shostak at SRI published a different combination scheme in the same period. Nearly every later solver rests on one of the two.
Nelson took the idea to DEC’s Systems Research Center in Palo Alto. There a group built extended static checking: a tool that reads a program with a few annotations and reports likely null dereferences, array-bound errors, and race conditions without running it. The version for Modula-3 was finished in 1996. The version for Java, begun in 1997 and continued under Compaq, was described at the PLDI conference in 2002 by Cormac Flanagan, Rustan Leino, Mark Lillibridge, Nelson, James Saxe, and Raymie Stata. Behind both was a prover called Simplify, by David Detlefs, Nelson, and Saxe. ESC/Java made a deliberate trade: it was allowed to miss some errors and to raise some false alarms, in return for answering in seconds with no human guiding the proof.
DPLL(T)
Simplify did its own case analysis, slowly. Around 2001 SAT solvers became several orders of magnitude faster (see SAT Solvers), and the obvious move was to borrow them. The first attempts were “eager”: translate the whole arithmetic problem into bits and hand it over. The approach that won is “lazy”. The SAT solver treats each arithmetic fact as an opaque Boolean variable and proposes an assignment; a theory solver checks whether the facts chosen are consistent as arithmetic; if not, it returns a short explanation, which the SAT solver learns as a new clause. Robert Nieuwenhuis, Albert Oliveras, and Cesare Tinelli gave the scheme its standard description and its name, DPLL(T), in the Journal of the ACM in 2006.
The field also organized itself. A common input language, SMT-LIB, let the same problem be given to every solver, and an annual competition, SMT-COMP, was first held in 2005 at the Computer Aided Verification conference. The competition did for SMT what the SAT competitions had done before: every year’s winner was the baseline for the next.
Z3
Leonardo de Moura and Nikolaj Bjørner built Z3 in the Research in Software Engineering group at Microsoft Research in Redmond and described it at the TACAS conference in 2008. Other DPLL(T) solvers existed. Z3 was engineered to be called by other programs millions of times, and Microsoft had programs waiting.
One was SAGE, a testing tool by Patrice Godefroid, Michael Levin, and David Molnar. SAGE runs a program on a valid input file, records every branch the program takes as a constraint on the bytes of the file, negates one constraint, and asks Z3 for a file that satisfies the new set. The result is an input that drives the program down a path it has not taken before. In a test on the Windows animated-cursor parser, which had needed an emergency security patch in April 2007, SAGE started from a well-formed file and produced the crashing one in 7 hours 36 minutes with no knowledge of the format. From 2008 it ran day and night on about a hundred machines in Microsoft’s security laboratories. By the authors’ account in 2012 that amounted to more than 300 machine-years and more than a billion constraints, “the largest computational usage ever for any Satisfiability Modulo Theories (SMT) solver”, and SAGE had found about one third of all the bugs discovered by file fuzzing during the development of Windows 7.
The verification tools came to depend on it as well. The Static Driver Verifier, which grew out of Thomas Ball and Sriram Rajamani’s SLAM project of 1999 and ships with Microsoft’s driver development kit, checks that Windows device drivers obey the kernel’s rules. Leino, who had moved from Compaq to Microsoft, designed the intermediate language Boogie and in 2009 the programming language Dafny, in which specifications are part of the source text and the compiler refuses a program whose proof Z3 cannot complete.
Microsoft released Z3 as open source under the MIT license at the beginning of 2015. It received the ACM SIGPLAN Programming Languages Software Award that year and the ETAPS Test of Time Award in 2018, and de Moura and Bjørner received the Herbrand Award in 2019. Its main academic rival descends from the Stanford line: the CVC family, whose current member, cvc5, was presented in 2022.
In 2013 de Moura started a second project at Microsoft Research, a proof assistant called Lean. Its history belongs to Computer-Assisted Proof.
⚠️ Dead End: The Push Button
The promise of SMT-based verification was proof without a prover’s skill: write the specification, press the button. It holds for the fragments that are decidable. As soon as a specification quantifies over all elements of a data structure, the problem is undecidable in general and the solver falls back on heuristics for choosing instances. A proof that goes through in two seconds may then run forever after an unrelated edit to the program, and the engineer is left to guess what the solver wants to be told.
Interactive proof assistants make the opposite trade: the human writes every step, and the machine checks it (see Formal Methods and Model Checking). The large verified systems of the 2000s and 2010s were built that way. In practice the two have merged. Proof assistants call SMT solvers to dispose of routine steps, and SMT-based languages let the user write lemmas by hand where the automation gives up.
📚 Sources
- Nelson, G., and Oppen, D. C.: “Simplification by Cooperating Decision Procedures”, ACM Transactions on Programming Languages and Systems 1(2), October 1979, pp. 245–257 (Stanford AI Laboratory; the simplifier of the Stanford Pascal Verifier)
- Flanagan, C., Leino, K. R. M., Lillibridge, M., Nelson, G., Saxe, J. B., and Stata, R.: “Extended Static Checking for Java”, PLDI 2002
- Detlefs, D., Nelson, G., and Saxe, J. B.: “Simplify: A Theorem Prover for Program Checking”, Journal of the ACM 52(3), 2005
- Wikipedia: ESC/Java (ESC/Modula-3 ending in 1996, the 1997 start at Compaq SRC)
- Nieuwenhuis, R., Oliveras, A., and Tinelli, C.: “Solving SAT and SAT Modulo Theories: From an Abstract Davis–Putnam–Logemann–Loveland Procedure to DPLL(T)”, Journal of the ACM 53(6), 2006
- Wikipedia: Satisfiability modulo theories (eager and lazy approaches, SMT-COMP 2005 at CAV, Boogie and Dafny on Z3)
- de Moura, L., and Bjørner, N.: “Z3: An Efficient SMT Solver”, TACAS 2008
- Wikipedia: Z3 Theorem Prover (the RiSE group, open source in early 2015 under the MIT license, the three awards)
- Godefroid, P., Levin, M. Y., and Molnar, D.: “SAGE: Whitebox Fuzzing for Security Testing”, Communications of the ACM 55(3), March 2012, pp. 40–44 (the animated-cursor test, the machine-years and constraint counts, the Windows 7 figure)
- Wikipedia: SLAM project (Ball and Rajamani, 1999, the Static Driver Verifier) and Wikipedia: Dafny (Leino, 2009)
- Barbosa, H., et al.: “cvc5: A Versatile and Industrial-Strength SMT Solver”, TACAS 2022