BOSH: An Efficient Meta Algorithm for Decision-based Attacks
This work addresses the challenge of generating optimal adversarial examples with minimal distortion for hard-label black-box attacks, which is incremental as it improves upon existing iterative local update methods.
The paper tackles the problem of decision-based adversarial attacks getting stuck in local minima by proposing BOSH-attack, which uses Bayesian Optimization and Successive Halving to maintain multiple solution paths, resulting in better convergence with a query count reduced by a factor of 10 compared to existing methods.
Adversarial example generation becomes a viable method for evaluating the robustness of a machine learning model. In this paper, we consider hard-label black-box attacks (a.k.a. decision-based attacks), which is a challenging setting that generates adversarial examples based on only a series of black-box hard-label queries. This type of attacks can be used to attack discrete and complex models, such as Gradient Boosting Decision Tree (GBDT) and detection-based defense models. Existing decision-based attacks based on iterative local updates often get stuck in a local minimum and fail to generate the optimal adversarial example with the smallest distortion. To remedy this issue, we propose an efficient meta algorithm called BOSH-attack, which tremendously improves existing algorithms through Bayesian Optimization (BO) and Successive Halving (SH). In particular, instead of traversing a single solution path when searching an adversarial example, we maintain a pool of solution paths to explore important regions. We show empirically that the proposed algorithm converges to a better solution than existing approaches, while the query count is smaller than applying multiple random initializations by a factor of 10.