Don’t Search for a Search Method — Simple Heuristics Suffice for Adversarial Text Attacks (2021)

Abstract: Recently more attention has been given to adversarial attacks on neural networks for natural language processing (NLP). A central research topic has been the investigation of search algorithms and search constraints, accompanied by benchmark algorithms and tasks. We implement an algorithm inspired by zeroth order optimization-based attacks and compare with the benchmark results in the TextAttack framework. Surprisingly, we find that optimization-based methods do not yield any improvement in a constrained setup and slightly benefit from approximate gradient information only in unconstrained setups where search spaces are larger. In contrast, simple heuristics exploiting nearest neighbors without querying the target function yield substantial success rates in constrained setups, and nearly full success rate in unconstrained setups, at an order of magnitude fewer queries. We conclude from these results that current TextAttack benchmark tasks are too easy and constraints are too strict, preventing meaningful research on black-box adversarial text attacks.

## introduction neural networks are currently deployed in many production systems from image classification to natural language processing (nlp). while they show impressive results, many of such systems are also susceptible to adversarial examples. these examples are close in space to data points that are classified correctly, but due to small changes are classified incorrectly. this corresponds to the local non-smoothness noted by @xcite . @xcite present a zeroth order optimization-based (zoo) attack that significantly outperforms other black-box attacks for image processing. an initial goal of our work was to investigate whether a zoo approach that guides * part of the work done while the first author was interning at google. the search for adversarial examples by approximate gradient information can be transferred to adversarial attacks in nlp. to this end, we implemented a zoo-inspired algorithm in the textattack framework @xcite ) and compared it with their benchmark results @xcite . surprisingly, we found that search guided by a zoo approach only yields minimal improvements, whereas heuristic search exploiting nearest neighbors yields competitive success rates at minimal query count. we conclude from these results that the victim models in current benchmark tasks are too easily broken and imperceptibility constraints are too strict, thus defeating meaningful research on black-box search methods for adversarial attacks. ## related work black-box attacks on nlp systems generally attempt to search over discrete tokens and, instead of bounding the perturbation in euclidean space, use linguistic constraints over the selected tokens. @xcite implement a discrete genetic algorithm where genes are tokenized sentences (genetic alg in the above black-box attacks on nlp systems along with greedy and beam search are reimplemented by @xcite . their library, textattack, seeks to be a test bed for comparing adversarial attacks on nlp systems. to this end, a companion paper comparing different attacks has been released by @xcite . chen et al. (2017) work under the adversarial attack framework of carlini and wagner (2017) and use a zeroth order optimization method to work in a black-box setting to attack images. the zoo idea is to create pseudogradients using zeroth order estimates of the true gradient. their method performs point-wise perturbations on individual pixels by adding a scaled one-hot vector e i to the image x and computing the difference between the outputs. the derivative of this single perturbed pixel can then be calculated by f (x+µe i )-f (x-µe i ) 2µ inspired by the zeroth order optimization-based attack of @xcite and the interpretable displacements of @xcite , we developed a discretized version of zeroth order optimization for attacks on nlp systems, dubbed discretezoo. ## discretezoo for black-box attacks on nlp systems zeroth order optimization assumes nothing about the function to optimize other than the fact that it is smooth. we add the assumptions here that we possess a surrogate embedding space and that there is a smooth transformation from this embedding space to the internal embedding space of the target model. continuous zeroth order gradient estimation requires that any arbitrary point be queryable in order to use gaussian noise as perturbations. in the discrete case, however, the system only allows us to query with tokens. instead of sampling from a gaussian distribution then, we sample from the nearest neighbours around the target token in the surrogate embedding space. given the current token t, we can perturb its embedding e t with a vector µu k,t , with µ = ||e k -e t ||, u k,@xmath0, and e k being the embedding of another token. we can use this to calculate the finite differences between two different function evaluations. sampling a set of multiple neighbouring tokens n for displacements yields the update rule adding this estimated direction vector to the current embedding then moves towards an area of increasing goal function values, where we would hope to find a token suitable for flipping the label. once the direction vector is added to the embedding, we snap it to the nearest existing token by cosine similarity. in addition to the zoo-inspired search, we use the word importance ranking of @xcite and @xcite , which replaces each token in the text with an unk token to decide which tokens to attack first. additionally, we noticed that often label-flipping tokens are already available within the sampled tokens n . in this case, we should accept the sampled token and return early, saving queries to the model, instead of continuing to sample and construct a direction vector. another optimization prevents the algorithm from snapping to the nearest token if that token decreases the goal function value. a detailed algorithm is given in the appendix. code implementing the algorithm can be found at https://github.com/statnlp/ discretezoo . ## results results for the baseline attacks and discretezoo are summarized in in in the unconstrained setup, all search methods, including discretezoo, approach success rates of 100%. the methods are only able to evaluate the 50 nearest neighbors, however, the farthest baseline reaches success rates of 78.31% and 81.04% on movie reviews and snli, respectively. random and closest follow farthest in terms of success rate, with a query count that is an order of magnitude lower than other methods. the continued sampling version of the random baseline achieves nearly 100% success rate on both datasets with a similarly small query count. the relative success of the baseline heuristic methods shows that the nearest neighbor structure in the embedding space is already powerful enough to flip the label. much of the success of the other methods can already be attributed to these simple heuristics, showing that search is not always necessary. ## analysis the results of the previous experiments show slight improvement over previous methods but they appear curious. for example, some of the results have no variation on repeated runs even with a stochastic algorithm. additionally, random token selection appears to be competitive with greedywir methods. the counterfitted glove embedding space @xcite is a very sparse embedding space, containing a total of 65713 tokens. using the neighborhood threshold given by the constr. constraints, a cosine similarity of 0.9 or higher, then the average token in this embedding space has 0.72 neighbors. among tokens that have neighbors, the average rises to 2.63. histograms showing number of tokens over neighborhood size with different neighborhood definitions can be seen in figure 1 in the appendix. these values are an upper bound on the actual average number of neighbors as the constraints also include bertscore and a part of speech constraint which further restrict the space. the sparsity of the space coupled with the size of the neighborhoods induced by cosine similarity of 0.9 or higher could explain why the naive methods are able to perform so well compared to more sophisticated optimization methods. there are so few valid replacement tokens in the space that it is entirely feasible to try every option with the greedywir or beam methods. with a large enough sample size, discretezoo already observes all allowed replacement tokens during sampling and is able to stop if one of them flips the label. in this case, discretezoo and greedy-wir should produce similar results. this is effectively demonstrated by the random baseline, which chooses a replacement token randomly and is unable to use information from the goal function to decide between multiple replacement tokens. because there are so few possible replacement tokens, randomly selecting from the few that are available is roughly as good of a strategy as beam search or greedily selecting the best replacement token from all options. the results given by the random baseline are close to those reported by @xcite for their greedywir baselines. this suggests that the success of their attacks compared to the more advanced search methods is not because of their algorithm finding good texts but rather because the search space has been so restricted that any choice will work. methods besides greedywir are allowed more flexibility. instead of just considering one target position at a time, they are allowed to consider the best replacement for all positions. this turns the attack into a combinatorial problem of finding which combination of positions is best to attack instead of which replacement tokens are the best. additionally, this shows that the models being attacked are very brittle. given a single target token that has replacements, there are on average only three to choose from. selecting one of these three very similar tokens is already enough to flip the label in many cases. ## conclusion zeroth order optimization methods have been shown to yield superior performance for black box attacks in continuous spaces such as images @xcite . in attacks on nlp systems, only a discrete set of tokens are admissable as input but they are still processed as vectors in continuous space. this allows for optimization in the continuous space instead of in the discrete token space. we implement a zeroth order optimization algorithm in the textattack library @xcite and compare with the results of @xcite . while our method appears to be competitive, we find that the linguistic constraints imposed on the search methods are so tight that nearly no optimization is necessary. instead, selecting the farthest allowable token or a random token is already enough to flip the label in many cases. we argue that more robust tasks are required for meaningful research on black-box adversarial text attacks.