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

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.

Key Contributions

• CAC algorithm: iterative surrogate-model distillation combined with adversarial search-space contraction for provable black-box adversarial example generation
• Transferability guarantee proving CAC finds an adversarial example for the black-box target within a fixed number of algorithm iterations
• Empirical SOTA performance over existing black-box attack methods on ImageNet across multiple architectures including vision transformers

🛡️ Threat Analysis

Details

Similar Papers