Black-Box Testing Liveness Properties of Partially Observable Stochastic Systems

Javier Esparza, Vincent P. Grande

Abstract

Testing liveness properties in partially observable stochastic systems presents a significant challenge in formal verification, as it is often impossible to distinguish between a property violation and a delayed event without internal state access. This paper presents a novel black-box testing strategy, $\mathbb{S}[f]$, which utilizes a restart mechanism and requires only logarithmic memory. By reducing $\omega$-regular properties to Rabin languages and employing a block-based execution strategy, the approach scales to systems with over 500 million states, significantly outperforming existing fully-observable testing methods.

Introduction

In the domain of software verification, black-box testing is essential for analyzing large-scale systems where internal code or state-space dimensions are unknown. While safety properties ("something bad never happens") are relatively straightforward to test, liveness properties ("something good eventually happens") pose a unique difficulty in stochastic environments. The fundamental ambiguity lies in determining whether a system has failed to satisfy a liveness property or if the observation window has simply been too short.

Existing methodologies often assume "full observability," where every state transition is visible to the tester. However, real-world systems are typically partially observable, offering only limited outputs or variable values. This research addresses the challenge of detecting liveness violations in partially observable stochastic systems using a single control action: restarting the system.

Methodology: The $\mathbb{S}[f]$ Strategy

The authors propose a restart-based strategy, $\mathbb{S}[f]$, designed to detect violations of $\omega$-regular properties. The approach consists of several key components:

1. Automata Reduction

To handle complex specifications, the researchers demonstrate that any $\omega$-regular property can be reduced to a "Rabin language." This reduction simplifies the testing problem into a canonical form suitable for the restart strategy.

2. Block-Based Execution

Instead of allowing the system to run indefinitely, $\mathbb{S}[f]$ executes the system in discrete blocks of steps. The size of these blocks is determined by a growth function $f(n)$, such as a polynomial $n^c$. This ensures that the strategy probes deeper into the state space over successive iterations.

3. The Restart Mechanism

After each block, the strategy evaluates the "second half" of the observations made since the most recent restart. If this history fails to show progress toward satisfying the liveness property (a "bad" check), the strategy triggers a system restart. This prevents the tester from becoming trapped in "dead-end" components of the state space that do not satisfy the property.

4. Logarithmic Memory Efficiency

A significant advantage of $\mathbb{S}[f]$ over previous "fully observable" strategies is its memory footprint. While older methods required linear memory to store the entire state history, $\mathbb{S}[f]$ only needs to maintain a small set of counters. This results in logarithmic memory usage relative to the execution length, enabling the analysis of much larger systems.

Experimental Evaluation

The strategy was evaluated against a diverse set of benchmarks:

  • Synthetic Markov Chains: Designed to stress-test parameters like "progress radius" (the difficulty of reaching a target state) and "progress probability."
  • PRISM Benchmark Suite: Including standard protocols such as nand, bluetooth, crowds, and herman.
  • Population Protocols: Large-scale distributed computing models from the Peregrine tool suite, which often defy exhaustive model checking.

Key Insights and Results

The experimental results highlight the efficiency and scalability of the proposed approach:

  • Scalability to Massive State Spaces: The strategy successfully identified violations in "gridworld" models containing over 500 million states. In contrast, previous state-of-the-art methods, such as the "Bold" and "Cautious" strategies, either timed out or exceeded memory limits.
  • Superior Efficiency: In the scale10 benchmark, the $\mathbb{S}[f]$ strategy found violations within 75–179 steps, whereas previous methods required over 3,600 steps.
  • Optimal Performance: The authors mathematically proved that a polynomial growth strategy ($f(n) = n^c$) is asymptotically optimal. No other black-box strategy can significantly outperform this approach in terms of the expected number of steps to find a violation.
  • Debugging Utility: The strategy discovered counterexamples for population protocols that specialized tools like Peregrine could not prove correct, establishing its value as a robust debugging tool for complex distributed systems.

Discussion and Limitations

While the $\mathbb{S}[f]$ strategy represents a major advancement, certain limitations remain. The current proofs assume the system is a finite-state Markov chain. While this covers a vast range of applications, the strategy's performance on truly infinite-state systems remains unproven. Additionally, the choice of the exponent $c$ in the growth function $f(n) = n^c$ is critical; a small $c$ may be optimal for some systems, while a larger $c$ is better for others. Without prior knowledge of the system's "progress radius," selecting the ideal $c$ remains a challenge.

Future research may explore subexponential but superpolynomial growth functions and the extension of these techniques to systems involving continuous time or reward structures.

Summary updated

Abstract

We study black-box testing for stochastic systems and arbitrary ω-regular specifications, explicitly including liveness properties. We are given a finite-state probabilistic system that we can only execute from the initial state. We have no information on the number of reachable states, or on the probabilities; further, we can only partially observe the states. The only action we can take is to restart the system. We design restart strategies guaranteeing that, if the specification is violated with non-zero probability, then w.p.1 the number of restarts is finite, and the infinite run executed after the last restart violates the specification. This improves on previous work that required full observability. We obtain asymptotically optimal upper bounds on the expected number of steps until the last restart. We conduct experiments on a number of benchmarks, and show that our strategies allow one to find violations in Markov chains much larger than the ones considered in previous work.
BibTeX
@inproceedings{esparza2023black,
  author = {Javier Esparza and Vincent P. Grande},
  title = {{Black-Box Testing Liveness Properties of Partially Observable Stochastic Systems}},
  booktitle = {ICALP},
  year = {2023},
  url = {https://openreview.net/forum?id=2e63dz4y1z},
}
Figure