Abstract
Bounded model checking (BMC) is a procedure that searches for counterexamples to a given property through bounded executions of a non-terminating system. This paper compares the performance of SAT-based, BDD-based, and explicit state-based BMC on benchmarks drawn from commercial designs. Our experimental framework provides a uniform and comprehensive basis to evaluate each of these approaches. The experimental results suggest that for designs with deep counterexamples, BDD-based BMC is much faster. For designs with shallow counterexamples, SAT-based BMC is more effective than BDD-based BMC, but explicit state-based BMC is also comparably effective.
Introduction
Model checking is essential for verifying that complex systems satisfy specific safety and liveness properties. Bounded Model Checking (BMC) focuses this search within a specific execution depth ($k$). While SAT-based solvers have recently been hailed as the superior engine for BMC, this study provides a rigorous "head-to-head" comparison against Binary Decision Diagrams (BDDs) and explicit state-based engines using a unified industrial framework. By using the commercial tool FormalCheck as a common platform, the researchers eliminated the "apples-to-oranges" discrepancies common in previous tool comparisons.
Experimental Methodology
To ensure a fair comparison, all engines were integrated into the COSPAN engine within FormalCheck. This setup allowed all three engines to operate on identical, statically reduced models, ensuring that differences in performance were due to the engines themselves rather than front-end optimizations.
- BDD-based BMC: Utilized standard reachability analysis. A key advantage is its ability to reach a "fix-point," allowing it to prove a property holds if all reachable states are explored.
- Explicit State BMC: Implemented as a random search. While it provides no coverage guarantees, it is computationally "cheap" and easy to bound.
- SAT-based BMC: Tested using two state-of-the-art solvers of the era, BerkMin and zChaff.
The study evaluated 62 industrial benchmarks from Cadence customer designs, categorized by the known depth of their counterexamples.
Performance on Shallow Counterexamples
For benchmarks with shallow counterexamples (depth $\le 30$), the results challenged the assumption of SAT's absolute dominance. While SAT solvers were highly consistent, the random explicit state search proved remarkably effective for safety properties.
As shown in Table 1, explicit state search often outperformed both BDD and SAT engines on shallow safety benchmarks (e.g., A1, A7, A14). However, SAT remained the most reliable for liveness properties (marked 'L' in the type column), which require finding cycles that random searches often miss.
Performance on Deep Counterexamples
As the search depth increases beyond 60 steps, the performance landscape shifts significantly. Contrary to the trend of favoring SAT for BMC, BDDs emerged as the superior engine for deep counterexamples.
As seen in Table 2, BDDs scale more effectively with depth in many cases (e.g., B9 through B17), provided the state space remains manageable. Furthermore, BDDs are the only engine capable of providing a definitive proof of correctness by reaching a fix-point, a feat neither SAT nor explicit state search can reliably achieve for industrial-scale designs due to the size of completeness thresholds.
Conclusion
The experimental evidence suggests that no single engine is universally superior. SAT-based BMC offers the most consistent performance across various designs, but BDDs are significantly faster for deep bugs, and explicit state search is a powerful tool for catching shallow safety errors quickly. These findings advocate for a "portfolio" approach in industrial verification, where multiple engines are deployed in parallel to leverage their respective strengths.
Summary updated