跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.20861 · v1

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

首次提交 2026-11-16 18:36
版本更新 2026-11-16 18:36
雷达观测 2026-11-17 17:11
arXiv ↗PDF ↗

摘要

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.

作者备注:VMCAI 2027

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-16 18:36 · 最新观测版本

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.

查看此版本解读 →查看此版本原文 ↗