A Strong Baseline for Query Efficient Attacks in a Black Box Setting (2021)

Abstract: Existing black box search methods have achieved high success rate in generating adversarial attacks against NLP models. However, such search methods are inefficient as they do not consider the amount of queries required to generate adversarial attacks. Also, prior attacks do not maintain a consistent search space while comparing different search methods. In this paper, we propose a query efficient attack strategy to generate plausible adversarial examples on text classification and entailment tasks. Our attack jointly leverages attention mechanism and locality sensitive hashing (LSH) to reduce the query count. We demonstrate the efficacy of our approach by comparing our attack with four baselines across three different search spaces. Further, we benchmark our results across the same search space used in prior attacks. In comparison to attacks proposed, on an average, we are able to reduce the query count by 75% across all datasets and target models. We also demonstrate that our attack achieves a higher success rate when compared to prior attacks in a limited query setting.

## introduction in recent years, deep neural networks (dnns) have achieved high performance on a variety of tasks @xcite @xcite @xcite . however, prior studies @xcite have shown evidence that dnns are vulnerable to adversarial examples -inputs generated by slightly changing the original input. such changes are imperceptible to humans but they deceive dnns, thus raising serious concerns about their utility in real world applications. existing nlp attack methods are broadly classified into white box attacks and black box attacks. white box attacks require access to the target model's * equal contribution parameters, loss function and gradients to craft an adversarial attack. such attacks are computationally expensive and require knowledge about the internal details of the target model which are not available in most real world applications. black box attacks crafts adversarial inputs using only the confidence scores or class probabilities predicted by the target model. almost all the prior black box attacks consists of two major components (1) search space and (2) search method. a search space is collectively defined by a set of transformations (usually synonyms) for each input word and a set of constraints (e.g., minimum semantic similarity, part-of-speech (pos) consistency). the synonym set for each input word is generated either from the nearest neighbor in the counter-fitted embedding space or from a lexical database such as hownet @xcite or wordnet @xcite . the search space is variable and can be altered by either changing the source used to generate synonyms or by relaxing any of the above defined constraints. a search method is a searching algorithm used to find adversarial examples in the above defined search space. given an input with w words and each word having t possible substitutes, the total number of perturbed text inputs is (t +1) w . given this exponential size, the search algorithm must be efficient and exhaustive enough to find optimal adversarial examples from the whole search space. black box attacks proposed in @xcite employ combinatorial optimization procedure as a search method to find adversarial examples in the above defined search space. such methods are extremely slow and require massive amount of queries to generate adversarial examples. attacks proposed in @xcite search for adversarial examples using word importance ranking which first rank the input words and than substitutes them with similar words. the word importance ranking scores each word by observing the change in the confidence score of the target model after that word is removed from the input (or replaced @xmath0. although, compared to the optimization based methods, the word importance ranking methods are faster, but it has some major drawbacks -(1) each word is ranked by removing it from the input (or replacing it with @xmath1, (2) it not clear whether the change in the confidence score of the target model is caused by the removal of the word or the modified input and (3) this ranking mechanism is inefficient on input of larger lengths. in general, their exists a trade off between the attack success rate and the number of queries. a high query search method generates adversarial examples with high success rate and vice-versa. all such prior attacks are not efficient and do not take into consideration the number of queries made to the target model to generate an attack. such attacks will fail in real world applications where there is a constraint on the number of queries that can be made to the target model. to compare a new search method with previous methods, the new search method must be benchmarked on the same search space used in the previous search methods. however, a study conducted in @xcite have shown that prior attacks often modify the search space while evaluating their search method. this does not ensure a fair comparison between the search methods because it is hard to distinguish whether the increase in attack success rate is due to the improved search method or modified search space. for example, @xcite compares their search method with @xcite where the former uses universal sentence encoder (use) @xcite and the latter use language model as a constraint. also, all the past works evaluate their search methods only on a single search space. in this paper foot_0 , we address the above discussed drawbacks through following contributions: ## proposed approach given a target model f : @xmath2, that maps the input text sequence x to a set of class labels y. our goal is to generate an adversarial text sequence x adv that belongs to any class in y except the original class of x i.e. f(x ) = f(x adv ). the input x adv must be generated by substituting the input words with their respective synonyms from a chosen search space. our search method consists of two steps (1) word ranking -ranks all words in the input text and (2) word substitution -substitutes input words with their synonyms in the order-of-rank (step 1). ## ablation study we study the effectiveness of attention and lsh component in our method by doing a three way ablation. we observe the change in success rate, perturbation rate and queries when both or either one of the two ranking components are removed. no lsh and attention: first, we remove both the attention and lsh scoring steps and rank the ## acknowledgement we would like to thank all the reviewers for their critical insights and positive feedback. we would also like to thank riyaz ahmed bhat for having valuable discussions which strengthen our paper and helped us in responding to reviewers. a appendix algorithm 2 word ranking input: test sample x output: w containing score of each word x i 1: f attn ← han () or da() 2: α ← f attn (x ) 3: for x i in x do 4: s ← synonyms(x i ) 5: