Don't Search for a Search Method -- Simple Heuristics Suffice for Adversarial Text Attacks

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