PaperlayerView exact revision on arXiv

Source-linked AI summary

Generating Natural Language Attacks in a Hard Label Black Box Setting

Rishabh Maheshwary, Saket Maheshwary, Vikram Pudi

arXiv:2012.14956v2cs.CL

TL;DR

NLP adversarial attacks are challenging because discrete word changes can alter meaning, and hard-label black-box attacks observe only the target’s predicted label. This paper uses population-based optimization to generate semantically similar adversarial examples without substitute models or training data. Across the reported tasks and comparisons, the attack achieves higher success with lower perturbation than prior strategies.

  • Problem

    NLP attacks must preserve semantics and fluency despite discrete word changes, while hard-label black-box attacks can observe only the target’s predicted label.

    Source: Introduction · p. 1

  • Method

    A population-based decision attack optimizes semantically similar adversarial text using only the target’s top label, without substitute models or training data.

    Source: Introduction · p. 1

  • Results

    The attack achieves higher success rates and lower perturbation rates than prior strategies in a highly restricted setting.

    Source: Introduction · p. 1, Conclusion · p. 7

  • Takeaways & Limitations

    The experiments report that hard-label decision-based attacks can generate adversarial examples for NLP classification and entailment tasks without substitute models or training data.

    Source: Introduction · p. 1, Conclusion · p. 7

Abstract

from arXiv · show

We study an important and challenging task of attacking natural language processing models in a hard label black box setting. We propose a decision-based attack strategy that crafts high quality adversarial examples on text classification and entailment tasks. Our proposed attack strategy leverages population-based optimization algorithm to craft plausible and semantically similar adversarial examples by observing only the top label predicted by the target model. At each iteration, the optimization procedure allow word replacements that maximizes the overall semantic similarity between the original and the adversarial text. Further, our approach does not rely on using substitute models or any kind of training data. We demonstrate the efficacy of our proposed approach through extensive experimentation and ablation studies on five state-of-the-art target models across seven benchmark datasets. In comparison to attacks proposed in prior literature, we are able to achieve a higher success rate with lower word perturbation percentage that too in a highly restricted setting.

Introduction

NLP attacks must preserve meaning and fluency despite discrete word changes, while hard-label black-box attacks can use only the target’s predicted label. The paper proposes a population-based decision attack for NLP and reports higher success with lower perturbation than prior strategies in this restricted setting.

Introduction

  • NLP attacks are difficult because a single word replacement can alter meaning, and generated text must remain grammatical and fluent.White-box methods require internal model details, while score-based and transfer-based approaches depend on confidence scores or substitute models.Source: Introduction · p. 1
  • Hard-label black-box attacks observe only the target’s top label, avoiding access to its architecture, gradients, confidence scores, training data, or substitute models.The authors describe this setting as practical but highly challenging.Source: Introduction · p. 1
  • The attack targets text classification and entailment, generating plausible, semantically similar adversarial examples without training data or substitute models.It uses population-based optimization to maximize semantic similarity.Source: Introduction · p. 1
  • The authors report higher success rates and lower perturbation rates than prior attacks in a highly restricted setting.They describe hard-label attacks as previously explored in computer vision, but say theirs is the first exploration of this setting for NLP.Source: Introduction · pp. 1–2

Related Work

  • Prior approaches include gradient-dependent white-box attacks, confidence-score-based attacks, substitute-model transfer attacks, and a decision-based GAN approach requiring training data [Zhao, Dua, and Singh 2017].The paper contrasts its setting with these methods’ access or data requirements.Source: Related Work · p. 2

Problem Formulation

The formulation seeks an adversarial text that changes the target model’s prediction while remaining semantically similar to the original. It expresses this as constrained optimization, then reformulates the constraint using a discontinuous penalty.

Problem Formulation

  • The goal is to find an adversarial sequence X* that the target misclassifies while remaining semantically similar to the original input X.The paper casts this goal as a constrained optimization problem.Source: Problem Formulation · p. 2
  • S measures semantic similarity, while C equals 1 when X* is outside the target model’s decision boundary and 0 otherwise.The constrained objective requires C(F(X*)) = 1.Source: Problem Formulation · p. 2
  • The reformulated objective uses δ, which is 0 when its condition is true and −∞ otherwise, but remains discontinuous and difficult to optimize with hard-label outputs.Optimizing it can yield an adversarial sample with minimal perturbation.Source: Problem Formulation · p. 2

Proposed Attack

The attack uses three stages: initialize an adversarial sample, reduce its substitutions while preserving adversarial status, and optimize semantic similarity. Synonym constraints and a smaller search space guide this process.

Proposed Attack

  • The proposed strategy initializes X* outside the decision boundary, moves it closer through search-space reduction, then optimizes semantic similarity until it is on the boundary.The target model is queried using only hard-label outputs.Source: Proposed Attack · p. 2, Figure 1 · p. 3

Initialisation

  • Initialization substitutes words with same-part-of-speech synonyms from the top 50 counter-fitted-embedding neighbors, sampling until the input crosses the decision boundary or 30% of its words are replaced.The authors avoid random words and out-of-vocabulary tokens because these can substantially alter meaning.Source: Initialisation · pp. 2–3

Search Space Reduction

  • Search-space reduction restores synonyms to their original words in similarity-ranked order, retaining replacements only while the sample remains adversarial.This moves the sample toward the decision boundary and is described as speeding optimization and helping prevent local optima.Source: Search Space Reduction · p. 3

Population Based Optimization

  • The optimization overview describes a Genetic Algorithm that evolves candidate populations using fitness evaluation, selection, crossover, and mutation.The paper introduces GA as a search-based optimization technique inspired by natural selection.Source: Overview · p. 3, Population Based Optimization · p. 3

1. Initialisation:

The passage states that the algorithm starts with an initial set of candidates.

1. Initialisation:

  • The algorithm starts with an initial set of candidates.Source: §1 · p. 3

2. Selection:

Candidate selection uses fitness values to choose two parents.

2. Selection:

  • Two candidates are selected as parents according to their fitness values.Source: §2 · p. 3

3. Crossover:

Crossover combines selected parents to produce the next set of candidates.

3. Crossover:

  • Selected parents undergo crossover to produce the next set of candidates.Source: §3 · p. 3

4. Mutation:

The procedure uses genetic-algorithm operations to improve semantic similarity while preserving adversarial criteria. The authors report improved success and lower perturbation in the hard-label setting.

4. Mutation:

  • Genetic-algorithm optimization prioritizes semantic similarity rather than target-label probability scores, which are unavailable in the hard-label setting.The method uses mutation, selection, and crossover iteratively.Source: §4 · p. 3
  • The approach improves attack success rate and lowers perturbation percentage in a hard-label setting.Source: §4 · p. 4

Optimization Procedure

  • Mutation tests the original word and its synonyms, filters candidates that fail adversarial criteria, and retains similarity-improving replacements.When several candidates improve similarity, the highest-scoring candidate is selected.Source: Optimization Procedure · p. 4
  • Candidates are selected for crossover according to semantic-similarity fitness, favoring parents with higher similarity to the original text.Source: Optimization Procedure · p. 4

Optimization Steps

  • Crossover generates new candidates, which are filtered by adversarial criteria and similarity before mutation and progression to the next population.The procedure allows up to 100 iterations and at most 25 mutations per substituted-word index.Source: Optimization Steps · p. 5

Experiments

The attack was evaluated on seven classification and entailment datasets, five target models, and seven baselines. It achieved over 90% success and improved on TextFooler across reported metrics.

Experiments

  • Experiments compared the proposed attack strategy with seven state-of-the-art baselines across seven benchmark datasets and five target models, holding out 10% of each dataset for hyperparameter tuning.Source: Experiments · p. 5, Experimental Settings · p. 6

Datasets

  • The benchmarks covered AG News, Yahoo Answers, MR, IMDB, Yelp Reviews, SNLI, and MultiNLI, spanning topic and sentiment classification plus textual entailment.The dataset descriptions identify SNLI and MultiNLI as entailment corpora.Source: Datasets · p. 5

Target Models

  • The target models included WordCNN, WordLSTM, and BERT for classification, plus ESIM, InferSent, and BERT for entailment.The reported WordCNN and WordLSTM configurations used 150 filters or hidden units and 200-dimensional GloVe embeddings.Source: Target Models · p. 5

Baselines

  • The seven baselines included score-based methods PSO, TextFooler, PWWS, TextBugger, and Genetic Attack, plus decision-based GANs and substitute-model-based DeepRL.The passage describes the approaches each baseline uses.Source: Baselines · p. 5

Experimental Settings

  • Evaluation measured after-attack accuracy, word perturbation rate, grammatical-error increase, semantic similarity, and human judgments; examples with perturbation above 25% were filtered out.Semantic similarity was computed with USE; metrics were averaged over generated examples for each dataset.Source: Evaluation Metrics · p. 5, Experimental Settings · p. 5
  • More than 90% success rate on classification and entailment tasks; versus TextFooler, perturbation rate and after-attack accuracy fell by at least 33% and 32%, respectively, and grammatical error rate fell by 27%.The comparison with other baselines also favored the attack on success and perturbation rates.Source: Attack Performance · p. 6, Table 3 · p. 6, Table 2 · p. 6

Ablation Study

The ablations indicate that both search-space reduction and genetic optimization contribute to attack quality and efficiency.

Ablation Study

  • Without search-space reduction, perturbation rose 1.2%, similarity fell 0.1, and optimization slowed at least fivefold; using GA reduced perturbation 4.4% and improved similarity 0.16 versus no GA.Relative to initialization alone, the combined procedure had 20% lower perturbation and 0.25 higher semantic similarity on average.Source: Ablation Study · p. 6

Analysis

The analysis evaluates initialization, transferability, adversarial training, and human judgments of the generated examples. It reports that adversarial-data augmentation improves robustness, while synonym-based initialization supports better semantic similarity and lower perturbation than random-word initialization.

Importance of Synonym-based Initialisation

  • On average, random-word initialization lowers semantic similarity by 0.1 and raises perturbation rate by 2.4% on BERT.The comparison removes synonym-based initialization, which samples from the top 50 synonyms in the counter-fitted space.Source: Analysis · p. 6, Table 6 · p. 7

Transferability

  • Adversarial examples generated by the attack show better transferability than prior attacks on IMDB and SNLI.Table 7 lays out transferability results with the attack-generating model in rows and the model attacked in columns.Source: Analysis · p. 6, Table 7 · p. 7

Analysis Tables

  • Table 4 presents BERT adversarial examples, marking original words and substituted words in bold, with substitutions also enclosed in brackets.Table 5 reports average perturbation rate and semantic similarity for the search-space-reduction and genetic-algorithm analysis, but the supplied passage does not give its outcomes.Source: Table 4 · p. 7, Table 5 · p. 7

Human Evaluation

  • Human evaluators assigned the original class label to 96% of IMDB and 92% of SNLI adversarial examples.The evaluation sampled 25% of adversarial examples and hid their true labels from evaluators; Table 8 presents evaluation scores.Source: Analysis · p. 7, Table 8 · p. 7

Adversarial Training

  • After adversarial-data augmentation, BERT’s after-attack accuracy and perturbation rate increase by 15% and 10%, respectively; Figure 3 depicts increases as more samples are added.The authors interpret the changes as evidence that augmenting training data with adversarial samples makes the target model more robust to attacks.Source: Figure 3 · p. 7, Analysis · p. 7

Conclusion

The paper proposes a population-based decision attack that crafts plausible, semantically similar text adversarial examples using only the target model’s top predicted label. Experiments across multiple models and benchmark datasets report higher success and lower perturbation than prior attack strategies in a highly restricted setting.

Conclusion

  • The proposed decision-based attack uses population-based optimization to craft plausible, semantically similar adversarial examples from only the top predicted label.The conclusion frames the setting as hard-label black-box, where many prior attacks do not work as well.Source: Conclusion · p. 7
  • Extensive experiments across multiple target models and benchmark datasets compare the attack with state-of-the-art baselines.Source: Conclusion · p. 7
  • In a highly restricted setting, the attack achieves higher success rates and lower perturbation rates than prior attack strategies.Source: Conclusion · p. 7

Related papers

Loading 2012.14956v2…