TextDecepter: Hard Label Black Box Attack on Text Classification

Given an input text space $X$ and a set of $n$ labels , $Y=\{Y_{1},Y_{2},...,Y_{n}\}$, we have a text classification model $F:X\rightarrow Y$ which maps from the input space $X$ to the set of labels $Y$. Let there be a text $x\in X$ which is correctly predicted by the model to be belonging to the class $y\in Y$ i.e. $F(x)=y$. We also have a semantic similarity function $Sim:X\times X\rightarrow[0,1]$. Then, a successful adversarial attack changes the text $x$ to $x_{adv}$, such that

where $\epsilon$ is the minimum similarity between original and adversarial text.

Let us consider a binary classification model with labels $\{Y_{0},Y_{1}\}$ which we want to attack. We are given a text $T\in X$ having $m$ sentences, $S=\{s_{1},s_{2},...,s_{m}\}$. The classification model correctly predicts $T$ to be belonging to class $Y_{0}$ i.e. $F(T)=Y_{0}$. We input each of the $m$ sentences to $F$ and get their individual labels. Let $A$ and $B$ form a partition of $S$ such that $F(a)=Y_{0},\forall a\in A$ and $\mathcal{P}$ (A) be the power set of $A$. Let $\mathcal{A}_{r}$ be a set of $r$-combinations of $A$. We define another set $G=\{B\cup c\ |c\in\mathcal{P}(A)\}\}$. We refer to each of the elements in $G$ as an ’aggregate’.

We consider the attack in the black-box setting, where an attacker does not have any information about the model weights or architecture and is allowed to query the model with specific inputs and get the final decision of the classifier model as an output. Further, the class confidence scores are not provided to the attacker in the output, making it a hard-label black-box attack. Although NLP APIs provided by Google, AWS and Azure do provide the confidence scores for the classes, but in a real-world application setting, like toxic content detection on a social media platform, the confidence scores are not provided, thereby making it a hard label black-box setting. Such an attack scenario also helps to gauge the model robustness.

The proposed methodology for generating adversarial text has three main steps:

Step 1: Sentence Importance Ranking: We observe that when people convey opinions or emotions, not all the sentences convey the same emotion, few sentences are just facts without any emotion or sentiment. Other sentences can also be stratified based on varying levels of intensity. This forms the basis of our sentence ranking algorithm which helps to prioritize our attack on specific portions of the text in order of importance.

We assume that different sentences in the text contribute to the overall class decision to a varying level of intensity. Each of the sentences can either support or oppose the final decision of the classifier and the intensities which they do so are additive. Consider an example of sentiment analysis, where the labels are positive and negative. The assumption of additivity of sentence class intensity, also helps us to infer that sentences in set $B$ when joined together to form a text, will belong to class $Y_{1}$. Hereby, we refer to the same as the class of set $B$ or the classifier’s decision of set $B$.

We define the importance of a sentence in set $A$ by its ability to change the classifier’s decision of set $B$ from $Y_{1}$ to $Y_{0}$. If an individual sentence from set $A$ when added to set $B$ is able to change the class of set $B$ from $Y_{1}$ to $Y_{0}$, then we consider the sentence to belong to level 1 importance. More generally, if a sentence from set $A$ is able to change the classifier’s decision of set $B$ only when it is put together with some subset of $A$ with at least $k-1$ sentences, then the sentence belongs to level k importance. The $k-1$ other sentences in all such subsets also belong to level k importance. Also, once the importance of a sentence is fixed at the $k^{th}$ level we do not consider it in subsequent levels.

Step 2: Word importance ranking:

After finding the importance of sentences in step 1, we need to find the importance ranking of the words to be attacked in these sentences. We observe that words with a certain Part of Speech (POS) tags are more important than others. For example, for a sentiment classification task, adjectives, verbs, adverbs are more important than nouns, pronouns, conjunctions, or prepositions. Further, we consider adjectives to be more important than adverbs. Consider a sentence, “The movie was very bad”. In this sentence, “bad” is the adjective and shapes the sentiment of the sentence. The adverb “very” increases the intensity of the adjective, making the predicted class confidence score increase further.

Step 3: Attack: We use the word Level perturbations in order of word importance obtained from the previous step. We select synonyms to replace the original words using cosine distance between word vectors. Further, to maintain the syntax of the language, only those synonyms having the same POS tags as that of the original word are considered for further evaluations. Experiments are done using, both, coarse and fine POS tag masks.

Let us look at the details of each of these steps:

1. 1.

   Synonym extraction: We use the word embedding by [10] which obtained state-of-the-art performance on SimLex-999, a dataset designed by [11] to measure how well different models judge the semantic similarity between words.

2. 2.

   POS checking: To maintain the syntax of the adversarial example generated, we filter out the synonyms which have a different POS tag than the original word. We experiment with, both, coarse and fine POS tagging.

We select a synonym to replace a particular word if its usage leads to one of the following:

1. 1.

   Misclassification of the entire text.

2. 2.

   Misclassification of the original labeled sentence to which the target word belongs.

3. 3.

   Misclassification of the original label aggregate to which the target word belongs.

If multiple synonyms fulfill the rules, then the one which fulfills the rule of higher preference is selected. If multiple synonyms fulfill the highest preference rule, then that synonym is selected whose placement in the review is semantically nearest to the original review. We terminate the algorithm once the text misclassifies, or when all the important words have been iterated over.

The justification for the higher preference of sentence than the aggregate to which it belongs comes from the additivity assumption. Consider a sentence $v\in A$, $\{v\}\in\mathcal{A}_{r}$. Now, add it to set $B$ to form an ’aggregate’, i.e. $B\cup\{v\}\in G$. Assuming the additivity of class intensities of sentences, we can easily see that when sentences in $B\cup\{v\}$ are joined to form a piece of text, it either belongs to class $Y_{1}$ or, in case, it belongs to class $Y_{0}$, then the intensity of class $Y_{0}$ is lesser when compared to $v$ alone. In other words, an ’aggregate’ belonging to class $Y_{0}$ has lesser intensity of class $Y_{0}$ when compared with individual sentences belonging to class $Y_{0}$ which are part of that aggregate. Hence, a synonym which can flip the decision of the classifier, both, on the sentence and the aggregate (initially classified as $Y_{0}$) to which the sentence belongs would be preferred against a synonym which is just able to change the classifier’s decision on the aggregate alone.

Step 4: Reset insignificant replacements
Consider a directed acyclic graph, where a node represents a text and a directed edge between two nodes means that the latter node text can be obtained by replacement of a word $w$ in former node text by its most semantically similar synonym $w^{\prime}$, given that the synonym has the same POS tag as the original word. Further, the weight of each edge is 1. Then, crafting an adversarial example from a given piece of text can be formulated as a path finding problem as follows; find a path from an initial node $T$ to final node $T^{\prime}$, such that $F(T)=Y_{0}$ and $F(T^{\prime})\neq Y_{0}$. The sentence and word ranking algorithm decide the order of perturbation. Thereafter, we use the aggregates belonging to the original class as heuristics to guide our graph search. The algorithm stops once the text misclassifies. Although, the heuristics help us in finding a path, but they do not guarantee if it is the shortest path. In the absence of confidence scores of classes, the problem of finding the shortest path has an exponential search space. So, once the given text is turned adversarial, the algorithm visits all the replaced words and resets those replacements without which the perturbed text remains adversarial.

Let there be $n$ sentences in a text and $m$ words in total.

1. 1.

   Getting the class label of each of the individual sentences: $O(n)$

2. 2.

   Sentence Importance ranking: The algorithm takes all possible combinations of sentences from the set of original labeled sentences and insert each of them to the set of sentences which do not have the original label. Hence, the time complexity of this step becomes $O(2^{n})$.

3. 3.

   Word importance ranking:

   1. (a)

      Sort the original labeled sentences in order of their importance ranking: $O(n\log n)$

   2. (b)

      Iterate over all the words in the sorted sentences and make the word perturb sequence: $O(m)$

   3. (c)

      Generation of cosine similarity matrix of words in text with 65 thousand words in the vocabulary: $O(m)$

4. 4.

   Pick the top $k$ synonyms for each of the candidate words that are to be perturbed. The cosine similarity matrix consists of similarity of each of the words in the text with all the words in the vocabulary. We sort the similarity values for each word with all the other words in the vocabulary. Hence, amounting to total time complexity of $O(m)$

5. 5.

   Attack: Replace each of the $k$ synonyms of a word in the original text, the original labeled aggregates (obtained from sentence importance ranking step), and the original labeled sentences to which they belong. Hence, the time complexity of this step becomes $O(kmn)$.

6. 6.

   Removal of insignificant perturbations: $O(m)$

Hence, the overall time complexity of the attack framework becomes $O(2^{n})+O(kmn)$

The generation of adversarial texts requires that we are able to get the synonyms for a particular word during the attack phase. Hence, a cosine similarity matrix is kept in the RAM to quickly generate synonyms for a particular word. In our attack framework, we keep the cosine similarity of only the words in the text that is being attacked, with all the 65 thousand words in the vocabulary. It is an improvement over the memory requirement in the attack framework of TextFooler [7] which keeps the cosine similarity matrix of all the 65 thousand words in the vocabulary, constituting a square matrix of size 65 thousand, consuming nearly 17 GB of RAM if single-precision floating-point format is used.

We study the effectiveness of our attack methodology on sentiment classification on IMDB and Movie Review (MR) datasets. We target three models: word-based convolutional neural network (WordCNN) [12], word-based long-short term memory (WordLSTM) [13], and Bidirectional Encoder Representations from Transformers (BERT) [14]. We attack the pre-trained models open-sourced by [7] and evaluate our attack algorithm on the same set of 1000 examples that the authors had used in their work. We also run the attack algorithm against Google Cloud NLP API. The summary of the datasets used by [7] for training the models are in Table  I and their original accuracy are given in Table II

1. 1.

   Attack success rate: We first measure the accuracy of the target model on the 1000 test samples and call it original accuracy. Then, we measure the accuracy of the target models against the adversarial samples generated from the same test samples and call it after-attack accuracy. The difference between the original accuracy and the after-attack accuracy of a classification model is called the attack success rate.

2. 2.

   Percentage of Perturbed words: The percentage of words replaced by their synonyms on an average gives us a metric to quantify the change made to a given text.

3. 3.

   Semantic similarity: It tells us the degree to which the two given texts carry a similar meaning. We use the Universal Sentence Encoder to measure the Semantic Similarity between original and adversarial text. Since my main aim is to generate adversarial texts, we just control the semantic similarity to be above a certain threshold.

4. 4.

   Number of queries: The average number of queries made to the target model tells us the efficiency of the attack model.

We report our results of the hard label black-box attacks in terms of automatic evaluation on two text classification tasks using coarse and fine POS masks. The main results are summarized in Tables  III and IV. Our attack algorithm is able to bring down the accuracy of all the major text classification models with an attack success rate greater than 50% for all the models. Further, the percentage of perturbed words is nearly 3% for all the models on the IMDB dataset and between 10-16% for all the models on the MR dataset. In the IMDB dataset, which has an average word length of 215 words, our attack model is able to conduct successful attacks by perturbing less than 7 words on average. That means that our attack model can identify the important words in the text and makes subtle manipulations to mislead the classifiers. Overall, our algorithm can attack text classification models pertaining to sentiment analysis with an attack success rate greater than 50%, no matter how long the text sequence or how accurate the target model. Further, our model requires the least amount of information among all the models it is compared with.

The attack model is also able to attack GCP NLP API and brings down the accuracy from 76.4% to 16.7% for the MR dataset. Further, it changes only 10.2% of the words in the text to generate the adversary. The results are unprecedented as we have achieved the results without having any information about the confidence scores of the classes involved. The attack algorithm and the carefully crafted adversarial texts can be utilized for the study of interpretability of the BERT model [15].

The query number is almost linear to the text length, with a ratio in (6,10) which is at par with [7] and [4].

We compare our attack against state-of-the-art adversarial attack systems on the same target model and dataset. For GCP NLP API, we compare our attack results against [4] and [5] on MR datasets. With wordCNN and wordLSTM as the target models, the comparison is against [4], [6], [7]. The results of the comparison are summarised in table  V and  VI. The lower attack success rates, when compared to the other attack systems, can be attributed to the fact that our attack system does not make use of confidence scores of the classes that other published systems do.

Following the practice of [7], we perform human evaluation by sampling 100 adversarial examples from the MR dataset with the WordLSTM. We perform three experiments to verify the quality of our adversarial examples. First, the human judges are asked to give the grammaticality score of a shuffled mix of original and adversarial text on a scale of 1-5. As shown in Table, the grammaticality of the adversarial texts with fine POS tag mask is closer to the original texts when compared with coarser POS tag mask. However both of the scores are above 4 meaning that using, both, coarse and fine POS tags result in smooth adversarial texts.

Second, the judges assign classification labels to a shuffled set of original and adversarial texts, for both coarse and fine POS masks. The results show that the overall agreement between the labels of the original and adversarial text for both the cases are quite high, 92% and 93% respectively. This suggests that improving the grammaticality of the adversarial texts using a fine POS mask does not contribute much to the overall meaning of the texts to humans.

Third, the judges determine whether the adversarial texts retain the meaning of the original text. The judges are given three options, 1 for similar, 0.5 for ambiguous, and 0 for dissimilar. The average sentence similarity score is 0.88 when a fine POS mask is used compared to 0.86 when a coarse POS mask is used for synonym-selection, suggesting a marginal improvement in sentence similarity scores in the former.

Part of Speech (POS) tags can be of two types: Coarse-grained (Noun, Verb, Adjective, etc.) or Fine-grained (Noun-proper-singular, noun-proper-plural, verb-past, verb-present, etc). TextDecepter uses a POS mask to reject those synonyms which do not belong to the same POS as that of the original word when they are placed in the text. A Fine-grained POS mask helps to maintain grammaticality to a greater extent when compared to the coarse-grained POS mask as demonstrated in Table X. However, during human evaluation, we observed that improving the grammaticality of the adversarial texts for sentiment classification dataset using fine POS does not contribute much to the overall understanding of the text for humans. We recommend using the appropriate POS mask depending on the grammaticality requirement for the context in which adversarial texts are being generated.

Aggregates The most critical step of our algorithm is the use of aggregates, which belong to the original class, to select or reject synonyms for replacement. To validate the effectiveness of this step we remove the usage of aggregates and select a synonym for replacement only when its presence is able to misclassify the original text. The results for the BERT model are shown in table XI . After removing the sentence importance ranking step, we see that the after-attack accuracy increases by 32% for IMDB and 35% for MR dataset, respectively. This suggests the importance of aggregates for selecting synonym for replacement, the removal of which renders the attack ineffective. The aggregates generated in the sentence importance ranking step help us to select those synonyms which can take the original text towards misclassification.