PARSE : An Efficient Search Method for Black-box Adversarial Text Attacks (2022)

Abstract: Neural networks are vulnerable to adversarial examples. The adversary can successfully attack a model even without knowing model architecture and parameters, i.e., under a black-box scenario. Previous works on word-level attacks widely use word importance ranking (WIR) methods and complex search methods, including greedy search and heuristic algorithms, to find optimal substitutions. However, these methods fail to balance the attack success rate and the cost of attacks, such as the number of queries to the model and the time consumption. In this paper, We propose PAthological woRd Saliency sEarch (PARSE) that performs the search under dynamic search space following the subarea importance. Experiments show that PARSE can achieve comparable attack success rates to complex search methods while saving numerous queries and time, e.g., saving at most 74% of queries and 90% of time compared with greedy search when attacking the examples from Yelp dataset. The adversarial examples crafted by PARSE are also of high quality, highly transferable, and can effectively improve model robustness in adversarial training.

## introduction neural networks have achieved remarkable success in various nlp tasks while being vulnerable to adversarial examples. the adversary can craft adversarial examples, which contain noise that is imperceptible to human but can mislead the model decision, even without knowing the model architecture and parameters. under such black-box scenario, word-level attacks have been more focused on by recent studies for the flexibility of the attack and the high quality generated examples @xcite @xcite @xcite . word-level attacks can flexibly fit * corresponding author. the grammar and semantics constraints by changing the similarity and semantics threshold when filtering candidate substitutions, and the generated adversarial examples will not be detected by a spell checker @xcite or substantially damage the overall semantic and logic of the sentence @xcite . high-quality adversarial examples ensure the attacks are imperceptible to human and can be used to learn the robustness of models better. to better explain our contribution to the wordlevel adversarial attack, we would like first to define the word-level attack as a combinatorial optimization problem, which is similar to @xcite . under this setting, a wordlevel adversarial attack method can be decomposed into search space and search method. the search space gives all the possible substitutions that meet the similarity and semantics requirements for the target words, i.e., decides what words the target words can be transformed into. the search method is the search strategy to perform the attack, i.e., decides which words to be transformed @xcite and what words should be transformed into (pick from the search space). search method is the most significant part of an attack method, as the exponential nature of the search space makes inefficiency search method difficult to attack large-scale and long examples. therefore, we fix the search space and only focus on the search methods in this paper. various search methods for word-level black-box attacks have been proposed, divided into simple methods, including the variants of word importance ranking (wir) methods @xcite @xcite , and complex methods, including greedy search @xcite , beam search @xcite , genetic algorithm @xcite , and particle swarm optimization (pso) algorithm @xcite . wir methods search substitutions for each word in the descending order of word importance scores, which is faster than other complex search methods, while is poor in attack success rate. other search methods can always achieve better attack success rates, while they need more queries to the target model and time, as they directly search on the search space of the entire sentence. previous works fail to balance well between performance and efficiency. in this paper, to achieve higher attack success rates with fewer queries and time in wordlevel black-box attacks, we propose a search method called pathological word saliency search (parse). parse separates the entire sentence into multiple subarea according to the stability of words and searches in the descending order of the subarea importance. therefore, parse avoids directly searching on the huge search space of the entire sentence and reduces the cost of attacks. searching on each subarea instead of on each word like wir methods also makes parse less likely to be stuck in local optima. extensive experiments demonstrate that parse achieves comparable attack success rates to complex search methods while saving numerous queries and time, e.g., saving at most 74% of queries and 90% of time compared with greedy search when attacking the yelp dataset @xcite . figure 1 shows the performance comparisons. the major contributions of this paper are summarized as follows: