# Efficient Combinatorial Optimization for Word-level Adversarial Textual Attack

arXiv: https://arxiv.org/abs/2109.02229 · HTML: https://mlsanity.com/paper/2109.02229/

## Key facts

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

## Builds on (most cited first, 29 of 29)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Ensemble Adversarial Training: Attacks and Defenses](https://mlsanity.com/paper/1705.07204/) (2017)
- [Universal Adversarial Triggers for Attacking and Analyzing NLP](https://mlsanity.com/paper/1908.07125/) (2019)
- [Is BERT Really Robust? A Strong Baseline for Natural Language Attack on Text Classification and Entailment](https://mlsanity.com/paper/1907.11932/) (2019)
- [Adversarial Examples for Evaluating Reading Comprehension Systems](https://mlsanity.com/paper/1707.07328/) (2017)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [BERT-ATTACK: Adversarial Attack Against BERT Using BERT](https://mlsanity.com/paper/2004.09984/) (2020)
- [Generating Natural Language Adversarial Examples](https://mlsanity.com/paper/1804.07998/) (2018)
- [TextBugger: Generating Adversarial Text Against Real-world Applications](https://mlsanity.com/paper/1812.05271/) (2018)
- [Black-box Generation of Adversarial Text Sequences to Evade Deep Learning Classifiers](https://mlsanity.com/paper/1801.04354/) (2018)
- [Synthetic and Natural Noise Both Break Neural Machine Translation](https://mlsanity.com/paper/1711.02173/) (2017)
- [Adversarial Example Generation with Syntactically Controlled Paraphrase Networks](https://mlsanity.com/paper/1804.06059/) (2018)
- [Generating Natural Adversarial Examples](https://mlsanity.com/paper/1710.11342/) (2017)
- [Combating Adversarial Misspellings with Robust Word Recognition](https://mlsanity.com/paper/1905.11268/) (2019)
- [Deep Text Classification Can be Fooled](https://mlsanity.com/paper/1704.08006/) (2017)
- [Crafting Adversarial Input Sequences for Recurrent Neural Networks](https://mlsanity.com/paper/1604.08275/) (2016)
- [Deceiving Google's Perspective API Built for Detecting Toxic Comments](https://mlsanity.com/paper/1702.08138/) (2017)
- [Text Processing Like Humans Do: Visually Attacking and Shielding NLP Systems](https://mlsanity.com/paper/1903.11508/) (2019)
- [Seq2Sick: Evaluating the Robustness of Sequence-to-Sequence Models with Adversarial Examples](https://mlsanity.com/paper/1803.01128/) (2018)
- [Interpretable Adversarial Perturbation in Input Embedding Space for Text](https://mlsanity.com/paper/1805.02917/) (2018)
- [It's Morphin' Time! Combating Linguistic Discrimination with Inflectional Perturbations](https://mlsanity.com/paper/2005.04364/) (2020)
- [Generating Natural Language Attacks in a Hard Label Black Box Setting](https://mlsanity.com/paper/2012.14956/) (2020)
- [Parsimonious Black-Box Adversarial Attacks via Efficient Combinatorial Optimization](https://mlsanity.com/paper/1905.06635/) (2019)
- [Generating Fluent Adversarial Examples for Natural Languages](https://mlsanity.com/paper/2007.06174/) (2020)
- [Word-level Textual Adversarial Attacking as Combinatorial Optimization](https://mlsanity.com/paper/1910.12196/) (2019)
- [Automatic Construction of Parallel Portfolios via Explicit Instance Grouping](https://mlsanity.com/paper/1804.06088/) (2018)
- [On Performance Estimation in Automatic Algorithm Configuration](https://mlsanity.com/paper/1911.08200/) (2019)

## Built on by (most cited first, 17 of 17)

- [Testing and Understanding Erroneous Planning in LLM Agents through Synthesized User Inputs](https://mlsanity.com/paper/2404.17833/) (2024)
- [Safe Delta: Consistently Preserving Safety when Fine-Tuning LLMs on Diverse Datasets](https://mlsanity.com/paper/2505.12038/) (2025)
- [Saliency Attack: Towards Imperceptible Black-box Adversarial Attack](https://mlsanity.com/paper/2206.01898/) (2022)
- [Less is More: Understanding Word-level Textual Adversarial Attack via n-gram Frequency Descend](https://mlsanity.com/paper/2302.02568/) (2023)
- [A Modified Word Saliency-Based Adversarial Attack on Text Classification Models](https://mlsanity.com/paper/2403.11297/) (2024)
- [Reliable Robustness Evaluation via Automatically Constructed Attack Ensembles](https://mlsanity.com/paper/2211.12713/) (2022)
- [Effective and Imperceptible Adversarial Textual Attack via Multi-objectivization](https://mlsanity.com/paper/2111.01528/) (2021)
- [Adversarial Attacks and Defenses in Machine Learning-Powered Networks: A Contemporary Survey](https://mlsanity.com/paper/2303.06302/) (2023)
- [Disentangled Text Representation Learning with Information-Theoretic Perspective for Adversarial Robustness](https://mlsanity.com/paper/2210.14957/) (2022)
- [Exploring Gradient-Guided Masked Language Model to Detect Textual Adversarial Attacks](https://mlsanity.com/paper/2504.08798/) (2025)
- [SemDiff: Generating Natural Unrestricted Adversarial Examples via Semantic Attributes Optimization in Diffusion Models](https://mlsanity.com/paper/2504.11923/) (2025)
- [Submodular Maximization under the Intersection of Matroid and Knapsack Constraints](https://mlsanity.com/paper/2307.09487/) (2023)
- [Training Quantized Deep Neural Networks via Cooperative Coevolution](https://mlsanity.com/paper/2112.14834/) (2021)
- [Hardware-Aware DNN Compression for Homogeneous Edge Devices](https://mlsanity.com/paper/2501.15240/) (2025)
- [AED: An black-box NLP classifier model attacker](https://mlsanity.com/paper/2112.11660/) (2021)
- [Memory efficient location recommendation through proximity-aware representation](https://mlsanity.com/paper/2310.06484/) (2023)
- [Semantic Stealth: Adversarial Text Attacks on NLP Using Several Methods](https://mlsanity.com/paper/2404.05159/) (2024)

## 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.