On the Effectiveness of Small Input Noise for Defending Against Query-based Black-Box Attacks

Since we deal with adversarial attacks on the image classification task throughout the paper, we briefly explain adversarial attacks on the image classification task in this section.

Suppose that a neural network $f({\bm{x}})$ classifies an image ${\bm{x}}$ among total $N$ classes and returns a class-wise probability vector ${\bm{y}}=[y_{1},...,y_{N}]$ for ${\bm{x}}$. For notational convenience, we also denote the probability of $i^{th}$ class (i.e., $y_{i}$) as $f({\bm{x}})_{i}$ and the top-1 class index as $h({\bm{x}})=\operatorname*{arg\,max}_{i\in C}y_{i}$, where $C=\{1,...,N\}$.

In a black-box threat model, an adversary has a clean image ${\bm{x}}_{0}$ whose class index is $c_{0}$ and wants to generate an adversarial example $\hat{{\bm{x}}}={\bm{x}}_{0}+\bm{\delta}$ to fool a target model $f$. In the following, we denote the adversarial example at $t^{th}$ step in an iterative attack algorithm as $\hat{{\bm{x}}}_{t}=\bm{x}_{0}+\bm{\delta}_{t}$. The adversary should generate an adversarial example within a perturbation norm budget $\epsilon$ and query budget $Q$. If we let $q$ be the number of queries used to make $\bm{\delta}_{t}$, then we can write the adversary’s objective as follows:

where $\ell({\bm{x}})=f({\bm{x}})_{c_{0}}-\max_{c\neq c_{0}}f({\bm{x}})_{c}$ for untargeted attacks and $\ell({\bm{x}})=\max_{c\neq\hat{c}}f({\bm{x}})_{c}-f({\bm{x}})_{\hat{c}}$ for targeted attacks with target class index $\hat{c}$. Since decision-based attacks cannot obtain $\ell({\bm{x}})$, they have a different objective for untargeted attacks as follows:

Unless otherwise noted, in this paper, we use $p=2$ and focus on untargeted attacks because it is more challenging for defenders. Besides, we assume that each pixel value is normalized into $[0,1]$.

Query-based attacks can be largely divided into score-based and decision-based attacks according to the available type of output of the target model (class-wise probabilities for score-based attacks and the top-1 class index for decision-based attacks). On the other hand, query-based attacks can be categorized into optimization-based attacks and local search-based attacks. Optimization-based methods optimize an adversary’s objective loss with estimated gradients of the loss with respect to $\hat{{\bm{x}}}_{t}$. In contrast, local search-based attacks repeatedly update an image according to how the model’s output changes after adding a small perturbation.

In the following, we briefly introduce various query-based attacks used in this paper.

Bandit optimization with priors (Bandit-TD). Ilyas et al. [21] observe that the image gradients in successive steps of an iterative attack have strong correlations. In addition, they find that the gradients of surrounding pixels also have correlations. Bandit-TD exploits this information as priors for efficient gradient estimation.

Simple Black-box Attack (SimBA & SimBA-DCT). For each iteration, SimBA [17] samples a vector ${\bm{q}}$ from a pre-defined set Q and modify the current image $\hat{{\bm{x}}}_{t}\textrm{ with }\hat{{\bm{x}}}_{t}-{\bm{q}}$ and $\hat{{\bm{x}}}_{t}+{\bm{q}}$ and updates the image in the direction of decreasing ${\bm{y}}_{c_{0}}$. Inspired by the observation that low-frequency components make a major contribution to misclassification [16], SimBA-DCT exploits DCT basis in low-frequency components for query-efficiency.

Boundary Attack (BA). BA [5] updates $\hat{{\bm{x}}}_{t}$ on the decision-boundary so that the perturbation norm gradually decreases via random walks while misclassification is maintained.

Sign-OPT. Cheng et al. [10] treat a decision-based attack as a continuous optimization problem of the nearest distance to the decision boundary. They use the randomized gradient-free method [29] for estimating the gradient of the distance. Cheng et al. [11] propose Sign-OPT, which uses the expectation of the sign of gradient with random directions to estimate the gradients efficiently without exhaustive binary searches.

Hop Skip Jump Attack (HSJA). Chen et al. [7] improve BA with gradient estimation. For each iteration of HSJA, it finds an image on the boundary with a binary search algorithm, and estimates the gradients, and calculates the step-size towards the decision boundary.

GeoDA. Rahmati et al. [34] propose a geometry-based attack that exploits a geometric prior that the decision boundary of the neural network has a small curvature on average near data samples. By linearizing the decision boundary in the vicinity of samples, it can efficiently estimate the normal vector of the boundary, which helps to reduce the number of required queries for generating adversarial examples.

As Dong et al. [14] observe that randomization is important for effective defense against query-based attacks, we focus on randomization-based defenses among various defense methods. In what follows, we briefly explain three randomization-based defenses along with PGD-adversarial training.

Random Self-Ensemble (RSE). RSE [26] adds Gaussian noise with $\sigma_{\textrm{inner}}=0.1$ to the input of each convolutional layer, except for the first convolutional layer where $\sigma_{\textrm{init}}=0.2$ is used. To stabilize the performance, they use an ensemble of multiple predictions for each image.

Parametric Noise Injection (PNI). He et al. [20] propose a method to increase the robustness of neural networks by adding trainable Gaussian noise to the activation or weight of each layer. They introduce learnable scale factors of noise and allow them to be learned with adversarial training.

Random Resizing and Padding (R&P). Xie et al. [39] propose a random input transform-based method. In front of network inference, it applies random resizing and random padding to its input sequentially, making adversaries obtain noisy gradients. It can be easily applied to a pre-trained model, but it increases total computational time due to the enlarged input image.

PGD-Adversarial Training (PGD-AT). Madry et al. [27] propose PGD-adversarial training which trains a model with adversarial examples generated by Projected Gradient Descent (PGD) [27]. Unlike other defenses that are ineffective against adaptive attacks, it is well known that PGD-AT provides strong defense against a variety of white-box attacks.

To defend against query-based black-box attacks, we add Gaussian noise with a sufficiently small $\sigma$ to the input as follows.

For an adversary, since the exact value of $\bm{\eta}$ is unknown, there are multiple possible output values for any ${\bm{x}}$, so $f_{\bm{\eta}}$ is a random process. In what follows, we will explain how this transform introduces tremendous difficulty in both gradient estimation and local search in query-based black-box attacks.

In this subsection, we will explain how small Gaussian input noise can disturb the gradient estimation in optimization-based attacks. We first look at defense against score-based attacks and then deal with decision-based attacks.

The core of optimization-based attacks is an accurate estimation of $\nabla\ell({\bm{x}})$, which needs to be approximated with finite difference because of the black-box setting. For instance, the gradient can be estimated as $\tilde{{\bm{g}}}$ by Random Gradient-Free method [29] as follows.

Conceptually, by introducing small Gaussian noise into input, $\tilde{{\bm{g}}}$ can greatly differ from the true gradient $\nabla\ell$ as shown in Fig. 1.

To illustrate it more formally, let us represent $\bm{\eta}$ by replacing it with $\bm{\eta}({\bm{x}})$ to clarify $\bm{\eta}$ depends on both time and ${\bm{x}}$. Suppose $f_{\bm{\eta}({\bm{x}})}^{*}$ is a sample function of the random process $f_{\bm{\eta}({\bm{x}})}({\bm{x}})$ at some time. Then, this function is noisy with regard to ${\bm{x}}$ because of $\bm{\eta}({\bm{x}})$. We also assume that $\ell^{*}$ is derived from $f_{\bm{\eta}({\bm{x}})}^{*}$, then unless $\mathrm{Var}[\ell^{*}({\bm{x}}+{\bm{u}})]$ is extremely small, $\ell^{*}$ is discontinuous and non-differentiable, and thus, $\nabla\ell^{*}$ does not exist. Therefore, the estimated gradient using finite differences does not converge to the target gradient $\nabla\ell$. For example, simplifying the problem, if $f$ is a one-dimensional function $\mathbb{R}\rightarrow\mathbb{R}$ and sampled $\eta(1.000)=0.08$ and $\eta(1.001)=-0.03$ then, the sampled function values $f(x+\eta(x))$ at $x=1.000$ and $x=1.001$ become $f(1.080)$ and $f(0.9701)$, respectively. Therefore, if the variance of $f$ is large, the sample function becomes more noisy.

In decision-based attacks, $\hat{{\bm{x}}}_{t}$ is likely to be in the vicinity of the decision boundary. Therefore, even small noise can move $\hat{{\bm{x}}}_{t}$ across the boundary so that the output is changed. The estimated gradient through erroneous predictions hinders the generation of adversarial examples. We illustrate the working principle of SND against decision-based attacks in supplementary material. Besides, the binary search algorithm, which is widely used to calculate the distance to the decision boundary [7, 11], can make a larger error due to $\bm{\eta}$. Therefore, algorithms such as HSJA, which assume that $\hat{{\bm{x}}}$ is near the decision boundary, are likely to work incorrectly.

Local search-based attacks try to update the image in the direction that decreases the adversarial objective loss. However, since the output is unreliable due to noise, this becomes similar to random motion. Suppose an adversary recognizes that the attack objective loss decreases for $\hat{\bm{x}}_{t}+\bm{q}$, where $\bm{q}$ is a perturbation, and updates $\hat{\bm{x}}_{t+1}$ as $\hat{\bm{x}}_{t}+\bm{q}$. However, since the actually evaluated input of $f$ is $\hat{\bm{x}}_{t}+\bm{q}+\bm{\eta}$, where $\bm{\eta}\sim\mathcal{N}(\bm{0},\sigma^{2}\bm{I})$, the attack objective loss might increase at the originally intended input $\hat{\bm{x}}_{t}+\bm{q}$. This prediction error makes the attack algorithm stuck in the iterative process and prevents generating adversarial examples.

Solid research for adversarial defense requires evaluating the defense ability against adaptive attacks that exactly know the working principle of the defense [6]. Athalye et al. [1] show that randomization-based defense such as R&P can be circumvented through the Expectation Over Transform (EOT) technique [2]. The EOT technique approximates the gradient at each gradient descent step by averaging gradients w.r.t. several samples transformed by randomization-based defenses. In the black-box setting, the gradients w.r.t. an input cannot be obtained at once, and it should be estimated using the finite-difference by giving several queries. Therefore, EOT-based adaptive attacks in black-box settings average outputs for each input to get a reliable prediction for accurate gradient estimation.

The above way of averaging the noisy output (i.e., expectation) is one of two primary techniques for handling noise in derivative-free optimization [38]. The other primary technique is threshold selection which stores a reliable candidate solution set (in our framework, candidate adversarial examples) that makes minimal losses. It accepts a new solution for the candidate set when the evaluated loss is less than the recorded smallest loss by the threshold. This principle of threshold selection can be adapted to the gradient estimation step in query-based attacks. Since decision-based attacks try to reduce the size of adversarial perturbation, selecting a candidate set with a sufficiently large threshold is identical to increasing $\sigma$ of random perturbations in the gradient estimation like Eq. 4 to ignore the disturbance of small input noise. However, increasing the perturbation size can amplify the gradient estimation error by itself.

Therefore, following the suggestion of [1, 38], we design expectation-based adaptive attacks against SND. In the following, we shed light on the difficulty of evading the proposed defense with the adaptive attacks in detail.

In our framework, the input of the function, ${\bm{x}}+\bm{\eta}$, is a Gaussian random process. But the result of the nonlinear function $f$, $f({\bm{x}}+\bm{\eta})$, is no longer a Gaussian random process. This makes it very difficult for query-based attacks to bypass SND. For expectation-based adaptive attacks, adversaries can approximate $f({\bm{x}})$ as $\mathbb{E}_{\bm{\eta}}[f_{\bm{\eta}}({\bm{x}})]$ by taking the average over multiple queries using the fact that $\mathbb{E}(\bm{\eta})=\bm{0}$. However, this attempt requires many queries for each iteration and greatly diminishes query efficiency. We note that adversaries should also consider the query efficiency for their adaptive attacks.

In addition, even if a large amount of queries are used, $\mathbb{E}_{\bm{\eta}}[f_{\bm{\eta}}({\bm{x}})]$ may be different from $f({\bm{x}})$ because of the nonlinearity of the deep neural networks. With simple examples, we will explain how the expectation value differs from the actual value when Gaussian noise is added to the input of nonlinear functions.

From the proof on the simple network, we can expect that the average of the output may have an error with the actual output even in a deep neural network.

In this section, we evaluated the defense ability of SND against eight query-based black-box attacks: BA, Sign-OPT, HSJA, GeoDA, SimBA, SimBA-DCT, Bandit-TD, and Subspace Attack, along with other defense methods: PNI, RSE, R&P, and PGD-AT. We used the CIFAR-10 [23] and ImageNet [13] datasets for our experiments and following previous studies [7, 17, 20], we used ResNet-20 for CIFAR-10 and ResNet-50 [19] for ImageNet as target networks. Following [5], we randomly sampled 1,000 and 250 correctly classified images from the CIFAR-10 test set and the ImageNet validation set for evaluation. We describe detailed experimental settings in supplementary material.

For evaluation metrics, we first define a successfully attacked image as an image from which an attack can find an adversarial image within the perturbation budget $\epsilon$ and query budget $Q$. With this definition, we use attack success rate, which is the percentage of the number of successfully attacked images over the total number of evaluated images. We note that since we evaluate defense performance, a lower attack success rate is better. We measured the $\ell_{2}$ norm of perturbations and set $\epsilon$ to $1.0$ for the CIFAR-10 dataset, and to $5.0$ for the ImageNet dataset. Note that we denote the $q^{th}$ query image as $\hat{{\bm{x}}}^{q}$. $\hat{{\bm{x}}}^{q}$ and $\hat{{\bm{x}}}_{t}$ can be different.

We first evaluated the clean accuracy of models with defenses on the original test split (10K images) of the CIFAR-10 and validation split (50K images) of the ImageNet dataset. As shown in Table 1, SND hardly reduces the clean accuracy compared to other methods. The accuracy drop caused by SND is not significant at $\sigma\leq 0.01$, which implies that sufficiently small $\sigma$ hardly affects clean accuracy.

We performed four decision-based attacks against models with defenses, and Table 2 shows the evaluated attack success rates. SND shows competitive defense ability despite having more than 5% higher clean accuracy compared to other defenses. Moreover, due to significant performance drop, RSE and PNI cannot be applied to the models for large-scale image classification with the ImageNet dataset.

We performed six query-based attacks against models with defenses, and Table 3 shows the evaluated attack success rates. When the query budget $Q$ is 20K, the average of the attack success rates over the attacks against the baseline is 87.9%, whereas SND with $\sigma=0.01$ significantly reduces it to 10.0%. SND with $\sigma=0.001$ also significantly reduces the average attack success rate to 29.5%, which is comparable to the second-best method, R&P (22.5%).

We also calculated the average $\ell_{2}$ norm of perturbations of query images $||{\bm{x}}_{0}-\hat{{\bm{x}}}^{q}||_{2}$ at the predefined query budget $Q$ to show whether the perturbation norm diverges or not. If an attack stops in the middle without requesting $Q$ queries, we used the last query image instead. In decision-based attacks, it can be seen that randomization-based defenses, SND and R&P, significantly increase the perturbation norm as $q$ increases. In SimBA and SimBA-DCT, the perturbation norm is minimal in SND and R&P, which implies that the attacks have significant difficulty in finding a perturbation which decreases $y_{c_{0}}$.

To provide supporting evidence for assumptions of SND in score-based attacks, we calculated $\hat{\sigma}=\sqrt{\mathrm{Var}[\ell({\bm{x}}+\bm{\eta})]},$ where $\bm{\eta}\sim\mathcal{N}(\bm{0},\sigma^{2}\bm{I})$. With $\sigma=0.01$ and 1,000 test images of the CIFAR-10, we evaluated $\ell({\bm{x}}+\bm{\eta})$ for 100 iterations for each clean image and calculated the $\hat{\sigma}$ averaged over all images. In our experiment, $\hat{\sigma}=0.04$ which is small but sufficient to make $\ell({\bm{x}}+\bm{\eta})$ to be non-differentiable about ${\bm{x}}$.

In decision-based attacks, our assumption in Section 3.2 is that if $\hat{{\bm{x}}}_{t}$ is near the decision boundary, small noise can easily move the image across the boundary. We evaluated $P_{mis}:=P(h({\bm{x}})\neq h({\bm{x}}+\bm{\eta}))$ through experiments. We counted the above mismatch case for all queries during the attack process. With $\sigma=0.001\textrm{, }0.01$ and the CIFAR-10 test images, the average of $P_{mis}$ over all the attacks is calculated as 0.22 and 0.25, respectively. In contrast, on clean images, $P_{mis}$ is obtained as 0.002 and 0.021, respectively. Therefore, the results shown in Table 4 support our argument.

As described in Section 3.4, we devised an adaptive attack against SND that takes the expectation of predictions for repetitive $T$ queries. In this experiment, we performed HSJA against SND with $\sigma=0.01$ on the CIFAR-10 dataset. Since HSJA is a decision-based attack, we regard the most predicted class in $T$ queries as the expected class. We measured the attack success rate and $P_{mis}$ according to the query budget, and the adaptive attack clearly shows a higher attack success rate than the baseline ($T=1$), as shown in Table 5. On the same query budget, however, the adaptive attack shows a lower attack success rate (e.g., 22.7% ($T{=}1$) > 18.2% ($T{=}5$) at $Q$=10K, and 29.3% ($T{=}5$) > 27.3% ($T{=}10$) at $Q$=50K). Therefore, the expectation-based adaptive attack has limitations due to the restricted query budget. Moreover, even if $T$ increases, $P_{mis}$ does not decrease and this reinforces our argument in Section 3.4. We also applied the adaptive attack to BA, SO, and GeoDA on CIFAR-10 and two score-based attacks (SimBA-DCT and Bandit-TD) on ImageNet for comprehensive comparisons. The experimental results are shown in supplementary material.

So far, we have used a fixed $\sigma$ for SND. Changing $\sigma$ for each query may reduce clean accuracy while maintaining the defense ability. From this motivation, we multiplied $\bm{\eta}$ with $k$ which is randomly sampled between 0 and 1 from the beta distributions with three different settings: (1) Uniformly random (the same as $\alpha{=}\beta{=}1$) (2) Sampling from a beta distribution with $\alpha{=}\beta{=}2$ whose probability density function (PDF) is $\cap$-shaped. (3) Sampling from a beta distribution with $\alpha{=}\beta{=}0.5$ whose PDF is $\cup$-shaped. We calculated clean accuracy and average $\ell_{2}$ norm of noise for each method. Among the three ways, at $\sigma=0.01$, $\alpha{=}\beta{=}2$ is better than the others in terms of the loss of clean accuracy and the defensive ability against Sign-OPT. Detailed results can be found in supplementary material.

Since SND protects models by interfering with gradient estimation and the local search of query-based attacks, we do not expect SND is effective against transfer-based attacks as these attacks exploit the transferability of adversarial examples. However, our method is complementary with other defenses, which are mainly effective against transfer-based black-box attacks such as [22] and [36]. Combined with other defense techniques, SND can work well against general black-box attacks, provided that the model’s parameters are kept secret to adversaries.

To support this argument, we experimented with Subspace attack [18], a hybrid attack that exploits transferability in query-based attacks. Specifically, the Subspace attack exploits transferability-based priors, which are gradients from local substitute models trained on a small proxy dataset. We used pre-trained ResNet-18 and ResNet-34 [19] as reference models for gradient priors. We performed the attack based on the $\ell_{\infty}$ norm because the authors provide parameter settings only for the $\ell_{\infty}$ norm.

Detailed experimental results are described in supplementary material, but the results show that SND alone cannot effectively defend against the hybrid attack with gradient priors. However, when SND is combined with PGD-AT, it effectively protects the model and decreases the attack success rate from 100% to 42.4% at $Q$=20K and $\sigma{=}0.01$. To focus on the defensive ability against gradient estimation, we recalculated the attack success rate without initially misclassified images. Then, the newly obtained attack success rate decreases from 100% to 16.4% at $Q$=20K. This result implies that SND can be combined with other defenses against transfer-based attacks to achieve strong defense ability against all types of black-box attacks.

To the best of our knowledge, studies that mainly target defending against query-based black-box attacks have not yet been published. However, history-based detection techniques for query-based attacks have been proposed recently [9, 25]. Considering that adversary requires many queries of similar images for finding an adversarial example, they store information about past query images to detect the unusual behavior of query-based attacks.

Li et al. [24] analyze the connection between the robustness of models against additive Gaussian noise and adversarial perturbations. They derive the certified bounds on the norm bounded adversarial perturbation, and they propose a new training strategy to improve the certified robustness. Similarly, randomized smoothing [12] creates a smoothed classifier that correctly classifies when Gaussian noise is added to the classifier’s input. Cohen et al. [12] prove that this smoothed classifier can have $\ell_{2}$ certified robustness for an input. Both SND and the above certified defenses add Gaussian noise to the input. However, the purpose of the addition of noise in the certified defenses is to induce the classifier to gain certified robustness. Whereas SND adds noise to disturb an accurate measurement of the output to defend against query-based black-box attacks at the inference. In addition, the certified defenses use a much larger $\sigma$ ($\geq 0.25$) than SND ($0.01$).