Gradient Structure Estimation under Label-Only Oracles via Spectral Sensitivity

• URL: http://arxiv.org/abs/2601.14300v1
• Date: Sat, 17 Jan 2026 02:47:47 GMT
• Title: Gradient Structure Estimation under Label-Only Oracles via Spectral Sensitivity
• Authors: Jun Liu, Leo Yu Zhang, Fengpeng Li, Isao Echizen, Jiantao Zhou,
• Abstract summary: We develop a unified theoretical perspective showing that a wide range of existing sign-flipping hard-label attacks can be interpreted as implicitly approximating the sign of the true loss gradient.<n>Motivated by this first-principles understanding, we propose a new attack framework that combines a zero-query frequency-domain initialization with a Pattern-Driven Optimization (PDO) strategy.<n>We empirically validate our framework through extensive experiments on CIFAR-10, ImageNet, and ObjectNet, covering standard and adversarially trained models, commercial APIs, and CLIP-based models.
• Score: 37.729118253160145
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hard-label black-box settings, where only top-1 predicted labels are observable, pose a fundamentally constrained yet practically important feedback model for understanding model behavior. A central challenge in this regime is whether meaningful gradient information can be recovered from such discrete responses. In this work, we develop a unified theoretical perspective showing that a wide range of existing sign-flipping hard-label attacks can be interpreted as implicitly approximating the sign of the true loss gradient. This observation reframes hard-label attacks from heuristic search procedures into instances of gradient sign recovery under extremely limited feedback. Motivated by this first-principles understanding, we propose a new attack framework that combines a zero-query frequency-domain initialization with a Pattern-Driven Optimization (PDO) strategy. We establish theoretical guarantees demonstrating that, under mild assumptions, our initialization achieves higher expected cosine similarity to the true gradient sign compared to random baselines, while the proposed PDO procedure attains substantially lower query complexity than existing structured search approaches. We empirically validate our framework through extensive experiments on CIFAR-10, ImageNet, and ObjectNet, covering standard and adversarially trained models, commercial APIs, and CLIP-based models. The results show that our method consistently surpasses SOTA hard-label attacks in both attack success rate and query efficiency, particularly in low-query regimes. Beyond image classification, our approach generalizes effectively to corrupted data, biomedical datasets, and dense prediction tasks. Notably, it also successfully circumvents Blacklight, a SOTA stateful defense, resulting in a $0\%$ detection rate. Our code will be released publicly soon at https://github.com/csjunjun/DPAttack.git.

Related papers

• A Few Large Shifts: Layer-Inconsistency Based Minimal Overhead Adversarial Example Detection [13.109309606764754]
  We introduce a plug-in detection framework that leverages internal layer-wise inconsistencies within the target model itself.<n>Our method achieves state-of-the-art detection performance with negligible computational overhead.
  arXiv  Detail & Related papers  (2025-05-19T00:48:53Z)
• Typicalness-Aware Learning for Failure Detection [26.23185979968123]
  Deep neural networks (DNNs) often suffer from the overconfidence issue, where incorrect predictions are made with high confidence scores. We propose a novel approach called Typicalness-Aware Learning (TAL) to address this issue and improve failure detection performance.
  arXiv  Detail & Related papers  (2024-11-04T11:09:47Z)
• AdvQDet: Detecting Query-Based Adversarial Attacks with Adversarial Contrastive Prompt Tuning [93.77763753231338]
  Adversarial Contrastive Prompt Tuning (ACPT) is proposed to fine-tune the CLIP image encoder to extract similar embeddings for any two intermediate adversarial queries. We show that ACPT can detect 7 state-of-the-art query-based attacks with $>99%$ detection rate within 5 shots. We also show that ACPT is robust to 3 types of adaptive attacks.
  arXiv  Detail & Related papers  (2024-08-04T09:53:50Z)
• Graph Anomaly Detection with Noisy Labels by Reinforcement Learning [13.135788402192215]
  We propose a novel framework REGAD, i.e., REinforced Graph Anomaly Detector. Specifically, we aim to maximize the performance improvement (AUC) of a base detector by cutting noisy edges approximated through the nodes with high-confidence labels.
  arXiv  Detail & Related papers  (2024-07-08T13:41:21Z)
• Lazy Layers to Make Fine-Tuned Diffusion Models More Traceable [70.77600345240867]
  A novel arbitrary-in-arbitrary-out (AIAO) strategy makes watermarks resilient to fine-tuning-based removal. Unlike the existing methods of designing a backdoor for the input/output space of diffusion models, in our method, we propose to embed the backdoor into the feature space of sampled subpaths. Our empirical studies on the MS-COCO, AFHQ, LSUN, CUB-200, and DreamBooth datasets confirm the robustness of AIAO.
  arXiv  Detail & Related papers  (2024-05-01T12:03:39Z)
• Advancing Adversarial Robustness Through Adversarial Logit Update [10.041289551532804]
  Adversarial training and adversarial purification are among the most widely recognized defense strategies. We propose a new principle, namely Adversarial Logit Update (ALU), to infer adversarial sample's labels. Our solution achieves superior performance compared to state-of-the-art methods against a wide range of adversarial attacks.
  arXiv  Detail & Related papers  (2023-08-29T07:13:31Z)
• Revisiting and Advancing Fast Adversarial Training Through The Lens of Bi-Level Optimization [60.72410937614299]
  We propose a new tractable bi-level optimization problem, design and analyze a new set of algorithms termed Bi-level AT (FAST-BAT) FAST-BAT is capable of defending sign-based projected descent (PGD) attacks without calling any gradient sign method and explicit robust regularization.
  arXiv  Detail & Related papers  (2021-12-23T06:25:36Z)
• RamBoAttack: A Robust Query Efficient Deep Neural Network Decision Exploit [9.93052896330371]
  We develop a robust query efficient attack capable of avoiding entrapment in a local minimum and misdirection from noisy gradients. The RamBoAttack is more robust to the different sample inputs available to an adversary and the targeted class.
  arXiv  Detail & Related papers  (2021-12-10T01:25:24Z)
• Gaussian MRF Covariance Modeling for Efficient Black-Box Adversarial Attacks [86.88061841975482]
  We study the problem of generating adversarial examples in a black-box setting, where we only have access to a zeroth order oracle. We use this setting to find fast one-step adversarial attacks, akin to a black-box version of the Fast Gradient Sign Method(FGSM) We show that the method uses fewer queries and achieves higher attack success rates than the current state of the art.
  arXiv  Detail & Related papers  (2020-10-08T18:36:51Z)
• Towards Query-Efficient Black-Box Adversary with Zeroth-Order Natural Gradient Descent [92.4348499398224]
  Black-box adversarial attack methods have received special attentions owing to their practicality and simplicity. We propose a zeroth-order natural gradient descent (ZO-NGD) method to design the adversarial attacks. ZO-NGD can obtain significantly lower model query complexities compared with state-of-the-art attack methods.
  arXiv  Detail & Related papers  (2020-02-18T21:48:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.