  We focus on the problem of adversarial attacks against models on discrete
sequential data in the black-box setting where the attacker aims to craft
adversarial examples with limited query access to the victim model. Existing
black-box attacks, mostly based on greedy algorithms, find adversarial examples
using pre-computed key positions to perturb, which severely limits the search
space and might result in suboptimal solutions. To this end, we propose a
query-efficient black-box attack using Bayesian optimization, which dynamically
computes important positions using an automatic relevance determination (ARD)
categorical kernel. We introduce block decomposition and history subsampling
techniques to improve the scalability of Bayesian optimization when an input
sequence becomes long. Moreover, we develop a post-optimization algorithm that
finds adversarial examples with smaller perturbation size. Experiments on
natural language and protein classification tasks demonstrate that our method
consistently achieves higher attack success rate with significant reduction in
query count and modification rate compared to the previous state-of-the-art
methods.
