  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.
