Journal of Applied Mathematics
Volume 2013 (2013), Article ID 964682, 13 pages
http://dx.doi.org/10.1155/2013/964682
Research Article

A Unified Framework for DPLL(T) + Certificates

Min Zhou,1,2,3,4 Fei He,1,2,3 Bow-Yaw Wang,5 Ming Gu,1,2,3 and Jiaguang Sun1,2,3

1Tsinghua National Laboratory for Information Science and Technology (TNList), Beijing 100084, China
2School of Software, Tsinghua University, Beijing 100084, China
3Key Laboratory for Information System Security, MOE, Beijing 100084, China
4Department of Computer Science and Technologies, Tsinghua University, Beijing 100084, China
5Institute of Information Science, Academia Sinica, Taipei 115, Taiwan

Received 6 February 2013; Accepted 8 April 2013

Academic Editor: Xiaoyu Song

Copyright © 2013 Min Zhou et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Satisfiability Modulo Theories (SMT) techniques are widely used nowadays. SMT solvers are typically used as verification backends. When an SMT solver is invoked, it is quite important to ensure the correctness of its results. To address this problem, we propose a unified certificate framework based on DPLL(T), including a uniform certificate format, a unified certificate generation procedure, and a unified certificate checking procedure. The certificate format is shown to be simple, clean, and extensible to different background theories. The certificate generation procedure is well adapted to most DPLL(T)-based SMT solvers. The soundness and completeness for DPLL(T) + certificates were established. The certificate checking procedure is straightforward and efficient. Experimental results show that the overhead for certificates generation is only 10%, which outperforms other methods, and the certificate checking procedure is quite time saving.