  Black-box hard-label adversarial attack on text is a practical and
challenging task, as the text data space is inherently discrete and
non-differentiable, and only the predicted label is accessible. Research on
this problem is still in the embryonic stage and only a few methods are
available. Nevertheless, existing methods rely on the complex heuristic
algorithm or unreliable gradient estimation strategy, which probably fall into
the local optimum and inevitably consume numerous queries, thus are difficult
to craft satisfactory adversarial examples with high semantic similarity and
low perturbation rate in a limited query budget. To alleviate above issues, we
propose a simple yet effective framework to generate high quality textual
adversarial examples under the black-box hard-label attack scenarios, named
HQA-Attack. Specifically, after initializing an adversarial example randomly,
HQA-attack first constantly substitutes original words back as many as
possible, thus shrinking the perturbation rate. Then it leverages the synonym
set of the remaining changed words to further optimize the adversarial example
with the direction which can improve the semantic similarity and satisfy the
adversarial condition simultaneously. In addition, during the optimizing
procedure, it searches a transition synonym word for each changed word, thus
avoiding traversing the whole synonym set and reducing the query number to some
extent. Extensive experimental results on five text classification datasets,
three natural language inference datasets and two real-world APIs have shown
that the proposed HQA-Attack method outperforms other strong baselines
significantly.
