Adversarial examples are carefully constructed modifications to an input that
completely change the output of a classifier but are imperceptible to humans.
Despite these successful attacks for continuous data (such as image and audio
samples), generating adversarial examples for discrete structures such as text
has proven significantly more challenging. In this paper we formulate the
attacks with discrete input on a set function as an optimization task. We prove
that this set function is submodular for some popular neural network text
classifiers under simplifying assumption. This finding guarantees a $1-1/e$
approximation factor for attacks that use the greedy algorithm. Meanwhile, we
show how to use the gradient of the attacked classifier to guide the greedy
search. Empirical studies with our proposed optimization scheme show
significantly improved attack ability and efficiency, on three different text
classification tasks over various baselines. We also use a joint sentence and
word paraphrasing technique to maintain the original semantics and syntax of
the text. This is validated by a human subject evaluation in subjective metrics
on the quality and semantic coherence of our generated adversarial text.

本文提出对于离散输入的攻击作为优化任务的形式化表达，并证明了针对一些流行的神经网络文本分类器，该函数在简化假设下是次模的。同时，本文提出了使用攻击分类器的梯度来引导贪心搜索的方法。在三种不同的文本分类任务和多个基线上进行的实证研究表明，我们提出的优化方案在攻击能力和效率方面均显著提高。我们还使用联合句子和词汇改写技术来维护文本的原始语义和语法。在主观度量中，我们还使用人类主体评估来验证了生成的对抗文本的质量和语义连贯性。