Introduction
In the domain of formal hardware verification, designers typically rely on two distinct modeling paradigms: axiomatic models and operational models. Axiomatic models describe system behavior through a set of invariants or rules that must hold over an entire execution trace. These models are highly concise and serve as the industry standard for defining complex memory consistency models. Conversely, operational models describe systems as state machines with explicit transitions. While more verbose, operational models are compatible with powerful, state-of-the-art automated verification tools, such as Property Directed Reachability (PDR) or IC3.
Historically, bridging the gap between these two worlds required manual conversion—a process that is notoriously slow, error-prone, and requires formal proofs to ensure equivalence. This paper introduces a framework to automate this conversion, enabling the application of high-performance verification tools to systems previously restricted to slower, manual analysis.
The Theoretical Challenge: Impossibility and $\mu$specRE
The researchers focused their efforts on $\mu$spec, a language designed for modeling microarchitectural orderings. A primary contribution of this work is the identification of the theoretical limits of conversion. The authors prove a "negative" result: it is mathematically impossible to convert every possible $\mu$spec axiom into a finite-state machine. This is because certain axioms require the system to "remember" an infinite history of events to ensure a global property is never violated.
To circumvent this, the authors identified a specific subset of axioms termed $\mu$specRE (Refinable and Extensible). These axioms are "well-behaved," meaning they can be monitored locally without requiring infinite memory. By restricting the conversion to this subset, the framework ensures that the resulting models remain finite and computationally tractable.
Methodology: Axiom Automata and $t$-reordering
The core technical contribution is the generation of Axiom Automata. These are small finite-state machines designed to "watch" a hardware design as it executes. If the system performs an action that would eventually lead to an axiom violation, the automaton enters a designated "bad" state, signaling a failure to the verification tool.
To manage the complexity of out-of-order execution—where instructions may finish in a different order than they started—the authors introduced a $t$-reordering bound. This bound ($t$) limits how far an instruction can "jump" ahead of its neighbors in the execution stream. This constraint keeps the state space manageable, allowing the automata to function effectively within the constraints of modern hardware synthesis and verification environments.
Experimental Evaluation
The framework was evaluated using three realistic hardware designs (RTL):
multi_vscale: A multicore implementation of an in-order RISC-V processor.sdram_ctrl: A complex memory controller for SDRAM.tomasulo: A classic out-of-order execution engine.
By converting axiomatic specifications into RTL-compatible monitors, the authors utilized standard industry tools like Yosys and SymbiYosys to perform verification.
Key Results and Bug Discovery
- Unbounded Proofs: The researchers successfully used PDR to provide "unbounded" proofs for the
multi_vscalepipeline. Unlike Bounded Model Checking (BMC), which only verifies the first $N$ steps of execution, PDR proves the property holds for all possible execution lengths. - Practical Performance: Verification times were highly efficient. Proofs for the
multi_vscaleprocessor completed in 1–2 minutes, while the complex SDRAM controller required approximately 8 minutes. - Real-world Utility: The tool discovered a legitimate bug in the
tomasulodesign. The error involved an incorrect reset of the Register Alias Table, which led to a violation of the "execute-in-order-if-dependent" axiom.
Limitations and Future Directions
While the generation of axiom automata is fully automated, the process of "instrumenting" the hardware—physically plugging the monitors into the RTL—currently requires manual effort. Future work aims to automate this integration step. Additionally, while the current theory is grounded in $\mu$spec, the authors suggest that the underlying concepts of extensibility and local monitoring could be applied to other frameworks, such as the Cat language used for memory models.
Conclusion
By providing a theoretical and practical bridge between axiomatic specifications and operational verification tools, this work significantly lowers the barrier to rigorous hardware verification. The ability to automatically generate monitors from high-level rules allows designers to catch subtle architectural bugs using industry-standard automated solvers, ensuring higher reliability in complex microarchitectural designs.
Summary updated