Introduction
Adversarial attacks—tiny, intentional perturbations that fool machine learning models—pose a significant security threat. In real-world "black-box" scenarios, attackers often only have access to a model's final hard-label output (e.g., "Cat" or "Dog") rather than internal gradients or probability scores. Current decision-based attacks typically rely on random search and query-intensive techniques like binary search to find the exact distance to a decision boundary. This process is highly inefficient, often exhausting query budgets before a successful perturbation is found.
The Approximation Decision Boundary Approach (ADBA) addresses this by ditching the requirement for precise boundary calculations. By utilizing a statistical median-search strategy (ADBA-md), the algorithm can compare perturbation directions in significantly fewer queries, achieving higher success rates with 30-50% fewer queries than current state-of-the-art methods.
Methodology: Approximating the Boundary
ADBA shifts the focus from calculating the exact boundary to approximating it just enough to make a directional decision.
- Approximation Decision Boundary (ADB): Instead of high-precision calculations (e.g., 0.001), ADBA uses a rough estimate. If direction A is adversarial at this estimate and direction B is not, the algorithm immediately identifies A as the superior direction without further queries.
- ADBA-md (Median-Search): By analyzing the probability distribution of decision boundaries across various models, the authors discovered that using the median value of this distribution as the approximation point maximizes the likelihood of differentiating two directions. This provides the most "bits" of information per query.
- Query Efficiency: While standard binary search might require ~10 queries for accuracy, the ADBA-md approach requires only 4 queries on average to determine which of two directions is superior.
Experimental Results
The researchers evaluated ADBA against leading attacks (OPT, SignOPT, HSJA, and RayS) using ImageNet, MNIST, and CIFAR-10 datasets across six diverse architectures: VGG19, ResNet50, Inception-V3, ViT-B32, DenseNet161, and EfficientNet-B0.
As shown in the performance curves above, ADBA variants maintain a ~90% success rate even with a tight budget of 1,000 queries, while competing methods often drop below 30%. Across all ImageNet models, ADBA-md achieved a success rate of over 99.3% within a 10,000-query budget.
On the VGG19 model, ADBA-md required an average of 197.6 queries, compared to 470.1 for the previous state-of-the-art, RayS. Overall, ADBA-md reduced the average query count by 30-40% and the median query count by approximately 50% across the board.
Key Insights
- Precision vs. Progress: In the early stages of an attack, exact boundary knowledge is unnecessary. ADBA treats the boundary as a stochastic variable, prioritizing directional progress over measurement precision.
- Architecture Agnosticism: Surprisingly, the statistical distribution of decision boundaries is remarkably consistent across different neural network architectures, from CNNs to Vision Transformers. This allows the "median" discovered on one model to work effectively on others without recalibration.
Conclusion and Future Work
ADBA demonstrates that statistical approximation can drastically improve the efficiency of black-box adversarial attacks. While this study focused on $l_\infty$ norm constraints and untargeted attacks, future research may explore how these statistical distributions behave under different distance metrics (like $l_2$ norms) and how the logic applies to targeted attacks. Additionally, as attacks become more query-efficient, defensive strategies may need to evolve to detect the specific statistical patterns associated with median-search queries.
Summary updated