HQA-Attack: Toward High Quality Black-Box Hard-Label Adversarial Attack on Text

Summary

This paper proposed a new approach HQA-Attack using iterative substituting normal words and replacing with synonyms for creating high quality adversarial text samples in the setting of black box attack + hard label. The experimental results on several NLP datasets and two commercial APIs validate the effectiveness of the proposed methods.

Strengths

1. This paper is well-written. The problem this paper focuses on is important, and the proposed method is interesting. 2. The experiments are sufficient, and the conclusion is convincing.

Weaknesses

1. In this paper, the theoretical analysis (e.g., theorems) is missing. I think it is a suggested part, especially for a top machine learning conference like NeurIPS. More specifically, your proposed method still needs many iterations including calling functions to get hard labels. Even though empirical results shown in Figure 2, the reason about why the proposed method reduces the number of queries. A theriacal analysis about it is suggested. The analysis of computational complexity is also suggested especially the proposed method is described as practical. 2. The fluency of sentences seems not to be considered. When we replace the words in the sentence, we should consider if the remaining sentence is still fluent. Correct me if I am wrong.

Questions

1. Just curious. Did authors consider using ChatGPT to help you generate some similar sentences?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

The authors provided the description of limitations such as potential negative societal impact of their work.

Summary

This paper presents a black-box adversarial attack method that can create high-quality adversarial samples without accessing the predictive probability/gradients of the victim model. The approach is based on synonyms substitution. In the attack framework, this paper also proposes some tricks to reduce the query number and increase the semantic similarity. Experimental results demonstrate the effectiveness of the proposed attack, indicating further attention is needed to look into this adversarial problem.

Strengths

This paper looks into an important and interesting research problem. Black-box textual adversarial attack is a challenging problem due to the discrete nature of the text. This paper presents a concrete approach that can effectively address this problem, crafting high-quality adversarial samples with high semantic similarity and fewer query numbers. Experimental results show that this approach is more effective than previous approaches, like LeapAttack.

Weaknesses

Please correct me if I have some misunderstanding of the paper. 1. I don't see too much novelty in the proposed approach compared to previous work [1]. The basic intuitions are both first constructing a successful but low-quality adversarial sample, and then iteratively performing multiple rounds of substitution to improve the quality. If I understand correctly, only the reverse searching process is optimized in this paper. 2. I have some problems with the practical issues of the proposed approach and experimental settings, as indicated in this paper [2]. First, why do attackers want to attack a new classification model, or the sentiment analysis model you adopt in the experiments? What is the motivation and what benefits can they get? Please justify the reasonability of the considered experimental settings. Second, why do the attackers want to craft some high-quality samples that retain high similarity compared to the original ones? The goal of attacking is to bypass the detection system and retain only the adversarial meaning. So what is the motivation of the attackers to spend a huge amount of time doing engineering to retain the meaning of the whole sentence to the maximum? 3. For the evaluation, human annotation is important to verify the validity of adversarial samples, since many adversarial samples may be invalid due to the change in core semantics meaning, but they still retain high similarity computed by neural models. 4. In the experiments, only some old-school models are considered, such as BERT, WordCNN, LSTM. The results from these models don't have too much significance since none of them are frequently employed nowadays. The experiments should be conducted on some more advanced models, like T5, DeBERTa, and also may consider some other paradigms, like few-shot, and zero-shot inference via GPT. [1] Generating Natural Language Attacks in a Hard Label Black Box Setting. Rishabh Maheshwary, Saket Maheshwary, Vikram Pudi. AAAI [2] Why Should Adversarial Perturbations be Imperceptible? Rethink the Research Paradigm in Adversarial NLP. Yangyi Chen, Hongcheng Gao, Ganqu Cui, Fanchao Qi, Longtao Huang, Zhiyuan Liu, Maosong Sun. EMNLP

Questions

Please see the second point in the Weakness section.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

This paper has a limitation section that effectively addresses the limitations of the proposed approach.

Summary

- The authors consider a problem of black-box hard-label adversarial attack, which adversarially perturbs the input text while having access only to the output label of the victim model. - They propose HQA-Attack method which can successfully perturb the input text into the adversarial text with higher semantic similarity and lower perturbation rate compared to the baseline hard-label adversarial attack methods on text data under a tight query budget. - The process can be summarized into three components: 1. Random initialization to find an adversarial example. 2. Sequentially substitutes original words back as many as possible, beginning from the adversarial example found in step 1. 3. Further optimization step to improve semantic similarity and perturbation rate. - The experimental results show the HQA-Attack's superiority in hard-label adversarial attacks.

Strengths

- The authors conduct experiment on various datasets and victim models containing commercial classification system such as google cloud and alibaba cloud. - The second step of HQA-Attack, which greedily substitute original words back, is very simple and intuitive.

Weaknesses

- The attack space is limited. HQA-Attack seems to construct a word substitution candidate set of a word without considering any knowledge from the sentence. - The justification of the third step seems poor. I think more theoretical or empirical evidence that supports the necessity of the third step should be added.

Questions

- Soft-label adversarial attack methods such as TextFooler, BERT Attack, and BAE considers the word substitution set which depends on the whole sentence. In my understanding, HQA-Attack can be extended to more flexible attack spaces equipped with sentence-dependent word substitution sets. Can you provide some experimental results on this setting? - The third step of HQA-Attack is not intuitive to me. Can you provide the theoretical or empirical results that show the importance of the third step? For example, I want to see an ablation result with and without the third step. - In BBA, they first find the adversarial example with Bayesian Optimization and conduct a "post-optimization" process which further optimizes near the adversarial example to reduce the perturbation size based on trained Gaussian Process (GP). While this method is solving the soft-label adversarial attack problem, the idea of using GP to consider previous evaluation history seems still valid in the hard-label attack setting. Can you provide a comparison of HQA-Attack with a simple GP-based hard-label attack? [TextFooler] Is BERT Really Robust? Natural Language Attack on Text Classification and Entailment, Di Jin et al., AAAI 2020 [BERT Attack] BERT-ATTACK: Adversarial Attack against BERT using BERT, Linyang Li et al., EMNLP 2020 [BAE] BAE: BERT-based Adversarial Examples for Text Classification, Siddhant Garg et al., EMNLP 2020 [BBA] Query-Efficient and Scalable Black-Box Adversarial Attacks on Discrete Sequential Data via Bayesian Optimization, Deokjae Lee et al., ICML 2022

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors provide some broader impacts and limitations in Appendix F.

Summary

This paper proposes a new hard-label black-box attack on textual data that aims to improve the performance on semantic similarity and perturbation rate. The main novel techniques are word back-substitution and a new strategy for optimizing the adversarial example. Evaluations on 5 classification tasks, 3 inference tasks, and 2 online APIs show that the proposed attack obtains better quality than 3 previous attacks. Evaluations also include the attack's convergence, the performance on robust models, and several ablation studies.

Strengths

### Originality * **Novel attack.** The attack techniques are overall novel to my knowledge. The proposed strategy to optimize quality is new. ### Quality * **Solid methodology.** The overall attack design is solid, and the new optimizing strategy is well-developed. * **Comprehensive evaluations.** The experiments are comprehensive. I appreciate the several tasks and the inclusion of robust models and ablation studies. ### Clarity * **Good presentation.** The paper is generally well-written and the methodology is largely easy to follow with some focus. ### Significance * **Improved performance regarding quality.** It is good to see that the proposed optimization strategy can improve the adversarial example's quality in all settings. The convergence behavior is also better than previous attacks.

Weaknesses

### Originality **Q1: Unclear novelty in the word back-substitution component.** I was a bit confused by the contribution in Section 4.2. From L149-153, it seems that previous attacks only compute the similarity gain once and hence determining the replacement order, so the initially computed order is inaccurate after the adversarial example has applied any replacement. However, isn't this the same case for Equation (3) and Algorithm 1, where the order is computed once (Algorithm 1, L2-7), and then the attack applies replacements one by one (Algorithm 1, L10-17)? Basically, it is unclear how the proposed method is different from previous attacks, and how it would be able to solve this problem. If there is indeed a difference, what if previous attacks do recompute this order at each iteration? Would they have better performance, or is there an inherent challenge in their methodology? From the current presentation I could not see any challenge, as this computation is generally offline and does not need model queries. In other words, in this part of the question, it is hard to evaluate the novelty between "naively recomputing the order" and "recomputing the order with the proposed strategy." ### Quality **Q2: The qualitative results are somewhat insufficient.** While the quantitative results in Section 5 are good and promising, the current qualitative results are a bit insufficient for demonstrating the improved quality. Currently, only three sentences are provided in the supplementary, and it would be hard to tell if they have covered the general sense of improved quality. Since this paper's main claim is the improved quality of adversarial examples, it might be important to have more examples of the adversarial examples and, more importantly, the comparisons between different attacks. It is not intuitive to tell the difference between 5-10% of similarity or perturbation rate improvement. For example, would there be an observable quality improvement if the semantic similarity was improved by 10%? Note that I have no concerns with the chosen metrics, but the paper can be strengthened if more qualitative results are provided. **Q3: The choice of $k$.** At L259, the number of synonyms sampled for direction estimation is set to $k=5$. I am curious if this value would be too small, given that there might be tens of synonyms. I also noticed that the results are constant regarding $k\in\{5, 10, 15\}$ so $k=5$ seemed to be sufficient. Is there any explanation for why this is sufficient? In this case, it might be informative to add results for $k\in[1, 4]$ where the number of samples is insufficient. ### Clarity **Q4: Confusion in determining the optimizing order.** It is not very straightforward why Section 4.3.1 determines that the most similar word pair get optimized first. In Equation (6), the word $w_i$ gets sampled with a higher probability if $d_i$ is small, meaning the cos similarity between (the embeddings of) $w_i$ and $w^\prime_i$ is high. Can you clarify why it starts from similar words (rather than non-similar words), and replace such similar words with synonyms that again aim to improve semantic similarity? **Q5: Confusion in the final updating step.** In L224-225, why the replacement word is chosen from $S(w_i)$, yet the similarity was compared pertaining $\bar{w}_i$? **Minor Points:** * Missing specification of the synonyms set. It is unclear how the synonyms were generated and how large it is (relevant to Q3). * The methodology description in Section 4.3.2 is a bit convolved. ### Significance **Q7: Used the same random initialization as previous attacks.** While the improvement in quality is promising, and this paper legitimately focuses on improving the quality, the task's performance is not reduced more than other attacks because they share the same initialization (source of the adversary). I am not penalizing for this point, but this is one aspect that limits the significance of this paper (compared with attacks that might also improve the attack success rate).

Questions

I am willing to raise my score if Q1-Q2 (major) and Q3-Q5 (intermediate) are sufficiently clarified.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

This paper proposes a novel and effective methods for black-box textual adversarial attacks. The proposed framework focuses on maximizing the similarity of the adversarial texts and the original texts through shrinking the perturbation. In the experiments, the authors prove that the proposed methods can significantly improve the quality of generated adversarial examples according to the metrics of text similarity and perturbation rate. The authors also conduct comprehensive ablation studies to show the effectiveness of different module in the proposed framework.

Strengths

1. This paper accurately points out the limitations of the previous work on textual adversarial attacking, and it proposes a simple and effective methods to improve the quality of generated adversarial examples. 2. The experiments are exhaustive and convincing. The selection of evaluation benchmarks is comprehensive, and it also evaluate on real-world APIs, which further illustrate the practicability of the proposed methods. According to the results, the proposed methods can significantly improve the quality of adversarial examples. In addition, the ablation study also interprets the effectiveness of different module of the attacking framework.

Weaknesses

1. It lacks human evaluation to evaluate the quality of the generated adversarial examples. The human evaluation is claimed critical in previous textual adversarial works, since some slight perturbations that changes the semantic of the original texts may not be reflected through automatic evaluation such as text similarity and perturbation rate. (The authors have added the human evaluation experiments.) 2. It would be helpful for us to better understand the mechanism of adversarial attacks if the authors can add some analysis of why the adversarial examples can successfully full the models / what triggers the wrong predction / whether different victim models make different mistakes or same mistakes.

Questions

1. The authors should add human evaluation experiments about the quality of generated adversarial examples.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors should address the limitation of the proposed framework in the conclusion section.

Thanks for your insightful reviews

Dear reviewers, Thanks for your insightful reviews. It appears that we have received a little bit of divergent reviews. While most reviewers are positive toward the paper, some reviewers have raised questions regarding the contributions and experiments. Now that the authors have provided the detailed responses for each review, we kindly request those of you who haven't read the response to take a moment to review these materials and determine if they effectively address the concerns you raised. Best, AC

Thanks for your detailed response

Dear authors, Thanks for your detailed response. I think your response has addressed some of the reviewer's concerns. Best, AC

Thanks for your detailed response.

Dear authors, Thanks for your detailed response. I think your response has addressed some of the reviewer's concerns. Best, AC