Contract And Conquer: How to Provably Compute Adversarial Examples for a Black-Box Model?

Anna Chistyakova; Mikhail Pautov

cs.LGMar 11, 2026

Contract And Conquer: How to Provably Compute Adversarial Examples for a Black-Box Model?

Authors: Anna Chistyakova, Mikhail Pautov

Organizations: Trusted AI Research Center, RAS · AXXX

Abstract

Black-box adversarial attacks are widely used as tools to test the robustness of deep neural networks against malicious perturbations of input data aimed at a specific change in the output of the model. Such methods, although they remain empirically effective, usually do not guarantee that an adversarial example can be found for a particular model. In this paper, we propose Contract And Conquer (CAC), an approach to provably compute adversarial examples for neural networks in a black-box manner. The method is based on knowledge distillation of a black-box model on an expanding distillation dataset and precise contraction of the adversarial example search space. CAC is supported by the transferability guarantee: we prove that the method yields an adversarial example for the black-box model within a fixed number of algorithm iterations. Experimentally, we demonstrate that the proposed approach outperforms existing state-of-the-art black-box attack methods on ImageNet dataset for different target models, including vision transformers.

Figures & tables

Figure 1: Illustration of the contraction of the adversarial example search space. Given the number $j$ of algorithm iteration, the adversarial example search space on iteration $j$ , namely, $U_{\delta}(x)_{j},$ is the intersection of the $\rho_{j}-$ vicinity of an adversarial example $z_{j}$ with the initial attack search space, $U_{\delta}(x).$ Formally, $U_{\delta}(x)_{j}=U_{\delta}(x)\cap U_{\rho_{j}}(z_{j}).$ The quantity $\rho_{j}$ is defined in Eq. 7 . For each algorithm iteration, the adversarial example search space is represented by the intersection of bold circles.

Figure 2: Schematic representation of the proposed method. Given alternation iteration $j$ and the target model $T$ , we prepare the distillation dataset $\mathcal{D}(S)$ and train the surrogate model $S_{j}$ . Then, $S_{j}$ is attacked at the target point $x$ in the white-box setting, and an adversarial example $z_{j}$ is computed. If $z_{j}$ is transferable to $T,$ algorithm returns $z_{j}$ and stops; otherwise, the adversarial example search space is contracted as shown in Fig. 1 , $(z_{j},T(z_{j}))$ is added to the distillation dataset, and the next instance of the surrogate model, $S_{j+1},$ is obtained.

Method	ASR	AQN	Avg $l_{2}$	Std $l_{2}$	Avg $l_{\infty}$	Std $l_{\infty}$
CAC (ours)	$1.00$	$487.95$	$\underline{35.074}$	$18.833$	$\underline{0.153}$	$0.080$
HopSkipJump $l_{2}$	$1.00$	$500.31$	$48.838$	$29.118$	$0.539$	$0.280$
HopSkipJump $l_{\infty}$	$1.00$	$500.01$	$73.255$	$35.856$	$0.361$	$0.202$
SignOPT	$1.00$	$548.24$	$48.047$	$28.467$	$0.551$	$0.283$
GeoDA	$1.00$	$524.98$	$49.658$	$31.117$	$0.180$	$0.094$

Table 1: Quantitative comparison of attack methods, hard-label setting, the target model is ResNet-50, the dataset is ImageNet.

Method	ASR	AQN	Avg $l_{2}$	Std $l_{2}$	Avg $l_{\infty}$	Std $l_{\infty}$
CAC (ours)	$1.00$	$488.91$	$49.282$	$26.488$	$\underline{0.165}$	$0.091$
HopSkipJump $l_{2}$	$1.00$	$500.34$	$70.122$	$38.343$	$0.685$	$0.318$
HopSkipJump $l_{\infty}$	$1.00$	$500.01$	$106.142$	$48.455$	$0.563$	$0.292$
SignOPT	$1.00$	$557.31$	$74.744$	$44.850$	$0.708$	$0.338$
GeoDA	$1.00$	$540.21$	$65.471$	$40.497$	$0.190$	$0.124$
PAR	$1.00$	$322.38$	$38.751$	$25.745$	$0.889$	$0.233$

Table 2: Quantitative comparison of attack methods, hard-label setting, the target model is ViT-B, the dataset is ImageNet.

Method	ASR	AQN	Avg $l_{2}$	Std $l_{2}$	Avg $l_{\infty}$	Std $l_{\infty}$
CAC (ours)	$1.00$	$489.93$	$\underline{36.396}$	$19.038$	$\underline{0.122}$	$0.068$
SquareAttack $l_{\infty}$	$0.98$	$500.00$	$89.292$	$4.953$	$0.250$	$0.000$
SparseRS	$0.94$	$500.00$	$44.470$	$2.574$	$0.994$	$0.017$

Table 3: Quantitative comparison of attack methods, soft-label setting, the target model is ResNet-50, the dataset is ImageNet.

Method	ASR	AQN	Avg $l_{2}$	Std $l_{2}$	Avg $l_{\infty}$	Std $l_{\infty}$
CAC (ours)	$1.00$	$488.60$	$\underline{41.370}$	$23.579$	$\underline{0.144}$	$0.084$
SquareAttack $l_{\infty}$	$0.26$	$500.00$	$90.103$	$4.602$	$0.250$	$0.000$
SparseRS	$0.79$	$500.00$	$44.335$	$2.444$	$0.993$	$0.017$

Table 4: Quantitative comparison of attack methods, soft-label setting, the target model is ViT-B, the dataset is ImageNet.

Method	ASR	AQN	Avg $l_{2}$	Std $l_{2}$	Avg $l_{\infty}$	Std $l_{\infty}$
CAC (ours)	$1.00$	$291.0$	$\underline{2.675}$	$1.091$	$\underline{0.061}$	$0.025$
HopSkipJump $l_{2}$	$1.00$	$300.07$	$2.704$	$2.634$	$0.174$	$0.161$
HopSkipJump $l_{\infty}$	$1.00$	$310.66$	$3.281$	$3.232$	$0.082$	$0.085$
SignOPT	$0.92$	$288.59$	$3.642$	$3.351$	$0.242$	$0.209$
GeoDA	$0.96$	$300.81$	$3.388$	$3.440$	$0.071$	$0.071$

Table 5: Quantitative comparison of attack methods, hard-label setting, the target model is ResNet-50, the dataset is CIFAR-10.

Method	ASR	AQN	Avg $l_{2}$	Std $l_{2}$	Avg $l_{\infty}$	Std $l_{\infty}$
CAC (ours)	$1.00$	$489.89$	$21.625$	$11.990$	$\underline{0.070}$	$0.044$
HopSkipJump $l_{2}$	$0.99$	$496.30$	$40.160$	$33.460$	$0.417$	$0.281$
HopSkipJump $l_{\infty}$	$1.00$	$500.01$	$60.742$	$40.929$	$0.292$	$0.226$
SignOPT	$0.96$	$532.76$	$40.653$	$33.664$	$0.426$	$0.265$
GeoDA	$0.94$	$604.32$	$25.871$	$23.517$	$0.071$	$0.078$
PAR	$1.00$	$281.56$	$20.526$	$17.515$	$0.645$	$0.236$

Table 6: Quantitative comparison of attack methods, hard-label setting, the target model is ViT-B, the dataset is CIFAR-10.

Method	ASR	AQN	Avg $l_{2}$	Std $l_{2}$	Avg $l_{\infty}$	Std $l_{\infty}$
CAC (ours)	$1.00$	$291.00$	$\underline{2.468}$	$1.075$	$\underline{0.056}$	$0.025$
SquareAttack $l_{\infty}$	$0.82$	$300.00$	$13.028$	$0.637$	$0.250$	$0.000$
SparseRS	$0.96$	$300.00$	$4.371$	$0.348$	$0.920$	$0.065$

Table 7: Quantitative comparison of attack methods, soft-label setting, the target model is ResNet-50, the dataset is CIFAR-10.

Method	ASR	AQN	Avg $l_{2}$	Std $l_{2}$	Avg $l_{\infty}$	Std $l_{\infty}$
CAC (ours)	$1.00$	$489.50$	$\underline{15.745}$	$9.850$	$\underline{0.050}$	$0.037$
SquareAttack $l_{\infty}$	$0.85$	$500.00$	$92.182$	$3.57$	$0.250$	$0.000$
SparseRS	$0.98$	$500.00$	$43.198$	$1.86$	$0.974$	$0.032$

Table 8: Quantitative comparison of attack methods, soft-label setting, the target model is ViT-B, the dataset is CIFAR-10.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Method	Hyperparameters
HopSkipJump $l_{2}$ / $l_{\infty}$	num_samples_for_init = $100$ num_samples_for_grad_est = $100$ max_iter= $100$
SignOPT	num_samples_for_init = $100$ num_samples_for_grad_est = $100$ max_iter = $100$
GeoDA	sub_dim = 150 db_search_steps = 200 bin_search_tol = 0.0001 $\lambda$ = 0.6 $\sigma$ = 0.0002
PAR	initial_patch_size = $56$ min_patch_size = $7$
AdvViT	num_samples_for_init = $100$ init_attempts_extra = $100$ patch_num = $14$ dim_size = $4$ $\alpha$ = $4.0$ K_sign = $100$
SquareAttack $l_{\infty}$	$\varepsilon=\frac{32}{255}$ p_init = $0.05$

Appendix

Table 9: Hyperparameters of baseline methods

Adversarial Attacks

Adversarial attacks exploit crafted inputs, poisoned data, or system interactions to manipulate AI predictions, behavior, privacy, or reliability.

See all 447 papers

Reinforcement Learning Inspired Black-box Adversarial Attacks for Computer Vision
Sep 21, 2026Florian Krone, Elena Hoemann, Sven HallerbachAdversarial Attacks Adversarial Robustness
Institute for AI Safety and Security German Aerospace Center (DLR) Sankt Augustin, Germany
Almost for Free: Crafting Adversarial Examples with Convolutional Image Filters
May 1, 2026Alexander Warnecke, Konrad RieckAdversarial Attacks Adversarial Examples
1BIFOLD & TU Berlin
Attack logics, not outputs: Concept-based Property Attacks for Shortcut Elimination in Neural Networks
Oct 26, 2026Raik Dankworth, Felix Mächtle, Thomas Eisenbarth +1Adversarial Attacks Adversarial Robustness
Institute of Software Engineering and Programming Languages University of Luebeck · Institute of IT Security University of Luebeck

Sep 21, 2026J/K move · Enter open · S save

Reinforcement Learning Inspired Black-box Adversarial Attacks for Computer Vision

Florian Krone, Elena Hoemann, Sven Hallerbach

Institute for AI Safety and Security German Aerospace Center (DLR) Sankt Augustin, Germany

Adversarial Attacks Adversarial Robustness Adversarial Perturbations Black-Box Adversarial Attacks

Open paper AskPDF arXiv

Neural networks, both convolution or transformer based, are essential for modern computer vision systems. However, they are vulnerable to small perturbations, almost imperceptible to humans, which significantly alter the model's prediction. These adversarial attacks are often considered to be a significant threat to the implementation of neural networks in safety-critical applications. Most attacks utilize the white-box threat model and therefore require full access to the target model, making them unrealistic to use in practice. We propose a novel approach under the more realistic black-box threat model that utilizes concepts from reinforcement learning to optimize perturbations with a non-differentiable target model. Reinforcement learning algorithms have already been optimized to be query efficient, making them an ideal starting point when designing black-box adversarial attacks. We show the success of our reinforcement learning inspired black-box adversarial attack (RIBA) in generating adversarial perturbations using only a small number of queries to the target model, by comparing it to state of the art attacks on different models on the Cifar10 and ImageNet data sets. RIBA takes

25.4\%

fewer median queries to generate attacked images against a ResNet-18 on Cifar10 and

22.5\%

fewer median queries to fool a Vit-B/16 model on ImageNet. Additionally, we demonstrate that RIBA can match the performance of white-box attacks on an adversarially trained model.

Abstract

Adversarial Attacks

Explore similar work

Reinforcement Learning Inspired Black-box Adversarial Attacks for Computer Vision

Almost for Free: Crafting Adversarial Examples with Convolutional Image Filters

Attack logics, not outputs: Concept-based Property Attacks for Shortcut Elimination in Neural Networks