Title: NATURAL LANGUAGE ADVERSARIAL ATTACK AND DEFENSE IN WORD LEVEL

Abstract: Up until very recently, inspired by a mass of researches on adversarial examples for computer vision, there has been a growing interest in designing adversarial attacks for Natural Language Processing (NLP) tasks, followed by very few works of adversarial defenses for NLP. To our knowledge, there exists no defense method against the successful synonym substitution based attacks that aim to satisfy all the lexical, grammatical, semantic constraints and thus are hard to perceived by humans. We contribute to fill this gap and propose a novel adversarial defense method called Synonym Encoding Method (SEM), which inserts an encoder before the input layer of the model and then trains the model to eliminate adversarial perturbations. Extensive experiments demonstrate that SEM can efficiently defend current best synonym substitution based adversarial attacks with little decay on the accuracy for benign examples. To better evaluate SEM, we also design a strong attack method called Improved Genetic Algorithm (IGA) that adopts the genetic metaheuristic for synonym substitution based attacks. Compared with existing genetic based adversarial attack, IGA can achieve higher attack success rate while maintaining the transferability of the adversarial examples.

1. INTRODUCTION:

Deep Neural Networks (DNNs) have made great success in various machine learning tasks, such as computer vision (Krizhevsky et al., 2012; He et al., 2016) , and Natural Language Processing (NLP) (Kim, 2014; Lai et al., 2015; Devlin et al., 2018) . However, recent studies have discovered that DNNs are vulnerable to adversarial examples not only for computer vision tasks (Szegedy et al., 2014) but also for NLP tasks (Papernot et al., 2016) , causing a serious threat to their safe applications. For instance, spammers can evade spam filtering system with adversarial examples of spam emails while preserving the intended meaning.

In contrast to numerous methods proposed for adversarial attacks (Goodfellow et al., 2015; Nicholas & David, 2017; Anish et al., 2018) and defenses (Goodfellow et al., 2015; Guo et al., 2018; Song et al., 2019) in computer vision, there are only a few list of works in the area of NLP, inspired by the works for images and emerging very recently in the past two years (Zhang et al., 2019) . This is mainly because existing perturbation-based methods for images cannot be directly applied to texts due to their discrete property in nature. Furthermore, if we want the perturbation to be barely perceptible by humans, it should satisfy the lexical, grammatical and semantic constraints in texts, making it even harder to generate the text adversarial examples.

Current attacks in NLP can fall into four categories, namely modifying the characters of a word (Liang et al., 2017; Ebrahimi et al., 2017) , adding or removing words (Liang et al., 2017) , replacing words arbitrarily (Papernot et al., 2016) , and substituting words with synonyms (Alzantot et al., 2018; Ren et al., 2019) . The first three categories are easy to be detected and defended by spell or syntax check (Rodriguez & Rojas-Galeano, 2018; Pruthi et al., 2019) . As synonym substitution aims to satisfy all the lexical, grammatical and semantic constraints, it is hard to be detected by automatic spell or syntax check as well as human investigation. To our knowledge, currently there is no defense method specifically designed against the synonym substitution based attacks.

In this work, we postulate that the model generalization leads to the existence of adversarial examples: a generalization that is not strong enough causes the problem that there usually exists some neighbors x of a benign example x in the manifold with a different classification. Based on this hypothesis, we propose a novel defense mechanism called Synonym Encoding Method (SEM) that encodes all the synonyms to a unique code so as to force all the neighbors of x to have the same label of x. Specifically, we first cluster the synonyms according to the Euclidean Distance in the embedding space to construct the encoder. Then we insert the encoder before the input layer of the deep model without modifying its architecture, and train the model again to defend adversarial attacks. In this way, we can defend the synonym substitution based adversarial attacks efficiently in the context of text classification.

Extensive experiments on three popular datasets demonstrate that the proposed SEM can effectively defend adversarial attacks, while maintaining the efficiency and achieving roughly the same accuracy on benign data as the original model does. To our knowledge, SEM is the first proposed method that can effectively defend the synonym substitution based adversarial attacks.

Besides, to demonstrate the efficacy of SEM, we also propose a genetic based attack method, called Improved Genetic Algorithm (IGA), which is well-designed and more efficient as compared with the first proposed genetic based attack algorithm, GA (Alzantot et al., 2018) . Experiments show that IGA can degrade the classification accuracy more significantly with lower word substitution rate than GA. At the same time IGA keeps the transferability of adversarial examples as GA does.

2. BACKGROUND AND RELATED WORK:

Let W denote the word set containing all the legal words. Let x = {w 1 , . . . , w i , . . . , w n } denote an input text, C the corpus that contains all the possible input texts, and Y ∈ N K the output space. The classifier f : C → Y takes an input x and predicts its label f (x), and let S m (x, y) denote the confidence value for the y-th category at the softmax layer. Let Syn(w, σ, k) represent the set of first k synonyms of w within distance σ, namely

Syn(w, σ, k) = {w 1 , . . . , w i , . . . , w k |w i ∈ W ∧ w -w 1 p ≤ ... ≤ w -w k p < σ},

where w -w p is the p-norm distance evaluated on the corresponding embedding vectors.

2.1. NATURAL LANGUAGE ADVERSARIAL EXAMPLES:

Suppose we have an ideal classifier c : C → Y that could always output the correct label for any input text x. For a subset of (train or test) texts T ⊆ C and a small constant , we could define the natural language adversarial examples as follows:

A = {x adv ∈ C | ∃x ∈ T , f (x adv ) = c(x adv ) = c(x) = f (x) and d(x -x adv ) < }, (1)

where d(x -x adv ) is a distance metric to evaluate the dissimilarity between the benign example x = {w 1 , . . . , w i , . . . , w n } and the adversarial example x adv = {w 1 , . . . , w i , . . . , w n }. It is usually defined as the p-norm distance:

d(x -x adv ) = x -x adv p = ( i w i -w i p ) 1 p .

2.2. TEXT ADVERSARIAL ATTACKS:

In this subsection, we provide a brief overview of three popular synonym substitution based adversarial attack methods.

Greedy Search Algorithm (GSA). Kuleshov et al. (2018) propose a greedy search algorithm to substitute words with their synonyms so as to maintain the semantic and syntactic similarity. GSA first constructs a synonym set W s for an input text x = {w 1 , . . . , w i , . . . , w n }:

W s = {Syn(w i , σ, k)|1 ≤ i ≤ n}.

(2)

Initially, let x adv = x. Then at each stage for x adv = {w 1 , . . . , w i , . . . , w n }, GSA finds a word ŵ i ∈ W that satisfies the syntactic constraint and minimizes S m (x, y true ) where x = {w 1 , . . . , w i-1 , ŵ i , w i+1 , . . . , w n }, and updates x adv = x. Such process iterates until x adv becomes an adversarial example or the word replacement rate reaches a threshold.

Genetic Algorithm (GA). Alzantot et al. (2018) propose a population-based algorithm to replace words with their synonyms so as to generate semantically and syntactically similar adversarial examples. There are three operators in GA:

• M utate(x): Randomly choose a word w i in text x that has not been updated and substitute w i with w i , one of its synonyms Syn(w i , σ, k) that does not violate the syntax constraint by the "Google 1 billion words language model" (Chelba et al., 2013) and minimize S m (x, y true ) where x = {w 1 , . . . , w i-1 , w i , w i+1 , . . . , w n } and S m (x, y true ) < S m (x, y true );

• Sample(P): Randomly sample a text from population P with a probability proportional to 1 -S m (x i , y true ) where x i ∈ P;

• Crossover(a, b): Construct a new text c = {w c 1 , . . . , w c i , . . . , w c n }, where w c i is randomly chosen from {w a i , w b i } based on the input texts a = {w a 1 , . . . , w a i , . . . , w a n } and b = {w b 1 , . . . , w b i , . . . , w b n }. For a text x, GA first generates an initial population P 0 of size m:

P 0 = {M utate(x), . . . , M utate(x)}.

(3)

Then at each iteration, GA generates the next generation of population through crossover and mutation operators:

x i+1 adv = arg min

EQUATION

GA terminates when it finds an adversarial example or reaches the maximum number of iteration limit.

Probability Weighted Word Saliency (PWWS). Ren et al. (2019) propose a new synonym substitution method called Probability Weighted Word Saliency (PWWS), which considers the word saliency as well as the classification confidence. Given a text x = {w 1 , . . . , w i , . . . , w n }, PWWS first calculates the saliency of each word S(x, w i ):

S(x, w i ) = S m (x, y true ) -S m (x i , y true ) where xi = {w 1 , . . . , w i-1 , unk, w i+1 , . . . , w n }, (5)

where "unk" means the word is removed. Then PWWS calculates the maximum possible change in the classification confidence resulted from substituting word w i with one of its synonyms:

∆S * mi (x) = max w i ∈Syn(wi,σ,k)

[S m (x, y true )-S m (x i , y true )] where x i = {w 1 , . . . , w i , . . . , w n }. (6)

Then, PWWS sequentially checks the words in descending order of φ(S(x, w i )) i • ∆S * mi (x), where φ(z) i = e z i n k=1 e z k , and substitutes the current word w i with its optimal synonym w * i :

EQUATION

PWWS terminates when it finds an adversarial example x adv or it has replaced all the words in x.

2.3. TEXT ADVERSARIAL DEFENSES:

There exist very few works for text adversarial defenses.

• In the character-level, Pruthi et al. (2019) propose to place a word recognition model in front of the downstream classifier to defend character-level adversarial attacks by combating adversarial spelling mistakes. • In the word level, for defenses on synonym substitution based attacks, only Alzantot et al. (2018) and Ren et al. (2019) incorporate the adversarial training strategy proposed in the image domain (Goodfellow et al., 2015) with their text attack methods respectively, and demonstrate that adversarial training can promote the model's robustness. However, there is no defense method specifically designed to defend the synonym substitution based adversarial attacks.

3. THE PROPOSED TEXT DEFENSE METHOD:

We first introduce our motivation, then present the proposed text defense method, Synonym Encoding Method (SEM).

3.1. MOTIVATION:

Let X denote the input space, V (x) denote the -neighborhood of data point x ∈ X , where Ideally, to defend the adversarial attack, we need to train a classifier f which not only guarantees f (x) = y true , but also assures ∀x ∈ V (x), f (x ) = y true . Thus, the most effective way is to add more labeled data to improve the adversarial robustness (Schmidt et al., 2018) . Ideally, as illustrated in Figure 1 (b), if we have infinite labeled data, we can train a model f : ∀x ∈ V (x), f (x ) = y true with high probability so that the model f is robust enough to adversarial examples. Practically, however, labeling data is very expensive and it is impossible to have infinite labeled data.

V (x) = {x ∈ X | x -x < }. As illustrated in

Because it is impossible to have enough labeled data to train a robust model, as illustrated in Figure 1 (c), Wong & Kolter (2018) propose to construct a convex outer bound and guarantee that all data points in this bound share the same label. The goal is to train a model f : ∀x ∈ V , f (x ) = f (x) = y true . Specifically, they propose a linear-programming (LP) based upper bound on the robust loss by adopting a linear relaxation of the ReLU activation and minimize this upper bound during the training. Then they bound the LP optimal value and calculate the elementwise bounds on the activation functions based on a backward pass through the network. Although their method does not need any extra data, it is hard to scale to realistically-sized networks due to its high complexity.

In this work, as illustrated in Figure 1 (d), we propose a novel way to find a mapping m : X → X where ∀x ∈ V (x), m(x ) = x. In this way, we force the classification to be more smooth and we do not need any extra data to train the model or modify the architecture of the model. All we need to do is to insert the mapping before the input layer and train the model on the original training set. Now the problem turns into how to locate the neighbors of data point x. For image tasks, it is hard to find all images in the neighborhood of x in the input space, and there could be infinite number of neighbors. For NLP tasks, however, utilizing the property that words in sentences are discrete tokens, we can easily find almost all neighbors of an input text. Based on this insight, we propose a new method called Synonym Encoding Method to locate the neighbors of an input x .

3.2. SYNONYM ENCODING:

We assume that the closer the meaning of two sentences is, the closer their distance is in the input space. Thus, we can suppose that the neighbors of x are its synonymous sentences. To find the synonymous sentence, we can substitute words in the sentence with their synonyms. To construct the mapping m, all we need to do is to cluster the synonyms and allocate a unique token for each cluster, which we call the Synonym Encoding Method (SEM). The details are in Algorithm 1.

Algorithm 1 Synonym Encoding Method Input: W : dictionary of words, n: size of W , σ: distance for synonyms, k: number of synonyms for each word Output: E: encoding result 1: E = {w 1 : None, . . . , w n : None} 2: for each word w i ∈ W do

3: if E[w i ] = NONE then 4: if ∃w j ∈ Syn(w i , σ, k), E[w j ] = NONE then 5: w * i ← the closest w j ∈ W where E[w j ] = NONE 6: E[w i ] = E[w * i ] 7: else 8: E[w i ] = w i 9:

end if 10:

for each word w j in Syn(w i , σ, k) do

11: if E[w j ] = NONE then 12: E[w j ] = E[w i ] 13:

end if 

4. THE IMPROVED GENETIC BASED TEXT ATTACK:

The current synonym substitution based text adversarial attacks (Alzantot et al., 2018; Kuleshov et al., 2018; Ren et al., 2019) have a constraint that they only substitute words at the same position once or replace words with the first k synonyms of the word in the original input x. This constraint can lead to local minimum for adversarial examples, and it is hard to choose a suitable k as different words may have different number of synonyms.

To address this issue, we propose an Improved Genetic Algorithm (IGA), which allows to substitute words in the same position more than once based on the current text x . In this way, IGA can traverse all synonyms of a word no matter what value k is. Meanwhile, we can avoid local minimum to some extent as we allow the substitution of the word by the original word in the current position. In order to guarantee that the substituted word is still a synonym of the original word, each word in the same position can be replaced at most λ times.

Differs to the first genetic based text attack algorithm of Alzantot et al. (2018) , we change the structure of the algorithm, including the operators for crossover and mutation. For more details of IGA, see Appendix A.

5. EXPERIMENTS:

We evaluate SEM with four attacks, GSA (Kuleshov et al., 2018) , GA (Alzantot et al., 2018) , PWWS (Ren et al., 2019) and our IGA, on three popular datasets involving three neural network classification models. The results demonstrate that SEM can significantly improve the robustness of neural networks and IGA can achieve better attack performance as compared with existing attacks. And we further provide discussion on the hyper-parameter of SEM in Appendix B.

5.1. EXPERIMENTAL SETUP:

We first provide an overview of the datasets and classification models used in the experiments.

Datasets. In order to evaluate the efficacy of SEM, we choose three popular datasets: IMDB, AG's News, and Yahoo! Answers. IMDB (Potts, 2011 ) is a large dataset for binary sentiment classification, containing 25, 000 highly polarized movie reviews for training and 25, 000 for testing. AG's News (Zhang et al., 2015) Models. To better evaluate our method, we adopt several state-of-the-art models for text classification, including Convolution Neural Networks (CNNs) and Recurrent Neural Networks (RNNs). The embedding dimension for all models are 300 (Mikolov et al., 2013) . We replicate the CNN's architecture from Kim (2014) , which contains three convolutional layers with filter size of 3, 4, and 5 respectively, a max-pooling layer and a fully-connected layer. LSTM consists of three LSTM layers where each layer has 300 LSTM units and a fully-connected layer (Liu et al., 2016) . Bi-LSTM contains a bi-directional LSTM layer whose forward and reverse have 300 LSTM units respectively and a fully-connected layer.

Baselines. We take the method of adversarial training (Goodfellow et al., 2015) as our baseline. However, due to the low efficiency of text adversarial attacks, we cannot implement adversarial training as it is in the image domain. In the experiments, we adopt PWWS, which is quicker than GA and IGA, to generate 10% adversarial examples of the training set, and re-train the model incorporating adversarial examples with the training data.

5.2. EVALUATION ON DEFENSE METHODS:

To evaluate the efficiency of the SEM method, we randomly sample 200 correctly classified examples on different models from each dataset and use the above attack methods to generate adversarial examples with or without defense. The more effective the defense method is, the smaller the classification accuracy of the model drops. Table 1 shows the efficacy of various attack and defense methods. For each network model, we look at each row to find the best defense result under the setting of no attack, or GSA, PWWS, GA, and IGA attacks:

• Under the setting of no attack, adversarial training (AT) could improve the classification accuracy of the models on all datasets, as adversarial training (AT) is also the way to augment the training data. Our defense method SEM reaches an accuracy closing to normal training (NT). • Under the four attacks, however, the classification accuracy with normal training (NT) and adversarial training (AT) drops significantly. For normal training (NT), the accuracy degrades more than 75%, 42% and 40% on the three datasets respectively. And adversarial training (AT) cannot defend these attacks effectively, especially for PWWS and IGA on IMDB and Yahoo! Answers, where AT only improves the accuracy a little (smaller than 5%). By contrast, SEM can remarkably improve the robustness of the deep models for all the four attacks.

5.3. DEFENSE FOR TRANSFERABILITY:

In the image domain, the transferability of adversarial attack refers to its ability to decrease the accuracy of models using adversarial examples generated based on other models (Szegedy et al., 2014; Goodfellow et al., 2015) . Papernot et al. (2016) 

6. CONCLUSION:

Synonym substitution based adversarial attacks are currently the best text attack methods, as they are hard to be checked by automatic spell or syntax check as well as human investigation. In this work, we propose a novel defense method called Synonym Encoding Method (SEM), which encodes the synonyms of each word to defend adversarial attacks for text classification task. Extensive experiments show that SEM can defend adversarial attacks efficiently and degrade the transferability of adversarial examples, at the same time SEM maintains the classification accuracy on benign data.

To our knowledge, this is the first and efficient text defense method in word level for state-of-the-art synonym substitution based attacks.

In addition, we propose a new text attack method called Improved Genetic Attack (IGA), which in most cases can achieve much higher attack success rate as compared with existing attacks, at the same time IGA could maintain the transferability of adversarial examples.

A DETAILS OF IGA:

Here we introduce our Improved Genetic Algorithm (IGA) in details and show how IGA differs from the first proposed generic attack method, GA (Alzantot et al., 2018) . Regard a text as a chromosome, there are two operators in IGA:

• Crossover(a,b): For two texts a and b where a = {w a 1 , . . . , w a i-1 , w a i , w a i+1 , . . . , w a n } and b = {w b 1 , . . . , w b i-1 , w b i , w b i+1 , . . . , w b n }, randomly choose a crossover point i from 1 to n, and generate a new text c = {w a 1 , . . . , w a i-1 , w a i , w b i+1 , . . . , w b n }. • M utate(x, w i ): For a text x = {w 1 , . . . , w i-1 , w i , w i+1 , . . . , w n } and a position i, replace w i with ŵi where ŵi ∈ Syn(w , σ, k) to get a new text x = {w 1 , . . . , w i-1 , ŵi , w i+1 , . . . , w n } that minimizes S m (x, y true ).

The details of IGA are described in Algorithm 2.

Algorithm 2 The Improved Genetic Algorithm Input: x: input text, y true : true label for x, M : maximum number of iterations Output: x adv : adversarial example 1: for each word w i ∈ x do 2: 

P 0 i ← M utate(x, w i ) 3: end for 4: for g = 1 → M do 5: x adv = arg min xi∈P g S m (x i , y true ) 6: if f (x adv ) =

for i = 2 → |P g-1 | do 11:

Randomly sample parent 1 , parent 2 from P g-1

12: child = Crossover(parent 1 , parent 2 )

13:

Randomly choose a word w in child 14:

P g i ← M utate(child, w)

15:

end for 16: end for 17: return x adv Compared with GA, IGA has the following differences:

• Initialization: GA initializes the first population randomly, while IGA initializes the first population by replacing each word by its optimal synonym, so our population is more diversified. • M utation: Different from GA, IGA allows to replace the word that has been replaced before so that we can avoid local minimum. • Crossover: To better simulate the reproduction and biological crossover, we randomly cut the text from two parents and concat two fragments into a new text rather than randomly choose a word of each position from the two parents.

The selection of the next generation is similar to GA, greedily choose one offspring, and then generate other offsprings by M utate(Crossover(•, •)) on two randomly chosen parents. But as M utate and Crossover are different, IGA has very different offsprings.

B HYPER-PARAMETER STUDY ON SEM:

To explore how hyper-parameter of SEM influences the efficacy, we try different ranging from 0 to 1.2 for three models on IMDB with or without adversarial attacks. The results are illustrated in Figure 3 .

On benign data, as shown in Figure 3 (a), the classification accuracy of the models decreases a little when increases. Because a bigger indicates that we need less words to train the model, which could degrade the efficacy of the models. Nevertheless, the classification accuracy does not decrease much as SEM could maintain the semantic invariance of the original text after encoding.

Then we show the defense efficacy of SEM on the three models when changing the value of , as shown in Figure 3 (b)-(d). When = 0 where SEM could not take any impact, we see that the accuracy is the lowest under all attacks. When increases, SEM starts to defend the attacks, the accuracy increases rapidly and reach the peak when = 0.5. Then the accuracy decays slowly if we continue to increase . Thus, we choose = 0.5 to be a good trade-off on the accuracy of benign examples and adversarial examples. 5 to Table 6 . We see that IGA substitutes less words than GA on these models under normal training. I enjoyed this film which I thought was well written and proceeded, there was plenty of humorous and a igniting storyline, a tepid and enjoyable experience with an emotional terminate. GA 99.9 1 I am sorry but this is the hardest film I have ever seen in my life. I cannot believe that after making the first one in the series they were able to get a budget to make another. This is the least terrifying film I have ever watched and laughed all the way through to the end.

68.9. 0:

This is a unique masterpiece made by the best superintendent ever lived in the ussr. He knows the art of film making and can use it supremely alright. If you find this movie, buy or copy it! 72.1 0 I enjoyed this film which I thought was well written and acted, there was plenty of humour and a provoking storyline, a lukewarm and agreeable experience with an emotional ending.

IGA 99.8 1 I am sorry but this is the hardest film I have ever seen in my life. I cannot believe that after making the first one in the series, they were able to get a budget to make another. This is the least scary film I have ever watched and laughed all the way through to the end.

This is a sole masterpiece made by the best director ever lived in the ussr. He knows the art of film making and can use it very well. If you find this movie, buy or copy it! I enjoyed this film which I thought was well written and acted , there was plenty of humour and a provoking storyline, a warm and enjoyable experience with an emotional ending.

Original 97.0 0 I am sorry but this is the worst film I have ever seen in my life. I cannot believe that after making the first one in the series, they were able to get a budget to make another. This is the least scary film I have ever watched and laughed all the way through to the end.

95.3. 1:

This is a unique masterpiece made by the best director ever lived in the ussr. He knows the art of film making and can use it very well. If you find this movie, buy or copy it! 98.2 0 I enjoyed this film which I thought was well written and proceeded, there was plenty of humorous and a igniting storyline, a tepid and enjoyable experiment with an emotional terminate.

GA 78.8 1 I am sorry but this is the hardest film I have ever seen in my life. I cannot believe that after making the first one in the series, they were able to get a budget to make another. This is the least scary film I have ever watched and laughed all the way through to the end.

This is a unique masterpiece made by the best superintendent ever lived in the ussr. He knows the art of film making and can use it supremely alright. If you find this movie buy or copy it! 81.2 0 I enjoyed this film which I thought was alright written and acted, there was plenty of humour and a arousing storyline, a lukewarm and enjoyable experiment with an emotional ending.

IGA 78.8 1 I am sorry but this is the hardest film I have ever seen in my life. I cannot believe that after making the first one in the series they were able to get a budget to make another. This is the least scary film I have ever watched and laughed all the way through to the end.

This is a sole masterpiece made by the best director ever lived in the ussr. He knows the art of film making and can use it very alright. If you find this movie buy or copy it!

:



Figures and Tables:

Figure 1 (a), we postulate that the generalization of the model leads to the existence of adversarial examples. More generally, given a data point x ∈ X , ∃x ∈ V (x), f (x ) = y true where x is an adversarial example of x.

Figure 1: The neighborhood of a data point x in the input space. (a) Traditional training: there exists some data point x that the model has never seen before and yields wrong classification, in other words, such data point x will be an adversarial example. (b) Adding infinite labeled data: this is an ideal case that the model has seen all the data points to resist adversarial examples. (c) Constructing a convex outer bound: all data points in this polytope will share the label of x. (d) Mapping neighborhood data points: mapping all neighbors to the center x so as to eliminate adversarial examples.

consists news article pertaining four classes: World, Sports, Business and Sci/Tech. Each class contains 30, 000 training examples and 1, 900 testing examples. Yahoo! Answers (Zhang et al., 2015) is a topic classification dataset from the "Yahoo! Answers Comprehensive Questions and Answers" version 1.0 dataset with 10 categories, such as Society & Culture, Science & Mathematics, etc. Each class contains 140,000 training samples and 5,000 testing samples.

Figure 2: Classification accuracy by human evaluation. Human Evaluation. To further verify that the perturbations in the adversarial examples generayed by IGA are hard for humans to perceive, we also perform a human evaluation on IMDB with 35 volunteers. We first randomly choose 100 benign examples that can be classified correctly and generate adversarial examples by GA and IGA on the three models so that we have a total of 700 examples. Then we randomly split them into 7 groups where each group contains 100 examples. We ask every five volunteers to classify one group independently. The accuracy of human evaluation on benign examples is 93.7%. As shown in Figure 2, the classification accuracy of human on adversarial examples generated by IGA is slightly higher than those generated by GA, and is slightly closer to the accuracy of human on benign examples. Summary. IGA can achieve the highest attack success rate when compared with previous synonyms substitution based adversarial attacks and yield lower word replacement rate than GA. Besides, the adversarial examples generated by IGA maintains the same transferability as GA does and are a little bit harder for humans to distinguish. Several generated adversarial examples by GA and IGA are listed in Appendix C.

Figure 3: The classification accuracy for various ranging from 0 to 1.2 for three models on IMDB.

Accuracy of various classification models on the datasets, with and without defenses, under adversarial attacks. For each model (Word-CNN, LSTM, or Bi-LSTM), if we look at each row, the highest classification accuracy for various defense methods is highlighted in bold to indicate the best defense efficacy; if we look at each column, the lowest classification accuracy under various adversarial attacks is highlighted in underline to indicate the best attack efficacy. NT: Normal Training, AT: Adversarial Training.

Table content: <table><tr><td>Dataset</td><td>Attack</td><td colspan="2">Word-CNN(%)</td><td/><td>LSTM(%)</td><td colspan="2">Bi-LSTM(%)</td></tr><tr><td/><td/><td>NT</td><td colspan="2">AT SEM NT</td><td colspan="2">AT SEM NT</td><td>AT SEM</td></tr><tr><td/><td colspan="7">No Attack 88.7 89.1 86.8 87.3 89.6 86.8 88.2 90.3 87.6</td></tr><tr><td/><td>GSA</td><td colspan="2">13.3 16.9 66.4</td><td colspan="2">8.3 21.1 72.2</td><td colspan="2">7.9 20.8 73.1</td></tr><tr><td>IMDB</td><td>PWWS</td><td>4.4</td><td>5.3 71.1</td><td>2.2</td><td>3.6 77.3</td><td>1.8</td><td>3.2 76.1</td></tr><tr><td/><td>GA</td><td colspan="2">7.1 10.7 71.8</td><td>2.6</td><td>9.0 77.0</td><td>1.8</td><td>7.2 71.6</td></tr><tr><td/><td>IGA</td><td>0.9</td><td>2.7 65.1</td><td>0.9</td><td>1.8 71.2</td><td>0.9</td><td>2.7 69.3</td></tr><tr><td/><td colspan="7">No Attack 91.7 92.2 88.7 91.8 92.1 90.9 91.7 92.2 88.7</td></tr><tr><td>AG's News</td><td>GSA PWWS GA</td><td colspan="6">33.0 37.8 63.9 45.9 56.7 83.2 33.0 37.8 63.9 30.7 41.5 67.6 50.0 55.7 85.0 30.7 41.5 67.6 24.1 40.6 77.9 43.8 57.3 86.4 24.1 40.6 77.9</td></tr><tr><td/><td>IGA</td><td colspan="6">21.5 35.5 70.3 40.0 55.3 81.8 21.5 35.5 70.3</td></tr><tr><td/><td colspan="7">No Attack 68.4 69.3 65.8 71.6 71.7 69.0 72.3 72.8 70.2</td></tr><tr><td>Yahoo! Answers</td><td>GSA PWWS GA</td><td colspan="6">19.6 20.8 49.4 27.6 30.5 48.6 24.6 30.9 53.4 10.3 12.5 52.6 21.1 22.9 54.9 17.3 20.0 57.2 13.7 16.6 59.2 15.8 17.9 66.2 13.0 16.0 63.2</td></tr><tr><td/><td>IGA</td><td colspan="6">8.9 10.0 51.4 10.5 15.1 53.3 12.4 13.5 55.7</td></tr></table>

find that the adversarial examples in NLP also exhibite a good transferability. Therefore, a good defense method not only could defend the adversarial attacks but also resists the transferability of adversarial examples. To evaluate the ability of preventing the transferability of adversarial examples, we generate adversarial examples on each model under normal training, and test them on other models with or without defense on Yahoo! Answers. The results are shown in Table 2. Almost on all models with adversarial examples generated by other models, SEM could yield the highest classification accuracy. Accuracy of various classification models for adversarial examples generated on other models on Yahoo! Answers for evaluating the transferability. * indicates that the adversarial examples are generated based on this model. As shown in Table 1, looking at each column, we see that under normal training (NT) and adversarial training (AT), IGA can always achieve the lowest classification accuracy, which corresponds to the highest attack success rate, on all models and datasets among the four attacks. Under review as a conference paper at ICLR 2020 at local minimum while IGA continues to substitute words and gain a lower classification accuracy, as demonstrated in Table 1.

Table content: <table><tr><td>Attack</td><td colspan="2">Word-CNN(%)</td><td/><td>LSTM(%)</td><td colspan="2">Bi-LSTM(%)</td></tr><tr><td/><td>NT</td><td>AT SEM</td><td>NT</td><td>AT SEM</td><td>NT</td><td>AT SEM</td></tr><tr><td>GSA</td><td colspan="2">19.6* 52.7 57.5</td><td colspan="2">52.6 58.4 61.8</td><td colspan="2">52.7 57.5 59.6</td></tr><tr><td colspan="3">PWWS 10.3* 54.4 57.2</td><td colspan="2">46.5 57.7 61.4</td><td colspan="2">53.1 57.9 56.8</td></tr><tr><td>GA</td><td colspan="2">13.7* 49.9 55.2</td><td colspan="2">43.0 66.0 65.6</td><td colspan="2">56.4 65.5 67.4</td></tr><tr><td>IGA</td><td colspan="2">8.9* 53.7 56.5</td><td colspan="2">46.5 56.6 58.6</td><td colspan="2">53.1 56.8 57.2</td></tr><tr><td>GSA</td><td colspan="4">47.2 52.7 55.9 27.6* 60.9 62.1</td><td colspan="2">53.8 61.9 62.8</td></tr><tr><td colspan="5">PWWS 43.7 54.7 56.5 21.1* 59.9 61.8</td><td colspan="2">50.6 59.2 61.4</td></tr><tr><td>GA</td><td colspan="4">41.0 48.5 54.8 15.8* 57.4 57.5</td><td colspan="2">43.4 58.2 60.9</td></tr><tr><td>IGA</td><td colspan="4">47.8 53.0 55.2 10.5* 53.4 58.3</td><td colspan="2">53.5 59.0 61.1</td></tr><tr><td>GSA</td><td colspan="2">43.7 53.4 54.3</td><td colspan="4">52.9 57.7 58.7 24.6* 60.4 61.1</td></tr><tr><td colspan="3">PWWS 41.7 48.5 49.7</td><td colspan="4">41.2 58.0 60.4 17.3* 60.1 58.6</td></tr><tr><td>GA</td><td colspan="2">36.9 45.7 49.0</td><td colspan="4">43.0 58.8 60.7 13.0* 58.2 60.0</td></tr><tr><td>IGA</td><td colspan="2">44.8 50.6 52.3</td><td colspan="4">45.1 57.4 58.7 12.4* 60.1 61.1</td></tr><tr><td colspan="5">5.4 EVALUATION ON ATTACK METHODS (IGA VS. GA)</td><td/></tr><tr><td colspan="7">For text attacks, we compare the proposed IGA with GA from various aspects, including attack</td></tr><tr><td colspan="4">efficacy, transferability and human evaluation.</td><td/><td/></tr><tr><td>Attack Efficacy.</td><td/><td/><td/><td/><td/></tr></table>

The word substitution rate for GA and IGA on different models.

Table content: <table><tr><td colspan="2">Dataset Attack</td><td colspan="3">Word-CNN(%)</td><td/><td>LSTM(%)</td><td/><td colspan="3">Bi-LSTM(%)</td></tr><tr><td/><td/><td>NT</td><td colspan="3">AT SEM NT</td><td colspan="3">AT SEM NT</td><td colspan="2">AT SEM</td></tr><tr><td>IMDB</td><td>GA IGA</td><td>9.3 6.4</td><td>9.3 7.8</td><td colspan="3">4.3 10.0 10.6 6.3 5.3 6.9</td><td>4.0 5.7</td><td>6.3 5.6</td><td>8.0 6.6</td><td>3.1 7.5</td></tr><tr><td>AG's</td><td>GA</td><td colspan="2">10.3 17.7</td><td colspan="3">6.6 18.3 21.2</td><td colspan="3">9.8 12.0 21.4</td><td>8.5</td></tr><tr><td>News</td><td>IGA</td><td colspan="2">12.1 11.4</td><td colspan="3">6.3 14.4 12.0</td><td colspan="3">9.6 13.5 11.6</td><td>4.6</td></tr><tr><td>Yahoo!</td><td>GA</td><td>12.4</td><td>9.5</td><td colspan="3">4.7 12.5 15.8</td><td colspan="3">8.1 13.9 15.3</td><td>4.7</td></tr><tr><td>Answers</td><td>IGA</td><td>6.4</td><td>7.1</td><td>3.7</td><td>7.9</td><td>8.2</td><td>4.5</td><td>3.6</td><td>8.2</td><td>5.1</td></tr></table>

y true then

Table content: <table><tr><td>7:</td><td>return x adv</td></tr><tr><td>8: 9:</td><td>end if P g 1 ← x adv</td></tr><tr><td>10:</td><td/></tr></table>

The adversarial examples generated by GA and IGA on IMDB using Word-CNN model.

Table content: <table><tr><td/><td colspan="2">Confidence(%) Prediction</td><td>Text</td></tr><tr><td/><td/><td/><td>I enjoyed this film which I thought was well written and</td></tr><tr><td/><td>97.9</td><td>1</td><td>acted , there was plenty of humour and a provoking story-line, a warm and enjoyable experience with an emotional</td></tr><tr><td/><td/><td/><td>ending.</td></tr><tr><td/><td/><td/><td>I am sorry but this is the worst film I have ever seen in</td></tr><tr><td/><td/><td/><td>my life. I cannot believe that after making the first one</td></tr><tr><td>Original</td><td>99.7</td><td>0</td><td>in the series, they were able to get a budget to make an-</td></tr><tr><td/><td/><td/><td>other. This is the least scary film I have ever watched and</td></tr><tr><td/><td/><td/><td>laughed all the way through to the end.</td></tr><tr><td/><td/><td/><td>This is a unique masterpiece made by the best director</td></tr><tr><td/><td>95.8</td><td>1</td><td>ever lived in the ussr. He knows the art of film making and can use it very well. If you find this movie, buy or</td></tr><tr><td/><td/><td/><td>copy it!</td></tr><tr><td/><td/><td/><td>I cared this film which I thought was well written and</td></tr><tr><td/><td>50.6</td><td>0</td><td>acted, there was plenty of humour and a igniting story-line, a tepid and enjoyable experience with an emotional</td></tr><tr><td/><td/><td/><td>ending.</td></tr><tr><td/><td/><td/><td>I am sorry but this is the harshest film I have ever seen</td></tr><tr><td/><td/><td/><td>in my life. I cannot believe that after making the first</td></tr><tr><td>GA</td><td>92.7</td><td>1</td><td>one in the series, they were able to get a budget to make</td></tr><tr><td/><td/><td/><td>another. This is the least scary film I have ever watched</td></tr><tr><td/><td/><td/><td>and laughed all the way through to the end.</td></tr><tr><td/><td/><td/><td>This is a sole masterpiece made by the nicest director per-</td></tr><tr><td/><td>59.0</td><td>0</td><td>manently lived in the ussr. He knows the art of film mak-ing and can use it much well. If you find this movie, buy</td></tr><tr><td/><td/><td/><td>or copy it!</td></tr><tr><td/><td/><td/><td>I enjoyed this film which I think was well written and</td></tr><tr><td/><td>88.3</td><td>0</td><td>acted, there was plenty of humour and a causing story-line, a lukewarm and enjoyable experience with an emo-</td></tr><tr><td/><td/><td/><td>tional ending.</td></tr><tr><td/><td/><td/><td>I am sorry but this is the hardest film I have ever seen</td></tr><tr><td/><td/><td/><td>in my life. I cannot believe that after making the first</td></tr><tr><td>IGA</td><td>70.8</td><td>1</td><td>one in the series, they were able to get a budget to make</td></tr><tr><td/><td/><td/><td>another. This is the least scary film I have ever watched</td></tr><tr><td/><td/><td/><td>and laughed all the way through to the end.</td></tr><tr><td/><td/><td/><td>This is a sole masterpiece made by the best director per-</td></tr><tr><td/><td>54.8</td><td>0</td><td>manently lived in the ussr. He knows the art of film mak-ing and can use it very well. If you find this movie, buy</td></tr><tr><td/><td/><td/><td>or copy it!</td></tr></table>

The adversarial examples generated by GA and IGA on IMDB using LSTM model.

Table content: <table><tr><td colspan="2">Confidence(%) Prediction</td><td>Text</td></tr><tr><td/><td/><td>I enjoyed this film which I thought was well written and</td></tr><tr><td>99.9</td><td>1</td><td>acted , there was plenty of humour and a provoking story-line, a warm and enjoyable experience with an emotional</td></tr><tr><td/><td/><td>ending.</td></tr><tr><td/><td/><td>I am sorry but this is the worst film I have ever seen in</td></tr><tr><td/><td/><td>my life. I cannot believe that after making the first one</td></tr><tr><td>97.2</td><td>0</td><td>in the series, they were able to get a budget to make an-</td></tr><tr><td>Original</td><td/><td>other. This is the least scary film I have ever watched and laughed all the way through to the end.</td></tr><tr><td/><td/><td>This is a unique masterpiece made by the best director</td></tr><tr><td>99.7</td><td>1</td><td>ever lived in the ussr. He knows the art of film making and can use it very well. If you find this movie, buy or</td></tr><tr><td/><td/><td>copy it!</td></tr><tr><td>88.2</td><td>0</td><td/></tr></table>

The adversarial examples generated by GA and IGA on IMDB using Bi-LSTM model.

Table content: <table><tr><td colspan="2">Confidence(%) Prediction</td><td>Text</td></tr><tr><td>99.6</td><td>1</td></tr></table>

Peer review (iclr2020):
This paper focuses on synonym based substitution defense from adversarial attacks (SEM) and proposes an improved adversarial attack approach (IGA). The topic is important and the proposed idea could make the adversarial attack more meaningful. Unlike prior work using spelling checkers (map wrongly spelled words to correct ones) to reduce the effects of character modifying based attacks, the authors map word synonyms to a unique encoding. The authors claim that the results demonstrate that SEM can significantly improve the robustness of neural networks and that IGA can achieve better attack performance compared to existing attacks. The work is generally well-explained. Being limited to word synonym substitution based attacks makes the paper a little bit narrow, but it is fine if the methods are thoroughly investigated. Could you use any typical and existing cluster algorithms with the SEM encoder? Why do you want to invent something new (since there is no reference for the proposed Algo. 1, I have to assume that the authors did invent it)? Are there any advantages of the proposed Algo. 1 over some typical cluster algorithms? Did you fine-tune the word embedding? if embeddings are not fixed during training, it may change the Syn(w, delta,k), since calculating Syn(w, delta,k) is based on the embeddings, right? how does k affect the experiment? One concern from Algorithm 1 is that the mapping E you want to learn is biased by the order of how you traverse in W (line 2 in Algo. 1). Suppose you traverse W by the order (...,w_1,w_2,w_3,...) , if w_2 is in both Syn(w_1,delta,k) and Syn(w_3,delta,k), then E(w_2) = E(w_1). However if the order is (...,w_3,w_2,w_1,...), then E(w_2) = E(w_3). I wonder whether this matter or not. How about the computational costing time for GSA,PWWS, GA, and IGA ? This could matter if you compared their attack performance with your proposed IGA. IGA could traverse all synonyms of a word no matter what value k is. Does this have a similar impact with the cases we increase k or delta (the distance threshold)? All these cases will make the search space bigger and may also cost longer time (like more iterations), I think. In the extreme cases of IGA, if two words are mutually the only synonym with each other, it could replace each other for many times. The good thing is that there was a maximum number, lambda. BTW, what is the maximum number lambda? The authors mention they randomly sample 200 examples to evaluate the efficiency of the SEM method. The SEM layer is not that time-consuming during training. I guess that the adversarial attack should be time-consuming? In this case, changing GA to IGA should be more carefully evaluated, it may cost a longer time. minor comments 1. In Algo. 1, we can remove *E[w_j*] 
eq NONE* in line 5, since it was already mentioned in line 4. 2. Can you directly report the numbers in Figure 2? 3. you mention in the introduction that the extra encoder is called SEM, and then you call the clustering algorithms also SEM. So should SEM be the encoder for the defense, or just a new cluster algorithm? 4. The subscripts for w and w* are confusing. In the first equation (the unnamed one), the subscripts for w* (1,2,...k) seem like the order based on the distance. In the paragraph just below equation (1), the subscripts for w* or w (i.e., 1,2,...n) denote the word order based on the input x. In Algo. 1, the subscripts for w denote the order in the vocabulary. It may need to be changed in some ways. 5. In the first paragraph of Sec. 2, did you explain K? I think K (capital one) and k are not related, could you change one of them to another letter.