CS Paper Radar

A Matched Evaluation of QUBO Action Models and Defensive Remediation in Cyber Attack Graphs

Kasymkhan Khubiev, Yaroslav Kholodov, Alexey S. Petrenko

cs.CR ·submitted 2026-11-01 20:28 UTC · v1

Abstract

This study examines how vulnerability-specific actions affect quadratic unconstrained binary optimization (QUBO) models for minimum-cost cyber attack paths and defensive remediation. Edge-flow and variable-length hop formulations are evaluated using simulated annealing, steepest descent, and tabu search against exact classical references. Experiments on six independent synthetic topologies separate the effects of transition eligibility, vulnerability labels, exploit costs, and multiple exploit alternatives. A single labeled action per eligible transition preserves feasible paths, optimal costs, and QUBO size. Under the tested settings, multiple exploit alternatives were associated with approximately unchanged valid-path recovery, lower optimal-path recovery, and substantially larger representations, particularly for the hop formulation. These recovery differences remain descriptive because they are not statistically significant after correction for multiple comparisons. An evaluation on a published 3CX attack graph with synthetic costs demonstrates applicability beyond the generated topologies. The defensive extension selects patches within a budget to raise attack-path costs to specified thresholds or disconnect protected targets. Against exhaustive and mixed-integer references, the tested QUBO heuristics recovered an optimal patch set in 12 of 16 calls across eight scenarios on one topology. The results characterize formulation correctness, solution recovery, and resource requirements using classical local optimization, without establishing quantum computational advantage.

Comment
20 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

AI-Based Vulnerability Assessment Capability and Cyber Attack Graph Analysis

cs.CR ·2026-09-28 ·Joni Herttuainen, Kirsi Hellsten, Vesa Kuikka, Ambrose Kam, Arlanda Johnson +2 more
similarity 0.62
Abstract

Cyber threats targeting mission-critical infrastructure are becoming more sophisticated while the barrier to launching attacks continues to fall. Traditional point solutions like antivirus and firewalls are reactive and fail to address the combinatorial complexity of modern attack surfaces. This paper presents an investigation combining two complementary methodologies: Lockheed Martin's Vortex/Crow framework, which applies multi-agent reinforcement learning (MARL) over industry-standard cyber knowledge graph to identify and prioritize attack vectors and TTPs (tactics, techniques, and procedures); and Aalto's probabilistic attack graph model that combines network topology and its vulnerabilities to compute system-level risk metrics. The 2015 Ukraine Power Grid cyberattack serves as a well-documented validation scenario. Applied independently to the same operational technology (OT) network topology, both methodologies converge on the same attack vectors and exploit sequences as those documented in the incident record, thus providing mutual cross-validation. Attack graph analyses using node-level elimination experiments identify industrial control systems (ICS) as the most critical enablers of attack propagation, representing high-priority targets for defensive hardening. Comparison of CVSS (v2.0) and IronMiner vulnerability scoring yields in general consistent results, with IronMiner providing more actionable differentiation at network periphery nodes. The layered methodology of baseline assessment and node-level elimination proves to be scalable to large enterprise networks, thus offering defenders a structured, AI-enabled path to prioritize mitigation under realistic time and resource constraints.

0.24

Diversifying Moving Target Defense Against Adaptive Attacks Through Factorized Diffusion

eess.SY ·2026-10-16 ·Chenhan Xiao, Yang Weng
similarity 0.62
Abstract · 10 pages, 5 figures

Proactive defense offers a means to enhance power-system cybersecurity through controlled modifications of system configurations. One example is moving target defense (MTD), which uses distributed flexible AC transmission system (D-FACTS) devices to perturb transmission-line reactances against stealthy false data injection attacks. Existing MTD methods primarily rely on deterministic optimization, producing a single perturbation plan for each operating condition. However, repeated or highly correlated plans may expose predictable system configurations that attackers can learn and exploit. To address this limitation, this paper reformulates MTD as a conditional generative problem that produces diverse, secure, and physically feasible perturbation candidates. Learning such a distribution is challenging because MTD decisions jointly involve selecting branches, determining perturbation magnitudes, and coordinating adjustments across the network. To make this problem tractable, we factorize the decision distribution into three sequential conditional stages: branch selection, magnitude allocation, and continuous refinement. Graph-conditioned diffusion models are employed to capture the discrete and continuous decisions while accounting for network dependencies. Furthermore, a - objective is incorporated into diffusion training to favor candidates with desirable defense effectiveness and operational costs. Numerical studies on the IEEE 118- and 300-bus systems show that the proposed framework achieves AC feasibility comparable to that of optimization-based MTD baselines and higher - values, while reducing online computation time by an order of magnitude. The generated candidate pool remains effective under changing operating conditions and device availability, providing diverse high-value alternatives for flexible online cyber defense.

0.19

Objective Transfer in Single-Node Network Criticality: Optimal Constants and Exact Separation Thresholds

cs.DM ·2026-09-28 ·Onur Ugurlu
similarity 0.59
Abstract · 20 pages, 2 figures, 1 table. Ancillary files: replay scripts and exact certificates (anc/)

When a vertex is selected as the most damaging single attack target under one damage objective, how much of the optimal damage under a different objective does it retain? We study this for the three objectives commonly used in critical node detection -- pairwise connectivity (PC), size of the largest surviving component (LCC) and number of components (NC) -- for single-vertex attacks on connected graphs, with the attacked vertex counted in the damage and ties resolved optimistically. For the pair PC, LCC the loss is bounded: a PC-optimal vertex retains at least a $2-\sqrt2$ fraction of the optimal LCC damage, an LCC-optimal vertex at least 2/3 of the optimal PC damage, and both constants are best possible. Neither bound depends on the choice among tied optimal vertices or on whether the attacked vertex is counted, and both remain valid as lower bounds for attack sets of any fixed size. For the four directions involving NC no positive constant exists; explicit families have ratios decaying like 1/k, and no single attack set retains a positive fraction of all three optima uniformly. We also determine the smallest orders at which the sets of optimal vertices become disjoint: 7 for LCC/NC, 8 for PC/NC, 9 for PC/LCC and 11 for all three pairwise, with trees realising the triple separation for every n>=11; these values rest on an exhaustive enumeration of the 11,989,762 connected graphs with 3<=n<=10. Finally, the most critical vertex in a Birnbaum-type sense may depend on the failure probability: a six-vertex graph, of smallest possible order, changes leader once, at $p^*=3-\sqrt5$. Adding universal vertices lifts the budget-one examples to every fixed budget, so over all connected graphs the same constants are optimal at every fixed budget; behaviour within restricted classes such as trees is left open.

0.23

Dynamic Attack Surfaces: A Queue of Branching Processes

cs.IT cs.CReess.SY ·2026-10-13 ·Ismail Cosandal, Abdullah Y. Etcibasi, C. Emre Koksal, Sennur Ulukus
similarity 0.59
Abstract

Modern attack surfaces are inherently dynamic. Vulnerabilities emerge over time and they remain exposed to exploit until defenders discover and patch them. Artificial intelligence (AI) amplifies these dynamics by accelerating both offensive and defensive processes, making modern cybersecurity increasingly a competition among interacting time scales and resources. We capture this competition using a queue of branching processes that couples vulnerability discovery and resource-constrained patching with the evolving attacker population targeting each vulnerability. Our primary risk metric is the cumulative number of exploits a vulnerability experiences before it is patched. We derive the expected cumulative number of exploits under birth-death-immigration (BDI) and rise-decay (RD) models of attacker activity. Under a BDI model of attacker activity, we identify a phase transition: the expected cumulative number of exploits is finite only when attacker growth remains below both the vulnerability discovery rate and the effective patching rate. Across both attacker models, increasing the exploit rate does not necessarily increase the expected number of exploits because faster attacker departure can sufficiently limit the active attacker population. Finally, we show that equal proportional AI amplification of offensive and defensive capabilities need not preserve security: accelerating both sides can shift the defensive bottleneck and move the system into an unbounded-risk regime.

0.20

A Graph-Based Stackelberg Security Game for Trustworthy 6G Disaggregated Architecture

cs.CR eess.SP ·2026-08-24 ·Lav R. Varshney, Xinbo Wu
similarity 0.59
Abstract

Open, cloud-native, and AI-enabled 6G architectures make network functions easier to deploy, observe, and replace, often implemented with separate software modules. However, each explicit interface can also create an entry point, trust transition, and lateral-movement route from a cybersecurity perspective. This paper formulates architectural disaggregation as a graph-based Stackelberg design game for 6G system security. A deployment graph specifies candidate 6G system seams, while an architecture-dependent directed attack graph specifies externally reachable functions and multistage paths. The defender commits to seams and allocates hardening and monitoring; an informed attacker then chooses a path and effort. Because edge traversal and evasion factors compose multiplicatively, the attacker's path response becomes a shortest-path problem after a logarithmic transformation. Convex effort costs admit a conjugate representation, and, for each fixed architecture, the defender's control problem is a convex exponential-epigraph program solvable by path generation. We derive an architecture-comparison criterion, a threshold for AI transducers within 6G systems that jointly add visibility and exposure, and comparative statics for attacker entry and bypass innovation. Experiments with stylized standards-anchored O-RAN/6G systems over RAN, RIC, core, cloud, and edge-AI functions show that neither full integration nor maximal disaggregation is generally best. Uncontrolled seams can increase risk, whereas selectively monitored and hardened seams can improve the Stackelberg objective. We find a boundary is worthwhile only when its detection and containment gains exceed its added attack opportunities and coordination cost.

0.21

CyberBinGym: Can AI Agents Turn Binary Patches into Real Exploits?

cs.CR cs.AIcs.LG ·2026-11-07 ·Lambang Akbar Wijayadi, Zhaoqi Xiao, Zhun Wang, Hongwei Li, Wenbo Guo +3 more
benchmark similarity 0.56
Abstract

Security fixes usually reach users as compiled updates, but deployment delays leave unpatched systems exposed. During this window, comparing patched and unpatched binaries can reveal how to exploit a vulnerability, turning a defensive update into actionable information for attackers. Existing benchmarks do not measure this capability: they expose source code, rely on human-crafted challenges, or evaluate binary comprehension without requiring exploitation. We introduce CyberBinGym, a benchmark containing 100 tasks derived from real vulnerabilities in 53 widely used projects, spanning six vulnerability families and three levels of analysis complexity. Agents receive stripped vulnerable and patched binaries without source code or vulnerability information, and must combine static and dynamic analysis to recover and exploit the vulnerability. Evaluation separately measures vulnerability recovery through differential crash testing and end-to-end exploitation through flag retrieval, with trajectory audits to reject reward hacking. The strongest evaluated agent recovers the target vulnerability in 88% of tasks and exploits it in 20%. Providing the patched binary raises its exploit rate from 10% to 25% on a matched 20-task subset; with standard binary hardening enabled, it still exploits two of its 20 previously successful tasks. These results demonstrate that current agents can turn released binary patches into working exploits in a controlled setting, although exploitation remains unreliable. These capabilities lower the barriers to targeting unpatched software and compress defenders' effective response window, increasing the urgency of timely patch deployment.

0.13

CyberPersistBench: Evaluating LLM-Based Cyber Attackers on Installation and Persistence

cs.CR ·2026-09-29 ·Sujin Chen, Lijun Li, Xuhong Wang, Jing Shao
benchmark similarity 0.56
Abstract · 29 pages, 15 figures

While LLM-based attackers exhibit growing proficiency in vulnerability exploitation, most existing cybersecurity benchmarks suffer from single-stage truncation, prematurely terminating evaluation upon initial access. In practice, initial footholds are exceptionally fragile across operational disruptions such as service restarts and host reboots. Whether LLM-based attackers can establish and maintain durable footholds beyond initial compromise remains a central blind spot in cybersecurity evaluation. To bridge this gap, we introduce CyberPersistBench, the first benchmark dedicated to post-compromise installation and persistence. Decoupled from upfront exploitation, CyberPersistBench frames persistence as an adversarial survival task in which agents use native host mechanisms to maintain footholds across staged system disruptions. Deterministic checks support a six-level scoring method (L1--L6) spanning installation and persistence. The benchmark comprises 203 core tasks across seven categories, augmented by multi-host and active defense extensions. Empirical evaluations across five frontier agents show that autonomous persistence remains limited (27.6%--44.8%) and drops further on defense-enabled tasks (5.5%--13.3%); nonetheless, these results reveal an emerging cyberattack risk, underscoring the necessity of benchmarking post-compromise persistence. CyberPersistBench thus establishes a foundational benchmark for post-compromise installation and persistence, delineating the operational boundaries of autonomous cyber agents.

0.21

Security Games on Series-Parallel Attack Graphs with Adaptive Attackers

cs.GT ·2026-08-21 ·Russell Kai Min Tan, Hui Han Chin, Chun Kai Ling
similarity 0.56
Abstract · 68 pages, 10 figures. Added examples and updated acknowledgements

We study security games on attack graphs, where an adaptive attacker seeks to reach a target by sequentially attempting stochastic controls along the current attack frontier, while a defender allocates limited resources across controls to delay compromise. The attacker may choose among exponentially many attack routes and freely pivot between them as successes and failures are observed, yielding an exponentially large space of contingent attack policies. For any fixed defender allocation, we show that an optimal attacker policy on a two-terminal series-parallel attack graph is an index policy: at each step, the attacker selects an available control with the largest value of an extension of the classical Gittins index. The indices and the resulting attacker best response can be computed in polynomial time, without explicitly enumerating attack paths or contingent policies. To the best of our knowledge, this is the first optimal index characterization for adaptive attackers in security games on general series-parallel attack graphs. We further develop efficient algorithms for computing the attacker's exact utility and an exact defender subgradient, enabling deterministic first-order optimization of defensive resource allocations without sampling attack trajectories. Our framework strictly generalizes prior approaches restricted to parallel chains and out-trees, while exploiting the compositional structure of series-parallel graphs to support interpretable attacker policies and parallel computation across independent subgraphs. Experiments demonstrate that the resulting methods scale substantially better than naive explicit-state approaches while producing effective defensive allocations.

0.47