Accelerated Model Checking of Parametric Markov Chains

Paul Gainer, Ernst Moritz Hahn, Sven SchewearXiv 2018 · arXiv

TL;DR

This paper introduces a high-performance approach to parametric model checking by replacing traditional symbolic polynomial fractions with Directed Acyclic Graphs (DAGs) to represent rational functions. By avoiding the computationally expensive process of simplifying complex algebraic expressions during state elimination, the authors achieve speedups of 20x to 120x over existing state-of-the-art tools.

What Problem Does This Paper Address?

Parametric Markov Chains (PMCs) are powerful tools for analyzing systems where transition probabilities aren't fixed constants but functions of parameters (e.g., the probability of a message being lost, $p$, or the chance of a coin flip, $1-p$). They allow researchers to ask "what if" questions: What is the optimal value for $p$ to ensure 99% reliability?

However, analyzing these models is notoriously slow. The standard technique, state elimination, works similarly to converting a finite automaton into a regular expression. As states are removed, the labels on the remaining edges—which are rational functions (fractions of polynomials)—grow exponentially in complexity. Traditional tools spend the vast majority of their time performing "expression simplification" (finding greatest common divisors to cancel out common factors). This "symbolic explosion" often leads to out-of-memory errors or prohibitive runtimes for even moderately sized systems.

Fig. 1: Simulating a biased dice by a biased coin.

Methods

The authors propose a shift in how we store and manipulate these symbolic expressions. Instead of representing a rational function as a pair of coprime polynomials, they use arithmetic circuits represented as DAGs.

Key Innovations:

  1. DAG-based Representation: Every algebraic operation (addition, multiplication, additive/multiplicative inverse) simply adds a new node to a global DAG. This makes symbolic operations practically constant-time, as no immediate simplification is required.
  2. Structural Sharing: By using hash maps, the system identifies and reuses existing nodes for identical operations, preventing the graph from growing redundantly.
  3. Random Point Evaluation: To check if two complex nodes in the DAG represent the same function (without full algebraic simplification), the authors use the Schwartz-Zippel Lemma. By evaluating the functions at a few random points, they can identify equivalent nodes with extremely high confidence.
  4. Synergy with State Elimination: The state elimination algorithm itself follows a DAG-like structure. The authors exploit this natural fit, integrating the DAG representation directly into the ePMC model checker.
Fig. 2: An arithmetic circuit (DAG) representing the probability function for a specific die roll.

The authors also extend this technique to compute long-run average rewards, a more complex property that involves analyzing the recurrence behavior of the system.

Fig. 3: Computation of long-run average values.

Datasets

The approach was evaluated using four well-known benchmarks from the probabilistic model checking community:

  • Crowds Protocol: An anonymity protocol for internet users.
  • Bounded Retransmission Protocol (BRP): A file transfer protocol over lossy channels.
  • Cyclic Polling Server: A network model with multiple clients and a single server.
  • Oscillator Synchronisation: A model of coupled nodes adjusting their internal clocks.

The authors compared their tool, ePMC(D) (DAG-based) and ePMC(DS) (Simplified DAG), against the standard PRISM, Storm (both its parametric and sampling engines), and the original polynomial-based version of ePMC.

Key Insights and Ideas

  • Deferring the Pain: The core "aha" moment is that you don't need to simplify expressions during the elimination process. By keeping them in a DAG, you only pay the price of evaluation when you actually need a numerical result.
  • Numerical Robustness: Surprisingly, evaluating a DAG using floating-point arithmetic is often more numerically stable than evaluating a simplified polynomial fraction. The latter frequently suffers from "cancellation" errors that force the use of slow, exact arithmetic.
  • Heuristics Matter: The order in which states are eliminated significantly impacts the size of the resulting DAG. The authors found that TargetBFS (eliminating states backwards from the target) is generally the most effective heuristic.

Key Results

  • Massive Speedups: Compared to traditional polynomial-based methods in PRISM and ePMC, the DAG approach was 20 to 120 times faster.
  • Scalability: On the Bounded Retransmission Protocol, the DAG-based engine handled models with over 50,000 transitions in under 30 seconds, while traditional symbolic engines ran out of memory.
  • Competitive with Sampling: The approach even outperformed Storm’s sampling engine (which uses value iteration) in several instances, particularly when a high number of parameter valuations needed to be checked.

Limitations and Future Work

  • Human Readability: While DAGs are efficient for computers, a DAG with millions of nodes is impossible for a human to interpret compared to a simple (if long) polynomial string.
  • Memory Footprint: For certain models, like the Cyclic Polling Server, the DAG can become extremely large, leading to high memory consumption even if the runtime remains low.
  • Future Directions: The authors suggest integrating interval arithmetic to provide guaranteed error bounds for parameter ranges and exploring GPGPU acceleration to parallelize the evaluation of the DAG across thousands of points simultaneously.

Summary updated

Abstract

Parametric Markov chains occur quite naturally in various applications: they can be used for a conservative analysis of probabilistic systems (no matter how the parameter is chosen, the system works to specification); they can be used to find optimal settings for a parameter; they can be used to visualise the influence of system parameters; and they can be used to make it easy to adjust the analysis for the case that parameters change. Unfortunately, these advancements come at a cost: parametric model checking is---or rather was---often slow. To make the analysis of parametric Markov models scale, we need three ingredients: clever algorithms, the right data structure, and good engineering. Clever algorithms are often the main (or sole) selling point; and we face the trouble that this paper focuses on -- the latter ingredients to efficient model checking. Consequently, our easiest claim to fame is in the speed-up we have often realised when comparing to the state of the art.
BibTeX
@misc{gainer2018accelerated,
  author = {Paul Gainer and Ernst Moritz Hahn and Sven Schewe},
  title = {{Accelerated Model Checking of Parametric Markov Chains}},
  year = {2018},
  eprint = {1805.05672},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.05672},
}

Loading related content...

Figure