Bounded Model Checking Sample Clauses
Bounded Model Checking. The key idea of BMC is to exercise the behavior of a system only up to a certain depth of computations [BCCZ99, CBRZ01, CKOS05]. BMC has been established as a valuable bug-hunting framework for hardware and soft- ware [CKL04], which is motivated by the observation that bugs can often be found after few computation steps if only the right inputs are chosen. How- ever, it has been observed that bounded model checking can also be applied for formal verification if the unrolling depth k of the transition relation is large enough. Precisely, the unrolling depth k has to match the complete- ness threshold c of the system, which can intuitively be described as: If no counterexample of length c or less is found, the specification holds for all (in- finite) executions of the model. Hence, BMC with k c suffices for proving correctness of a system [BCCZ99, Thm. 27]. However, computing the com- pleteness threshold is as least as hard as solving the model checking problem itself [CKOS04, KOS+11]. Consequently, BMC is often used for verification up to a certain bound, without giving an actual correctness guarantee for nonterminating executions of the system.
Bounded Model Checking. In bounded model checking, the loops in a program are unrolled to a certain bound. Next, a logical formula is constructed for the program and a property the program needs to satisfy, where the formula only considers the unrolled part of the loop. Finally, automated theorem proving is applied, as in the case of contract-based verification. Remark that this method is necessarily incomplete, as a counterexample to a property may only be found by unrolling the loop further than the chosen bound. Dynamic Verification. In dynamic verification, instrumentation code is added to programs to be able to observe certain unwanted program behavior, e.g., data races can be detected by adding code that records the memory locations accessed by different threads. The instrumented programs are run on concrete inputs to see if the unwanted program behavior occurs in practice. Note that adding instrumentation code is likely to reduce the performance of a programs and, hence, should be kept to a minimum to ensure reasonable execution times.