mlsanityData to 7 Oct 2026

Efficient Combinatorial Optimization for Word-level Adversarial Textual Attack

arXiv 2109.02229 ↗First posted 6 Sep 2021cs.CL cs.NEcited by 17

Not on the map. Why?

Abstract (arXiv)

Over the past few years, various word-level textual attack approaches have been proposed to reveal the vulnerability of deep neural networks used in natural language processing. Typically, these approaches involve an important optimization step to determine which substitute to be used for each word in the original input. However, current research on this step is still rather limited, from the perspectives of both problem-understanding and problem-solving. In this paper, we address these issues by uncovering the theoretical properties of the problem and proposing an efficient local search algorithm (LS) to solve it. We establish the first provable approximation guarantee on solving the problem in general cases.Extensive experiments involving 5 NLP tasks, 8 datasets and 26 NLP models show that LS can largely reduce the number of queries usually by an order of magnitude to achieve high attack success rates. Further experiments show that the adversarial examples crafted by LS usually have higher quality, exhibit better transferability, and can bring more robustness improvement to victim models by adversarial training.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 29 of its 51 references that are in the map. First posted on arXiv 6 Sep 2021.

Builds on

29 of 51 references.

References · 29

  1. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  2. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  3. 2013Intriguing properties of neural networkscited by 5,114
  4. 2017Ensemble Adversarial Training: Attacks and Defensescited by 833
  5. 2019Universal Adversarial Triggers for Attacking and Analyzing NLPcited by 709
  6. 2019Is BERT Really Robust? A Strong Baseline for Natural Language Attack on Text Classification and Entailmentcited by 663
  7. 2017Adversarial Examples for Evaluating Reading Comprehension Systemscited by 568
  8. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 564
  9. 2020BERT-ATTACK: Adversarial Attack Against BERT Using BERTcited by 488
  10. 2018Generating Natural Language Adversarial Examplescited by 422
  11. 2018TextBugger: Generating Adversarial Text Against Real-world Applicationscited by 376
  12. 2018Black-box Generation of Adversarial Text Sequences to Evade Deep Learning Classifierscited by 341
17 more
  1. 2017Synthetic and Natural Noise Both Break Neural Machine Translationcited by 304
  2. 2018Adversarial Example Generation with Syntactically Controlled Paraphrase Networkscited by 282
  3. 2017Generating Natural Adversarial Examplescited by 182
  4. 2019Combating Adversarial Misspellings with Robust Word Recognitioncited by 162
  5. 2017Deep Text Classification Can be Fooledcited by 105
  6. 2016Crafting Adversarial Input Sequences for Recurrent Neural Networkscited by 102
  7. 2017Deceiving Google's Perspective API Built for Detecting Toxic Commentscited by 99
  8. 2019Text Processing Like Humans Do: Visually Attacking and Shielding NLP Systemscited by 99
  9. 2018Seq2Sick: Evaluating the Robustness of Sequence-to-Sequence Models with Adversarial Examplescited by 93
  10. 2018Interpretable Adversarial Perturbation in Input Embedding Space for Textcited by 67
  11. 2020It's Morphin' Time! Combating Linguistic Discrimination with Inflectional Perturbationscited by 64
  12. 2020Generating Natural Language Attacks in a Hard Label Black Box Settingcited by 50
  13. 2019Parsimonious Black-Box Adversarial Attacks via Efficient Combinatorial Optimizationcited by 49
  14. 2020Generating Fluent Adversarial Examples for Natural Languagescited by 49
  15. 2019Word-level Textual Adversarial Attacking as Combinatorial Optimizationcited by 37
  16. 2018Automatic Construction of Parallel Portfolios via Explicit Instance Groupingcited by 11
  17. 2019On Performance Estimation in Automatic Algorithm Configurationcited by 8

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 3; 2023: 4; 2024: 3; 2025: 4.

17 papers.

Sort:

By area:

  1. 2024Testing and Understanding Erroneous Planning in LLM Agents through Synthesized User Inputscited by 22
  2. 2025Safe Delta: Consistently Preserving Safety when Fine-Tuning LLMs on Diverse Datasetscited by 17
  3. 2022Saliency Attack: Towards Imperceptible Black-box Adversarial Attackcited by 12
  4. 2023Less is More: Understanding Word-level Textual Adversarial Attack via n-gram Frequency Descendcited by 9
  5. 2024A Modified Word Saliency-Based Adversarial Attack on Text Classification Modelscited by 9
  6. 2022Reliable Robustness Evaluation via Automatically Constructed Attack Ensemblescited by 6
  7. 2021Effective and Imperceptible Adversarial Textual Attack via Multi-objectivizationcited by 5
  8. 2023Adversarial Attacks and Defenses in Machine Learning-Powered Networks: A Contemporary Surveycited by 5
  9. 2022Disentangled Text Representation Learning with Information-Theoretic Perspective for Adversarial Robustnesscited by 4
  10. 2025Exploring Gradient-Guided Masked Language Model to Detect Textual Adversarial Attackscited by 4
  11. 2023Submodular Maximization under the Intersection of Matroid and Knapsack Constraintscited by 2
  12. 2025SemDiff: Generating Natural Unrestricted Adversarial Examples via Semantic Attributes Optimization in Diffusion Modelscited by 2
5 more
  1. 2021Training Quantized Deep Neural Networks via Cooperative Coevolutioncited by 1
  2. 2025Hardware-Aware DNN Compression for Homogeneous Edge Devicescited by 1
  3. 2021AED: An black-box NLP classifier model attackercited by 0
  4. 2023Memory efficient location recommendation through proximity-aware representationcited by 0
  5. 2024Semantic Stealth: Adversarial Text Attacks on NLP Using Several Methodscited by 0