Fast Gradient Sign Method (FGSM attack) proof

 

FGSM

 

FGSM wants to move in the direction that crosses the boundary via one jump like one-gadget.

 

 

 

$ x'=x+r $, pertubated image, can be created by an equation: 

$ x'=x+\epsilon \cdot sign(\nabla_{x} L(x, y)) $

 

Although the attack code is easily implemented by few lines,

I think we should study why $ x+r $ can be expressed by the above equation in some constraints.

https://pytorch.org/tutorials/beginner/fgsm_tutorial.html

 

 

 

$$ \text{For an image } x \in \mathbb{R}^p \text{ and its correct label } y \in \{1,2,..., K\}, \newline \text{the untargeted FGSM can be defined as the following optimization problem:} \\[6pt] r^{*} \in \argmax_{r\in R^p} \ L(x, y)+r^{T}\nabla_{x} L(x, y) \ \text{subject to} \ ||r||_{\infty} \leq \epsilon \\[6pt] \text{where } \epsilon >0 \text{ is a hyperparameter and } L \text{ is the cross-entropy function.} \newline \text{Suppose that } L(x,y) \text{is continuously differentiable in terms of the first argument } x. \newline \text{Using the KKT conditions, show that the adversarial example } \newline x'=x+r^* \text{ is expressed by } x'=x+\epsilon \cdot sign(\nabla_{x} L(x, y)). $$ $ \boldsymbol{\mathbf{proof)}} $ $$ \text{The optimization problem we need to have to solve is as follows:} \\[6pt] \max_{r\in R^p} \ L(x+r, y) \ \text{subject to} \ ||r||_{\infty} \leq \epsilon \\[6pt] \text{Using the first-order Taylor approximation, the following equation can be expressed.} \\[6pt] \max_{r \in R^p} \ L(x, y)+r^{T}\nabla_{x} L(x, y) \ \text{subject to} \ ||r||_{\infty} \leq \epsilon \\[20pt] \text{Given that }||r||_\infty \text{ is defiend as } \max_{i} |r_{i}| \text{, the above problem can be express as follows:} \\[6pt] \max_{r \in R^p} \ L(x, y)+r^{T}\nabla_{x} L(x, y) \ \text{s.t.} \ r_{i} \leq \epsilon , \ \ r_{i} \leq -\epsilon \ , \ i=1,..., \ p\\[6pt] \text{Focusing on the specific term, we consider:} \\[6pt] \max_{r \in R^p} \ r^{T}\nabla_{x} L(x, y) \ \text{s.t.} \ r_{i} \leq \epsilon , \ \ r_{i} \leq -\epsilon ,\ i=1,..., \ p \\[20pt] \text{To employ the KKT conditions, we transform the problem into one of finding a} \newline \text{ local minimizer} \\[6pt] \min_{r \in R^p} \ -r^{T}\nabla_{x} L(x, y) \ \text{s.t.} \ r_{i} \leq \epsilon , \ \ r_{i} \leq -\epsilon ,\ i=1,..., \ p \\[20pt] \text{By converting the problem into the form of a Lagrangian function and examining}\newline \text{the KKT conditions, we can analyze the necessary conditions for optimality in the} \newline \text{presence of constraints.} \\[10pt] \mathcal{L(r,\alpha,\beta)}=\ -r^{T}\nabla_{x} L(x, y)-\sum^{p}_{i=1}{\alpha_{i}(\epsilon-r_{i}})-\sum^{p}_{i=1}{\beta_{i}(\epsilon+r_{i}}) \\[10pt] \left\{ \begin{aligned} & [\nabla\mathcal{L(r,\alpha,\beta)}]_i=-[\nabla_{x} L(x, y)]_i+\alpha_i-\beta_i=0 \ \cdots \text{Stationarity} \\ & -\epsilon \leq r_i \leq \epsilon \ \cdots \text{Feasibility} \\ & \alpha_i \geq 0, \ \beta_i \geq 0 \ \cdots \text{Dual Feasibility} \\ & \alpha_{i}(\epsilon-r_i)=0, \beta_{i}(\epsilon+r_i)=0 \ \ \cdots \text{Complementary Slackness} \end{aligned} \right. \\[10pt] \text{if} \ |r_i|<\epsilon, \text{then } \alpha_i=0, \ \beta_i=0. \Rightarrow -[\nabla_{x} L(x, y)]_i = 0 \\[6pt] \text{if} \ r_i=\epsilon, \text{then } \beta_i=0. \Rightarrow \alpha_i =[\nabla_{x} L(x, y)]_i \geq 0 \\[6pt] \text{if} \ r_i=-\epsilon, \text{then } \alpha_i=0. \Rightarrow \beta_i =-[\nabla_{x} L(x, y)]_i \geq 0 \\[10pt] \text{thus}\\[10pt] r_i=\left\{ \begin{aligned} & +\epsilon \ \ \ \text{if } [\nabla_{x} L(x, y)]_i > 0 \\ & -\epsilon \ \ \ \text{if } [\nabla_{x} L(x, y)]_i < 0 \\ & 0 \ \ \ \ \ \ \ \text{otherwise} \end{aligned} \right. \\ \text{For convenience in the 'otherwise' case, we calculate it as zero.} \\[10pt] \text{therefore } x'=x+\epsilon \cdot sign(\nabla_{x} L(x, y)) $$