Abstract
Bounded model checking (BMC) has proven to be an efficient method for finding bugs in system designs. In this paper, we present an incremental semantic translation for Bounded model checking and give an incremental algorithm. We implement this method in the NuSMV model checker and report encouraging results.
Introduction
Bounded Model Checking (BMC) is a widely adopted technique for identifying design flaws in hardware and software. By unrolling a system model to a finite bound $k$ and translating the verification task into a Boolean Satisfiability (SAT) problem, BMC can efficiently find counterexamples. However, as the bound $k$ increases, traditional BMC methods suffer from two primary bottlenecks: formula explosion and redundant computation. Standard methods often restart the SAT solver for each increment of $k$, discarding valuable "learned clauses" that could accelerate subsequent steps.
Methodology
To address these limitations, this research proposes an incremental semantic encoding approach. This method leverages two primary optimizations to improve solver performance and formula compactness.
1. Semantic Encoding
Unlike standard "syntactic" unrolling, which follows the literal structure of a Linear Temporal Logic (LTL) formula, this approach utilizes a "semantic" translation based on tableau construction. This generally results in significantly smaller and more compact Boolean formulas, especially for complex LTL properties, by focusing on the state space of the property's requirements.
2. Incremental Optimization
The semantic encoding is refactored to be compatible with incremental SAT solvers (such as zChaff). The encoding is partitioned into three distinct components:
- Model Unrolling (Permanent): The basic transition steps of the system.
- $k$-Invariant Constraints (Permanent): Logic regarding loops that remains constant regardless of the bound.
- $k$-Dependent Constraints (Temporary): Logic that changes specifically because the path has been extended.
By introducing a proxy state ($s_p$) to represent the endpoint of a path, the researchers successfully decoupled the path unrolling from the loop constraints. This allows the SAT solver to maintain the permanent constraints in memory while only swapping out the temporary group at each step, preserving learned knowledge across iterations.
Experimental Evaluation
The proposed method, BMC_INC, was implemented within the NuSMV framework and evaluated against several state-of-the-art encodings: the standard NuSMV encoding, VMCAI2005, CAV2005, and a non-incremental semantic version (BMC_TAB). The benchmarks used include well-known nontrivial protocols such as the Alternating Bit Protocol (abp4), Bounded Retransmission Protocol (brp), and the PCI bus protocol.
As shown in the experimental results, BMC_INC consistently outperforms existing methods in both speed and scalability. For instance, in the abp4 model, BMC_INC identifies a bug in just 2 seconds, compared to 62 seconds for the standard NuSMV encoding. In more complex models like dme3, BMC_INC successfully solves properties in 170–307 seconds that cause other methods to either time out (TO) or run out of memory (MO). The data confirms that the incremental semantic approach reaches the required bound $k$ faster than non-incremental versions, proving that the incremental overhead is well worth the performance gain.
Conclusion
The incremental semantic approach significantly enhances the efficiency of BMC for LTL. By isolating $k$-dependent constraints and utilizing tableau-based encodings, the method enables SAT solvers to reuse learned knowledge, leading to substantial speedups. While currently focused on LTL, future work could involve extending this methodology to other temporal logics and integrating completeness thresholds to prove the absence of bugs.
Summary updated