Abstract
Traditional formal verification focuses on binary outcomes—determining whether a system satisfies a specification or not. However, modern resource-constrained systems require quantitative answers regarding battery life, peak power, and response times. This paper introduces a unified framework for verifying quantitative properties by utilizing "bound functions." These designer-provided thresholds transform undecidable infinite-state problems into decidable ones, offering efficient algorithms that match the performance of specialized, property-specific solutions.
Introduction: The Shift to Quantitative Verification
Formal verification has long been a cornerstone of reliable system design, yet its traditional binary nature (Yes/No) is increasingly insufficient. For engineers working on embedded systems or autonomous agents, the critical questions are numerical: "What is the maximum lifetime of this system given a specific battery capacity?" or "What is the minimum resource capacity required to complete a task?"
Verifying these properties typically involves systems with integer-valued registers, such as counters. Unfortunately, checking properties in such systems is generally undecidable, meaning no universal algorithm can provide a correct answer in finite time. Historically, researchers bypassed this by creating ad-hoc, property-specific algorithms for niche problems like "energy games." This research seeks to systematize these efforts into a single, expressive, and computationally feasible mathematical framework.
The Quantitative-Bound Framework
The authors extend the standard verification toolkit into the integer-based domain through several novel components. At the foundation are Quantitative Structures, where states are labeled with integers representing costs, rewards, or power consumption rather than simple boolean truths.
To process these structures, the paper introduces Quantitative-Bound Automata (QBA). These are finite-state machines equipped with integer registers that output a value based on a system "trace." To prevent calculations from diverging to infinity, the authors introduce the core innovation: Bound Functions ($f$). These functions, provided by the system designer, map a system to an integer threshold. They come in two primary forms:
- Value-bounds: A cap on how high a register can increment before it is treated as effectively infinite.
- Iteration-bounds: A limit on the number of steps the algorithm should execute before concluding the value is stable.
By integrating these bounds into a Quantitative-Bound $\mu$-Calculus, the framework allows for the specification of complex properties using fixed-point operators adapted for the integer domain. This allows for the translation of linear-time specifications into branching-time specifications, which is essential for solving games where a system must perform against an adversarial environment.
Benchmarking and Key Insights
As a theoretical contribution, the framework was evaluated against four classic quantitative benchmarks in formal methods:
- Response Time: The maximum latency between a request and its response.
- Fair Maximum: The highest value observed on a path, subject to a fairness condition.
- Lifetime: The number of steps possible before resource exhaustion.
- Peak Running Total: The minimum initial resource needed to prevent the system from ever running out.
Decidability via Designer Knowledge
The primary insight of the paper is that while general counter machines are undecidable, real-world engineering problems often possess natural bounds. By leveraging the designer's domain knowledge through the bound function, the problem becomes solvable. Furthermore, the authors demonstrate that iteration bounds are often significantly more efficient than value bounds. While a value might be numerically large (requiring extensive state representation), the number of steps required to calculate that value is often relatively small.
Unified Complexity
Despite being a "generic" framework, the approach does not suffer a performance penalty. For specific problems like energy games, this general method achieves a complexity of $O(|G|^3 \cdot \Delta)$, matching the efficiency of algorithms designed specifically for those tasks. It also provides a bridge between closed systems (model checking) and open systems (two-player games) through "robust" formulas.
Results and Complexity Classes
The paper establishes clear complexity bounds for the proposed algorithms:
- Model checking with value bounds (QBA-VMC): PSPACE-complete.
- Model checking with iteration bounds (QBA-IMC) and game solving (QBA-VGS/IGS): EXPTIME-complete.
For "monotonic" automata—where values only increase—the authors prove that iteration bounds are linear with respect to value bounds, leading to significantly faster verification cycles. The generic dynamic programming approach was shown to match best-known specialized algorithms for Threshold Büchi Games ($O(|G|^2)$) and standard Energy Games.
Limitations and Future Work
The primary limitation of this framework is the reliance on manual bound specification. While these bounds are often "natural" to define in an engineering context, automatically discovering the tightest possible bound remains an undecidable problem. Additionally, the current framework is strictly integer-based; extending these techniques to real-valued or continuous-time systems (such as hybrid automata) represents a significantly more complex challenge. Finally, like most formal methods, the framework must contend with the "state space explosion" problem, as the state space grows exponentially with the number of registers ($k$).
Summary updated