SHARP : Search-Based Adversarial Attack for Structured Prediction (2022)

Abstract: Adversarial attack of structured prediction models faces various challenges such as the difficulty of perturbing discrete words, the sentence quality issue, and the sensitivity of outputs to small perturbations. In this work, we introduce SHARP, a new attack method that formulates the black-box adversarial attack as a search-based optimization problem with a specially designed objective function considering sentence fluency, meaning preservation and attacking effectiveness. Additionally, three different searching strategies are analyzed and compared, i.e., Beam Search, Metropolis-Hastings Sampling, and Hybrid Search. We demonstrate the effectiveness of our attacking strategies on two challenging structured prediction tasks: Pos-tagging and dependency parsing. Through automatic and human evaluations, we show that our method performs a more potent attack compared with pioneer arts. Moreover, the generated adversarial examples can be used to successfully boost the robustness and performance of the victim model via adversarial training.

## introduction adversarial attacking aims to mislead the victim model (e.g., a trained dependency parser) to produce erroneous outputs when feeding adversarial examples. the process can be seen in figure 1 . adversarial training improves the victim model in terms of performance and robustness by training on adversarial examples. since structured prediction tasks such as sequence labeling and dependency parsing are critical building blocks of many natural language processing (nlp) systems, it is essential ˚kewei tu is the corresponding author. ; these authors contributed equally. to study adversarial attacks and defense of structured prediction models @xcite . however, multiple technical challenges are faced by attackers of structured prediction models in the nlp area. all adversarial attackers for nlp tasks face general challenges related to gradient computation of discrete inputs, grammatical correctness, and meaning preservation @xcite @xcite @xcite . another potential but important challenge lies in the sensitivity of structured prediction: small perturbations to input sentences may very likely change the target output structures. in contrast, small perturbations typically do not change sentence classification labels. @xcite first qualitatively proposed this assumption. we quantitatively investigate this sensitivity in ## related work there is limited literature available for adversarial attacking on structured prediction tasks. previous adversarial training has been conducted on nlp tasks such as text classification @xcite , machine translation @xcite @xcite and dialogue systems @xcite . recently, adversarial training has also been explored on structured prediction tasks, such as dependency parsing @xcite . @xcite replaced some words with adversarially chosen counterparts with the same part of speech tags. they target specific syntactic adversarial sentence examples to attack dependency parser. @xcite investigated generation-based attackers for structured prediction tasks. ## conclusion in this paper, we quantitatively investigate the sensitivity of structured prediction tasks and formulate the black-box adversarial attack as a search problem that seeks to maximize a specially designed objective function. both automatic and human evaluations show that our approach beats the previous approaches by a large margin in attacking victim models and simultaneously guarantees better fluency and meaning preservation. our defense experiments show that the adversarial samples generated by our approach can be used to improve the original model's robustness and performance.