In this supplementary document, we provide additional materials to supplement our main submission. In Section A, we talk about the societal impacts of our work In Section B, we provide detailed experimental settings as well as further evaluation results on CIFAR-10 and ImageNet. We also provide the comparison with input transformation-based defense methods. In Section D, we give the proofs w.r.t. In Section E, we give the proofs w.r.t. The proofs of Theorem 3 are given in Section F. In Section C, we provide the analysis and evaluation of decision-based attacks. Deep neural networks (DNNs) have been successfully applied in many safety-critical tasks, such as autonomous driving, face recognition and verification, etc. And adversarial samples have posed a serious threat to machine learning systems.

In Section A, we talk about the societal impacts of our work In Section B, we provide detailed experimental settings as well as further evaluation results on CIFAR-10 and ImageNet. Forreal-worldapplications,theDNNmodelaswellas the training dataset, are often hidden from users. Extensive experiments verify our theoretical analysis and showtheeffectiveness ofourdefense methods against several state-of-the-art query-based attacks. On ImageNet, [23] released the ResNet-50 model fine-tuned with Gaussian noise sampled from N(0,0.5I)andwedirectlyadoptit. The experimental results on ImageNet are shown in Figure 3 (a-d).

Machine learning models are vulnerable to adversarial examples. In this paper, we are concerned with black-box adversarial attacks, where only loss-oracle access to a model is available. At the heart of black-box adversarial attack is the gradient estimation problem with query complexity O(n), where n is the number of data features. Recent work has developed query-efficient gradient estimation schemes by exploiting data- and/or time-dependent priors. Practically, sign-based optimization has shown to be effective in both training deep nets as well as attacking them in a white-box setting. Therefore, instead of a gradient estimation view of black-box adversarial attacks, we view the black-box adversarial attack problem as estimating the gradient's sign bits. This shifts the view from continuous to binary black-box optimization and theoretically guarantees a lower query complexity of $\Omega(n/ \log_2(n+1))$ when given access to a Hamming loss oracle. We present three algorithms to estimate the gradient sign bits given a limited number of queries to the loss oracle. Using one of our proposed algorithms to craft black-box adversarial examples, we demonstrate evasion rate experiments on standard models trained on the MNIST, CIFAR10, and IMAGENET datasets that set new state-of-the-art results for query-efficient black-box attacks. Averaged over all the datasets and metrics, our attack fails $3.8\times$ less often and spends in total $2.5\times$ fewer queries than the current state-of-the-art attacks combined given a budget of 10,000 queries per attack attempt. On a public MNIST black-box attack challenge, our attack achieves the highest evasion rate surpassing all of the submitted attacks. Notably, our attack is hyperparameter-free (no hyperparameter tuning) and does not employ any data-/time-dependent prior, the latter fact suggesting that the number of queries can further be reduced.