BESA: BERT-based Simulated Annealing for Adversarial Text Attacks

1 Introduction

Deep Neural Networks (DNNs) have shown the vulnerability to adversarial examples in Natural Language Processing (NLP) field for text classification [Papernot et al., 2016]. Adversarial text example is the original input with some malicious perturbations. These modifications are usually imperceptible to human readers but can easily subvert DNNs correct prediction. Therefore, exploring potential textual adversarial attacks is crucial to understand DNNs behaviors and ensure their robust performance, especially on those securitycritical applications, such as sentiment analysis and toxic comment detection [Zhang et al., 2019].

∗Corresponding Author

Existing text attack algorithms can be roughly divided into three groups: character-level attacks, sentence-level attacks, and word-level attacks. The character-level attacks (e.g., noise → nosie) result in misspelled words, and the sentence-level attacks (e.g. inserting a sentence into the original text) usually lead to dramatic semantic changes. Therefore, most recent works have focused on the word-level attacks with two main steps: (1) determining the substitution words, and (2) determining which word(s) to be substituted. In the first step, the substitution words should be semantically close to the original word so that the modifications are imperceptible to humans. Typical strategies search candidate words from the Glove embedding space [Alzantot et al., 2018], the WordNet synonym space [Ren et al., 2019], and the HowNet sememe space [Zang et al., 2020]. However, these algorithms create the candidates subset for every single word and ignore their contextual environments, which easily produce out-of-context modifications [Li et al., 2020]. In the second step, most prior works perform word replacement by descending order of word importance score (WIS). There are various definitions for WIS, such as probability weighted word saliency (PWWS) [Ren et al., 2019] and the changes of DNNs' confidence after deleting a word [Jin et al., 2020; Garg and Ramakrishnan, 2020], etc. However, altering words by a fixed (or static) WIS order usually leads to local optimal and word over-substitution. For example, we empirically found that changing the top-3 WIS words {top1, top2, top3} altogether can not mislead a classifier, but sometimes forming a two-word combination {top1, top3} can make it.

In this paper, we propose BESA, a BERT-based Simulated Annealing algorithm, to address these problems and generate fluent adversarial text examples. Specifically, we employ the BERT Masked Language Model (BERT-MLM) [Devlin et al., 2018] to generate candidates in the first step. The BERTMLM is trained from both left-to-right and right-to-left (i.e., bi-directorial text sequences) on extremely large English text data with general-purpose. Therefore, it is capable of predicting contextual fitting words [Devlin et al., 2018]. In the second step, we propose to determine the word replacement priority via the Simulated Annealing (SA) optimization method [Kirkpatrick et al., 1983]. The SA breaks the fixed (static) replacement order and provides more options of word replacements, which is significantly effective in finding high-quality adversarial examples. Besides, it allows our algorithm to escape from local optima by a controlled probability, making it closer to the best possible word substitution in the attack. Extensive experiments demonstrate that the proposed BESA achieves the highest attack success rate via a low word substitution rate. We emphasize our main contributions as below.

• We propose to generate natural substitution tokens via a pre-trained BERT-MLM. These tokens can well fit the text contextual and be read smoothly by humans.
• We design an effective Simulated Annealing (SA) method to determine the word replacement priority. The SA objective function is designed for accomplishing a high attack success rate (ASR) and low word substitution rate (WSR).
• We evaluate the effectiveness of our overall model, the BESA, on five public datasets. Experimental results manifest that our BESA not only improves the ASR and reduces the WSR, but also shows superiorities in keeping grammar correctness and semantic similarities.

2 RelatedWorks

We categorize textual attack methods into character-level attacks, sentence-level attacks, and word-level attacks. The character-level attacks handle text adversarial samples by inserting, deleting, or swapping characters [Liang et al., 2018]. However, these operations produce misspelled words, which can be easily defended by a spelling checker. Sentence-level attack concatenates a distracting sentence with the input text to confuse the reading comprehension system [Jia and Liang, 2017]. Nevertheless, the generated sentences are usually human unreadable and semantically uninterpretable.

Word-level attack replaces the original words with their synonyms by solving two main challenges (1) how to select synonym candidates and (2) how to determine the word replacement priority. Early works employ Glove embedding vectors to represent words and identify the nearest neighbors as synonym candidates [Alzantot et al., 2018; Jin et al., 2020]. However, the Glove embedding usually fails to distinguish antonym from synonym. For example, the word pair {east,west} and {expensive, cheaper} are close in the Glove embedding space, but they are semantically opposite. Therefore, a counter-fitting post process is essential to ensure the semantic similarity. Compared with Glove embedding, searching synonyms from human-annotated linguistic thesauri is a more straightforward approach. [Ren et al., 2019] selected synonyms from WordNet, which groups words based on their meanings, and designed the probability weighted word saliency (PWWS) for greedy word perturbation. [Zang et al., 2020] presented a sememe-based word substitution, which searched replacement tokens from HowNet and found adversarial example via particle swarm optimization (PSO). However, Glove-based and thesaurusbased strategies collect substitution words for every single word, ignoring howwell they fit into the context.

Several recent works take advantage of language models to predict contextual friendly tokens, intending to generate more fluent text adversarial samples [Garg and Ramakrishnan, 2020; Li et al., 2020]. However, both of them adopt a static word replacement order guided by the word importance score (WIS), leading to redundancy word substitution. The difference lies in that [Garg and Ramakrishnan, 2020] defined the WIS as probability decrease of the correct label after deleting a word, while [Li et al., 2020] replaced each of the original words by a dummy symbol [MASK].

3 The BESAMethod

This section details our BESA algorithm. Before delving into details, we present the attack settings and expectations.

3.1 Black-box Untargeted Attack

The BESA algorithm is designed for black-box attack, where no DNNs architecture, internal parameter, and gradient information are accessible, a setting close to real-life attack scenarios. The only capacity of a black-box adversary is inputting an example to the victim model and querying its prediction results, acting as a regular user.

Suppose we are given a text dataset with N samples X = {X1,X2, · · · ,XN}, belonging to L labels Y = {Y1,Y2, · · · ,YL}, a DNNs classifier F needs to learn a input-output mapping f : X → Y so that any input X ∈ X can be classified to the true label Ytrue, by optimizing the posterior probability:

An adversarial text example X∗ is defined as the original input X that is modified with slight perturbation ∆X, i.e., X∗ = X+∆X. A text adversarial attacker expects the perturbation ∆X is imperceptible to human but can mislead the classifier F into any label other than the true label (untargeted attack) or a user-specified label (targeted attack). In this work, we design BESA as an untargeted attack. In linguistic perspectives, the adversarial example should be lexical correct, grammar correct, and semantic similar to the original texts. These constraints aim to ensure humans cannot spot the difference before and after an attack. To this end, we generate contextual friendly synonyms via BERT-MLM (Sec 3.2) and reduce the substitution rate by SA optimization (Sec 3.3).

3.2 BERT-based Candidate Selection

Since BERT Masked Language Model (BERT-MLM) is trained by masking a proportion of words, it is capable of generating supplementary words to reconstruct the sentence. Suppose the input sentence X = {w1, w2, · · · , wn} contains n words, for each word wi, we replace it with the [MASK] token and then predict the substitution words Si with BERTMLM. The substitution words are contextual-aware and wellfitted with the surrounding text, but can not guarantee semantic similarity. For example, in the sentence "I [MASK] this move", predicting the [MSAK] as "like" or "hate" are equally fluent but delivering different sentiment. Therefore, we employ the Universal Sentence Encoder (USE) [Cer et al., 2018] to calculate the semantic similarity score and filter out lowsemantic-consistency words by a threshold. To avoid grammar errors, we further filter out candidates that have different Part-of-Speech (POS) tags with the original word. These two filter steps are uniformly denoted in line 5 of Algorithm 1.

Algorithm 1: The proposed BESA algorithm

Input: Original sentence with n words X = (w1, · · · , wn) Input: DNNs classifier F Output: Adversarial example Xadv 1 Initialization: USE threshold = 0.5, the highest temperature Tmax = 1000, the lowest temperature Tmin = 50, internal simulation steps K = 20, the balance parameter δ = 0.01, attack radius parameter σ = 3, the initial adversarial example Xadv = X, and the initial time t = 0; /* BERT-based Candidate Selection */ 2 for i = 1 to n do 3 Replace the wi with [MASK]; 4 Generate the candidate set Bi with BERT-MLM; 5 Bi = Filter(Bi); 6 Find the best candidate w∗ i fromBi via Eq. (5); /* Definition of the Objective Function */ 7 Function J(F,X,Xadv, δ): 8 Calculate the true label score: Ptrue = F(Xadv); 9 Count the perturbation cost: cost = len(X ̸=Xadv); 10 Objective value: y = Ptrue + δ × cost; 11 return y; /* The Simulated Annealing Optimization */ 12 while Tmax > Tmin do 13 for k = 1 to K do 14 y = J(F, X, Xadv , δ); 15 index = t+randint(0, σt) ; ▷ Random index 16 if index > n then 17 continue; 18 Replace the index word in Eq. (7) to craft Xkadv; 19 ynew = J (F, X, Xkadv , δ); 20 if ynew - y < 0 then 21 Xadv =Xkadv ; ▷ Good modification 22 else 23 p = e-(ynew-y)/Tmax ; ▷ Metropolis 24 r = random(0, 1); 25 if r < p then 26 Xadv =Xkadv ; ▷ Bad modification 27 if F(Xadv) ̸=Ytrue then 28 returnXadv ; ▷ Successful attack 29 t = t + 1; 30 Tmax = Tmax/(1+ t) ; ▷ Quick cooling 31 return Adversarial example Xadv

After filtering, every w′i ∈ Si is a potential candidate for replacing the original word wi. To select the best candidate from Si, we define the candidate importance score Iw′i as the true score probability reduction:

where

Then we identify the candidate w′i that attains the highest Iw′i as the best substitution word. The best candidate selection method R(wi, Si) can be denoted as below:

Repeating these steps on every word completes the first stage of our algorithm, which is summarized in Algorithm 1 from line 2 to line 6. Based on the best substitution words, we obtain n adversarial examples {X∗1 ,X∗2 , · · · ,X∗n } with each X∗i = {w1, · · · ,w∗ i , · · · ,wn}. The change of true label probability between X and X∗i indicates the strongest attack effect that can be achieved by altering wi.

A straightforward way to determine the word substitution priority is by the descending order of the ∆P ∗ i , where the resorted sequence order is given in Eq. (7).

However, sequentially modifying words by this static order easily leads to word over-substitution, as there is no theoretical guarantee that the top-k words combination contributes most in misleading a classifier. For example, replacing the two word {top1, top3} in H sometimes even better than replacing three words {top1, top2, top3}. Therefore, it is critical to optimize word substitution priority.

3.3 Simulated Annealing (SA) Optimization

Before elaborating on our algorithm, we first explain the concepts of the original Simulated Annealing (SA). The SA is a combinatorial optimization algorithm inspired by the physical annealing procedure of metals. It targets to find the minimal value of an objective function from many independent molecules (i.e., variables). Specifically, the algorithm starts from a "melting" state with high temperature and gradually reduces the temperature until the system "freezes" to a steady-state. At each temperature, the interval simulation must proceed long enough for the system to reach equilibrium. During simulating, any better molecular movement that decreases the objective function is directly accepted. Nevertheless, modifications that increase the objective function are also accepted with a transition probability. Therefore, the SA is possible to transition from the local optimum, while a static greedy search and particle swarm optimization (PSO) are incapable of avoiding such a risk.

In this paper, we treat the best word substitution order determination as a multivariates combinatorial optimization problem. Specifically, a word in the sentence corresponds to a molecule in search space, and each molecule position movement corresponds to a word substitution. To optimize the word substitution priority by SA, we first initialize essential variables in line 1 of Algorithm 1, including the highest temperature Tmax, the lowest temperature Tmin, the internal simulation steps at each temperature K, etc. When designing the objective function (Algorithm 1 from line 7 to line 11), we expect that a good adversarial example Xadv can deliver a low true label probability

and simultaneously preserve a low perturbation cost

where len(X ̸= Xadv) count the number of different words between X and Xadv. The final objective value balances Eq.

(8) and Eq. (9) with an parameter δ

The SA optimization starts from line 12 of Algorithm 1 with the highest temperature Tmax. At each temperature, enough simulations (K) are attempted to reach the equilibrium. Each simulation first queries the objective function J to obtain the original objective value of y in line 14. Then the SA algorithm randomly selects a molecular from the whole molecular space to move. In this work, we restrict the word selection interval with an attack radius parameter σ, and the target word index is determined by Eq. (11)

where randint(0, σt) randomly selects a integer from [0, σt]. This enables us to locate the most important word in the initial time (t = 0) and enlarges the attack radius as time goes by. Then we replace the index-th word of H to craft a new adversarial example in line 18 and query the new objective value ynew in line 19. To decide whether the modification is accepted or not, we employ the typical Metropolis principle

If the word replacement decreases the objective function, we accept it as a good modification in line 21. Otherwise, we accept a bad modification by a probability as listed from line 23 to line 26. After modification, if the classifier F is misled, we return the successful adversarial example in line 28; otherwise, the internal simulation continues to iterate. If no successful adversarial example can be found through all internal iterations, the time t will pass and the temperature will decrease. For efficiency, we adopt the quick cooling function

This procedure continues until we achieve a successful attack or the temperature reduced to Tmin. Intuitively, the SA optimization provides sufficient combination options with internal simulations and can jump out of local optima by Metropolis criteria. These properties are significant in achieving a high success attack rate with a low perturbation cost.

4 Experiments and Analysis

We provide the source code in the supplementary material to ensure the results in this section are reproducible.

4.1 Datasets and VictimModels

We conduct experiments on five widely used text datasets, including IMDB [Maas et al., 2011] , Question Natural Language Inference (QNLI) [Rajpurkar et al., 2016], Movie Review (MR) [Pang and Lee, 2005], Stanford Natural Language Inference (SNLI) [Bowman et al., 2015], and SST-2 [Socher et al., 2013]. The IMDB, MR, and SST-2 are used for binary sentiment classification tasks, where QNLI and SNLI are used for natural language inference. Statistical details of these datasets are summarized in Table 1.

We apply our BESA to six victim models, such as CNN, LSTM, BERT [Devlin et al., 2018], DistilBERT [Sanh et al., 2019], RoBERTa [Liu et al., 2019], and XLNet [Yang et al., 2019]. The CNN consists of a 200-dimensional embedding layer and a 1-D convolutional layer containing 150 filters with filter sizes of 3×4×5. The LSTM consists of a 200-dimensional embedding layer and a bidirectional LSTM layer with 150 hidden states. Both CNN and LSTM have a dropout rate of 0.3. We download BERT (bert-base-uncased), RoBERTa (roberta-base), XLNet (xlnet-base-cased), and DistilBERT (distilbert-base-uncased, distilbert-base-cased) from the Transformers model hub HuggingFace 1 . Different versions of DistilBERT are implemented on different datasets, i.e., (uncased: IMDB, QNLI) and (cased: SNLI, SST-2). The original test results are listed in Table 2's "ACC" column.

4.2 Baselines

To evaluate the effectiveness of our BESA, we compare it with typical black-box word-level attack algorithms, such as TextFooler (TEFO) [Jin et al., 2020], BERT-based Adversarial Examples (BAE) [Garg and Ramakrishnan, 2020], BERTAttack (BEAT) [Li et al., 2020], PWWS [Ren et al., 2019], and PSO [Zang et al., 2020]. As mentioned in Section 2, most existing works (TEFO, BAE, BEAT, and PWWS) rephrase words by a static WIS descending order, which is inflexible in finding the optimal solution. [Zang et al., 2020] treated every sentence as a particle and optimize its location in the search space via PSO. However, the PSO needs abundant of query to find the final modification, leading to high computational cost and low efficiency (Table 3).

4.3 EvaluationMetrics and Experiment Settings

Evaluation Metrics. We evaluate the attack performance mainly by the Attack Success Rate (ASR) and Word Substitution Rate (WSR). The ASR is defined as the proportion of successful adversarial examples to the total number of correctly classified samples. The WSR refers to the percentage of replaced words occupied by the total number of words in the sentence. Intuitively, a rational attacker expects a high ASR with a low WSR. Besides, we assess the quality of the adversarial text examples by calculating the grammar errors and semantic consistency.

Experiment Settings. The parameter settings for our BESA are given in line 1 of Algorithm 1. Parameter tuning details are listed in supplementary. For all baselines, we use their author recommended parameter value. To achieve efficiency, we randomly select 1000 samples from the test set to craft adversarial samples. All experiments are implemented on the TextAttack framework [Morris et al., 2020].

1 https://huggingface.co/models

4.4 Experimental Results

The experimental results of both ASR and WSR are listed in Table 2. For the ASR, our BESA achieves nearly perfect results on all scenarios and outperforms the baselines, often by a large margin. The WSR results show that our BESA obtains such attack effects by making the lowest word modifications in most cases. We attribute this superiority to the SA optimization, as this is the major improvement of our BESA compared with baselines (BAE and BEAT). Additionally, Table 2 results show that the advanced models (BERT, DistilBERT, RoBERTa, and XLNet) are generally more robust than traditional classifiers (CNN and LSTM), as attacking them need more word substitutions but obtaining less success rate.

Figure 2: The semantic similarity before and after attacks.

Grammar Errors. Grammatical errors in a sentence largely affect its fluency, so fewer grammar errors are naturally preferred. We employ the LanguageTool 2 to detect the spell and grammar errors for the original samples and the corresponding adversarial samples on all datasets. Figure 1 plots the number of grammar errors induced by various attack algorithms. Clearly, our BESA brings the minimum number of syntax errors and sometimes even fixes the original errors.

Semantic Consistency. The semantic similarity between the original sample and the adversarial sample plays an important role in ensuring that readers do not change their initial decisions. We adopt the Universal Sentence Encoder (USE) score to indicate the semantic consistency before and after attacks. Figure 2 shows the USE score on the five datasets and all victim models. Results illustrate that our BESA achieves comparable (second highest) semantic consistency.

2 https://languagetool.org/

Efficiency Analysis. We carry out all experiments on Enterprise Linux Workstation 7.7 with Intel(R) Xeon(R) Gold 6150 2.7GHz CPU, NVIDIA Quadro P5000 16G GPU, and 176GB RAM. Table 3 lists the time consuming of various methods by attacking BERT. Results show that our BESA costs more time than static counterparts (TEFO, BAE, BEAT, PWWS) but more efficient than the PSO. Besides, the PSO is not suitable for attacking very deep models (DisBERT, BERT, XLNet, RoBERTa) with long text input. For example, it only completed 73 IMDB samples in one week to cheat BERT. For this reason, results of PSO are shown as infeasible to obtain (i.e., dash "-") in Tables 2 and 3.

4.5 Adversarial Training

Adversarial training is a prevalent technique to improve the DNNs robustness by incorporating adversarial examples into the training set. To validate this, we train the LSTM model on the MR dataset and obtains 75.14% test accuracy. Then we randomly generate and join {500, 1000, 2000} MR adversarial samples to its training data and retrain the LSTM. The 3-run main accuracy and standard deviation for our BESA are shown in Figure 3. We only show the average accuracy for baselines to make the results clear. Figure 3 demonstrates that the model robustness gradually improved by appending more adversarial examples, and our BESA brings greater robustness improvement than the five baselines.

4.6 Transferability

The transferability of adversarial attack implies whether its adversarial samples designed for misleading the classifier F can also fool an unknown classifier F ′ . We evaluate the transferability on SST-2 dataset. Specifically, we choose the ad- SST-2 (Label change): Negative (51%) → Positive (98%)

Very special effects, brilliantly bold colors visuals and heightened reality can't hide the giant achilles' heel in "stuart little 2": there 's just no story, folks.

MR (Label change): Negative (56%) → Positive (81%)

The first mistake, I suspect, is casting shatner as a legendary professor and kunis as a brilliant college arts student-where's pauly shore as the rocket scientist?

Table 4: Adversarial examples crafted by BESA. The blue and red color denotes the original and substitution words, respectively.

versarial examples crafted for attacking BERT to perform the transfer attack on four unknown models (LSTM, CNN, DistilBERT, and RoBERTa). Their classification accuracy on both clean data (no attack) and adversarial data are shown in Figure 4. Figure 4 illustrates that our BESA generates adversarial samples with overall higher transferability than baselines.

4.7 Qualitative Examples

We list two adversarial examples crafted by our BESA in Table 4. Both examples successfully mislead the LSTM model from Negative to Positive with high confidence (i.e., > 80%). Owing to the BERT-MLM, the substitution words (visuals and arts) are well-fit the surrounding text and do not change the sentiment label from human perception. More examples can be found in the supplementary material.

5 Conclusion and FutureWork

In this paper, we proposed an innovative word-level text attack algorithm named BESA (BERT-based Simulated Annealing). The BESA employs the BERT Mask Language Model to generate substitution candidates and optimizes the word substitution order via Simulated Annealing (SA). We evaluate the effectiveness of BESA by comparing it with representative baselines on widely used text datasets. Experimental results illustrate that our BESA achieves the highest attack success rate by modifying the least words. Due to the contextual-awareness and the low modification rate of our method, BESA makes fewer grammar errors and keeps a high semantic similarity. Additionally, the adversarial examples generated by our algorithm show good properties in transfer attack and adversarial retrain. In the future, improving the language model to further enhance the semantic similarity is a promising work direction.