Abstract
As hardware designs increase in complexity, traditional formal verification methods like Binary Decision Diagrams (BDDs) face significant scalability challenges. This paper presents a comprehensive industrial evaluation of eight Boolean Satisfiability (SAT)-based model checking techniques. Using a benchmark suite of over 1,000 real-world designs from Cadence Design Systems, we analyze the performance of Bounded Model Checking (BMC), Abstraction Refinement, and Unbounded methods. Our results demonstrate that while interpolation-based model checking serves as the most robust general-purpose tool, the optimal choice of algorithm is highly dependent on whether the verification goal is to identify bugs or prove property correctness.
Introduction
Model checking is a critical automated process for verifying that hardware designs—such as processors and memory controllers—adhere to specific safety and liveness properties. For decades, this field was dominated by Binary Decision Diagrams (BDDs). However, BDDs are prone to "memory explosion," particularly when dealing with data-path intensive designs like multipliers.
The emergence of SAT solvers offered a potential solution to these limitations. While academic research has proposed numerous SAT-based algorithms, there has been a lack of large-scale, uniform data regarding their performance in high-stakes industrial environments. This study addresses this gap by benchmarking eight distinct SAT-based techniques against a massive suite of industrial hardware designs, providing a "reality check" on the state of formal verification.
Experimental Framework
The Benchmark Suite
The study utilizes a diverse dataset from Cadence Design Systems, consisting of 85 hardware designs ranging from a few hundred to over 100,000 lines of HDL code. Within these designs, 1,182 individual properties were identified for verification. The properties were categorized as follows:
- 803 Passes: Properties proven true for all time.
- 364 Failures: Properties where a counterexample (bug) was found.
- 15 Unknowns: Properties that could not be resolved within the 3,600-second time limit.
Evaluated Algorithms
The eight algorithms were categorized into three primary methodologies:
- Bounded Model Checking (BMC): Searches for bugs up to a fixed step k. This included standard BMC and Circuit-Based BMC (which utilizes SAT-sweeping for logic simplification).
- Abstraction Refinement: Simplifies models by removing variables. We compared Counterexample-Based (CEX) refinement against Proof-Based refinement, which uses the SAT solver’s mathematical proof of unsatisfiability to guide abstraction.
- Unbounded (Complete) Methods: Capable of proving properties true for all time. This included k-Induction, Interpolation (using Craig Interpolants), and Quantification/ATPG-based methods.
Comparative Analysis of Algorithms
The Dominance of Interpolation
Interpolation emerged as the "Swiss Army Knife" of the study. It was the most robust method, solving 1,157 out of 1,182 properties. By creating over-approximations of reachable states, interpolation proved significantly more effective at proving properties true than traditional BDD-based methods, solving nearly 32% more properties (1,157 vs. 876).
Bounded Model Checking and Logic Simplification
In the realm of BMC, the study revealed an interesting trade-off regarding logic simplification. While "Circuit-Based" BMC simplifies the problem before solving, the overhead of this simplification makes it slower than standard BMC at shallow search depths. However, as the search depth increases (e.g., beyond 100 steps), the initial investment in simplification pays off, leading to significantly faster solving times.
Abstraction Refinement: Proof vs. Counterexample
When refining abstractions, the Proof-Based method generally outperformed the CEX-based approach. Utilizing the SAT solver's internal logic to identify critical variables proved more efficient than analyzing individual failed paths. This suggests that the internal state of the SAT solver provides a more holistic view of the design's constraints.
Industrial Performance Results
The performance metrics highlight a clear divergence in algorithm efficiency based on the verification outcome:
- Finding Bugs (Failing Properties): Standard BMC remains the fastest method for bug hunting, with an average runtime of 9.6 seconds. Proof-Based abstraction followed as a strong complete-method contender at 22.1 seconds.
- Proving Truth (Passing Properties): Interpolation was the clear leader, averaging 21.9 seconds per property—nearly 2.5 times faster than the next best method, Proof-Based abstraction (54.9 seconds).
- Overall Efficiency: The average time per property for Interpolation was 100.5 seconds, a massive improvement over the 991.3 seconds required for BDDs and the 2,045.4 seconds for k-induction.
Discussion and Limitations
Despite the success of interpolation, the study noted that k-induction struggled significantly with this benchmark suite, often failing due to memory exhaustion. Furthermore, methods relying on backward reachability (such as ATPG-based methods) were less scalable than forward-moving approximations like interpolation when faced with large state spaces.
A key takeaway for industrial application is that no single algorithm is optimal for every scenario. While interpolation is the best general-purpose choice, specific cases still favor k-induction or ATPG methods. This supports the adoption of a "portfolio" approach, where multiple solvers are run in parallel to maximize verification coverage.
Conclusion
SAT-based model checking has revolutionized hardware verification, offering scalability that BDDs cannot match. Interpolation-based techniques represent the current state-of-the-art for industrial applications, particularly for proving property correctness. Future work should focus on the hybridization of these techniques—specifically combining the strengths of proof-based and counterexample-based refinement—to create even more resilient verification engines.
Summary updated