Abstract
Modern formal verification relies heavily on Boolean Satisfiability (SAT) solvers to prove the correctness of hardware designs. However, SAT-based methods like interpolation often struggle with deep state spaces and massive industrial designs that exceed memory limits. This paper presents two novel techniques to address these bottlenecks: InterpHybrid, a heuristic that switches between interpolation and Binary Decision Diagrams (BDDs), and InterpInc, an incremental interpolation method that leverages circuit-testing logic to handle large-scale designs. Experimental results on over 1,200 industrial benchmarks demonstrate that these methods significantly improve robustness and solve problems that were previously intractable due to memory exhaustion.
Introduction
Model checking is a critical process in hardware design, providing mathematical proof that a system satisfies specific safety and liveness properties. While modern verification has shifted from Binary Decision Diagrams (BDDs) to SAT-based methods—specifically Bounded Model Checking (BMC) and Interpolation—two primary challenges remain: depth and scale.
Interpolation can become computationally expensive when a proof requires exploring deep execution paths. Furthermore, on massive industrial designs (exceeding 100,000 lines of code), the memory required to "unfold" the system for a SAT solver often leads to crashes. This paper explores how to integrate Abstraction Refinement—the process of simplifying a model and incrementally adding detail—with SAT-based unbounded model checking to overcome these hurdles.
Methodology
The authors propose two distinct algorithms designed to optimize different aspects of the verification pipeline:
1. InterpHybrid: A Multi-Engine Heuristic
InterpHybrid is designed to balance the strengths of interpolation and BDDs. While SAT solvers are generally superior for large designs, BDDs remain highly efficient at solving the simplified, "abstracted" versions of problems. InterpHybrid monitors the progress of the interpolation engine; if the algorithm struggles at high depths, the system heuristically switches to a BDD-based Proof-Based Abstraction (PBA). By using a progress-based switching measure, the tool avoids the overhead of BDDs unless they are likely to provide a performance benefit.
2. InterpInc: Incremental Interpolation
Standard abstraction refinement requires a "concretization" step, where a potential error found in a simplified model is checked against the full, complex design. On massive designs, this step often hits a "memory wall."
InterpInc addresses this by borrowing "justification" techniques from Automatic Test Pattern Generation (ATPG). Instead of unfolding the entire concrete model, InterpInc identifies a "frontier" of variables likely relevant to the property. These variables are added to the abstraction incrementally, allowing the solver to find a proof without ever loading the entire design into memory.
Experimental Setup
The proposed methods were evaluated using a comprehensive industrial benchmark suite consisting of:
- 1,205 problems derived from 85 hardware designs.
- Designs ranging from small modules to systems with over 100,000 lines of HDL code.
- A property distribution of 799 passing, 312 failing, and 94 unknown results.
- Categorization by difficulty: BM1 (easy), BM2 (medium), BM3 (hard), and MOUT (memory-intensive).
Key Results and Insights
Performance and Robustness
The InterpHybrid method proved to be the most robust overall, resolving 1,068 problems. This outperformed both standard interpolation (1,032 solved) and standard proof-based abstraction (1,010 solved). On hard problems (BM3), InterpHybrid reduced the average runtime from 916 seconds to 698 seconds.
Breaking the Memory Wall
The InterpInc method showed its strength in the MOUT (memory-intensive) category. In scenarios where standard interpolation could only solve 2 out of 29 problems before crashing, InterpInc successfully resolved 14 (8 passes and 6 failures).
The Role of Coarse Abstractions
A significant insight from the study is that interpolation does not require a "perfect" or minimal abstraction to be effective. While InterpInc produces larger abstractions than traditional methods (averaging 999 state variables compared to 38–70), these "coarse" abstractions are much cheaper to compute. This trade-off is essential for preventing memory exhaustion in large-scale industrial applications.
Conclusion
By combining the localization power of interpolation with the efficiency of BDDs and ATPG-style justification, the authors demonstrate that abstraction refinement can significantly extend the reach of SAT-based model checking. While the success of these methods depends on heuristic sensitivity and can result in larger abstractions, they provide a vital path forward for verifying the massive designs found in modern hardware engineering. Future work will focus on refining the "progress measures" for engine switching and developing more sophisticated techniques for finding minimal justifications in the incremental phase.
Summary updated