Query-Efficient Textual Adversarial Example Generation for Black-Box Attacks

Zhen Yu, Zhenhua Chen, Kun HeNAACL 2024 · OpenReview

Abstract

Deep neural networks for Natural Language Processing (NLP) have been demonstrated to be vulnerable to textual adversarial examples. Existing black-box attacks typically require thousands of queries on the target model, making them expensive in real-world applications. In this paper, we propose a new approach that guides the word substitutions using prior knowledge from the training set to improve the attack efficiency. Specifically, we introduce Adversarial Boosting Preference (ABP), a metric that quantifies the importance of words and guides adversarial word substitutions. We then propose two query-efficient attack strategies based on ABP: query-free attack ($ABP_{free}$) and guided search attack ($ABP_{guide}$). Extensive evaluations for text classification demonstrate that $ABP_{free}$ generates more natural adversarial examples than existing universal attacks, $ABP_{guide}$ significantly reduces the number of queries by a factor of 10–500 while achieving comparable or even better performance than black-box attack baselines. Furthermore, we introduce the first ensemble attack $ABP_{ens}$ in NLP, which gains further performance improvements and achieves better transferability and generalization by the ensemble of the ABP across different models and domains.

Introduction

Deep Neural Networks (DNNs) in Natural Language Processing (NLP) are notoriously fragile. Minor perturbations, such as swapping a single word for its synonym, can successfully flip a model's prediction (e.g., from "Positive" to "Negative"). However, generating these adversarial examples in a black-box setting—where the attacker only has access to the model's output—is computationally expensive. Current state-of-the-art attacks often require thousands of queries to identify influential words, making them impractical for real-world scenarios with rate limits or high costs. Conversely, "universal attacks" require zero queries but often produce nonsensical text that is easily detectable. This paper addresses the gap by proposing a query-efficient framework that leverages prior knowledge to guide adversarial generation.

Methodology: Adversarial Boosting Preference (ABP)

The core contribution is the Adversarial Boosting Preference (ABP) metric. Instead of an exhaustive search for every new input, ABP utilizes a "proxy" model on the training set to identify linguistic vulnerabilities. ABP is defined by two factors:

  1. Preference ($P$): The frequency of a specific word substitution (e.g., "good" $\rightarrow$ "fine") in successful adversarial examples within the training data.
  2. Influence ($I$): The average change in the model's output logits when that substitution is applied.

Attack Strategies

Based on ABP, three attack strategies are developed:

  • $ABP_{free}$ (Query-Free): A universal-style attack that swaps the top 25% of words based on pre-computed ABP scores, requiring zero queries to the victim model.
  • $ABP_{guide}$ (Guided Search): A black-box attack that prioritizes perturbations using ABP. It follows a three-step process: Greedy Search for an initial hit, Guided Walk for probabilistic exploration, and Pruning to restore naturalness by removing unnecessary changes.
  • $ABP_{ens}$ (Ensemble): Aggregates ABP scores from multiple architectures (e.g., BERT, ALBERT, LSTM) to create a model-agnostic attack with enhanced transferability.
The three-step process of ABP_guide: Greedy Search, Guided Walk, and Pruning.

Experimental Setup

The methods were evaluated on three sentiment analysis benchmarks: IMDB (large-scale movie reviews), SST (fine-grained sentiment), and MR (short snippets). The target models included BERT, ALBERT, and LSTM.

Results and Discussion

The proposed methods demonstrate a significant improvement in the efficiency-performance trade-off.

Efficiency and Success Rate

While traditional black-box attacks like PWWS or PSO require 4,000 to 11,000 queries per sample on IMDB, $ABP_{guide}$ achieves comparable success rates with only 22 to 42 queries—a 10x to 500x reduction. As shown in Figure 3, ABP-based methods occupy the ideal "Higher performance, Lower cost" quadrant compared to baselines.

Comparison of attack success rate versus average query number, highlighting the efficiency of ABP methods.

Naturalness and Real-World Impact

Human evaluations indicate that $ABP_{free}$ generates significantly more natural text (70.8% naturalness) compared to the Universal Adversarial Trigger (UAT) baseline (15.2%). Furthermore, $ABP_{ens}$ proved effective against commercial systems, achieving a 96% success rate against the Amazon Cloud sentiment analysis API.

Key Insights

  • Domain Specificity: Vulnerability is tied to the domain; "fragile" words in movie reviews differ from those in other contexts. Calculating ABP per label (Positive vs. Negative) increases precision.
  • Prior Knowledge: Leveraging pre-computed importance scores drastically reduces the need for brute-force probing.
  • Pruning for Fluency: The final pruning step is critical for maintaining linguistic naturalness, making adversarial examples harder to detect.

Conclusion

This work introduces a highly efficient framework for generating textual adversarial examples. By leveraging prior knowledge through the ABP metric, the proposed attacks significantly reduce query costs while maintaining high success rates and naturalness. Future work may explore integrating ABP with more complex optimization algorithms and utilizing it to identify vocabulary weaknesses for improved adversarial training.

Summary updated

Abstract

Deep neural networks for Natural Language Processing (NLP) have been demonstrated to be vulnerable to textual adversarial examples. Existing black-box attacks typically require thousands of queries on the target model, making them expensive in real-world applications. In this paper, we propose a new approach that guides the word substitutions using prior knowledge from the training set to improve the attack efficiency. Specifically, we introduce Adversarial Boosting Preference (ABP), a metric that quantifies the importance of words and guides adversarial word substitutions. We then propose two query-efficient attack strategies based on ABP: query-free attack (ABPfree) and guided search attack (ABPguide). Extensive evaluations for text classification demonstrate that ABPfree generates more natural adversarial examples than existing universal attacks, ABPguide significantly reduces the number of queries by a factor of 10 500 while achieving comparable or even better performance than black-box attack baselines. Furthermore, we introduce the first ensemble attack ABPens in NLP, which gains further performance improvements and achieves better transferability and generalization by the ensemble of the ABP across different models and domains. Code is available at https://github.com/BaiDingHub/ABP.
BibTeX
@inproceedings{yu2024query,
  author = {Zhen Yu and Zhenhua Chen and Kun He},
  title = {{Query-Efficient Textual Adversarial Example Generation for Black-Box Attacks}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2024},
  url = {https://openreview.net/forum?id=QtGi2D5zeb},
}
Figure