{'fraction_non_alphanumeric': 0.028981232255447808, 'fraction_numerical': 0.015670513624128905, 'mean_word_length': 4.898651587646803, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Adversarial Black-Box Attacks On Text Classifiers Using Multi-Objective Genetic Optimization Guided By Deep Networks

We propose a novel genetic-algorithm technique that generates black-box adversarial examples which successfully fool neural network based text classifiers. We perform a genetic search with multi-objective optimization guided by deep learning based inferences and Seq2Seq mutation to generate semantically similar but imperceptible adversaries. We compare our approach with DeepWordBug (DWB) on SST and IMDB sentiment datasets by attacking three trained models viz. char-LSTM, word-LSTM and elmo-LSTM. On an average, we achieve an attack success rate of 65.67% for SST and 36.45% for IMDB across the three models showing an improvement of 49.48% and 101% respectively. Furthermore, our qualitative study indicates that 94% of the time, the users were not able to distinguish between an original and adversarial sample.


Introduction
Deep Neural Networks (DNNs) have witnessed tremendous success in day to day applications like chat-bots and self-driving vehicles. This has made it imperative to test the robustness of these models prior to their deployment for public consumption. Szegedy et al. (2013) first demonstrated the vulnerability of DNNs in computer vision by strategically fabricating adversarial examples. These carefully curated examples remain correctly classified by a human observer but can fool a targeted model.
Adversarial generation can be broadly classified into two types based on their access to the model. The generation algorithms that rely on the model internals are known as white-box algorithms (Papernot et al., 2017;Kurakin et al., 2016;Baluja and Fischer, 2017). Others (Su et al., 2019;Sarkar et al., 2017;Cisse et al., 2017) which work without any knowledge about the model parameters and gradients are known as black box algorithms and are more prevalent in real-world scenarios. These works triggered a flurry of research towards i) evaluating the vulnerability of DNNs by attacking them with unperceivable perturbations, ii) measuring sensitivity and iii) developing defense mechanisms against such attacks. As industry increasingly employs DNN models in NLP tasks like text classification, sentiment analysis and question answering, such systems are also under the threat of adversaries (Zhao et al., 2019;Horton, 2016).
Existing adversarial techniques used to misguide image-based systems cannot be applied to text based systems because of two key reasons. First, image pixel values are continuous whereas words are discrete tokens. Hence, small changes in pixel values go unnoticed but the same cannot be said for typos or misfit words. Second, due to its discrete nature, input words are mapped to a continuous space using word embeddings. Therefore, any gradient computation is done only on the embeddings and not directly on the input words. Hence, previous gradient based attacks like FGSM (Goodfellow et al., 2014) are difficult to apply on text models. In addition to the above challenges, perturbations applied to original text should be carefully crafted so that the adversarial sample is still a) structurally similar: the user should not be able to find differences in a quick glance, b) semantically relevant: the generated sample should bear the same meaning as the source sample and c) grammatically coherent: the generated sample should look natural and be grammatically correct.
To generate text adversaries satisfying multiple criteria, we formulate a multi-objective optimization problem, that once solved, results in the generation of text samples with adversarial properties. Thus, we model adversarial generation as a natural search space selection problem where the best adversaries are selected from a pool of samples initialized by different techniques. This selection is based on multiple objectives, where each objective measures a desirable adversarial quality. The selected samples then further undergo mixing (reproduction) and slight modifications (mutation) to create even better adversaries. As this model resembles the biological process of evolution, we rely on genetic algorithms as a tool to solve this optimization problem. Our genetic algorithm works in tandem with a sophisticated SeqtoSeq model for mutation, embedding based word replacements, textual noise insertions and deep learning based objectives to ensure a good selection of candidate solutions.
In summary, we propose a novel multi-objective genetic optimization that works in tandem with deep learning models to generate text adversaries satisfying multiple criterion. We conduct an extensive quantitative and qualitative study to measure the quality of the text adversaries generated and compare them with DeepWordBug (DWB) .

Existing Literature
Most black-box adversarial algorithms for text have been rule based or have used supervised techniques. Such attacks are generally applied at sentence, word and character granularities.
At the sentence granularity, Jia and Liang (2017) shows how the addition of an out-of-context sentence acts like an adversary for comprehension systems. However, these sentences are easily identifiable as out-of-context by human evaluators.
At the word granularity, perturbations are generally introduced by selective word replacements. Papernot et al. (2017) focuses on minimum word replacements for generating adversarial sentences. Alzantot et al. (2018) uses single-objective genetic algorithms to generate adversaries by replacing words with their synonyms at an attempt to preserve semantics. Sato et al. (2018) introduces direction vectors which associate the perturbed embedding to a valid word embedding from the vocabulary.
To target character based models, adversarial attacks focusing at a character level have also surfaced.  suggests a method to introduce random character level insertions using nearest keyboard neighbours. Li et al. (2018) focuses on attacking with character and word level perturbations. They introduce misspellings which map to unknown tokens when the model refers to a dictionary. However, introducing numerous misspellings makes it very difficult to comprehend adversaries.
Multi-objective optimization has been effective for many applications like image-segmentation and generating speech adversaries for ASR systems (Bong and Mandava, 2010;Khare et al., 2018). Our multi-objective optimization algorithm leverages the use of both selective word replacements and character level error insertion strategies. But unlike other works that rely on simple heuristics, we ensure that the modifications we make are essential and minimal by infusing guidance from deep learning based objectives. Guided by networks like Infersent (Conneau et al., 2017), OpenAI GPT (Radford, 2018) and SeqtoSeq (Bahdanau et al., 2014), we create adversaries that are structurally similar, semantically relevant and grammatically coherent.

Proposed Approach
Multi-objective optimization is the process of optimizing multiple objective functions (Coello et al., 2006). The interaction among different objectives gives rise to a set of compromised solutions known as Pareto-optimal solutions (Fonseca and Fleming, 1995). Evolutionary algorithms are one class of popular approaches to generate such Paretooptimal solutions.
Inspired from evolutionary systems, we consider adversarial text generation as an evolutionary process to generate adversarial samples satisfying multiple criteria. Carefully designed deep learning objectives and text processing algorithms assist in creating improved candidate solutions (text-samples) for fooling the classifier. Further, we propose various metrics to assess the fitness of a candidate (text-sample) within a population. After multiple generations, we finally apply heuristics to pick the most appropriate adversary that satisfies the desired adversarial properties discussed in the introduction.
An overview of the proposed algorithm for producing adversarial text samples for a given input is shown in Algorithm 1. The entire process is divided into six main stages typical to an evolutionary process: i) Population Initialization, ii) Mutation, iii) Fitness Evaluation iv) Mating Pool Identification, v) Crossover and vi) Dominance Evaluation.
Our algorithm supports two ways of fooling classifiers. 1) Selectively substituting words with semantically equivalent terms. 2) Combining substitution of selective words along with introduction of typographical errors. We refer to these two modes of attacks as Attack Single and Attack Combined respectively. We report the results for both the types in the experiments section. The flow of the algorithm across the 6 stages can be seen in Fig. 1 and lines 65 to 94 in Algorithm 1. The details of each stage are explained in the following sections.

Initialization
In this phase (Algorithm 1, Lines 15-28), candidate samples in the population are initialized. For each sample, we lowercase and remove punctuation from the original text and perform word-level perturbations. These perturbations are done by first identifying the most important words in the text and then replacing them with semantically equivalent terms. To find the important words in the text, we max-pool the penultimate layer of the In-ferSent Model, which has been trained as a universal sentence encoder. Once the most important words are identified, we search for their nearest neighbours in the GloVe embedding space (Pennington et al., 2014). This is done by finding similar vectors having cosine similarity more than δ (a hyper-parameter). We leverage the FAISS toolkit (Johnson et al., 2017) for this step. To make sure that these neighbours are synonyms, we also verify that the cosine similarity is more than δ even in the counter-fitted vector space (Mrkšić et al., 2016).
After finding the possible substitutions, we then initialize a population of candidate samples with all the possible combinations of original and substituted words. From this population, a small subset is selected randomly to make the genetic computation tractable. This careful initialization maintains diversity in the population and seeding it with original text guarantees faster convergence.

Mutation
The diversity of the existing population is further enhanced by mutation. In the text space, the mutation of a candidate is defined as a suitable word substitution. We rely on 2 main approaches for substitutions 1) GloVe Mutator -a nearest neighbour search in the counter-fitted vector space as mentioned in the initialization phase and 2) Sequence Mutator -an encoder-decoder deep learning model to perform mutations in a sentence.
The Sequence Mutator is trained as a sequence to sequence bi-directional LSTM model with attention for the sole objective of predicting the same input that is fed to it. Hence the Sequence Mutator is made to iteratively predict a word given its left Find important words w imp in t Orig using Inf er 19: Find substitute words w sub for the w imp with nearest neighbour search 20: Allow only synonyms from w sub using w cf to ensure similarity > δ 21: 22: % Find all combinations of substitutions and create sentences % 23: combinations ← powerset(w sub ) 24: for w ∈ combinations do 25: Apply w in t Orig and add to P else 71: % Half population (P S ) has only word swaps % 72: % Half population (P T ) has word swaps with typos % 76: 78: 79: % Perform GA multiple times % 80: repeat 81: if M ode is Attack Single then 82: % Perform an iteration of GA on the whole population % 83: % Perform an iteration of GA on the word swaps population % 87: % Perform 1 iteration of GA on the typo population % 90: 92: until P T otali+1 == P T otali or i > maxiters 93: return P T otali+1 This training objective makes the Sequence Mutator very similar to a language model. However, a key difference between the two, is the initial state supplied to the decoder. In a language model, the initial state is generally a vector of zeros, however, in the Sequence Mutator it is the context vector passed by the encoder. This context vector helps in copying the input sentence effectively. We perform beam search to get the top 5 predictions from the Sequence Mutator. This step helps to randomly sample a mutated form of the input sentence.
In general, it is observed that the most probable prediction made by the Sequence Mutator is the original sentence itself and the remaining 4 predictions are similar sentences with 1 or 2 words substituted probabilistically during decoding. We use the fairseq toolkit (Ott et al., 2019) for fast prototyping of sequence to sequence model architectures.
It is very important to note that in the case of Attack Single , we pass the entire population through the Sequence Mutator or Glove Mutator, whereas, in the case of Attack Combined , we pass half of the population through the Sequence Mutator or Glove Mutator and for the other half we introduce typographical errors (Algorithm 1, Lines 66-77).
For typographical errors, we randomly select one or multiple words wherein the maximum number of words selected are less than 10% of the length of the sentence. For the selected words, only 1 of the following ways of typographical error introduction is chosen. i) Character swaps (Soni and Lin, 2019) and ii) QWERTY character map exchanges (Pruthi et al., 2019). Character swaps are implemented by randomly choosing a character from the word and then swapping its place with an adjacent character. For the QWERTY character map exchange, the first step is to maintain a list of the adjacent symbols for every character in the QWERTY keyboard. When a character is randomly chosen, it is replaced by any one of the adjacent symbols. Both errors are included keeping in mind that they constitute a large portion of the most common typographical errors made while typing.
These steps are outlined in Algorithm 1 (Lines 5-13). To ensure diversity, we maintain both the normal and mutated forms of each candidate in the population. In Algorithm 1, the normal and mutated forms of a candidate individual are denoted as Ind and IndM ut respectively.

Fitness Evaluation
In-order to generate better candidate samples in the next generation, we need to identify the fittest candidates from the current population. The fitness function (Algorithm 1, Lines: 30-33) evaluates the adversarial nature of the samples i.e. the structural similarity, the semantic relevance and the ability to fool the target classification model. The fitness function for each candidate is a 3 element vector F .
The first objective value f 1 measures the absolute change in the posterior probabilities when an individual candidate (Ind) and when the original text (Orig) are fed to the classifier (M odel).
f 1 = abs(M odel(Ind) − M odel(Orig)) (2) The second objective value measures the structural similarity between Ind and Orig. This is calculated by finding the positional jaccard co-efficient between the 2 sentences. As shown in Fig. 2, the intersection is 2 words and the union is 6 words. Hence, P osJaccard = 1/3.
The third and final objective value measures the semantic relevance between Ind and Orig. For this, we use the InferSent model to encode the sentences to fixed size vectors after which the cosine similarity is calculated.
f 3 = Sim( Inf er(Orig), Inf er(Ind)) (5) In this manner, we incorporate each adversarial quality as an objective value derived from a deep learning model. By doing so, we ensure that only adversaries that have high structural similarity and semantic relevance progress to later iterations and form a major portion of the gene pool.

Mating Pool Identification
Once we calculate all the fitness functions, we then identify the fittest parents from the population. This step (Algorithm 1, Lines: 40-43) conducts a tournament selection to choose parents that will further undergo a crossover operation to produce children. In this tournament, a candidate sample completely dominates another opponent if the sample is at least as good as the opponent across all objective values. If not, the tie breaker for the tournament is the crowding metric which is a sub-part of the NSGA-2 (Deb et al., 2002) algorithm.

Crossover
To enhance diversity in the adversarial samples, crossover is performed among the parent candidates. For crossover (Algorithm 1, Lines: 45-54) between two parents, we use a single point structural crossover. A word index is chosen randomly and then parts of the text after the index are swapped between the 2 samples. As each candidate sample has a normal and mutated form, we perform crossovers between normal and mutated forms separately. Hence 2 candidate samples produce 4 offsprings -2 from crossover of the normal forms and 2 from crossover of the mutated forms.

Dominance Evaluation
After the creation of children we proceed to evaluate their objective values. Post this, we are left with two sets of populations -the first is the set of parents and the second is the set of children.
To maintain a constant population size during adversarial generation, we need to choose the best candidates from the combined group containing both parents and children. For this (Algorithm 1, Lines: 35-38), we employ our selection algorithm based on NSGA-2 (Deb et al., 2002). In its standard formulation NSGA-2 groups candidates together if and only if every candidate in the group is not better than every other candidate in that group across all the objective values. Within the same group, ranks are given to candidates based on crowding metrics. We find that on experimentation, the standard formulation is successful at selecting good quality adversaries from the population.

Final Selection
This process of evolution is repeated until the last iteration (60 steps) is reached or until population convergence (Algorithm 1, Lines: 79-93). To measure the grammatical coherence of the candidate samples, we pass the adversaries through the Ope-nAI GPT language model (LM) (Radford, 2018) and calculate the word normalized perplexity loss for each of the adversaries. The lower the loss for a particular candidate sample the better its quality. In order to select the best adversarial candidate from the final population, it was essential to derive a metric that emphasized on the desired adversarial qualities. For a given candidate individual (Ind i ), we would prefer that it has higher structural similarity (f 2 i ) and higher semantic relevance (f 3 i ) while simultaneously having a lower word normalized perplexity (LM i ).
Using this intuition, the metric (score i with α = 1.2) was calculated for each adversary and the best elmo-LSTM -to + IMDB : caught the tail ... dont see the shooting only adds to the chillness of the plot to see both child infant and adult alike struggle to comprehend scavenge and come to terms with the senseless inane shootings was at times overwhelming surprising and will admit that i shed quite.
elmo-LSTM + to - scoring adversaries were chosen from the test sets of SST-2 and for 1000 reviews from IMDB corpus. On a K80 GPU, each iteration takes 0.5 seconds for Glove and 3 seconds for the Sequence Mutator.

Implementation Details
Classifiers: We studied the efficacy of our algorithm on 3 classifiers that consume text in unique ways -a word-LSTM model (word-tokens), a char-LSTM model (character-tokens) and an elmo-LSTM model (word and character tokens). Every model was trained on two sentiment datasets viz. Stanford Sentiment Treebank (SST-2) (Socher et al., 2013) and IMDB movie reviews (Maas et al., 2011). The char and word LSTMs were trained using the AllenNLP (Gardner et al., 2017) toolkit. The elmo-LSTM was trained from scratch using a combination of Elmo (Peters et al., 2018) and GloVe embeddings. Sequence Mutator: We trained 2 different instances of the Sequence Mutator -one for each dataset. In order to enhance its mutation capability, we train the mutator on a combined corpus of the test-set of the datasets and Wikitext-2 (Merity et al., 2016). This allowed the mutator to be finetuned for the particular dataset but yet at the same time be exposed to a general natural language understanding. To ensure predictions were accurate, we windowed long sentences in the dataset into short groups of utmost 30 words. To ensure a fast inference, we limited the model size to 4.9 * 10 7 parameters. While training, we used a learning rate of 10 −3 and eventually stopped the process when the average softmax cross-entropy loss of the model reached 0.05 or below. Table 1 lists few adversarial samples generated by our approach. In order to validate the efficacy of our algorithm, we generate adversaries for test-set inputs in SST and IMDB, and record the drop in accuracies for each classifier. As a baseline, we also attacked the 3 classifiers with the current state of the art approach DeepWordBug (DWB) .

Evaluation
We performed both quantitative (Table 2) and qualitative (section 4.3) studies of our algorithm versus DWB. The study covers the following three dimensions -i) Performance degradation of the target models, ii) Transferability of adversarial samples across models, iii) Desired adversarial qualities in the generated samples.
The effect of adversarial text on a model is measured by the success rate and the decrease in model accuracy. Table 2 lists the original accuracy of the models, success rate of generated adversaries and the degraded accuracy of the models. There is a significant improvement over DWB across all the experiments. We also infer that our most successful strategy is the Attack Combined algorithm with a Sequence Mutator. On average, our success rate was 65.67% for SST classifiers and 36.45% for IMDB classifiers, where as, for DWB, it was only 43.93% and 18.1% respectively. As a result, there is a larger drop in accuracy when using our algorithm when compared to DWB as listed in Table 2. We also highlight the difference in success rates of the Attack Single mode with the Glove and Sequence mutator respectively. If one does not intend to allow typographical adversaries, there is a significant benefit in using the Sequence mutator.
Further, Table 3 shows the transferability of ad-   Figure 4: Perplexity Score versaries between the 3 models. As shown, for the SST dataset, 41.44% and 41.24% of the adversaries curated for word-LSTM and elmo-LSTM respectively were transferable to char-LSTM. This clearly indicates that our attacks are transferable across models. As DWB aggressively introduces typographical errors in its adversaries, each typo maps to the unknown token irrespective of the classifier. Hence, as evident from Table 3, such adversaries are more transferable than those created by our approach. However, the increase in typos impact the quality of generated adversaries and affect its similarity with the original text.
This is further verified in Fig. 3 and Fig. 4, where we depict the distribution of various metrics that measure the quality of generated adversaries. We evaluate the adversaries using the objectives f 2 and f 3 along with natural language metrics like  Blue, Meteor, Greedy matching score (GMS) and Vector extrema cosine similarity (VECS) (Sharma et al., 2017). We obtain an average f 2 value of 0.747 for SST and 0.832 for IMDB in comparison to DWB (0.396 and 0.756 respectively). This 88.6% increase for SST and 10.05% increase for IMDB in f 2 values indicates that we change far fewer words than DWB. This can be verified by the Average Words Replaced statistic in Table 3. We notice a similar trend for the f 3 objective values as well. We also outperform DWB on word overlap metrics like Blue and Meteor. The Blue score for SST has a noticeably larger deviation for DWB when compared to our approach. Meteor mimics human judgment better than Blue by incorporating stemming and synonymy. We report higher Meteor scores in our generated adversaries signifying minimal perturbations. Similar improvements are noticed in sentence level metrics like VECS and GMS. VECS calculates the cosine similarity of sentence level embeddings whereas GMS calculates similarity scores between word embeddings and averages it for a sentence. Both of these sentence level metrics attain very high values with less deviation. These quantitative measures indicate that most of our adversaries enjoy high structural similarity and semantic relevance. In order to study the grammatical coherence of our adversaries, we also study the LM scores in Fig. 4. We observe that our average LM score for generated adversaries in SST and IMDB were 5.94 and 5.5 which is 24.1% and 5.66% lower in comparison to DWB (7.83 and 5.83) signifying better grammatical coherence. All the quantitative measures suggest that our algorithm performs well at maximizing adversarial qualities in all generated adversaries. However, this is further validated by a qualitative study.

Qualitative Evaluation
We conducted a human evaluation study to determine if the generated adversaries were in reality visually imperceptible to humans. In order to assess the quality of the adversaries across various criteria, 34 users (students and researchers from a computer science background) were presented with randomly sampled pairs of original and generated adversaries and then asked to answer multiple questions. We infer our insights from a total of 831 data points obtained through this study. Firstly, they were asked to predict the label of both the original and adversarial sample. 94% of the users identified the same label for both the original and adversarial text indicating that adversarial samples remained unperceivable to users but were yet able to fool the model. Secondly, the users were asked whether the pairs had the same semantic meaning. 85% of users identified them as semantically similar. This proved that the adversarial samples retained enough details from the reference and were semantically relevant. Finally, users were asked to rate the naturalness and grammatical correctness of each sample on a scale of 1 − 5. The average score of 3.2 for adversarial samples was very close to the score of 3.5 for original samples which indicated that the adversarial samples were natural and grammatically coherent.

Conclusion and Future Work
We have successfully established that genetic algorithms can produce good quality adversaries if coupled with inference from deep learning based objectives and Seq2Seq mutation. Both the qualitative and quantitative evaluations indicate that most of the adversaries generated have desired adversarial qualities of structural similarity, semantic relevance and grammatical coherence.
The possible future directions for this work are i) Experimentation with algorithm sub-modules -During Initialization, LIME (Ribeiro et al., 2016) based strategy can be used to select important words for perturbation. ii) Data Augmentation -We can study the performance of the classifiers when trained with these additional adversarial samples. iii) Expanding Attacks -We can study our performance on tasks like question answering, summarization etc.