Skip to main content
Erschienen in: International Journal on Software Tools for Technology Transfer 5/2017

17.06.2016 | Regular Paper

metaSMT: focus on your application and not on solver integration

verfasst von: Heinz Riener, Finn Haedicke, Stefan Frehse, Mathias Soeken, Daniel Große, Rolf Drechsler, Goerschwin Fey

Erschienen in: International Journal on Software Tools for Technology Transfer | Ausgabe 5/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Many applications from artificial intelligence and formal methods use decision procedures as their core solving engines. In this context, automated reasoning based on Satisfiability (SAT) or Satisfiability Modulo Theories (SMT) is very effective. For a given application, however, selecting the best reasoning engine is a daunting task requiring first-hand experience and insight into engine-specific implementation details. Developers have to decide which concrete engine to use and how to integrate the engine into an application. Although file formats, e.g., DIMACS CNF or SMT-LIB, standardize the input of SAT and SMT solvers, not all engines provide input interfaces compliant with these standards. When following the standard, advanced (and not standardized) features of the solvers remain unused and their integration is left to the users. This work presents metaSMT, a framework that eases the integration of existing reasoning engines into applications. Inspired by SMT-LIB, metaSMT provides a domain-specific language that allows for engine-independent programming and offers a generic interface to advanced features as an extra abstraction layer. State-of-the-art solvers for satisfiability and other theories are available via metaSMT with little programming effort. Language bindings for C++ and Python are provided. We show how metaSMT can be used as a portfolio consistency checker for SMT-LIB2 instances. The benchmark set of the category quantifier-free bit-vector theory from SMT-LIB (1.6 GB) is used for these experiments.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
2.
Zurück zum Zitat Abdessaied, N., Soeken, M., Wille, R., Drechsler, R.: Exact template matching using boolean satisfiability. In: IEEE International Symposium on Multiple-Valued Logic, pp. 328–333 (2013) Abdessaied, N., Soeken, M., Wille, R., Drechsler, R.: Exact template matching using boolean satisfiability. In: IEEE International Symposium on Multiple-Valued Logic, pp. 328–333 (2013)
3.
Zurück zum Zitat Arbel, E., Rokhlenko, O., Yorav, K.: SAT-based synthesis of clock gating functions using 3-valued abstraction. In: Formal Methods in, Computer-Aided Design, pp. 198–204 (2009) Arbel, E., Rokhlenko, O., Yorav, K.: SAT-based synthesis of clock gating functions using 3-valued abstraction. In: Formal Methods in, Computer-Aided Design, pp. 198–204 (2009)
4.
Zurück zum Zitat Armando, A., Mantovani, J., Platania, L.: Bounded model checking of software using SMT solvers instead of SAT solvers. Int. J. Softw. Tools Technol. Transf. 11(1), 69–83 (2009)CrossRefMATH Armando, A., Mantovani, J., Platania, L.: Bounded model checking of software using SMT solvers instead of SAT solvers. Int. J. Softw. Tools Technol. Transf. 11(1), 69–83 (2009)CrossRefMATH
5.
Zurück zum Zitat Barrett, C., Conway, C.L., Deters, M., Hadarean, L., Jovanovic, D., King, T., Reynolds, A., Tinelli, C.: CVC4. In: Computer Aided Verification, pp. 171–177 (2011) Barrett, C., Conway, C.L., Deters, M., Hadarean, L., Jovanovic, D., King, T., Reynolds, A., Tinelli, C.: CVC4. In: Computer Aided Verification, pp. 171–177 (2011)
6.
Zurück zum Zitat Barrett, C., Stump, A., Tinelli, C.: The SMT-LIB standard: Version 2.0 (2012) Barrett, C., Stump, A., Tinelli, C.: The SMT-LIB standard: Version 2.0 (2012)
7.
Zurück zum Zitat Barrett, C.W., Sebastiani, R., Seshia, S.A., Tinelli C.: Handbook of Satisfiability, chapter Satisfiability Modulo Theories, pp. 825–885. IOS Press, Amsterdam (2009) Barrett, C.W., Sebastiani, R., Seshia, S.A., Tinelli C.: Handbook of Satisfiability, chapter Satisfiability Modulo Theories, pp. 825–885. IOS Press, Amsterdam (2009)
8.
Zurück zum Zitat Biere, A.: PicoSAT essentials. J. Satisfiab. Boolean Model Comput. 4(2–4), 75–97 (2008)MATH Biere, A.: PicoSAT essentials. J. Satisfiab. Boolean Model Comput. 4(2–4), 75–97 (2008)MATH
9.
Zurück zum Zitat Biere, A.: Lingeling, plingeling and treengeling entering the sat competition 2013. In: Theory and Applications of Satisfiability Testing, pp. 51–52 (2013) Biere, A.: Lingeling, plingeling and treengeling entering the sat competition 2013. In: Theory and Applications of Satisfiability Testing, pp. 51–52 (2013)
10.
Zurück zum Zitat Biere, A., Cimatti, A., Clarke, E.M., Zhu, Y.: Symbolic model checking without BDDs. In: Tools and Algorithms for the Construction and Analysis of Systems, pp. 193–207 (1999) Biere, A., Cimatti, A., Clarke, E.M., Zhu, Y.: Symbolic model checking without BDDs. In: Tools and Algorithms for the Construction and Analysis of Systems, pp. 193–207 (1999)
11.
Zurück zum Zitat Bjesse, P.: A practical approach to word level model checking of industrial netlists. In: Computer Aided Verification, pp. 446–458 (2008) Bjesse, P.: A practical approach to word level model checking of industrial netlists. In: Computer Aided Verification, pp. 446–458 (2008)
12.
Zurück zum Zitat Brummayer, R., Boolector, A.Biere: An efficient SMT solver for bit-vectors and arrays. In: Tools and Algorithms for the Construction and Analysis of Systems, pp. 174–177 (2009) Brummayer, R., Boolector, A.Biere: An efficient SMT solver for bit-vectors and arrays. In: Tools and Algorithms for the Construction and Analysis of Systems, pp. 174–177 (2009)
13.
Zurück zum Zitat Bruttomesso, R., Cok, D.R., Griggio, A.: Satisfiability modulo theories competition (SMT-LIB) 2013: rules and procedures, 2012. This version revised, pp. 6–2 (2012) Bruttomesso, R., Cok, D.R., Griggio, A.: Satisfiability modulo theories competition (SMT-LIB) 2013: rules and procedures, 2012. This version revised, pp. 6–2 (2012)
14.
Zurück zum Zitat Cok, D.R.: jSMTLIB: tutorial, validation and adapter tools for SMT-LIBv2. In: NASA Formal Methods, pp. 480–486 (2011) Cok, D.R.: jSMTLIB: tutorial, validation and adapter tools for SMT-LIBv2. In: NASA Formal Methods, pp. 480–486 (2011)
15.
Zurück zum Zitat Cook, S.A.: The complexity of theorem-proving procedures. In: Symposium on the Theory of, Computing, pp. 151–158 (1971) Cook, S.A.: The complexity of theorem-proving procedures. In: Symposium on the Theory of, Computing, pp. 151–158 (1971)
16.
Zurück zum Zitat de Moura, L.M., Bjørner, N.: Z3: an efficient SMT solver. In: Tools and Algorithms for the Construction and Analysis of Systems, pp. 337–340 (2008) de Moura, L.M., Bjørner, N.: Z3: an efficient SMT solver. In: Tools and Algorithms for the Construction and Analysis of Systems, pp. 337–340 (2008)
17.
Zurück zum Zitat Drechsler, R., Eggersglüß, S., Fey, G., Glowatz, A., Hapke, F., Schlöffel, J., Tille, D.: On acceleration of SAT-based ATPG for industrial designs. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 27(7), 1329–1333 (2008)CrossRef Drechsler, R., Eggersglüß, S., Fey, G., Glowatz, A., Hapke, F., Schlöffel, J., Tille, D.: On acceleration of SAT-based ATPG for industrial designs. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 27(7), 1329–1333 (2008)CrossRef
18.
Zurück zum Zitat Eén, N., Sörensson, N.: An extensible SAT-solver. In: Theory and Applications of Satisfiability Testing, pp. 502–518 (2003) Eén, N., Sörensson, N.: An extensible SAT-solver. In: Theory and Applications of Satisfiability Testing, pp. 502–518 (2003)
19.
Zurück zum Zitat Ganai, M.K., Gupta, A.: Accelerating high-level bounded model checking. In: International Conference on Computer Aided Design, pp. 794–801 (2006) Ganai, M.K., Gupta, A.: Accelerating high-level bounded model checking. In: International Conference on Computer Aided Design, pp. 794–801 (2006)
20.
Zurück zum Zitat Ganesh, V., Dill, D.L.: A decision procedure for bit-vectors and arrays. In: Computer Aided Verification, pp. 519–531 (2007) Ganesh, V., Dill, D.L.: A decision procedure for bit-vectors and arrays. In: Computer Aided Verification, pp. 519–531 (2007)
21.
Zurück zum Zitat Haedicke, F., Alizadeh, B., Fey, G., Fujita, M., Drechsler, R.: Polynomial datapath optimization using constraint solving and formal modelling. In: International Conference on Computer Aided Design, pp. 756–761 (2010) Haedicke, F., Alizadeh, B., Fey, G., Fujita, M., Drechsler, R.: Polynomial datapath optimization using constraint solving and formal modelling. In: International Conference on Computer Aided Design, pp. 756–761 (2010)
22.
Zurück zum Zitat Haedicke, F., Le, H.M., Groe, D., Drechsler, R.: CRAVE: an advanced constrained random verification environment for SystemC. In: International Symposium on System-on-Chip, pp. 1–7 (2012) Haedicke, F., Le, H.M., Groe, D., Drechsler, R.: CRAVE: an advanced constrained random verification environment for SystemC. In: International Symposium on System-on-Chip, pp. 1–7 (2012)
23.
Zurück zum Zitat Hudak, P.R.: Modular domain specific languages and tools. In: International Conference on Software Reuse, pp. 134 (1998) Hudak, P.R.: Modular domain specific languages and tools. In: International Conference on Software Reuse, pp. 134 (1998)
24.
Zurück zum Zitat Levin, L.A.: Universal search problems. Problems of Information Transmission. Translation from Russian to English, 9(3), 115–116 (1973) Levin, L.A.: Universal search problems. Problems of Information Transmission. Translation from Russian to English, 9(3), 115–116 (1973)
25.
Zurück zum Zitat McMillan, K.L.: Interpolation and SAT-based model checking. In: Computer Aided Verification, pp. 1–13 (2003) McMillan, K.L.: Interpolation and SAT-based model checking. In: Computer Aided Verification, pp. 1–13 (2003)
26.
Zurück zum Zitat Niklas Eén, N.S.: Translating pseudo-boolean constraints into SAT. J. Satisfiab. Boolean Model. Comput. 2(1–4), 1–26 (2006)MATH Niklas Eén, N.S.: Translating pseudo-boolean constraints into SAT. J. Satisfiab. Boolean Model. Comput. 2(1–4), 1–26 (2006)MATH
27.
Zurück zum Zitat Palikareva, H., Cadar, C.: Multi-solver support in symbolic execution. In: Computer Aided Verification, pp. 53–68 (2013) Palikareva, H., Cadar, C.: Multi-solver support in symbolic execution. In: Computer Aided Verification, pp. 53–68 (2013)
29.
Zurück zum Zitat Riener, H., Bloem, R., Fey, G.: Test case generation from mutants using model checking techniques. In: International Conference on Software Testing, Verification, and Validation Workshops, pp. 388–397 (2011) Riener, H., Bloem, R., Fey, G.: Test case generation from mutants using model checking techniques. In: International Conference on Software Testing, Verification, and Validation Workshops, pp. 388–397 (2011)
30.
Zurück zum Zitat Riener, H., Fey, G.: Model-based diagnosis versus error explanation. In: International Conference on Formal Methods and Models for Co-Design, pp. 43–52 (2012) Riener, H., Fey, G.: Model-based diagnosis versus error explanation. In: International Conference on Formal Methods and Models for Co-Design, pp. 43–52 (2012)
31.
Zurück zum Zitat Riener, H., Frehse, S., Fey, G.: Improving fault tolerance utilizing hardware-software-co-synthesis. In: Design, Automation, and Test in Europe, pp. 939–942 (2013) Riener, H., Frehse, S., Fey, G.: Improving fault tolerance utilizing hardware-software-co-synthesis. In: Design, Automation, and Test in Europe, pp. 939–942 (2013)
32.
Zurück zum Zitat Somenzi, F.: CUDD: CU Decision Diagram Package Release 2.4.1. University of Colorado at Boulder, Boulder (2009) Somenzi, F.: CUDD: CU Decision Diagram Package Release 2.4.1. University of Colorado at Boulder, Boulder (2009)
33.
Zurück zum Zitat Strichman, O.: Pruning techniques for the SAT-based bounded model checking problem. In: Correct Hardware Design and Verification Methods, pp. 58–70 (2001) Strichman, O.: Pruning techniques for the SAT-based bounded model checking problem. In: Correct Hardware Design and Verification Methods, pp. 58–70 (2001)
34.
Zurück zum Zitat Wille, R., Fey, G., Große, D., Eggersglüß S., Drechsler, R.: Sword: A SAT like prover using word level information. In: IFIP/IEEE International Conference on Very Large Scale Integration, pp. 88–93 (2007) Wille, R., Fey, G., Große, D., Eggersglüß S., Drechsler, R.: Sword: A SAT like prover using word level information. In: IFIP/IEEE International Conference on Very Large Scale Integration, pp. 88–93 (2007)
Metadaten
Titel
metaSMT: focus on your application and not on solver integration
verfasst von
Heinz Riener
Finn Haedicke
Stefan Frehse
Mathias Soeken
Daniel Große
Rolf Drechsler
Goerschwin Fey
Publikationsdatum
17.06.2016
Verlag
Springer Berlin Heidelberg
Erschienen in
International Journal on Software Tools for Technology Transfer / Ausgabe 5/2017
Print ISSN: 1433-2779
Elektronische ISSN: 1433-2787
DOI
https://doi.org/10.1007/s10009-016-0426-1

Weitere Artikel der Ausgabe 5/2017

International Journal on Software Tools for Technology Transfer 5/2017 Zur Ausgabe