GREAT Score: Global Robustness Evaluation of Adversarial Perturbation using Generative Models

Thanks for the author's replies. My questions have been partially resolved. However, I still have the following concerns:

1. Could you provide any high-level explanations of how the gap between two probabilities (i.e., $g(G(z))$) measures the lower bound of minimal perturbation ($\Delta_{\min}$)? The scale of the two probabilities' gap is $g(G(z)) \in [0,(\pi/2)^{1/2}]$, right? If your theorem holds, the lower bound of the minimal perturbation belongs to $[0,(\pi/2)^{1/2}]$, right? It is weird that the minimal distance $\Delta_{\min}$ should be related to the dimensionality whereas the gap between two probabilities is irrelevant to the dimensionality.

2. You mean that '''uncalibrated score is the default choice''. However, it is still confusing for me to judge which model is more robust based on your metric. For example, in terms of uncalibrated score, Gowal_extra (0.534) is more robust than Rebuffi_extra (0.507); in terms of AutoAttack accuracy, Gowal_extra (80.53) is less robust than Rebuffi_extra (82.32). Further, in terms of calibrated score, Rebuffi_28_ddpm (1.214) is more robust than Rebuffi_70_ddpm (1.208); in terms of AutoAttack accuracy, Rebuffi_28_ddpm (78.80) is less robust than Rebuffi_70_ddpm (80.42). I believe this inconsistency makes the rank of the model unclear in terms of robustness, which degrades the soundness and contribution.

GREAT Score measures classification margin, while AutoAttack measures accuracy under a fixed perturbation budget ϵ. AutoAttack’s ranking will change if we use different ϵ values... Therefore, we note that GREAT Score and AutoAttack are complementary evaluation metrics and they don’t need to match perfectly.

We express sincere gratitude for your valuable feedback and constructive comments.

Question 1: The definition of robustness in Eq. (1) and Eq.(4) seems to be confusing and possibly wrong, how does the gap between two probabilities measure the minimal perturbation?

The reviewer's question is exactly one of the major contributions of our work - establishing the connection between the defined metric in Eq. (1) and the derived certified lower bound in Appendix A.2.3. The novelty lies in the use of a generative model taking random Gaussian noise as input and adapting the Stein’s Lemma to derive a global certified lower bound on the minimal perturbation defined in Eq. (1). Please see the proof of Theorem 1 in Appendix 6.4 for the detailed derivation. If the reviewer still feels uncertain about this connection, we are willing to engage in further discussion to address the concern.

Question 2：Determine which rank should be used.

The criterion depends on whether or not additional information is available to a user at the time of evaluating global robustness. We would like to emphasize that the calibrated GREAT score ranking is expected to be better than the uncalibrated one since calibration improves the rankings by providing additional information (e.g. calibrated with CW attack distortion). In principle, if no additional information is provided, then the uncalibrated score is the default choice. If some auxiliary information (e.g., attack perturbations) is available, then we suggest the use of a calibrated score.

Question 3: How can you guarantee the gap between the two probabilities achieved by the generated data is achieved in the worst case?

Based on the reviewer's comment, we believe there may be some misunderstandings about our guarantee. We would like to use the following points to clarify the reviewer's concern.

1. For a generated sample $G(z)$, the gap in our context refers to the difference in the prediction probability between the correct class $c$ and the most likely (top-1) predicted class, where the gap is defined as $f_c(G(z)) - \max_{k \in \{1,\ldots,K\},k\neq c} f_k(G(z))$. We note that $f_k(\cdot)$ is the prediction probability of class $k$, instead of a probability distribution.
2. Our goal is not to generate data that achieves the worst-case "gap" (we don't actually know what gap refers to here in the reviewer's comment). Instead, we are using our defined gap to derive a certified lower bound on the true global robustness, as proved in Sec. 6.4.

We hope our explanation clarifies the reviewer's concern. We are at the reviewer's disposal to answer any further questions the reviewer may have.

Question 4: The table and figure should be resized to be larger, which makes it easier to read.

In the updated version, we have included new changes requested by reviewers and shortened some parts to remain in 9 pages.

Question 6: Appendix chapters need to be arranged according to the order in which they appear in the main text.

We have updated our paper to rearrange the order.

Question 7: Some of the examples in the article need to be replaced to adhere to the previous arguments.

We have rearranged the graphs and appendix.

Question 8: For other competitive methods, it would be better to use all the data in the dataset to measure robustness rather than the strategy proposed by the author?

For a fair comparison, we indeed compared our metric with other methods on the same set of generated samples. For baseline methods, we also reported their robust accuracy on the entire test set. For example, as demonstrated in Table 2, the utilization of AutoAttack on both synthetic and original data resulted in a low correlation coefficient of 0.7296, suggesting the instability of using AutoAttack for model ranking. Moreover, scalability is the unique strength of our method, as our method only requires forward inferences with the predictions made on the generated data samples, whereas attack algorithms are computationally intense, as discussed in the run-time analysis in Sec. 4.4.

Question 9: Does it still make sense to use a lower bound if a true global robustness evaluation can be obtained with high computational efficiency?

Based on the findings presented in following research, it has been established that the computation of the local minimum perturbation is an NP-hard/NP-complete problem, which means the true global robustness is computationally inefficient to obtain. Therefore, computationally efficient lower bounds such as GREAT Score become a viable alternative for global robustness evaluation.

Daskalakis, Constantinos, Stratis Skoulakis, and Manolis Zampetakis. "The complexity of constrained min-max optimization." Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 2021.

Katz, Guy, et al. "Reluplex: An efficient SMT solver for verifying deep neural networks." Computer Aided Verification: 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part I 30. Springer International Publishing, 2017.

We express sincere gratitude for your valuable feedback and constructive comments.

Question 1: There are obvious spelling and coincidence errors in the paper.

We are sorry about the spelling errors and typos. We have run a careful check in the revised version.

Question 2: Simplify the introduction of generative models and add the description of global robustness evaluation.

In the updated version, we have included new changes requested by reviewers and shortened some parts to remain in 9 pages.

Question 3: Draw flow charts of the algorithm.

This is a great suggestion! We have added a flowchart right after the algorithm in Figure 5 of the Appendix.

Question 4: Give a more detailed time complexity calculation.

Here we analyze the time complexity of our algorithm. The time complexity of the GREAT Score algorithm is determined by the number of iterations (generated samples) in the loop, which is denoted as $N_S$. Within each iteration, the algorithm performs operations such as random selection, sampling from a Gaussian distribution, generating samples, and predicting class labels using the classifier. We assume these operations have constant time complexity $I$ and absorb them in the big $O$ notation.

Additionally, the algorithm computes the sample mean of the recorded statistics, which involves summing and dividing the values. As there are $N_S$ values to sum and divide, this step has a time complexity of $O(N_S)$.

Therefore, the overall time complexity of the algorithm can be approximated as $O(N_S \cdot I)$.

For CW attack, the optimization process iteratively uses gradients to find the adversarial perturbation. The number of iterations required depends on factors such as the desired level of attack success and the convergence criteria. Each iteration involves computing gradients, updating variables, and evaluating the objective function. It also involves a hyperparameter search stage to adjust the weighted loss function.

Let $B$ be the complexity of backpropagation, $T_g$ be the number of iterative optimizations, and $T_b$ be the number of binary search steps for the hyperparaneter. The dominant computation complexity of CW attack for $N_S$ samples is in the order of $O(N_S \cdot T_g \cdot T_b \cdot B)$. Normally, $T_g$ is set to 1000, and $T_b$ is set to 9. Therefore, the CW attack algorithm is much more time-consuming than ours. In the table below, we include a table of run-time comparison of GREAT Score and CW Attack on the same 500 examples for Rebuffi_extra and Gowal_extra models.

Question 5: The layout of the experimental results graphs and tables is confusing.

We understand the reviewer's concern, but the space of our revision is constrained by the ICLR submission guideline that does not allow for an extra page in the revised version. Nonetheless, we have made adjustments to our revised version to include the requested changes by all reviewers and optimize the graph and table presentations.

Dear Reviewer npik,

First of all, we would like to thank you all again for your valuable time and efforts spent reviewing our paper and helping us improve it. We have also revised our paper to reflect our responses to your questions.

As the discussion period is closing, we sincerely look forward to your feedback.

It would be very much appreciated if you could once again help review our responses and let us know if these address your concerns. We are eager to answer any further questions you might have. We strive to improve the paper consistently, and it is our pleasure to have your feedback!

Best regards,

Authors

Question 3.2: Explain why the GREAT score serves as a lower bound for the CW attack distortion.

We would like to clarify that the derivation of GREAT Score is irrelevant to CW attack, and it is not an attack algorithm that finds an adversarial perturbation. In fact, we proved in Sec. 3.1 that GREAT Score is a lower bound of the minimal perturbation, making it a natural lower bound for all successful adversarial perturbations, including CW attack.

We further emphasize their differences using the following points:

1. Although our equation (3) may look similar to the second term of the CW attack objective, the only similarity is that they are the evaluation of the classification criterion for misclassification. Note that our metric does not involve any $L_2$ norm loss term as did in the CW attack.
2. Another notable difference is that the CW attack aims to find a perturbation $\delta^*$, whereas our metric is to use a generated sample $G(z)$ from a generative model for global robustness evaluation. Our metric shows a certified perturbation range and does not involve the design of attack perturbation.
3. In Theorem 1 we showed that GREAT Score serves as a certified lower bound of the true robustness (minimal perturbation), whereas CW attack (and any other attack methods) is an upper bound of the minimal perturbation.

Question 4: Privacy-aware question for training data.

Thank you for your advice. To our understanding, the mentioned paper discloses the risk of leaking private training data through model queries at inference time. However, our statement is about preventing the use of private and sensitive data to evaluate/audit a model. The scope is different from the privacy of training data. For example, when evaluating online facial recognition APIs (as discussed in Sec. 4.5), using our generated samples is more privacy-preserving than using real private and sensitive facial images. On the other hand, in this context, the mentioned paper is interested in finding private facial images used to train those APIs, which is beyond our scope.

Question 5: "In Figure 2, we compare the cumulative robust accuracy (RA)" <- RA is used before its definition on page 7; please define on the first use of the acronym RA.

We have defined it in the summary of Classifiers on the RobustBench part.

Question 6: "using the Rebuffi_extra model (Rebuffi et al., 2021)" <- please give a short inline description of this model.

We have added it to the updated version.

Question 7: "DMs reverse the forward process and implement a sampling process from Gaussian noises to reconstruct the true samples" <- Please mention that this is done by solving a stochastic differential equation.

We have added the description in the updated version.

We express sincere gratitude for your valuable feedback and constructive comments.

Question 1: limitation to L2-based attacks.

As stated and explained in Sec. 5, we admitted that our GREAT Score focused on $L_2$ norm, due to the restriction of extending Stein's Lemma to obtain a closed-form global Lipschitz constant in other $L_p$ norms. Please see Lemma 4 in Appendix A.3 for details about the derivation.

Nonetheless, we hope the new insights and contributions from this paper, such as global certified robustness using generative models and its use in evaluating the robustness of online black-box APIs can outweigh this limitation.

Question 2: The paper's description of some relevant work is either terse or lacking.

We understand the reviewer's concern, but our revision is constrained by the ICLR submission guideline that does not allow for an extra page in the revised version. Nonetheless, we have made adjustments to our revised version to expand the descriptions of related work in the main paper. We also note that we have provided extended discussion in the supplementary material.

Question 3: Please explain that the CW (L2) attack solves an optimization objective which results in low L2 distortion. Also, it is important to note why the GREAT score serves as a lower bound for the CW attack distortion.

Question 3.1: Explain CW (L2) attack solves an optimization objective that results in low L2 distortion.

Using our nation, consider a $K$-way classifier $f$. Let $x$ be a data sample and $y$ be its top-1 classification label. Denote $\delta$ as the adversarial perturbation. The untargeted CW Attack ($L_2$ norm) solves the following optimization objective:

$\delta^* = \underset{\delta}{\arg \min } ( \Vert \delta \Vert_2^2 + \alpha \cdot \max \{f_y(x + \delta) - \max_{k \in \{1,\ldots,K\},k\neq y} f_k(x + \delta),0 \} ),$ where $f_k(\cdot)$ is the prediction of the $k$-th class, and $\alpha > 0$ is a hyperparameter.

If the second term of the objective function is zero, then by definition $x+\delta$ is a perturbed sample of $x$ causing label flipping. In CW attack implementation, given $\alpha$, it uses a gradient-based optimization solver and runs it for $T_g$ iterations to solve for the smallest $\delta$ that makes the second term zero. Then, it performs a binary search on $\alpha$ for a $T_b$ number of trials (in each trial, another round of multiple iterations is executed) to ensure the second term remains zero while aiming to minimize the first term (the square of the $L_2$ performance level). Finally, the attack algorithm returns the smallest perturbation in the entire process such that $f_y(x + \delta) < \max_{k \in \{1,\ldots,K\},k\neq y} f_k(x + \delta)$ (equivalently, when the second term is 0). If no solution is found, one should increase either $T_b$ and $T_g$.

The dominant computation complexity of CW attack for $N_S$ samples is in the order of $O(N_S \cdot T_g \cdot T_b \cdot B)$, where $B$ is the complexity of backpropagation. On the other hand, the complexity of GREAT Score is $O(N_S \cdot I)$, where $N_S$ is the number of generated samples, and $I$ is the forward inference cost of the generative model and the classifier. A run-time comparison is shown in Sec. 4.4. In the table below, we include a table of run-time comparisons of GREAT Score and CW Attack on the same 500 examples for Rebuffi_extra and Gowal_extra models.

We express sincere gratitude for your valuable feedback and constructive comments.

Question 1: Error bound induced by the difference between the underlying data distribution and generative data distribution.

The reviewer's intuition is correct. In our ablation study of generative models (GMs), we do find that better GMs give higher ranking. In Figure 3, we show that increasing the Inception Score of GMs can significantly increase the Spearman's rank correlation. Intuitively, a higher inception score means better learning of GMs to the underlying data distribution, resulting in improved ranking efficiency in our case. We also had a discussion on the approximation guarantee of some GMs to the true data distribution in Sec. 6.2.

Question 2: Table 1 lacks clear advantages of GREAT score over other metrics despite significant distortion differences.

The main message we wanted to deliver for Table 1 is to show the complete statistics of different methods on all CIFAR-10 models. The results also verify our main theoretical contribution (Theorem 1) that GREAT Scores are indeed certified lower bounds of minimal perturbation, as the perturbations found by CW Attack (an upper bound) are all numerically larger than that of GREAT Score.

The "Advantages" of GREAT Scores are demonstrated in other figures and tables in the same section. For example, high model ranking correlation (Sec. 4.3, Table 2 & Table 3), fast run time (Sec. 4.4 & Fig. 4), and its utility in the evaluation of online black-box APIs (Sec. 4.5, Table 4 & Table 5).

Question 3: Are there any other options besides generative models or GANs, which can approximate the unknown data distribution?

This is a great question! Beyond our discussion in Sec. 6.2, in addition to generative models such as GANs or Diffusion models, another approach commonly used to approximate unknown data distributions is Kernel Density Estimation (KDE). KDE is a non-parametric statistical tool that can provide an estimation of the underlying data distribution based on observed data samples.

Several research papers have explored the application of KDE for approximating hidden data distributions, such as

S. A. Bigdeli, G. Lin, L. A. Dunbar, T. Portenier and M. Zwicker, "Learning Generative Models Using Denoising Density Estimators," in IEEE Transactions on Neural Networks and Learning Systems, doi: 10.1109/TNNLS.2023.3308191.

M. Rosenblatt, Remarks on some nonparametric estimates of a density function.Ann.Math. Stat.27, 832–837 (1956).

E. Parzen, On estimation of a probability density function and mode. Ann. Math. Stat.33, 1065–1076 (1962).

However, it is important to note that KDEs typically perform well in low-dimensional settings and they are known to suffer from the curse of dimensionality. For common datasets like CIFAR-10 and ImageNet, KDE may not be the most effective approach to accurately approximate the underlying data distribution given the limited size of their training data.

Question 4: Figures 1 and 2 should be larger. Similarly, it is hard to get a close look at Tables 1 and 2. The figures and tables on Pages 7 and 8 are not well-constructed.

Thanks for your advice. Although the ICLR submission guideline does not allow for an extra page in the revised version, we have rearranged the tables and figures to improve the clarity of figures. Please see the updated version.