CS Paper Radar

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

Zhiming Chi, Andrea Turrini, Yong Li, Lijun Zhang

cs.CR cs.AI ·submitted 2026-11-16 10:36 UTC · v1
theory

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.

Comment
VMCAI 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Towards a Theory of Quantitative Vulnerability Analysis for Engineering Systems

eess.SY math.OC ·2026-10-01 ·Daniel A. Eisenberg, David L. Alderson
position similarity 0.60
Abstract · 18 pages, 1 figure, 10 tables

Since the 1980s, risk analysis for engineering systems has been defined based on a tuple of scenarios, $\mathcal{S}$, likelihoods, $L$, and consequences, $C$, where $Risk = (\mathcal{S},L,C)$. We argue that equating this triplet with risk alone is insufficient and potentially misleading. Instead, we define this tuple as a vulnerability space $\mathcal{V} = (\mathcal{S},L,C)$, which becomes risk only when one makes specific interpretations of likelihood and consequence. Here, an interpretation has mathematical meaning, and defines a map that assigns data elements about system vulnerability to a perspective. Formally, we define a vulnerability perspective as a specific choice of interpretations of likelihood and consequence data that allows vulnerability analysis measures to be defined and analyzed. We argue that risk is only one of four common perspectives on $\mathcal{V}$ and demonstrate mathematically why each perspective should remain a distinct concept. First, we show how interpretation of $C$ as a set-valued function produces reliability measures, not risk measures. Then, we show how interpretation of $L$ via possibility theory will produce adversarial and safety measures distinct from risk. This new theoretical framework clarifies the conceptual, mathematical, and practical differences between risk, reliability, adversarial, and safety perspectives---four common engineering system analyses often conflated in the literature. A consequence of our theory is that no single perspective will reveal all vulnerabilities of an engineering system, suggesting decision-making via risk analysis may incur unavoidable and underappreciated tradeoffs from other vulnerability perspectives.

0.31

Cheap to Hypothesize, Costly to Verify: The Defense Surface of Agentic Vulnerability Discovery

cs.CR cs.AI ·2026-09-28 ·Kaikai Zhang, Zihan Zhang, Yuchong Xie, Zesen Liu, Shuangjie Yao +2 more
code/data similarity 0.60
Abstract · Project page: https://xxbai.space/redherring/

Autonomous LLM agents turn vulnerability discovery into a repository-scale search: they generate many vulnerability hypotheses but can verify only a subset under a finite budget. We show that autonomous vulnerability discovery exhibits a hypothesis-verification asymmetry, where verifying a candidate hypothesis through reachability analysis, execution, and proof-of-concept construction is substantially more expensive than forming it. Under a finite resource budget, this makes autonomous discovery a resource-bounded selective-verification process, further exposing verification effort as a unique defense surface. We present RedHerring, which inserts certifiably safe decoys that divert verification effort from real vulnerabilities. Each decoy combines a CVE-derived vulnerability chain that attracts verification with a false bridge that keeps its dangerous sink unreachable. A private certificate lets the defender verify this property efficiently, while establishing the same fact from the released repository requires solving a computationally hard problem. RedHerring further adapts each decoy to the target repository so that it reads as ordinary program logic. Across 33 OSS-Fuzz projects, 70 evaluation instances, and five models under matched budgets, RedHerring reduces real vulnerabilities discovered by 38.7-60.4%. Trajectory analysis shows that agents spend 30.6-51.5% of completion tokens and an estimated 32.5-49.9% of runtime verifying decoys, showing that RedHerring redirects a substantial fraction of the fixed search budget toward decoys. When explicitly informed that decoys may be present, the agent adapts its search strategy, yet RedHerring still reduces vulnerabilities discovered by 37.2% relative to an informed Baseline, showing that its effectiveness does not depend on decoy secrecy.

0.57

CASEL: Consequence-Aware Selective Execution for Reliable Long-Horizon Tool-Using Agents

cs.AI cs.CRcs.SE ·2026-10-27 ·Yanyan Zhang, Fei Shen, Ting Yan, Hao Zhang
top venue similarity 0.60
Abstract · 6 pages, 4 figures. Accepted at the 2026 5th International Conference on Cloud Computing, Big Data Application and Software Engineering (CBA…

Tool-using language agents increasingly modify external systems, yet most runtime safeguards allocate scrutiny by generic uncertainty scores or coarse mutation heuristics. We introduce CASEL (Consequence-Aware Selective Execution Layer), a model-agnostic runtime allocation policy that combines calibrated failure probability, state-dependent consequence, reversibility, ambiguity, and evidence freshness to choose, for each proposed tool call, among direct execution, verification, sandboxing, clarification, approval, and abstention by minimizing a per-mode cost. We formalize direct execution as selective prediction and state and test the validity conditions of a finite-sample threshold and a trajectory risk ledger. In a controlled simulation over 20 seeds with 120,000 test actions each, in which every method has the same intervention menu and the same compute cost, CASEL reduces harmful-side-effect trajectories from 14.75 percent for an uncertainty-ranked gate to 7.02 percent and mean normalized harm from 0.184 to 0.123. A gate ranked by the product of failure probability and consequence reaches similar harm (5.82 percent, 0.120) but sends 45 percent more actions to human approval, and removing reversibility-aware routing raises the rate to 15.53 percent. A trajectory-level risk budget, in contrast, increases harm at equal cost (11.82 percent). Intervention effectiveness is assumed, not measured: the results rank allocation rules under the simulator's assumptions and do not establish deployment effectiveness.

0.31

Risk-certified prompt optimization for LLM-as-a-judge guardrails

cs.CL cs.LG ·2026-11-15 ·Hussein Jawad, Alexandre Landeau, Guy Fleury Iradukunda, Paul Beaumont, Théodore Rezel +2 more
similarity 0.59
Abstract

LLM-as-a-judge guardrails are often controlled primarily through system prompts, yet standard prompt optimization methods target average performance rather than explicit safety constraints. This paper studies system-prompt selection as a constrained optimization problem: maximize benign pass rate while keeping the missed-attack rate below a user-specified level α with finite-sample statistical control. The framework combines LLM-based judging, automatic prompt generation, and distribution-free risk certification. This work instantiates it in two procedures: CPS and CRISP. CPS generates a fixed pool of prompts from training data, then certifies candidates on a held-out evaluation set using simultaneous upper confidence bounds and selects the certified prompt with the highest benign utility. CRISP instead integrates risk feedback into an adaptive search, using hard example-guided rewriting and a reusable-holdout interface to steer generation toward the feasible utility frontier. Experiments on four datasets covering prompt injection, system-prompt leakage, and sensitive-information disclosure show that risk-certified selection consistently respects the target missed-attack level on heldout tests, while utility improves as the permitted risk is relaxed. CRISP is especially useful when fixed-pool search fails to produce certifiable high-utility candidates.

0.13

CAPE - Context-Aware Prioritization Engine for Vulnerability Scoring and Management

cs.CR cs.SE ·2026-10-09 ·Rakesh Podder, Viktoria Koscinski, Indrajit Ray
code/data similarity 0.59
Abstract

Vulnerability patching is critical for safeguarding an enterprise's software ecosystem from cyber attacks. However, patching requires adequate preparation for potential system downtime and for unforeseen effects of the patched software on a live system. Thus, effective risk mitigation requires prioritization strategies that explicitly account for the operational context of the affected software. While vulnerability prioritization based on Common Vulnerability Scoring System (CVSS), Exploit Prediction Scoring System (EPSS) and CISA Known Exploited Vulnerabilities (KEV) catalog, can help, their differing goals and methodologies often lead to inconsistent, context-unaware decisions resulting in mis-allocated remediation efforts. In this work, we present the Context-Aware Prioritization Engine (CAPE), a vulnerability analysis framework that enriches each vulnerability scanner report of vulnerabilities (CVEs) with deployment-specific evidence. This evidence is used to perform vulnerability reachability, centrality, and exploitability analysis, producing a ranked priority score for the effective distribution of remediation effort. We evaluate CAPE on 30 open-source agentic applications comprising 6,138 scanner-reported CVEs. Our evaluation shows that a significant majority of CVEs are not reachable and exploitable which results in significant disparities between CAPE and context-free baselines - the CVSS, EPSS, and KEV. It also shows that CAPE consistently surfaces confirmed-exploitable CVEs at higher priority than all baselines, demonstrating that context-aware analysis provides substantially more accurate remediation guidance than context-free severity scoring alone.

0.33

Scenario-Based Compositional Statistical Model Checking for Safety Specifications

cs.LO cs.AIcs.ROcs.SE+1 ·2026-10-04 ·Abhinav Pomalapally, Arya Raeesi, Kevin Kai-Chun Chang, Beyazit Yalcinkaya, Sanjit A. Seshia
published similarity 0.58
Abstract · 24 pages, 8 figures, 5 tables. Extended version of paper accepted to The 26th International Conference on Runtime Verification (RV 2026)

In safety-critical domains such as autonomous driving, systems must be evaluated across a large number of environment conditions, often represented as composite scenarios built from primitive scenarios. Existing statistical model checking (SMC) approaches analyze each composite scenario independently, requiring many expensive simulations and resulting in substantial redundant computation when scenarios share common structure. This work introduces a scenario-based compositional SMC framework for safety and co-safety specifications, enabling efficient analysis of composite scenarios. Our approach decomposes scenarios into primitives and specifications into sub-specifications, verifies each primitive independently, and composes the resulting statistical estimates using importance sampling and kernel density estimation. Our empirical evaluation shows that the proposed framework can accurately answer verification queries for previously unseen composite scenarios while reducing simulation cost through parallelization and trace reuse.

0.34

Where World Models Break: Natural-Input Failure Discovery

cs.AI ·2026-08-23 ·Zhanpeng Shi, Zi Liang, Rong Feng, Shiqin Tang, Xuyang Chen +1 more
similarity 0.58
Abstract

World models predict action-conditioned futures and serve as critical internal simulators for downstream planning and control. However, catastrophic prediction failures of world models could dangerously propagate through the control pipeline, as subsequent agent or model training and decision-making depend heavily on the continuous environment evolution forecasted by these world models. Existing evaluations overlook this systemic risk: by aggregating average errors over benign generations from general queries, they fail to stress-test the model against catastrophic collapses under rare or unobserved condition-action combinations. To bridge this gap, we formalize the natural-input failure discovery problem: under a finite query budget, finding environment-valid conditions and action prefixes that induce severe prediction risk, verifying whether these failures reproduce on fresh seeds, and testing their persistence under nearby valid edits. Discovering such critical failures is computationally challenging, as valid condition-action combinations explode exponentially, rendering exhaustive search or standard sampling infeasible given the high cost of noisy rollouts. To tackle this, we propose BasinLens, which exploits the underlying structure of valid inputs, where each coordinate possesses environment-defined semantic types and admissible domains, by pairing uncertainty-guided global search with typed local replacements. Across diverse benchmarks and world-model families, BasinLens exposes reproducible and locally persistent failure modes that conventional evaluations fail to reveal, showing that average-case benchmarks can mask important vulnerabilities in world-model-driven control.

0.22

Specification-Guided Path Shortcutting for Efficient Probabilistic Model Checking

cs.LO ·2026-09-02 ·Tsubasa Matsumoto, Kazuki Watanabe, Masaki Waga
publishedbenchmark similarity 0.57
Abstract · To Appear in EMSOFT2026

Given the safety-critical nature of many embedded systems, their safety assurance is essential. Because such systems are typically stochastic, probabilistic model checking is a particularly important technique. However, there is a well-known scalability issue due to state-space explosion, especially when verifying complex properties. To mitigate this issue, we propose specification-guided path shortcutting for probabilistic systems, focusing on Markov chains (MCs) and $ω$-regular properties. The key idea is that, when the verified property is fixed, certain sequences of transitions in an MC can be replaced with a single transition without changing the satisfaction probability, and thus, we can reduce the state space of the MC. We implement the proposed path shortcutting and evaluate its contribution to the performance of probabilistic model checking, using Storm as the baseline model checker. The results suggest that our approach often outperforms the baseline, particularly on benchmark instances with complex specifications.

0.22