On the Design of Black-box Adversarial Examples by Leveraging Gradient-free Optimization and Operator Splitting Method

Introduction

In recent years, deep neural networks (DNNs) have achieved significant breakthroughs in many machine learning (ML) tasks. However, despite these success stories, there have been many recent studies showing that even state-of-the-art DNNs might still be vulnerable to adversarial misclassification attacks . The adversarial attacks find and add visually imperceptible noises to an originally correctly classified input and essentially cause it to be misclassified by the DNNs. This raises security concerns about the robustness of DNNs in extreme situations with high reliability and dependability requirement such as face recognition, autonomous driving car and malware detection . Investigating adversarial examples has become an increasingly prevailing topic to develop potential defensive measures in trustworthy ML . It essentially lays the groundwork for building a new generation of highly robust and reliable ML models acting as the core engine of future AI technology.

However, most of preliminary studies on this topic are restricted to the white-box setting where the adversary has complete access and knowledge of the target system (e.g., DNNs) . Despite the theoretical interest, white-box attack methods are not adapted to practical black-box threat models. It is often the case that internal states/configurations and operating mechanism of public ML systems are not revealed to the practitioners (e.g., Google Cloud Vision API). Accordingly, the only mode of interaction with the system is via submitting inputs and receiving the corresponding predicted outputs.

To boost the practicality of such approaches, a few recent works have introduced a new class of threat models that exploit either a surrogate of the target model or a gradient-free attack method . However, adversarial attacks that exploit a surrogate of the target model tend to yield low success rate if the surrogate is inaccurate. On the other hand, while attacks that use zeroth-order gradient estimation are often more effective, they require a large number of queries to obtain an accurate estimate. Thus they are usually not economically efficient, especially in query-limited settings due to budget constraints.

To mitigate the above limitations of the existing literature, this paper introduces a new perspective in the design of black-box adversarial attacks: We propose a general attack framework based on an operator splitting method, the alternating direction method of multipliers (ADMM), which integrates with both zeroth-order (ZO) optimization and Bayesian optimization (BO). Furthermore, unlike previous works which for ease of optimization often assume a specific distortion metric between an input and its perturbed version, our proposed framework is amenable to a broad family of distortion metrics including those previously used in the literature.

$\bullet$ We propose a general black-box adversarial attack framework via ADMM, including zeroth-order ADMM (ZO-ADMM) and ADMM with Bayesian optimization (BO-ADMM). We exploit a promising ZO-ADMM with random gradient estimation (RGE) to design efficient black-box attacks that generalize the previous ZO coordinate descent based black-box attacks and sidestep the notoriously intensive query complexity of attacks based on coordinate-wise random gradient estimation. Besides, we integrate the ADMM with BO for higher query efficiency in black-box settings (Section 4).

$\bullet$ Our framework is also made flexible to robustly accommodate for various threat models of the black-box attack (Section 5), which includes both score-based and decision-based settings. The former allows the attacker to have access to a vector of assessment scores for all output candidates (soft labels). And the latter only provides the system’s final decision on the most probable output (hard labels).

$\bullet$ Finally, we demonstrate the efficiency of our proposed framework on a variety of real-world image classification datasets such as MNIST, CIFAR-10 and ImageNet. The empirical results consistently show that our framework perform competitively to existing works in terms of the attack success rate while achieving a significant reduction on the query complexity (Section 6).

Related Works

The vulnerability of DNNs was first studied in the seminal works , which were followed by a series of white-box threat models that assume full access of the target model’s internal parameters/configurations. However, such internal knowledge of the target model is often not revealed and the adversary can only interact with it via submitting input queries and receiving feedback on potential outputs. Therefore, in the remaining of this section, we will summarize recent advances on black-box adversarial attacks and discuss their limitations in comparison to our proposed framework.

A black-box attack using surrogate model is essentially a transfer attack in which the adversary trains a DNN with data labeled by the target model. The resulting DNN is then exploited as a surrogate of the target model for which we can apply any state-of-the-art white-box attacks without requiring full access to internal states and operating mechanisms of the target model. Such attacks however depend heavily on the quality of training a surrogate model that closely resembles the true target model . As a result, transfer attack tends to yield low success rate in data-intensive domains (e.g., ImageNet) for which it is hard to find a qualifiled surrogate.

2 Black-box Attacks with Gradient Estimation

3 Other Black-box Attacks

In addition to the aforementioned works, there are also other black-box attacks under different practical settings, which are explored very recently. Among those, the notable boundary method implements a decision-based attack, which starts from a very large adversarial perturbation (thus causing an immediate misclassification) and tries to reduce the perturbation (i.e., minimize the distortion) through a random walk while remaining adversarial via staying on the boundary between the misclassified class and the true class. However, it suffers from high computational complexity due to a huge number of queries needed to decrease the distortion and it also has no guarantee on the convergence. Different from , the work formulates the hard-label black-box attack as a real-valued optimization problem which is usually continuous and can be solved by the zeroth-order optimization algorithm. Similarly, addresses the problem of finding a universal (image-agnostic) perturbation in the hard-label black-box setting.

In this paper, we will instead introduce an interesting reformulation of adversarial black-box attack based on ADMM, including ZO-ADMM that enjoys the operator splitting advantage of ADMM and BO-ADMM that reduces the query complexity with the aid of Gaussian process.

Problem Formulation

In the remaining of this section, we will discuss possible choices for the loss function $f(\mathbf{x},t)$. Note that, without loss of generality, we only focus on targeted attack with designated target class $t$ to mislead the DNN since the untargeted attack version can be easily implemented similar to the targeted attack . We also emphasize that in the black-box setting, the gradients of $f(\mathbf{x},t)$ can not be obtained directly as it does in the white-box setting. The form of the loss function $f(\mathbf{x},t)$ depends on the constrained information in different black-box feedback settings. In particular, the definition of score-based (Section 3.1) and decision-based (Section 3.2) attacks as well as their loss functions will be discussed in the following subsections.

In the score-based attack setting, the adversaries are able to make queries to DNN to obtain the soft labels (i.e., scores or probabilities of an image belonging to different classes), while information on gradients are not available. The loss function of problem (3) in the score-based attack is:

which is motivated by and yields the best known performance among white-box attacks. $P(\mathbf{x})_{j}$ denotes the target model’s prediction score or probability of the $j$-th class, and $\kappa$ is a confidence parameter which is usually set to zero. Basically, this implies $f(\mathbf{x}_{0}+\bm{\delta},t)=0$ if $P(\mathbf{x}_{0}+\bm{\delta})_{t}$ is the largest among all classes, which means the perturbation $\bm{\delta}$ has successfully made the target model misclassified $\mathbf{x}_{0}+\bm{\delta}$ to target class $t$. Otherwise, it will be larger than zero. Note that in Eqn. (3.1) the log probability $\log P(\mathbf{x})$ is used instead of directly using the actual probability $P(\mathbf{x})$. This is based on the observation that the output probability distribution tends to have one dominating class, making the query on the probability/score less effective. The utilization of the log operator can help to reduce the effect of the dominating class while it preserves the probability order for all classes.

2 Decision-based Attack

Different from the score-based attack, the decision-based attack is more challenging in that the adversaries can only make queries to get the hard-labels instead of the soft-labels. Let $H(\mathbf{x})_{i}$ denote the hard-label decision. $H(\mathbf{x})_{i}=1$ if the decision for $\bm{x}$ is label $i$, and $0$ otherwise. We also have $\sum_{i=1}^{K}H(\mathbf{x})_{i}=1$ for all $K$ classes. Then the loss function of problem (3) in the decision-based attack is specified as

Therefore, $f(\mathbf{x}_{0}+\bm{\delta},t)\in\{-1,1\}$, and the attacker succeeds if $f(\mathbf{x}_{0}+\bm{\delta},t)=-1$. The loss function (4) is nonsmooth with discrete outputs. The decision-based attack is therefore more challenging because existing combinatorial optimization methods become almost ineffective or inapplicable.

A General Black-box Adversarial Attack Framework

where $\mathcal{I}(\mathbf{z})$ is the indicator function given by,

The augmented Lagrangian of the reformulated problem (4) is given by

where $\mathbf{u}$ is Lagrangian multiplier, and $\rho>0$ is a given penalty parameter. It can be further transformed as below,

The ADMM algorithm splits optimization variables into two blocks and adopts the following iterative scheme,

where $k$ denotes the iteration index. In problem (11), we minimize $\mathcal{L}(\mathbf{z},\bm{\delta},\mathbf{u})$ over $\mathbf{z}$ given parameters $\bm{\delta}^{k}$ and $\mathbf{u}^{k}$. In problem (12), we minimize $\mathcal{L}(\mathbf{z},\bm{\delta},\mathbf{u})$ over $\bm{\delta}$ given $\bm{z}^{k+1}$ from the previous step and $\mathbf{u}^{k}$. Then, the Lagrangian multiplier $\bm{u}$ is updated in Eqn. (13). The major advantage of this ADMM-type algorithm is that it allows us to split the original complex problem into sub-problems, each of which can be solved more efficiently or even analytically. In what follows, we solve problems (11) and (12) respectively.

where $\mathbf{a}=\bm{\delta}^{k}-(1/\rho)\mathbf{u}^{k}$. We set $D(\bm{z})=\|\bm{z}\|_{2}^{2}$ . Problem (4.1) can be decomposed elementwise as below,

where $[\mathbf{x}]_{i}$ (or $x_{i}$) denotes the $i$-th element of $\mathbf{x}$. The solution to problem (4.1) is then given by

2 𝜹\bm{\delta}-step

where $\bm{b}=\bm{z}^{k+1}+(1/\rho)\bm{u}^{k}$. In the white-box setting, since the gradients of $f(\mathbf{x}_{0}+\bm{\delta},t)$ are directly accessible, gradient descent method like stochastic gradient descent (SGD) or Adam can be applied straight-forwardly. However, in black-box settings, the gradients of $f(\mathbf{x}_{0}+\bm{\delta},t)$ are unavailable. Thus, to overcome this difficulty, we adopt two derivative-free methods: the random gradient estimation (RGE) method and the Bayesian optimization corresponding to ZO-ADMM and BO-ADMM, respectively.

In the black-box setting, the gradient of $f(\mathbf{x}_{0}+\bm{\delta},t)$ is estimated through random gradient estimation (RGE),

where $d$ is the number of optimization variables, $\nu>0$ is a smoothing parameter, $\{\mathbf{u}_{j}\}$ denote independent and identically distributed (i.i.d.) random direction vectors drawn from a uniform distribution over a unit sphere, and $Q$ is the number of random direction vectors. It has been shown in that a large $Q$ reduces the gradient estimation error and improves the convergence of ZO-ADMM. However, we find that a moderate size of $Q$ is sufficient to provide a good trade-off between estimation error and query complexity, e.g., $Q=20$ in our experiments. We also highlight that the RGE in (22) only requires $O(Q)$ query complexity instead of $O(dQ)$ caused by coordinate-wise gradient estimation used in . Note that the natural evolutionary strategy (NES) uses a central difference based gradient estimator requiring $2Q$ queries. By contrast, RGE uses a forward difference based random gradient estimator, yielding $Q+1$ query counts, leading to higher query efficiency.

With the aid of RGE, the solution to problem (4.2) can now be obtained via stochastic gradient descent-like methods. However, it suffers from extremely high iteration and function query complexity due to the non-linearity of $f$ as well as the iterative nature of ADMM. To sidestep this computational bottleneck, we propose the use of the linearized ADMM algorithm in ZO-ADMM with RGE, and thus it enjoys dual advantages of gradient-free operation and linearization of the loss function. By linearization, the loss function $f(\mathbf{x}_{0}+\bm{\delta},t)$ in problem (4.2) is replaced with its first-order Taylor expansion plus a regularization term (known as Bregman divergence), that is, $\hat{\nabla}f(\bm{\delta}^{k}+\mathbf{x}_{0},t))^{T}(\bm{\delta}-\bm{\delta}^{k})+\frac{1}{2}\|\bm{\delta}-\bm{\delta}^{k}\|_{\mathbf{G}}^{2}$, where $\mathbf{G}$ is a pre-defined positive definite matrix, and $\|\mathbf{x}\|_{\mathbf{G}}^{2}=\mathbf{x}^{T}\mathbf{G}\mathbf{x}$. We choose $\mathbf{G}=\eta_{k}\mathbf{I}$ where $1/\eta_{k}>0$ is a decaying parameter, e.g., $\eta_{k}=\alpha\sqrt{k}$ for a given constant $\alpha>0$. The Bregman divergence term is used to stabilize the convergence of $\bm{\delta}$.

Combining linearization and RGE, problem (4.2) now takes the following form:

which yields a quadratic programming problem with the following closed-form solution:

Note that Eqn. (25) can be calculated with only one step of gradient estimation, which is a significant improvement on query efficiency compared with solving problem (4.2) using gradient descent method with thousands of random estimations. The convergence of the linearized ADMM for non-convex problems is proved in .

2.2 Bayesian Optimization

In addition to RGE, BO is an alternative approach to solve problem (4.2) . We model $l(\bm{\delta})\mathrel{\mathop{:}}=f(\bm{x}_{0}+\bm{\delta},t)+\frac{\rho}{2}\|\bm{\delta}-\mathbf{b}\|_{2}^{2}$ as a Gaussian process with a prior distribution $l(\cdot)\sim\mathcal{N}(\mu_{0},\kappa(\cdot,\cdot))$, where $\mu_{0}=0$ in practice and $\kappa(\cdot,\cdot)$ is a positive definite kernel . Consider a finite collection of noisy observations $\mathcal{D}_{k}=\{y_{1},\ldots,y_{k}\}$, where $y_{i}\sim\mathcal{N}(l(\bm{\delta}^{i}),\sigma_{n}^{2})$, and $\sigma_{n}^{2}$ is the noise variance. The posterior probability of a new function $l(\bm{\delta})$ evaluation given $\mathcal{D}_{k}$ is a Gaussian distribution with mean $\mu$ and variance $\sigma$, that is $l(\bm{\delta})|\mathcal{D}_{k}\sim\mathcal{N}(\mu,\sigma^{2})$, where

$K_{ij}=\kappa(\bm{\delta}^{i},\bm{\delta}^{j})$, $\bm{\kappa}$ is a vector of covariance terms between $\{\bm{\delta}^{i}\}_{i=1}^{k}$ and $\bm{\delta}$, namely, $\kappa_{i}=\kappa(\bm{\delta}^{i},\bm{\delta})$.

We choose the kernel function $\kappa(\cdot,\cdot)$ as the ARD Matérn $5/2$ kernel ,

where $\{\theta_{i}\}_{i=0}^{d}$ are hyperparameters. Note that $\kappa(\bm{\delta},\bm{\delta})=\theta^{2}_{0}$.

To determine the hyper-parameters $\bm{\theta}=\{\{\theta_{i}\}_{i=0}^{d},\sigma_{n}^{2}\}$, we minimize the negative log marginal likelihood $\log p(\mathcal{D}_{k}|\bm{\theta})$ ,

where $\mathbf{y}=[y_{1}\ y_{2}\ \ldots\ y_{k}]^{\top}$. This can be achieved by a standard gradient descent routine $\bm{\theta}\leftarrow\bm{\theta}{-}\eta\partial{L}/\partial\bm{\theta}$ with a sufficiently small learning rate $\eta$.

In the setting of BO, the solution to problem (4.2) is often acquired by maximizing the expected improvement (EI). The EI acquisition function is defined as

where $l^{+}$ denotes the best observed value, and $\mathcal{I}(l(\bm{\delta})\leq l^{+})=1$ if $l(\bm{\delta})\leq l^{+}$, and $0$ otherwise. $\Phi$ and $\phi$ denote the CDF and PDF of the standard normal distribution, respectively. We refer readers to the supplementary material for the detailed derivation of Eq. (4.2.2). We obtain $\bm{\delta}_{k+1}$ through the projected gradient descent method,

The projection is introduced to ensure the feasibility of the next query point in BO.

Customized Score-based and Decision-based Black-box Attacks

For the score-based black-box attack, problem (3) with loss function (3.1) can be naturally solved through the general ADMM framework.

In the decision-based black-box attack, the form of the loss function (4) is non-smooth with discrete outputs. To overcome the discontinuity in Eqn. (4), a smoothing version of (4), denoted by $f_{\mu}$ with smoothing parameter $\mu>0$ , is taken into consideration,

Performance Evaluation

In this section, the experimental results of the score-based and decision-based black-box attacks are demonstrated. We compare the proposed ADMM-based framework with various attack methods on three image classification datasets, MNIST , CIFAR-10 and ImageNet . The results of state-of-the-art white-box attack (i.e., C&W attack) are also provided for reference.

We train two networks for MNIST and CIFAR-10 datasets, respectively, which can achieve 99.5% accuracy on MNIST and 80% accuracy on CIFAR-10. The model architecture has four convolutional layers, two max pooling layers, two fully connected layers and a softmax layer. For ImageNet, we utilize a pre-trained Inception v3 network instead of training our own model, which can achieve 96% top-5 accuracy. All experiments are conducted on machines with NVIDIA GTX 1080 TI GPUs.

In the evaluation on MNIST and CIFAR-10, 200 correctly classified images are selected from MNIST and CIFAR-10 test datasets, respectively. For each image, the target labels are set to the other 9 classes and a total of 1800 attacks are performed for each attack method.

2 Evaluation on ImageNet

We perform targeted and untargeted attacks in the score-based and decision-based settings on ImageNet. 100 correctly classified images are randomly selected. For each image in targeted attack, 9 random labels out of 1000 classes are selected to serve as the targets. We do not perform the transfer attack since it does not scale well to ImageNet due to training of the surrogate model. Instead, we provide the results of new baselines on ImageNet, including the query-limited attack as well as the label-only attack proposed in , and the bandit optimization based attack with time and data-dependent priors (named as Bandits${}_{\text{TD}}$) . The query-limited and Bandits${}_{\text{TD}}$ attacks are score-based attacks. The label-only attack is a decision-based attack.

The experimental results are summarized in Table 2. For score-based attacks, we can observe that the score-based ZO-ADMM attack can achieve a high ASR with fewer queries than the other attacks. It reduces the query number on initial success by 94.3% and 99.2% for untargeted and targeted attacks, respectively, compared with the ZOO attack. For decision-based attacks, the ZO-ADMM attack can obtain a high ASR with fewer queries compared with the label-only attack or even the ZOO attack using score-based information. Some adversarial examples generated by the ZO-ADMM attack are demonstrated in the supplementary material. More experimental results including the comparison with AutoZoom and the boundary method method are demonstrated in the Appendix.

3 Convergence of the ZO-ADMM Attack

Conclusion

Acknowledgement

This work is partly supported by the National Science Foundation CNS-1932351.

References

If $D(\bm{z})=\|\bm{z}\|_{0}$, the solution to problem (11) can be obtained as follows,

If $D(\bm{z})=\|\bm{z}\|_{1}$, the solution to problem (11) can be obtained as below,

where $(x)_{+}=x$ if $x\geq 0$ and 0 otherwise.

If $D(\bm{z})=\|\bm{z}\|_{1}+\frac{\beta}{2}\|\bm{z}\|_{2}^{2}$, which is also know as elastic net regularization, the solution to problem (11) can be obtained through,

Appendix B Derivation for maximizing EI

Appendix C BO-ZO-ADMM

Appendix D Comparison with AutoZoom and Boundary method

Appendix E Convergence of the ZO-ADMM attack

Figure A1 shows the convergence of the ZO-ADMM attack v.s. query number or ADMM iteration number. Figure A2 shows the convergence comparison of the ZO-ADMM method and the Boundary method.

Appendix F Examples for the decision-based ZO-ADMM attack

In the following, we provide more adversarial examples generated by the proposed ZO-ADMM decision-based black-box attack.