Counterexample-Preserving Reduction for Symbolic Model Checking

Wanwei Liu, Rui Wang, Xianjin Fu, Ji Wang, Wei Dong, Xiaoguang Mao

TL;DR

Model checking complex systems against Linear Temporal Logic (LTL) specifications is notoriously expensive, with costs exploding as formulas get longer. This paper introduces CePRe (CounterExample-Preserving REduction), a technique that simplifies LTL formulas by leveraging specific properties of the model being checked. Unlike traditional methods that require logical equivalence, CePRe only ensures the simplified formula produces the same set of counterexamples, leading to massive speedups in both BDD-based and SAT-based model checking.

Introduction

In formal verification, Linear Temporal Logic (LTL) is the standard for describing system behaviors over time (e.g., "if a request is made, a grant must eventually follow"). However, the computational "tax" for checking these properties is heavy: the complexity is exponential relative to the length and nesting depth of the LTL formula.

Existing tools try to simplify these formulas before checking them, but they typically rely on logical equivalence—meaning the two formulas must be identical in meaning across all possible models. This paper argues that this is too restrictive. If we know something about the specific system (model) we are checking, we can simplify the formula much further. For instance, if a certain condition is an invariant (always true) in our specific system, we can strip it out of the formula even if it isn't a universal logical truth.

The CePRe Methodology

The core idea of CePRe (CounterExample-Preserving REduction) is to transform a formula $\phi$ into a simpler $\psi$ such that $CE(\phi, M) = CE(\psi, M)$—they share the same counterexample set for model $M$. This approach utilizes two main categories of reduction rules:

Model-Independent Rules

These are standard logical simplifications and "duality" principles that hold regardless of the system being checked. They often target nested temporal operators to reduce formula complexity and the resulting state space.

Examples of model-independent LTL reduction rules.

Model-Dependent Rules

The true power of CePRe lies in model-dependent reductions. These rules use "lightweight" checks (like SAT-solving) to see if a part of the formula is redundant given the model's transitions or invariants. For example, if the model $M$ always satisfies $p \to q$, then the complex formula $p \mathbf{U} q$ (p until q) can be reduced simply to $q$.

These rules are applied via a "Max-Match" Strategy, an iterative algorithm that searches for the most impactful reductions, prioritizing simpler conditions and shorter resulting formulas. The authors implemented CePRe as a front-end optimization for NuSMV, a popular symbolic model checker.

Key Results and Performance

The researchers evaluated CePRe using industrial benchmarks (16 specifications from hardware verification) and 200 randomly generated cases. The experimental results showed that CePRe is highly effective:

  • BDD Efficiency: In the Pit.g.ltl benchmark, CePRe reduced the number of BDD nodes to just 12.5% of the original count.
  • SAT-Based BMC: For the Pti.gnv.ltl spec, the number of clauses generated for the SAT solver dropped from 2,101 to 299.
  • Stability: In one case (P0.ltl on dme3), the standard model checker suffered a segmentation fault due to complexity, while the CePRe-optimized version successfully found a counterexample.
  • Shorter Counterexamples: When a violation was found, the counterexamples produced by the reduced formulas were often shorter and easier for engineers to debug.

Conclusion

By shifting the focus from universal logical equivalence to model-specific counterexample preservation, CePRe significantly lowers the barrier for LTL model checking. While the overhead of preliminary SAT-solving is a consideration for extremely large models, the structural impact—fewer BDD nodes and fewer SAT clauses—provides a clear path toward more scalable formal verification. Future work will look into more aggressive reduction schemas involving three or more operators and the exploitation of fairness constraints during the reduction phase.

Summary updated

BibTeX
@article{liu2014counterexample,
  author = {Wanwei Liu and Rui Wang and Xianjin Fu and Ji Wang and Wei Dong and Xiaoguang Mao},
  title = {{Counterexample-Preserving Reduction for Symbolic Model Checking}},
  journal = {J. Appl. Math.},
  year = {2014},
  doi = {10.1155/2014/702165},
}
Figure