MATT: Random Local Implicit Purification for Defending Query-based Attacks

Performance on Transfer Attack and White-box Attack

• We did not provide the performance of transfer attacks and white-box attacks because they are out of the scope of this work that aims to provide a general defense mechanism for query-based attacks.

• But our method can surely be used to defend against white-box attacks and transfer attacks according to our theoretical analysis on gradient estimation.

Efficiency and Training Complexity

• We have achieved a constant inference cost compared to linearly increase cost for ensembling. Moreover, we have achieved a '4x' inference speed up by removing the local ensemble technique. As for training complexity, it has a constant factor difference。

• We have already discussed the efficiency of from linearly increase to constant in Section 4.2. This efficiency is further validated by experiments in Appendix C.

• Another '4x' inference speedup is discussed in Section 4.2 and Appendix F.1.

• Training complexity has a constant factor difference with training one purifier due to the presence of multiple purification models.

Generalization Ability

• The generalization between different model structures has already been included in the training and testing process of our purifiers. Specifically, we train the purifiers using adversarial examples generated by Table 2, while we test the purifiers on models listed in Table 3. This training and testing gap shows that our purifier can generalize to protect unseen models.

• Training: Generating adversarial examples with models listed in Table 2.

• Testing: Evaluating the performance of our mechanism on models listed in Table 3.

Table 2: Details of the models used for training purifiers.

Table 3: Details of the models used for testing. The first two models are standardly trained model, the last two are adversarially trained model.

[2] Eduardo Dadalto. Resnet18 trained on cifar10. https://huggingface.co/edadaltocg/resnet18_cifar10, 2022. Accessed: 2023-07-01.

[3] Torchvision. Resnet50 - torchvision main documentation. https://pytorch.org/vision/main/models/generated/torchvision.models.resnet50.html, 2023. Ac- cessed: 2023-11-11

[4] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In Proceedings of the British Machine Vision Conference 2016, (BMVC), 2016.

[5] Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Edoardo Debenedetti, Nicolas Flammarion, Mung Chiang, Prateek Mittal, and Matthias Hein. Robustbench: a standardized adversarial robustness benchmark. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, (NeurIPS), 2021

[6] Sven Gowal, Chongli Qin, Jonathan Uesato, Timothy A. Mann, and Pushmeet Kohli. Uncovering the limits of adversarial training against norm-bounded adversarial examples. CoRR, 2020

[7] Hadi Salman, Andrew Ilyas, Logan Engstrom, Ashish Kapoor, and Aleksander Madry. Do adversarially robust imagenet models transfer better? In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, (NeurIPS), 2020a

We thank reviewer TG1v for the thoughtful and detailed review. We have made necessary amendments to our paper according to the feedback. Please find below our responses to your comments.

Presentation of the PRELIMINARIES

We provide the necessary equations in the Preliminaries section, especially the new gradient approximator $g(x)$, because we believe they can facilitate readers to better understand our subsequent theoretical analysis.

We agree and thank the reviewer's suggestions for the balance of detail and brevity, and we thus decide to move the detailed equations to the Appendix while retaining the information regarding the adversarial purification in the main body due to its novelty in the black-box attacks research community.

Problem with Experimental Setting

We regret that the reviewer may misunderstand our experimental settings, and we wish to clarify and justify our settings to address any potential misunderstandings.

• We did not see our evaluation procedures as problematic because we follow the settings of a related work [1] that uses correctly classified examples instead of all test samples to exclude the influence of misclassification on the attack or the defense performance.

• This experimental setting leads to the seemingly high accuracy of 80%, 84.8%, and 86.3% on the ImageNet dataset. In fact, the corresponding accuracy on the whole dataset is 60%, 63.6%, and 64.7%, respectively, assuming the original accuracy is 75% and no statistical bias with randomly chosen examples.

• We have provided a table of converted accuracy below and in Appendix H of the revised paper for your reference.

Table 1: A table of converted accuracy.

[1] Vo V, Abbasnejad E M, Ranasinghe D. QUERY EFFICIENT DECISION BASED SPARSE ATTACKS AGAINST BLACK-BOX DEEP LEARNING MODELS International Conference on Learning Representations. 2021.

Thank you again for your time and effort in reviewing our work.

There are only less than 2 days left to the rebuttal deadline, and we sincerely want to know whether our responses can successfully address all your concerns.

Please also let us know if you have further concerns. We are glad to continually improve our work to address them.

We deeply appreciate the comprehensive review and constructive feedback provided by reviewer cfuj on our work. We hope the following explanations and modifications will address your concerns and improve the clarity of our paper.

Revising the figures.

We would like to express our gratitude to the reviewer for pointing out the issues in our figures. We have revised Figures 3 and 4 according to the suggestions. Additionally, we have also updated Figure 2 for a better illustration of our methods. Please find below our modifications to the figures.

Figure 3

• Small batches: The small batches are extracted from the original image, which is segmented into several patches. We have now added additional annotations to the figure to clarify this (Cut up operation).
• Ensembling: The ensembling method encodes the entire image into high-level features using different purifiers. The final encoding is formed by randomly sampling from these features. We have improved the figure to better illustrate this process.
• Random Patch-wise Encoding: The original image is pre-segmented, and the patches are randomly assigned to different purifiers. The final encoding is formed by the high-level features of these patches.

Figure 4

• Attack during Training: This step aims to provide adversarial images for our training process. For better illustration, we have listed out the attack algorithms used (PGD, BIM, and FGSM).
• Revised Training Loop: We have updated the training loop into a triangle shape to better illustrate the training process. The process involves generating adversarial images, using all purifiers for purification, and training the classifier with all the purified images under different combinations under $\ell_1$ loss. We have added these details to the figure.
• Omitting Testing Phase: As our defense mechanism is an end-to-end process, we omitted the testing phase in the figure for brevity.

Novelty and Contribution

We acknowledge your concerns regarding the novelty of our work. We would like to clarify that our work's novelty lies in two main aspects:

1. Theoretical Advancement: Through rigorous theoretical analysis, we demonstrate that a deterministic purification process is unsuitable for black-box attack defense. This conclusion is also corroborated by our experimental findings (Robust accuracy 2.2% for CIFAR-10, 6.70% for ImageNet). This represents a significant theoretical advancement.

2. Technical Contribution: Stemming from this analysis, we introduce a random patch-wise mechanism with constant inference cost to enhance robustness, which signifies our technical contribution. Actually, we have addressed other efficiency issues (cancelling local ensemble, utilizing smaller encoders) for the existing purification methods but not listed as the main contribution in the paper. An acceleration from linear time to constant time is achieved in Figure 7 and Figure 8 compared to simple ensemble method, which enables the application of purification methods in real-world MLaaS systems (million-fold extra cost).

We hope the observations from theoretical analysis will be instrumental in designing purification-based methods for black-box systems. We have emphasized these insights in our contribution section (Section 1) for further clarity in the revised version of the paper.

Thank you again for your time and effort in reviewing our work.

There are only less than 2 days left to the rebuttal deadline, and we sincerely want to know whether our responses can successfully address all your concerns.

Please also let us know if you have further concerns. We are glad to continually improve our work to address them.

We thank reviewer bHtq for the comprehensive and detailed evaluation of our work. We appreciate the time and effort you put into reviewing our work. Please find below our responses to your comments.

Addressing Novelty Concerns

Our work theoretically and experimentally addresses the limitations of existing purification methods for black-box defense. We have listed the key points below:

• Our work provides a theoretical analysis for purification-based defense in black-box setting. The analysis quantifies the relationship between the number of purifiers and the robustness of the system. (Theoretical Contribution)
• Random-patch wise mechanism has constant inference cost with the number of purifiers and uses the most efficient purifier, which makes our mechanism the most efficient purification method. This method is suitable for real-world MLaaS systems (million-fold inference cost). (Technical Contribution)

Elucidating Insights from the Paper

We wish to underscore the insights from the convergence of black-box defense and the protection over specific adversarial points, which apply universally to all purification-based methods (preprocessor stage) for black-box defense.

• Our work proves that a single deterministic purifier cannot improve the system's robustness against black-box attacks from the above two aspects.
• To address this issue, we design a random patch-wise method to maintain a constant inference cost regardless of the number of purifiers.
• We hope the insights from our theoretical analysis will be instrumental in designing purification-based methods for black-box systems, which is now emphasized in our contribution section (Section 1) for further clarity in the revised version of the paper.

Response to Questions

We apologize for any confusion caused by the presentation of our paper and appreciate your patience.

Question 1: "extremely low" and "extremely high"

The term 'extremely low' in Section 1's second paragraph refers to the impracticality of deploying resource-intensive defense algorithms against query-based attacks in real-world scenarios. Following this sentence, 'a million-fold cost' for large corporations is used to illustrate the impracticality of the defense mechanism.

Question 2: "the robustness of the system is averaged across different purifiers"

We understand the ambiguity of this phrase and have revised the sentence to clarify its meaning:

"While adversarial optimal points persist, the presence of multiple optimal points under different purifiers serve as the first trial to enhance the robustness of all purification-based methods."

We acknowledge the challenge of identifying adversarial points for any purification function and present our solution as a pioneering effort to obscure these points, thereby bolstering the system's robustness.

Thank you again for your time and effort in reviewing our work.

There are only less than 2 days left to the rebuttal deadline, and we sincerely want to know whether our responses can successfully address all your concerns.

Please also let us know if you have further concerns. We are glad to continually improve our work to address them.

We thank reviewer XS3B for the comprehensive and detailed evaluation of our work. We appreciate the time and effort you put into reviewing our work. Please find below our responses to your comments.

Motivation for the Design

We propose our random patch-wise purification method to facilitate the application (low extra inference cost required) of multiple purifiers (proved necessary to defend black-box attacks) in a real-world MLaaS system. We have updated our motivation in Section 4.1 accordingly and listed the key points below:

• Our theoretical analysis has proved that a single deterministic purifier cannot improve the system's robustness against black-box attacks.
• Since directly ensembling multiple purifiers will linearly increase the inference cost, we propose a random patch-wise method to maintain a constant inference cost regardless of the number of purifiers. It is the key point since extra inference cost for each image lead to a million-fold cost increase in real-world MLaaS systems.
• Our method is the purification method with the lowest inference cost among all the purification methods as illustrated in Table 1 in the paper.
• We can surely use this method to defend white-box attack, which is not the focus of our paper.

Trade-off between accuracy and defense performance.

We have conducted detailed experiments to determine the clean accuracy of using each purification model available and the whole defense mechanism, which can be found in Appendix I of the revised paper. The conclusion is that, either the usage of single purification model or the entire defense mechanism will have barely minimum impact on the clean accuracy of the classifier.

Presentation of the method detail.

We have revised our paper for presentation of the method detail and found that the clarity of our paper is influenced by lack of explanation and annotations on figures as suggested by reviewer cfuj. In the revised paper, we have made the following changes to improve the clarity of our paper:

• Figure 2: We have circled the main body of a purifier model for later reference.
• Figure 3: We have added annotations to the figure to better illustrate the difference of our method and the ensemble method.
• Figure 4: We have added more details to present the training process of our method. The caption is also revised for better illustration.

Thank you again for your time and effort in reviewing our work.

There are only less than 2 days left to the rebuttal deadline, and we sincerely want to know whether our responses can successfully address all your concerns.

Please also let us know if you have further concerns. We are glad to continually improve our work to address them.