Scenario-Based Risk Certificates for Multi-Property Vulnerability Discovery in Parametric MDPs

Safety-critical systems such as network protocols and distributed algorithms depend on environmental parameters whose exact values are uncertain. Parametric Markov decision processes (pMDPs) model such systems by making transition probabilities symbolic functions of the parameters. For a single quantitative requirement, parametric verification asks which parameter valuations satisfy the requirement. In practice, however, engineers often monitor several safety and performance requirements at once, and one valuation may make several requirements vulnerable simultaneously. In this paper we study multi-property vulnerability discovery under requirement-wise semantics: given a pMDP and M quantitative requirements, we construct candidate regions of the parameter space that may contain violations, and study budgets for random testing under a specified parameter distribution. To solve this, we adopt a two-layered approach in which the scenario-approximation layer provides PAC guarantees on identifying conservative vulnerability regions for each requirement while the testing layer treats random parameter exploration as coverage of overlapping regions and yields a stopping certificate computed from the marginal region masses alone; a composition theorem then bounds the expected non-discovery score by the scenario approximation error plus the testing risk from the two layers. For confirmed discoveries, candidate hits are checked by model checking and budgets use independently certified discovery probabilities. Experiment evaluate these certificates using empirical surrogates and independent confidence bounds.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.20861
Primary Topic
Formal Methods in Verification
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Scenario-Based Risk Certificates for Multi-Property Vulnerability Discovery in Parametric MDPs

Andrea Turrini, Zhiming Chi, Yong Li, Lijun Zhang
arXiv (Cornell University)
Formal Methods in Verification
preprint

Scenario-Based Risk Certificates for Multi-Property Vulnerability Discovery in Parametric MDPs

Andrea Turrini, Zhiming Chi, Yong Li, Lijun Zhang
preprint en

Abstract

Safety-critical systems such as network protocols and distributed algorithms depend on environmental parameters whose exact values are uncertain. Parametric Markov decision processes (pMDPs) model such systems by making transition probabilities symbolic functions of the parameters. For a single quantitative requirement, parametric verification asks which parameter valuations satisfy the requirement. In practice, however, engineers often monitor several safety and performance requirements at once, and one valuation may make several requirements vulnerable simultaneously. In this paper we study multi-property vulnerability discovery under requirement-wise semantics: given a pMDP and M quantitative requirements, we construct candidate regions of the parameter space that may contain violations, and study budgets for random testing under a specified parameter distribution. To solve this, we adopt a two-layered approach in which the scenario-approximation layer provides PAC guarantees on identifying conservative vulnerability regions for each requirement while the testing layer treats random parameter exploration as coverage of overlapping regions and yields a stopping certificate computed from the marginal region masses alone; a composition theorem then bounds the expected non-discovery score by the scenario approximation error plus the testing risk from the two layers. For confirmed discoveries, candidate hits are checked by model checking and budgets use independently certified discovery probabilities. Experiment evaluate these certificates using empirical surrogates and independent confidence bounds.

arXiv (Cornell University)
Formal Methods in Verification
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon