CS Paper Radar

Dynamical low-rank equilibrium computation for stochastic games between advanced persistent threats and moving target defense

Tian Zijian, Zhang He, Chen Xinjie, Wang Wenhai, Liu Xinggao

cs.GT cs.AIcs.CReess.SY ·submitted 2026-09-20 08:03 UTC · v2
theorycode/data

Abstract

Moving target defense (MTD) against advanced persistent threats (APTs) in industrial control systems (ICS) has well-established game-theoretic formulations, but their practical value hinges on equilibrium computation, which faces two gaps: full-rank value iteration is prohibitively expensive at industrial scale, and the resulting defense strategies admit no certified robustness against adversarial perturbations. We first reveal that the attack and defense influence matrices of ICS dynamics are intrinsically low-rank: APTs infiltrate through a handful of entry points and MTD reconfigures only a few components per cycle. Our theory makes four contributions. First, an augmented gradient matrix certifies that the low-rank structure propagates through the non-smooth Bellman operator of the zero-sum stochastic game, so that every Bellman target lies near a low-dimensional subspace and low-rank truncation incurs an explicit error bound (Lemma 1, Theorem 1). Second, we propose the Dynamical Low-Rank Nash Equilibrium algorithm, named DLR-NE, which augments the rank-r search space each iteration, regularizes the core matrix spectrum, and retracts via truncated SVD, and prove that it converges geometrically to a neighborhood whose error decomposes into five physically interpretable sources (Theorem 2). Third, its per-step cost is O(nr^2), a Theta(n/r^2) speedup over full-rank value iteration (Theorem 3). Fourth, a single weight trades accuracy against a certified sensitivity bound of the induced defense strategy under core-matrix perturbations (Corollary 1). Six experiments on a nonlinear power-system testbed confirm each prediction, with 94% parameter compression at 2.3% utility loss. All experimental data and code are publicly available.

Comment
Regular Paper, under review at Automatica (submission 26-2265). v2: corrected the utility-loss figure in Experiment 5 (2.3%). This preprint is the full-length version; the journal submission is a condensed 16-page two-column version. Source code: https://github.com/tz98lab/dlr-ne-ics-security

Closest papers

Nearest neighbours by meaning across the whole index.

Defense Filters for Robust Learning of Partially Observed Dynamical Systems

eess.SY math.OC ·2026-10-15 ·Jihun Kim, Javad Lavaei
similarity 0.64
Abstract · 8 pages, 1 figure

Robust estimation of unknown system dynamics from partial observations under attack is a core challenge in learning for control, increasingly critical in multi-agent networks subject to adversarial data poisoning. Existing methods either require highly restrictive assumptions on the adversary or yield weak error bounds. In this paper, we consider identifying partially observed linear dynamical systems subject to adversarial attacks with an attack probability $p < 0.5$ at each time. We propose a defense-filtering framework leveraging knowledge of the observation matrix to construct a defense filter satisfying full column rank and subspace separability conditions, which enables the evaluation of a single-attack scenario against observed data. Using this framework, we analyze the constrained $\ell_2$-norm estimator and establish finite-sample error bounds for recovering the Markov parameter matrix up to a linear transformation. This is the first approach to provide provable system identification guarantees via a defense filter for partially observed systems subject to harsh environments where the attack probability approaches $0.5$.

0.36

Hierarchical Defense in Leader-Defender-Attacker Games: Nested Equilibria and Receding-Horizon Control

eess.SY ·2026-10-07 ·Honglei Guo, Hanfang Zhang, Guochuan Zhang, Yuhan Zhao
similarity 0.63
Abstract

We formulate a discrete-time leader-defender-attacker game that combines hierarchical interaction within a protective group with competition against an external attacker. The leader seeks to reach a prescribed demand point while avoiding capture, whereas the defender seeks to intercept the attacker while remaining near the leader. To capture their distinct objectives and asymmetric interactions, we introduce a nested equilibrium concept combining a leader-defender Stackelberg relationship with a Nash-type best-response condition for the attacker. For linear dynamics and quadratic objectives, we derive affine response laws and a backward recursion, together with sufficient conditions for unique stagewise solutions. We further express arrival, capture, and interception conditions as quadratic inequalities in the initial joint state, characterizing winning regions under the resulting policy. A receding-horizon algorithm implements the computed control laws using updated state information. Numerical experiments over randomized initial configurations examine the influence of the prediction horizon and compare the proposed method with an independent-control baseline, illustrating differences in game outcomes and the agents' realized costs.

0.18

Epsilon-Nash Equilibria in History-Dependent SA-MDPs

cs.GT cs.CR ·2026-09-16 ·Brandon Gary Kaplowitz, Dominik Bohnet Zurcher, Akash Agrawal, Tala Jafari, Christian Schroeder de Witt +1 more
theory similarity 0.63
Abstract

We study state-adversarial Markov decision processes (SA-MDPs) as games of observation-space attacks: at each step, an agent selects an action from a received observation while an adversary$\unicode{x2014}$who knows the true state the agent is in$\unicode{x2014}$chooses a perturbed observation within a state-dependent proximity set. While existing work focuses on Markovian policies, we develop a solution concept and computational approach for SA-MDPs under history dependence. History dependence can materially change equilibrium outcomes and can force both the agent and the adversary to adapt their strategies. First, we prove the non-existence of universal (agnostic of the initial state distribution) history-dependent equilibrium policies. Our main result presents the first algorithmic route to computing $ε$-approximations of initial-state dependent equilibria. We do so by reducing SA-MDPs to a strategically equivalent constrained zero-sum one-sided partially observable stochastic game. We test our algorithm on small analytically verifiable games and show that it scales to larger, more realistic benchmarks, including Atari Freeway rollouts with a 12-period ahead horizon.

0.21

Planning Against Learning in Rank-1 Games

cs.GT ·2026-08-18 ·William Overman
similarity 0.61
Abstract

Learning algorithms are often used to make decisions in repeated multi-agent environments. When another player understands how a learner adapts from past experience, that player can plan strategically across rounds to influence the learner's future behavior. Recent work shows that optimizing against Replicator Dynamics, the continuous-time analogue of Multiplicative Weights Update, is tractable in zero-sum games but can be hard in unrestricted general-sum games. We study the first structured class beyond zero sum: bimatrix games satisfying $\text{rank}(A+B)=1$, for which Nash equilibria can be computed in polynomial time. Our main result shows that this equilibrium tractability does not extend to planning against learning dynamics. Unless $\mathsf{P}=\mathsf{NP}$, approximating the optimizer's optimal continuous-time reward within a fixed additive constant is NP-hard even when $\text{rank}(A+B)=1$, the learner starts from the uniform state, and the optimizer is restricted to constant strategies. The hardness persists for bounded payoff matrices and polynomially bounded horizons. We complement this result with structural characterizations of several tractable special cases. Thus rank-one games already separate efficient equilibrium computation from strategic planning against a learning opponent.

0.06

Efficient Nash Equilibrium Computation for Cybersecurity Games

cs.GT cs.AI ·2026-09-16 ·Michael Lanier, David Farmer, Yevgeniy Vorobeychik
theory similarity 0.61
Abstract

Game-theoretic analyses of cyber defence often compute equilibria of games whose payoffs exist only as the output of a simulator. Iterative equilibrium-finding methods grow a set of attacker and defender policies and need the payoff of every attacker--defender pair, so they are bottlenecked by payoff estimation: each payoff costs many simulator runs. We introduce Regret-Weighted Payoff Sampling (RWPS), which spends a fixed simulation budget on the payoffs the equilibrium actually depends on and predicts the rest with a model trained on every payoff measured so far. Standard error bounds for estimated games are driven by the worst-estimated payoff, so they cannot credit an estimator that is inaccurate only where accuracy does not matter. We prove a bound that weights payoff errors by the opponent's equilibrium strategy, a certificate that can be computed from simulated payoffs alone, and a condition under which errors in the predicted payoffs cannot change either player's regret. On three synthetic general-sum games, one of them a Colonel Blotto game of military resource allocation, the new bounds are four to six times tighter than the standard one, and RWPS finds less exploitable equilibria than minimum-regret-first search, information-gain search and progressive sampling at the same budget. On two cyber-defence simulators, CyGym and a new game whose hosts are LLM agents exposed to prompt injection, it gives the least exploitable equilibria at the smallest budgets.

0.26

Approximate Dynamic Programming for Link Reconfiguration to Reduce Malicious Input Controllability in Consensus Networks

eess.SY ·2026-10-29 ·Nathaniel Mailhot, Mohammad Pirani, Davide Spinello
similarity 0.60
Abstract

Communication links influence how strongly a malicious input at one sensor affects a consensus network. We study how a defender can reduce this influence by selecting one additional link after observing the currently attacked sensor. The attacked sensor changes over time, and vulnerability is measured by the trace of a finite-horizon controllability Gramian. A prescribed local epsilon-greedy attacker response rule defines a discounted Markov decision process for the defender. Exact dynamic programming (DP) provides an optimal policy using the full Gramian payoff matrix and attacker transition model. We then introduce approximate dynamic programming (ADP) that learns from sampled attacker transitions and empirical Gramian costs estimated from measured impulse responses. Under conditionally unbiased costs and standard sampling and learning-rate conditions, the learned action-value table converges to the exact DP solution. The analysis uses Bellman contraction and bounds the effect of persistent Gramian estimation bias, establishing when measured responses recover optimal defender decisions without constructing the full payoff matrix. In simulations on 20- and 100-node graphs, empirical ADP rollout costs are within 0.23% and 1.76%, respectively, of exact DP. In a two-dimensional intruder tracking example, both policies reduce network-wide root-mean-square tracking error spread by approximately 25% relative to an unmitigated attack.

0.18

Networked Multi-Resource Defense Capabilities in a General Lotto Game

cs.GT cs.CReess.SY ·2026-08-28 ·Faezeh Shojaeighadikolaei, Keith Paarporn
publishedbenchmark similarity 0.60
Abstract · 9 pages, 3 figures, Accepted for presentation at the 65th IEEE Conference on Decision and Control (CDC 2026)

Ensuring the security of complex systems involves the strategic allocation of defensive resources to prevent various types of attacks from succeeding. A defender often has multiple types of defensive assets at its disposal, where it must decide how to optimally deploy their heterogeneous capabilities across different attack types. In this paper, we formulate a multi-resource allocation problem in the form of a General Lotto game where a defender possesses various types of resources. A feature that we introduce is that their individual effectiveness against different types of attacks is characterized by a network weight matrix. In our analysis, we derive upper and lower bounds on the performance of the defender, and provide numerical evidence suggesting that they are tight. For the case of two attack types, we analytically prove that the bounds coincide, establishing an exact equilibrium characterization. We then numerically compare our proposed networked multi-resource architecture to an independent-defense benchmark from the existing literature. These results highlight fundamental and tractable structures underlying multi-attack-type defense problems.

0.21

A Hidden Markov Preference Model for Online Prediction of Adversary Actions

cs.LG ·2026-11-05 ·Angel Daruna, Michael Cogswell, Tixiao Shan, Yi Yao, Han-Pang Chiu +1 more
benchmark similarity 0.59
Abstract

A defender anticipating an attacker needs a probability distribution over the attacker's next action from information available before that action occurs. Two structures complicate this: the attacker's behavioral regime persists and can switch within an episode, and each action combines an operation with state-dependent arguments whose feasible values change over time. We capture both with a hidden Markov model whose latent state is the active regime and whose regime-conditioned action law is defined on a feasibility-masked tree of executable actions. The same likelihood forms the next-action distribution and updates the regime belief once the action is seen, and a partially observed prefix contributes its resolved local factors. Estimation separates into convex logistic fits that Baum-Welch reuses when regimes are unlabeled. We derive a reach-weighted nodewise KL expression for regime information, a sequence-wise log-loss bound for switching regime paths, and a uniform fallback guarantee. On the CAGE 2 cyber defense benchmark the filtered latent state is worth 0.8 nats per step, and after a controller switch the loss begins to fall in three steps against ten for a recurrent baseline.

0.27