# A Self-Adaptive Approximated-Gradient-Simulation Method for Black-Box Adversarial Sample Generation
## 3 Our Proposed Algorithm
### Model Construction  
In a DNN, the image \(x\) is entered into the hidden layer to retrieve its features, and finally outputs the confidence vector of n categories \(p(x,n)\in[0,1]\). The SAGM is a black-box attack method without concern for the DNN internal configurations; therefore, the adversarial image \(x^{\prime}\) that is similar to the image \(x\) belonging to category \(t\) is identified as another category \(t^{\prime}(t^{\prime}\
eq t)\). To achieve this goal, the SAGM needs to solve the following constrained optimization problem presented in Equation (2). \[ \begin{array}{ll}minimize&D(x^{\prime})=\left\|x^{\prime}-x\right\|_{2}\\ s.t.&C(x^{\prime})=t^{\prime}\\ &x^{\prime}=x+\delta\\ &\delta\in[0,1]^{n}\end{array}  \tag{2}\]  
The constrained optimization problem is to explore similar images with validity to implement misclassification. \(C(x^{\prime})=t^{\prime}\) is an extremely non-linear function whose purpose is to misclassify the image into category \(t^{\prime}\). In other words, the confidence that the image  
Figure 1: The SAGM framework. belongs to category \(t^{\prime}\)(i.e.,\(p(x^{\prime},t^{\prime})\)) is the highest among all categories. Based on this consideration, the non-linear function is converted to the following Equation (3) function. \[l\big{(}x^{\prime}\big{)}=p\big{(}x^{\prime},t\big{)}-\underset{k\
eq t}{\max} p\big{(}x^{\prime},k\big{)} \tag{3}\]  
where \(t\) is the category of the original image \(x,p(x^{\prime},t)\) is confidence in the category \(t\), \(\underset{k\
eq t}{\max}p(x^{\prime},k)\) is the maximum confidence among all categories \(k\) that do not belong to category \(t\). When \(l(x^{\prime})\) is less than or equal to 0, the image is misclassified into other categories. Therefore, the converted function has the same purpose as the original function, which is to misclassify perturbed images. The constrained optimization problem (2) is transformed into the following new constrained optimization problem for optimization (Equation (4)). \[ \begin{array}{ccc}minimize&D(x^{\prime})=\|x^{\prime}-x\|_{2}\\ s.t.&p(x^{\prime},t)-\underset{k\
eq t}{\max}p(x^{\prime},k)\leq 0\\ &&x^{\prime}=x+\delta\\ &&\delta\in[0,1]^{n}\end{array}  \tag{4}\]  
The main purpose of Equation (4) is to explore the perturbed vector \(\delta\) and add it to the original image \(x\) to fool the DNN. The relationship between the three parameters in Equation (4) is depicted in Figure 2.  
Figure 2 shows that there is an area gap between the two different categories. The red and blue dashed circles represent the feasible region \(X=\bigg{\{}x\bigg{|}x\in\underset{k\
eq t}{\max}\ p(x^{\prime}+\delta,k)\bigg{\}}\) and initial solution \(X_{0}=\{x|x\in p(x,t)\}\) of the model (4), respectively. The black dashed line indicates the gap \(\delta\) between the two categories. Based on the characteristics of the model, model (4) is converted to an unconstrained non-linear optimization problem using the exterior point method, which constructs a penalty function to penalize points in the infeasible region, as seen in the following formula (Equation (5)). \[P(x)=\bigg{\{} \begin{array}{cc}0,&x\in X\\ M,&x\
otin X\end{array}  \tag{5}\]  
where \(M\) is a large positive number. The penalty function (5) can be transformed into the unconstrained problem, but there is a jump at the boundary. Therefore, to avoid this problem, the penalty function of  
(4) is constructed as shown in Equation (6). \[ \begin{array}{c}P_{cg}(\delta)=\varepsilon_{g}\bigg{\{}\bigg{[}\max\bigg{(} p(x+\delta,t)-\underset{k\
eq t}{\max}\ p(x+\delta,k),0\bigg{)}\bigg{]}\\ \hskip 14.226378 pt+[\max(-\delta,0)]+[\max(\delta-1,0)]\bigg{\}}\end{array}  \tag{6}\]  
Figure 2: The relationship between the adversarial image and the original image. In (6), \(c_{g}\) is the penalty parameter with an ascending sequence, making \(x\) gradually approach the optimal solution from the outside of the feasible region. Therefore, (4) is converted to the following augmented objective function (Equation (7)).