# Certifiable Black-Box Attacks with Randomized Adversarial Examples: Breaking Defenses with Provable Confidence

arXiv: https://arxiv.org/abs/2304.04343 · HTML: https://mlsanity.com/paper/2304.04343/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 77 of its 106 references that are in the map.
- First posted on arXiv 10 Apr 2023.

## Builds on (most cited first, 30 of 77)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Aggregated Residual Transformations for Deep Neural Networks](https://mlsanity.com/paper/1611.05431/) (2016)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [Ensemble Adversarial Training: Attacks and Defenses](https://mlsanity.com/paper/1705.07204/) (2017)
- [Universal adversarial perturbations](https://mlsanity.com/paper/1610.08401/) (2016)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [VoxCeleb: a large-scale speaker identification dataset](https://mlsanity.com/paper/1706.08612/) (2017)
- [Square Attack: a query-efficient black-box adversarial attack via random search](https://mlsanity.com/paper/1912.00049/) (2019)
- [Distillation as a Defense to Adversarial Perturbations against Deep Neural Networks](https://mlsanity.com/paper/1511.04508/) (2015)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [ECAPA-TDNN: Emphasized Channel Attention, Propagation and Aggregation in TDNN Based Speaker Verification](https://mlsanity.com/paper/2005.07143/) (2020)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Countering Adversarial Images using Input Transformations](https://mlsanity.com/paper/1711.00117/) (2017)
- [Black-box Adversarial Attacks with Limited Queries and Information](https://mlsanity.com/paper/1804.08598/) (2018)
- [Feature Squeezing: Detecting Adversarial Examples in Deep Neural Networks](https://mlsanity.com/paper/1704.01155/) (2017)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Decision-Based Adversarial Attacks: Reliable Attacks Against Black-Box Machine Learning Models](https://mlsanity.com/paper/1712.04248/) (2017)
- [Evading Defenses to Transferable Adversarial Examples by Translation-Invariant Attacks](https://mlsanity.com/paper/1904.02884/) (2019)
- [SpeechBrain: A General-Purpose Speech Toolkit](https://mlsanity.com/paper/2106.04624/) (2021)

## Built on by (most cited first, 5 of 5)

- [Learning Robust and Privacy-Preserving Representations via Information Theory](https://mlsanity.com/paper/2412.11066/) (2024)
- [RDI: An adversarial robustness evaluation metric for deep neural networks based on model statistical features](https://mlsanity.com/paper/2504.18556/) (2025)
- [PLRV-O: Advancing Differentially Private Deep Learning via Privacy Loss Random Variable Optimization](https://mlsanity.com/paper/2509.06264/) (2025)
- [Low-Cost Hard-Label Adversarial Attack with Theoretical Foundations](https://mlsanity.com/paper/2601.14300/) (2026)
- [What the Eyes See, the LLMs Miss: Exploiting Human Perception for Adversarial Text Attacks](https://mlsanity.com/paper/2606.09700/) (2026)

## Abstract (arXiv)

Black-box adversarial attacks have demonstrated strong potential to compromise machine learning models by iteratively querying the target model or leveraging transferability from a local surrogate model. Recently, such attacks can be effectively mitigated by state-of-the-art (SOTA) defenses, e.g., detection via the pattern of sequential queries, or injecting noise into the model. To our best knowledge, we take the first step to study a new paradigm of black-box attacks with provable guarantees -- certifiable black-box attacks that can guarantee the attack success probability (ASP) of adversarial examples before querying over the target model. This new black-box attack unveils significant vulnerabilities of machine learning models, compared to traditional empirical black-box attacks, e.g., breaking strong SOTA defenses with provable confidence, constructing a space of (infinite) adversarial examples with high ASP, and the ASP of the generated adversarial examples is theoretically guaranteed without verification/queries over the target model. Specifically, we establish a novel theoretical foundation for ensuring the ASP of the black-box attack with randomized adversarial examples (AEs). Then, we propose several novel techniques to craft the randomized AEs while reducing the perturbation size for better imperceptibility. Finally, we have comprehensively evaluated the certifiable black-box attacks on the CIFAR10/100, ImageNet, and LibriSpeech datasets, while benchmarking with 16 SOTA black-box attacks, against various SOTA defenses in the domains of computer vision and speech recognition. Both theoretical and experimental results have validated the significance of the proposed attack. The code and all the benchmarks are available at urlhttps://github.com/datasec-lab/CertifiedAttack.