Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a new method for model stealing/knowledge distillation with hard label information only, based on a two-part modification of the standard model stealing pipeline. The standard pipeline feeds images to the target model, collects the corresponding labels, and trains a substitute model on the image-label pairs. First, the proposed method erases high-information patches from the images fed to the target model in order to collect additional (nearby) labels, providing extra information about the target model. Second, after training a first substitute model on the target images and their erased counterparts, the proposed method trains a second substitute model on both the original target data, the erased images and their labels, and "smoothed" predictions from the first substitute model in order to improve generalization.
main_review: Overall, the proposed methodology is not the simplest, but at the same time the modifications of the standard KD pipeline are creative and seem to non-negligibly improve performance on a variety of tasks. My more specific comments and questions are below:

- L149: What does "the attention map is also a kind of supervision signal pushing two models to be similar" mean? I also did not understand how this statement follows from the cited source.
- Does Section 3.1 mean that we actually train 3 substitute models throughout the process? One just on D_T to get the grad-cam, then another on D_T + D_E, then another on D_T + D_E and the smoothed pseudo labels?
- I think much of the math (e.g., the first two lines of equation 4) adds very little clarity and instead makes things more confusing by introducing additional symbols and notation. Similarly with the first line of equation 5, I think there is no reason to introduce a concept as well as an acronym (MSP) if it is only going to be used once on the immediate next line.
- The legends in Figure 4 are extremely hard to read, especially in print.
- Based on Figure 5 and the corresponding part of the results section, it seems as though the self-KD matters much less for performance than the CAM-driven erasing (which I also thought was the more well-motivated modification of the two). To what extent could the self-KD be replaced by more "conventional" ways to improve generalization and prevent overfitting like Cutout regularization, more aggressive data augmentation, higher weight decay, etc?
- The Amazon API demonstration was very interesting but lacked many experimental details---what was the setup here? What architecture was used by the proposed method vs KnockoffNets vs ActiveThief? How were parameters chosen, etc.? At face value the results are very impressive but need to be put into context with experimental details.

Overall, I think the paper showcases a creative idea that significantly improves over prior work, and presents the main ideas fairly clearly (especially in light of how complicated the method is). The clarity could be improved in places and further experimental details should be provided, and some additional results following up on the ablation study would (in my opinion) further improve the paper.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a new model stealing attack when the victim model only returns the class label to the queries instead of confidence or probability information. Prior attacks struggle in this setting to extract high-accuracy models. The proposes attack has two steps, first they query the model with a sample and probabilistically remove the input region using the GRAD-CAM of the substitute model. This aims to fit more information into a single query and simulates the prediction probabilities. Second, they use a self-knowledge distillation scheme on the substitute model to alleviate overfitting. Overall, their scheme achieves higher stolen accuracy than prior attacks, more resilient to a prior defense and allows the attacker to craft more transferable adversarial examples.
main_review: The paper is well-written and the intuitions behind the design is pretty clear. The setting is a relevant and a realistic setting as many of the defenses rely on obfuscating/perturbing the prediction probabilities to thwart the stealing attacks. Along these lines, I would also recommend the authors to look into Prediction Poisoning defense by Orekondy et al and evaluate the efficacy against their setting where the defense does not preserve the top-1 label.

Strengths:
+ Intuitive, well-designed attack, relevant setting.
+ Circumvents the one of the prediction perturbation-based defenses (Adaptive Misinformation)

Weaknesses:
- My first main concern is the baseline attacks the authors have selected. Both ActiveThief and KnockoffNets are active learning-based and they do not modify the query samples themselves, they only select them from a larger set. The proposed attack on the other hand actively modifies the samples. I believe a more suitable baselines would be something like Prada attack that modifies the queries with perturbations to extract more information from them.

- My second main concern is the ablation study itself. The ablation in the paper completely disables one or the other step of the attack and measure the attack success. A better ablation study would replace the steps with something trivial rather than removing altogether to see whether we need a rather complicated design to begin with. For the GRAD-CAM step, experimenting with random data augmentations (for example CutOut) and for the second step using something like label smoothing to prevent overfitting to potentially noisy labels would be more informative to understand the usefulness of the design.

- I also recommend the authors to experiment with the Prediction Poisoning defense, obviously in preserving top-1 label setting, the defense would be ineffective against the proposed attack (which is a good thing), but in other settings the attack's success might be reduced.

- It is also useful to present the attack results that use the full prediction probabilities to give a sense of the upper-bound on how good a label-only attack can get. 


Questions:

? Do you start from a pre-trained models before launching the model stealing attacks? This seems to be a standard practice in the prior work but I wasn't sure if it's the case here too.

? If the Adaptive Misinformation defense's OOD detector was trained on the samples generated by your attack, how would your attack fare?

==============
AFTER REBUTTAL
==============
Thanks for the extra experiments and the discussion. I'm bumping up my score, please include the detailed ablation study in the paper. I think it strengthens your story much more.
limitations_and_societal_impact: (See above)
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This submission proposes a new model stealing attack method, black-box dissector, under the hard-label setting. Specifically, this paper uses CAM-driven erasing strategy and random erasing module to increase the information inquired from the victim model. Experiments are conducted on CIFAR-10, SVHN, Caltech256 and CUBS200 datasets and achieved superior performance compared to other attack methods. In addition, ablation studies are conducted to verify the effectiveness of the proposed attack.
main_review: The underlying idea that gain more informative pseudo-labels by erasing response area is very insightful. Given recent upsurge in research on model and data security, the notion that model can be efficiently reproduced from APIs that output hard-labels is an emerging concern. There is also clear differentiation between black-box dissector from prior work. The experiment results also show the effectiveness of stealing attack. The reported attacks seem to significantly outperform some competitive baselines. In addition, black-box dissector can achieve high accuracy when the distributions between training dataset of victim model and attack dataset are far apart, which is of great help to other tasks such as transfer learning and domain adaptation.

Recently, there have been some new defense and detection methods against model stealing attacks [1][2]. I wonder if black-box dissector can still maintain high attack performance under these defenses.

In addition, could the authors comment on whether the label refinement [3] can improve the performance of model stealing attack if the entire attack dataset can be directly input into the victim model and get the hard-labels?

[1] P. Maini, M. Yaghini, and N. Papernot, “Dataset inference: Ownership resolution in machine learning,” in International Conference on Learning Representations, 2021.

[2] X. Wang, Y. Xiang, J. Gao, and J. Ding, “Information laundering for model privacy,” in International Conference on Learning Representations, 2021.

[3] K. Ghasedi Dizaji, A. Herandi, C. Deng, W. Cai, and H. Huang, “Deep clustering via joint convolutional autoencoder embedding and relative entropy minimization,” in Proceedings of the IEEE international conference on computer vision, 2017, pp. 5736–5745.

limitations_and_societal_impact: The CAM-driven erasing strategy proposed in this paper is mainly addressing the problem of information acquisition when soft labels cannot be obtained. It would be interesting to compare the attack performance between using CAM-driven erasing strategy and using soft label.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work presents a more effective model stealing attack using an erasing-based method which makes use of saliency maps.  The method is clever and intuitive.
main_review: Thank you for the interesting work.  This paper seems to make appreciable progress on an important problem.  Below are several minor comments:

1) In general, the writing and grammar could be improved for the sake of clarity.  This is a major area for potential improvement in this paper.

2) Figure 2 is a little hard to parse.  The meaning of some of the arrows is unclear.

3)  Your victim models perform quite a bit worse than I would expect on the tasks given.  I believe hyperparameter tuning could significantly improve their performance, and maybe you could also significantly improve the performance of your attack as well with better hyperparameter tuning.

4)  It seems like the self-kd is not very important for the performance of your method.  I think you should have better justification for this component of your method.

limitations_and_societal_impact: The authors do adequately address the limitations and impact of their work.
review_title: null

Meta-review: The paper studies model stealing attack in the hard-label black-box setting, where the victim model only returns the top-1 label for each query. To overcome this challenge and acquire more information, the paper designs a novel erasing-based scheme to improve the performance of model stealing attack. 

This is a borderline case where the paper has pros and cons. On the positive side, the paper is proposing a novel idea that improves black-box model stealing attack by an erasing-based technique, and all the reviewers like the novelty of the paper. However, the proposed method is based on heuristics and lack fundamental theoretical justifications. In particular, it is not clear how the proposed method can overcome the challenges when Grad-CAM gives wrong or noisy input region, especially in the initial training stage. Further, the method is quite complicated (pointed out by reviewer ohZm) and there are some presentation issues (pointed out by reviewer WyuJ). After deeply looking into the paper, AC and SAC decide the reject the paper due to lack of analysis and the presentation issues. We encourage the authors to address these issues and resubmit to another top conference. 
Decision: Reject