Anti attack based on conjugate gradient method

1 introduction

  Deep learning models are vulnerable to attacks against samples , Although the existing methods based on the fastest descent have achieved a high attack success rate , But the ill conditioned problem of optimization will occasionally reduce their attack performance . To solve this problem , In this paper, the author draws lessons from the conjugate gradient method which is effective for such problems , A new anti attack algorithm based on conjugate gradient method is proposed . In fact, in the optimization course of the University , It will involve learning the fastest descent method , conjugate gradient method , And quasi Newton method . The author applies the conjugate gradient method to combat attacks very well . Experimental results show that , For most models , The method proposed in this paper is better than the existing SOTA The algorithm can find better confrontation samples with fewer iterations , Moreover, the more diversified search of the method proposed in this paper significantly improves the success rate of countering attacks .

Thesis link ： https://arxiv.org/abs/2206.09628
Paper code ： https://github.com/yamamura-k/ACG

2 Against attack

  Let locally differentiable functions $g:\mathcal{D}\subseteq {\mathbb{R}}^m\to {\mathbb{R}}^K$ It's a $K$ Class classifier , The category label is $\arg \underset{k}{\max }(g_k(\cdot ))$. sample ${\mathbf{x}}_{\mathrm{orig}}\in \mathcal{D}$ By classifier $g$ Classified as $c$. Given the distance function $d(\cdot ,\cdot )$ And disturbance size $\epsilon >0$, The feasible region for countering attacks is defined as $\mathcal{S}=\{\mathbf{x}\in \mathcal{D}|d({\mathbf{x}}_{\mathrm{orig}},\mathbf{x})\le \epsilon \}$, Counter samples ${\mathbf{x}}_{\mathrm{adv}}$ Defined as $$\arg \underset{k}{\max }{g}_k({\mathbf{x}}_{\mathrm{adv}})\ne c,d({\mathbf{x}}_{\mathrm{orig}},{\mathbf{x}}_{\mathrm{adv}})\le \epsilon$$ Make $L$ To find the confrontation sample ${\mathbf{x}}_{\mathrm{adv}}$ The objective function of . The mathematical form of fighting attacks is as follows ：$$\underset{\mathbf{x}\in \mathcal{D}}{\max }L(g(\mathbf{x}),c)s.t.d({\mathbf{x}}_{\mathrm{orig}},\mathbf{x})\le \epsilon$$ The above formula makes the sample $\mathbf{x}$ For classifiers $g$ Classify into $c$ Class differentiation decreases . In general , There are two kinds of distances used against attacks , They are Euclidean distances $d(\mathbf{v},\mathbf{w}):=\Vert \mathbf{v}-\mathbf{w}{\Vert }_2$, Uniform distance $d(\mathbf{v},\mathbf{w}):=\Vert \mathbf{v}-\mathbf{w}{\Vert }_{\infty }$ And $\mathcal{D}=[0,1{]}^m$.

 PGD Attack is a very important method to combat attack . Given classifier $f:{\mathbb{R}}^m\to \mathbb{R}$,PGD The mathematical form of the generated countermeasure sample is ${\mathbf{x}}^{(k+1)}=P_{\mathcal{S}}({\mathbf{x}}^{(k)}+{\eta }^{(k)}\nabla f({\mathbf{x}}^{(k)}))$, among ${\eta }^{(k)}$ The step size of resisting disturbance ,$P_{\mathcal{S}}$ Project the sample to the feasible region $\mathcal{S}$ The operation of .APGD The attack was PGD An improved version of the attack , It introduces momentum operation in the iterative process . Make ${\mathbf{\delta }}^{(\mathbf{k})}$ Iterate the direction of attack for each step （ namely $\nabla f({\mathbf{x}}^k)$）,APGD The specific form of attack is as follows ：
$$\begin{array}{rl}{\mathbf{z}}^{\prime (k+1)}& ={\mathbf{x}}^{(k)}+{\eta }^{(k)}\sigma ({\mathbf{\delta }}^{(k)})\\ {\mathbf{z}}^{(k+1)}& =P_{\mathcal{S}}({\mathbf{z}}^{\prime (k)})\\ {\mathbf{x}}^{(k+1)}& =P_{\mathcal{S}}({\mathbf{x}}^{(k)}+\alpha ({\mathbf{z}}^{(k+1)}-{\mathbf{x}}^{(k)})+(1-\alpha )({\mathbf{x}}^{(k)}-{\mathbf{x}}^{(k-1)}))\end{array}$$ among $\sigma$ Expressed as a way of regularization ,$\alpha$ Is the intensity coefficient of momentum , Generally, take $\alpha =0.75$.

3 Conjugate gradient attack

  Conjugate gradient method is generally used to solve linear problems , Then it is extended to solve convex quadratic minimization problems and general nonlinear problems . Conjugate gradient method can be used in unconstrained and projection constrained problems . Given an initial point ${\mathbf{x}}^{(0)}$, Initial conjugate gradient ${\mathbf{s}}^0$ Set to $0$, The first $k$ Search points ${\mathbf{x}}^{(k)}$ And conjugate gradient ${\mathbf{s}}^{(k)}$ Is updated to $$\begin{array}{rl}{\mathbf{s}}^{(k)}& =-\nabla f({\mathbf{x}}^{(k)})+{\beta }^{(k)}{\mathbf{s}}^{(k-1)}\\ {\eta }^{(k)}& =\mathrm{argmin}\{f({\mathbf{x}}^{(k)}+\eta {\mathbf{s}}^{(k)})|\eta \ge 0\}\\ {\mathbf{x}}^{(k+1)}& ={\mathbf{x}}^{(k)}+{\eta }^{(k)}{\mathbf{s}}^{(k)}\end{array}$$ among $k\ge 1$,${\beta }^{(k)}$ It is the parameter calculated from the past search information .${\eta }^{(k)}$ Usually satisfied by something similar to Wolfe Determined by conditional linear search , Because it is difficult to solve the following problems $${\eta }^{(k)}=\mathrm{argmin}\{f({\mathbf{x}}^{(k)}+\eta {\mathbf{s}}^{(k)})|\eta \ge 0\}$$ Consider minimizing a strictly quadratic convex function problem $$f(\mathbf{x})={\mathbf{x}}^{\top }A\mathbf{x}+{\mathbf{b}}^{\top }\mathbf{x}$$ among $A$ It's a positive definite matrix ,$\mathbf{x}\in {\mathbb{R}}^n$. under these circumstances , coefficient ${\beta }^{(k)}$ The calculation formula of is $${\beta }^{(k)}=\frac{*A{\mathbf{s}}^{(k-1)},-\nabla f({\mathbf{x}}^{(k)})*}{*A{\mathbf{s}}^{(k-1)},{\mathbf{s}}^{(k-1)}*}$$ When the objective function is strictly convex , From the conjugate gradient method , Less than $n$ The global optimal solution can be found in the next iteration .
  For nonlinear problems , There are some calculation coefficients ${\beta }^{(k)}$ The formula is proposed , In this paper, the author uses the coefficient calculation formula as follows ：$${\beta }_{HS}^{(k)}=\frac{*\nabla f({\mathbf{x}}^{(k)},{\mathbf{y}}^{(k-1)})*}{*{\mathbf{s}}^{(k-1)},{\mathbf{y}}^{(k-1)}*}$$ among ${\mathbf{y}}^{(k-1)}=\nabla f({\mathbf{x}}^{(k-1)})-\nabla f({\mathbf{x}}^{(k)})$, And ${\beta }^{(k)}\ge 0$, You can also use $\max \{{\beta }^{(k)},0\}$ Instead of ${\beta }^{(k)}$. Proposed by the paper ACG The specific form of the algorithm is as follows ：$$\begin{array}{rl}{\mathbf{y}}^{(k-1)}& =\nabla f({\mathbf{x}}^{(k-1)})-\nabla f({\mathbf{x}}^{(k)})\\ {\beta }_{HS}^{(k)}& =\frac{*-\nabla f({\mathbf{x}}^{(k)}),{\mathbf{y}}^{(k-1)}*}{*{\mathbf{s}}^{(k-1)},{\mathbf{y}}^{(k-1)}*}\\ {\mathbf{s}}^{(k)}& =\nabla f({\mathbf{x}}^{(k)})+{\beta }_{HS}^{(k)}{\mathbf{s}}^{(k-1)}\\ {\mathbf{x}}^{(k+1)}& =P_{\mathcal{S}}\left({\mathbf{x}}^{(k)}+{\eta }^{(k)}\cdot \sigma ({\mathbf{s}}^{(k)})\right)\end{array}$$ The search algorithm of attack step size is as follows ：
$$\begin{array}{rl}(\mathrm{I})& N_{\mathrm{inc}}<\rho \cdot (w_j-w_{j-1})\\ (\mathrm{II})& {\eta }^{(w_j-1)}={\eta }^{(w_j)}\mathrm{and}{f}_{\max }^{(w_{j-1})}=f_{\max }^{(w_j)}\end{array}$$

• Conditions $(\mathrm{I})$ It means that the number of objective functions corresponding to the growth point is less than a certain threshold , Then the local maximum point has a high probability to occur in this interval . The details are shown in the following example ：
  
• When the function value of a discontinuity rises and falls abruptly , Then the condition is $(\mathrm{II})$ There will also be local maximum points , The specific examples are as follows ：
  
  in summary , The final algorithm flow chart is shown below ：
  

4 Paper understanding

  The automatic conjugate gradient counter attack proposed by the author of this paper is different from the original conjugate gradient method . Corresponding to nonlinear optimization problem , Given point ${\mathbf{x}}^{(k)}$ And conjugate direction ${\mathbf{s}}^{(k)}$, The original conjugate gradient method will first be at point ${\mathbf{x}}^{(k)}$ Along the direction conjugate direction ${\mathbf{s}}^{(k)}$ Search for the next iteration point that maximizes the objective function ${\mathbf{s}}^{(k+1)}$, The iteration step is ${\eta }^{(k)}$ For the problem of positive definite quadratic form , The above steps can be solved directly ; Nonlinear problems can be solved by linear search or other search algorithms . Then find the conjugate direction ${\mathbf{s}}^{(k+1)}$. In this paper , The author directly gives the iteration step size and the set of search discontinuities , Then, as the iteration progresses, the iteration discontinuity is continuously reduced to resist disturbance ${\eta }^{(k)}$ Size , Thus, the optimal anti disturbance is finally obtained . If according to the original conjugate gradient method , The algorithm flow of countering attack based on conjugate gradient method can be changed as follows ：

• step 0： Given the initial point ${\mathbf{x}}^{(0)}$, neural network $f$, The feasible region $\mathcal{S}$, Note that the initial conjugate gradient direction is ${\mathbf{s}}^{(0)}=\nabla f({\mathbf{x}}^{(0)})$
• step 1： By linear search in the conjugate direction ${\mathbf{s}}^{(k)}$ Search attack step on ${\eta }^{(k)}\in [0,1]$, bring $${\eta }^{(k)}=\arg \min \{f({\mathbf{x}}^{(k)}+{\eta }^{(k)}\cdot {\mathbf{s}}^{(k)})\}$$
• step 2： Get the second $k+1$ Step confrontation sample ${\mathbf{x}}^{k+1}$ by $${\mathbf{x}}^{(k+1)}=P_{\mathcal{S}}\left({\mathbf{x}}^{(k)}+{\eta }^{(k)}\cdot \sigma ({\mathbf{s}}^{(k)})\right)$$
• step 3: Make $k=k+1$, And go to the step 1 In the middle .

5 experimental result

  The following table shows the paper method ACG And other gradient based methods APGD stay CIFAR10 Attack success rate of data set . You can intuitively find ,ACG The attack success rate of is higher than APGD Attack success rate of . These results suggest that , Regardless of the data set or the architecture of the model used ,ACG Both show higher attack performance . Besides ,ACG The method does not rely on random numbers to select the initial point , Because the initial point is the center of the feasible region , Thus we can see that ,ACG Only in deterministic operation, it is better than APGD.

  The image below shows APGD and ACG Between the last two consecutive search points 2 The transformation of norms . Can be observed ACG Search point ratio APGD Our search points move further . Besides , To study projection pairs APGD Influence , The author also calculates the ratio of travel distance between two search points , It represents the amount of update distance wasted by projection . And ACG comparison ,APGD It shows a higher projection ratio in the travel distance . Due to the introduction of conjugate direction ,ACG Than APGD Move more .

  The following figure is a visual example of conjugate gradient attack search for multimodal functions . The initial search point is represented by a white star , The search ends with a white square . Circles represent search points . Black circles indicate search diversification , White circles indicate search intensity . In the left “A” To “F” Indicates local optimum ,“E” Represents the global optimum . The examples on the left and in the middle are failed searches that cannot find the global optimal value due to the lack of diversification or intensification . The example on the right shows the search that successfully finds the global optimal value due to the appropriate balance between diversification and intensification . The following figure shows enhanced search 、 Visualization of diversified search and appropriate search , Demonstrates the appropriate balance between diversification and reinforcement . Six local solutions can be observed from the contour of the function in the figure , among “E” The local solution of the position is the global optimal solution .

6 Core code example

  The algorithm source code is provided in the paper , The code is a little complicated , The following code is a relatively simple core code rewritten according to the core algorithm of the paper .

class ACG_attack(object):
	# Input_x shape : R^n
	def __init__(self, input_x, input_y, model, N_iter, W_set, eta):
		self.input_x = input_x
		self.input_y = input_y
		self.model = model
		self.eta = eta
		self.N_iter = N_iter
		self.W_set = W_set
		self.rho = rho

	def judgement(self, k, x_new, x_old, eta_list, loss_list):
		flag = False
		CE = nn.CrossEntropyLoss()
		count = 0 
		j = self.W_set.index(k)
		for i in range(self.W_set[j-1], k-1):
			y_new = self.model(x_new)
			y_old = self.model(x_old)
			if CE(y_new, self.input_y) > CE(y_old, self.input_y):
				count += 1
		if count < self.rho * (k - self.W_set[j-1]):
			flag = True
		if eta_list[k] == eta_list[self.W_set[j-1]] and loss_list[k] == loss_list[self.W_set[j-1]]:
			flag = True
		return flag

	def attack(self):
		eta_list = []
		loss_list = []
		nabla_list = []
		s_list = []
		input_shape = self.input_x.shape
		self.input_x.requires_grad = True
		CE = nn.CrossEntropyLoss()
		x_adv = self.input_x.view(-1)
		x_pre = self.input_x.view(-1)
		x_adv.requires_grad = True
		x_pre.requires_grad = True
		beta = 0
		eta_old = self.eta
		# Compute the graident of f w.r.t x
		y = model(x_pre)
		loss = CE(y, self.input_y)
		loss.backward()
		s_0 = self.input_x.grad.detach().view(-1)
		s_pre = s_0
		# Auto conjugate gradient method
		x_old = x_pre
		s_old = s_pre
		loss_list.append(loss)
		eta_list.append(self.eta)
		nabla_list.append(s_pre)
		s_list.append(s_pre)
		for k in range(self.N_iter):
			x_new = torch.clamp( x_old + eta_pre * torch.sign(s_old) , 0, 1)
			x_new.requires_grad = True
			y_new = self.model(x_new)
			y_adv = self.model(x_adv)
			loss_new = CE(y_new, self.input_y)
			loss_old = CE(y_adv, self.input_y)
			loss_new.backward()
			loss_list.append(loss_new)
			y_list = []
			if CE(y_new, self.input_y) > CE(y_adv, self.input_y):
				x_adv = x_new
				x_pre = x_old
				s_pre = s_old
			eta_new = eta_old
			eta_list.append()
			nabla_list.append(x_new.grad.data)
			if k in self.W_set[1:]:
				if self.judgement(k, x_new, x_old, eta_list, loss_list):
					eta_new = eta_old / 2 
					eta_list[-1] = eta_new
					x_new = x_adv 
					x_old = x_pre
					s_old = s_pre
			y_list.append(nabla_list[-1].view(-1)-nabla_list[-2].view(-1))
			beta = torch.dot(-nabla_list[-1].view(-1), y_list[-1].view(-1))/(torch.dot(s_list[-1].view(-1)), y_list[-1].view(-1))
			beta_list = beta
			s_new = nabla_list[-1] + beta * s_list[-1]
			s_list.append(s_new)
	return x_adv

Summary of new words

diversified： diversify
renders： present
discriminative： Differentiated