Efficient Combinatorial Optimization for Word-Level Adversarial Textual Attack
- 26 November 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Audio, Speech, and Language Processing
- Vol. 30 (23299290) , 98-111
Abstract
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.Keywords
All Related Versions
Funding Information
- Guangdong Provincial Key Laboratory (2020B121201001)
- Guangdong Introducing Innovative and Entrepreneurial Teams (2017ZT07X386)
- Science and Technology Commission of Shanghai Municipality (19511120600)
- National Leading Youth Talent Support Program of China
- MOE University Scientific-Technological Innovation Plan Program
This publication has 32 references indexed in Scilit:
- Deep Text Classification Can be Fooled2018
- Interpretable Adversarial Perturbation in Input Embedding Space for Text2018
- Adversarial Example Generation with Syntactically Controlled Paraphrase Networks2018
- E-Mail Spam Filtering: A Review of Techniques and Trends2017
- Deep Android Malware Detection2017
- Adversarial Examples for Evaluating Reading Comprehension Systems2017
- Crafting adversarial input sequences for recurrent neural networks2016
- QoS-aware long-term based service composition in cloud computing2015
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate AlgorithmsManagement Science, 1977