Combining Abstraction Refinement and SAT-Based Model Checking

Nina Amla, Kenneth L. McMillan

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

Abstract

Unbounded model checking methods based on Boolean satisfiability (SAT) solvers are proving to be a viable alternative to BDD-based model checking. These methods include, for example, interpolation based and sequential ATPG-based approaches. In this paper, we explore the implications of using abstraction refinement in conjunction with interpolation-based model checking. Based on experiments using a large industrial benchmark set, we conclude that when using interpolation- based model checking, measures must be taken to prevent the overhead of abstraction refinement from dominating runtime. We present two new approaches to this problem. One is a hybrid approach that decides heuristically when to apply abstraction. The other is a very coarse but inexpensive abstraction method based on ideas from ATPG. This approach can produce order-of-magnitude reductions in memory usage, allowing significantly larger designs to be verified.
BibTeX
@inproceedings{amla2007combining,
  author = {Nina Amla and Kenneth L. McMillan},
  title = {{Combining Abstraction Refinement and SAT-Based Model Checking}},
  booktitle = {TACAS},
  year = {2007},
  doi = {10.1007/978-3-540-71209-1\_31},
}
Figure