Year: 2021

Abstract:
The AutoAttack (AA) has been the most reliable method to evaluate adversarial robustness when considerable computational resources are available. However, the high computational cost (e.g., 100 times more than that of the project gradient descent attack) makes AA infeasible for practitioners with limited computational resources, and also hinders applications of AA in the adversarial training (AT). In this paper, we propose a novel method, minimum-margin (MM) attack, to fast and reliably evaluate adversarial robustness. Compared with AA, our method achieves comparable performance but only costs 3% of the computational time in extensive experiments. The reliability of our method lies in that we evaluate the quality of adversarial examples using the margin between two targets that can precisely identify the most adversarial example. The computational efficiency of our method lies in an effective Sequential TArget Ranking Selection (STARS) method, ensuring that the cost of the MM attack is independent of the number of classes. The MM attack opens a new way for evaluating adversarial robustness and contributes a feasible and reliable method to generate high-quality adversarial examples in AT.

text: The AutoAttack (AA) has been the most reliable method to evaluate adversarial robustness when considerable computational resources are available. However, the high computational cost (e.g., 100 times more than that of the project gradient descent attack) makes AA infeasible for practitioners with limited computational resources, and also hinders applications of AA in the adversarial training (AT). In this paper, we propose a novel method, minimum-margin (MM) attack, to fast and reliably evaluate adversarial robustness. Compared with AA, our method achieves comparable performance but only costs 3% of the computational time in extensive experiments. The reliability of our method lies in that we evaluate the quality of adversarial examples using the margin between two targets that can precisely identify the most adversarial example. The computational efficiency of our method lies in an effective Sequential TArget Ranking Selection (STARS) method, ensuring that the cost of the MM attack is independent of the number of classes. The MM attack opens a new way for evaluating adversarial robustness and contributes a feasible and reliable method to generate high-quality adversarial examples in AT.

heading: 1 INTRODUCTION
text: The deep neural network (DNN) has attracted a large number of researchers from different disciplines such as computer science (Goodfellow et al., 2016; Castelvecchi, 2016; Vaswani et al., 2017), physics (DeVries et al., 2018; Huang et al., 2019; Levine et al., 2019), biology (Maxmen, 2018a;b; Webb, 2018) and medicine (Hao et al., 2015; Esteva et al., 2017). The success of DNN mainly lies in its ability to learn useful high-level features from abundant data (Deng & Yu, 2014; LeCun et al., 2015). These learned features have been successfully used to address many difficult tasks. For example, DNNs can recognize images with high accuracy comparable to human beings (LeCun et al., 1998; Krizhevsky et al., 2012). In addition, DNNs are also widely used for speech recognition (Hinton et al., 2012), natural language processing (Andor et al., 2016), and playing games (Mnih et al., 2013; Silver et al., 2016).
As the impacts of DNN increase fast, its reliability has been a key to deploy it in real-world applications (Huang et al., 2011; Kurakin et al., 2017). Recently, a growing body of research shows that DNNs are vulnerable to adversarial examples, i.e., test inputs that are modified slightly yet strategically to cause misclassification (Szegedy et al., 2014; Nguyen et al., 2015; Kurakin et al., 2017; Carlini & Wagner, 2017a; Finlayson et al., 2019; Wang et al., 2019; Zhang et al., 2020b; Gao et al., 2021). The existence of such adversarial examples undoubtedly lowers the reliability of DNNs. Meanwhile, researchers have also been considering finding a reliable way to evaluate adversarial robustness of a DNN before deploying it in the real world.
The high-level idea of evaluating adversarial robustness of a DNN is quite straightforward, i.e., generating adversarial examples and calculating the accuracy of the DNN on these examples (this kind of accuracy is also known as adversarial robust accuracy). Szegedy et al. (2014) first pointed out the existence of adversarial examples and used a less powerful box-constrained L-BFGS method to generate them. Based on the studies in (Szegedy et al., 2014), Goodfellow et al. (2015) put forward the fast gradient sign method (FGSM). One common loss function they used is cross-entropy (CE) loss, and to maximize the loss function, FGSM uses its gradient to determine in which direction the pixel’s intensity should be increased or decreased. Madry et al. (2018) introduced a simple refinement
of the FGSM: projected gradient descent attack (PGD), where instead of taking a single step of size in the direction of the gradient sign, multiple smaller steps are taken.
Existing Evaluation Methods. PGD was an effective method to evaluate adversarial robustness of a standard-trained DNN (Madry et al., 2018) since adversarial robust accuracy of a standard-trained DNN is always very low after using PGD. Nevertheless, the existence of adversarial examples has already inspired research on training a robust DNN to defend against them, which means that a standard-trained DNN is not the only DNN we might meet and we need to evaluate adversarial robustness of a robust DNN as well. Unfortunately, PGD fails to reliably evaluate adversarial robustness of a robust DNN (Carlini & Wagner, 2017b; Croce & Hein, 2020).
Carlini & Wagner (2017b) observed the phenomenon of gradient vanishing in the widely used CE loss for the potential failure of L-BFGS, FGSM and PGD, and replaced the CE loss with many possible choices. Croce & Hein (2020) claimed that the fixed step size and the single attack used are the causes of poor evaluations, and they put forward an ensemble of diverse attacks (consisting of APGD-CE, APGD-DLR, FAB and Square) called AutoAttack (AA) to test adversarial robustness. Until now, AA has been the most reliable method to evaluate adversarial robustness (Croce & Hein, 2020).
However, though AA performs well in reliability, it needs a large amount of computational time. As shown in Figure 1(a), for attacking a ResNet-18 model on CIFAR-10 (following the adversarial training in (Madry et al., 2018)), the computational cost of AA (or T-AA) is 65 times (or 100 times) more than PGD used in (Madry et al., 2018), where T-AA is more time-consuming since it considers each target for APGD-DLR and FAB in AA. Worse still, in the worst case as analyzed in Appendix A, the computational cost of AA (or T-AA) is even 109 times (or 440 times) more than PGD.
A Dilemma Between Reliability and Computational Efficiency. The high computational cost makes AA infeasible when considerable computational resources are unavailable. Unfortunately, such scenarios are common in the real world, e.g., for practitioners who need real-time evaluation at each epoch of the training process of a robust model, such high computational cost is unacceptable. Similarly, since a large number of adversarial examples need to be generated at each epoch during adversarial training (AT), such high computational cost hinders applications of AA in AT. In consideration of the high reliability but low computational efficiency of AA, and the high computational efficiency but low reliability of PGD, we seem to encounter a dilemma: we have to consider giving up one factor (reliability or computational efficiency) when evaluating the adversarial robustness.
Our Reliable and Fast Solution. In this paper, we are dedicated to achieving reliability and computational efficiency simultaneously. For reliability, we evaluate the quality of adversarial examples using the margin between two targets for precisely identifying the most adversarial example. For computational efficiency, we put forward an effective Sequential TArget Ranking Selection (STARS) method to ensure that the cost of the MM attack is independent of the number of classes.
Reliability. To achieve reliability, we investigate the reasons behind the failure of PGD. We identify that CE loss, which is based on the probability of the true label py, is not an appropriate measure to the quality of adversarial examples. In Figure 2, we provide a simple demonstration to this issue, in which we consider one targeted false label t. As we can see, it is much more reasonable to measure the quality of adversarial examples in terms of the margin of probability py−pt. The most adversarial example in Figure 2 then corresponds to the one with the minimum margin of probability instead of the minimum probability py. Detailed study of the rationality of minimum-magrin is provided in Section 3.1. Since the search space B of high dimensional images is large (grey area), previous studies use gradient descent methods to generate the adversarial example that maximizes the loss function (Goodfellow et al., 2015; Carlini & Wagner, 2017b; Madry et al., 2018).
Though it looks promising to generate adversarial examples via minimizing the margin of probability, we find that there are still two issues: (a) The probability p is a kind of rescaling method to the logits z. Croce & Hein (2020) heuristically rescaled the logits z using their proposed DLR (defined at Eq.(6)). We investigate the performance of different rescaling methods in Section 3.1. We numerically find that the method using natural logits zy − zt (the meaning of margin) with no rescaling performs the best; (b) For the problem of multi-class and untargeted attacks, the margin is then zy −maxi 6=y zi. However, −(zy − maxi 6=y zi) is not an appropriate loss function, because the max function only considers one target at the current step while those unconsidered targets may lead to more adversarial examples. Hence, the reliable method is to minimize zy − zt for each t 6= y and take the most adversarial one, which is a widely used solution (Croce & Hein, 2020).
Computational Efficiency. Although running the attack for each false target is reliable, the computational cost depends on the number of classes. For datasets with a large number of classes, e.g., CIFAR-100 (100 classes) and Imagenet (1,000 classes), the computational cost will increase accordingly. To achieve computational efficiency, we propose a Sequential TArget Ranking Selection (STARS) method in Section 3.2 to make the computational time independent of the number of classes. According to the ranking of predicted probability, STARS method only selects a few highest targets and runs a sequential attack. Experiments show that, benefited from STARS method, MM attack can save 76.36% of the computational time on CIFAR-10, 98.51% on CIFAR-100 and 77.78% on SVHN.
By taking all the above factors into consideration, we propose a novel method, the minimummargin (MM) attack. Its detailed realization is provided in Section 3. We present extensive experimental results in Section 4, which verify that our MM attack can fast and reliably evaluate adversarial robustness. In particular, MM attack achieves comparable performance but only costs 3% of the computational time compared with the current benchmark AA. Hence, our proposed MM attack provides a new direction of evaluating adversarial robustness and contributes a feasible and reliable method to generate high-quality adversarial examples in AT.

heading: 2 PRELIMINARY
text: Neural Networks. A neural network is a function fθ : Rn → [0, 1]K , where θ is the parameters contained in fθ and K is normally the number of classes. The output of the network is computed
using the softmax function, which ensures that the output is a valid probability vector. Namely, given an input x ∈ Rn, fθ(x) = [p1, . . . , pK ] = p where ∑K i=1 pi = 1 and pi is the probability that input x has on class i. Before the softmax function, the output of the network is called logits z, i.e., p = softmax(z). The classifier assigns the label y = arg maxi f(x)i.
Projected Gradient Descent Attack (PGD). Madry et al. (2018) proposed the projected gradient descent (PGD) attack to generate adversarial examples to mislead a well-trained classifier fθ. Specifically, they start with setting x0 = x, and then in each iteration:
x′(t+1) = ΠB [x(0)](x ′ (t) + α sign(∇x′(t)`(fθ(x ′ (t)), y)), t = 0, 1, 2, . . . , (1)
where
B [x] = {x′ | d∞(x, x′) ≤ }, (2)
is the closed ball of radius > 0 centered at x; the x(0) refers to the starting point which corresponds to the natural example (or the natural example perturbed by a small Gaussian or uniformly random noise); x(t) is the adversarial example at step t; ΠB [x(0)](·) is the projection function that projects the adversarial variant back to the -ball centered at x(0) if necessary; the `∞ distance metric is d∞(x, x ′) = ‖x− x′‖∞; and ` is cross entropy (CE) loss:
CE(f, x, y) = − log(py) = −zy + log  K∑ j=1 ezj , (3) where pi = ezi/ ∑K j=1 e zj , i = 1, ...,K, and z is the logits of the model outputs.
Carlini and Wagner attack (CW). Carlini & Wagner (2017b) observed the phenomenon of gradient vanishing in the widely used CE loss for potential failure. The gradient w.r.t x in Eq. (3) is given by
∇xCE(f, x, y) = (−1 + py)∇xzy + ∑ i 6=j pi∇xzi. (4)
If py ≈ 1 and consequently pi ≈ 0 for i 6= y, then ∇xCE(x, y) ≈ 0 in Eq. (4). This gradient vanishing issue can lead to the failure of attacks. Motivated by this phenomenon, Carlini & Wagner (2017b) replaced the CE loss with several possible choices. Among these choices, the widely used one for the untargeted attack is
CW(f, x, y) = −zy(x′) + max i 6=y zi(x ′). (5)
AutoAttack (AA). Croce & Hein (2020) claimed that the fixed step size and the lack of diversity in attack methods are the main reasons for the limitations of previous studies. Motivated by the line search method (Grippo et al., 1986), they put forward adaptive projected gradient descent attack (APGD). They showed that using adaptive step size significantly improves the adversarial robustness compared with using fixed step size. For the loss function at Eq. (5), they claim that scale invariance w.r.t. z is necessary, and they proposed an alternative loss function:
DLR(f, x, y) = −zy(x ′)−maxi 6=y zi(x′)
zπ1(x ′)− zπ3(x′)
, (6)
where π is the permutation of the components of z in decreasing order. For the targeted attack, they propose another alternative loss function:
Targeted-DLR(f, x, y, t) = − zy(x ′)− zt(x′)
zπ1(x ′)− 12 · (zπ3(x′) + zπ4(x′))
. (7)
For the lack of diversity, they claimed that diverse attacks are beneficial for reliability, and then they put forward an ensemble of various parameter-free attacks called AutoAttack (AA) to test adversarial robustness, where AA contains APGD-CE, APGD-DLR, FAB and Square. Targeted AutoAttack (T-AA) replaces APGD-DLR with the targeted APGD-DLR, and replaces FAB with targeted FAB.

heading: 3 THE REALIZATION OF MINIMUM-MARGIN ATTACK
text: In this section, we discuss the realization of our minimum-margin (MM) Attack. In Section 3.1, we verify the rationality of using minimum-margin as the loss function and discuss the influence of different logits rescaling methods on robustness. In Section 3.2, we propose an effective Sequential TArget Ranking Selection (STARS) method to improve computational efficiency. In Section 3.3, we provide the detailed descriptions of MM attack.

heading: 3.1 THE RATIONALITY OF MINIMUM-MARGIN
text: To understand the rationality of our minimum-margin, we first look into the situation where no adversarial attack can succeed. Then we show that the formulation of minimum-margin is naturally derived from such a situation. We say that a classifier f is completely robust if ∀x′ ∈ B [x], arg maxi f(x
′)i = arg maxi f(x)i. The following condition is necessary and sufficient to the complete robustness:
Condition 1. Given a natural example x with its true label y, the K-class classifier f satisfies
∀x′ ∈ B [x], zy(x′)−max i 6=y zi(x ′) ≥ 0, (8)
where B [x] = {x′ | d∞(x, x′) ≤ }; zy(x′) = f(x′)y; zi(x′) = f(x′)i.
According to this condition, to reliably evaluate the complete robustness, the adversarial attacks should find the adversarial examples with minimum zy(x′)−maxi 6=y zi(x′), i.e., the most non-robust data point. It indicates that we should replace the CE loss in Eq. (3) with −(zy(x′)−maxi6=y zi(x′)) as the loss function in adversarial attacks. However, as mentioned before, −(zy − maxi 6=y zi) in Eq. (5) is not an appropriate loss function since it only focuses on the current step. The reliable method is to minimize zy − zt for each target t 6= y and take the most adversarial one. To verify the rationality of minimum-margin, we conduct experiments on different datasets with −(zy − zt) being the loss function (MM). In Table 1, MM performs a more reliable evaluation than PGD and CW.
The comparison with Targeted-DLR. Targeted-DLR (Croce & Hein, 2020) heuristically rescales the logits z in Eq. (7). For the logit of true target zy and a false target zt, the relative magnitude of zy and zt is constant under different rescaling methods. However, though the rescaling methods preserve the sign of zy− zt, they will lead to different adversarial variants. Clearly, there is no perfect rescaling method that can perform the best in any situation but inappropriate rescaling methods will hinder the searching for the most adversarial example.
We conduct experiments to investigate the difference of using different rescaling methods. The experimental setting follows (Madry et al., 2018), and we replace the CE loss with seven different logits rescaling methods. In Table 2, the successful set denotes the number of examples that can be attacked successfully in the test set of CIFAR-10 (10, 000 examples). As shown in Table 2, inappropriate logits rescaling methods (e.g., Targeted-DLR in AA) reduce the reliability, and the method using natural logits (no rescaling) performs the best among the seven methods. The results motivate us to use it as the loss function. Note we do not deny that there could be a better rescaling method, but still, a reasonably good result can be obtained by no rescaling (natural logits in Table 2).
We also investigate the difference among different successful sets. The non-empty difference sets A ∪ Bi − A and A ∪ Bi − Bi in Table 2 suggest that diverse logits rescalings can be considered when considerable computational resources are available, we analyze it in Appendix C.
Algorithm 1 MM Attack 1: Input: natural data x, true label y, set of false labels C, model f , loss function `MM , maximum number of
PGD steps N , perturbation bound , initial step size α, the number of classes K, targets selection number Ks, checkpoints set W ;
2: Output: adversarial data x′; 3: while Ks > 0 do 4: x′0 ← x; x′max ← x; fmax ← f(x′0); c = arg maxi∈C f(x)i; 5: for k = 0 to N − 1 do 6: x′k+1 ← ΠB [x] ( x′k + αsign(∇x′k`MM (f(x ′ k), y, c) ) ; 7: if f(x′k+1) > fmax then x′max ← x′k+1; fmax ← f(x′k+1); 8: if k ∈W and (Condition 2 or Condition 3) then α← α/2; x′k+1 ← x′max; 9: end for
10: C ← C \ {c}; 11: if arg maxi∈C f(x
′)i 6= y then Ks ← 0; 12: Ks ← Ks − 1; 13: end while

heading: 3.2 SEQUENTIAL TARGET RANKING SELECTION METHOD
text: As mentioned in the introduction, for multi-class and untargeted attacks, the widely used and reliable method is to minimize the loss function −(zy − zt) for each target t 6= y, and then take the most adversarial one. Since the computational cost of such a solution depends on the number of classes, it is unacceptable for practitioners with limited computational resources. Here, we propose a fast solution which saves a large amount of running time with little-to-no performance lost. We call our solution the Sequential TArget Ranking Selection (STARS), which consists of the following strategies.
Given a natural input x and a K-class classifier f , denoting the predicted probability as f(x)i for a false label i, a natural intuition is that the false target i with a higher value of f(x)i is more likely to lead to a successful attack. To verify this intuition, in Figure 3, we compare the performance between only selecting the false targets with Ks highest predicted probabilities and selecting all the K − 1 false targets. The results show that only selecting Ks (e.g., Ks = 3) highest targets achieves comparable performance. Combining this strategy with MM attack, we then denote MM3 (or MM5) as the MM attack with Ks = 3 (or Ks = 5). For the ranking of predicted probability f(x)i, we also investigate the difference of replacing the natural input x with adversarial examples in Appendix D, which shows that the replacement only has limited improvements. For the sake of efficiency, we recommend to use the ranking of f(x)i of the natural input x, which does not need extra computation.
Figure 3 also motivates us to perform a sequential attack based on the ranking of predicted probability on false targets: first, consider the false target i with the highest predicted probability f(x)i; if the attack succeeds, terminate MM attack on other targets; otherwise, continue to consider the false target with the second highest predicted probability, and so on.
Our experiments show that with the help of STARS method, MM3 attack saves 76.36% of the computational time on CIFAR-10, 98.51% on CIFAR-100 and 77.78% on SVHN.

heading: 3.3 MINIMUM-MARGIN ATTACK
text: With the above considerations, we summarize our scheme of MM attack in Algorithm 1. We follow the setting of the adaptive step size selection in Croce & Hein (2020) and specify checkpoints W = {w0 = 0, ..., wn} at which the MM attack decides whether to halve the current step size. The two conditions in Algorithm 1 are:
Condition 2. wj−1∑ i=wj−1 1f(x′i+1)>f(x′i) < β · (wj − wj−1), (9)
Condition 3. αwj−1 ≡ αwj and fwj−1max ≡ fwjmax. (10)

heading: 4 EXPERIMENTS
text: In this section, we justify the efficacy of our MM attack. In the experiments, we consider `∞-norm bounded perturbation (i.e., ||x′ − x||∞ ≤ ) in both training and evaluations. The images of all datasets are normalized into [0,1].

heading: 4.1 BASELINES
text: We evaluate 3 versions of our MM attack and compare them with 8 baselines. MM3 (or MM5) is the version of MM attack with maximum step number K = 20 and targets selection number Ks = 3 (or Ks = 5); MM+ is the version of MM attack with maximum step number K = 100 and targets selection number Ks = 9. Baselines consist of PGD (Madry et al., 2018), CW (Carlini & Wagner, 2017b), APGD-CE, APGD-DLR, FAB, Square, AA and T-AA (Croce & Hein, 2020).

heading: 4.2 EXPERIMENTAL SETUP
text: We verify our methods on different neural networks including ResNet-18 (He et al., 2016) and Wide-ResNet-34 (WRN-34) (Zagoruyko & Komodakis, 2016) using different datasets: CIFAR-10, CIFAR-100, SVHN. The adversarial training (AT) method in this paper follows (Madry et al., 2018). The training setup follows previous works (Madry et al., 2018; Zhang et al., 2019) that all networks are trained for 100 epochs using SGD with 0.9 momentum. The initial learning rate is 0.1 (0.01 for SVHN), and is divided by 10 at epoch 60 and 90, respectively. The weight decay is 0.0002 (0.0035 for SVHN). The previous work (Rice et al., 2020) observed that overfitting in robust adversarial training hurts test set performance. Thus, following Rice et al. (2020), we compare different methods based on the performance of the best checkpoint model (the early stopping results at epoch 60). For generating the adversarial data for updating the network, we set the `∞-norm bounded perturbation train = 8/255; the maximum number of PGD steps is K = 10; step size α = train/10. In testing, unless otherwise specified, we set `∞-norm bounded perturbation test = 8/255. For PGD and CW, we follow the setting in (Zhang et al., 2020a): the maximum number of steps K = 20, and the step size α = /4. For APGD-CE, APGD-DLR, FAB and their corresponding targeted version, we follow the setting in (Croce & Hein, 2020): the maximum number of steps K = 100. There is a random start in training and testing, i.e., uniformly random perturbations ([− train,+ train] and [− test,+ test]) are added to natural instances.

heading: 4.3 PERFORMANCE EVALUATION
text: We report the performance of our MM attack and all baselines on CIFAR-10, CIFAR-100, SVHN with the model structure chosen as ResNet-18. As shown in Figure 4, first, our MM attack can perform better than any single attack of PGD, CW, A-DLR, A-CE and FAB; second, compared with the ensemble of diverse attacks AA and T-AA, our MM attack achieves comparable performance but only incurs a very small amount of computational time. Extensive experiments on the large-capacity network WRN-34 are provided in Appendix E.

heading: 4.4 ADVERSARIAL TRAINING WITH MM ATTACK
text: By injecting adversarial examples into the training data, adversarial training (AT) methods seek to train an adversarial-robust deep neural network whose predictions are locally invariant in a small neighborhood of its inputs. Existing empirical defense methods formulate the adversarial training as a min-max optimization problem (Madry et al., 2018). Since a large number of adversarial examples need to be generated during training, practitioners pay great attention to the time cost of adversarial
example generation. Compared with AA, MM attack contributes a feasible and reliable method to generate high-quality adversarial examples in AT. Table 3 reports the performance. MM3-F10 (MM3-F20) denotes AT using adversarial examples generated by MM attack with 10 (20) fixed steps. MM3 denotes AT using adversarial examples generated by MM attack with 20 adaptive steps. We choose 11 testing methods to evaluate the robustness of 5 adversarial trained models. As shown in Table 3, by replacing PGD generated adversarial examples with MM attack generated adversarial examples, the robustness of AT model is significantly improved.

heading: 5 CONCLUSION
text: In this work, we proposed MM attack, which can reliably and efficiently evaluate adversarial robustness. For its reliability, we identified minimum-margin (MM) as the key evaluation criterion for the most adversarial example. For its computational efficiency, we proposed an effective STARS method to ensure that its computational time is independent of the number of classes. Our experiments showed that MM attack achieves comparable performance compared with AA, but only costs 3% of the computational time. Its reliability and efficiency further allow us to extend MM attack into AT, which significantly improves the quality of adversarial examples in AT.
ETHICS STATEMENT
This paper does not raise any ethics concerns. This study does not involve any human subjects, practices to data set releases, potentially harmful insights, methodologies and applications, potential conflicts of interest and sponsorship, discrimination/bias/fairness concerns, privacy and security issues, legal compliance, and research integrity issues.
REPRODUCIBILITY STATEMENT
To ensure the reproducibility of experimental results, we will provide a link for an anonymous repository about the source codes of this paper in the discussion phase.

heading: A THE COMPUTATIONAL TIME IN THE WORST CASE
text: In this section, we discuss the computational time in the worst case. According to their attack mechanism as an ensemble of diverse attacks, AA and T-AA consider one attack first. If the attack succeeds, stop other attacks on the current example; else, continue to consider the next attack in the ensemble. According to the strategy of our STARS method, MM attack considers the false target with the largest predicted probability first, if the attack succeeds, stop attacks on other false targets; else, continue to consider the next target in the ranking of the predicted probability. The computational time of these methods is influenced by different datasets and models. Hence, in the worst case that all attacks inside fail to succeed, the computational time is the sum of the individual time of each attack. Hence, the computational cost of AA (or T-AA) is 109 times (or 440 times ) more than PGD, and 34 times (or 139 times) more than MM3 in this case.

heading: B THE REALIZATION OF ADVERSARIAL TRAINING OF MM ATTACK
text: We summarize the adversarial training of MM Attack in Algorithm 2. We use MM3 attack to generate adversarial examples, and the computational time is about 2 times as much as PGD (Madry et al., 2018), which can be acceptable for most practitioners.

heading: C POTENTIAL BENEFITS OF DIVERSE RESCALINGS
text: We investigate the difference among different successful sets of seven rescaling methods mentioned above. In Table 2, the setting follows (Madry et al., 2018) (with 20 fixed steps). In Table 4, the setting follows (Croce & Hein, 2020) (with 100 adaptive steps). In Table 2 and Table 4, the non-empty difference sets A ∪ Bi − A and A ∪ Bi − Bi suggest that diverse rescaling methods can complement each other. Hence, when considerable computational resources are available, we recommend practitioners to consider diverse logits rescaling on a strong attack (e.g., our MM attack) rather than diverse weak attacks. Note that we do not argue that diverse weak attacks is unnecessary but rather that when a reliable enough attack exists, most relatively weak attacks have limited benefits other than increased computational cost.

heading: D THE REPLACEMENT OF NATURAL DATA FOR THE RANKING IN STARS
text: In our STARS method, we also investigate the difference of replacing the natural input x with adversarial examples. Table 5 shows that the replacement has limited improvements.

heading: E DETAILED EXPERIMENTAL RESULTS
text: To verify the rationality of minimum-margin, we conduct experiments on different step size, different step number and different B [x] in Table 6 and Table 7. We compare the reliability and the computational time between MM attacks and baselines. In Table 8 and Table 9, unless specified, the model structure is ResNet-18. The experiments verify that our MM attack achieves comparable performance but only incurs a very small amount of computational time.

heading: F EXPERIMENTAL RESOURCES
text: We implement all methods on Python 3.7 (Pytorch 1.7.1) with an NVIDIA GeForce RTX 3090 GPU with AMD Ryzen Threadripper 3960X 24 Core Processor. The CIFAR-10 dataset, the SVHN and the CIFAR-100 dataset can be downloaded via Pytorch. Given the 50, 000 images from the CIFAR-10 and CIFAR-100 training set, 73, 257 digits from the SVHN training set, we conduct the adversarial training on ResNet-18 and Wide ResNet-34 for classification.
Algorithm 2 Adversarial Training of MM attack. 1: Input: network architecture f parametrized by θ, training dataset S, loss function l, learning rate η, number
of epochs T , batch size n; 2: Output: Adversarial robust network fθ; 3: for epoch = 1, 2, . . . , T do 4: for mini-batch = 1,2,. . . ,N do 5: Sample a mini-batch {(xi, yi)}ni=1 from S; 6: for i = 1, 2, . . . , n do 7: Obtain adversarial data of MM attack x′i of xi by Algorithm 1; 8: end for 9: θ ← θ − η ∑n i=1∇θ` (fθ (x ′ i) , yi) /n;
10: end for 11: end for
CIFAR-10
0.003 20 51.14 -3.33 49.95 -2.14 48.23 -0.42 47.81 0.00
1/255 40 50.16 -3.15 49.13 -2.12 47.46 -0.45 47.01 0.00
1/255 20 50.28 -3.22 49.19 -2.13 47.50 -0.44 47.06 0.00
1/255 40 49.30 -2.92 48.45 -2.07 46.88 -0.50 46.38 0.00
2/255 10 50.54 -3.26 49.38 -2.10 46.70 -0.42 47.28 0.00
2/255 20 49.36 -2.93 48.48 -2.05 46.92 -0.49 46.43 0.00
4/255 10 49.52 -2.97 48.60 -2.05 47.02 -0.47 46.55 0.00
SVHN
PGD-20 Diff. CW Diff. MM3-F Diff. MM9-F Diff.
ResNet-18
4 67.90 -0.70 68.06 -0.86 67.23 -0.03 67.20 0.00
8 51.14 -3.33 49.95 -2.14 48.23 -0.42 47.81 0.00
12 45.53 -4.62 43.85 -2.94 41.86 -0.95 40.91 0.00
WRN-34
4 70.23 -0.30 70.55 -0.62 69.94 -0.01 69.93 0.00
8 53.69 -2.07 53.89 -2.27 51.95 -0.33 51.62 0.00
12 46.76 -3.68 46.24 -3.16 44.05 -0.97 43.08 0.00

Review summaries:
The paper proposed a strong adversarial attack, i.e., an attack that can generate strong adversarial examples and thus can better evaluate the adversarial robustness of given deep learning models. Compared with the SOTA attack, the proposed attack is much faster and thus easier to be applied in practice. The idea is novel and the results are solid. 

This paper proposes a minimum-margin (MM) attack to evaluate defenses. The authors report detailed results on the effects of different loss functions. Experiments are done on CIFAR-10/100 and SVHN, against the adversarially trained models.