Verifying Quantitative Properties Using Bound Functions

Arindam Chakrabarti, Krishnendu Chatterjee, Thomas A. Henzinger, Orna Kupferman, Rupak Majumdar

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.

Figure 1: A quantitative structure where states are labeled with integer values representing costs or rewards.

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:

  1. Value-bounds: A cap on how high a register can increment before it is treated as effectively infinite.
  2. 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

Abstract

We define and study a quantitative generalization of the traditional boolean framework of model-based specification and verification. In our setting, propositions have integer values at states, and properties have integer values on traces. For example, the value of a quantitative proposition at a state may represent power consumed at the state, and the value of a quantitative property on a trace may represent energy used along the trace. The value of a quantitative property at a state, then, is the maximum (or minimum) value achievable over all possible traces from the state. In this framework, model checking can be used to compute, for example, the minimum battery capacity necessary for achieving a given objective, or the maximal achievable lifetime of a system with a given initial battery capacity. In the case of open systems, these problems require the solution of games with integer values.
BibTeX
@inproceedings{chakrabarti2005verifying,
  author = {Arindam Chakrabarti and Krishnendu Chatterjee and Thomas A. Henzinger and Orna Kupferman and Rupak Majumdar},
  title = {{Verifying Quantitative Properties Using Bound Functions}},
  booktitle = {CHARME},
  year = {2005},
  doi = {10.1007/11560548\_7},
}
Figure