A Survey of Acceleration Techniques for SMT-Based Bounded Model Checking
Authors:
- Leyuan LiuLLLeyuan Liu
- Weiqiang KongWKWeiqiang Kong
- Takahiro AndoTATakahiro Ando
- Hirokazu YatsuHYHirokazu Yatsu
- Akira FukudaAFAkira Fukuda
- 1 December 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 554-559
Abstract
Model checking is wildly acknowledged to be an effective formal technique for verifying that a finite state system satisfies desired properties expressed in temporal logic. There are primarily two types of model checking approaches: explicit model checking and symbolic model checking. To mitigate the notorious state exploration problems suffered by explicit model checking, bounded model checking (BMC) has been proposed as an alternative to other symbolic model checking approaches based on binary decision diagrams. Although originally SAT solvers are used by BMC as the reasoning engine, a recent trend is to switch from SAT to SMT solvers. In this paper, we survey contributions on acceleration of SMT-based BMC. In addition, we discuss some related techniques that could be potentially used as well for the acceleration purpose.Keywords
This publication has 22 references indexed in Scilit:
- Parallelizing the Spin Model CheckerLecture Notes in Computer Science, 2012
- Satisfiability modulo theoriesCommunications of the ACM, 2011
- SMT-Based Bounded Model Checking for Embedded ANSI-C SoftwareIEEE Transactions on Software Engineering, 2011
- d-TSR: Parallelizing SMT-Based BMC Using Tunnels over a Distributed Framework2009
- Tunneling and slicing2008
- The Design of a Multicore Extension of the SPIN Model CheckerIEEE Transactions on Software Engineering, 2007
- Multi-Core Model Checking with SPIN2007
- Efficient distributed SAT and SAT-based distributed Bounded Model CheckingInternational Journal on Software Tools for Technology Transfer, 2006
- Improving Spin’s Partial-Order Reduction for Breadth-First Search2005
- The model checker SPINIEEE Transactions on Software Engineering, 1997