Syntactic Optimizations for PSL Verification

Alessandro Cimatti, Marco Roveri, Stefano Tonetta

Abstract

Formal verification of hardware designs using the IEEE standard Property Specification Language (PSL) often faces a performance bottleneck during the conversion of properties into Nondeterministic Büchi Automata (NBAs). This paper proposes a syntactic preprocessing flow that applies rewriting rules directly to PSL formulas. By simplifying Sequential Extended Regular Expressions (SEREs) and refining Suffix Operator Normal Form (SONF), this approach bridges the gap between fast modular compilation and efficient search times. Experimental results demonstrate that these syntactic optimizations can achieve search performance comparable to expensive semantic minimization techniques while remaining computationally inexpensive.

Introduction

The verification of complex hardware properties typically relies on PSL, which integrates Linear Temporal Logic (LTL) with Sequential Extended Regular Expressions (SEREs). Verification tools generally follow one of two paths:

  1. Monolithic Approaches: These utilize semantic simplifications, such as minimizing the resulting automaton. While this yields efficient search times, the minimization process is often too computationally expensive for large specifications.
  2. Modular Approaches: Methods like Suffix Operator Normal Form (SONF) allow for rapid automaton construction but often produce redundant structures, leading to slow verification search times.

This research addresses this trade-off by introducing a syntactic preprocessing layer that "melts away" the redundancies introduced by PSL's "syntactic sugar" before the automaton generation phase.

Methodology

The authors propose a four-stage syntactic preprocessing flow designed to optimize formulas without the overhead of graph-based semantic minimization.

1. SERE Simplification

The flow targets conjunction operators (& and &&) within regular expressions, which are primary drivers of state-space explosion. By simplifying these arguments early, the tool prevents exponential growth during conversion.

2. SERE-to-LTL Conversion

Whenever possible, regular expressions are converted into LTL. This allows the verification engine to leverage highly optimized LTL algorithms rather than general-purpose automata methods.

3. SONF Refinement

After partitioning the formula into SONF, specific rules are applied to Suffix Operator Subformulas (SOS). These rules push implications deeper into expressions, facilitating better sharing of sub-components.

A comprehensive set of syntactic rewriting rules for PSL operators, including diamonds and implications.

4. LTL Optimization

Finally, standard LTL simplification rules are applied to the resulting temporal logic components to ensure the final output is as lean as possible.

A specific rewriting rule targeting the globally quantified implication of a starred regular expression.

Experimental Evaluation

The proposed method, referred to as TACAS07, was evaluated using three primary benchmarks:

  • Property Test Suite: 1,000 formulas combining industrial patterns with randomly generated SEREs.
  • Gigamax Model: A standard NuSMV hardware model for testing Model Checking (MC) performance.
  • Language Emptiness (LE) Tests: 400 formulas used to evaluate satisfiability check speeds.

Results

The TACAS07 method was compared against the monolithic approach (MONO) and a previous modular approach (FMCAD06). Key findings include:

  • Robustness: TACAS07 successfully solved 36 "hard" problems that caused the FMCAD06 approach to time out.
  • Speed: The total time (compilation plus search) was significantly reduced. Search times were comparable to the MONO approach, but the compilation phase was orders of magnitude faster.
  • Efficiency: For properties solvable by previous modular methods, the new syntactic optimizations provided a speedup of approximately one order of magnitude.

Conclusion and Future Work

Syntactic rewriting offers a powerful, transparent, and customizable way to optimize formal verification. While the method excels in SAT-based Bounded Model Checking (SBMC), the authors noted that it is currently "incomparable" when using Binary Decision Diagrams (BDDs) due to the introduction of fairness constraints that can disrupt variable ordering. Future work will focus on scaling these rules to larger formula sets and developing BDD-specific algorithms to better handle the modular structures produced by this optimization flow.

Summary updated

Abstract

The IEEE standard Property Specification Language (PSL) allows to express all ω-regular properties mixing Linear Temporal Logic (LTL) with Sequential Extended Regular Expressions (SEREs), and is increasingly used in many phases of the hardware design cycle, from specification to verification. In recent works, we propose a modular and symbolic PSL compilation that is extremely fast in conversion time and outperforms by several orders of magnitude translators based on the explicit construction and minimization of automata. Unfortunately, our approach creates rather redundant automata, which result in a penalty in verification time. In this paper, we propose a set of syntactic simplifications that enable to significantly improve the verification time without paying the price of automata simplifications. A thorough experimental analysis over large sets of paradigmatic properties shows that our approach drastically reduces the overall verification time.
BibTeX
@inproceedings{cimatti2007syntactic,
  author = {Alessandro Cimatti and Marco Roveri and Stefano Tonetta},
  title = {{Syntactic Optimizations for PSL Verification}},
  booktitle = {Tacas},
  year = {2007},
  doi = {10.1007/978-3-540-71209-1\_39},
}
Figure