acceptodds
Under review as a conference paper at ICLR 2027

BAPS: Boundary-Anchored Probabilistic Search for Reliable Decision-Based Attacks against Input-Noise Defenses

Abstract

Randomized input noise causes identical queries to return inconsistent hard labels across repeated calls, making both boundary localization and boundary point selection more difficult. We propose BAPS (Boundary-Anchored Probabilistic Search), which maintains a boundary anchor separately from a set of reliable candidates under the radius constraint. Sequential paired comparisons then allocate raw model queries to resolve uncertain boundary decisions. Once a candidate is selected, it is fixed and tested using 200 fresh draws of defense randomness. Strict attack success requires both and a one-sided 95% lower confidence bound on the attack probability of at least . Across nine CIFAR-10 noise conditions, BAPS achieves an overall strict attack success rate (ASR) of 67.7%, compared with 61.4% for a radius-constrained adaptation of PopSkipJump (PSJ). On ImageNet with ResNet50, BAPS achieves macro-average strict ASRs of 37.6%, 54.6%, 75.1%, 87.4%, and 95.1% at , respectively. Under the pre-specified analysis plan, all 90 paired comparisons of BAPS against SurFree and CGBA remain significant after multiple-comparison correction. At fixed , BAPS's ASR increases from 16.7% to 50.1% as the query budget increases from 5K to 50K. Without model-specific tuning, the same ImageNet configuration achieves 31.8% ASR on ConvNeXt-Tiny at and , compared with 10.8% for CGBA, the strongest baseline evaluated in this setting. Under the evaluated protocols, BAPS improves strict ASR over adapted baselines while maintaining independent final verification.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
adversarial robustness, black-box adversarial attacks, decision-based attacks, stochastic input-noise defenses, probabilistic search

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_5v2UOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes BAPS, a decision-based black-box attack for classifiers with randomized input-noise defenses. Repeated queries to the same input may return inconsistent hard labels. BAPS separates probability-boundary geometry estimation from reliable endpoint selection. It uses sequential paired comparisons around boundary anchors, a radius-constrained candidate archive, and independent 200-draw verification of the final output. Experiments on CIFAR-10 and ImageNet under Gaussian, uniform, and Laplace input noise report improved strict ASR over adapted SurFree/CGBA baselines and mixed results relative to an adapted PSJ baseline.

Critical strengths
  1. The proposed strict ASR criterion is an interesting evaluation perspective. Requiring the final adversarial example to achieve a high attack probability with an explicit confidence lower bound is informative, and could be useful for evaluating attacks against randomized defenses.
Critical weaknesses
  1. The core technical novelty and query-efficiency advantage are not convincingly established. Many ingredients have clear precedents, such as low-frequency priors, local normal estimation, tangent moves, and probabilistic boundary search. The main distinctive choice is to spend repeated queries refining a small number of paired directional comparisons and to maintain a separate reliability archive. The paper does not provide a matched-budget comparison showing that this is better than using the same queries to explore more noisy directions as in HSJA/PSJ-style normal estimators.

  2. The experimental evidence is too tied to the paper’s own strict-ASR protocol and is not broad enough to establish general effectiveness. Almost all attack results are reported only under the paper-specific choice of τ=0.9\tau=0.9, 95% one-sided confidence, and 200 fresh verification draws, without standard ASR, final padvp_{\mathrm{adv}}, distortion/border-distance, or sensitivity to these operating points. It is difficult to tell whether BAPS is generally a better attack or mainly better under its own evaluation criterion. In addition, Gaussian, uniform, and Laplace noise are all variants of independent additive pixel noise, so the paper does not sufficiently test qualitatively different randomized defenses such as random resize/padding, crop/resize, blur/compression, or other stochastic transformations.

Questions for authors
  1. How often does the claimed geometry–reliability mismatch actually occur in practice? Is this decoupling genuinely necessary?

  2. How sensitive is BAPS to its heuristic design choices? 15 DCT directions, DCT scales, h=0.5, 3–7 samples per side, momentum, proposal multipliers, probability/radius gates, and the 7+31 archive screening scheme, they are introduced with limited justification.

  3. The paper explicitly changes PSJ’s process, and many ImageNet runs hit the imposed iteration cap. How much of the observed gap is due to these adaptations rather than the underlying attack method, and can results under a more native PSJ configuration be provided?

  4. Under the stated confidence-sequence formula, α=0.025\alpha=0.025, and a cap of only 3–7 samples per side, the advertised early-stopping condition appears unable to trigger at all?

Reviewer_ktbuOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes a novel decision-based black-box attack called BAPS. The authors study it in the setting of the model defense based on adding input noise. The stochastic hard-label attacks setup is formulated as a search problem under constraints on perturbation radius and attack query budget. The obtained results are validated on CIFAR-10 and ImageNet and compared with existing attacks such as PSJ, SurFree and CGBA across several attack settings.

Critical strengths
  1. Decision-based black-box attacks allow to evaluate model robustness in a more realistic setting than the classical white-box attacks and this paper advances the robustness evaluation results compared to existing methods as demonstrated in Tables 1 and Table 2. Therefore, this paper is valuable for the adversarial robustness field.

  2. The method is evaluated across multiple settings including different datasets (CIFAR10, ImageNet) and attack budgets.

Critical weaknesses
  1. The paper does not consider the targeted attack scenario (perturbing to a pre-defined class rather than any class) which limits the application of the proposed method.

  2. The evaluation is only done for CNN-based architectures. An evaluation with transformer-based architecture would be valuable.

  3. The method provides lower ASR for bigger σ\sigma than an existing method on CIFAR10 (Table 1).

Minor writing issues:

  • The word "equation" is repeated in the line 172.
  • Please clarify what is "shell archive" in the line 220.
Questions for authors
  1. Could you please better clarify in the paper the notation that you use in the definition of Z in the line 161?
Reviewer_STMPOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

Paper addresses an interesting problem of formulating attacks as search label problem (in budget constrained and perturbation radius constraint) settings with goal of increase the attack rate, while assuming an input-noise defence mechanism in place. A BAPS approach is proposed which maintains probability boundary anchors and reliable candidate set, decoupling geometric search from statistical verification of the candidates.

Critical strengths

Overall, the paper is well written, research is nicely motivated and presented. The proposed BAPS algorithm is sound.

Critical weaknesses

I have main concern about the premie of the paper. It formulates an attack mechanism around input noise as defence mechanism, which is one of many defence methods, this limits the generalziation of BAPS.

I have also concerns with the results in Table 1. Only PSJ or SurFree and CBGA are used as the attacks — it would be much stronger statement to compare against other (non-constrained) black-box attack methods, to establish a strong baseline. Secondly, the improved over PSJ is not significant, given PSJ is re-implementation and not original version, doubts BAPS superiority claims.

Questions for authors

Why different implementations of PSJ are used in Table 1 and 2? Why epsilon = 1 chose in Table 1 as default? It would be good discuss effectiveness of PSJ when \sigma = 0.010, it is just coincidence or this is just a trend, this warrants test over 0.020 and higher values.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.