  Adversarial attacks in Natural Language Processing apply perturbations in the
character or token levels. Token-level attacks, gaining prominence for their
use of gradient-based methods, are susceptible to altering sentence semantics,
leading to invalid adversarial examples. While character-level attacks easily
maintain semantics, they have received less attention as they cannot easily
adopt popular gradient-based methods, and are thought to be easy to defend.
Challenging these beliefs, we introduce Charmer, an efficient query-based
adversarial attack capable of achieving high attack success rate (ASR) while
generating highly similar adversarial examples. Our method successfully targets
both small (BERT) and large (Llama 2) models. Specifically, on BERT with SST-2,
Charmer improves the ASR in 4.84% points and the USE similarity in 8% points
with respect to the previous art. Our implementation is available in
https://github.com/LIONS-EPFL/Charmer.
