Discrete adversarial attacks and submodular optimization and their application in text classification
Discrete Adversarial Attacks and Submodular Optimization with Applications to Text Classification
The authors formalize discrete adversarial attacks on text as set function optimization, prove that this function is submodular on two types of text classifiers, and propose gradient-guided greedy and joint sentence-word paraphrasing attacks.
Targeted attack: maximize the classifier's output probability for a specified target label. The attacker can compute the gradient of the attacked classifier (using gradient-guided search), with at most k−1 substitutions per feature and at most m features changed; the victim systems are text classifiers (WCNN, LSTM), and the paper does not label the threat model with black-box/white-box terminology.
- Generating adversarial examples for discrete inputs such as text is harder than for continuous data: gradient methods do not directly apply, the space of substitution combinations grows exponentially, and it is difficult to preserve the semantics and syntax of the original source.
- Formalizes discrete attacks as set function maximization, proves it is submodular on two types of text classifiers (simplified W-CNN, one-dimensional hidden-unit RNN), giving greedy a 1−1/e approximation guarantee; and proposes gradient-guided greedy word rewriting and a sentence-level plus word-level joint rewriting procedure.
- Attacking WCNN and LSTM on the three tasks News, Trec07p, and Yelp: at λw=20%, adversarial accuracy is as low as 16.5% (LSTM, News, Table 2); with word-level attack only, Algorithm 3 has a higher success rate than the two baselines and lower time cost (Table 3); 5-person human evaluation (n=60 each) considers the generated text close in quality to the original source (Table 4).
- The submodularity proof relies on simplifying assumptions (e.g., W-CNN without dropout/softmax, one-dimensional hidden-unit RNN); only two models, WCNN and LSTM, and three English classification tasks are tested; human evaluation has only 5 people, 60 items each; the paper has no dedicated limitations section.
- Evaluated models
- WCNNLSTM
- Benchmarks
- Fake/Real NewsTrec07pYelp reviews
- Metrics
- adversarial test accuracyattack success rate (SR)timehuman evaluation (Task I accuracy, Task II 1–5 分)
The researchers propose a discrete adversarial attack method for text classifiers, formalizing the attack on discrete inputs as a set function optimization task. The paper proves under simplifying assumptions that this set function is submodular for some common neural network text classifiers, thereby guaranteeing that the attack using a greedy algorithm has a 1-1/e approximation factor, and uses the gradients of the attacked classifier to guide the greedy search. Experiments on three text classification tasks show that this optimization scheme significantly improves attack capability and efficiency compared with multiple baselines; the authors also employ joint sentence and word rewriting techniques to preserve the original text's semantics and syntax, and verify through human subjective evaluation the quality and semantic coherence of the generated adversarial text.
Paper analysis
What problem does this paper attempt to solve?
Generating adversarial examples for discrete inputs such as text: the combinatorial space is exponential, gradient methods do not directly apply, and it is difficult to preserve the semantics and syntax of the original source.
Core problem: how to quickly and effectively generate adversarial examples for discrete input structures such as text, while preserving the semantics and syntax of the original source.
- Problem setting: adversarial examples are small modifications to the input that change the classifier output but are not easily noticed by humans. The authors note that attacks on continuous data (images, audio) have succeeded, but generating adversarial examples on discrete structures such as text and code is harder.
- Shortcomings of existing methods (according to the paper): gradient methods do not directly apply to discrete structures, and their variants (when the model is differentiable with respect to the embedding layer) are efficient but have poor success rates; the combinatorial space of feature-by-feature substitutions grows exponentially with input length, making optimal solutions infeasible; existing character-level/word-level greedy heuristic methods are slow, and there is a lack of theoretical understanding of when they are effective.
- Difficulty of preserving functionality: the authors note that existing methods either change too many features or change the original meaning; for example, [19] changes as many as 50% of words and achieves only a 30% success rate, [18] replaces words with completely different words, and [21] inserts irrelevant sentences; these changes are easy for humans to notice.
- Core observation of the paper: the authors formulate discrete attacks as an optimization problem over a set function and prove that on two commonly used text classifiers this set function is submodular, so that the greedy algorithm has a 1 − 1/e approximation guarantee.
- What the paper proposes: a general framework for discrete attacks, a gradient-guided greedy word-level paraphrasing algorithm (Gradient-Guided Greedy Word Paraphrasing), a joint sentence-level and word-level paraphrasing technique, and experimental validation on three text classification tasks.
- Threat model:
- Goal: targeted attack, maximizing the classifier's output probability for a specified target label y (Problem 1).
- Knowledge: the attacker can compute the gradient of the attacked classifier with respect to word embeddings (Algorithm 3 uses gradient-guided search); the paper does not label this with white-box/black-box terminology.
- Capability: at most k−1 candidate substitutions per feature, at most m features changed (constraint klk0 ≤ m); in experiments the word paraphrase ratio is λw=20%.
- Victim system: text classifiers (WCNN, LSTM), with tasks of fake news detection, spam filtering, and sentiment analysis.
What related research exists?
Related work falls into three categories: attacks on continuous data, discrete/text attacks, and semantics-preserving paraphrasing; the baselines are the greedy of [19] and the gradient method of [18].
Adversarial attacks and defenses on continuous data (images/audio)
- Szegedy et al. [4] found that deep neural network image classifiers can be fooled by tiny pixel perturbations; Goodfellow et al. [5], DeepFool [6], Carlini & Wagner [8], etc. continue this direction.
- On defenses, the paper mentions adversarial training [5, 13] as the current state-of-the-art defense, but building robust classifiers remains difficult (Athalye et al. [14]).
Attacks on discrete/text inputs
- Word- or character-level substitution attacks: selecting replacement words using continuous word embeddings or designed scoring functions, already used to attack NLP classifiers [15, 16, 22, 23, 24, 25, 18, 19, 26, 27, 20] and sequence-to-sequence models [17, 28, 29, 30].
- Ribeiro et al. [31] use semantically equivalent rules to debug NLP models; the paper points out that such work considers attacks only within a single input structure (word or character), does not attack jointly, and does not consider sentence-level effects.
- Jia and Liang [21] attack reading comprehension systems by inserting additional sentences; the paper considers this beyond its scope because this approach changes the meaning of the original source.
- Other work focuses on robustness to out-of-vocabulary terms [32] and embedding-space representations [33], which the paper states are not regarded as adversarial examples.
Baseline methods and benchmarks
- Baselines: the objective-guided greedy method of [19] (Kuleshov et al., 2018), greedily substituting word by word according to function value; the gradient method of [18] (Gong et al., 2018), selecting synonym substitutions according to a first-order Taylor expansion.
- Benchmarks/datasets: Fake/Real News (6336 articles, 5336 train/1000 test), Trec07p spam corpus (75,419 emails, 10% as test), Yelp reviews (560,000 train/38,000 test), the same three tasks as [19].
Positioning of this paper: the authors state that unlike work such as [31] that considers only a single input structure, this paper does joint sentence-level and word-level rewriting; compared with the greedy of [19], this paper uses gradient magnitude to guide the search and can substitute multiple words per round; theoretically it also unifies the two types of heuristics, gradient methods (solving a relaxed problem) and greedy methods (with an approximation guarantee under the submodular assumption).
How does the paper address this problem?
Formulate the attack as set function maximization, prove that submodularity guarantees the greedy approximation ratio, then implement it with gradient-guided greedy plus joint sentence-word paraphrasing.
Overall approach: formalize discrete adversarial attacks as an optimization problem over a set function, prove that this function is submodular on two types of text classifiers, so that the greedy algorithm has a 1 − 1/e approximation guarantee; on this basis, design a complete attack pipeline of gradient-guided greedy word paraphrasing and joint sentence-level + word-level paraphrasing.
Problem setting and formalization
- Input x = [x1, …, xn], each feature has at most k−1 substitutions; the transformation T is marked by an index vector l ∈ {0,…,k−1}ⁿ, with the constraint klk0 ≤ m (at most m features changed).
- Targeted attack: l∗ = argmax|l|0 ≤ m Cy(V(Tl(x))), i.e., maximize the classifier's output for the target label y under the substitution-count constraint; equivalently, find the set S∗ = argmax|S| ≤ m f(S), where f(S) is the maximum target-label output when only features in S are allowed to change.
- Proposition 1: this problem is NP-hard for general classifiers, and even for some convex classifiers it can be reduced from subset sum.
Theory: two tractable paths
- Gradient method = relaxed problem: assuming Cy is smooth, use a first-order Taylor expansion to relax the problem to maximizing V(Tl(x))ᵀ∇Cy(v) (Problem 2), similar to Frank-Wolfe; Proposition 2 proves that this relaxation can be solved in polynomial time for both bag-of-words and word2vec embedding (the set function degenerates to a modular function). The authors consider [18] to belong to this category, but ReLU breaks smoothness and first-order expansion only looks locally, limiting effectiveness.
- Greedy method = submodularity assumption: if f is monotone non-decreasing and submodular, then greedy under a cardinality constraint has a 1 − 1/e approximation (Claim 1, citing Nemhauser et al. [38]). The authors state that both the greedy of [19] and the method in this paper implicitly assume submodularity.
Two proofs of submodularity
- Simplified W-CNN (Theorem 1): when there is no dropout or softmax layer, windows do not overlap (s ≥ h), all output-layer weights w0 are non-negative, and only substitutions that increase the output are considered, f is submodular; the proof idea is that max pooling applied to a modular function is submodular, and the sum of submodular functions is still submodular.
- One-dimensional hidden-unit RNN (Theorem 2): with T time steps, a single node per hidden layer, positive w and output weights y, and a non-decreasing and concave activation function, f is submodular; the authors call this result surprising, because word vectors affect the output at different time steps and are not separable.
Attack pipeline (Algorithm 1–3)
- Candidate set construction: at the word level, use the 300-dimensional paragram embedding of Paragram-SL999 to generate neighboring paraphrases; at the sentence level, use the Para-nmt-50m pretrained model of Wieting and Gimpel to generate sentence paraphrases; at most k candidates are kept per word/sentence.
- Semantic and syntactic constraints: semantically, Word Mover Distance (WMD) limits the distance between candidate and original source (thresholds δs, δw); syntactically, a language model P requires |ln P(x) − ln P(x′)| ≤ δ.
- Algorithm 2 (sentence-level greedy): try candidate paraphrases sentence by sentence, greedily select by classifier output value, until Cy(V(x)) ≥ τ or the number of paraphrased sentences reaches λs·l.
- Algorithm 3 (gradient-guided greedy word paraphrasing): in each round, select the N=5 most important words by the L2 norm of the word embedding gradient, enumerate all combinations in the Cartesian product of the candidate sets of these 5 words, and take the combination that maximizes the classifier output; until Cy(x) ≥ τ or the number of paraphrased words reaches λw·n. The authors state that replacing multiple words in one round can account for the joint effect of multiple words, and that the design is inspired by the Gauss-Southwell rule [39] in coordinate descent.
- Overall order: first do sentence-level paraphrasing (Algorithm 2); if the termination threshold τ is already reached, return directly; otherwise, then do word-level paraphrasing (Algorithm 3). The authors explain that gradients are used only at the word level because sentence paraphrasing changes the word count, and gradients computed before paraphrasing may not correspond to positions in the new sentence.
Key parameters (Section 6.2)
- Termination threshold τ = 0.7; number of candidate neighbors k = 15; semantic similarity δw = δs = 0.75 (spacy's WMD similarity, [0,1] range).
- Syntactic constraint δ = 2 (News, Yelp); for Trec07p, δ = ∞ because the emails contain many corrupted words and the language model fails.
- Paraphrase ratios: λw = 20% (all datasets); λs = 20% (Yelp, News), λs = 60% (Trec07p).
What experiments did the paper conduct?
Attacking WCNN and LSTM on three tasks: adversarial accuracy as low as 16.5%, the optimization algorithm is faster and better, and human evaluation quality is close to the original source.
Experimental setup
- Models tested: WCNN (temporal convolution with kernel size 3 + max-pooling + fully connected) and a one-layer LSTM with 512 hidden units, 2 in total.
- Datasets: Fake/Real News (5336 train/1000 test), Trec07p (67.9k train/7.5k test), Yelp reviews (560k train/38k test), see Table 6.
- Baselines: the objective-guided greedy of [19] (including both the value reported in the paper and the value reproduced by the authors with the same word candidate set, both allowing λw=50%) and the gradient method of [18].
- Metrics: original/adversarial test accuracy (Table 2), attack success rate SR and time cost (Table 3, units not stated in the paper), human evaluation (Table 4).
- Training setup: vocabulary takes the top 100,000 most frequent words, embeddings use pretrained word2vec (300 dimensions), 10% of training data as validation set, mini-batch 16.
- Human evaluation: 5 evaluators, each sees n = 60 texts (half original, half generated), Task I classification accuracy takes majority vote, Task II averages 1–5 scores for "how much it looks human-written".
Main results
Table 2: original and adversarial test accuracy on the three datasets (this paper's method λw=20%; both [19] columns λw=50%, * is the authors' reproduction with the same word candidate set).
Swipe horizontally to read the table
Dataset Model Origin ADV (ours) ADV [19] ADV [19]* News WCNN 93.1% 35.4% 71.0% 70.5% News LSTM 93.3% 16.5% 37.0% 22.8% Trec07p WCNN 99.1% 48.6% 64.5% 63.5% Trec07p LSTM 99.7% 31.1% 39.8% 37.6% Yelp WCNN 93.6% 23.1% 39.0% 41.2% Yelp LSTM 96.4% 30.0% 24.0% 29.2% - The authors state that under both comparison settings, this paper's method flips more predicted classes with fewer word rewrites (20% vs 50%), and on this basis argue that joint sentence-word rewriting is more effective than word substitution alone.
- Exception: when attacking LSTM on Yelp, this paper's adversarial accuracy of 30.0% is higher than the value 24.0% reported in [19] (i.e., the attack is weaker), but lower than the reproduced value 29.2%.
- The authors state that sentence-level attacks almost fully preserve the original meaning, and are therefore less likely to be noticed by humans; Appendix C gives concrete examples compared with [19, 18].
Joint effect of rewrite proportions (Figure 4)
- What was measured: when attacking LSTM, the success rate for sentence-level rewrite proportion λs from 0% to 60% and word-level proportion λw of 0%/10%/20%/30%.
- Results: the authors report that on the sentiment analysis task, rewriting only 10% of words successfully attacks only about 5% of reviews; after first doing 60% sentence-level rewriting, the success rate rises to close to 60%.
- Authors' interpretation: sentence-level rewriting has the greatest effect when only a small number of word rewrites is allowed.
Comparison of word-level optimization algorithms (Table 3)
- What was measured: on WCNN with word-level attack only (no sentence-level rewriting), comparing Algorithm 3, the objective-guided greedy of [19], and the gradient method of [18] in SR and time cost at λw=5% and 20%.
- Results (λw=20%): SR on News is 45.4% (this paper) vs 28.4% ([19]) and 12.8% ([18]); on Trec07p 45.3% vs 24.9% and 3.4%; on Yelp 55.9% vs 45.0% and 9.1%. On time cost the authors state this paper's method needs only 1/5 to 1/3 of [19] (e.g., News λw=20%: 0.31 vs 1.46).
- Authors' interpretation: this paper's method is the most effective of the three mechanisms; the gradient method of [18] performs poorly when few substitutions are allowed. The authors state this paper's method is more suitable for WCNN, partly because 5% dropout is used at inference, and [19] changing only one word per round makes it hard to distinguish from dropout noise, whereas this paper changes 5 words per round.
Human evaluation (Table 4)
- What was measured: 5 evaluators classify original and generated texts (Task I) and score "how much it looks human-written" on 1–5 (Task II), n = 60 items each.
- Results: Task I classification accuracy original/adversarial is News 70.0%/50.0%, Trec07p 80.0%/80.0%, Yelp 100.0%/100.0%; Task II is News 3.06±0.67/3.13±0.50, Trec07p 3.23±0.31/3.10±0.40, Yelp 1.93±0.55/2.10±1.05.
- Authors' interpretation: generated text quality is close to the original, and even slightly higher on Yelp, but the authors note this finding is not necessarily statistically significant.
Adversarial training (Table 5)
- What was measured: randomly take 20% of training data, generate adversarial examples with Algorithm 1, and merge them with correct labels into the training set for retraining.
- Results: adversarial accuracy generally rises, e.g., LSTM+News from 16.5% to 32.7%, LSTM+Yelp from 30.0% to 46.7%, WCNN+Yelp from 23.1% to 44.4%; clean test accuracy also mostly rises slightly (e.g., LSTM+News 93.3%→94.5%).
- Authors' interpretation: in almost all cases, adversarial training improves model generalization and reduces the attack success rate.
Other ablations and analysis
- Figure 1 and Appendix C give 6 concrete generation examples (three datasets × two models), with sentence-level rewrites marked in red and word-level rewrites in blue, compared with the outputs of [19] and [18].
- In the appendix examples, the gradient method of [18] repeatedly fails to flip predictions (e.g., in C.1 ADV is still 99.5% Real), consistent with its low SR in Table 3.
What are some points that can be further explored?
The paper has no limitations section; the theory relies on simplifying assumptions, the experiments cover only two models and three English tasks, and the human evaluation is small-scale.
Limitations and future directions noted by the authors
- The paper does not specifically discuss limitations (there is no Limitations/Discussion section). The following are applicability conditions and reservations the authors themselves state in the main text:
- The submodularity proof relies on simplifying assumptions: W-CNN must have no dropout/softmax, non-overlapping windows, non-negative w0, and only substitutions that increase the output are considered (Theorem 1, Section 4.2.1); RNN must have one-dimensional hidden units, positive w and y, and a non-decreasing and concave activation (Theorem 2, Section 4.2.2).
- The authors call the smoothness assumption of gradient methods "unnatural": ReLU breaks smoothness, first-order expansion only looks locally, and synonym embeddings are not necessarily close (Section 4.1).
- Gradient guidance is used only at the word level, because sentence paraphrasing changes the word count and gradients computed before paraphrasing may not correspond to positions in the new sentence, so sentence-level gradient information is "not very reliable" (Section 5.2).
- In human evaluation, generated text on Yelp scored slightly higher, but the authors state that this finding is not necessarily statistically significant (Table 4 caption).
- The authors state that the framework can be generalized to discrete attacks such as malware detection, spam filtering, and image segmentation (Section 1), but experiments are conducted only on text classification.
Scope of experiments
- The models tested are WCNN and LSTM, 2 in total (Section 6.1); the theoretical analysis covers a simplified W-CNN and a one-dimensional hidden-unit RNN.
- The datasets are three English text classification tasks, News, Trec07p, and Yelp (Table 6), all binary classification.
- Attack settings: word paraphrase ratio λw ≤ 20% (main results), sentence paraphrase ratio λs is 20% (News, Yelp) or 60% (Trec07p); Figure 4 sweeps λs 0–60% and λw 0–30%.
- The baselines are the objective-guided greedy of [19] and the gradient method of [18]; the optimization algorithm comparison (Table 3) is done only on WCNN.
- Human evaluation uses 5 evaluators, each with n = 60 items (Table 4); the paper does not report the number of queries for the attack, the total time to generate a single sample (the unit of time in Table 3 is not specified), or inter-evaluator agreement.
Summarize the main content of the paper
A submodular optimization framework for discrete attacks: theoretical guarantee of greedy approximation ratio, gradient guidance plus joint sentence-word rewriting, validated as effective on three tasks.
A paper on an optimization framework for discrete adversarial attacks, targeting text classification scenarios.
- Problem: generating adversarial examples on discrete inputs such as text is harder than on continuous data: gradient methods do not directly apply, the space of substitution combinations grows exponentially, and it is difficult to preserve the semantics and syntax of the original source.
- Method: formalizes the attack as maximizing a set function f(S) under a cardinality constraint; proves the problem is NP-hard in general, but that f is submodular on a simplified W-CNN (no dropout/softmax, non-overlapping windows) and a one-dimensional hidden-unit RNN, so the greedy algorithm therefore has a 1 − 1/e approximation guarantee. The attack is implemented as sentence-level greedy rewriting (Algorithm 2) plus gradient-guided greedy word rewriting (Algorithm 3, selecting 5 words per round by gradient norm to enumerate combinations), with candidates generated from a paraphrase corpus and filtered by WMD and a language model.
- Main results: attacking WCNN and LSTM on News, Trec07p, Yelp, at λw=20% adversarial accuracy is as low as 16.5% (LSTM, News, Table 2), outperforming [19] which allows λw=50% in most settings; the exception is Yelp+LSTM where 30.0% is higher than the 24.0% reported in [19].
- Optimization comparison: with word-level attack only, Algorithm 3 achieves SR of 45.4%/45.3%/55.9% on WCNN (News/Trec07p/Yelp, λw=20%), higher than [19] and [18], with time cost 1/5 to 1/3 of [19] (Table 3).
- Quality and defense: 5 evaluators (n=60 each) consider the generated text close in quality to the original source (Table 4); after adversarial training with adversarial examples generated from 20% of training data, adversarial accuracy generally rises (e.g., LSTM+News 16.5%→32.7%, Table 5).
- Authors' conclusions: the authors state that gradient-guided greedy inherits the efficiency of gradient methods and the attack capability of greedy methods, and that joint sentence-word rewriting can generate an attack space while preserving semantics and syntax; theoretically, the submodular assumption unifies the existing two types of heuristics, gradient and greedy.