Random Noise Defense Against Query-Based Black-Box Attacks
Year: 2021

Abstract:
The query-based black-box attacks have raised serious threats to machine learning models in many real applications. In this work, we study a lightweight defense method, dubbed Random Noise Defense (RND), which adds proper Gaussian noise to each query. We conduct the theoretical analysis about the effectiveness of RND against query-based black-box attacks and the corresponding adaptive attacks. Our theoretical results reveal that the defense performance of RND is determined by the magnitude ratio between the noise induced by RND and the noise added by the attackers for gradient estimation or local search. The large magnitude ratio leads to the stronger defense performance of RND, and it’s also critical for mitigating adaptive attacks. Based on our analysis, we further propose to combine RND with a plausible Gaussian augmentation Fine-tuning (RND-GF). It enables RND to add larger noise to each query while maintaining the clean accuracy to obtain a better trade-off between clean accuracy and defense performance. Additionally, RND can be flexibly combined with the existing defense methods to further boost the adversarial robustness, such as adversarial training (AT). Extensive experiments on CIFAR-10 and ImageNet verify our theoretical findings and the effectiveness of RND and RND-GF.

heading: 1 Introduction
text: Deep neural networks (DNNs) have been successfully applied in many safety-critical tasks, such as autonomous driving, face recognition and verification, etc. However, it has been shown that DNN models are vulnerable to adversarial examples [18, 21, 26, 29, 48], which are indistinguishable from natural examples but make a model produce erroneous predictions. For real-world applications, the DNN model as well as the training dataset, are often hidden from users. Instead, only the model feedback for each query (e.g., labels or confidence scores) is accessible. In this case, the product providers mainly face severe threats from query-based black-box attacks, which don’t require any knowledge about the attacked models.
In this work, we focus on efficient defense techniques against query-based black-box attacks, of which the main challenges are 1) the defender should not significantly influence the model’s feedback to normal queries, but it is difficult to know whether a query is normal or malicious; 2) the defender has no information about what kinds of black-box attack strategies adopted by the attacker. Considerable efforts have been devoted to improving the adversarial robustness of DNNs [13, 34, 49, 50]. Among them, adversarial training (AT) is considered as the most effective defense techniques [3, 49]. However, the improved robustness from AT is often accompanied by significant degradation of the
†Corresponding author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
clean accuracy. Besides, the training cost of AT is much higher than that of standard training, and then it also often suffers from poor generalization to new samples or adversarial attacks [20, 39, 45, 46]. Thus, we argue that AT-based defense is not a very suitable choice for black-box defense. In contrast, we expect that a good defense technique should satisfy the following requirements: well keeping clean accuracy, lightweight, and plug-and-play.
To this end, we study a lightweight defense strategy, dubbed Random Noise Defense (RND) against query-based black-box attacks. For query-based attacks [1, 2, 7, 9, 11, 19, 23, 26, 27, 32, 35], the core is to find an attack direction by gradient estimation or random search based on the exact feedback of consecutive queries, which leads to a decrease of the designed objective. RND is realized by adding random noise to each query at the inference time. Therefore, the returned feedback with randomness results in poor gradient estimation or random search and slows down the attack process.
To better understand the effectiveness of RND, we provide a theoretical analysis of the defense performance of RND against query-based attacks and adaptive attacks. Our theoretical results reveal that the defense performance of RND is determined by the magnitude ratio between the noise induced by RND and the noise added by the attackers for gradient estimation or random search. The attack efficiency is significantly affected by a large magnitude ratio. The attackers need more queries to find the adversarial examples or fail to find a successful attack under limited query settings. That is, the larger ratio leads to the better defense performance of RND. Apart from standard attacks, the adaptive attack (EOT) [3] has been considered as an effective strategy to mitigate the random effect induced by the defenders. We also conduct theoretical analysis about the defense effect of RND against EOT attacks, and demonstrate that the magnitude ratio is also crucial to mitigate adaptive attacks and the adaptive attacks have the limited impact of evading the RND. On the other hand, large random noises to each query may lead to degradation of clean accuracy. To achieve a better trade-off between the defense effect and the clean accuracy while maintaining training time efficiency, we further propose combining RND with a lightweight Gaussian augmentation Fine-tuning (RND-GF). RND-GF enables us to adopt larger noise in inference time to disturb the query process better.
We conduct extensive experiments on CIFAR-10 and ImageNet. The experimental results verify our theoretical results and demonstrate the effectiveness of RND-GF. It is worth noting that RND is plug-and-play and easy to combine with existing defense methods such as AT to boost the defense performance further. To verify these, we evaluate the performance of RND combined with AT [22] and find that the RND can improve the robust accuracy of AT by up to 23.1% against the SOTA black-box attack Square attack [2] with maintaining clean accuracy.
The main contributions of this work are four-fold.
• We study a lightweight random noise defense (RND) against black-box attacks theoretically and empirically. Our theoretical results reveal that the effectiveness of RND is determined by the magnitude ratio between the noise induced by RND and the noise added by the attackers for gradient estimation and random search.
• We theoretically analyze the performance of RND against the adaptive attack (EOT) and demonstrate that EOT has the limited effect of evading the RND.
• Leveraging our theoretical analysis, we further propose an efficient and stronger defense strategy RND-GF by combining the Gaussian augmentation Fine-tuning and RND towards a better trade-off between clean and adversarial performance.
• Extensive experiments verify our theoretical analysis and show the effectiveness of our defense methods against several state-of-the-art query-based attacks.

heading: 2 Related Work
text: Query-based Methods. Here we mainly review the query-based black-box attack methods, which can be categorized into two classes, including gradient estimation and search-based methods. Gradient estimation methods are based on zero-order (ZO) optimization algorithms. The attacker utilizes a direct search strategy to find the search direction in search-based methods instead of explicitly estimating gradient. Furthermore, for our theoretical analysis, we focus on score-based queries. The continuous score (e.g., the posterior probability or the logit) for each query is returned, in contrast to the decision-based queries which return hard labels. Specifically, [26] proposed the first limited query-based attack method by utilizing the Natural Evolutionary Strategies (NES) to estimate the
gradient. [32] proposed the ZOsignSGD algorithm, which is similar to NES. Based on Bandit Optimization, [27] proposed to combine the time and data-dependent gradient prior with gradient estimation, which dramatically reduced the number of queries. For the `2 norm constrain, SimBA [23] randomly sampled a perturbation from orthonormal basis. SignHunter [1] focuses on estimating the sign of gradient and flipped the sign of perturbation to improve query efficiency. Square attack [2] is the state-of-art query-based attack method that selects localized square-shaped updates at random positions of images.
Black-Box Defense. Compared with the defense for white-box attacks, the defense specially designed for black-box attacks has not been well studied. Two recent works [8, 31] proposed to detect malicious queries based on the comparison with the history queries since the malicious queries are more similar with each other compared with normal queries. AdvMind [37] proposed to infer the intent of the adversary, and it also needed to store the history queries. However, suppose the attacker adopted the strategy of long-interval malicious queries. In that case, the defender has to store a long history, with a very high cost of storage and comparison. [42] proposed the first black-box certified defense method, dubbed denoised smoothing. [5] also showed that adding random noise can defend against query-based attacks through experimental evaluations, without theoretical analysis of the defense effect. There are also a few randomization-based defenses. R&P [51] proposed a random input transform-based method. RSE [33] added large Gaussian noise to both the input and activation of each layer. PNI [25] combined adversarial training with adding Gaussian noise to the input or weight of each layer. However, these methods significantly sacrificed the accuracy of benign examples and also have a huge training cost. PixelDP [30] and random smoothing [13, 41] proposed to train classifiers with large Gaussian noise to get certified robustness under the `2 norm. However, they require to obtain a majority prediction of this query. Obviously, that places a huge burden on model inference and even helps the attacker get the more accurate gradient estimation. The too large Gaussian noise used in those methods also sacrifices clean accuracy. In contrast, RND maintains a good clean accuracy and only perturbs each query once, without any extra burden. [40] showed that the model with Gaussian augmentation training achieves the state-of-art defense against common corruptions, while the defense to black-box attacks is not evaluated.

heading: 3 Preliminaries

heading: 3.1 Score-based Black-Box Attack
text: In this work, we mainly focus on the score-based attacks. The analysis and evaluation of decisionbased attacks are shown in supplementary materials. We denote the attacked model asM : X → Y with X being the input space and Y being the output space. Given a benign data (x, y) ∈ (X ,Y), the goal of adversarial attack is to generate an adversarial example xadv that is similar with x, but to enforce prediction ofM to be different with the true label y (i.e., untargeted attack) or to be a target label h (i.e., targeted attack). The optimization of untargeted attack can be formulated as follows,
min xadv∈NR(x) f(xadv) = min xadv∈NR(x) (My(xadv)−max j 6=y Mj(xadv)). (1)
For targeted attack, the objective function is maxj 6=hMj(xadv)−Mh(xadv).Mj(xadv) denotes the logit or softmax output w.r.t. class j. NR(x) = {x′| ‖x′ − x‖p ≤ R} indicates a `p ball around x (p is often specified as 2 or∞), with R > 0. In attack evaluation, as long as L(xadv) is less than 0, attackers consider the attack to be successful.
The score-based attack algorithms commonly adopt the projected gradient descent algorithms, xt+1 = ProjNR(x)(xt − ηtg(xt)). (2)
For white-box attacks, g(xt) is the gradient of f(x) w.r.t. xt. However, for black-box attacks, the gradient g(xt) cannot be directly obtained. So the attackers utilize the gradient estimation or random search to conduct the update g(xt).

heading: 3.2 Zero-Order Optimization for Black-Box Attack
text: Zero-order optimization (ZO) has become the mainstream of black-box attacks, dubbed ZO attacks. The general idea of ZO attack methods is to estimate the gradient according to the objective values returned by querying. The gradient estimator widely used in score-based and decision-based attacks
[7, 10, 12, 12, 16, 26, 27, 32, 36] is
gµ(x) = f(x+ µu)− f(x)
µ u, (3)
where u ∼ N (0, I), and µ ≥ 0. Based on this gradient estimator, the update of attack becomes xt+1 = ProjNR(x)(xt − ηtgµ(xt)). (4)

heading: 3.3 Random Search for Black-Box Attack
text: The search-based attacks also depend on the value of f(x+ µu)− f(x) to find attack directions. Here, u is a searching direction sampled from some pre-defined distributions, such as gaussian noise in [12], orthogonal basis in [23] and squared perturbations in [2]. The µ is the size of perturbation in each search step such as the size of square in Square attack [2]. The work of [1, 35] adopt the fixed size schedule. If f(x+ µu)− f(x) < 0, the attackers consider u as a valuable attack direction. So, the direction searching becomes
s(x) = I(h(x) < 0) · µu where h(x) = f(x+ µu)− f(x), (5)
where, I is the indicator function. And the updating of search-based attacks becomes xt+1 = ProjNR(x)(xt + s(xt)). (6)

heading: 4 RND: Random Noise Defense Against Query-based Attack Methods

heading: 4.1 Random Noise Defense
text: In the gradient estimator (e.g., Eq.(3)) and searching direction (e.g., Eq.(5)), the attacker adds one small random perturbation µu to get the objective difference between two queries. Thus, if the defender can further disturb this random perturbation, the gradient estimation or searching direction is expected to be misled to decrease the attack efficiency. However, it’s also hard for defenders to identify whether a query is normal or malicious. Inspired by those observations, we study a lightweight defense method, dubbed Random Noise Defense (RND), that simply adds random noise to each query. For RND, the feedback for one query x isM(x+ νv), with v ∼ N (0, I) is standard Gaussian noise added by the defender, and the factor ν > 0 controls the magnitude of random noise. Considering the task of defending query-based black-box attacks, RND should satisfy: 1) the prediction of each query will not be changed significantly; 2) the estimated gradient or direction searching should be perturbed as large as possible towards better defense performance. The gradient estimator and searching direction under RND become
gµ,ν(x) = f (x+ µu+ νv1)− f (x+ νv2)
µ u, (7)
sν(x) = I(hν(x) < 0) · µu where hν(x) = f(x+ µu+ νv1)− f(x+ νv2), (8)
where v1,v2 ∼ N (0, I) are both standard Gaussian noise generated by the defender. To satisfy the first requirement, one cannot add too large noise to each query. However, to meet the second requirement, ν should be large enough to change the gradient estimation or searching direction. We need to choose a proper ν to achieve a good trade-off between these two requirements. In the following, we provide the theoretical analysis of RND, which can shed light on the setting of ν.

heading: 4.2 Theoretical Analysis of Random Noise Defense Against ZO Attacks
text: In this section, we will present the theoretical analysis of the effect of RND against ZO attacks. Specifically, we study the convergence property of ZO attack in Eq.(4) with gµ,ν(x) in Eq.(7) being the gradient estimator. Throughout our analysis, the measure of adversarial perturbation is specified as `2 norm, corresponding to NR(x) = {x′|‖x′ − x‖2 ≤ R}. To facilitate subsequent analyses, we first introduce some assumptions, notations, and definitions.
Assumption 1. f(x) is Lipschitz-continuous, i.e., |f(y)− f(x)| ≤ L0(f)‖y − x‖. Assumption 2. f(x) is continuous and differentiable, and ∇f(x) is Lipschitz-continuous, i.e., ‖∇f(y)−∇f(x)‖ ≤ L1(f)‖y − x‖.
Notations. We denote the sequence of standard Gaussian noises added by the attacker as U t = {u0,u1, . . . ,ut}, with t being the iteration index in the update Eq.(4). The sequence of standard Gaussian noises added by the defender is denoted as Vt = {v01,v02, . . . ,vt1,vt2}. The generated sequential solutions are denoted as {x0,x1, . . . ,xQ}, and the benign example x is used as the initial solution, i.e., x0 = x. d = |X | denotes the input dimension. Definition 1. The Gaussian-Smoothing function corresponding to f(x) with ν > 0,v ∼ N (0, I) is
fν(x) = 1
(2π)d/2
∫ f(x+ νv) · e− 12‖v‖ 2 2 dv. (9)
Due to the noise inserted by the defender, fν becomes the objective function for the attacker. We also define the minimum of fν(x), f∗ν = fν(x ∗) = minx∈NR(x0) fν(x).

heading: 4.2.1 Theoretical Analysis under General Non-Convex Case
text: Here, we report theoretical analysis of RND under general non-convex case satisfying Assumption 1.
Theorem 1. Under Assumption 1, for any Q ≥ 0, consider a sequence {xt}Qt=0 generated according to the descent update Eq.(4) using the gradient estimator gµ,ν(x) in Eq.(7) , with the constant stepsize,
η = [
R γ(α)2d3L30(f)(Q+1)
]1/2 Then,
1
Q+ 1 Q∑ t=0 EUt,Vt(‖∇fµ,ν(xt)‖2) ≤ 2L0(f) 5 2R 1 2 d 3 2 (Q+ 1) 1 2 1 2 γ(α) (10)
where νµ = α and γ(α) = α+ √ 2 2 , which is always increasing function of α.
Remark 1. Due to the non-convexity assumption, we only guarantee the convergence to a stationary point of the function fµ,ν(x), which is a smoothing approximation of fν . To bound the gap between fµ,ν(x) and fν(x), i.e., |fµ,ν(x)− fν(x)| ≤ , ∀ x ∈ NR(x), we could choose µ ≤ µ̂ = d1/2L0(f) [36]. The minimum of upper bound is denoted as δ, then the upper bound for the expected number of queries is O ( γ(α)2
d3L50(f)R δ2
) .
The convergence rate of ZO attacks is important since attackers need to find adversarial examples within limited queries effectively. Theorem 1 shows the convergence rate is positive related to the ratio νµ . The larger ratio ν µ will lead to the higher upper bound of convergence error and slower convergence rate. In consequence, the attackers need much more queries to find adversarial examples. Specifically, if νµ 1, the query complexity is equivalent to the original constant term O( d3
δ2 ). When ν µ ≥ 1, the query complexity is really improved over O( d3
δ2 ). Therefore, the attack efficiency will be significantly reduced under the queries limited setting, leading to failed attacks or a much larger number of queries for successful attacks. Therefore, the large ratio νµ leads the effectiveness of RND. In accordance with our intuition, the defenders should insert larger noise (i.e., ν) than that added by the attack (i.e., µ) to achieve the satisfied defense effect.
Trade-off of Larger ν and Clean Accuracy: If f(x) is Lipschitz-continuous, then |fν(x)− f(x)| ≤ νL0(f)d1/2 [36]. The larger ν is, the larger the gap between fν(x) and f(x). So the clean accuracy of the model with adding larger noise will also decrease. This is also shown in Figure 1 (d), which forms a trade-off between defense performance of RND and clean accuracy.
Larger Noise Size µAdopted by Attackers: The attacker may be aware of the defense mechanism, increasing the adopted noise size µ. Our experiment results also verify this point. As shown in Figure 2 (a), for NES attack, the attack failure rate is almost 0, when ν = µ = 0.01. This shows adding small noise can’t always guarantee an effective defense. Previous work [5, 15] don’t consider this and overestimate the effect of small noise. However, increasing the noise size µ will also lead to less accurate gradient estimation and random search in Eq.(3) and Eq.(5), leading to a significant decrease in attack performance consequentially. Taking the NES [26] and Bandit attack [27] on ImageNet as examples, as shown in Figure 3, when µ increase from 0.01 to 0.05, the `∞ attack failure rates increase from 5.1%, 5.0% to 22.8%, 25.7% respectively. For Square attack, [2], when µ increases from 0.3 to 0.5, the average number of queries has doubled. To guarantee a successful
attack, attackers cannot always increase µ. Our experimental results show that the attack performance decreases significantly when the µ of ZO attacks and Square attack is larger than 0.01 and 0.3. Based on the above analysis, we propose the stronger defense method in Section 4.4. It enables us to add larger noise (ν > µ) and still maintains a good clean accuracy.

heading: 4.2.2 Theoretical Analysis of Random Noise Defense Against Adaptive Attacks
text: As suggested in recent studies of robust defense [3, 6, 49], the defender should take a robust evaluation against the corresponding adaptive attack. The attacker is aware of the defense mechanism. Here we study the defense effect of RND against adaptive attacks. Since the idea of RND is to insert random noise to each query, an adaptive attacker could utilize Expectation Over Transformation (EOT) [4] to obtain a more accurate estimation, i.e., querying one sample multiple times to get the average value. Then, the gradient estimator used in ZO attacks Eq.(4) becomes
g̃µ,ν(x) = 1
M M∑ j=1 f(x+ µu+ νvj1)− f(x+ νvj2) µ µ, (11)
where vj1,vj2 ∼ N (0, I), with j = 1, . . . ,M . Note that here the definition of the sequential standard Gaussian noises added by the defender (see Section 4.2.1) should be updated to Vt = {v01, . . . ,v0M , . . . ,vt1, . . . ,vtM}. vij ∈ Vt contains vij1 and vij2. The convergence analysis of ZO attack with Eq.(11) against RND is presented in Theorem 2.
Theorem 2. Under Assumption 1 and 2, for any Q ≥ 0, consider a sequence {xt}Qt=0 generated according to the descent update Eq.(4) using the gradient estimator g̃µ,ν(x) Eq.(11), we have
1
SQ Q∑ t=0 ηtEUt,Vt(‖∇fµ,ν(xt)‖2) ≤ L0(f)R SQ + 1 SQ Q∑ t=0 η2t (L0(f) 2L1(f)d 2( 1 2 + 2ν2 µ2M )
+ ν2L0(f)L1(f) 2
µ d
5 2 +
ν4L1(f) 3(M + 1)
2µ2M d3)
(12)
The larger M for EOT: Theorem 2 shows that the upper bound will be reduced with larger M . So, EOT can mitigate the defense effect caused by the randomness of RND. However, with M going to infinity, the upper bound of expected convergence error (i.e., Eq. (12)) is still determined by the max term ν 4
µ2 d 3. It implies that the attack improvement from EOT is limited, especially with
the larger ratio νµ . Experiments in Section 5.3 verify our analysis of EOT attack.

heading: 4.3 Theoretical Analysis of Random Noise Defense Against Search-based Attacks
text: In this section, we will show how RND affects search-based attacks. Based on the Eq.(5) and Eq.(8), by adding noise νv, the value of hν(x) will be different from that of h(x), and there is certain probability that Sign(hν(x)) be different from Sign(h(x)). When the random noise νv causes inconsistence between Sign(hν(x)) and Sign(h(x)), RND will mislead the attackers to select the incorrect attack directions (i.e., abandoning the descent direction w.r.t. f or selecting the ascent direction), so as to decrease attack performance. We have following theoretical analysis about this. Theorem 3. Under Assumption 1, considering the direction update Eq.(6) with Eq.(8) in search-based attacks, we have,
P (Sign(h(x)) 6= Sign(hν(x)) ≤ 2L0(f)ν
√ d
|h(x)| (13)
The probability P is intuitively controlled by the relative values of the hν(x) and h(x). The proof is shown in Section F of supplementary materials. Theorem 3 shows the probability of misleading attacker is positive correlated with ν|h(x)| . Due to the small value µ and local linearity of model, we have |h(x)| = |f(x + µu) − f(x)| ≈ L0(f)µ‖u‖. Therefore, the |h(x)| is also positively correlated with the stepsize µ within the small neighborhoods. So the probability of changing the sign is positively correlated with νµ . The larger ratio ν µ leads to the larger upper bound of the probability. The attackers are more likely to be misleading and need much more queries to find adversarial examples. So, the defense performance of RND is better. As shown in Figure 1 (a-c), the evaluations on Square attack verify our analysis.

heading: 4.4 RND with Gaussian Augmentation Fine-tuning
text: The aforementioned theoretical analyses reveal that RND should choose a proper noise magnitude ν to achieve a good balance between clean accuracy and defense effectiveness. To achieve a high-quality balance, we could reduce the sensitivity of the target model to random noises. The influence of the noise on the accuracy of each query will be reduced. To satisfy the lightweight requirement of black-box defense, we propose to utilize Gaussian Augmentation Fine-tuning (GF), which fine-tunes the deployed model with Gaussian augmentation. We add random Gaussian noise to each training sample as a pre-processing step in the fine-tuning process. Consequently, the model fine-tuned with GF is expected to maintain good accuracy, even though defenders add a relatively large random noise to each query. As shown in Figure 1 (d), GF models still maintain the high clean accuracy under larger noise.

heading: 5 Experiments

heading: 5.1 Experimental Settings
text: Datasets and Classification Models. We conduct experiments on two widely used benchmark datasets in adversarial machine learning: CIFAR-10 [28] and ImageNet [14]. For classification models, we use VGG-16 [43], WideResNet-16-10 and WideResNet-28-10 [54] on CIFAR-10. We conducted standard training, and their clean accuracy on the test set is 92.76% 95.10, and 96.60%, respectively. For ImageNet, we adopt the pretrained Inception v3 model [47] and ResNet-50 model [24] provided by torchvision package and the clean accuracy are 76.80% and 74.90%, respectively.
Black-box Attack Methods and Compared Defense Methods. We consider several mainstreamed query-based black-box attack methods, including NES [26], ZO-signSGD (ZS) [32], Bandit [27], ECO [35], SimBA [23], SignHunter [1] and Square attack [2]. Note that the NES, ZS, Bandit are gradient estimation based attack methods, and the other four are search-based methods. SimBA and ECO are only designed for `2 and `∞ attack, respectively. Following [26], we evaluate all the attack methods on the whole test set of CIFAR-10 and 1,000 random sampled images from the validation set of ImageNet. We present the evaluation performance against the untargeted attack under both `∞ and `2 norm settings. The perturbation budget of `∞ is set to 0.05 for both datasets. For `2 attack, the perturbation budget is set to 1 and 5 on CIFAR-10 and ImageNet, respectively. The number of maximal queries is set to 10,000. We adopt the attack failure rate and the average number of query as an evaluation metric. The higher the attack failure rate and the larger the average number of query, the better the adversarial defense performance. We compare our methods with RSE [33] and PNI [25] on CIFAR-10. We adopt the pre-trained AT model [22] which shows better robustness than other AT models. For ImageNet, we compare pre-trained Feature Denoise (FD) model [52] and adopt pre-trained AT in Robustness Library [17]. The implementation details of those methods are given in the Section B.1 and B.2 of supplementary materials.

heading: 5.2 Evaluation of RND Against Query-based Black-Box Attacks
text: We first evaluate the defense performance of RND with various settings of µ and ν against querybased black-box attacks and verify the theoretical results in Section 4.2 and 4.3. Specifically, we set
ν ∈ {0.0, 0.01, 0.02} and µ ∈ {10−4, 5∗10−4, 10−3, 0.005, 0.01, 0.05} for ZO attacks on CIFAR-10 and µ ∈ {10−4, 0.001, 0.01, 0.05} on ImageNet. For Square attacks, we set µ ∈ {0.05, 0.1, 0.2, 0.3}. Figure 1 (a-c) presents the defense performance of RND against Square attack on CIFAR-10 and ImageNet, respectively. Figure 2 (a-c) and 3 (a-c) present the defense performance of RND against NES, ZS and Bandit on CIFAR-10 and ImageNet, respectively.
The results in Figure 1 (a-c), 2 (a-c), and 3 (a-c) show that: the attack failure rate of all attack methods generally increases as the value of νµ increases. Specifically, for a fixed value of ν (e.g., 0.01), the attack failure rate increases as µ decreases. While for a certain value of µ (e.g., 10−4), the attack failure rate increases as ν increases. These collaborate our theoretical analysis that the ratio of νµ determines the probability of changing sign and the convergence rate of ZO attacks. The larger ν µ , the higher the probability of changing the sign and the convergence error of ZO attacks, which results in poor attack performance under the query-limited settings.
We also evaluate the defense performance of RND with various values of ν against other searchbased black-box attacks and the results are shown in Figure 2 (d) for CIFAR-10 and Figure 3 (d) for ImageNet. As shown in the plots, the RND can significantly boost the defense performance. The attack failure rate increases as the value of ν increases. The complete evaluations, including the WideResNet-16 on CIFAR-10, the `2 attack, and the mean and medium number of queries of successful attacks, are reported in Section B.4 of supplementary materials.

heading: 5.3 Evaluation of RND Against Adaptive Attacks
text: We then evaluate the defense effect of RND against the adaptive attack EOT and verify our theoretical analysis in Section 4.2.2. We evaluate EOT with M ∈ {1, 5, 10} on CIFAR-10 and ImageNet, and ν is set to 0.02 and µ is set to 0.001 and 0.1 for ZO attacks and Square attack, respectively. The evaluation with even larger M and µ is presented in Section B.5 of supplementary materials.
We consider two settings of query budget: 1) adaptive query budget that assigns query budget of 10,000 ×M for different value of M ; 2) fixed query budget that adopt a fixed query budget of 10,000 for all M . We first evaluate the performance with adaptive query budget on NES and ZS, and their numerical results are shown in Table 1. As shown in Table 1, the attack failure rate decreases as M increases on both datasets. However, the average number of the query of successful attack also significantly increases as M increases, which demonstrates that the adaptive EOT attack can
increase the attacking success rate with a sacrifice of query efficiency. More importantly, we observe that the relative performance improvements induced by EOT generally decrease as M increases. These verify our theoretical analysis in Section 4.2.2.
The evaluation under the fixed query budget is also reported in Table 1. On small-scale dataset CIFAR10, the attack failure rate of all attacks generally decreases as M increases. Yet, we also observe a similar phenomenon in that the relative performance improvements induced by EOT decrease as M increases. For the large-scale dataset ImageNet, EOT can increase the attack performance with a significant sacrifice of query efficiency under most cases, except for NES and ZS. The attack performance of NES and ZS decreases as M increases. Specifically, for a fixed number of queries, the larger the M , the smaller the number of iterations for ZO attack under limited query setting. The poor performance of NES and ZS with larger M may be because the improvements induced by EOT are less than the potential degeneration caused by the decrease of iterations.

heading: 5.4 Evaluation of RND-GF and the Combination of RND with AT
text: In this section, we evaluate the performance of RND combined with Gaussian augmentation Finetuning, dubbed RNG-GF. In fine-tuning phase, we adopt the cyclic learning rate [44] to achieve superconvergence in 50 epochs. The training detail is shown in Section B.3 of supplementary materials. We adopt the attack failure rate and the average number of queries under the stronger adaptive attack EOT for evaluation. As that in the Section 5.2, we also tune the parameter µ for attackers and tune M ∈ {1, 5, 10} for EOT to achieve the best attack performance for all attack methods.
The comparison with other defense methods is shown in Table 2, where GF refers to standard fine-tuning with Gaussian augmentation. RND denotes the clean model coupled with random noise defense, and RND-GF indicates the GF model coupled with RND. As shown in the Table 2, RND can significantly boost the defense performance of the Clean Model on both datasets. For example, RNG achieves 20% ∼ 40% improvement against Bandit and SignHunter on both datasets. The proposed
GF can protect the clean accuracy from the larger noise induced by RND. Therefore, we adopt a relatively larger ν = 0.05 for RND-GF. According to our theoretical analysis, larger ν will lead to better defense performance. Experimental results also show that RNG-GF significantly improves the defense performance under all attack methods while maintaining good clean accuracy compared with RND. For example, RNG-GF achieves 40% ∼ 50% and 20% ∼ 30% improvements against ZO and search-based attacks on CIFAR-10. Compared with RSE, PNI, and FD, RND-GF achieves a higher failure rate against Bandit, SimBA, and ECO and leads to much more queries on other attacks. Besides, it also maintains a much better clean accuracy and lower training cost.
Without any extra modification, RND can be easily combined with many existing defense methods. We adopt the pre-trained AT WideNet-28 (`∞) model [22] and pre-trained AT ResNet-50 (`∞) model in Robustness Library [17] on CIFAR-10 and ImageNet, respectively. As shown in Figure 1 (d), AT models are less affected by adding noise like GF models. So we can adopt the larger noise (ν = 0.05) in inference time. Combining AT with RND, RND-AT significantly improves the robustness against all attacks and achieves the best performance among all methods. Based on AT models, RND-AT achieves 23.1% and 22.7% improvements against Square attack on CIFAR-10 and ImageNet.

heading: 5.5 Discussion and Limitations
text: As shown in Section 3.1, we focus on the score-based attacks. The analysis and evaluation of RND against decision-based attacks are shown in Section C of supplementary materials. Besides, as we mainly focus on practical query-based black-box attacks where the models and the training datasets are unknown to the attackers, we don’t cover the attacks utilizing the transferability from surrogate to target models. These methods usually assume that the surrogate models are trained on the same training set with the target model. It is difficult to obtain the training set behind the target model in real scenarios. Meanwhile, there have been some defense strategies developed for transfer-based attacks [38, 50, 53]. It is interesting to explore the combination of RND and these works towards better defense performance against transfer-based attacks. We leave it to future works.

heading: 6 Conclusion
text: In this work, we study a lightweight black-box defense, dubbed Random Noise Defense (RND) for query-based black-box attacks, which is realized by adding proper Gaussian noise to each query. We give the first theoretical analysis of the effectiveness of RND against both standard and adaptive query-based black-box attacks. Based on our analysis, we further propose RND-GF ,which combines RND with Gaussian augmentation Fine-tuning to obtain a better trade-off between clean accuracy and robustness. Extensive experiments verify our theoretical analysis and demonstrate the effectiveness of the RND-GF against several state-of-the-art query-based attacks. Without any extra modification, RND can easily combine with the existing defense methods, such as AT. We further demonstrate that when combined with RND, RND-AT can significantly boost the adversarial robustness. Given that RND is very simple and effective, we recommend it should become a baseline to evaluate new query-based black-box attack methods.

heading: Acknowledgment
text: We want to thank Jiancong Xiao, Ziniu Li, Congliang Chen, Jiawei Zhang, and Yingru Li for helpful discussions. We want to thank the anonymous reviewers for their valuable suggestions and comments. Baoyuan Wu and Zeyu Qin are partially supported by the Natural Science Foundation of China under grant No.62076213, the university development fund of the Chinese University of Hong Kong, Shenzhen under grant No.01001810, the special project fund of Shenzhen Research Institute of Big Data under grant No.T00120210003, and Tencent AI Lab Rhino-Bird Focused Research Program under grant No. JR202123. Hongyuan Zha is partially supported by a grant from Shenzhen Research Institute of Big Data.

Review summaries:
This paper proposes a simple but theoretically supported defense method against query-based black-box attack, called as Random Noise Defense. The core idea is to add Gaussian noise to a given input image at each query so it can be considered as quite simple. However, this paper shows theoretical analyses of RND against zero-order optimization, adaptive and search-based attacks. The overall finding through each theoretical analysis is that the number of queries for successful attacks by an attacker changes with the ratio of nu/mu. To overcome trade-off between clean accuracy and larger nu, the authors propose Gaussian augmentation fine-tuning for the target model. From the extensive experiments using CIFAR-10 and ImageNet against various black-box attacks, the authors demonstrated that, not only the results of theoretical analysis are confirmed by experiments but RND achieves the superior performance. Also, they showed RND can be easily combined with other defense methods and it achieves the state-of-the-art defense performance when it is combined with the adversarially-trained model.

The authors suggest the use of Random Noise Defense (RND) to protect deep learning models from black-box query-based attacks. The authors motivate their proposal via both theoretical and experimental validation -- where RND is a lightweight defense that augments random noise to input queries. The paper further proposes RND-GF that is trained to be robust (smoothened) to random noise -- in order to further improve the adversarial robustness.