Research map / Adversarial robustness and security / Attacks on text and graphs
Quickest Detection of Adversarial Attacks Against Correlated Equilibria
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Models adversarial manipulation of a mediator's public signal in correlated equilibria as a zero-sum quickest change detection game and derives a generalized CUSUM detector that is asymptotically maxmin optimal.
Problem
Detecting an adversary who compromises the mediator's public recommendation signal in a repeated correlated equilibrium, as quickly as possible while limiting false alarms and utility loss to the victim player.
Approach
Formulates the attacker-defender interaction as a two-person zero-sum game over stopping rules and manipulation distributions; the optimal attack is an exponential tilting family of the CE distribution (tau_theta), and the defender's best response is a generalized CUSUM/SPRT-based stopping rule against this family.
Key results
- In the Extended Game of Chicken, at MTBFA of 5x10^4 the attack impact under the minmax attack is less than 250, versus a no-limit total utility of around 3x10^5.
- Detection delay grows logarithmically with MTBFA, and the tau_theta_min attack is the most effective attack in the toy game.
- On the Sioux-Falls routing game with 528 players and an approximate CCE from GP-MW, the proposed attacks and detector remain effective.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the generalized CUSUM detection scheme against the maxmin attack | Extended Game of Chicken · Extended Game of Chicken | attack impact: less than 250; around 3×10^5 without a limit on the number of time steps | Helped |
| Increase the attack parameter θ above θ_min | Generalized CUSUM detector · Extended Game of Chicken | mean detection delay | Helped |
| Use the proposed detection scheme against attacks, including random attacks outside F_Θ | Generalized CUSUM detector · Sioux Falls routing game | attack impact | Helped |
Surprising findings
- A random attack distribution outside the optimal family F_Theta is still detected effectively.
Limitations
- Assumes the victim knows the CE distribution and that utilities of distinct action profiles are distinct (quantization used in routing game).
- Results are asymptotic as false-alarm cost C goes to infinity; the routing game uses an approximate CCE rather than a CE.
- Only one victim player's utility is observed; attacks are restricted to stationary manipulation distributions.
Experimental setup
Datasets: Sioux-Falls traffic network
Benchmarks: Extended Game of Chicken Sioux-Falls routing game
Metrics: MTBFA mean detection delay attack impact
Baselines: random attack distribution in D_epsilon tau_theta1 and tau_theta2 attacks
Builds on: Lorden's asymptotic optimality of CUSUM generalized SPRT GP-MW no-regret learning
Closest papers by meaning
- A Game Theoretic Analysis of Additive Adversarial Attacks and Defenses (NeurIPS 2020 · similarity 0.86)
- Nonzero-sum Adversarial Hypothesis Testing Games (NeurIPS 2019 · similarity 0.85)
- Mixed Nash Equilibria in the Adversarial Examples Game (ICML 2021 · similarity 0.85)
- Regret Minimization in Stackelberg Games with Side Information (NeurIPS 2024 · similarity 0.83)
- No Free Lunch Theorem and Black-Box Complexity Analysis for Adversarial Optimisation (NeurIPS 2024 · similarity 0.83)
- Rethinking Adversarial Policies: A Generalized Attack Formulation and Provable Defense in RL (ICLR 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.