Efficient CSL Model Checking Using Stratification

Lijun Zhang, David N. Jansen, Flemming Nielson, Holger Hermanns

Abstract

For continuous-time Markov chains (CTMCs), the model-checking problem with respect to continuous-time stochastic logic (CSL) has been shown to be decidable, but initial proofs led to algorithms with worse-than-exponential complexity. While efficient polynomial-time algorithms were developed for the "binary until" sublogic, "full" CSL remained computationally expensive. This paper proposes an efficient polynomial-time approximation algorithm for full CSL. The key to our method is the notion of stratified CTMCs with respect to the CSL property to be checked. On a stratified CTMC, the probability to satisfy a CSL path formula can be approximated by a transient analysis in polynomial time using uniformization. We present a measure-preserving, linear-time and -space transformation of any CTMC into an equivalent, stratified one. This makes the present work the centerpiece of a broadly applicable full CSL model checker. Recently, the decision algorithm by Aziz et al. was shown to work only for stratified CTMCs; our transformation ensures decidability for general CTMCs.

TL;DR

This research introduces a polynomial-time approximation algorithm for model checking "full" Continuous-time Stochastic Logic (CSL) on Markov chains. By transforming any model into a "stratified" version using a deterministic finite automaton (DFA), the authors reduce the complex problem of checking multiple sequential time-bounded events to a series of efficient transient probability analyses.

What Problem Does This Paper Address?

Continuous-time Markov chains (CTMCs) are mathematical models used to represent systems that evolve stochastically over time, such as computer networks, chemical reactions, or biological processes. To verify these systems, researchers use Continuous-time Stochastic Logic (CSL).

While checking simple "binary until" properties (e.g., "What is the probability that state A holds until state B is reached within 5 seconds?") was solved with efficient polynomial-time algorithms by Baier et al. in 2000, "multiple until" formulas remained a challenge. These formulas describe a sequence of events (e.g., "High concentration until Medium, then Medium until Low, all within specific time windows").

Prior to this work, the only known algorithm for these complex properties had worse-than-exponential complexity, making it practically useless for real-world systems. Furthermore, the authors discovered that the original 1996 proof for CSL decidability by Aziz et al. contained a subtle flaw: it only worked correctly for a specific subclass of models. This paper provides the transformation necessary to make the logic sound for all CTMCs.

Methods: The Stratification Approach

The authors introduce the concept of stratification. A CTMC is "stratified" with respect to a property if its transitions strictly follow the order of events required by that property. The core of their approach involves three steps:

  1. DFA Construction: They build a Deterministic Finite Automaton (DFA) that acts as a "monitor." This DFA tracks whether a path through the Markov chain is currently satisfying the sequence of requirements in the CSL formula.
The DFA monitor tracks the satisfaction of sequential CSL requirements.
  1. Product Transformation: They create a "product" CTMC by combining the original model with the DFA. This transformation is measure-preserving, meaning the probabilities remain the same, but the resulting model is guaranteed to be stratified.
The resulting product CTMC is stratified, ensuring transitions follow the formula's logical order.
  1. Recursive Transient Analysis: On a stratified model, the probability of satisfying the formula can be calculated recursively. Each step of the recursion uses uniformization—a standard, efficient numerical technique for transient analysis—to compute the probability of staying in a "stratum" for a specific amount of time before moving to the next.

As a theoretical computer science paper, this work uses small, illustrative CTMC examples to demonstrate non-stratified behavior and show how their transformation resolves these issues, rather than large-scale empirical datasets.

Key Insights and Ideas

  • The Stratification "Trick": The difficulty of multiple until formulas stems from the model "jumping back and forth" between states that satisfy different parts of the formula. By taking the product with a DFA, you effectively "unroll" the model so it can only move forward through the formula's stages.
  • Fixing the Decidability Gap: The authors point out that the seminal 1996 algorithm failed on non-stratified models. Their transformation doesn't just make model checking faster; it provides the necessary bridge to ensure that CSL model checking is mathematically sound for all CTMCs.
  • Efficiency: The transformation to a stratified model is remarkably efficient, requiring only linear time and space relative to the size of the original model and the length of the formula.

Key Results

  • Polynomial Complexity: The paper successfully moves full CSL model checking from exponential complexity to polynomial time. Specifically, for finite time bounds, the complexity is $O(|\mathbf{R}|k \cdot \lambda b)$, where $|\mathbf{R}|$ is the number of transitions, $k$ is the formula length, and $\lambda b$ relates to the time bound and transition rates.
  • Linear Transformation: The product construction is $O(|S|k)$ in space and $O(|\mathbf{R}|k)$ in time, making it highly scalable for large models.
  • Algorithmic Contribution: This work provides the theoretical centerpiece for modern, "full" CSL model checkers (like PRISM or MRMC), allowing them to handle complex oscillatory or sequential properties common in systems biology.

Limitations and Future Work

  • Infinite Time Bounds: If the formula includes infinite time intervals (steady-state analysis), the complexity involves Gaussian elimination, which is $O((|S|k)^3)$. While still polynomial, this is significantly more expensive than the transient analysis used for finite bounds.
  • Logic Extensions: The authors suggest that their DFA-based approach could be adapted for other logics, such as PCTL* or step-bounded LTL, potentially offering similar efficiency gains in those domains.
  • Numerical Precision: Like all approximation algorithms based on uniformization, the method's accuracy depends on the chosen precision ($\varepsilon$), which can impact computation time for very high-precision requirements.

Summary updated

Abstract

For continuous-time Markov chains, the model-checking problem with respect to continuous-time stochastic logic (CSL) has been introduced and shown to be decidable by Aziz, Sanwal, Singhal and Brayton in 1996. Their proof can be turned into an approximation algorithm with worse than exponential complexity. In 2000, Baier, Haverkort, Hermanns and Katoen presented an efficient polynomial-time approximation algorithm for the sublogic in which only binary until is allowed. In this paper, we propose such an efficient polynomial-time approximation algorithm for full CSL. The key to our method is the notion of stratified CTMCs with respect to the CSL property to be checked. On a stratified CTMC, the probability to satisfy a CSL path formula can be approximated by a transient analysis in polynomial time (using uniformization). We present a measure-preserving, linear-time and -space transformation of any CTMC into an equivalent, stratified one. This makes the present work the centerpiece of a broadly applicable full CSL model checker. Recently, the decision algorithm by Aziz et al. was shown to work only for stratified CTMCs. As an additional contribution, our measure-preserving transformation can be used to ensure the decidability for general CTMCs.
BibTeX
@inproceedings{zhang2012efficient,
  author = {Lijun Zhang and David N. Jansen and Flemming Nielson and Holger Hermanns},
  title = {{Efficient CSL Model Checking Using Stratification}},
  booktitle = {Logical},
  year = {2012},
  doi = {10.2168/lmcs-8(2:17)2012},
}
Figure