CS Paper Radar

How Much Do $\ell_1$ Attacks Need Concentrated Perturbations?

Melika Shirian, Kianoosh Vadaei, Arshia Hemmat

cs.LG cs.AIcs.CV ·submitted 2026-10-20 07:37 UTC · v1

Abstract

A global $\ell_1$ budget limits how much an adversary may change an image, not how that change is distributed. We ask how much of an $\ell_1$ attack's observed success remains when large coordinate changes are restricted. We add a per-coordinate cap to the budget, enforce the joint constraint by exact in-loop projection, and sweep the cap for APGD-$\ell_1$, SLIDE, and FMN-$\ell_1$ without altering their objectives. Across 18 standard-model settings, caps of at most $32/255$ retain a median $97\%$ of attack success relative to each method's native uncapped baseline, while median peak magnitude falls by $80\%$ and median effective support nearly triples. At matched realized $\ell_1$, capped perturbations remain structurally distinct; separate ImageNet comparisons also show lower LPIPS and DISTS at selected caps. Direct in-loop constrained optimization preserves up to $88$ percentage points more attack success than post-hoc clipping, highlighting the importance of constraint enforcement. Suitable caps nevertheless vary across attacks and models, and adversarially trained classifiers exhibit more heterogeneous concentration sensitivity. These results establish perturbation concentration as a complementary, model- and attack-dependent axis of $\ell_1$ attack evaluation.

Comment
23 pages, 10 figures, 15 tables, including appendices

Closest papers

Nearest neighbours by meaning across the whole index.

Don't Waste the Noise: Importance-Guided Perturbation Allocation under Joint Global and Local Constraints

cs.LG cs.AIcs.CV ·2026-10-01 ·Melika Shirian, Kianoosh Vadaei
similarity 0.63
Abstract

Adversarial optimization under a shared $\ell_1$ budget requires deciding not only how much perturbation to use, but also where that limited budget should be spent. This allocation problem becomes particularly important when individual input coordinates are subject to local magnitude constraints, which restrict the extent to which perturbation can be concentrated on a small number of locations. We introduce an importance-guided allocation mechanism that uses a fixed clean-gradient prior to steer perturbation toward model-sensitive regions while leaving the feasible perturbation set unchanged. A centered allocation objective encourages perturbation at above-average importance locations and discourages unnecessary expenditure elsewhere, thereby redistributing rather than enlarging the available budget. Across ten robust model--dataset configurations under a common capacity-limited threat setting, the proposed method improves attack success over matched APGD- and PMA-based baselines by $2.52$ to $17.70$ percentage points. Allocation analysis shows that these gains are accompanied by substantially greater perturbation mass in high-importance regions without increased global $\ell_1$ consumption. Mechanism ablations further show that centered non-uniform redistribution provides part of the benefit, while model-derived importance yields an additional improvement. These results identify perturbation allocation as a distinct and practically relevant dimension of adversarial optimization under shared-budget, locally constrained threat models.

0.19

Multimodal Resource-Exhaustion Attacks on Vision-Language Models via Joint Pixel-Prompt Optimization

cs.AI cs.CRcs.CV ·2026-09-05 ·Zhaoxiong Ni, Yatie Xiao, Chi-Man Pun, Fei Peng, Qingxiao Guan +1 more
top venuecode/data similarity 0.60
Abstract · Extended version of the paper accepted by ACM CCS 2026

Resource-exhaustion attacks against autoregressive vision-language models (VLMs) typically assume unimodal threat models, treating the image branch as the primary optimization surface while holding user-visible prompts fixed. Even recent loop-centric variants remain confined to this single-channel paradigm, leaving the exploitation of availability unexplored as a cross-modal optimization problem over jointly controllable input surfaces. We introduce Joint Pixel-Prompt Optimization (JPPO), the first compound adversarial framework elevating the visible prompt to a first-class adversarial variable alongside image perturbations. Under a restricted joint-input threat model, JPPO performs coupled, stagewise optimization over both the pixel and prompt surfaces. This produces synergistic cost amplification, mechanistically distinct from loop-dependent failures, exhibiting negligible loop incidence in our experiments. Evaluating five open-source VLM families on MS COCO and ImageNet under an 8/255 infinity-norm budget, JPPO achieves over 4.6x latency and 5.3x energy amplification on Qwen2.5-VL-7B, and over 36.6x latency with 32.7x energy amplification on BLIP-2. This represents the strongest cost amplification among directly compared baselines while requiring substantially fewer optimization iterations. Ablations confirm this amplification arises from multimodal coordination rather than prompt length or isolated modalities. These findings reveal structural blind spots in current VLM serving defenses, motivating cost-aware robustness evaluation as a first-class security requirement for multimodal deployments.

0.34

Margin-Drop Coordinates for Cross-Budget Robustness Evaluation

cs.LG cs.CV ·2026-08-20 ·Yanliang Huang, Zhen Zhang, Peng Xie, Wenyuan Wu, Sitong Zhu +2 more
hot direction similarity 0.58
Abstract

Fixed-budget robustness evaluation can select the wrong frozen vision encoder. An encoder that survives a shallow attack may lose most of that robustness when the same evaluation is strengthened. We ask whether the shallow evaluation contains enough information to identify this budget fragility. For each clean-correct sample, the evaluation records the clean pairwise margin, the first-order linearized margin-drop scale, the margin drop from a clean-start one-step attack, and the drop reached by an iterative attack. Normalizing by that scale gives three margin-drop coordinates capturing clean margin slack, one-step shortfall, and drift, where drift is the additional normalized margin drop the iterative attack reaches beyond the one-step perturbation. Together, they reconstruct the normalized post-attack margin and therefore the pass-or-fail outcome. Across 42 pretrained frozen vision encoders, the shallow survival rate carries essentially no rank information about subsequent PGD-10 to PGD-200 collapse, at Spearman -0.006, while the median shallow drift coordinate ranks the same collapse at +0.811. The result persists in a held-out encoder pool and under an $\ell_\infty$ evaluation. With deep evaluation limited to 11 encoders, ranking by shallow drift recovers 11 of the 17 high-collapse encoders, compared with 5 under survival-rate ranking. The full coordinate decomposition further distinguishes cases that share the same fixed-budget residual but diverge at deeper budgets, and separates margin repair from drift repair under interventions, revealing distinct repair paths that endpoint robustness alone does not identify.

0.36

Bit-Flip Attacks on Vision-Language-Action Models: Action-Decoding Architecture Shapes the Vulnerability

cs.CR cs.AI ·2026-08-16 ·Yudong Gao, Linghan Chen, Wenhan Wu, Mia Zhou, Jiyao Wang +3 more
similarity 0.57
Abstract

Quantized Vision-Language-Action (VLA) models expose a weight-fault surface: Rowhammer-style faults can corrupt deployed INT8 bits. We present the first bit-flip attack on a VLA: a few gradient-selected flips reduce closed-loop success to $0\%$, while hundreds of random flips are harmless. Across four model variants spanning three action-head families, damaging bits concentrate in a few action-generating layers, but the empirical budget depends sharply on the head: direct regression and token policies fall in $1$--$5$ flips, whereas the evaluated flow-matching policies require ${\sim}100$--$300$. Our fixed-direction manifold-escape loss cuts \pizero{}'s budget from ${\sim}1000$ to ${\sim}100$ flips, and a matched five-direction sweep shows that the attack is not specific to an all-positive direction. On a direct head, protecting $3.1\%$ of weights preserves $60\%$ success at $K{=}100$, and protecting $5.3\%$ moves the open-loop break threshold from 3 to 100 flips. Finally, task-calibrated emulated $K{=}100$ flips yield $0/20$ real-robot successes, versus $14/20$ clean and $16/20$ global-random. Weight integrity is therefore a security boundary for embodied foundation models. Code is included as ancillary material.

0.41

Can Attack Difficulty Be Characterized Before Optimization? A Study of Pre-optimization Difficulty in Person-Vanishing Attacks

cs.CV ·2026-09-28 ·Jingyao Xu, Dongdong Wang, Siyang Lu
similarity 0.57
Abstract

Adversarial attacks against object detectors are traditionally studied from an optimization perspective, where attack difficulty is regarded as an outcome observed only after adversarial optimization. This raises a fundamental question: \emph{can the relative attack difficulty of different inputs be characterized before optimization begins?} In this paper, we investigate this question for person-vanishing attacks by introducing the concept of pre-optimization attack difficulty, which captures intrinsic differences in optimization effort across input images. To estimate this latent difficulty before optimization, we propose Quad-CLEVER, an efficient geometry-based estimator derived from a quadratic approximation of the local person-vanishing margin along the most attack-relevant direction. Extensive experiments across multiple attack algorithms demonstrate that Quad-CLEVER consistently correlates with the observed optimization cost, providing empirical evidence that attack difficulty exhibits a predictable pre-optimization structure. Building upon this finding, we further propose a difficulty-aware attack framework that leverages the estimated difficulty to adaptively allocate optimization budgets for a base attack under a fixed computational budget. On BDD100K, the proposed framework improves the image-level attack success rate by up to 5.78$\%$ while reducing the average optimization cost by up to 11.42 iterations. On the more challenging EventPed dataset, it saves 2.25 optimization iterations while maintaining comparable attack performance. These results demonstrate that attack difficulty can be meaningfully estimated before optimization and that exploiting such estimates enables more computationally efficient adversarial attacks.

0.28

Pareto-Improving Adversarial Attacks with Primal-Dual Regularization

cs.LG ·2026-10-03 ·Yang Dai, Longfei Zhang, Wei Tao, Li Shen, Jincai Huang +1 more
positioncode/data similarity 0.57
Abstract · 17 pages, 10 figures

Transferable adversarial attacks are arguably the most practical black-box threat model. Under the same perturbation budget, stronger transfer attacks attain higher attack success rate (ASR), yet their imperceptibility also tends to degrade. Under such a fixed-budget protocol, transferability and imperceptibility therefore appear to trade off against each other. We argue that this conflict is an artifact of fixed-budget evaluation, not an intrinsic trade-off. When attacks are compared on the ASR--imperceptibility Pareto frontier obtained by sweeping $ε$, stronger transfer attacks already attain better imperceptibility at matched ASR than weaker ones. To exploit this latent advantage, we introduce the stealthy transfer attack ST, a plug-in primal-dual wrapper that adds an $L_\infty$ saturation regularizer to the standard constrained objective and resolves it through a two-step primal-dual update: a projected primal step on the perturbation coupled with an $L_1$-ball projection on a dual variable that absorbs the regularizer through Fenchel duality, requiring no auxiliary models or handcrafted perceptual priors. Empirically, ST extends the Pareto frontier across different base attacks and additional surrogate architectures. At $ε{=}16/255$, average imperceptibility gains over each base attack are $17\%$ on LPIPS and $14\%$ on NIQE while ASR is preserved or improved. At matched high-ASR levels, the strongest ST variants further Pareto-dominate dedicated stealth-oriented transfer attacks, confirming that the latent imperceptibility advantage of strong transfer attacks can be unlocked by a primal-dual optimization wrapper without sacrificing transferability. Code will be made available at \url{https://github.com/AndssY/ST}.

0.35

Preventing Model Extraction in Contextual Linear Optimization

cs.LG math.OC ·2026-10-21 ·Adam N. Elmachtoub, Tianyi Lin, Wenxuan Liu
theory similarity 0.54
Abstract · 25 pages, 11 figures

Consider a contextual linear optimization problem, where a predict-then-optimize (PTO) system returns optimal decisions without revealing the cost vectors used in its downstream linear program. Our focus is on how to prevent attackers, who can submit context queries, from extracting the underlying prediction model. Although the cost-to-decision map is many-to-one, observations across contexts can reveal the underlying prediction model. For linear models, we provide sufficient conditions where the attacker can learn the model up to positive scaling by only observing the decision. These conditions motivate an adaptive attack that alternates inverse optimization with boundary sampling, i.e., using context queries leading to decision boundaries of the current attacker model. To prevent extraction, we propose a mechanism that perturbs decisions only when the predicted cost vector is near a decision boundary. We establish a regret bound in terms of the perturbation radius. For the attackers that fit the defended responses as optimal decisions under the evaluation distribution, we also prove a lower bound on expected extraction error. Experiments on synthetic instances and real data quantify the security-performance trade-off of the defense mechanism and illustrate that our defense can increase the extraction error.

0.18

Fair ASR: Re-Evaluating Black-Box Jailbreaks under Shared Target-Call Budgets

cs.CR cs.AI ·2026-08-18 ·Zhida He, Xiaoyu Wen, Han Qi, Ziyuan Zhou, Peng Yu +3 more
code/data similarity 0.54
Abstract · 29 pages, 8 figures, 13 tables. Code: https://github.com/xsddys/Fair-ASR

Reliable jailbreak evaluation is essential for assessing LLM safety, but most existing studies rely solely on attack success rate (ASR) without accounting for its dependence on attack budgets, resulting in unfair comparisons across methods. Existing compute-aware evaluations reduce heterogeneous resources into FLOPs, which is difficult to estimate for black-box models and fails to capture resource-specific constraints. To provide a comparable evaluation basis, we introduce Fair-ASR, an evaluation protocol for black-box jailbreak attacks under shared target-call budgets B, using target calls as a directly observable and method-agnostic comparison axis while tracking attacker calls separately for efficiency analysis. We re-evaluate 11 representative attacks under the Fair-ASR protocol and find that attack rankings change substantially across target-call budgets, simple stochastic perturbations and hand-crafted templates remain highly competitive under equal target access, and no evaluated LLM-driven method is efficient in both target and attacker calls. Motivated by this efficiency gap, we introduce ReCode, a compositional budget-efficient attack that combines desensitization rewriting with two effective low-cost primitives identified by Fair-ASR. Under a budget of 20 target calls, ReCode achieves 85% ASR on GPT-5 while requiring only 7.19 attacker calls per request on average, showing strong efficiency in both target and attacker calls.

0.25