HQA-Attack: Toward High Quality Black-Box Hard-Label Adversarial Attack on Text
Authors: Han Liu
Zhi Xu
Xiaotong Zhang
Feng Zhang
Fenglong Ma
Hongyang Chen
Hong Yu
Xianchao Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: High-quality adversarial example
Black-box hard-label textual adversarial attack

Abstract: Black-box hard-label adversarial attack on text is a practical and challenging task, as the text data space is inherently discrete and non-differentiable, and only the predicted label is accessible. Research on this problem is still in the embryonic stage and only a few methods are available. Nevertheless, existing methods rely on the complex heuristic algorithm or unreliable gradient estimation strategy, which probably fall into the local optimum and inevitably consume numerous queries, thus are difficult to craft satisfactory adversarial examples with high semantic similarity and low perturbation rate in a limited query budget. To alleviate above issues, we propose a simple yet effective framework to generate high quality textual adversarial examples under the black-box hard-label attack scenarios, named HQA-Attack. Specifically, after initializing an adversarial example randomly, HQA-attack first constantly substitutes original words back as many as possible, thus shrinking the perturbation rate. Then it leverages the synonym set of the remaining changed words to further optimize the adversarial example with the direction which can improve the semantic similarity and satisfy the adversarial condition simultaneously. In addition, during the optimizing procedure, it searches a transition synonym word for each changed word, thus avoiding traversing the whole synonym set and reducing the query number to some extent. Extensive experimental results on five text classification datasets, three natural language inference datasets and two real-world APIs have shown that the proposed HQA-Attack method outperforms other strong baselines significantly.

HQA-Attack: Toward High Quality Black-Box Hard-Label Adversarial Attack on Text
Han Liu
Zhi Xu Dalian University of Technology
Dalian University of Technology
Dalian, China
Dalian, China
1iu. han. dww@gmaillm....m com
xu. zhi duw@gmaillmll.... com
Xiaotong Zhang*
Feng Zhang
Dalian University Technology Dalian, China zxt. www.ddutttamal...mmmmmmmmmm com
Peking University Beijing, China zf eng. www.mmaaaaaaa.ammmmmmm com
Fenglong Ma
Hongyang Chen Zhejiang Lab Hangzhou, China dr h. wwwwhheee..c....oo org
The Pennsylvania State University Pennsylvania, USA fenglongspsu.edu
Hong Yu Dalian University of Technology Dalian, China
Xianchao Zhang
Dalian University of Technology Dalian, China xczhangodlut. edu. cn
hongyu@dlut.edi edu..utt.du..oom
Abstract
Black-box hard-label adversarial attack on text is practical and challenging task, as the text data space is inherently discrete and non-diffcrentiable, and only the predicted label is accessible. Research this problem is still in the embryonic stage and only a few methods are available. Nevertheless, existing methods rely on the complex heuristic algorithm unreliable gradient estimation strategy, which probably fall into the local optimum and inevitably consume numerous queries, thus are difficult craft satisfactory adversarial examples with high semantic similarity and low perturbation rate in a limited query budget. To alleviate above issues, we propose simple yet effective framework generate high quality textual adversarial examples under the black-box -bx hard-label attack scenarios, named HQA- Attack. Specifically, after initializing an adversarial example randomly, HQA-attack first constantly substitutes original words back as many as possible, thus shrinking the remaining changed
the perturbation rate. Then it leverages the synonym words to further optimize the adversarial example with the direction which can improve the semantic similarity and satisfy the adversarial condition simultaneously. In addition, during the optimizing procedure, it searches transition synonym word for each changed word, thus avoiding traversing the whole synonym set and reducing the query number to some extent. Extensive experimental results on five text classification datasets, three natural language inference datasets and two real-world APIs have shown that the proposed HQA-Attack method outperforms other strong baselines significantly.
*Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Introduction
Deep neural networks (DNNs) have achieved a tremendous success and are extremely popular in various domains, such as computer vision [3 35), natural language processing [31 15], robotics 26 and so on. spite of the promising performance achieved by DNN models, there are some concerns around their robustness, as evidence shows that even slight perturbation to the input data can fool these models into producing wrong predictions [0 19 I 5) and these perturbed examples are named as adversarial examples. Investigating the generation rationale behind adversarial examples seems a promising way to improve the robustness of neural networks, which motivates the research about adversarial attack. Most existing adversarial attack methods focus computer vision [3 36, 39] and have been well explored. However, the adversarial attack on text data is still challenging, not only the text data space is intrinsically discrete and con-differentiable, but also changing words slightly may affect the fluency in grammar and the consistency in semantics seriously.
Based on the accessibility level of victim models, existing textual adversarial attack methods can be categorized into white-box attacks 99 25 and black-box attacks [19] 41 20) For white-box attacks, the attackers are assumed to have full information about the victim model, including training data, model architecture and parameters. Therefore, it is easy to formulate this type of attack as an optimization problem and utilize the gradient information to generate adversarial examples. However, as most model developers are impossible to release all the model and data information, white-box attacks seem excessively idcalistic and cannot work well in real-world applications. For black-box attacks, the attackers assumed to have only access the predicted results, e.g., confidence scores or predicted labels, which seem more realistic. Existing black- box textual attack methods can be For soft-label methods, they require the victim model to provide the confidence scores to calculate the importance of each word, and then replace words sequentially until an adversarial example is generated. However, is also impractical as most real APIs do not allow users to access the confidence scores. For hard-label methods, they only need know the predicted labels of the victim model to fulfill the attack task, thus are more practicable and promising.
divided into seft-label setting 22 6 [4] and hard-label setting 23
38 37
Only handful of methods proposed to deal with the black-box hard-label textual ad- versarial attack task, which mainly rely heuristic- based [23] or gradient- based strate- gies [8 37). Specifically, HLGA [23] is the first hard-label adversarial attack method, which leverages population-basse heuristic optimiza- tion algorithm to craft plausible and semanti- cally similar adversarial examples. However, as it requires a large population of adversarial can- optimization strat- egy is easy to fall into the local optimum, HLGA inevitably consumes numerous query numbers. TextHoaxer (38) formulates the budgeted hard- label adversarial attack task on text data as a gradient-based optimization problem of pertur- bation matrix in the continuous word embedding space. LeapAttack (37 utilizes the gradient- based optimization by designing a novel mecha- nism that can interchange discrete substitutions and continuous vectors. Although these gradient- based methods improve the query efficiency to some extent, they still need some unnecessary queries caused by inaccurate gradient estimation. Furthermore, in tight budget scenarios, query inefficiency will directly bring about serious side effects on the semantic similarity and perturbation rate.
0.95
+
Initiaizationn
0.90
Decision boundary
Substituting original
0,80
Optimiatng
0.70
adversrid reample
(B)
Simllarity
Sshypse
didates and population-basee
Figure 1: The overview of HQA HQA-Attack. (A) Generate an adversarial example x' by initialization. (B) Update r1 & & T)) by substituting original words back. (C) Obtain x'41 by optimizing the adversarial example. The similarity isohypse is line which consists of points having the equal semantic similarity with the original example
To alleviate the above issues, we propose a simple yet effective framework for producing High Quality black-box hard-label Adversarial Attack, named HQA-Attack. The overview of HQA- Attack is shown in Figure [] By "high quality", it means that the HQA-Attack method can generate adversarial examples with high semantic similarity and low perturbation rate under tight query budget. Specifically, HQA-Attck first generates an adversarial example by initialization, and then

---

sequentially substitutes original words back as many passible, thus shrinking the perturbation rate. Finally, it utilizes the synonym set further optimize the adversarial example with the direction which can improve the semantic similarity and satisfy the adversarial condition simultaneously. In addition, to avoid going through the synonym set, it finds a transition synonym word for each changed word, thus reducing the query number to a certain extent. Experimental results on eight public benchmark datasets and two real-word APIs (Google Cloud and Alibaba Cloud) have demon- strated that HQA-Attack performs better than other strong baselines in the semantic similarity and perturbation rate under the same query budget. The source code and demo are publicly available at https://github.com/ff
2 Related Work
2.1 Soft-Label Textual Adversarial Attack
Adversarial attacks in soft-label settings rely on the probability distribution of all categories to generate adversarial examples. A series of strategies [16. 21 24 utilize the greedy algorithm to craft adversarial examples, which first determine the word replacement order and greedily replace each word under this order. TextFooler [16] first determines the word replacement order according to the prediction change after deleting each word, and then replaces words back according to the word importance until adversarial examples are generated. Similarly, TextBugger [2]] calculates the importance of sentences and the importance of words respectively by comparing the prediction before and after removing them. In addition, there some methods [40 [] which use combinatorial optimization algorithm to generate adversarial examples.
2.2 Hard-Label Textual Adversarial Attack
Adversarial attacks in hard-label settings only allow to access the predicted label, which seem more challenging and practical. HLGA (3 is the first hard-label textual adversarial attack method. It uses random initialization and search space reduction to get an incipient adversarial example, and then uses the genetic algorithm including mutation, selection and crossover three operations to further optimize the adversarial example. Although HLGA generate adversarial examples with high semantic similarity with the original example and low perturbation rate, it needs to maintain large candidate set in each iteration, which wastes large number of queries. To alleviate this issue, TextHoaxer (38) uses the word embedding space to represent the text, and introduces a perturbation matrix and a novel objective function which consists of a semantic similarity term, pair-wise perturbation constraint and a sparsity constraint. By using the gradient- based strategy to optimize the perturbation matrix, TextHoaxer can generate appropriate adversarial examples another gradient-based method. After random initialization, it optimizes the adversarial example by constantly moving the example closer to the decision boundary, estimating the gradient and finding the proper words to update the adversarial example. In Appendix K, we further discuss some potential application scenarios about hard-label textual adversarial attack.
tight budget. LeapAttack (37) is
Problem Formulation
In this paper, we focus on the task of black-box hard-label textual adversarial attack, i.e., attackers can only access to the predicted label from the victim model generate adversarial examples. Specifically, given an original ex- ample x = [wn, W2 ..., wr,] with the ground truth label y, where w, is the i-th word, and n is the total number of words in æ. This task aims to construct an adversarial example x' = [w] w/y.... ..., w']] through replacing the original
Table 1: Symbol explanation.
Symbol
Explanation
æ x' 2/
original example i [us u2, ..., wn] the adversarial example x - [wo, way w/]] the adversarial example in the 1-th step the transition word associated with ws the updating direction the word vector of w. the victim model the true label of the synonym set of w;
u
f
y/
S ((x))
a' (wx)
the example after replacing the i-th word of x'' with ws
Sim(;)) (:))
the similarity function between sentences
3

---

word with a synonym w/ in the synonym set S(w;) which includes w; itself, thus misleading the victim model f to output an incorrect prediction result:
f(x') * f(x) = y,
(I)
where Eq. T can be seen as the adversarial condition. There may exist several adversarial examples which can satisfy Eq. (I), but an optimal adversarial example x* is the one that has the highest semantic similarity with the original example among all the candidates. Formally.
x arg max Sim(x, s.t. f(x') # f(z),
where Sim(r, x²) is the semantic similarity between a and x'. Table | summarizes the symbol explanation in detail.
4
The Proposed Strategy
4.1
Initialization
To fulfill the black-box hard-label textual adversarial attack task, we follow previous works [23 38 37 to first utilize random initialization to generate an adversarial example. Specifically, considering each word to; whose part-of- (POS) is noun, verb, adverb and adjective in the original example x, we randomly select a synonym w/ from the synonym set S(w;, of w, as the substitution of w; and repeat this procedure until the generated adversarial example x' satisfies the adversarial condition.
Obviously, using random initialization to generate the adversarial example usually needs to change multiple words in the original example, thus necessarily leading to the low semantic similarity and large perturbation rate. To alleviate the above issue, we attempt to iteratively optimize the semantic similarity between the original example and the adversarial example in the t-th iteration x', where 1 & & < T and T is the total number of iterations. Furthermore, given an adversarial example z', we can generate the adversarial example 4'41 by the following steps. (I) Substituting original words back; (2) Optimizing the adversarial example.
4.2 Substituting Original Words Back
In order to improve the semantic similarity of the generated adversarial example, previous works first use the semantic similarity improvement brought by each original word as measure to decide the replacement order, and then continually put original words back in each iteration. It means that in each iteration, by going through each word in the adversarial example, the semantic similarity improvement is only calculated once, and the replacement order is determined beforehand. However, making each replacement with the original word will change the intermediate generated adversarial example, thereby affecting the semantic similarity between the original example and the intermediate generated adversarial example, so just calculating the semantic similarity improvement at the beginning of each iteration to decide the replacement order is inaccurate.
23
To address the above problem, we propose to constantly substitute the original word which can make the intermediate generated adversarial example have the highest semantic similarity with the original example until the adversarial condition is violated. Specifically, given the original sample [1, u2...., W.,] and the adversarial example x = [w[, w?,..., w/, in the t-th iteration, we can substitute original words back with the following steps.
1. Picking out an appropriate substitution word w. from x with the following formula:
W arg max Sim =((ww)) C(f, xf(w)))
(3)
where Sim(æ 2 (w:)) is the semantic similarity between x and vf(ww), and xf(w:) is the example obtained by substituting the corresponding word wi with w,. C(f. x, (w;)) is two-valued function defined as:
(1, to f(x) (z((ww:))
f(x) # f(a((w:))
C(S, x(((w))
where f denotes the victim model. C equals if f(x) * f(x((w:)), and 0 otherwise.

---

2. If C(f. (. 1, it indicates that (((w)) can attack successfully. We substitute the corresponding original word in z/ with Wae and repeat the above step.
3. If ((ff,,,a/((( O, indicates that 2f(w²) cannot satisty the adversarial condition. We terminate the swapping procedure, and return the result of the previous step.
After the above procedure, we can obtain new adversarial example z which can retain the original words as many as possible, thus improving the semantic similarity and reducing the perturbation rate. The algorithm procedure is shown in Appendix A, and the analysis of computational complexity and query numbers shown in Appendix C.I.
4.3 Optimizing the Adversarial Example
To further ameliorate the quality of the generated adversarial example, we optimize the adversarial example by leveraging the synonym set of each word. One may argue that we could directly traverse the synonym set to seek out the most ideal synonym word which has the highest semantic similarity and satisfies the adversarial condition simultaneously. However, in most real-world application scenarios, the query number is usually limited. To avoid going through the synonym set, we propose to optimize the adversarial example with the following two steps. (1) Determining the optimizing order; (2) Updating the adversarial example sequentially. The analysis of computational complexity and query numbers is shown in Appendix C.2.
4.3.1 Determining the Optimizing Order
In this step, aim to determine suitable optimizing order. To ensure the diversity of the gener- ated adversarial example, we utilize the sampling method to determine the optimizing order. The probability distribution used by the sampling method is generated follows. For w/ in xr, and w; in x, we first use the counter-fitting fittinn word vectors (27] to obtain their corresponding word vectors, and calculate the cosine distance between them as follows:
d; - cos( (w, V.!))
(5)
where Vm; and Vwn denote the word vectors w; and w/ respectively. cos(..) is the cosine similarity function. Then we compute the probability associated with the position of w; in x with the following formula:
2- d3
Pr
(2-12-44
(6)
where m is the total number of changed words between x and æ. According to the probability distribution, we can obtain the optimizing order for x/c-
4.3.2 Updating the Adversarial Example Sequentially
According the optimizing order, we update the adversarial example with the synonym set se- quentially. In particular, for the adversarial example z/ in the t-th iteration, we update it with the following steps. (1) Finding the transition word; (2) Estimating the updating direction; (3) Updating the adversarial example.
Finding the transition word. This step aims to search a reasonable transition word, thus avoiding traversing the synonym set for each changed word. Given the adversarial example at [w', "w/,,//,-.. w/...., wo/] and the current optimized word w/. we randomly select r synonyms from S(w:) to construct the set {w(") w((²) .... w." (r(")) }. use each element in to replace w/ in a/e and then obtain the transition word w; with the following formula:
W. = arg max Sim(a, 2(((1())) C( (( RR
where 2/ (u((()) is the example obtained by substituting the corresponding word w/ in ay with .)) E R. According to Eq. 7 we can get that can make the example adversarial and improve the semantic similarity to some extent, while avoiding going through the synonym set. Furthermore, can search other possible replacement words around the transition word w.
5

---

Estimating the updating direction. As the transition word üi originates from randomly generated synonym set, we can further optimize with a reasonable direction. Specifically, we first generate the set K = [w (1) wi Wi (k)) by randomly sampling k synonyms from ((w;), and then obtain the set M (m)( ( ),... 24 (1, where x/ ( is the example by replacing wn in z with ( By calculating the semantic similarity between each element in M and the original text we can get the set S (s(1) s(2), ..... "e.,,...' )( where واك) = Sim(2, z xx((x))) is the semantic similarity between x and x4 <<(ww))) In the similar manner, the semantic similarity between and (w; can be computed 8; Sam(a, ( (T::).
Intuitively, if (نو 8, 0, indicates that pushing the word vector ra; towards e increase the semantic similarity, i.e., 1 w Vni, is the direction which can improve the semantic similarity. And if (03) 5, O, moving the word vector along the inverse direction of w Vm, can improve the semantic similarity. Based on the above intuition, we estimate the final updating direction u by weighted averaging over the k possible directions. Formally.
"nf tends to
k u a
Σ
a U..))
(8)
where 0j is the corresponding weight associated with the direction v (i Ums. and it can be calculated by a, = (80) - s,)/ Σ (s(0) - s:l.
Updating the adversarial example. Due to the discrete nature of text data, we need to use the updating direction
pick out the corresponding replacement word w, from S(w;), where W; the word which has the maximum cosine similarity between u and væ, - Vaz and ensures that 2; ( (w;) satisfies the adversarial condition. After obtaining w. we can generate 2 in the optimizing order sequentially. In addition, to reduce the number of queries and shrink the perturbation rate, when implementing the program, we first use x to initialize 4'411 and then replace the word Wi one by one until 1 satisfies the adversarial condition.
4.4
The Overall Procedure
The detailed algorithm procedure of HQA-Attack is given in Appendix B. In particular, HQA-Attack first gets the initial adversarial example by random initialization. Then it enters into the main loop. In each iteration, HQA-Attack first substitutes original words back, then determines the optimizing order, and finally updates the adversarial example sequentially. In addition. we provide some mechanism analysis of HQA-Attack from the perspective of decision boundary in Appendix D.
5
Experiments
5.1
Experimental Settings
Datasets. We conduct experiments on five public text classification datasets MR [28), AG's News Yahoo [2).
42).
Yelp 42), IMDB (22), and three natural language inference datasets SNLI [3].
MNLI 333 mMNLI
33
The detailed dataset description is shown in Appendix E. We follow the
previous methods 23
38
37
to take 1000 test examples of each dataset to conduct experiments.
Baselines, We compare with three state-of-the-at black-bon hard-label textual adversarial attack
methods: (1) HLGA 23 is a hard-label adversarial attack method that employs the genetic algorithm to generate the adversarial example. (2) TextHoaxer (38] is a hard-label adversarial attack method that formulates the budgeted hard-label adversarial attack task text data gradient-based optimization problem of perturbation matrix in the continuous word embedding space. (3) LeapAttack (37] is a recent hard-label adversarial attack method, which estimates the gradient by the Monte Carlo method.
Evaluation Metrics. We use two widely used evaluation metrics semantic similarity and perturbation rate. For semantic similarity, we utilize the universal sequence encoder [4] to calculate the semantic similarity between two texts. The range of the semantic similarity between [0, 1]. and the larger semantic similarity indicates the better attack performance. For perturbation rate, we use the ratio

---

of the number of changed words over the number of total words in the adversarial example, and the lower perturbation rate indicates the better results.
Victim Models. We follow [23 38 37 to adopt three widely used natural language processing
models victim models: BERT 8 WordCNN 177. and WordLSTM B All the model
parameters are taken from the previous works [23 38 37 We also attack some advanced models like T5 (30] and DeBERT (12), and the results are shown in Appendix To further verify the effectiveness of different algorithms in real applications, we also attempt to use Google Cloud API
(https://cloud.g google. gwwgle.com//atue.....ooooooooooo www.//otoralllaanneennnee -laguuugg and Alibaba Cloud API /tttps:/ai..allyum.oom wwwiaa..cco//iiii. as the victim models.
Implementation Details. For the random initialization, we employ the same method used in previous methods 23 38 37). After the initialization, we follow 23 38 to perform a pre-processing step to remove the unnecessary replacement words. For the hyperparameters, we consistently r and k = 5 for all the datasets. The detailed parameter investigation is provided in Appendix G. In addition, during the optimization procedure, if we re-optimize the same adversarial example three times and no new better adversarial examples are generated, we randomly go back to the last three or four adversarial example. We do not re-optimize an adversarial example more than two times. For fair comparison, we follow [23] 38 37 to generate 50 synonyms for each word by using the counter- fitting word vector. We also conduct experiments based on BERT-based synonyms, and the results are shown in Appendix H.
5.2 Experimental Results
5.2.1 Comparison on Semantic Similarity and Perturbation Rate
We exactly follow the previous work [38] to set the query budget to 1000, i.e., the number of allowed queries from the attacker is 1000. As different algorithms the same random initialization step which determines the prediction accuracy after the adversarial attack, so different algorithms have the same prediction accuracy. Our goal is generate the adversarial examples with higher semantic similarity and lower perturbation rate. Tables 2 and 3 report the experimental results when attacking text classification models. The best results are highlighted in bold.
As shown in Tables and 3 when the query limit is 1000, for different datasets and tasks, HQA- Attack can always generate adversarial examples that have the highest semantic similarity and the lowest perturbation rate. Specifically, for the dataset MR with short text data, HQA-Attack increases the average semantic similarity by 6.9%, 6.5%, 6.9% and decreases the average perturbation rate by 0.777% 0.832%, 0.983% compared with the second best method when attacking BERT, WordCNN and WordLSTM respectively. For the dataset IMDB with long text data, HQA-Attack increases the average semantic similarity by 4.5%, 3.4%, 2.7% and decreases the average perturbation rate by 1.426%, 0.601 %. 0.823% compared with the second best method when attacking BERT, WordCNN and WordLSTM respectively. For the dataset with more than two categories like AG, HQA-Attack increases the average semantic similarity by 10.6%, 8.8%, 11.6% and decreases the average perturbation rate by 4.785% 3.885%. 5.237% compared with the second best method when attacking BERT, WordCNN and WordLSTM respectively. All these results demonstrate that HQA-Attack can generate high- high-quality adversarial examples in the bight-budget hard-label setting.
5.2.2 Comparison Attack Efficiency
The attack efficiency is an important criterion evaluating the attack performance, as most DNN-based NLP platforms the number of queries is limited. Therefore, We further compare the proposed HQA-Attack with two latest methods TextHoaxer and Ltap under different query budgets [100, 300, 500, 700, 1000] on text classification datasets. As shown in Figure 2 with the query budget increasing, the average semantic similarity of all the methods keeps increasing and the average perturbation rate of all the methods keeps decreasing, In terms of semantic similarity and perturbation rate, HQA-Attack always performs much better than other methods in all the budgets. These results further validate that our proposed HQA-Attack has the ability generate adversarial examples with higher semantic similarity and lower perturbation rate in different budget limits.
5.2.3 Attack Real-World APIs
7

---

Table 2: Comparison of semantic similarity (Sim) and perturbation rate (Pert) with the budget limit of 1000 when attacking text classification models. Ace stands for model prediction accuracy after the adversarial attack, which is determined by the random initialization step and the same for different adversarial attack models.
BERT
WordCNN
WordI_STW STM
Dataset
Method
Sim Ac)(%)
Pert(%)
Aco(%)
Sim(%) (%) Pert(%) Acc(%) Sim
Pert(%)
HIGA
62.5
14.532
64.4
14.028
63.5
14,462
TextHoaxer
67.3
11,905
68.6
12.056
67.3
12.324
MR
1.0
0.7
0.7
LeapAttack
61.6
14.643
63.2
14.016
61.3
14.435
IIQA-Attack
74.2
11.128
75.1
11.224
74.2
11.341
HLGA
60.5
17.769
71.9
13.855
61.8
17.890
TextHoaxer
63.2
15.766
73.9
12.716
63.8
16.520
AG
2.8
1.4
5.7
LeapAttack
62.6
16.143
72.0
12.827
63.0
17.028
HQA-Attack
73.8
10,981
82.7
8.831
75.4
11,283
HLGA
68.7
7.453
71.9
8,564
63.8
9.531
TextHoaxer
70.2
6.841
74.8
7.740
67.0
8,502
Yahoo
0.8
0.8
1.9
LeapAttack
66.7
7.448
74.3
7.842
64.7
9,095
HQA-Attack
76.4
5.609
82.4
6.132
73.9
6.645
HLGA
71.9
10.411
79.7
9.102
78,8
8.654
TextHoaxer
73.8
9.585
81.3
8.545
80.4
8.108
Yclp
0.6
0.6
3.2
LeapAttack
72.7
9.877
80.1
8.816
79.6
8.111
HQA-Attack
81.9
6.756
87.8
6.312
86.7
5.786
HLGA
83.2
5.571
87.6
4,464
87.6
4.464
TextHoaxer
84.7
5,202
88.8
4.197
88.8
4.197
IMDB
0.1
0.0
0.3
LeapAttack
84.0
5.041
89.7
3.886
89.0
4.021
HQQ--Atack
89.2
3.615
93.1
3.285
91.7
3.198
Table 3: Comparison of semantic similarity (Sim) and perturbation rate (Pert) with the budget limit of 1000 when attacking natural language inference model (BERT).
SNLI
MNLI
mMNLI
Method
Acc(%)
Sim (+)
Pert(%) Acc(%) Sim(%) Pert(%) Acc(%) Sim(%) Pert (%))
HILGA
35.9
18.510
49.6
14.498
50.7
14.349
TextHoaxer
38.7
16.615
52.9
12.730
54.4
12.453
1.3
2.9
1.7
Attack
35.0
19,905
49.1
15.728
50.2
15.135
HQA-Attack
54.2
15.958
64.7
12.093
65.4
11,502
To further verify the effectiveness of different algorithms, we attempt to TextHoaxer, LeapAttack and HQA-Attack to attack two real-world APIs: Google Cloud (https://cloud. wwwp:odddgoggg...ooooo google.com//ntural language) and Alibaba Cloud hntpss//ai.aliyumn com/nlp). httm///.llllyll..olll..........) To further evaluate the fluency of the generated adversarial examples, we add the perplexity (PPL) as the additional evaluation metric which is calculated by using GPT-2 Large [29]. The lower PPL indicates the better performance. As Google and Alibaba only provide limited service budgets, we select 100 examples from the MR dataset whose lengths are greater than or equal to words to perform experiments, and restrict that each method can only query the API 350 times. 4sblessshoss the results of TextHoaxer, LeapAttack and HQA-Attack. It can seen that compared with second best results, HQA-Attack increases semantic similarity 5.7%, 5.1 5.1%, decreases the perturbation rate 0.062%, 0.007% and decreases the PPI. 9, 6 on Google Cloud and Alibaba Cloud respectively. We also compare the performance of TextHoaxer, LeapAttack and HQA-Attacl in different budget limits. The results are shown in Figure
Table 4: Comparison of semantic similarity and perturbation rate when attacking against real-world APIs.
Google Cloud
Alibaba Cloud
API
Sim(%) Pert(()
PPI.
Sim(%)
Pert(%)
PPL.
TextHoaxer LeapAttack
76.1
7.179
253
78.3
6.190
261
73.2
10.699
295
77.7
7.198
285
HQA-Attack
81.8
7.117
244
83.4
6.183
255

---

18k Ittaat
Lesalctsk
Lesalcteck
Lecalited
Fectllisier
(a) MR (Sim)
(b) AG (Sim)
(c) Yahoo (Sim)
(d) Yelp (Sim)
(e) IMDB (Sim)
Jctuck
Ircenng Bare
Teethare
Badpets
Budgets
Dudprta
Sonber
Dudgrts
Burgets
(I) MR (Pert)
(g)
AG (Pert)
(h) Yahoo (Pert)
Yelp (Pert)
(i) IMDB (Pert)
Figure 2: Comparison on semantic similarity and perturbation rate in different budget limits when
attacking against BERT.
Seaurt Stellarity
IgkeAttack
Nuturrant Race
LeepAttook
Leaptttack
TextHoeser
Tortifaazrr
IRt-Attack Lasphttack
HMA-Attook
LeepAttach
Tertllaser
TestHouser
Rumber of Budgetx
10
30
30
Maber Budgets
300
(a) Google (Sim)
(b) Google (Pert)
(c) Alibaba (Sim)
(d) Alibaba (Pert)
Figure 3: Comparison of semantic similarity and perturbation rate in different budget limits when attacking against real-world APIs.
Table 5: Human evaluation results in average classification accuracy($))
Dataset
HLGA
TextHoaxer
LeapAttack
HQA-Attack
MR
82.6
84.8
84.0
87.4
IMDB
84.4
85.4
85.0
88.6
3 We can get that HQA-Attack can have the higher semantic similarity and lower perturbation rate most cases, which further demonstrates the superiority of HQA-Attack over other baselines.
5.2.4 Human Evaluation
We have conducted the human evaluation experiments on the BERT model using HLGA, TextHoaxer, LeapAttack and HQA-Attack for the MR and IMDB datasets. Specifically, for each dataset, first randomly select 50 original samples, and use each adversarial attack method to generate the corresponding 50 adversarial examples respectively. Then we ask 10 volunteers to annotate the class labels for these samples, and calculate the average classification accuracy (Acc) for each method. Intuitively, if the accuracy is higher, means that the quality of the generated adversarial examples is better. The Acc(%) results of clean examples are 94.2% and 93.6% for MR and IMDB respectively. And the results of adversarial examples are shown Table 5 The results show that the adversarial examples generated by HQA-Attack are more likely to be classified correctly, which further verifies the superiority of Htt-kutack in preserving the semantic information.
5.2.5 Attack Models which Defend with Adversarial Training
With the development of the AI security, lot of works focus on defending against adversarial attacks. We further compare the attack performance when the victim model is trained with three effective adversarial training strategies HotFlip 9. SHIELD [18 and DNE 43). We select the BERT model as the victim model, set the query budget to 1000 and then perform experiments on the AG dataset. We also use the perplexity (PPL) as the additional evaluation metric to judge the fluency

---

Table 6: Comparison results of attacking models which defend with adversarial training.
HotFlip
SHIELD
DNE
Method
Acc(%) Sim(%) (%)
Pen((%) PPI. Acc(%) Sim(%) Pert(%) (%)
PPI. Acc(5%) Sim(%) Pert(()
PPI.
HLGA
55.8
17.185
59.8
15.206
565
58.6
14.132
444
TextHoaxer
55.5
17.145
463
67.8
12.312
469
66.5
11.517
363
21.7
12.6
18.6
LcapAttack
62.0
17.288
530
66.3
14,868
541
65.7
13.541
414
HQA-Attack
72.7
10.192
350
76.0
10.085
361
75.0
9.808
312
Table 7: Ablation study.
Random Initialization
w/o Substituting
w/ Optimizing
HQA-Attack
Dataset
Acc(%)
Sim (
Pert( %)
Sim %)
Pert(%)
Sim(%)
Pert(%)
Sim(%) (%)
Pert (6)
MR
0.7
18.2
39.234
74.4
12.638
74.2
11.673
75.1
11.224
AG
1.4
30.5
43.463
80.2
16.519
79.3
11.305
82.7
8.831
Yahoo
0.8
28.0
32.143
73.1
15.982
79.7
7.445
82.4
6.132
Yelp
0.6
18.3
38.595
71.6
19.342
85.2
7.883
87.8
6.312
IMDB
35.0
30.963
72.9
17.229
92.2
3,923
93.1
3.285
of the generated adversarial examples. Table shows the attack performance. We can observe that HQA-Attack can also obtain the best results compared with other strong baselines.
5.2.6 Ablation Study and Case Study
To investigate the effectiveness of different components, make the ablation study five text classification datasets when attacking WordCNN. The results are shown in Table 7 Random Ini- tialization means the adversarial examples generated only by the random initialization step. w/o Substituting means that the HQA-Attack model without the substituting original words back step. w/o Optimizing means that the HQA-Attack model which randomly selects word that keep the example adversarial as the replacement after substituting original words back without optimizing the adversarial example. easy to find that all modules contribute the model, which verifies that the substituting original words back step is useful and the optimizing the ad adversarial example step is also indispensable. To further demonstrate the effectiveness of our proposed word back-substitution strategy, we add some extra experiments in Appendix I. We also list some concrete adversarial exam- ples generated by HQA-Attack, which are shown Appendix These examples further demonstrate that our proposed HQA-Attack model can generate high-quality black-box hard-labe adversarial example with only a small perturbation.
Conclusion
In this paper, we propose a novel approach named HQA-Attack for crafting high quality textual adversarial examples in black-box hard-label settings. By substituting original words back, HQA- Attack can reduce the perturbation rate greatly. By utilizing the synonym set of the remaining changed words to optimize the adversarial example, HQA-Attack can improve the semantic similarity and reduce the query budget. Extensive experimental results demonstrate that the proposed HQA-Attack method can generate high quality adversarial examples with high semantic similarity, low perturbation rate and fewer query numbers. In future work, we plan to attempt more optimization strategies to refine the model, thus further boosting the textual adversarial attack performance.
Acknowledgments and Disclosure of Funding
The authors are grateful to the anonymous reviewers for their valuable comments. This work was sup- ported by National Natural Science Foundation of China (No. 62106035, 62206038, 61972065) and Fundamental Research Funds for the Central Universities (No. DUT2ORC(3)040 DUT20RC(3)666) and supported in part by Key Research Project of Zhejiang Lab (No. 2022P10AC01) and National Key Research and Development Program of China (2022YFB4500300),
10

---

References
[1] Moustafa Alzantot, Yash Sharma, Ahmed Blgohary, Bo-Jhang Ho, Mani B. Srivastava, and Kai-Wei Chang. Generating natural language adversarial examples. In EMNLP, pages 2890-2896, 2018.
[2] Michal Bednarek, Michal R. Nowicki, and Krzysztof Walas. HAPTR2: improved haptic transformer for legged robots' terrain classification. Robotics and Autonomous Systems, 158:104236, 2022.
[3] Samuel R. Bowman, Gabor Angeli, Christopher Potts, and Christopher D. Manning. A large annotated corpus for learning natural language inference. In EMNLP, pages 632-642, 2015.
[4] Daniel Cer, Yinfei Yang. Sheng-yi Kong, Nan Hua, Nicole Limtiaco, Rhomni St. John, Noah Constant, Mario Guajardo-Cespedes Cespedes, Steve Yuan, Chris Tar, Brian Strope, and Ray Kurzweil. Universal sentence encoder english. In EMNLP, pages 169-174, 2018.
[5] Yangyi Chen, Hongcheng Gao, Ganqu Cui, Fanchao Qi, Longtao Huang. Zhiyuan Liu, and Maosong Sun. Why should adversarial perturbations imperceptible? rethink the research paradigm adversarial NLP. In EMNLP, pages 11222-12 11237, 2022.
[6] Minhao Cheng, Jinfeng Yi, Pin- Yu Chen, Huan Zhang, and Cho-Jui Hsich. Seq2sick: Evaluating the robustness of 2020.
models with adversarial examples. In AAAI, pages 3601-3608 AAAI,
[7] Yong Cheng, Lu Jiang, and Wolfgang Macherey, Robust neural machine translation with doubly adversarial inputs. In ACL, pages 4324-4333. ACL, 2019.
[8] Jacob Devlin, Ming-We Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training deep bidirectional transformers for language understanding. In NAACL, pages 4171-41866 2019.
[9] Javid Ebrahimi, Anyi Rao, Daniel Lowd, and Dejing Dou. Hotflip: White-box adversarial examples for text classification. In ACL, pages 31-36, 2018.
[10] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy, Explaining and harnessing adversarial examples. In ICLR, 2015.
[11] Chuan Guo, Alexandre Sablayrolles, Hervé Jégou, and Douwe Kiela. Gradient Cradient-based adversarial attacks against text transformers. EMNLP, pages 5747-5757, 2021.
[12] Pengeheng Hc, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: dccoding-cnhane enhanced bert with disentangled attention. JCLR, 2021.
[13] Sepp Hochreiter and Jürgen Schmidhuher. Long short-term memory. Neural Computation, pages 1735- 1780, 1997.
[14] Yu-Lun Hsieh, Minhao Cheng, Da-Cheng Juan, Wei Wei, Wen-Lian Hsu, and Cho-Jui Hsieh. On the robustness of self-attentive models. In ACL, pages 1520- 1029.152..000 ACL, 2019.
[15] Junjie Hu, Hiroaki Hayashi. Kyunghyun Cho, and Graham Neubig. DEEP: demoising entity pre-training for neural machine translation. In ACL, pages 7753-1766, 2022.
[16] Di Jin, Zhijing Jin, Joey Tianyi Zhou, and Peter Szolovits. Is BERT really robust? A strong baseline for natural language attack on text classification and entailment. In AAAI, pages 8018-8025, 2020.
[17] Yoon Kim. Convolutional neural networks for sentence classification. In EMNLP, pages 1746 17516,17111110 2014.
[18] Thai Lc, Noscong Park, and Dongwon Lec. SHIELD: defending textual neural networks against multiple black-box adversarial attacks with stochastic multi-expert patcher. In ACL, pages 6661-6674, 2022.
[19] Deokjae Lee, Seungyong Moon, Junhycok Lee, and Hyun Oh Song. Query-efficient and scalable black-box adversarial attacks on discrete sequential data via bayesian optimization. In ICMI., pages 12478-12497 2022.
[20] Dianqi Li, Yizhe Zhang, Hao Peng, Liqun Chen, Chris Brockett, Ming-Ting Sun, and Bill Dolan. Contex- tualized perturbation for textual adversarial attack. In NAACL, pages 5053 5063,506,,000 2021.
[21] Jinfeng Li, Shouling Ji. Tianyu Du Bo Li, and Ting Wang. Textbugger: Generating adversarial text against real-world applications. In NDSS, 2019.
[22] Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng. and Christopher Potts. Learning word vectors for sentiment analysis. In ACL, pages 142-150 2011.
11

---

[23] Rishabh Maheshwary, Saket Maheshwary, and Vikram Pudi. Generating natural language attacks in a hard label black box setting. In AAAI, pages 13525-13533, 2021.
[24] Rishabh Maheshwary, Saket Maheshwary, and Vikram Pudi. A strong baseline for query efficient attacks in black box setting. In EMNLP. pages 8396-849689 8409, 2021.
[25] Zhao Meng and Roger Wattenhofer. A geometry-inspired attack for generating natural language adversarial examples. In COLING, pages 6679-6689, 2020.
[26] Luiz Henrique Mormille, Clifford Broni- Bediako, and Masayasu Atsumi. Regularizing self- attention on vision transformers with 2d spatial distance loss. Artif. Life Roboticx, 27(3):5665593 2022.
[27] Nikola Mrksic, Diarmuid Ó Séaghdha, Blaise Thomson, Milica Gasic, Lina Maria Bajas-Baraaon,, Pei- Hao Su, David Vandyke, Tsung-Hsiin Hsien Wen, and Steve J. Young. Counter-fitting word vectors to linguistic constraints. In NAACL, pages 142-148, 2016.
[28] Bo Pang and Lillian Lec. Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales. In ACL, pages 115-124, 2005.
[29] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog. 1(8)9, 2019.
[30]
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with unified text-to-text transformer. Journal of Machine Learning Research, 21: 21:140:1-140:67 2020.
[31] Amit Seker, Elron Bandel, Dan Barcket, Idan Brusilovsky, Refael Shaked Greenfeld, and Reut Tsarfaty. A Alephbert: Language model pre-training and evaluation from sub-word to sentence level. In ACL. pages 46-56, 2022.
[32] James Tu, Mengye Ren, Sivabalan Manivasagam, Ming Liang, Bin Yang, Richard Du, Frank Cheng, and Raquel Urtasun. Physically realizable adversarial examples for lidar object detection. In CVPR, pages 13712-13722, 2020.
[33] Adina Williams, Nikita Nangia, and Samuel R. Bowman. broad-coverage challenge corpus for sentence understanding through inference. NAACL, pages 1112-1122, 2018.
[34] Haiping Wu, Bin Xiao, Noel Codella, Mengehen Liu, Xiyang Dai, Lu Yuan, and Lei Zhang. Cvt: Introducing convolutions to vision transformers. In ICCV, pages 22-31, 2021.
[35] Wei Wu, Hao Chang, Yonghua Zheng, Zhu Li, Zhiwen Chen, and Ziheng Zhang. Contrastive leaming- based robust object detection under smoky conditions. CVPR, pages 4294-4301, 2022.
[36] Cihang Xie, Jianyu Wang. Zhishuai Zhang, Yuyin Zhou, Lingxi Xic, and Alan L. Yuille. Adversarial examples for semantic segmentation and object detection. In ICCV, pages 1378-1387, 2017.
[37] Muchao Ye, Jinghui Chen, Chenglin Miao, Ting Wang, and Fenglong Ma. Leapattack: Hard-label adversarial attack on text via gradient- optimization. In KDD, pages 2307-2315, 2022.
[38] Muchao Ye, Chenglin Miao, Ting Wang, and Fenglong Ma. Texthoaxer: Budgeted hare-label adversarial attacks on text. In AAAI, pages 3877-3884, 2022.
[39] Kan Yuan, Di Tang, Xiaojing Liao, XiaoFeng Wang. Xuan Feng, Chen, Menghan Sun. Haoran Lu, and Kehuan Zhang. Stealthy pomm Understanding real-world adversarial images for illicit online promotion. In IEEE S&P, pages 952-966, 2019.
[40] Yuan Zang, Fanchao Qi. Chenghao Yang. Zhiyuan Liu, Meng Zhang, Qun Liu, and Maosong Sun. Word-level textual adversarial attacking as combinatorial optimization. In ACL, pages 6066-6088, 2020.
[41] Zhiyuan Zeng and Deyi Xiong. An empirical study on adversarial attack on NMT: languages and positions matter. In ACL, pages 454-460, 2021.
[42] Xiang Zhang, Junbo Jake Zhao, and Yann LeCun. Character-Ievel convolutional networks for text classification. In NeurlPS, pages 649-657, 2015.
[43] Yi Zhou, Xiaoqing Zheng, Cho-Jui Hsich, Kai-Wei Wei Chang, and Xuanjing Huang. Defense against synonym substitution based ad adversarial attacks via dirichlet neighborhood ensemble. In ACL, pages 5482 5492, 2021.
12


Reviews:
[{"review_id": "jpkQW4bXGJ", "reviewer": "Reviewer_gEht", "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.", "questions": "1. The authors should add human evaluation experiments about the quality of generated adversarial examples.\n", "limitations": "The authors should address the limitation of the proposed framework in the conclusion section.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n2. 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.)\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**For Reviewer gEht.**\n\nThanks very much for your insightful and positive comments.\n\n**1. Add human evaluation experiments.**\n\nWe have conducted the human evaluation experiments on the Bert model using HLGA, TextHoaxer, LeapAttack and HQA-Attack for the MR and IMDB datasets. Specifically, for each dataset, we first randomly select 50 original samples, and use each adversarial attack method to generate the corresponding 50 adversarial examples respectively. Then we ask 10 volunteers to annotate the class labels for these samples, and calculate the average classification accuracy (Acc) for each method. Intuitively, if the accuracy is higher, it means that the quality of the generated adversarial examples is better. The detailed Acc(%) results are as follows.\n\n| Dataset | HLGA | TextHoaxer | LeapAttack | HQA-Attack |\n| ------- | ---- | ---------- | ---------- | ---------- |\n| MR      | 82.6 | 84.8       | 84.0       | **87.4**   |\n| IMDB    | 84.4 | 85.4       | 85.0       | **88.6**   |\n\nThe results show that the adversarial examples generated by HQA-Attack are more likely to be classified correctly, which further verifies the superiority of HQA-Attack in preserving the semantic information. We will follow your comments to add these results in the final version.\n\n**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 fool the models/what triggers the wrong prediction/whether different victim models make different mistakes or same mistakes.**\n\n(1) We would like to attempt to analyze our method from the perspective of decision boundary. Specifically, HQA-Attack consists of three steps. First, HQA-Attack generates an adversarial example by initialization, which means that the adversarial example is outside the decision boundary associated with the original true label. Second, HQA-Attack deals with the adversarial example by substituting original words back, which means that the adversarial example is getting closer to the decision boundary, thus improving the semantic similarity and reducing the perturbation rate. Third, HQA-Attack further optimizes the adversarial example along the direction that can increase the semantic similarity, which means the adversarial example is further approaching the decision boundary. The first step determines whether the adversarial example can fool the model and trigger the wrong prediction. The last two steps determine the quality of the adversarial example.\n\n(2) In general, different victim models have different decision boundaries, but they share the same label space. Therefore, one adversarial example can cause that different victim models make different mistakes or same mistakes. We list two adversarial examples generated by HQA-Attack on the AG dataset in the following table, and the substitute words are indicated by parentheses.\n\n| Adversarial Example                                          | True Label | BERT Prediction    | WordCNN Prediction  | WordLSTM Prediction |\n| ------------------------------------------------------------ | ---------- | -------- | -------- | -------- |\n| Witnesses to confront cali cartel ~~kingpin~~ (**punisher**) thirteen years into their probe , u.s. investigators have assembled a team of smugglers , accountants and associates to testify against colombian cartel ~~kingpin~~ (**studs**) gilberto rodriguez orejuela. | World      | Sports   | World    | Business |\n| Boys ' cured ' with gene therapy gene therapy can cure ~~children~~ (**enfants**) born with a condition that knocks out their natural defences against infection , mounting evidence shows. | World      | Sci/Tech | Sci/Tech | Sci/Tech |\n\nAccording to the results, we can get that the first example shows that different victim models can make different mistakes, and the second example shows that different victim models can make the same mistake.\n\n(3) We will follow your comments to add these explanations in the final version."}, {"review_id": "BlnFEGujC7", "reviewer": "Reviewer_27hb", "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.", "questions": "I am willing to raise my score if Q1-Q2 (major) and Q3-Q5 (intermediate) are sufficiently clarified.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "### Originality\n\n* **Novel attack.** The attack techniques are overall novel to my knowledge. The proposed strategy to optimize quality is new.\n\n### Quality\n\n* **Solid methodology.** The overall attack design is solid, and the new optimizing strategy is well-developed.\n* **Comprehensive evaluations.** The experiments are comprehensive. I appreciate the several tasks and the inclusion of robust models and ablation studies.\n\n### Clarity\n\n* **Good presentation.** The paper is generally well-written and the methodology is largely easy to follow with some focus.\n\n### Significance\n\n* **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.\n", "weaknesses": "### Originality\n\n**Q1: Unclear novelty in the word back-substitution component.**\n\nI 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.\n\nIf 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.\"\n\n### Quality\n\n**Q2: The qualitative results are somewhat insufficient.**\n\nWhile 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.\n\n**Q3: The choice of $k$.**\n\nAt 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.\n\n### Clarity\n\n**Q4: Confusion in determining the optimizing order.**\n\nIt 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?\n\n**Q5: Confusion in the final updating step.**\n\nIn L224-225, why the replacement word is chosen from $S(w_i)$, yet the similarity was compared pertaining $\\bar{w}_i$?\n\n**Minor Points:**\n*  Missing specification of the synonyms set. It is unclear how the synonyms were generated and how large it is (relevant to Q3).\n* The methodology description in Section 4.3.2 is a bit convolved.\n\n\n### Significance\n\n**Q7: Used the same random initialization as previous attacks.**\n\nWhile 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**For Reviewer 27hb.**\n\nThanks very much for your valuable and positive comments.\n\n**1. About the word back-substitution component.**\n\n(1) For the word back-substitution component, HQA-Attack is different from previous methods. Specifically, as shown in Alg. 1 (Appendix A), after replacing one original word successfully (Line 12-Line 13), our method can make the $flag$ = False (Line 14) and break out of the current loop (Line 15), where the current loop is from Line 10 to Line 17. Furthermore, as the $flag$ = False, our method will continue the outer loop and recompute the order, where the outer loop is from Line 1 to Line 21. By replacing the best original word in each iteration, HQA-Attack can make the intermediate generated adversarial example have the highest semantic similarity with the original example.\n\n(2) We have conducted experiments to verify the effectiveness of our proposed word back-substitution strategy. Specifically, we use our proposed word back-substitution strategy to replace the original word back-substitution strategy in LeapAttack to attack the WordCNN model. (Original) means the original method, and (Improved) means the method with our proposed word back-substitution strategy. The results (Sim(%)/Pert(%)) are shown as follows.\n\n\n| Dataset |  LeapAttack (Original) | LeapAttack (Improved) |\n| -------- | -------------------- | -------------------- |\n| MR       | 63.2/14.016          | **65.3/13.809**          |\n| AG       | 72.0/12.827          | **74.8/12.013**          |\n| Yahoo    | 74.3/7.842           | **74.6/7.623**           |\n| Yelp     | 80.1/8.816           | **81.5/8.120**           |\n| IMDB     | 89.7/3.886           | **90.8/3.796**           |\n\nThe results show that our proposed word back-substitution strategy can improve the semantic similarity and reduce the perturbation rate successfully. We will add these results in the final version.\n\n**2. About the qualitative results.**\n\nWe have conducted the human evaluation experiments on the Bert model using HLGA, TextHoaxer, LeapAttack and HQA-Attack for the MR and IMDB datasets. Specifically, for each dataset, we first randomly select 50 original samples, and use each adversarial attack method to generate the corresponding 50 adversarial examples respectively. Then we ask 10 volunteers to annotate the class labels for these samples, and calculate the average classification accuracy (Acc) for each method. Intuitively, if the accuracy is higher, it means that the quality of the generated adversarial examples is better. The detailed Acc(%) results are as follows.\n\n| Dataset | HLGA | TextHoaxer | LeapAttack | HQA-Attack |\n| ------- | ---- | ---------- | ---------- | ---------- |\n| MR      | 82.6 | 84.8       | 84.0       | **87.4**   |\n| IMDB    | 84.4 | 85.4       | 85.0       | **88.6**   |\n\nThe results show that the adversarial examples generated by HQA-Attack are more likely to be classified correctly, which further verifies the superiority of HQA-Attack in preserving the semantic information. We will follow your comments to add these results in the final version.\n\n**3. About the choice of $k$.**\n\nWe further conduct experiments for $k \\in [1,4]$ when attacking WordLSTM, the results (Sim(%)/Pert(%)) are shown in the following table.\n\n| $k$\\Dataset | MR          | AG          | Yahoo      | Yelp       | IMDB       |\n| ---------- | ----------- | ----------- | ---------- | ---------- | ---------- |\n| $k=1$        | 73.6/11.551 | 74.9/11.257 | 72.7/7.231 | 86.4/6.317 | 90.4/3.601 |\n| $k=2$        | 73.7/11.504 | 75.0/11.286 | 73.1/7.050 | 86.5/6.314 | 90.7/3.491 |\n| $k=3$        | 73.9/11.635 | 75.2/11.491 | 73.4/6.901 | 86.8/6.279 | 90.9/3.421 |\n| $k=4$        | 74.0/11.499 | 75.4/11.364 | 73.8/6.764 | 87.1/6.161 | 91.2/3.311 |\n\nCombining with the results $k =5, 10, 15$ in Table 2 of the supplementary material, we can find that $k=5$ is sufficient.\n\n**4. About the confusion in the optimizing order.**\n\nIn the procedure of substituting the original words back, if the changed word has a high semantic similarity with the original word but is not replaced by the original word, it indicates that this word position is important for the adversarial example. This circumstance can be summarized as if the semantic similarity between the changed word and the original word is higher, the word position is more important. Based on the observation, we use the strategy in Section 4.3.1 to determine the optimizing order. \n\n**5. About confusion in the final updating step.**\n\n(1) For fair comparison, we exactly follow the previous works HLGA, TextHoaxer and LeapAttack to choose the replacement word from $S(w_i)$.\n\n(2) To guarantee the semantic difference between the replacement word and the original word is always small, we choose the replacement word from $S(w_i)$.\n\n**6. About the minor points.**\n\n(1) For fair comparison, we follow the previous works HLGA, TextHoaxer and LeapAttack to generate 50 synonyms for each word by using the counter-fitting word vector. We will add these explanations in the final version.\n\n(2) We will polish the methodology description in Section 4.3.2 in the final version.\n\n**7. About the initialization.**\n\n(1) In the hard-label scenario, attackers can only access the model output labels. Therefore, in most existing hard-label settings, no matter images or texts, random initialization is the most commonly used method to obtain the initial adversarial example.\n\n(2) The initialization strategy is really a good research direction, one possible idea is to calculate the importance score of each word for the final prediction or evaluate the impact of the replacement of each word on the final prediction. We will further explore this direction in the future."}, {"review_id": "eAsbiiOSc9", "reviewer": "Reviewer_RbiV", "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.\n- 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.\n- The process can be summarized into three components:\n1. Random initialization to find an adversarial example.\n2. Sequentially substitutes original words back as many as possible, beginning from the adversarial example found in step 1.\n3. Further optimization step to improve semantic similarity and perturbation rate. \n- The experimental results show the HQA-Attack's superiority in hard-label adversarial attacks.", "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?\n- 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.\n- 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?\n\n[TextFooler] Is BERT Really Robust? Natural Language Attack on Text Classification and Entailment, Di Jin et al., AAAI 2020\n\n[BERT Attack] BERT-ATTACK: Adversarial Attack against BERT using BERT, Linyang Li et al., EMNLP 2020\n\n[BAE] BAE: BERT-based Adversarial Examples for Text Classification, Siddhant Garg et al., EMNLP 2020\n\n[BBA] Query-Efficient and Scalable Black-Box Adversarial Attacks on Discrete Sequential Data via Bayesian Optimization, Deokjae Lee et al., ICML 2022\n\n\n", "limitations": "The authors provide some broader impacts and limitations in Appendix F.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The authors conduct experiment on various datasets and victim models containing commercial classification system such as google cloud and alibaba cloud.\n- The second step of HQA-Attack, which greedily substitute original words back, is very simple and intuitive.\n", "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. \n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**For Reviewer RbiV.**\n\nThanks very much for your valuable and positive comments.\n\n**1. About the experiments with the sentence-dependent word substitution set.**\n\n(1) For fair comparison, we follow the previous works HLGA, TextHoaxer and LeapAttack to generate 50 synonyms for each word by using the counter-fitting word vector.\n\n(2) We have followed your comments to conduct experiments with the sentence-dependent word substitution set. Specifically, we modify our method with BERT-based synonyms to attack the WordCNN model. The results are as follows.\n\n| Dataset | Sim(%) | Pert(%) |\n| :-----: | :----: | :-----: |\n|   MR    |  73.4  | 11.856  |\n|   AG    |  81.3  | 10.798  |\n|  Yahoo  |  82.6  |  6.071  |\n|  Yelp   |  87.9  |  6.249  |\n|  IMDB   |  92.2  |  3.740  |\n\nFrom the above results and Table 2 of the original paper, it can be seen that BERT-based synonyms are competitive with counter-fitting word vector based synonyms. We will further attempt to consider these two types of synonyms simultaneously to improve the method in the future.\n\n**2. Ablation study of the third step.**\n\nIn the original paper, we have shown the ablation study of the third step in Table 6. Here we list the results (Sim(%)/Pert(%)) as follows.\n\n| Dataset | w/o Optimizing | HQA-Attack  |\n| ------- | -------------- | ----------- |\n| MR      | 74.2/11.673    | **75.1/11.224** |\n| AG      | 79.3/11.305    | **82.7/8.831**  |\n| Yahoo   | 79.7/7.445     | **82.4/6.132**  |\n| Yelp    | 85.2/7.883     | **87.8/6.312**  |\n| IMDB    | 92.2/3.923     | **93.1/3.285**  |\n\nFrom the results, it can be seen that the step of optimizing the adversarial example is necessary for HQA-Attack.\n\n**3. About the comparison of HQA-Attack with a simple GP-based hard-label attack.**\n\nWe have modified the BBA method to construct a simple GP-based hard-label attack model by replacing the prediction score with the hard label (0 or 1). We take the WordCNN as the victim model, and the results are as follows.\n\n| Dataset | Sim(%) | Pert(%) |\n| :-----: | :----: | :-----: |\n|   MR    |  63.6  | 14.946  |\n|   AG    |  72.3  | 14.573  |\n|  Yahoo  |  71.6  |  8.931  |\n|  Yelp   |  78.5  |  9.913  |\n|  IMDB   |  89.6  |  4.421  |\n\nFrom the above results and Table 2 of the original paper, it can be seen that HQA-Attack still performs better than the simple GP-based hard-label attack model. The possible reason is that the acquisition function used in GP heavily relies on the concrete prediction score of the victim model, but in the hard-label setting only predicted labels are accessible."}, {"review_id": "Om7YnXDrzn", "reviewer": "Reviewer_pVxP", "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. ", "questions": "Please see the second point in the Weakness section. ", "limitations": "This paper has a limitation section that effectively addresses the limitations of the proposed approach. ", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "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. \n\n1. 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. \n\n2. 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? \n\n3. 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.  \n\n4. 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. \n\n\n\n[1] Generating Natural Language Attacks in a Hard Label Black Box Setting. Rishabh Maheshwary, Saket Maheshwary, Vikram Pudi. AAAI\n[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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**For Reviewer pVxP.**\n\nThanks very much for your valuable and helpful comments.\n\n**1. About the contributions.**\n\nWe would like to clarify our contributions.\n\n(1) We propose a novel method for substituting original words back (Sec. 4.2), which is different from previous methods. Specifically, previous works only calculate the semantic similarity gain once and then determine the replacement order. However, the initially determined order is inaccurate after the adversarial example goes through several replacements. To solve this issue, we propose a new method which is shown in Alg. 1 (Appendix A). After replacing one original word successfully (Line 12-Line 13), our method can make the $flag$ = False (Line 14) and break out of the current loop (Line 15), where the current loop is from Line 10 to Line 17. Furthermore, as the $flag$ = False, our method will continue the outer loop and recompute the order, where the outer loop is from Line 1 to Line 21. By replacing the best original word in each iteration, HQA-Attack can make the intermediate generated adversarial example have the highest semantic similarity with the original example.\n\n(2) We propose a novel optimization strategy (Sec. 4.3), which is different from previous methods. Specifically, previous works rely on the complex heuristic algorithm or unreliable gradient estimation strategy, which probably fall into the local optimum and consume numerous queries. To alleviate above issues, in the optimizing procedure, HQA-Attack optimizes the adversarial example with the direction which can improve the semantic similarity and satisfy the adversarial condition simultaneously. And in the optimizing procedure, HQA-Attack searches a transition word for each changed word, thus reducing the queries to some extent.\n\n(3) Experimental results on 8 public datasets and 2 real-world APIs have shown that HQA-Attack outperforms other strong baselines greatly.\n\n**2. About the practical issues.**\n\n(1) The experimental settings are reasonable.\n\nFirst, the adversarial attack research aims to explore the system vulnerability rather than cause some destruction, and the classification model has been widely used in many real systems. As many APIs do not release the model and only provide the hard-label prediction results, so the hard-label black-box experimental settings are suitable for simulating such scenarios. \n\nSecond, we have conducted experiments on the classification models provided by Alibaba Cloud API and Google Cloud API, which are both real applications. After identifying the system vulnerability, the potential application is to use the adversarial examples to improve these systems and mitigate some negative impacts. \n\nIn addition, the experimental settings have been widely adopted by previous methods like HLGA, TextHoaxer and LeapAttack.\n\n(2) High-quality adversarial examples are essential. \n\nIn real world applications, low-quality adversarial examples can be easily detected by manual inspection or detection algorithms, which are meaningless to improve the system robustness. High-quality adversarial examples have higher semantic similarity and lower perturbation rate, which are easier to bypass manual inspection and detection algorithms, thus fulfilling the attack task. Furthermore, by utilizing high-quality adversarial examples to improve the original system, we can make the system more robust and safer.\n\n**3. About human evaluation.**\n\nWe have conducted the human evaluation experiments on the Bert model using HLGA, TextHoaxer, LeapAttack and HQA-Attack for the MR and IMDB datasets. Specifically, for each dataset, we first randomly select 50 original samples, and use each adversarial attack method to generate the corresponding 50 adversarial examples respectively. Then we ask 10 volunteers to annotate the class labels for these samples, and calculate the average classification accuracy (Acc) for each method. Intuitively, if the accuracy is higher, it means that the quality of the generated adversarial examples is better. The detailed Acc(%) results are as follows.\n\n| Dataset | HLGA | TextHoaxer | LeapAttack | HQA-Attack |\n| ------- | ---- | ---------- | ---------- | ---------- |\n| MR      | 82.6 | 84.8       | 84.0       | **87.4**   |\n| IMDB    | 84.4 | 85.4       | 85.0       | **88.6**   |\n\nThe results show that the adversarial examples generated by HQA-Attack are more likely to be classified correctly, which further verifies the superiority of HQA-Attack in preserving the semantic information. We will add these results in the final version.\n\n**4. About experiments on advanced models.**\n\nWe have conducted experiments to attack T5 and DeBERTa. Due to time limit, we select 1000 samples from each of sentence-level datasets (MR, AG and Yahoo) and 500 samples from document-level datasets (Yelp and IMDB). The results (Sim(%)/Pert(%)) are as follows. \n\n| Dataset (Method)           | T5          | DeBERTa     |\n| ----------------- | ----------- | ----------- |\n| MR (TextHoaxer)    | 65.7/12.463 | 66.6/12.251 |\n| MR (LeapAttack)    | 60.0/17.240 | 60.9/17.853 |\n| MR (HQA-Attack)    | **73.0/11.846** | **73.8/11.460** |\n| AG (TextHoaxer)    | 67.3/14.702 | 63.3/17.385 |\n| AG (LeapAttack)    | 65.7/17.697 | 62.7/20.289 |\n| AG (HQA-Attack)    | **76.8/11.365** | **75.0/13.019** |\n| Yahoo (TextHoaxer) | 64.7/7.735  | 66.0/9.360  |\n| Yahoo (LeapAttack) | 62.9/9.704 | 64.1/11.221 |\n| Yahoo (HQA-Attack) | **69.0/10.428**  | **72.2/10.051**  |\n| Yelp (TextHoaxer)  | 77.5/8.532  | 68.6/13.798 |\n| Yelp (LeapAttack)  | 76.3/10.348 | 68.8/15.370 |\n| Yelp (HQA-Attack)  | **84.1/7.514**  | **78.9/11.749** |\n| IMDB (TextHoaxer)  | 83.3/6.477  | 78.1/10.153 |\n| IMDB (LeapAttack)  | 83.7/7.087  | 78.7/11.018 |\n| IMDB (HQA-Attack)  | **87.0/6.142**  | **84.3/9.963**  |\n\n\nFrom the results, it can be seen that HQA-Attack still outperforms other strong baselines, which further verifies the superiority of HQA-Attack. We will add these results in the final version."}, {"review_id": "XdwjrdWBr2", "reviewer": "Reviewer_BWcn", "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. ", "questions": "1. Just curious. Did authors consider using ChatGPT to help you generate some similar sentences?", "limitations": "The authors provided the description of limitations such as potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-written. The problem this paper focuses on is important, and the proposed method is interesting. \n2. The experiments are sufficient, and the conclusion is convincing.\n", "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. \n2. 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. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**For Reviewer BWcn.**\n\nThanks very much for your valuable and positive comments.\n\n**1. Theoretical analysis of computational complexity and the number of queries.**\n\nWe have attempted to analyze the computational complexity and the number of queries for the main procedures of HQA-Attack, including Section 4.2 \"Substituting original words back\" and Section 4.3 \"Optimizing the adversarial examples\".\n\nGiven the original example $x$ and its initial adversarial example $x'$, $n$ represents the length of the original sample $x$. We can make the following analysis.\n\n(1) Analysis of substituting original words back.\n\nIn the best case, $x'$ only has one different word compared with $x$, so Alg. 1 (Appendix A) only calculates the cosine similarity once and queries the victim model once. In this case, the computational complexity is $\\mathcal{O}(1)$ and the number of queries is $\\mathcal{O}(1)$. \n\nIn the worst case, $x'$ has $n$ different words with $x$, which means we will conduct $n$ replacement iterations (Alg. 1 Line 1-Line 21). In this case, the number of calculating cosine similarity is $n, n-1, ..., 1$ from the $1$-st to the $n$-th iteration, so the computational complexity is $\\frac{(n+1)\\times n}{2} = \\mathcal{O}(n^2)$. And for the number of queries, there are two boundary cases. For Alg. 1 Line 10-Line 17, we may successfully replace the first word or replace the last word in $choices$. In the former case, the number of queries is $n = \\mathcal{O}(n)$. In the latter case, the number of queries in each iteration is $n, n-1, ..., 1$ from the $1$-st to the $n$-th iteration, so the number of queries is $\\frac{(n+1)\\times n}{2} = \\mathcal{O}(n^2)$.\n\nAccording to the above analysis, for Section 4.2, the overall computational complexity is $\\mathcal{O}(n^2)$ and the number of queries is $\\mathcal{O}(n^2)$, where $n$ is the length of the original sample $x$.\n\n\n(2) Analysis of optimizing the adversarial examples.\n\nAssume that $r$ is the number of synonyms in finding the transition word (Line 199), $k$ is the number of synonyms in estimating the updating direction (Line 208), $C = |S(w_i)|$ is the synonym set size for $w_i$. For the sake of analysis, we assume the synonym set size of each word is the same.\n\nIn Section 4.3.1 (Line 183), the number of calculating cosine similarity is $\\mathcal{O}(n)$ and the number of queries is $0$. Specifically, $x'_t$ may have only one different word with the original sentence $x$, and also may have $n$ different words, thus the corresponding computational complexity is $\\mathcal{O}(n)$, where $x'_t$ is the generated adversarial example through Section 4.2. And this step (Section 4.3.1) does not need to query the victim model.\n\nIn Section 4.3.2 (Line 194), the number of calculating cosine similarity is $\\mathcal{O}(n(r+k+C))$ and the number of queries is $\\mathcal{O}(n(r+C))$. Specifically, In Alg. 2 (Appendix B) Line 9-Line 14, the number of $I$ may be $1$ or $n$. In each iteration (Alg. 2 Line 10-Line 13), for the first sub-step (Alg. 2 Line 10), we randomly select $r$ synonyms to find the transition word, so the computational complexity is $\\mathcal{O}(r)$ and the number of queries is $\\mathcal{O}(r)$. For the second sub-step (Alg. 2 Line 11), we randomly select $k$ synonyms to obtain the updating direction, so the computational complexity is $\\mathcal{O}(k)$ and the number of queries is $0$. In the third sub-step (Alg. 2 Line 12), we obtain $\\widetilde{w}_i$ from $S(w_i)$, so the computational complexity is $\\mathcal{O}(C)$ and the number of queries is $\\mathcal{O}(C)$. Furthermore, in the experiments, we set the size of the synonym set is 50, so $r$, $k$ and $C$ are all integers which are not greater than 50. Then both $\\mathcal{O}(n(r+k+C))$ and $\\mathcal{O}(n(r+C))$ can be simplified to $\\mathcal{O}(n)$.\n \nAccording to the above analysis, for Section 4.3, the overall computational complexity is $\\mathcal{O}(n)$ and the number of queries is $\\mathcal{O}(n)$, where $n$ is the length of the original sample $x$.\n\nWe will follow your comments to add the above analysis in the final version.\n\n**2. About the fluency of sentences.**\n\nWe have evaluated the fluency of generated adversarial examples using the perplexity metric (PPL), which is a widely used metric for evaluating the sentence fluency [1,2,3]. In the original paper, we have provided the perplexity results in Tables 4 and 5, where the lower PPL values indicate the better fluency. It can be seen that our proposed HQA-Attack outperforms other baselines in terms of sentence fluency.\n\n[1] A Unified Evaluation of Textual Backdoor Learning: Frameworks and Benchmarks. NeurIPS 2022.\n\n[2] Subword Evenness (SuE) as a Predictor of Cross-lingual Transfer to Low-resource Languages. EMNLP 2022.\n\n[3] Gradient-based Constrained Sampling from Language Models. EMNLP 2022.\n\n**3. About using ChatGPT.**\n\nIn our upcoming work, we will attempt to leverage ChatGPT or other large language models (LLMs) to help us generate and optimize the adversarial examples. Here are some possible points. \n\n(1) Using LLMs to generate similar words, phrases or sentences for the original text.\n\n(2) Taking the LLMs as the substitution model to imitate the victim model, thus reducing the number of queries.\n\n(3) Investigating how to design appropriate prompts to guide LLMs to generate the adversarial examples directly."}]

Author rebuttal:
**For everyone.**

We would like to thank everyone for devoting the valuable time and effort to assist us in enhancing the quality of our manuscript. 

We have provided the detailed responses for each review, and we really appreciate your consideration.

Meta-review: The paper proposes a new hard-label black-box attack on textual data that aims to improve the performance in semantic similarity and perturbation rate. Experiments on various datasets and victim models verify that the proposed methods can significantly enhance the quality of generated adversarial examples, according to the metrics of text similarity and perturbation rate. 

Initially, we received slightly divergent reviews. While the majority of reviewers responded positively to the paper, some raised questions regarding its contributions and experiments. Subsequently, the authors' responses successfully addressed specific aspects of the reviewers' concerns, prompting several of them to raise their scores above the threshold. Consequently, I would like to suggest acceptance.
Decision: Accept (poster)