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

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 $\Vert x^{\ast }-x_0{\Vert }_2\le ϵ$ and a one-sided 95% lower confidence bound on the attack probability of at least $0.9$. 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 $ϵ\in \{5,10,20,30,40\}$, 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 $ϵ=5$, 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 $ϵ=5$ and $Q=20,000$, 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.