Discrete Adversarial Attacks and Submodular Optimization with Applications to Text Classification

Abstract

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.

arXiv commentIn SysML 2019

References in corpus (8)

• Explaining and Harnessing Adversarial Examples
• Generating Natural Adversarial Examples
• Deep Text Classification Can be Fooled
• Synthetic and Natural Noise Both Break Neural Machine Translation
• Adversarial Examples for Evaluating Reading Comprehension Systems
• HotFlip: White-Box Adversarial Examples for Text Classification
• Adversarial Texts with Gradient Methods
• DANCin SEQ2SEQ: Fooling Text Classifiers with Adversarial Text Example Generation

Cited by in corpus (4)

• Trust but Verify: An Information-Theoretic Explanation for the Adversarial Fragility of Machine Learning Systems, and a General Defense against Adversarial Attacks
• T3: Tree-Autoencoder Constrained Adversarial Text Generation for Targeted Attack
• Adversarial Attacks on Binary Image Recognition Systems
• Minimax Optimization: The Case of Convex-Submodular