Bias in Zeroth-Order Normal Estimation for Decision-Based Attacks

Decision-based image attacks commonly rely on zeroth-order (ZO) Monte Carlo probing to estimate decision-boundary normals and iteratively refine adversarial perturbations to minimize the $\ell_2$ norm. We theoretically analyze and empirically demonstrate an intrinsic inefficiency arising from heterogeneous input sensitivity, where only a small subset of coordinates strongly affects the target model’s predictions. Empirically, with one-bit feedback and a limited query budget, updates on low-sensitivity coordinates are overwhelmed by initialization and sampling noise, preventing their perturbations from exhibiting consistent improvement. By modeling ZO refinement as a stochastic dynamical system, we formally characterize its asymptotic behavior: the optimization enters a stationary regime, where the perturbation aligns (in expectation) with the normal and its coordinate-wise magnitudes encode a local sensitivity ranking. However, this stationarity does not generally yield $\ell_2$-optimal perturbations under nonlinear boundaries. Building on this observation, we propose a novel and effective algorithm, Sensitivity-Aware Rescaling (SAR), that leverages this sensitivity signal to infer an importance map from the current best perturbation, then progressively suppresses low-importance regions through a coarse-to-fine schedule to reduce the $\ell_2$ norm. Extensive experiments show that SAR achieves consistent improvements in perturbation norm, attack success rate, and visual imperceptibility. The code is available at https://github.com/Flyingssheep/SAR.

Decision-based adversarial attacks receive only the model’s final predicted label after each query. From this extremely limited information, they must construct a full noise image, deciding which way each pixel should move and how far it should move. We show that the classic “small-step probing” strategy used to estimate these directions is inherently noisy: under limited queries, only a small set of important pixels receives reliable guidance, while most less important pixels are dominated by random fluctuations. This means unnecessary perturbation often remains in pixels that do not meaningfully help the attack. Our key observation is that important pixels tend to move farther, so the magnitude of the current perturbation naturally encodes pixel importance. Using this signal, we build an importance map and propose Sensitivity-Aware Rescaling (SAR), which suppresses noise in less important regions and reallocates perturbation strength more effectively. As a result, SAR produces smaller, less visible adversarial perturbations and improves attack performance under the same query budget.