Greedy Attack and Gumbel Attack: Generating Adversarial Examples for Discrete Data

Puyudi Yang, Jianbo Chen, Cho-Jui Hsieh, Jane-Ling Wang, Michael I. Jordan

Introduction

Robustness to adversarial perturbation has become an extremely important criterion for applications of machine learning in security-sensitive domains such as spam detection , fraud detection , criminal justice , malware detection , and financial markets . Systematic methods for generating adversarial examples by small perturbations of original input data, also known as “attack,” have been developed to operationalize this criterion and to drive the development of more robust learning systems .

Most of the work in this area has focused on differentiable models with continuous input spaces . In this setting, the proposed attack strategies add a gradient-based perturbation to the original input. It has been shown that such perturbations can result in a dramatic decrease in the predictive accuracy of the model. Thus this line of research has demonstrated the vulnerability of deep neural networks to adversarial examples in tasks like image classification and speech recognition.

We focus instead on adversarial attacks on models with discrete input data, such as text data, where each feature of an input sample has a categorical domain. While gradient-based approaches are not directly applicable to this setting, variations of gradient-based approaches have been shown effective in differentiable models. For example, Li et al. proposed to locate the top features with the largest gradient magnitude of their embedding, and Papernot et al. proposed to modify randomly selected features of an input through perturbing each feature by signs of the gradient, and project them onto the closest vector in the embedding space. Dalvi et al. attacked such models by solving an integer linear program. Gao et al. developed scoring functions applicable for sequence data, and proposed to modify characters of the features selected by the scoring functions. Attack methods specifically designed for text data have also been studied recently. Jia and Liang proposed to insert distraction sentences into samples in a human-involved loop to fool a reading comprehension system. Samanta and Mehta added linguistic constraints over the pool of candidate-replacing words.

We propose a two-stage probabilistic framework for generating adversarial examples for models with discrete input, where the key features to be perturbed are identified in the first stage and subsequently perturbed in the second stage by values chosen from a pre-fixed dictionary. We derive two methods—Greedy Attack and Gumbel Attack—based on the proposed framework. Greedy attack evaluates models with single-feature perturbed inputs in two stages, while Gumbel Attack learns a parametric sampling distribution for perturbation. Greedy Attack achieves higher success rate, while Gumbel Attack requires fewer model evaluations, leading to better efficiency in real-time or large-scale attacks. Table 1 systematically compares our methods with other methods.

In summary, our contributions in this work are as follows: (1) We propose a probabilistic framework for adversarial attacks on models with discrete data. (2) We show that Greedy Attack achieves state-of-the-art attack rates across various kinds of models. (3) We propose Gumbel Attack as a scalable method with low model evaluation complexity. (4) We observe that character-based models in text classification are particularly vulnerable to adversarial attack.

Framework

Methods

In this section we present two instantiations of our general framework: Greedy Attack and Gumbel Attack.

Let $e_{i}$ denote the $d$ -dimensional one-hot vector whose $i$ th component is $1$ . To solve Problem (3), we decompose the objective as:

where $x_{(i)}$ replaces the $i$ th feature of $x$ with $w_{0}$ . We observe that the approximated objective is maximized if

Similarly, we decompose the objective in Problem (4) by conditioning on $H^{i_{1}}$ , and again use a greedy approximation:

where $x_{(i_{1}\to w_{j})}$ perturbs $x$ by replacing the $i_{1}$ th feature of $x$ with the value $w_{j}$ , but keeps the rest of the features the same as $\hat{x}$ . The approximated objective is maximized when

The same applies to $i_{2},\dots,i_{k}$ . The algorithm Greedy Attack is built up from Equation (6) and Equation (8) in a straightforward manner. See Algorithm 1 for details.

2 Gumbel Attack

The Gumbel trick involves using a Concrete random variable is introduced as a differentiable approximation of a categorical random variable, which has categorical probability $p_{1},p_{2},\dots,p_{d}$ and is encoded as a one-hot vector in d. The Concrete random variable $C$ , denoted by $C\sim\text{Concrete}(p_{1},p_{2},\dots,p_{d})$ , is a random vector supported on the relaxed simplex $\Delta_{d}:\,=\{z\in^{d}:\sum_{i}z_{i}=1\}$ , such that $C_{i}\propto\exp\{(\log p_{i}+\varepsilon_{i})/\tau\}$ , where $\tau>0$ is the tunable temperature, and $\varepsilon_{j}:\,=-\log(-\log u_{i})$ , with $u_{i}$ generated from a standard uniform distribution, defines a Gumbel random variable.

and approximate $G$ by the random variable $U$ defined from a collection of Concrete random variables:

We write $U=U(\alpha,x,\varepsilon)$ as it is a function of the parameters $\alpha$ , input $x$ and auxiliary random variables $\varepsilon$ . The perturbed input $\hat{X}=\phi(X,G)$ is approximated as

where we identify $X_{i},w_{0}$ and $w_{j}$ with their corresponding embeddings for convenience of notation.

Combining the application of the Gumbel technique on the entire training data set $\mathcal{D}$ and the greedy objective on a subset of data set $\mathcal{D}_{0}$ , the final objectives become the following:

Experiments

We evaluate the performance of our algorithms in attacking three text classification models, including CNN and LSTM. See Table 2 for a summary of data and models used, and the supplementary material for model details. During the adversarial attack, inputs are perturbed at their respective feature levels, and words and characters are units for perturbation for word and character-based models respectively. Codes for reproducing the key results wcan be found online at https://github.com/Puyudi/Greedy-Attack-and-Gumbel-Attack. We compare Greedy attack and Gumbel attack with the following methods:

Delete-1 Score : Mask each feature with zero padding, use the decrease in the predicted probability as the score of the feature, and Mask the top- $k$ features as unknown.

DeepWordBug : For each feature, compute a linear combination of two scores, the first score evaluating a feature based on its preceding features, and the second based on its following features. Weights are selected by the user.

Projected FGSM : Perturb a randomly selected subset of $k$ features by replacing the original word $w$ with a $w^{\prime}$ in the dictionary such that $\|\text{sgn}(\text{emb}(w^{\prime})-\text{emb}(w))-\text{sgn}(\nabla f)\|$ is minimized, where $\text{emb}(w)$ is the embedding of $w$ , and $\nabla f$ is the gradient of the predicted probability with respect to the original embedding.

Saliency : Select the top $k$ features by the gradient magnitude, defined as the $l_{1}$ norm of the gradient with respect to the features’ embeddings, and mask them as unknown.

Saliency-FGSM: Select the top $k$ features based on the Saliency map, and replace each of them using projected FGSM.

Two word-based models are used: a word-based convolutional neural network , and a word-based Long Short-Term Memory (LSTM) network :

IMDB with a word-CNN: We use the Large Movie Review Dataset (IMDB) for sentiment classification . It contains $50,000$ binary labeled movie reviews, with a split of $25,000$ for training and $25,000$ for testing. We train a word-based CNN model, achieving $90.1\%$ accuracy on the test data set.

Yahoo! Answers with an LSTM We use the ten-category corpus Yahoo! Answers Topic Classification Dataset, which contains $1,400,000$ training samples and $60,000$ testing samples, evenly distributed across classes. Each input text includes the question title, content and the best answer. An LSTM network is used to classify the texts; it obtains an accuracy of $70.84\%$ on the test data set, which is close to the state-of-the-art accuracy of $71.2\%$ achieved by character-based CNNs .

For Gumbel Attack, we parametrize the identifier $p_{\alpha}(x)$ and perturber $q_{\theta}(x)$ with the model structure plotted in Figure 2, consisting of a local information component and a global information component. The identifier and the perturber are trained separately, but both by rmsprop with step size $0.001$ . The models in both stages are trained with the Gumbel objective ( $\lambda_{2}=0$ ) on the training data for two epochs, except for the one in the second stage on the IMDB data set, where we optimize the greedy objective on a subset of size $1,000$ before we optimize over the Gumbel objectives due to the high variance introduced by optimizing the Gumbel objective alone, given the limited training data.

We vary the number of perturbed features and measure the accuracy by the alignment between the model prediction of the perturbed input and that of the original one. The same metric was used . The success rate of attack can be defined as the inconsistency with the original model: $1-$ accuracy.

The average accuracy over test samples is shown in Figure 3. Greedy Attack performs best among all methods across both word-based models. Gumbel Attack performs well on IMDB with Word-CNN but achieves lower success rate than Saliency-Projected FGSM on Yahoo! Answers with LSTM. Examples of successful attacks are shown in Table 3 and Table 4.

2 Character-based models

We carry out experiments on the AG’s News corpus with a character-based CNN . The AG’s News corpus is composed of titles and description fields of $196,000$ news articles from $2,000$ news sources . It is categorized into four classes, each containing $30,000$ training samples and $1,900$ testing samples. The character-based CNN has the same structure as the one proposed in Zhang et al. . The model achieves accuracy of $90.09\%$ on the test data set.

Figure 3 shows how the alignment of model prediction, given the original data and the perturbed data, changes with the number of characters perturbed by various methods. Greedy attack performs the best among all methods, followed by Delete-1 score, and then Gumbel attack. It is interesting to see that a Character-based CNN does no better than random selection when only $5$ characters are perturbed. Examples of successful attacks are shown in Table 5.

3 Efficiency, transferability and human evaluation

The efficiency of generating adversarial examples becomes an important factor for large-scale data. We evaluate the clock-time efficiency of various methods. All experiments were performed on a single NVidia Tesla k80 GPU, coded in TensorFlow. Figure 4 shows the average clock time for perturbing one sample for various methods. Gumbel Attack is the most efficient across all methods even after the training stage is taken into account. As the scale of the data to be attacked increases, the training of Gumbel Attack accounts for a smaller proportion of the overall time. Therefore, the relative efficiency of L2X to other algorithms will increase with the data scale.

Transferability.

An intriguing property of adversarial attack is that examples generated for one model may often fool other methods with different structures . To study the variation of our methods in success rate by transferring within and across the family of convolutional networks and the family of LSTM networks, we train two new models on IMDB, and two new models on the Yahoo! Answers respectively. For the IMDB data set, we trained another convolutional network called CNN2, differring from the original one by adding more dense layer, and an LSTM which is same as that used for the Yahoo! Answers data set. For the Yahoo! Answers data set, we train a new LSTM model called LSTM2, which is one-directional with $256$ memory units, and uses GloVe as pretrained word embedding. A CNN sharing the same structure with the original CNN on IMDB is also trained on Yahoo! Answers.

Then we perturb each test sample with Greedy Attack and Gumbel Attack on the original model of the two data sets, and feed it into new models. The results are shown in Figure 5. Greedy Attack achieves comparable success rates for attack on Yahoo! Answers, but suffers a degradation of performance on the IMDB data set. Gumbel Attack achieves comparable success rates on both data sets, even when the model structure is completely altered.

Human evaluation.

To ensure that small perturbations of adversarial examples in text classification do not alter human judgement, we present the original texts and the perturbed texts, as generated by Greedy Attack and Gumbel Attack, to workers on Amazon Mechanical Turk. Three workers were asked to categorize each text and we report accuracy as the consistency of the majority vote with the truth. If no majority vote exists, we interpret the result as inconsistent. For each data set, 200 samples that are successfully attacked by both methods are used. The result is reported in Figure 5.

On the IMDB movie review data, human accuracy drops by $10.5\%$ and $7.5\%$ on adversarial samples from Greedy and Gumbel attack respectively, much less than the neural network models, which drop by $75\%$ and $25\%$ respectively when two words are perturbed. On character-based models, the accuracy of human judgements stays at comparable levels on the perturbed samples as on the original samples. The Yahoo! Answers data set is not used for human judgement because the variety of classes and the existence of multi-category answers incur large variance.

Discussion

We have proposed a probabilistic framework for generating adversarial examples on discrete data, based on which we have proposed two algorithms. Greedy Attack achieves state-of-the-art accuracy across several widely-used language models, and Gumbel Attack provides a scalable method for real-time generation of adversarial examples. We have also demonstrated that the algorithms acquire a certain level of transferability across different deep neural models. Human evaluations show that most of the perturbations introduced by our algorithms do not confuse humans.

References

Appendix

The word-based CNN model is composed of a $50$ -dimensional word embedding, a $1$ -D convolutional layer of 250 filters and kernel size 3, a max-pooling and a $250$ -dimensional dense layer as hidden layers. Both the convolutional and the dense layers are followed by ReLU as nonlinearity, and Dropout as regularization. The model is trained with rmsprop for five epochs. Each review is padded/cut to $400$ words. The model achieves accuracy of $90.1\%$ on the test data set.

Yahoo! Answers with LSTM

The network is composed of a $300$ -dimensional randomly-initialized word embedding, a bidirectional LSTM, each LSTM unit of dimension $256$ , and a dropout layer as hidden layers. The model is trained with rmsprop . The model obtains accuracy of $70.84\%$ on the test data set, close to the state-of-the-art accuracy of $71.2\%$ obtained by character-based CNN .

AG’s News with Char-CNN

The character-based CNN has the same structure as the one proposed in Zhang et al. , composed of six convolutional layers, three max pooling layers, and two dense layers. The alphabet dictionary used is of size $69$ . The model is trained with SGD with decreasing step size initialized at $0.01$ and momentum 0.9. (Details can be found in Zhang et al. .) The model reaches accuracy of $90.09\%$ on the test data set.

Gumbel Attack for three models

The input is initially fed into a common embedding layer and a convolutional layer with $100$ filters. Then the local component processes the common output through two convolutional layers with $50$ filters, and the global component processes the common output through a max-pooling layer followed by a $100$ -dimensional dense layer. Then we concatenate the global output to local outputs corresponding to each feature, and process them through one convolutional layer with $50$ filters, followed by a Dropout layer . Finally a convolutional network with kernel size $1$ is used to output. All previous convolutional layers are of kernel size 3, and ReLU is used as nonlinearity.