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

1 Introduction

• Adversarial robustness is an important criterion for machine learning in security-sensitive applications, including spam, fraud, criminal justice, malware, and financial markets.Prior attack methods were developed to operationalize robustness and drive development of more robust learning systems.Source: §1 · p. 1
• Discrete inputs such as text have categorical features, so gradient-based attacks designed for continuous input spaces are not directly applicable.Prior work adapted gradients or used other strategies for discrete or text inputs.Source: §1 · p. 1
• The two-stage framework identifies features to perturb, then replaces them with values selected from a fixed dictionary; Greedy prioritizes success, while Gumbel requires fewer model evaluations.The paper notes Table 1 compares methods, including efficiency and black-box applicability.Source: §1 · p. 2, Table 1 · p. 2
• Greedy Attack achieves state-of-the-art attack rates across model types, while Gumbel Attack offers low model-evaluation complexity and character-based models are particularly vulnerable.The framework and its methods are intended for adversarial attacks on discrete data.Source: §1 · p. 2

2 Framework

• The attack seeks to change the model’s predicted class by perturbing at most k features of an input.Success is defined by a change in the model’s argmax prediction between the original and perturbed inputs.Source: §2 · p. 2
• The first stage searches for up to k positions to mask with the reference value w0, while the second searches for replacements from attacker-selected sub-dictionary W′.The candidate sets S1 and S2 encode these respective searches.Source: §2 · p. 3
• Because the two stage objectives are generally computationally intractable, the framework optimizes conditional distributions over feature selections and replacement choices.The first-stage distribution over masks is constrained through k independent, identically distributed one-hot draws.Source: §2 · p. 3
• The first-stage distribution ranks input features, and the framework selects the top k features for perturbation.The selected positions are determined by the ranking induced by P(Gs | x).Source: §2 · p. 3
• In the second stage, conditional categorical distributions rank replacement values for each selected feature, which receives its top-ranked value from W′.The replacement variables are one-hot and conditionally independent given the input.Source: §2 · p. 3

3.1 Greedy Attack

• Greedy Attack approximates feature masking and replacement objectives with single-feature model evaluations, repeating the greedy choice across the selected features.For replacement, it estimates attack success after substituting a feature with a dictionary value.Source: §3.1 · p. 4

3.2 Gumbel Attack

• Direct enumeration requires d^k and |W′|^k terms; the Gumbel-trick approximation achieved better performance, lower variance, and higher model-evaluation efficiency in experiments.Training requires gradients of the original model, but setting λ1 to zero enables black-box attacks.Source: §3.2 · p. 5
• Gumbel Attack replaces categorical sampling with differentiable Concrete random variables and trains parameterized distributions for feature identification and replacement.Its perturbed inputs use relaxed feature masks and weighted sums of candidate replacement embeddings.Source: §3.2 · p. 5
• Across three datasets, Gumbel Attack uses a shared embedding feeding local and global processing paths, whose outputs are merged through two convolutional layers.The local path uses two convolutional layers; the global path uses convolution, pooling, and dense layers.Source: Figure 2 · p. 6

4 Experiments

• The evaluation attacks text classifiers at their respective feature levels, using words or characters as perturbation units, and compares the proposed methods with four alternatives.The tested systems include CNN and LSTM models; the alternatives are Delete-1 Score, DeepWordBug, Projected FGSM, Saliency, and Saliency-FGSM.Source: §4 · p. 6

4.1 Word-based models

• Across both word-based models, Greedy Attack performs best; Gumbel Attack does well on IMDB but has lower success than Saliency-Projected FGSM on Yahoo! Answers.The comparisons use a word-CNN on IMDB and an LSTM on Yahoo! Answers.Source: §4.1 · pp. 6–7

4.2 Character-based models

• With five perturbed characters, a character-based CNN performs no better than random selection; Greedy Attack ranks first, followed by Delete-1 Score and Gumbel Attack.The character-based CNN is evaluated on AG’s News; the model has 90.09% test accuracy before attack.Source: §4.2 · pp. 7–8

4.3 Efficiency, transferability and human evaluation

• Gumbel Attack is the most efficient method even after training time is included, and its training time makes up a smaller share of total time as attack scale increases.Clock-time measurements were made on a single NVidia Tesla k80 GPU.Source: §4.3 · p. 8, Figure 4 · p. 9
• Gumbel Attack achieves comparable transfer success on both data sets, even when the model structure is completely altered; Greedy Attack is comparable on Yahoo! Answers but degrades on IMDB.Perturbed samples generated on each original model were evaluated on newly trained models.Source: §4.3 · pp. 8–9, Figure 5 · p. 9
• On IMDB adversarial samples, human accuracy drops 10.5% for Greedy and 7.5% for Gumbel, versus neural-model drops of 75% and 25% when two words are perturbed.Human judgments were collected from three workers on 200 samples successfully attacked by both methods per data set.Source: §4.3 · p. 9
• Yahoo! Answers was excluded from human evaluation because its varied classes and multi-category answers produce large variance.Source: §4.3 · p. 10

• Greedy Attack achieves state-of-the-art accuracy across several widely used language models, while Gumbel Attack provides scalable real-time generation.Source: §5 · p. 10
• The algorithms show a degree of transferability across different deep neural models.Source: §5 · p. 10
• Human evaluations find that most perturbations introduced by the algorithms do not confuse people.Source: §5 · p. 10

6.1 Model structure

• The IMDB Word-CNN uses 50-dimensional word embeddings, 250 convolutional filters, and a 250-dimensional dense layer; the Yahoo! Answers model uses a bidirectional LSTM with 256-dimensional units.The AG’s News Char-CNN follows Zhang et al. [30] and has six convolutional layers, three max-pooling layers, and two dense layers; the appendix also describes the Gumbel Attack model’s local and global components.Source: §6.1 · p. 12

6.2 Visualization on IMDB with Word-CNN

• IMDB examples include reviews paired with their sentiment labels, while the IMDB attack tables distinguish successful Greedy and Gumbel examples.The sample reviews include both positive and negative labels.Source: §6.2 · pp. 14–15, Table 6 · p. 16, Table 7 · p. 18

6.2 Visualization on IMDB with Word-CNN; 6.3 Visualization on AG’s News with Char-CNN; 6.4 Visualization on Yahoo! Answers with LSTM

• The IMDB, AG’s News, and Yahoo! Answers visualizations present successful examples from Greedy and Gumbel attacks.For IMDB and Yahoo! Answers, captions identify replaced words in red and original words in blue.Source: Table 6 · p. 16, Table 7 · p. 18, Table 8 · p. 20

6.4 Visualization on Yahoo! Answers with LSTM

• The Yahoo! Answers visualization includes question-and-answer text, and its Gumbel Attack table presents successful examples with replacing and original words marked.The examples span multiple question categories.Source: §6.4 · p. 25, Table 11 · p. 26