Adversarial Attacks

We can easily fool a classify network into misclassifying an input.

Suppose we are given a dataset.

$$D=\{(x,t)|x\in X,t\in \{1,\dots ,K\}\}$$

for $X\subset \mathbb{X}$, where the class of $x$ is $t$.

Let $f:\mathbb{X}\to {\mathbb{P}}^K$ be a classifier network, where

$${\mathbb{P}}^K=\left\{y\in {\mathbb{R}}^K|0\le y_i\le 1,\sum _i{y}_i=1\right\}$$

represents probability vectors, such as those produced by a softmax function.

The classification error is defined as:

$$R(f)\equiv {\mathbb{E}}_D[1\{\underset{i}{\mathrm{argmax}}(y_i)\ne t\}|(x,t)\in D,y=f(x)]$$

where:

• $1$ counts the number of occurrences
• $\underset{i}{\mathrm{argmax}}{y}_i$ gives the index of the largest element of $y$

Let’s define the $ϵ$-ball (neighborhood) of an input $x$ as:

$$\mathbb{B}(x,ϵ)=\{x^{\prime }\in \mathbb{X}|||x^{\prime }-x||\le ϵ\}$$

We ask ourselves, given an $(x,t)\in D$, is there $x^{\prime }\in \mathbb{B}(x,ϵ)$ such that

$$\underset{i}{\mathrm{argmax}}(y_i)\ne t,y=f(x^{\prime })$$

In other words, is there a very nearby input that would fool the network and yield an incorrect classification?

These can actually be found quite easily. This is called an adversarial attack. There are two main classes of adversarial attacks:

• Whitebox: Attacker has access to the whole model, e.g., weights, activations, etc.
• Blackbox: Attacker only has access to inputs and outputs

Gradient-Based Whitebox Attack

This is a common whitebox attack method. Recall that learning is done by gradient descent:

$$\theta =\theta -\kappa {\nabla }_{\theta }E$$

where $E$ is our loss function. Using backpropagation, we propagate the gradient of the cost function down through the layers of the network:

We can calculate ${\nabla }_{x}E$ using ${\nabla }_{z^1}E$:

$$\begin{array}{rl}{z}^1& =x{W}^0+b^1\\ {\nabla }_{x}E& ={\nabla }_{z_1}E\frac{\partial z^1}{\partial x}={\nabla }_{z^1}E\cdot (W^0{)}^T\end{array}$$

This gives us the gradient of the loss with respect to the input, telling us how to adjust out input in order to decrease (or increase) the loss.

Untargeted attack:

$$x^{\prime }=x+k{\nabla }_{x}E(f(x;\theta ),t(x))$$

This is essentially gradient ascent, pushing image in a direction to increase loss.

Targeted attack:

$$x^{\prime }=x-k{\nabla }_{x}E(f(x;\theta ),l)$$

where $l\ne t(x)$. This is gradient descent nudging the input to decrease loss for the wrong target class.

For example, a change in pixel intensity of $1$ in an 8-bit image is imperceptible to the human eye. If we want to perturb our image by $1$ for each pixel, then we let the perturbation be:

$$\Delta x=\text{sign}({\nabla }_{x}E)$$

such that $\Delta x=\pm 1$. This means that $||\Delta x|{|}_{\infty }=1$.

The more general version of this is FGSM:

Fast Gradient Sign Method

FGSM adjusts each pixel by $ϵ$, such that $\Delta x=ϵ\text{sign}({\nabla }_{x}E)$.

For example, for a 24-bit image where $(R,G,B)\in \{0,\dots ,255{\}}^3$, the perturbed image is computed as:

$$(R,G,B{)}^{\prime }=(R,G,B)\pm ϵ\text{sign}({\nabla }_{x}E)$$

which ensures that the perturbation follows $||\Delta x|{|}_{\infty }=ϵ$.

Instead of applying a fixed perturbation, one can also search for the smallest $||\Delta x||$ that causes misclassification:

$$\underset{||\Delta x||}{\min }[\underset{i}{\mathrm{argmax}}(y_i(x))\ne t(x)]$$

Intuition

Why are classification networks so easily fooled?

Consider the input space of $28\times 28$ for MNIST, such that there are $784$ total dimensions. That’s a lot of space. The classification partitions this high-dimensional space into 10 regions, one for each class.

It turns out that most points are not too far away from a decision boundary.

Learning is:

$$\underset{\theta }{\min }{\mathbb{E}}_D[L(f(x),t)]$$

Untargeted attack:

$$\underset{x^{\prime }\in \mathbb{B}(x,ϵ)}{\max }L(f(x^{\prime }),t)$$

Targeted attack:

$$\underset{x^{\prime }\in \mathbb{B}(x,ϵ)}{\min }L(f(x^{\prime }),\ell ),\ell \ne t$$