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, while most others have a negligible effect. 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 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://anonymous.4open.science/status/SAR-436.