BRP: Query-Efficient Block Revert Patch for Decision-Based Black-Box Adversarial Attack

Abstract

Adversarial patches pose a serious threat to deep neural networks, as small localized perturbations can decisively control model predictions. In real-world deployments, the decision-based black-box setting is the most realistic and challenging threat model, where attackers observe only the predicted labels. Designing adversarial patch attacks under this setting is of substantial real-world significance for rigorously testing model robustness under realistic black-box conditions. However, adversarial patch attacks in the decision-based setting remain largely underexplored. Existing methods often suffer from low query efficiency and require large patch areas, which significantly limit their practical applicability. We propose Block Revert Patch (BRP), a novel reverse construction method for query-efficient adversarial patch generation. Instead of adding perturbations, BRP formulates patch generation as a pixel-block reversion problem and employs a two-stage process to progressively refine the patch. Specifically, the single-block revert test stage uses a sliding window to temporarily revert individual blocks and collect those whose reversion maintains the adversarial effect. The global revert optimization stage then searches for an optimal combination of pixel-blocks from this set, further reducing the patch size. By iteratively alternating between these two stages, BRP progressively refines the patch in a coarse-to-fine manner. Experiments show that BRP significantly reduces patch size and query cost compared to state-of-the-art decision-based attacks, offering a strong and practical approach for evaluating model vulnerability in adversarial settings.