Document Type


Date of Degree

Summer 2012

Degree Name

PhD (Doctor of Philosophy)

Degree In

Computer Science

First Advisor

Stump, Aaron D

First Committee Member

Stump, Aaron

Second Committee Member

Tinelli, Cesare

Third Committee Member

Zhang, Hantao

Fourth Committee Member

Segre, Alberto

Fifth Committee Member

Landini, Gregory

Sixth Committee Member

Shankar, Natarajan


Satisfiability (SAT) and satisfiability modulo theories (SMT) solvers are high-performance automated propositional and first-order theorem provers, used as underlying tools in many formal verification and artificial intelligence systems. Theoretic and engineering advancement of solver technologies improved the performance of modern solvers; however, the increased complexity of those solvers calls for formal verification of those tools themselves. This thesis discusses two methods to formally certify SAT/SMT solvers. The first method is generating proofs from solvers and certifying those proofs. Because new theories are constantly added to SMT solvers, a flexible framework to safely add new inference rules is necessary. The proposal is to use a meta-language called LFSC, which is based on Edinburgh Logical Framework. SAT/SMT logics have been encoded in LFSC, and the encoding can be easily and modularly extended for new logics. It is shown that an optimized LFSC checker can certify SMT proofs efficiently. The second method is using a verified programming language to implement a SAT solver and verify the code statically. Guru is a pure functional programming language with support for dependent types and theorem proving; Guru also allows for efficient code generation by means of resource typing. A modern SAT solver, called versat, has been implemented and verified to be correct in Guru. The performance of versat is shown to be comparable with that of the current proof checking technology.


dependent types, formal methods, logical framework, satisfiability, satisfiability modulo theories, software verification


viii, 112 pages


Includes bibliographical references (pages 105-112).


Copyright 2012 Duckki Oe