Contract And Conquer: How to Provably Compute Adversarial Examples for a Black-Box Model?
Anna Chistyakova, Mikhail Pautov · 2026
Read Contract And Conquer: How to Provably Compute Adversarial Examples for a Black-Box Model? by Anna Chistyakova, Mikhail Pautov (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-10689.txt.
Introduction
Anna Chistyakova and Mikhail Pautov present Contract And Conquer, a method to compute adversarial examples for a black-box neural network with a guarantee. Black-box attacks probe robustness, but normally cannot promise an example exists for a given model. Their approach distills the black-box model on an expanding dataset while contracting the search space precisely. A transferability guarantee shows an adversarial example is found within a fixed number of iterations. On ImageNet it beat leading black-box attack methods across target models, including vision transformers.
Catalog record
| CREATOR | Anna Chistyakova, Mikhail Pautov |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38816 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.10689
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Contract And Conquer: How to Provably Compute Adversarial Examples for a Black-Box Model? Anna Chistyakova, Mikhail Pautov 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. † † affiliationnotice: Equal contribution 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. 1 Introduction Evaluating and enhancing the robustness of neural networks to malicious perturbations of input data, called adversarial attacks, is crucial in safety-critical applications, such as medicine or autonomous systems. It has long been known that a small, often imperceptible perturbation of image ( 23 ) or a minor paraphrase of an input prompt ( 82 ) can cause a desired change in the output of the corresponding model. It is noteworthy that the effectiveness of adversarial attacks is experimentally confirmed in the black-box settings, when the attacker has limited access to the model, namely, when they can query the model and receive its output in a fixed format ( 52 ; 41 ; 25 ) . 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. Starting from the seminal work ( 60 ) , the majority of research in the field of adversarial machine learning has focused on developing methods to compute adversarial examples and empirical approaches to defend the models against them. Mainly, the methods of computing adversarial examples are based on utilizing the information about the target model’s outputs and gradients ( 8 ; 40 ; 4 ; 49 ) or its estimation ( 25 ; 12 ; 14 ; 27 ) . In parallel, empirical defense methods are mainly based on adversarial training ( 40 ; 5 ) , where the model is trained on generated adversarial examples, gradient regularization ( 55 ) , calibration ( 59 ) , or weight perturbation ( 71 ; 74 ) . It is worth mentioning that the existence of an arms race between empirical defenses and adversarial attacks is concerning for security-critical applications: specifically, it can not be guaranteed that recently developed empirical defense mechanisms will remain effective against novel attack methods, and vice versa. Thus, the effectiveness of the application of empirical methods from adversarial machine learning to evaluate the robustness in safety-critical settings is questionable. More than that, a variety of regulatory acts for artificial intelligence systems are in the process of development today, for example, the EU AI Act or the US National AI Initiative Act. These frameworks, among other things, are designed to develop standards of robustness of machine learning algorithms and services to adversarial attacks. As a consequence, to deploy a machine learning system in a specific setting, one will have to verify that it complies with the aforementioned standards. To ground the evaluation of the resilience of machine learning methods to adversarial attacks, it may be reasonable to focus on certified robustness methods. Instead of relying on heuristics used in empirical defense approaches, certified robustness methods aim to provide mathematical guarantees about a model’s behavior when its input is subjected to a certain perturbation. The methods of certified robustness are usually based on randomized smoothing ( 15 ; 50 ; 63 ) , set propagation techniques ( 24 ; 43 ) , convex relaxation ( 3 ; 31 ) , or probabilistic certification ( 69 ; 51 ; 22 ) . These approaches can yield sample-level or population-level guarantees that no adversarial example exists, given the type of perturbation and the perturbation budget. Unfortunately, certified robustness comes at a cost of computationally expensive inference ( 15 ) , may require significant changes to both training and inference, limit available model architectures ( 17 ) , or may lead to a notable performance degradation of the certifiably robust model. Aforementioned drawbacks are among the ones that limit the embedding of certified robustness into the state-of-the-art machine learning services: for example, an integration of randomized smoothing defense into medical diagnostics or into digital services that mark harmful content may lead to a significant degradation of performance on benign input data or severely slow down the system. As a consequence, to both retain practical effectiveness and to align with the upcoming AI regulatory acts, the developers will probably seek alternatives to certified robustness. At the same time, a complementary research question arises: how to guarantee that the given black-box machine learning is not robust? Specifically, a method to prove that the given model is not robust might be an important tool for the assessment of robustness, especially from the perspective of compliance with the prospective standards. In this paper, we focus on this research question and propose Contract And Conquer (CAC), an iterative method to compute adversarial examples for black-box models with convergence guarantees. By design, CAC is an alternation of two processes: (i) knowledge distillation ( 29 ) of the target black-box target model by a small surrogate model and (ii) a white-box adversarial attack on a surrogate model within a vicinity of the target input point. Intuition behind CAC is simple: knowledge distillation forces the surrogate model to replicate the predictions of the target model in the closed vicinity of target point, where a white-box attack on the surrogate model is used to craft adversarial examples; careful alternation of these operations, together with small contraction of the vicinity of the target point, yields an upper bound on the number of alternations needed to compute an adversarial example for the black-box target model. Our contributions are summarized as follows: • A novel iterative transfer-based