Abstract
Formal verification of complex systems often relies on precise mathematical models, which are frequently unavailable in real-world scenarios. This paper presents a novel framework for the data-efficient verification of systems modeled as parametric Markov Decision Processes (pMDPs). By integrating formal parameter synthesis with active Bayesian learning, the proposed method designs experiments that prioritize the collection of the most informative data relative to a specific property. This property-directed approach allows for quantifying confidence in system safety or performance with significantly fewer observations than traditional statistical model checking, particularly for unbounded-time properties.
Introduction
Proving that a system, such as a robotic controller or a power grid, behaves correctly typically requires a complete mathematical model. However, in practice, system parameters—such as sensor failure rates or environmental transition probabilities—are often unknown. Traditional formal verification fails when models are incomplete, while Statistical Model Checking (SMC) treats the system as a black box, necessitating massive amounts of simulation data to achieve high confidence. This paper addresses the challenge of data-efficient verification: how to verify properties when data collection is expensive and the system is only partially understood.
Methodology
The authors propose a three-phase iterative framework designed to refine system knowledge through "smart" experimentation.
- Parameter Synthesis: The process begins by analyzing a parametric Markov Decision Process (pMDP) against a property $\phi$ expressed in Probabilistic Computation Tree Logic (PCTL). Using tools like PRISM or Storm, the framework identifies the feasible set ($\Theta_\phi$): the range of unknown parameter values for which the property holds.
- Active Experiment Design: Instead of random testing, the algorithm synthesizes a strategy $\pi$ designed to generate the most informative data. It prioritizes actions that are expected to move the system's confidence toward 0 or 1 as quickly as possible.
- Bayesian Inference & Confidence Computation: As data $D$ is collected, the model updates its belief $p(\theta|D)$ over the unknown parameters. The final confidence value $C = \mathbb{P}(\mathbf{S} \models \phi)$ is calculated by integrating this distribution over the feasible set $\Theta_\phi$.
Experimental Evaluation
The framework was evaluated using synthetic benchmarks designed to test various aspects of the approach:
- Simple pMDP models: Used to investigate edge cases where standard offline strategies might fail.
- Scalability tests: Models with up to 1,000 states were used to observe computational overhead relative to system complexity.
- Ground Truth Comparison: The calculated confidence was compared against the "true" mathematical satisfaction of the property to assess accuracy.
Key Results
The experimental results demonstrate several advantages over baseline methods:
- Faster Convergence: The synthesized active strategies reached high confidence levels significantly faster than random static or no-strategy baselines.
- Robustness to Trace Length: Unlike SMC, which often requires long traces for certain properties, this method proved relatively insensitive to trace length, provided the total number of observed transitions remained constant.
- Accuracy: The Mean Squared Error (MSE) relative to the ground truth was consistently lower, particularly when system parameters were near the boundaries of the feasible set.
Discussion and Conclusion
A key insight of this work is property-directed learning: by focusing only on the parts of the system that affect the specific property $\phi$, the method achieves superior data efficiency. Furthermore, the "feasible set" bridge allows the framework to handle unbounded-time properties (e.g., "eventually reaching a goal") that are typically inaccessible to standard SMC.
While effective, the current approach is limited by the complexity of synthesized strategies (currently deterministic and memoryless) and the number of available actions in the model. Future work will explore extending the framework to continuous-time Markov chains (CTMCs) and incorporating more complex strategy classes to further enhance efficiency in physical engineering applications.
Summary updated