On the Design of Black-box Adversarial Examples by Leveraging Gradient-free Optimization and Operator Splitting Method
Pu Zhao Sijia Liu Pin-Yu Chen Nghia Hoang Kaidi Xu Bhavya Kailkhura Xue Lin
cs.CV cs.CR cs.LG







On the Design of Black-box Adversarial Examples by Leveraging 
 Gradient-free Optimization and Operator Splitting Method
    
Pu Zhao^1, Sijia Liu^2, Pin-Yu Chen^2, Trong Nghia Hoang^2, Kaidi Xu^1, Bhavya Kailkhura^3, Xue Lin^1

^1Department of Electrical and Computer Engineering, Northeastern University

^2MIT-IBM Watson AI Lab, IBM Research

^3Syracuse University


zhao.pu@husky.neu.edu, {sijia.liu, pin-yu.chen, nghiaht}@ibm.com,  xu.kaid@husky.neu.edu, 
 
bkailkhu@syr.edu,  
xue.lin@northeastern.edu
 

    December 30, 2023
=====================================================================================================================================================================================================================================================================================================================================================================================================


empty


Robust machine learning is currently one of the most prominent topics  which could potentially help shaping a future of advanced AI platforms that not only perform well in average cases but also in worst cases or adverse situations. Despite the long-term vision, however, existing studies on black-box adversarial attacks are still restricted to very specific settings of threat models (e.g., single distortion metric and restrictive assumption on target model's feedback to queries) and/or suffer from prohibitively high query complexity. To push for further advances in this field, we introduce a general framework based on an operator splitting method, the alternating direction method
of multipliers (ADMM)  to devise efficient, robust black-box attacks that work with various distortion metrics and feedback settings without incurring high query complexity. Due to the black-box nature of the threat model,   the proposed ADMM solution framework is integrated with zeroth-order (ZO) optimization and Bayesian optimization (BO), and thus is applicable to the gradient-free regime. This results in two new black-box adversarial attack generation methods, ZO-ADMM and BO-ADMM.
Our empirical evaluations on image classification datasets show that our proposed approaches have  much lower  function query complexities compared to state-of-the-art attack methods, but achieve very competitive attack success rates. Codes are available at <https://github.com/LinLabNEU/Blackbox_ADMM>.




§ INTRODUCTION


In recent years,  deep neural networks (DNNs) have achieved  significant  breakthroughs <cit.> 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 <cit.>. 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 <cit.>. Investigating adversarial examples has  become an increasingly prevailing topic to develop potential defensive measures in trustworthy ML <cit.>. 

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) <cit.>. 





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 <cit.> or a
gradient-free  attack method <cit.>. 
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 <cit.> 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. 




Our Contributions: 


∙
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) <cit.> to design efficient black-box attacks that generalize the previous ZO coordinate descent based black-box attacks <cit.> 
 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 <ref>). 


∙ We further generalize our formulation to accommodate various bounded ℓ_p-norm-ball distortion metrics and their linear spans in the metric space (see Section <ref>). Such an extension is highly non-trivial  to be incorporated into existing formulations of other black-box  attacks,
which are often heavily customized towards a specific norm-ball (e.g., ℓ_2 or ℓ_∞) for distortion metrics. 


∙ Our framework is also made flexible to robustly accommodate for various  threat models of the black-box attack
(Section <ref>), 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).


∙ 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 <ref>). 




§ RELATED WORKS


The vulnerability of DNNs was first studied in the seminal works <cit.>,

which were followed by a series of white-box threat models <cit.> 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.



 §.§ Black-box Attack with Surrogate Model


A black-box attack using surrogate model is essentially a transfer attack <cit.> 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 <cit.>. 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.





 §.§ Black-box Attacks with Gradient Estimation 


Another approach to explore black-box attacks is to use gradient estimation via zeroth-order optimization (ZOO) <cit.>. They make queries to the model and estimate the output gradients with respect to the corresponding inputs, and then apply the state-of-the-art C&W attack method <cit.> to generate adversarial examples. However, this method is very computationally intensive as it requires a large number of queries per iteration to generate an accurate gradient estimation. Alternatively, the work <cit.> 
aims to estimate output gradient via greedy local search. At each iteration, the proposed technique perturbs only a small subset of input component. Such local search technique is very computationally efficient but it does not explicitly minimize the distortion between the original input and its perturbed version, the crafted noises often appear more visible. 
The work <cit.> investigates the   more realistic threat models by defining the query-limited setting, the partial information setting, and the label-only setting. Three attacks methods  are proposed based on the  Natural Evolutionary Strategies and Monte Carlo approximation. But it only puts limits on the ℓ_∞ norm instead of minimizing a certain ℓ_p norm. Based on <cit.>, the work <cit.> further investigates to utilize the prior information including the time-dependent priors (i.e., successive gradients are in fact heavily correlated) and the data-dependent priors (i.e., images tend to exhibit a spatially local similarity ) for higher query efficiency. 






 §.§ Other Black-box Attacks


In addition to the aforementioned works, there are also other  black-box attacks <cit.> under different practical settings, which are explored very recently. Among those, the notable boundary method
<cit.>
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 <cit.>, the work <cit.> 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, <cit.> 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 <cit.> 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 this work, we   focus on adversarial attacks in the application of image classification with DNNs. In what follows, we first provide a general problem formulation for adversarial attack which is amenable to either white-box or black-box settings. Then, we will develop an efficient solution to the more interesting black-box setting where the adversary only has access to certain types of output of the DNN model (its internal structures and configurations are unknown to the adversary). Specifically, given a legitimate image 𝐱_0 ∈ℝ^d with its correct class label t_0, we aim to design an optimal adversarial perturbation δ∈ℝ^d so that the perturbed example (𝐱_0 + δ) is misclassified to target class t ≠ t_0 by the DNN model trained on legitimate images. The adversarial perturbation δ can be obtained by solving the  problem of the  generic form,

    [                           _δ       f(𝐱_0 + δ, t) + γ D(δ);                   subject to (𝐱_0 + δ) ∈ [0,1]^d,  δ_∞≤ϵ, ]

where f(𝐱, t) denotes an attack loss incurred by misclassifying (𝐱_0 + δ) to target class t,   D(δ) is a distortion function that controls perceptual similarity between a legitimate image and an adversarial example, 
and
 ·_∞ signifies  the ℓ_∞ norm.
In problem (<ref>), the `hard' constraints ensure that the perturbed noise δ at each pixel (normalized to [0,1]) is imperceptible up to a predefined ϵ-tolerant threshold, 
and the non-negative 
parameter γ places emphasis on the distortion. 
Furthermore, in the above problem, we mainly set D(δ) = δ_2^2, which is motivated by the superior performance of the outstanding C&W ℓ_2 adversarial attack. We highlight that D(δ) can take other forms of ℓ_p norms as discussed in Section <ref>.







The problem (<ref>) is the general form of the problem in <cit.> which does not consider the D(δ) term. The advantage is that we are able to minimize the ℓ_p distortion after the adversarial perturbation is obtained, thus keeping the perturbation imperceptible. More specifically, if ϵ is too small, we may not be able to obtain a successful adversarial example. Thus, we need to increase ϵ to achieve a successful adversarial attack. But since ϵ only limits the largest element of the perturbation, the whole perturbation over the image might be relatively large and easy to be recognized in case of large ϵ.  Thus, the D(δ) term in problem (<ref>) helps to minimize the  ℓ_p distortion of the whole perturbation, keeping it unnoticeable. 

In the remaining of this section, we will discuss possible choices for the loss function f(𝐱, 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 <cit.>.
We also  emphasize that in the black-box setting, the gradients of f(𝐱, t) can not be obtained directly as it does in the white-box setting.
The form of the loss function  f(𝐱, t) depends on the  constrained information in different black-box feedback settings. In particular, the definition of score-based (Section <ref>) and decision-based (Section <ref>) attacks as well as their loss functions will be discussed in the following subsections.
 




 §.§ Score-based Attack


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 (<ref>)  in the score-based attack is:

    f(𝐱_0 + δ, t)  = max{   max_j ≠ t{log P(𝐱_0+ δ)_j }
        - log P(𝐱_0+ δ )_t, - κ},

which is motivated by <cit.> and yields the best known performance among white-box attacks. P(𝐱)_j denotes the target model's prediction score or probability of the j-th class,  and κ is a confidence parameter which is usually set to zero.  
Basically, this implies f(𝐱_0 + δ, t) = 0 if  P(𝐱_0+ δ )_t is the largest among all classes, which means the perturbation δ has successfully made the target model misclassified 𝐱_0 + δ to target class t. Otherwise, it will be larger than zero. 
Note that in Eqn. (<ref>) the log probability log P(𝐱) is used instead of directly using the actual probability P(𝐱). 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. 














 §.§ 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(𝐱)_i denote the  hard-label decision. 
H(𝐱)_i = 1 if the decision for x is label i, and 0 otherwise. We also have ∑_i=1^K H(𝐱)_i = 1 for   all K classes. Then  the loss function of problem (<ref>)  in the decision-based attack  is specified as

    f(𝐱_0 + δ, t) =max_j ≠ t  H(𝐱_0+ δ)_j -H(𝐱_0+ δ )_t,

 Therefore, f(𝐱_0 + δ, t) ∈{-1,1 }, and the attacker succeeds if f(𝐱_0 + δ, t) = -1.
The loss function (<ref>) 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



This section develops a general black-box adversarial attack framework for both the score-based and decision-based attacks by leveraging  ADMM and gradient-free optimization. We will show that the proposed attack  framework yields the following benefits: a) an efficient splitting between the black-box loss function  and the adversarial distortion function,  b)  generalization to various ℓ_p norm involved hard/soft constraints, and c) compatibility to different gradient-free operations.


By introducing an auxiliary variable 𝐳, problem (<ref>)  can be rewritten in the favor of ADMM-type methods <cit.>,

    [                         _δ, 𝐳 f(𝐱_0 + δ, t) + γ D(𝐳) + ℐ(𝐳);                    subject to                        𝐳 = δ, ]

where ℐ(𝐳) is the indicator function given by,

    ℐ(𝐳) = {[                            0 (𝐱_0 + 𝐳) ∈ [0,1]^d,  𝐳_∞≤ϵ,;                            ∞                   otherwise. ].


The augmented Lagrangian of the reformulated problem (<ref>) is given by

    ℒ(𝐳, δ, 𝐮) = 
       γ D(𝐳) + ℐ(𝐳)+  f(𝐱_0 + δ, t) 
    
      + 𝐮^T(𝐳 - δ) + ρ/2𝐳 - δ_2^2,

where  𝐮 is Lagrangian multiplier, and ρ > 0 is a given penalty   parameter. It can be further transformed as below,

    ℒ(𝐳, δ, 𝐮) = 
       γ D(𝐳) + ℐ(𝐳)+  f(𝐱_0 + δ, t) 
    
      + ρ/2z  - δ + 1/ρu_2^2 - 1 /2ρu_2^2.


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

    𝐳^k+1 = _𝐳ℒ(𝐳, δ^k, 𝐮^k), 
       δ^k+1 = _δℒ( 𝐳^k+1, δ,   𝐮^k ), 
       𝐮^k+1 = 𝐮^k + ρ ( 𝐳^k+1 - δ^k+1),
 
where k denotes the iteration index. In problem (<ref>), we minimize ℒ(𝐳, δ, 𝐮) over 𝐳 given parameters δ^k and 𝐮^k. In problem (<ref>), we minimize ℒ(𝐳, δ, 𝐮) over δ given z^k+1 from the previous step  and 𝐮^k. Then, the Lagrangian multiplier u is updated in Eqn. (<ref>). 
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 (<ref>) and (<ref>) respectively.



 §.§ 𝐳-step


Problem (<ref>) can be rewritten as

    [                           _𝐳         D(𝐳) + ρ/2γ𝐳 - 𝐚_2^2;                   subject to (𝐱_0 + 𝐳) ∈ [0,1]^d,  𝐳_∞≤ϵ, ]

where 𝐚 = δ^k - (1/ρ) 𝐮^k. We set D(z) = z_2^2 <cit.>.
Problem (<ref>) can be decomposed elementwise as below,  

    [                                          _z_i                        (z_i - ρ/2γ+ρ a_i  )^2;                                    subject to (  [ 𝐱_0   ]_i +  z_i ) ∈ [0,1],    |z_i| ≤ϵ, ]

where [𝐱]_i (or x_i) denotes the i-th element of 𝐱.
The solution to problem (<ref>) is then given by 

    [𝐳^k+1]_i = {[                  min{ 1-  [𝐱_0  ]_i, ϵ}  ρ/2γ+ρ a_i >  min{ 1-  [ 𝐱_0   ]_i, ϵ};               max{ -   [ 𝐱_0   ]_i, -ϵ} ρ/2γ+ρ a_i <  max{ -   [ 𝐱_0   ]_i, -ϵ};                              ρ/2γ+ρ a_i                              otherwise. ].




Generalization to various ℓ_p norms.
In problem (<ref>), in addition to the worst-case perturbation constraint z_∞≤ϵ, it is a common practice to set D(z) = z_2^2 to measure the similarity between the legitimate image and the adversarial example. If D(z)  takes other ℓ_p norms such as z_0, z_1, 
or even ℓ_p norm combinations like  z_1 + β/2z_2^2 for β≥ 0, we are still able to obtain the solutions with minor modifications in the z-step. 
This ability is highly non-trivial for other black-box  attacks, which  are  often  heavily  customized to minimize a specific ℓ_p norm for distortion measure.
Due to space limitation, we explicitly show the z-step solutions of D(z) = z_0, D(z) = z_1 and D(z) = z_1 + β/2z_2^2 derived with proximal operators <cit.> in the supplementary material. 



 









 §.§ δ-step


Problem (<ref>) can be written as

    [                              _δ f(𝐱_0 + δ, t) + ρ/2δ - 𝐛_2^2  , ]

where b =  z^k+1 + (1/ρ)  u^k. In the white-box setting, since the gradients of f(𝐱_0 + δ, 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(𝐱_0 + δ, t) are unavailable.   Thus, to overcome this difficulty, we adopt two derivative-free methods: the random gradient estimation (RGE) method <cit.> and the Bayesian optimization <cit.> corresponding to ZO-ADMM and BO-ADMM, respectively.




  §.§.§ Random gradient estimation

In the black-box setting, the gradient of f(𝐱_0 + δ, t) is estimated through random gradient estimation (RGE),
 
    ∇̂f(δ) = (d/(ν Q)) ∑_j=1^Q 
      [  f ( δ + ν𝐮_j ) - f ( δ )  ]𝐮_j,

where  d is the number of optimization variables, ν> 0 is a smoothing parameter, {𝐮_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 <cit.> 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 (<ref>) only requires O(Q) query complexity instead of O(dQ) caused by coordinate-wise gradient estimation used in <cit.>. Note that the  natural evolutionary strategy (NES) <cit.> 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 (<ref>) 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 <cit.> 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(𝐱_0 + δ, t) in problem (<ref>) is replaced with  its  first-order  Taylor  expansion  plus  a  regularization  term  (known  as  Bregman divergence), that is, ∇̂f(δ^k + 𝐱_0, t))^T ( δ - δ^k) + 1/2δ  - δ^k _𝐆^2, where 𝐆 is a pre-defined positive definite matrix, and 𝐱_𝐆^2 =  𝐱^T 𝐆𝐱. We choose 𝐆 = η_k  𝐈  where 1/η_k >0 is a decaying parameter, e.g.,   η_k = α√(k) for a given constant α > 0. The Bregman divergence term is used to stabilize the convergence of δ.

Combining linearization and RGE, problem (<ref>) now takes the following form:

    [                                   _δ     (∇̂f(δ^k + 𝐱_0, t))^T ( δ - δ^k);                                      + η_k/2δ - δ^k _2^2 + ρ/2δ - 𝐛_2^2 , ]

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

    δ^k+1 =  (1/  ( η_k +   ρ ) )
         ( η_k δ^k +ρ𝐛  - ∇̂f(δ^k + 𝐱_0,t)
         ).


Note that Eqn. (<ref>) can be calculated

with only one step of gradient estimation, which is a significant improvement on query efficiency compared with solving problem (<ref>) using gradient descent method with thousands of random estimations.  
The convergence of the linearized ADMM for non-convex problems is proved in <cit.>. 



  §.§.§ Bayesian Optimization


In addition to RGE, BO is an alternative approach to solve problem (<ref>) <cit.>.
We model 
l(δ) f( x_0 + δ,t) + ρ/2δ - 𝐛_2^2
as a Gaussian process with a prior distribution l(·) ∼𝒩(μ_0, κ(·, ·)), where μ_0 = 0 in practice and κ(·, ·) is a positive definite kernel <cit.>. 
Consider a finite collection of noisy observations 𝒟_k = { y_1, …, y_k }, where y_i   ∼𝒩(l(δ^i), σ_n^2), and σ_n^2 is the noise variance.
The posterior probability of a new function 
l(δ)
evaluation given 𝒟_k  is a Gaussian
distribution with mean μ and variance  σ, that is l(δ) | 𝒟_k ∼𝒩 (μ , σ^2), where

    μ    = κ^T [𝐊 + σ_n^2 𝐈]^-1𝐲, 
      σ^2     = κ(δ , δ ) - κ^T [𝐊 + σ_n^2 𝐈]^-1κ,

K_ij = κ(δ^i, δ^j), κ is a vector of covariance terms between {δ^i }_i=1^k and δ, namely, κ_i = κ(δ^i, δ). 

We choose the kernel function κ(·,·)  as the ARD Matérn 5/2 kernel <cit.>,

    κ(𝐱, 𝐲)    = θ_0^2 exp(-√(5) r) (1+ √(5)r + 5/3 r^2),
       r^2    = ∑_i=1^d (x_i - y_i)^2/θ_i^2,

where {θ_i }_i=0^d are hyperparameters. Note that κ(δ , δ ) = θ^2_0.

To determine the hyper-parameters θ = {{θ_i }_i=0^d,  σ_n^2},
we minimize the negative log marginal likelihood  log p(𝒟_k | θ) <cit.>,


    _θ  L(θ)     ≜1/2log|𝐊 + σ_n^2𝐈| 
       +  1/2𝐲^⊤(𝐊 + σ_n^2𝐈)^-1𝐲  ,

where 𝐲 = [y_1 y_2 … y_k]^⊤. This can be achieved by a standard gradient descent routine θ←θ-η∂L/∂θ with a sufficiently small learning rate η.

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

    δ^k+1   = EI(δ) 
       = 𝔼_l(δ)| 𝒟_k [  ( l^+ - l(δ)  ) ℐ (l(δ) ≤ l^+)  ],
        
       = _δ  (l^+ - μ) Φ ( l^+ - μ/σ ) + σϕ (
        l^+ - μ/σ ),

where l^+ denotes the best observed value, and ℐ (l(δ) ≤ l^+) = 1 if l(δ) ≤ l^+, and 0 otherwise. Φ and ϕ denote the CDF and PDF of the standard normal distribution, respectively.  We refer readers to the supplementary material for the detailed derivation of Eq. (<ref>). 
We obtain δ_k+1 through the projected  gradient descent method, 


    δ̂^(k+1) = δ^(k) + η∇_δ = δ^(k)EI (δ),  
       δ^(k+1) = Proj_(𝐱_0 + δ) ∈ [0,1]^d,  δ_∞≤ϵ (   δ̂^(k+1) ).

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 (<ref>) with loss function (<ref>) can be naturally solved through the general ADMM  framework. 

In the decision-based black-box attack, the form of the loss function (<ref>) is non-smooth with discrete outputs. To overcome the discontinuity in Eqn. (<ref>), a smoothing version of (<ref>), denoted by f_μ with smoothing parameter μ > 0 <cit.>,
 is taken into consideration,

    f_μ(𝐱_0 + δ, t)  = 𝔼_𝐮∈ U_b[f(𝐱_0 + δ + μ𝐮, t)],

where U_b is a uniform distribution within the unit Euclidean ball, or 𝐮 can follow a standard Gaussian distribution <cit.>.
The rational behind the smoothing technique in  (<ref>) is that
 the convolution of two functions, i.e.,
 ∫_𝐮 f(𝐱_0 + δ + μ𝐮, t) p(𝐮) d 𝐮,
 is at least as smooth as the smoothest
of the two original functions <cit.>. Therefore, when 
p is the density of a random variable with respect to Lebesgue measure, the loss function (<ref>) is then smooth.
In practice, we consider  
an empirical Monte Carlo approximation of (<ref>) 

    f_μ(𝐱_0 + δ, t) ≈ 1/N∑_i=1^N f(𝐱_0 + δ + μ𝐮_i, t),

where {𝐮_i } are N i.i.d. samples drawn from U_b. With the smoothed loss function as expressed in Eqn. (<ref>), problem (<ref>) can be solved by the proposed general  ADMM framework. 
 To initialize ADMM, we initialize the perturbation δ so that the initial perturbed image belongs to the target class, yielding a benefit of reducing query complexity compared to the initialization with an arbitrary image <cit.>.




§ 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 <cit.>, CIFAR-10 <cit.> and ImageNet <cit.>. 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 <cit.> 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.



 §.§ Evaluation on MNIST and CIFAR-10



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. 



The implementations of C&W (white-box) attack <cit.> and ZOO (black-box) attack <cit.>


are based on the GitHub code released by the authors[
Codes are available at <https://github.com/LinLabNEU/Blackbox_ADMM>.
]. 
For ZOO attack, we use ZOO-Adam with default Adam parameters. 

For the transfer attack <cit.>, we apply C&W attack  to the surrogate model 
with κ = 20 to improve the attack transferability and  2,000 iterations in each binary search step. 
In the proposed ZO-ADMM attacknote1, the sampling number 
in random gradient estimation as defined in Eqn. (<ref>), Q, is set to 20 and the sampling
number for the decision-based smoothed loss function (<ref>), N, is set to 10. 
 We set ρ=10 and γ=1 for MNIST, ρ=2000 and γ=10 for CIFAR-10, and ρ=1000 and γ=1 for ImageNet. ϵ is set to 1  for MNIST and CIFAR-10  [This setting is intended to make a fair comparison to the pure ℓ_2-norm attack framework ZOO. ]  and 0.05 for ImageNet. In Eq. (<ref>), we set ν=0.5   for three datasets.
The parameter μ in Eq. (<ref>) is set to 1 for MNIST, 0.1 for CIFAR-10, and 0.01 for ImageNet. 






The experimental results are shown in Table <ref>.
Besides the attack success rate (ASR) and the ℓ_p norms, we report the query number required to achieve the first successful attack, which characterizes how fast the generated adversarial perturbation can mislead DNNs.



We observe that the transfer attack suffers from low ASR and large ℓ_2 distortion.
Both the ZOO attack and the proposed ZO-ADMM attack with RGE  can achieve high ASR and competitive ℓ_2 distortion  close to the C&W white-box  attack. 
Compared with the ZOO attack, the   score-based  ZO-ADMM attack   requires  fewer queries to obtain the first successful adversarial example. The query count  in ZO-ADMM attack with RGE is reduced by 95.9% and 95.7% on MNIST and CIFAR-10, respectively. 
The reduction of query number is achieved by Eq. (<ref>) in ZO-ADMM, which only requires one step of gradient estimation to solve the approximation problem instead of thousands of steps to solve the original problem.   
We also observe that the score-based BO-ADMM attack   can achieve smaller query number compared with the RGE method, but it causes much larger ℓ_p distortion. The reason is that BO-ADMM does not have very precise control for the perturbation. So it requires larger perturbation to mislead the DNN model. 
 Although BO-ADMM may have its limitations, we find that combining the advantage of BO- and ZO-ADMM can lead to more query-efficient attacks. Please refer to the BO-ZO-ADMM section in the appendix.







We notice that the  decision-based ZO-ADMM attack   achieves an ℓ_2 distortion slightly larger than the score-based attack with more queries as shown in Table <ref>. This is not surprising, since only the hard label outputs are available in the decision-based attack, which is  more difficult to be optimized than the score-based attack. Although the ℓ_2 distortion is a bit larger, the perturbations are still visually indistinguishable.

We compare  the  decision-based ZO-ADMM attack  with the boundary attack <cit.>. As demonstrated in Table <ref>, the queries of the  decision-based ZO-ADMM attack is about 60% less than that of the boundary attack to achieve the same level ℓ_2 distortion. 
 We show the evolution of several adversarial examples in the decision-based attack versus the query number in Fig. <ref>. The decision-based attack starts from an image in the target class. 
Then it tries to decrease the ℓ_2 norm 
while keeping the classified label unchanged. After about 20,000 queries, the example is close to the original image with a satisfied ℓ_2 distortion.
 




 §.§ 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 <cit.>, and the bandit optimization based attack with time and data-dependent priors (named as Bandits_TD) <cit.>.
The query-limited  and Bandits_TD attacks are  score-based attacks. The label-only attack is a decision-based attack. 

 
The experimental results are summarized in Table <ref>. 
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 <cit.> and the boundary method <cit.> method are demonstrated in the Appendix.














 §.§ Convergence of the ZO-ADMM Attack
 


In Fig. <ref>, we demonstrate the convergence of the proposed ZO-ADMM targeted black-box attack, where  
the average ℓ_2 distortion of 9 targeted adversarial examples versus the query number 
is presented. 
As we can see, since we initialize the adversarial distortion from zeros, the  score-based ZO-ADMM attack
increases   ℓ_2 distortion  until a successful adversarial example is found. After that, it tries to decrease the  ℓ_2 distortion but keeps the target label unchanged. 
For the decision-based attack, Fig <ref> shows that the ℓ_2 distortion is initially large  as  ZO-ADMM   starts from an image in the target class instead of the original image. The resulting ℓ_2 distortion  then decreases as the query number increases.
We highlight that the ZO-ADMM attack is able to reach the successful attack with hundreds of queries on MNIST or CIFAR-10 and tens of thousands of queries on ImageNet, which significantly outperforms the ZOO attack. 
Besides Fig. <ref> demonstrating the  ℓ_2 distortion versus query number, we present the ℓ_2 distortion versus ADMM iteration number in the supplementary material and similar results can be drawn.
















 












 §.§ Evaluation for Various ℓ_p Norms



In the previous experiments, 

we mainly consider the case of  D(z) = z_2^2 for a fair comparison with other white-box and black-box algorithms. However, we highlight that the ZO-ADMM method is able to optimize various ℓ_p norms, not only ℓ_2 norm.
In Table <ref>, we present the experimental results for different ℓ_p norms when solving problem (<ref>). Here we focus on 
 three score-based black-box attacks with ZO-ADMM by minimizing the ℓ_0, ℓ_1 and ℓ_2 distortion, respectively. As we can see, our proposed method is well adapted to different ℓ_p norms in the design of black-box adversarial examples.







§ CONCLUSION


In this paper, we propose a general framework to design norm-ball bounded black-box adversarial examples by leveraging  an operator splitting method (namely, ADMM), together with the gradient-free operations including random gradient estimation and Bayesian optimization. The proposed framework can be applied to both score-based and decision-based settings. Compared  to  state-of-the-art  black-box  attacks,  our  approach  achieves better query efficiency without losing   the attack performance in terms of  attack success rate as well as ℓ_p-norm distortion.




§ ACKNOWLEDGEMENT

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



ieee_fullname










§ SOLUTIONS FOR DIFFERENT ℓ_P NORMS IN Z-STEP

In problem (11), we set D(z) = z_2^2 to measure the similarity between the legitimate image and the adversarial example. But D(z)  can also take other ℓ_p norms and the solutions in z-step can be obtained with minor modifications. 

In the following, we show the z-step solutions[We do not investigate the case of ℓ_∞ norm since the constraint z_∞≤ϵ on the ℓ_∞ norm is already taken into consideration.] for D(z) = z_0, D(z) = z_1, and D(z) = z_1 + β/2z_2^2, derived from proximal operators 
which are     applicable and   well-suited to problems of substantial recent interest involving large or high-dimensional datasets.



 §.§ Solutions for ℓ_0 norm

If D(z) = z_0, the solution to problem (11) can be obtained as follows,

    [𝐳^k+1]_i =    {[                       min{ 1-  [𝐱_0  ]_i, ϵ} if  c_i  
            > min{ 1-  [ 𝐱_0   ]_i, ϵ};                    max{ -   [ 𝐱_0   ]_i, -ϵ}  if   c_i 
         <  max{ -   [ 𝐱_0   ]_i, -ϵ};                                          c_i                                   otherwise, ].

where

    c_i = {[             a_i if a_i^2 > 2γ/ρ;               0       otherwise ].




 §.§ Solutions for ℓ_1 norm

If D(z) = z_1, the solution to problem (11) can be obtained as below,

    [𝐳^k+1]_i =    {[             min{ 1-  [𝐱_0  ]_i, ϵ}  if  (a_i-γ/ρ)_+ - (- a_i - γ/ρ)_+;                                            > min{ 1-  [ 𝐱_0   ]_i, ϵ};          max{ -   [ 𝐱_0   ]_i, -ϵ} if   (a_i-γ/ρ)_+ - (- a_i - γ/ρ)_+;                                          <  max{ -   [ 𝐱_0   ]_i, -ϵ};                        (a_i-γ/ρ)_+;                  - (- a_i - γ/ρ)_+                         otherwise, ].

where (x)_+ =x if x ≥ 0 and 0 otherwise.




 §.§ Solutions for combination of ℓ_1 and ℓ_2 norm

If D(z) = z_1 +  β/2z_2^2, which is also know as elastic net regularization, the solution to problem (11) can be obtained through,

    [𝐳^k+1]_i =    {[       min{ 1-  [𝐱_0  ]_i, ϵ}   if  1/1+γβ/ρ ( (a_i-γ/ρ)_+;                                      - (- a_i - γ/ρ)_+  );                                > min{ 1-  [ 𝐱_0   ]_i, ϵ};    max{ -   [ 𝐱_0   ]_i, -ϵ}   if  1/1+γβ/ρ ( (a_i-γ/ρ)_+;                                      - (- a_i - γ/ρ)_+  );                              <  max{ -   [ 𝐱_0   ]_i, -ϵ};       1/1+γβ/ρ ( (a_i-γ/ρ)_+;         - (- a_i - γ/ρ)_+  )                   otherwise, ].







§ DERIVATION FOR MAXIMIZING EI

EI can be transformed as follows,

    EI(δ)     l^' = 
        l(δ) - μ/σ=𝔼_l^' [
      ( l^+ - l^'σ - μ ) ℐ (
      l^'≤l^+ - μ/σ )
         ] 
        = (l^+ - μ) Φ ( l^+ - μ/σ ) - σ E_l^' [ 
        l^'ℐ (
      l^'≤l^+ - μ/σ )
         ] 
         = (l^+ - μ) Φ ( l^+ - μ/σ ) - σ∫_-∞^l^+ - μ/σ l^'ϕ (l^') d l^'
        =  (l^+ - μ) Φ ( l^+ - μ/σ ) + σϕ (
        l^+ - μ/σ ),




§ BO-ZO-ADMM

In BO-ZO-ADMM, BO is used to obtain a query-efficient attack solution (at early ADMM iterations) for initializing the ZO method, which can further minimize  the  adversarial distortion (at later ADMM iterations). Additional experiments showed that when reaching the same ℓ_2 distortion as  ZO-ADMM,   BO-ZO-ADMM    requires 380   queries on   MNIST and 320 queries on CIFAR-10, outperforming 493 and 421 queries in Table 1.




§ COMPARISON WITH AUTOZOOM AND BOUNDARY METHOD


For the comparison with AutoZoom <cit.>, we report the averaged number of queries for attacking 500images at the same ℓ_2 distortion level for MNIST, CIFAR-10,and ImageNet in Table <ref>.  As we can see, the proposed ZO-ADMM method is more query-efficient, while it is worth noting that AutoZOOM produces adversarial  perturbation  in  low-dimensional  latent  space,and thus saves more computation cost.




In Table <ref>, we show the comparison of ZO-ADMM method with the Query-limited <cit.> and Boundary methods <cit.> in terms of query number and ℓ_p norms on ImageNet. 






§ CONVERGENCE OF THE ZO-ADMM ATTACK


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





§ 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.









