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:
- 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.
- 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.
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.
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