Quantitative Multi-objective Verification for Probabilistic Systems

Vojtech Forejt, Marta Z. Kwiatkowska, Gethin Norman, David Parker, Hongyang QuTACAS 2011 · DOI

TL;DR

This paper introduces a novel framework for verifying probabilistic systems with multiple, potentially conflicting, quantitative objectives. It enables not only checking if a system meets these objectives but also synthesizing controllers that optimize them, and performing compositional verification for scalability.

What Problem Does This Paper Address?

Modern systems are increasingly complex, exhibiting both probabilistic behavior (due to failures, randomness) and nondeterminism. Furthermore, evaluating these systems often requires considering multiple performance metrics simultaneously, such as energy consumption, response time, and reliability. Traditional verification methods struggle with this complexity, especially when dealing with multiple, potentially competing, objectives. This paper addresses the challenge of formally verifying systems that have both probabilistic and nondeterministic aspects, and where we need to analyze multiple quantitative properties (like probabilities of certain events and expected rewards/costs) at the same time. This is crucial for tasks like designing controllers that balance performance and resource usage, or for verifying large systems by breaking them down into smaller, manageable components.

Methods

The core of this work is a new language for expressing "quantitative multi-objective properties" (qmo-properties). These properties combine traditional probabilistic temporal logic (like PCTL) with reward structures that capture quantitative measures like "expected total energy consumption" or "expected time to complete a task."

The authors then develop techniques to:

  • Verify qmo-properties: This involves checking if a property holds for all possible behaviors (adversaries) of the system. They achieve this by reducing the problem to checking "achievability queries" and then to solving linear programs.
  • Synthesize optimal adversaries (controllers): This addresses the problem of finding a system behavior (or a controller) that satisfies a qmo-property, often by optimizing one objective while constraining others (e.g., minimizing energy consumption while ensuring a certain level of performance). This is also solved via linear programming.
  • Perform compositional verification: To handle large systems, they extend the assume-guarantee paradigm. Instead of simple safety properties, they use qmo-properties for assumptions and guarantees, allowing for more expressive and powerful compositional reasoning. This is crucial because verifying large probabilistic systems non-compositionally can be computationally infeasible.

Datasets

Not discussed in the paper. The paper uses illustrative examples and case studies, including a disk drive controller and a randomized consensus algorithm, but does not present them as formal datasets.

Key Insights and Ideas

  • Unified framework for diverse objectives: The ability to combine probabilistic safety/liveness properties with expected reward measures in a single specification language is a significant step towards a more holistic system analysis.
  • Bridging verification and synthesis: The framework elegantly connects verifying system properties with synthesizing controllers that achieve desired quantitative trade-offs.
  • Scalability through compositionality: Extending assume-guarantee reasoning to quantitative multi-objective properties is key to tackling the verification of increasingly large and complex probabilistic systems.
  • Linear programming as a powerful backend: The reduction of complex verification and synthesis problems to linear programming provides an efficient and practical solution.

Key Results

  • The paper presents a framework that can verify quantitative multi-objective properties for probabilistic automata.
  • They demonstrate controller synthesis for a disk drive controller, minimizing expected execution time under power constraints.
  • They apply their compositional verification techniques to large case studies (randomized consensus algorithm, Zeroconf network configuration protocol), showing significant speedups and better scalability compared to non-compositional approaches. For instance, in one consensus case study with 5 processes, compositional verification was significantly faster and handled larger models than non-compositional methods.

Limitations and Future Work

  • Assumption 1: The paper relies on an assumption (Assumption 1) to ensure that expected rewards remain bounded, which is crucial for the linear programming approach. While they describe how to check this assumption, it's a constraint on the types of properties and models that can be directly analyzed.
  • Fairness: While fairness is incorporated, the paper focuses on unconditional fairness. More sophisticated fairness conditions might require further investigation.
  • Future Work: The authors suggest extending their compositional verification approach with learning-based assumption generation and investigating continuous-time models. They also note that their techniques can be adapted for multi-objective linear programming to approximate Pareto curves.

Summary updated

BibTeX
@inproceedings{forejt2011quantitative,
  author = {Vojtech Forejt and Marta Z. Kwiatkowska and Gethin Norman and David Parker and Hongyang Qu},
  title = {{Quantitative Multi-objective Verification for Probabilistic Systems}},
  booktitle = {TACAS},
  year = {2011},
  doi = {10.1007/978-3-642-19835-9\_11},
}
Figure