×

Adding decision procedures to SMT solvers using axioms with triggers. (English) Zbl 1356.68187

Summary: Satisfiability modulo theories (SMT) solvers are efficient tools to decide the satisfiability of ground formulas, including a number of built-in theories such as congruence, linear arithmetic, arrays, and bit-vectors. Adding a theory to that list requires delving into the implementation details of a given SMT solver, and is done mainly by the developers of the solver itself. For many useful theories, one can alternatively provide a first-order axiomatization. However, in the presence of quantifiers, SMT solvers are incomplete and exhibit unpredictable behavior. Consequently, this approach can not provide us with a complete and terminating treatment of the theory of interest. In this paper, we propose a framework to solve this problem, based on the notion of instantiation patterns, also known as triggers. Triggers are annotations that suggest instances which are more likely to be useful in proof search. They are implemented in all SMT solvers that handle first-order logic and are included in the SMT-LIB format. In our framework, the user provides a theory axiomatization with triggers, along with a proof of completeness and termination properties of this axiomatization, and obtains a sound, complete, and terminating solver for her theory in return. We describe and prove a corresponding extension of the traditional Abstract DPLL Modulo Theory framework. Implementing this mechanism in a given SMT solver requires a one-time development effort. We have implemented the proposed extension in the Alt-Ergo prover and we discuss some implementation details in the paper. To show that our framework can handle complex theories, we prove completeness and termination of a feature-rich axiomatization of doubly-linked lists. Our tests show that our approach results in a better performance of the solver on goals that stem from the verification of programs manipulating doubly-linked lists and sets.

MSC:

68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
03B35 Mechanization of proofs and logical operations

References:

[1] Alberti, F., Ghilardi, S., Sharygina, N.: Decision procedures for flat array properties. In: Ábrahám, E., Havelund, K. (eds.) and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science, vol. 8413, pp. 15-30. Springer, Berlin (2014) · Zbl 1448.68284
[2] Armando, A., Ranise, S., Rusinowitch, M.: A rewriting approach to satisfiability procedures. Inf. Comput. 183(2), 140-164 (2003). In: 12th International Conference on Rewriting Techniques and Applications (RTA 2001) · Zbl 1054.68077
[3] Bansal, K., Reynolds, A., King, T., Barrett, C., Wies, T.: Deciding local theory extensions via E-matching. In: Kroening, D., Păsăreanu, C.S. (eds.) Computer Aided Verification, CAV 2015, Lecture Notes in Computer Science. Vol. 9207, pp.87-105 Springer (2015) · Zbl 1381.68280
[4] Barrett, C.; Conway, CL; Deters, M.; Hadarean, L.; Jovanović, D.; King, T.; Reynolds, A.; Tinelli, C.; Gopalakrishnan, G. (ed.); Qadeer, S. (ed.), CVC4, No. 6806, 171-177 (2011), Berlin · doi:10.1007/978-3-642-22110-1_14
[5] Barrett, C., Stump, A., Tinelli, C.: The SMT-LIB standard version 2.0. Technical report, University of Iowa (2010) · Zbl 1216.68163
[6] Biere, A., Heule, M., van Maaren, H.: Handbook of Satisfiability, vol. 185. IOS Press, Amsterdam (2009) · Zbl 1183.68568
[7] Bjørner, N.: Engineering theories with Z3. In: Yang, H. (ed.) Proceedings of the 9th Asian Symposium on Programming Languages and Systems, APLAS 2011, Lecture Notes in Computer Science, vol. 7078, pp. 4-16. Springer, Berlin (2011) · Zbl 1232.68012
[8] Bobot, F., Conchon, S., Contejean, E., Lescuyer, S.: Implementing polymorphism in SMT solvers. In: SMT’08, ACM ICPS, vol. 367, pp. 1-5. ACM, New York (2008)
[9] Bradley, A.R., Manna, Z., Sipma, H.B.: What’s decidable about arrays? In: Emerson, E.A., Namjoshi, K.S. (eds.) Proceedings of the 7th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI 2006). Lecture Notes in Computer Science, vol. 3855, pp. 427-442. Springer, Berlin (2006) · Zbl 1176.68116
[10] Chatterjee, S., Lahiri, S.K., Qadeer, S., Rakamarić, Z.: A low-level memory model and an accompanying reachability predicate. Int. J. Softw. Tools Technol. Transf. 11(2), 105-116 (2009) · doi:10.1007/s10009-009-0098-1
[11] de Moura, L., Bjørner, N.: Efficient E-matching for SMT solvers. In: Pfenning, F. (ed.) CADE-21, LNCS, vol. 4603, pp. 183-198. Springer, Berlin (2007) · Zbl 1213.68578
[12] de Moura, L., Bjørner, N.: Engineering DPLL(T) \[+\]+ saturation. In: Armando, A., Baumgartner, P., Dowek, G. (eds.) IJCAR 2008, LNCS, vol. 5195, pp. 475-490. Springer, Berlin (2008) · Zbl 1165.68479
[13] de Moura, L., Bjørner, N.: Z3: An efficient SMT solver. In: Ramakrishnan, C. R., Rehof, J. (eds.) TACAS 2008, LNCS, vol. 4963, pp. 337-340. Springer (2008)
[14] de Moura, L., Bjørner, N.: Generalized, efficient array decision procedures. In: Biere, A., Pixley, C. (eds.) Formal Methods in Computer-Aided Design, 2009. FMCAD 2009, pp. 45-52. IEEE (2009)
[15] Detlefs, D., Nelson, G., Saxe, J.B.: Simplify: a theorem prover for program checking. J. ACM 52(3), 365-473 (2005) · Zbl 1323.68462 · doi:10.1145/1066100.1066102
[16] Dross, C., Conchon, S., Kanig, J., Paskevich, A.: Reasoning with triggers. In: 10th International Workshop on Satisfiability Modulo Theories, SMT 2012, pp. 22-31 (2012) · Zbl 1356.68187
[17] Dross, C., Filliâtre, J.C., Moy, Y.: Correct code containing containers. In: Gogolla, M., Wolff, B. (eds.) Proceedings of the 5th International Conference on Tests and Proofs, TAP’11, Lecture Notes in Computer Science, vol. 6706, pp. 102-118. Springer, Berlin (2011) · Zbl 1335.68052
[18] Ganzinger, H., Korovin, K.: Theory instantiation. In: Hermann, M., Voronkov, A. (eds.) Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2006, Lecture Notes in Computer Science, vol. 4246, pp. 497-511. Springer, Berlin (2006) · Zbl 1165.03315
[19] Ge, Y., Barrett, C., Tinelli, C.: Solving quantified verification conditions using satisfiability modulo theories. In: Pfenning, F. (ed.) CADE-21, LNCS, vol. 4603, pp. 167-182. Springer, Berlin (2007) · Zbl 1213.68376
[20] Ge, Y., de Moura, L.: Complete instantiation for quantified formulas in satisfiability modulo theories. In: Bouajjani, A., Maler, O. (eds.) Computer Aided Verification, LNCS, vol. 5643, pp. 306-320. Springer (2009) · Zbl 1242.68280
[21] Goel, A., Krstić, S., Fuchs, A.: Deciding array formulas with frugal axiom instantiation. In: Proceedings of the Joint Workshops of the 6th International Workshop on Satisfiability Modulo Theories and 1st International Workshop on Bit-Precise Reasoning, ACM ICPS, pp. 12-17. ACM, New York (2008)
[22] Jacobs, S., Kuncak, V.: Towards complete reasoning about axiomatic specifications. In: Jhala, R., Schmidt, D. (eds.) Proceedings of VMCAI-12, LNCS, vol. 6538, pp. 278-293. Springer, Berlin (2012) · Zbl 1317.68117
[23] Knuth, D.E., Bendix, P.B.: Simple word problems in universal algebras. In: Automation of Reasoning, Symbolic Computation, pp. 342-376. Springer, Berlin (1983) · Zbl 0188.04902
[24] Korovin, K.: iProver—an instantiation-based theorem prover for first-order logic (system description). In: Armando, A., Baumgartner, P., Dowek, G. (eds.) Proceedings of the 4th International Joint Conference on Automated Reasoning, (IJCAR 2008), Lecture Notes in Computer Science, vol. 5195, pp. 292-298. Springer, Berlin (2008) · Zbl 1165.68462
[25] Korovin, K.: Instantiation-based reasoning: from theory to practice. In: Schmidt, R.A. (ed.) 22nd International Conference on Automated Deduction, CADE’22, Lecture Notes in Computer Science, vol. 5663, pp. 163-166. Springer, Berlin (2009)
[26] Lynch, C., Morawska, B.: Automatic decidability. In: Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, pp. 7-16. IEEE (2002)
[27] Lynch, C., Ranise, S., Ringeissen, C., Tran, D.K.: Automatic decidability and combinability. Inf. Comput. 209(7), 1026-1047 (2011) · Zbl 1216.68163 · doi:10.1016/j.ic.2011.03.005
[28] McPeak, S., Necula, G.C.: Data structure specifications via local equality axioms. In: Etessami, K., Rajamani,S.K. (eds.) Computer Aided Verification, CAV 2005, Lecture Notes in Computer Science, vol. 3576, pp. 476-490. Springer, Berlin (2005) · Zbl 1081.68584
[29] Moskal, M.: Programming with triggers. In: Proceedings of the 7th International Workshop on Satisfiability Modulo Theories, ACM ICPS, pp. 20-29. ACM, New York (2009)
[30] Nelson, G.: Techniques for program verification. Technical Report CSL81-10, Xerox Palo Alto Research Center (1981)
[31] Nieuwenhuis, R., Oliveras, A., Tinelli, C.: Solving SAT and SAT modulo theories: from an abstract Davis-Putnam-Logemann-Loveland procedure to DPLL(T). J. ACM 53(6), 937-977 (2006) · Zbl 1326.68164 · doi:10.1145/1217856.1217859
[32] Piskac, R., Wies, T., Zufferey, D.: Automating separation logic using SMT. In: Sharygina, N., Veith, H. (eds.) Computer Aided Verification, CAV 2013, Lecture Notes in Computer Science, Vol. 8044, pp. 773-789. Springer, Berlin (2013)
[33] Rümmer, P.: E-matching with free variables. In: Voronkov, A., Bjørner, N. (eds.) Logic for Programming, Artificial Intelligence, and Reasoning: 18th International Conference, LPAR-18, LNCS, vol. 7180, pp. 359-374. Springer, Berlin (2012) · Zbl 1352.68214
[34] Suter, P.; Steiger, R.; Kuncak, V.; Jhala, R. (ed.); Schmidt, D. (ed.), Sets with cardinality constraints in satisfiability modulo theories, No. 6538, 403-418 (2011), Berlin · Zbl 1317.68124 · doi:10.1007/978-3-642-18275-4_28
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.