Research map / Adversarial robustness and security / Black-box and transfer attacks
ADBA: Approximation Decision Boundary Approach for Black-Box Adversarial Attacks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ADBA, a hard-label random-search black-box attack that compares perturbation directions using an approximation decision boundary instead of exact binary search, with ADBA-md choosing the distribution median as the boundary to need about four queries per comparison.
Problem
Decision-based (hard-label) black-box adversarial attacks need many queries because they use query-intensive binary search to find exact decision boundaries for each candidate perturbation direction.
Approach
Two perturbation directions can be compared without knowing their exact decision boundaries: if an approximation decision boundary fools one direction but not the other, the successful one is superior. ADBA-md sets the approximation boundary to the median of the estimated boundary distribution, so each comparison succeeds with probability 1/2 and takes about 4 queries on average.
Key results
- ADBA-md reaches 99.3%-100% attack success rate across six ImageNet classifiers with an average of 197.6 to 685.6 queries (median 115 to 273), versus RayS at 470.1 to 1243.5 average queries.
- ADBA-md needs about 4 queries on average to differentiate a pair of perturbation directions by design, versus about 10 for RayS's binary search to reach 0.001 accuracy, a roughly 2.5x reduction.
- On CIFAR-10 and MNIST, ADBA-md uses the ImageNet-estimated distribution parameters without re-estimation and achieves the lowest average and median query counts among the compared attacks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ADBA-md instead of RayS | ImageNet decision-based untargeted attacks · ImageNet test, six target models | average queries: 470.1 -> 197.6 (VGG19); 1243.5 -> 685.6 (ResNet50); 672.2 -> 418.3 (Inception-V3); 1005.1 -> 651.9 (ViT-B32); 733.6 -> 4 | Helped |
| Use ADBA-md instead of RayS | ImageNet decision-based untargeted attacks · ImageNet test, six target models | attack success rate: 100% vs 100% (VGG19); 98.8% -> 99.3% (ResNet50); 98.8% -> 99.7% (Inception-V3); 98.8% -> 99.8% (ViT-B32); 99.1% -> 99.7% | Mixed |
| Use ADBA-md instead of RayS | CIFAR-10 attack with a 7-layer CNN · CIFAR-10 | average queries: 813.3 -> 482.3 | Helped |
| Use ADBA-md instead of RayS | MNIST attack with a 7-layer CNN · MNIST | average queries: 697.4 -> 504.6 | Helped |
| Use the median-based ADB search instead of midpoint search (ablation) | ADBA · ImageNet test, six target models | average queries: 237.3 -> 197.6 (VGG19); 769.3 -> 685.6 (ResNet50); 461.3 -> 418.3 (Inception-V3); 768.4 -> 651.9 (ViT-B32); 485.7 -> 457 | Helped |
| Continue comparing the current best direction against the better candidate (ablation) | ADBA (ADBA-CCM variant) · ImageNet test, six target models | average queries: 237.3 -> 252.9 (VGG19); 769.3 -> 843.1 (ResNet50); 461.3 -> 511.7 (Inception-V3); 768.4 -> 909.4 (ViT-B32); 485.7 -> 535 | Hurt |
| Continue comparing the current best direction against the better candidate (ablation) | ADBA (ADBA-CCM variant) · ImageNet test, six target models | attack success rate: 100% -> 100% (VGG19); 97.9% -> 97.1% (ResNet50); 99.4% -> 99.1% (Inception-V3); 98.8% -> 98.2% (ViT-B32); 99.2% -> 98.7% | Hurt |
Surprising findings
- ADBA-md requires more search iterations than ADBA yet uses fewer total queries, because each iteration costs fewer queries.
- Continuing to compare the current best direction against the new candidates (ADBA-CCM) increases queries and lowers success rate, so it is skipped.
Limitations
- The 4-query expectation relies on an independence assumption between the decision boundaries of the two directions, which the authors acknowledge may not hold, so the actual query count may differ.
- The boundary distribution parameters were estimated only on ResNet50 with ImageNet, and generality was checked on only two extra datasets.
- Evaluation is limited to l-infinity untargeted attacks with a fixed epsilon and query budget.
Experimental setup
Datasets: ImageNet CIFAR-10 MNIST
Benchmarks: ImageNet CIFAR-10 MNIST
Metrics: attack success rate average queries median queries
Baselines: OPT SignOPT HSJA RayS
Builds on: RayS Boundary Attack OPT Sign-OPT HSJA
Closest papers by meaning
- Decision-Based Adversarial Attacks: Reliable Attacks Against Black-Box Machine Learning Models (ICLR 2018 · similarity 0.90)
- TtBA: Two-third Bridge Approach for Decision-Based Adversarial Attack (ICML 2025 · similarity 0.88)
- Efficient Black-box Adversarial Attacks via Bayesian Optimization Guided by a Function Prior (ICML 2024 · similarity 0.87)
- Mind the Gap: Detecting Black-box Adversarial Attacks in the Making through Query Update Analysis (CVPR 2025 · similarity 0.85)
- Understanding the Robustness of Randomized Feature Defense Against Query-Based Adversarial Attacks (ICLR 2024 · similarity 0.85)
- GSBA$^K$: $top$-$K$ Geometric Score-based Black-box Attack (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.