Low-Cost Hard-Label Adversarial Attacks with Theoretical Foundations

Researchers propose a low-cost hard-label black-box adversarial attack framework with theoretical guarantees; experiments show that it outperforms existing SOTA hard-label attacks in both success rate and efficiency, with the advantage particularly evident under low query budgets. Hard-label attacks rely only on the model's top-1 prediction; the paper establishes a unified theoretical framework that interprets existing sign-flipping hard-label attacks as approximations of the true gradient sign, and proves that their zero-query initialization has higher cosine similarity with the true gradient sign than a random baseline, and that the Pattern-Driven Optimization (PDO) algorithm has significantly lower query complexity than baseline search methods. Experiments cover standard and adversarially trained models on CIFAR-10, ImageNet, and ObjectNet, commercial APIs, and CLIP models, and maintain generalization on ImageNet-C, PathMNIST biomedical images, and dense prediction tasks such as segmentation. The method can also bypass the stateful defense Blacklight, with a detection rate of 0%.