  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.
