# Robust and Information-theoretically Safe Bias Classifier
against Adversarial Attacks††thanks: This work is partially supported by NSFC
grant No.11688101 and NKRDP grant No.2018YFA0306702.

Lijia Yu and Xiao-Shan Gao
Academy of Mathematics and Systems Science, Chinese Academy of Sciences,
Beijing 100190, China
University of Chinese Academy of Sciences, Beijing 100049, China
Email<EMAIL_ADDRESS>
###### Abstract

In this paper, the bias classifier is introduced, that is, the bias part of a
DNN with Relu as the activation function is used as a classifier. The work is
motivated by the fact that the bias part is a piecewise constant function with
zero gradient and hence cannot be directly attacked by gradient-based methods
to generate adversaries such as FGSM. The existence of the bias classifier is
proved an effective training method for the bias classifier is proposed. It is
proved that by adding a proper random first-degree part to the bias
classifier, an information-theoretically safe classifier against the original-
model gradient-based attack is obtained in the sense that the attack generates
a totally random direction for generating adversaries. This seems to be the
first time that the concept of information-theoretically safe classifier is
proposed. Several attack methods for the bias classifier are proposed and
numerical experiments are used to show that the bias classifier is more robust
than DNNs against these attacks in most cases.

Keywords. Robust DNN, adversarial samples, bias classifier, information-
theoretically safe, gradient-based attack.

##  1 Introduction

The deep neural network (DNN) [18] has become the most powerful machine
learning method, which has been successfully applied in computer vision,
natural language processing, game playing, protein structure prediction, and
many other fields.

One of the problems of DNN is the existence of adversaries [27], that is, it
is possible to intentionally make little modifications to an input such that
human can still recognize the input clearly, but the DNN outputs a wrong label
or even any label given by the adversary. Existence of adversarial samples
makes the DNN vulnerable in safety-critical applications. Although many
effective methods to defend adversaries were proposed [1, 4, 37], it was shown
that adversaries seem still inevitable for current DNNs [3, 23]. In this
paper, we present a new approach by using the bias part as the classifier and
show that the bias classifier is safe against adversaries in certain sense.

###  1.1 Contributions

Let ${\mathbb{I}}=[0,1]\subset{\mathbb{R}}$ and
${\mathcal{F}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ a classification DNN for
$m$ objects, using Relu as the activation function. For any
$x\in{\mathbb{I}}^{n}$, there exist $W_{x}\in{\mathbb{R}}^{m\times n}$ and
$B_{x}\in{\mathbb{R}}^{m}$ such that

${\mathcal{F}}(x)=W_{x}x+B_{x}$

where $W_{x}x$ is called the first-degree part and $B_{x}$ the bias part of
${\mathcal{F}}$. From the definition of the Relu function, the bias part

$B_{\mathcal{F}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$

defined as $B_{\mathcal{F}}(x)=B_{x}$ is a piecewise constant function with a
finite number of values.

The most popular and effective methods to generate adversaries, such as FGSM
[11] or PGD [20], use $\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ to make the
loss function bigger. An attack on DNNs only using the values of
${\mathcal{F}}(x)$ and $\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ is called a
gradient-based attack. Since $n$ is generally quite large, using
$\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ to find adversaries in the high-
dimensional space ${\mathbb{R}}^{n}$ seems inevitable.

Motivated by the above observation, the bias classifier is introduced in this
paper, that is, the bias part
$B_{\mathcal{F}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ of ${\mathcal{F}}$ is
used to classify the $m$ objects. Since $B_{\mathcal{F}}$ is a piecewise
constant function, it has zero gradient and is safe against direct gradient-
based attacks. The contributions of this paper are summarized below.

First, the existence of the bias classifier is proved. Precisely, it is proved
that for any classification problem, there exists a DNN ${\mathcal{F}}$ such
that its bias part $B_{\mathcal{F}}$ gives the correct label for the
classification problem with arbitrarily high probability.

Second, an effective training method for the bias classifier is proposed. It
is observed that the adversarial training method introduced in [20]
significantly increases the classification power of the bias part.
Furthermore, using the adversarial training method to the loss function
$L_{{\hbox{\scriptsize\rm{CE}}}}(B_{{\mathcal{F}}}(x),y)+\gamma
L_{{\hbox{\scriptsize\rm{CE}}}}({\mathcal{F}}(x),y)$ increases the
classification power of the bias part and decreases the classification power
of first-degree part of ${\mathcal{F}}$, and hence is used to train the bias
classifier.

Third, an information-theoretically safe bias classifier is given. The notion
of information-theoretically safe, also called perfectly safe, is borrowed
from cryptography [9, p.476], which means that the ciphertext yields no
information regarding the plaintext for cyphers which are perfectly random.
Let $W_{R}\in{\mathbb{R}}^{m\times n}$ be a random matrix satisfying certain
distributions, ${\mathcal{F}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ a trained
bias classifier, and $\widetilde{{\mathcal{F}}}(x)={\mathcal{F}}(x)+W_{R}x$.
Then, it is shown that $B_{\widetilde{{\mathcal{F}}}}$ is information-
theoretically safe against certain gradient-based attacks of
$\widetilde{{\mathcal{F}}}$, if the structure and parameters of
${\mathcal{F}}$ are kept secret. A network ${\mathcal{F}}$ is called
information-theoretically safe against an attack ${\mathcal{A}}$, if when
generating adversaries for an image $x$, the attack ${\mathcal{A}}$ gives a
random direction to generate adversaries, or equivalently, the adversary
creation rate of ${\mathcal{F}}$ under the attack ${\mathcal{A}}$ is equal to
the rate of certain random samples to be adversaries.

Fourth, several methods to attack the bias classifier are proposed.
Experiments with MNIST and CIFAR-10 data sets show that the bias classifier is
more robust than DNNs against these adversarial attacks in most cases.

###  1.2 Related work

There exist two main approaches to obtain more robust DNNs: using a better
training method or a better structure for the DNN. Of course, the two
approaches can be combined.

Many effective methods were proposed to train more robust DNNs to defend
adversaries [1, 4, 37, 33]. The adversarial training method proposed by Madry
et al [20] can reduce the adversaries significantly, where the value of the
loss function of the worst adversary in a small neighborhood of the training
sample is minimized. A similar approach is to generate adversaries and add
them to the training set [11]. A fast adversarial training algorithm was
proposed, which improves the training efficiency by reusing the backward pass
calculations [24]. A less direct approach to resist adversaries is to make the
DNN more stable by introducing the Lipschitz constant or $L_{p,\infty}$
regulations of each layer [5, 27, 35, 34]. Adding noises to the training data
is an effective way to increase the robustness [10, Sec.7.5]. Knowledge
distilling is also used to enhance robustness and defend adversarial examples
[15].

In this paper, the adversarial training method [20] is used to a new loss
function to train the bias classifier.

Many effective new structures for DNNs were proposed to defend adversaries [1,
4, 37, 33]. The ensembler adversarial training [28] was introduced for CNN
models, which can apply to large datasets such as ImageNet. In [32], a
denoising layer is added to each hidden layer to defend adversarial attack. In
[16], differential privacy noise layers are added to defend adversaries. In
[22], a low-rank DNN is shown to be more robust. In [36], a classification-
autoencoder was proposed, which is robust against outliers and adversaries. In
[6], it was observed that by taking average values of points in a small
neighbourhood of an input can give a larger robust region for the input. In
[12, 31], strategies to defend adversarial attacks by modifying the input were
given.

In this paper, a new idea to obtain robust DNNs is given, that is, the bias
part is used as the classifier to avoid gradient-based attacks. Another
advantage of using the bias part as the classifier is that, an information-
theoretically safe classifier can be constructed. The bias classifier does not
deliberately hide the gradient like the method in [2], so the white box attack
method for the gradient hiding method in [2] does not work for it.

The rest of this paper is organized as follows. In section 2, the existence of
the bias classifier is proved and the training method is given. In section 3,
several attack methods for the bias classifier are given. In section 4, the
bias classifier is shown to be information-theoretically safe against the
original-model gradient-based attack. In section 5, numerical experimental
results are given to show that the bias classifier indeed improves robustness
to resist adversaries. In section 6, conclusions are given

##  2 Classification using the bias part of DNN

In this section, we prove the existence of a DNN ${\mathcal{F}}$ such that the
bias part of ${\mathcal{F}}$ can be used as a classifier. We also give the
training algorithm for the new classifier.

###  2.1 The standard DNN

Denote ${\mathbb{I}}=[0,1]\subset{\mathbb{R}}$ and $[n]=\\{1,\ldots,n\\}$ for
$n\in{\mathbb{N}}_{>0}$. In this paper, we assume that
${\mathcal{F}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ is a classification DNN
for $m$ objects, which has $L$ hidden-layer, each hidden-layer has $n$ nodes
and uses Relu as activity functions, and the output layer does not have
activity functions. We write ${\mathcal{F}}$ as:

$\begin{array}[]{ll}x_{l}={\hbox{\rm{Relu}}}(W_{l}x_{l-1}+b_{l})\in{\mathbb{R}}^{n_{l}},W_{l}\in{\mathbb{R}}^{n_{l}\times
n_{l-1}},b_{l}\in{\mathbb{R}}^{n_{l}},l\in[L];\\\
{\mathcal{F}}(x_{0})=x_{L+1}=W_{L+1}x_{L}+b_{L+1},W_{L+1}\in{\mathbb{R}}^{m\times
n},b_{L+1}\in{\mathbb{R}}^{m}\\\ \end{array}$ (1)

where $x_{0}\in{\mathbb{I}}^{n},n_{0}=n,n_{L+1}=m$. Denote
$\Theta_{\mathcal{F}}=\\{W_{l},b_{l}\\}_{l=1}^{L+1}$ to be the parameter set
of ${\mathcal{F}}$. Given a training set ${\mathcal{S}}$, the network
${\mathcal{F}}$ can be trained as follows

$\min_{\Theta}\sum_{(x,y)\in{\mathcal{S}}}L_{{\hbox{\scriptsize\rm{CE}}}}({\mathcal{F}}(x),y).$
(2)

For any $x\in{\mathbb{I}}^{n}$, there exist $W_{x}\in{\mathbb{R}}^{m\times n}$
and $B_{x}\in{\mathbb{R}}^{m}$, such that ${\mathcal{F}}(x)=W_{x}x+B_{x}$. We
define the first-degree part of ${\mathcal{F}}$ to be
$W_{{\mathcal{F}}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$, that is
$W_{{\mathcal{F}}}(x)=W_{x}x$; and the bias part of ${\mathcal{F}}$ to be
$B_{{\mathcal{F}}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$, that is
$B_{{\mathcal{F}}}(x)=B_{x}$. It is easy to see that

${\mathcal{F}}(x)=W_{{\mathcal{F}}}(x)+B_{{\mathcal{F}}}(x)=W_{x}x+B_{x}.$ (3)

For a label $y\in[m]$ and $x\in{\mathbb{I}}^{n}$, denote
${\mathcal{F}}_{y}(x)$ to be the $y$-th coordinate of ${\mathcal{F}}(x)$.

A linear region of ${\mathcal{F}}$ is a maximal connected open subset of the
input space ${\mathbb{I}}^{n}$, on which ${\mathcal{F}}$ is linear [11]. On
each linear region $A$ of ${\mathcal{F}}$, there exist
$W_{A}\in{\mathbb{R}}^{m\times n}$ and $B_{A}\in{\mathbb{R}}^{m}$, such that
${\mathcal{F}}(x)=W_{A}x+B_{A}$ for $x\in A$. Due to the property of Relu
function, it is clear that ${\mathcal{F}}$ has a finite number of disjoint
linear regions and ${\mathbb{I}}^{n}$ is the union of the closures of these
linear regions.

###  2.2 Existence of bias classifier

In this section, we will prove that the bias part $B_{{\mathcal{F}}}$ of
${\mathcal{F}}$ can be used as a classifier. Let
${\mathbb{O}}\subset{\mathbb{I}}^{n}$ be the objects to be classified. For
$x\in{\mathbb{O}}$ and $r\in{\mathbb{R}}_{>0}$, when $r$ is small enough, all
images in

${\mathbb{B}}(x,r)=\\{x+\eta\,|\,\eta\in{\mathbb{R}}^{n},||\eta||<r\\}$

can be considered to have the same label with $x$. Therefore, the object
${\mathbb{O}}$ to be classified may be considered as bounded open sets in
${\mathbb{I}}^{n}$. This observation motivates the following existence
theorem, whose proof will be given in this section. For
$D\subset{\mathbb{R}}^{n}$, denote $V(D)$ to be the volume of $D$.

######  Theorem 2.1.

Let ${\mathbb{O}}=\bigcup_{i=1}^{m}O_{i}$ be the elements to be classified and
${\mathbb{L}}=\\{l\\}_{l=1}^{m}$ the label set, where
$O_{i}\subset{\mathbb{I}}^{n}$ is an open set, $O_{i}\bigcap O_{j}=\phi$ if
$i\neq j$, and $x$ has label $l$ for $x\in O_{l}$. Then for any $\epsilon>0$,
there exist a DNN ${\mathcal{F}}$ and a $D\subset{\mathbb{I}}^{n}$ with
$V(D)<\epsilon$, such that $B_{{\mathcal{F}}}(x)$ gives the correct label for
$x\in O\setminus D$, that is, the $l$-th coordinate of $B_{{\mathcal{F}}}(x)$
has the largest value among all coordinates of $B_{{\mathcal{F}}}(x)$ for
$x\in O_{l}\setminus D$.

A network satisfying the conditions of Theorem 2.1 gives a bias classifier,
which can be computed from ${\mathcal{F}}$ as follows since
$W_{{\mathcal{F}}}(x)=\frac{\nabla{\mathcal{F}}(x)}{\nabla x}\cdot x$, we have

$B_{{\mathcal{F}}}(x)={\mathcal{F}}(x)-W_{{\mathcal{F}}}(x)={\mathcal{F}}(x)-\frac{\nabla{\mathcal{F}}(x)}{\nabla
x}\cdot x.$ (4)

We first prove several lemmas. In this section, the notations
${\mathbb{O}},O_{l},{\mathbb{L}}$ introduced in Theorem 2.1 will be used
without mention. We will use another activation function
$\Gamma:{\mathbb{R}}\rightarrow{\mathbb{R}}$

$\Gamma(x)=\left\\{\begin{array}[]{lll}0&\hbox{ if }&x\leq 0\\\ 1&\hbox{ if
}&x>0\\\ \end{array}\right..$

######  Lemma 2.1 (Theorem 5 in [7]).

Let $l\in{\mathbb{L}}$ and $F_{l}:{\mathbb{R}}\to{\mathbb{R}}$ be a function
such that $F_{l}(x)=1$ if $x\in O_{l}$ and $F_{l}(x)=-1$ otherwise. Then for
any $\epsilon>0$, there exist $N\in{\mathbb{N}}_{>0}$,
$W\in{\mathbb{R}}^{N\times n}$, $b\in{\mathbb{R}}^{N\times 1}$,
$U\in{\mathbb{R}}^{1\times N}$, and $D\in{\mathbb{I}}^{n}$ with
$V(D)<\epsilon$, such that $|G(x)-F_{l}(x)|<\epsilon$ for
$x\in{\mathbb{O}}\setminus D$, where $G(x)=U\cdot\Gamma(Wx+b)$.

The following lemma shows that there exists a DNN with one hidden layer and
using $\Gamma$ as the activation function, which can be used as a classifier
for ${\mathbb{O}}$.

######  Lemma 2.2.

For any $\epsilon>0$, there exist $N\in{\mathbb{N}}_{>0}$,
$W\in{\mathbb{R}}^{N\times n}$, $b\in{\mathbb{R}}^{N\times 1}$,
$U\in{\mathbb{R}}^{1\times N}$, and $D\in{\mathbb{I}}^{n}$ with
$V(D)<\epsilon$, such that

$G(x)=U\cdot\Gamma(Wx+b):{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$

gives the correct label for $x\in{\mathbb{O}}\setminus D$, that is, the $l$-th
coordinate of $G(x)$ has the biggest value for $x\in O_{l}$.

###### Proof.

By Lemma 2.1, for $l\in{\mathbb{L}}=[m]$, there exist
$N_{a}\in{\mathbb{N}}_{>0}$, $W_{l}\in{\mathbb{R}}^{(N_{l},n)}$,
$b_{l}\in{\mathbb{R}}^{(N_{l},1)}$, $U_{l}\in{\mathbb{R}}^{(1,N_{l})}$, and
$D_{l}\in{\mathbb{I}}^{n}$ with $m(D_{l})<\epsilon/n$ such that

$G_{l}(x)=U_{l}\cdot\Gamma(W_{l}x+b_{l})\hbox{ and
}|G_{l}(x)-F_{l}(x)|<\epsilon/n$

for $x\in{\mathbb{O}}\setminus D$, where $F_{l}$ is defined in lemma 2.1. Let
$N=N_{a}m$, $W\in{\mathbb{R}}^{(N,n)}$, $b\in{\mathbb{R}}^{(N,1)}$, where the
$l$-th row of $W$ is the $l_{2}$-th row of $W^{l_{1}}$, the $l$-th row of $b$
is the $l_{2}$-th row of $b^{l_{1}}$, for $l=l_{1}N_{w}+l_{2}$, $1\leq
l_{2}\leq N_{w}$, and $l_{1}\in[m]$.

Let $V\in{\mathbb{R}}^{(m,N)}$ be formed as follows: for $j\in[m]$, the $j$-th
row of $U_{1}$ are zeros except the $j(N_{w}-1)+1$-th to the
$j(N_{w}-1)+N_{w}$-th rows, and the values of the $(j(N_{w}-1)+k)$-th place of
the $j$-th row of $U_{1}$ equal to the values of the $k$-th place of $U_{l}$,
where $k\in[N_{a}]$.

Now for $N\in{\mathbb{N}}_{>0}$, $W\in{\mathbb{R}}^{(N,n)}$,
$b\in{\mathbb{R}}^{(N,1)}$, $U\in{\mathbb{R}}^{(m,N)}$,

$G(x)=U\cdot\Gamma(Wx+b)$

satisfies $G(x)_{l}$=$G_{l}(x)$, where $G(x)_{l}$ is the $l$-th coordinate of
$G(x)$. So there exist a set $D=\bigcup D_{l}\in{\mathbb{I}}^{n}$ with
$m(D)<\epsilon$, such that $G(x)_{y}>1-\epsilon$ and $G(x)_{l}<-1+\epsilon$
for $l\neq l_{x}$, where $l_{x}$ is the label of $x$. Hence, $G(x)$ gives the
correct label for $x\in{\mathbb{O}}\setminus D$. ∎

######  Lemma 2.3.

The bias vector $b$ in Lemma 2.2 can be chosen to consist of nonzero values.

###### Proof.

By Lemma 2.2, there exist $N$, $W$, $b$, $U$, and $D_{1}\in{\mathbb{I}}^{n}$
with $V(D_{1})<\epsilon/2$, such that

$G(x)=U\Gamma(Wx+b)$

gives the correct label for $x\in{\mathbb{O}}\setminus D_{1}$. Now assume
$b_{\gamma}=b+I_{0}(b)\gamma$, where $I_{0}(x)=1-{\hbox{\rm{sign}}}(|x|)$ and
when $I_{0}$ is is used as function of a matrix or a vector, it acts on each
entry of this matrix or vector. We know that $b_{\gamma}$ does not have zero
parameters. Moreover, if $\Gamma(Wx+b)\neq\Gamma(Wx+b_{\gamma})$, then there
exists an $i\in[N]$ such that $W^{i}x+b^{i}>0$ and $W^{i}x+b_{\gamma}^{i}<0$
or $W^{i}x+b^{i}<0$ and $W^{i}x+b_{\gamma}^{i}>0$, where $W^{i}$ is the $i$-th
row of $W$, $b^{i}$ and $b_{\gamma}^{i}$ are respectively the $i$-th row of
$b$ and $b_{\gamma}$. Note that
$||W^{i}x+b_{\gamma}^{i}-W^{i}x+b^{i}||_{2}\leq\gamma$ when $x\in I_{n}$. If
$W^{i}z+b^{i}>0$ and $W^{i}z+b_{\gamma}^{i}<0$ or $W^{i}z+b^{i}<0$ and
$W^{i}z+b_{\gamma}^{i}>0$ for $z\in{\mathbb{R}}^{n}$, then we have
$|W^{i}z+b^{i}|<\gamma$. Assume $Z_{i}=\\{z||W^{i}z+b^{i}|<\gamma\\}$. We have
$m(Z_{I}\bigcap I_{0})<2\gamma C_{n}$. The volume of the intersection of any
hyperplane $C\in{\mathbb{R}}^{n}$ with ${\mathbb{I}}_{n}$ must have an upper
bound, which is denoted as $C_{n}$.

Let $Z=\\{z|\Gamma(Wx+b)\neq\Gamma(Wx+b_{\gamma})\\}$. Then we have
$m(Z\bigcap I_{n})<2\gamma NC_{n}$. Now let $\gamma=\frac{\epsilon}{4NC_{n}}$.
Then there exists a $D=D_{1}\bigcup(Z\bigcap I_{n})$ such that $D_{1}\in D\in
I_{n}$ and $m(D)<m(D_{1})+2\gamma NC_{n}<\epsilon$. Furthermore, for
$x\in{\mathbb{O}}\setminus D$, we have $\Gamma(Wx+b)=\Gamma(Wx+b_{\gamma})$.
Then it is easy to know that, there exist $N$, $W$, $b_{\gamma}$, $U$,
$D\in{\mathbb{I}}^{n}$with $m(D)<\epsilon$ such that

$G(x)=U\Gamma(Wx+b_{\gamma})$

gives the correct label for $x\in O\setminus D_{1}$, and $b_{\gamma}$ do not
have zero entries. The lemma is proved. ∎

######  Lemma 2.4.

Let ${\mathcal{F}}_{1}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ be a one-hidden-
layer DNN with activation function $\Gamma(x)$, and any coordinate of its bias
vector is nonzero. Then there exists a DNN ${\mathcal{F}}$, which has the same
structure as ${\mathcal{F}}_{1}$, except that the activation function of
${\mathcal{F}}$ is Relu, such that $B_{{\mathcal{F}}}(x)={\mathcal{F}}_{1}(x)$
for all $x\in{\mathbb{I}}^{n}$.

###### Proof.

Assume ${\mathcal{F}}_{1}(x)=U\Gamma(Wx+b)+c$. Let
${\mathcal{F}}(x)=W^{{\mathcal{F}}_{1}}{\hbox{\rm{Relu}}}(W^{\mathcal{F}}x+b^{\mathcal{F}})+c$,
where $W^{{\mathcal{F}}_{1}}=W^{1}{\hbox{\rm{diag}}}(\frac{b_{i}}{|b_{i}|})$,
$W^{\mathcal{F}}={\hbox{\rm{diag}}}(|b_{i}|^{-1})W$, and
$b^{\mathcal{F}}=b/|b|$ (position-wise division). Then ${\mathcal{F}}$
satisfies the condition of the lemma. ∎

We now prove Theorem 2.1.

Proof of Theorem 2.1. Because of Lemma 2.2, there exist a
$D\in{\mathbb{I}}^{n}$ with $m(D)<\epsilon$ and a network $G$ with one-hidden-
layer and with activation function $\Gamma(x)$, such that $G(x)$ gives the
correct label for $x\in{\mathbb{O}}\setminus D$. By Lemma 2.3, all the
parameters of $G$ are no zero. Then by Lemma 2.4, we can obtain a network
${\mathcal{F}}$ such that $B_{{\mathcal{F}}}=G(x)$, and the theorem is
proved.∎

###  2.3 Training the bias classifier

In order to increase the robustness of the network, we will use the
adversarial training introduced in [20], which is the best practical training
method to defend adversaries. Let $(x,y)$ be a data in the training set
${\mathcal{S}}$. Then the adversarial training uses the following loss
function for a given small $\varepsilon\in{\mathbb{R}}_{>0}$

$\min_{\Theta}\max_{||\zeta||<\varepsilon}\sum_{(x,y)\in{\mathcal{S}}}L_{{\hbox{\scriptsize\rm{CE}}}}({\mathcal{F}}(x+\zeta),y).$
(5)

In order to increase the power of the bias part $B_{\mathcal{F}}$, we use the
following loss function

$\min_{\Theta}\max_{||\zeta||<\varepsilon}\sum_{(x,y)\in{\mathcal{S}}}[L_{{\hbox{\scriptsize\rm{CE}}}}(B_{{\mathcal{F}}}(x+\zeta),y)+\gamma
L_{{\hbox{\scriptsize\rm{CE}}}}({\mathcal{F}}(x+\zeta),y)]$ (6)

where $\gamma$ is a super parameter. The training procedure is given in
Algorithm 1.

We first use numerical experiments to show that the adversarial training can
increase the classification power of $B_{\mathcal{F}}$. The accuracies of
${\mathcal{F}}$, $W_{{\mathcal{F}}}$, $B_{{\mathcal{F}}}$ on the test set for
three kinds of training methods are given in Table 1, respectively.

| $W_{{\mathcal{F}}}$ | $B_{{\mathcal{F}}}$ | ${\mathcal{F}}$
---|---|---|---
Normal training (2) | 98.80$\%$ | $15.62\%$ | 99.09$\%$
Adversarial training (5) | 90.61$\%$ | $98.77\%$ | 99.19$\%$
Adversarial training (6) | 0.28$\%$ | 99.09 $\%$ | 99.43$\%$
Table 1: Accuracies of network Lenet-5 for MNIST Algorithm 1 HTrain-1

0: The set of training data: ${\mathcal{S}}=\\{(x_{i},y_{i})\\}$;The initial
value of the parameter set $\Theta$: $\Theta_{0}$;The super parameter:
$M_{s},M_{b},M_{n}$.

0: The trained parameters $\widetilde{\Theta}$. In each iteration:Input
$\Theta_{k}$Let
$L(x,y,\Theta)=L_{{\hbox{\scriptsize\rm{CE}}}}(B_{{\mathcal{F}}_{\Theta}}(x),y)$.Let
$L_{1}(x,y,\Theta)=L_{{\hbox{\scriptsize\rm{CE}}}}({\mathcal{F}}_{\Theta}(x),y)$.For
$(x,y)\in{\mathcal{S}}$, do i=0, $x_{0}=x$ While $i<M_{s}$:
$x_{i+1}=x_{i}-M_{b}\frac{\partial L(x_{i},y,\Theta_{k})}{\partial x_{i}}$
$i=i+1$ $x=x_{i+1}$Let
$L(\Theta_{k})=\frac{1}{|{\mathcal{S}}|}\sum_{x,y\in{\mathcal{S}}}L(x,y,\Theta_{k})$.Let
$L_{1}(\Theta_{k})=\frac{1}{|{\mathcal{S}}|}\sum_{x,y\in{\mathcal{S}}}L_{1}(x,y,\Theta_{k})$.Let
$\bigtriangledown
L=\frac{\partial(L(\Theta_{k})+M_{n}L_{1}(\Theta_{k}))}{\partial\Theta_{k}}$.Output
$\Theta_{k+1}=\Theta_{k}+\gamma_{k}\bigtriangledown L$; $\gamma_{k}$ is the
stepsize at iteration k.

##  3 Attack methods for the bias classifier

In this section, several possible methods to attack the bias classifier are
given.

###  3.1 Safety against gradient-based attack

The most popular methods to generate adversaries, such as FGSM [11] or PGD
[20], use $\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ to make the loss function
bigger. More precisely, adversaries are generated as follows

$x\to
x+\varepsilon{\hbox{\rm{sign}}}(\frac{\nabla{\hbox{\rm{Loss}}}_{\mathcal{F}}(x)}{\nabla
x})$ (7)

for a small parameter $\lambda\in{\mathbb{R}}_{>0}$. It is easy to see that,
$\frac{\nabla{\hbox{\rm{Loss}}}_{\mathcal{F}}(x)}{\nabla x}$ can be obtained
from $\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ for most loss functions such as
$L_{CE}$. So, in the above attack, only the values of ${\mathcal{F}}(x)$ and
$\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ are needed and the detailed
structure of ${\mathcal{F}}$ are not needed. Inspired by this, between the
black-box or white-box DNN models, we consider a model in between. A DNN model
is called a gradient-based model, if for $x\in{\mathbb{I}}^{n}$, the values of
${\mathcal{F}}(x)$ and $\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ are known,
but the detailed structure of ${\mathcal{F}}$ is not known. Correspondingly,
an attack only uses the values of ${\mathcal{F}}(x)$ and
$\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ is called gradient-based attack.

Since the derivative of $B_{\mathcal{F}}$ is always zero, a gradient-based
attack against $B_{\mathcal{F}}$ becomes a black-box attack, and in this sense
we say that the bias classifier is safe against gradient-based attack.

In the gradient-based model, we do not know the structure of ${\mathcal{F}}$,
but we can calculate $B_{{\mathcal{F}}}(x)$ from
$\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ are
$\frac{\nabla{\hbox{\rm{Loss}}}_{\mathcal{F}}(x)}{\nabla x}$ using (4).

###  3.2 Original-model attack

An obvious attack for the bias classifier is to create adversaries of
$B_{\mathcal{F}}$ using the gradients of ${\mathcal{F}}$, which is called
original-model attack. The algorithm is below, where
$\widehat{B}_{{\mathcal{F}}}(x)$ is the label of $B_{{\mathcal{F}}}(x)$.

Algorithm 2 HAttack-1.1w

0: The value of the parameter $\Theta$ of ${\mathcal{F}}$;The super
parameters: $\epsilon\in{\mathbb{R}}$, $n\in{\mathbb{N}}$;A samples $x_{0}$
and its label $y$.

0: An adversarial sample $x_{a}$.$x=x_{0}$For $i=1,\ldots,n$: If
$\widehat{B}_{{\mathcal{F}}}(x)\neq y$: Break.
$x=x+\epsilon{\hbox{\rm{sign}}}(\frac{\nabla{\mathbb{L}}_{CE}({\mathcal{F}}(x),y)}{\nabla
x})$If $\widehat{B}_{{\mathcal{F}}}(x)\neq y$, $x_{a}=x$ output:
$x_{a}$Output: No adversary for $x_{0}$

###  3.3 Correlation attack on the bias classifier

From numerical experiments, we have the following observations. For a network
${\mathcal{F}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ trained with (6) and a
small vector $\epsilon\in{\mathbb{R}}^{n}$, the following facts happen with
high probability: $W_{{\mathcal{F}}}(x)[l]\geq
W_{{\mathcal{F}}}(x^{\prime})[l]$ if and only if $B_{{\mathcal{F}}}(x)[l]\leq
B_{{\mathcal{F}}}(x^{\prime})[l]$, where $l\in{\mathbb{L}}$ and
$x^{\prime}=x+\epsilon$. In other words, $W_{{\mathcal{F}}}$ and
$B_{{\mathcal{F}}}$ are co-related and we thus can attack the
$B_{\mathcal{F}}[l]$ by increasing $W_{{\mathcal{F}}}[l]$, which is called the
correlation attack.

In the correlation attack, we create adversaries by making
$W_{{\mathcal{F}}}(x)[y]-W_{\mathcal{F}}(x)[i]$ bigger, where $y$ is the label
of $x$, $i\in[m]$ and $i\neq y$. The attack procedure is given below.

Algorithm 3 HAttack-1.1

0: The value of the parameters $\Theta$ of ${\mathcal{F}}$;The super
parameters: $\epsilon\in{\mathbb{R}}$, $N\in{\mathbb{N}}$;A samples $x_{0}$
and its label $y$.

0: An adversarial sample $x_{a}$.For $i\in{\mathbb{L}}$ and $i\neq y$:
$x=x_{0}$, j=0 While $j<N$: $W_{x,y}=\frac{\nabla{\mathcal{F}}_{y}(x)}{\nabla
x}$, $W_{x,i}=\frac{\nabla{\mathcal{F}}_{i}(x)}{\nabla x}$,
$W_{di}=W_{x,y}-W_{x,i}$ $x=x+\epsilon W_{di}$ if
$\widehat{B}_{{\mathcal{F}}}(x)\neq y$ break else: j=j+1 if $j=N$, breakIf
$\widehat{B}_{{\mathcal{F}}}(x)\neq y$, $x_{a}=x$ output: $x_{a}$Output: No
adversary for $x_{0}$

##  4 Information-theoretically safety against original-model gradient-based
attack

By the original-model gradient-based attack, we mean using the gradient of
${\mathcal{F}}$ to generate adversaries for $B_{\mathcal{F}}$. In this
section, we show that it is possible to make the bias classifier safe against
this kind of attack. The idea is to make $\frac{\nabla{\mathcal{F}}(x)}{\nabla
x}$ random and $B_{\mathcal{F}}$ still gives the correct classification.

###  4.1 Safety of direct attack

We first train a DNN ${\mathcal{F}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ with
the method in Section 2.3. Let $W_{R}\in{\mathbb{R}}^{m\times n}$ and
${\mathcal{F}}_{R}(x)=W_{R}x:{\mathbb{R}}^{n}\to{\mathbb{R}}^{m}$ be a random
linear map and

$\widetilde{{\mathcal{F}}}(x)={\mathcal{F}}(x)+{\mathcal{F}}_{R}(x)={\mathcal{F}}(x)+W_{R}x.$
(8)

Then, it is easy to see that
$B_{\widetilde{{\mathcal{F}}}}=B_{{\mathcal{F}}}$.

Let ${\mathcal{U}}(a,b)$ be the uniform distribution in
$[a,b]\subset{\mathbb{R}}$. For $\lambda\in{\mathbb{R}}_{>0}$, denote
${\mathcal{M}}_{m,n}(\lambda)$ to be the random matrices such that the
elements of its $i$-row are in
${\mathcal{U}}(-2i\lambda,-(2i-1)\lambda)\cup{\mathcal{U}}((2i-1)\lambda,2i\lambda).$
It is easy to see that for $W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)$, we have
$||W_{R,i}-W_{R,j}||_{\infty}>\lambda$ for $i\neq j$, where $W_{R,i}$ is the
$i$-th row of $W_{R}$.

For $\rho\in{\mathbb{R}}_{>0}$ consider the following gradient-based direct
attack [39] for the network ${{\mathcal{F}}}$:

$\begin{array}[]{ll}{\mathcal{A}}_{1}(x,{{\mathcal{F}}},\rho)=x+\rho\,{\hbox{\rm{sign}}}(\frac{\nabla{{\mathcal{F}}}_{\overline{y}}(x)}{\nabla
x}-\frac{\nabla{{\mathcal{F}}}_{y}(x)}{\nabla x})\\\ \end{array}$ (9)

where $y$ is the label of $x$ and $\overline{y}=\arg\max_{i\neq
y}\\{\widetilde{{\mathcal{F}}}_{i}(x)\\}$.

######  Theorem 4.1.

Let $|\frac{\nabla{\mathcal{F}}(x)}{\nabla x}|_{\infty}<\lambda/2$ and
$W_{R}\in{\mathcal{M}}_{m,n}(\lambda)$. If the structure and parameters of
${\mathcal{F}}$ are kept secret, then $B_{\widetilde{{\mathcal{F}}}}$ is
information-theoretically safe against the attack
${\mathcal{A}}_{1}(x,\widetilde{{\mathcal{F}}},\rho)$ in the sense that
attacking $B_{\widetilde{{\mathcal{F}}}}$ using
${\mathcal{A}}_{1}(x,\widetilde{{\mathcal{F}}},\rho)$ gives a random direction
$({\mathcal{A}}_{1}(x,{{\mathcal{F}}},\rho)-x)/\rho$ for generating
adversaries.

###### Proof.

From (8), $\frac{\nabla\widetilde{{\mathcal{F}}}(x)}{\nabla
x}=\frac{\nabla{\mathcal{F}}(x)}{\nabla
x}+\frac{\nabla{\mathcal{F}}_{R}(x)}{\nabla x}=W_{x}+W_{R}$. Let $W_{x,i}$ and
$W_{R,i}$ to be the $i$-rows of $W_{x}$ and $W_{R}$, respectively. If
$W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)$, then
$||W_{R,i}-W_{R,j}||_{\infty}>\lambda$ for $i\neq j$. Since
$|\frac{\nabla{\mathcal{F}}(x)}{\nabla
x}|_{\infty}=|W_{x}|_{\infty}<\lambda/2$, we have
$||W_{x,i}-W_{x,j}||_{\infty}<\lambda$ for $i\neq j$. Then from (9),

$\begin{array}[]{ll}{\mathcal{A}}_{1}(x,\widetilde{{\mathcal{F}}},\rho)&=x+\rho\,{\hbox{\rm{sign}}}(\frac{\nabla\widetilde{{\mathcal{F}}}_{\overline{y}}(x)}{\nabla
x}-\frac{\nabla\widetilde{{\mathcal{F}}}_{y}(x)}{\nabla x})\\\
&=x+\rho\,{\hbox{\rm{sign}}}(W_{x,\overline{y}}-W_{x,y}+W_{R,\overline{y}}-W_{R,y})\\\
&=x+\rho\,{\hbox{\rm{sign}}}(W_{R,\overline{y}}-W_{R,y}).\\\ \end{array}$ (10)

Then
$({\mathcal{A}}_{1}(x,{{\mathcal{F}}},\rho)-x)/\rho=W_{R,\overline{y}}-W_{R,y}$
is a random vector. ∎

The notion of information-theoretically safe, also called perfectly safe, is
borrowed from cryptography [9, p.476], which means that the ciphertext yields
no information regarding the plaintext if the cyphers are perfectly random.

In the rest of this section, we give the exact adversary creation rate of
$B_{\widetilde{{\mathcal{F}}}}$ under attack ${\mathcal{A}}_{1}$. We first
introduce some notations. Let
${\mathcal{A}}(x,{\mathcal{F}}):{\mathbb{R}}^{n}\to{\mathbb{R}}^{n}$ be an
attack which tries to create an adversary ${\mathcal{A}}(x,{\mathcal{F}})$ for
${\mathcal{F}}$. Assume that $W_{R}$ satisfies a given distribution
${\mathcal{M}}_{m,n}$ of random matrices in ${\mathbb{R}}^{m,n}$. The safety
of the original-model gradient-based attack to $B_{\widetilde{{\mathcal{F}}}}$
under attack ${\mathcal{A}}$ can be measured by the following adversary
creation rate

$\begin{array}[]{ll}{\mathcal{C}}({{\mathcal{F}}},{\mathcal{A}},{\mathcal{M}}_{m,n})={\mathbb{E}}_{W_{R}\sim{\mathcal{M}}_{m,n}}[{\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}[{\mathbf{I}}(\widehat{B}_{{{\mathcal{F}}}}({\mathcal{A}}(x,\widetilde{{\mathcal{F}}}))\neq\widehat{B}_{{{\mathcal{F}}}}(x))]]\end{array}$
(11)

where $\widehat{B}_{{\mathcal{F}}}$ is the label of the classification and
${\mathcal{D}}_{{\mathbb{O}}}$ is the distribution of the objects to be
classified.

######  Corollary 4.1.

Under the same conditions in Theorem 4.1, we have

$\begin{array}[]{ll}{\mathcal{C}}({\mathcal{F}},{\mathcal{A}}_{1},{\mathcal{M}}_{m,n})=1/2^{n}E_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}\sum_{V\in\\{-1,1\\}^{n}}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho\,V)\neq\widehat{B}_{{\mathcal{F}}}(x))].\\\
\end{array}$ (12)

###### Proof.

From (10), since $W_{R,\overline{y}}-W_{R,y}$ is a random vector whose entries
having values in two intervals of the form $[-b_{2},-b_{1}]$ and
$[b_{1},b_{2}]$ for $b_{1},b_{2}\in{\mathbb{R}}_{>0}$, we have

$\begin{array}[]{ll}{\mathcal{C}}({\mathcal{F}},\rho)&=E_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}E_{W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}({\mathcal{A}}_{1}(x,\widetilde{{\mathcal{F}}},r))\neq\widehat{B}_{{\mathcal{F}}}(x))]\\\
&=E_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}E_{W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho\,{\hbox{\rm{sign}}}(W_{R,\overline{y}}-W_{R,y}))\neq\widehat{B}_{{\mathcal{F}}}(x))]\\\
&=1/2^{n}E_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}\sum_{V\in\\{-1,1\\}^{n}}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho\,V)\neq\widehat{B}_{{\mathcal{F}}}(x))].\\\
\end{array}$

∎

Note that ${\mathcal{C}}({\mathcal{F}},{\mathcal{A}}_{1},{\mathcal{M}}_{m,n})$
depends only on ${\mathcal{F}}$ and $\rho$, so denote

${\mathcal{C}}({\mathcal{F}},\rho)=1/2^{n}E_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}\sum_{V\in\\{-1,1\\}^{n}}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho\,V)\neq\widehat{B}_{{\mathcal{F}}}(x))].$

${\mathcal{C}}({\mathcal{F}},\rho)$ can be used as a measure of the robustness
of the bias classifier, which is the adversary rate of certain random samples.
As shown in section 5.3.1, ${\mathcal{C}}({\mathcal{F}},\rho)$ is small for
most networks when $\rho$ is small.

From Corollary 4.1, we give another more precise meaning for the information-
theoretically safety: a network ${\mathcal{F}}$ is information-theoretically
safe under certain attack ${\mathcal{A}}$ if the adversary creation rate of
${\mathcal{F}}$ under attack ${\mathcal{A}}$ is equal to the rate of random
samples to be adversaries.

###  4.2 Safety of FGSM attack

In this section, we show that the result in section 4.1 also holds for the
FGSM attack if $m=2$. Here is the FGSM attack:

${\mathcal{A}}_{2}(x,{\mathcal{F}},\rho)=x+\rho\,{\hbox{\rm{sign}}}(\frac{\nabla
L({{\mathcal{F}}}(x),y)}{\nabla x}).$ (13)

######  Theorem 4.2.

If $|\frac{\nabla{\mathcal{F}}(x)}{\nabla x}|_{\infty}<\lambda/2$ and
$W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)$, then
${\mathcal{C}}(\widetilde{{\mathcal{F}}},{\mathcal{A}}_{2},{\mathcal{M}}_{m,n}(\lambda))\leq{\mathcal{C}}(\widetilde{{\mathcal{F}}},\rho)$.

###### Proof.

Let $y\in\\{0,1\\}$ be the label of $x$. Use the notations introduced in the
proof of Theorem 4.1. Since the loss function is $L_{CE}$, we have

$\begin{array}[]{ll}\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla
x}&=\frac{1}{\sum_{i=1}^{m}e^{\widetilde{{\mathcal{F}}}_{i}(x)}}(\sum_{i=1}^{m}{e^{\widetilde{{\mathcal{F}}}_{i}}}(W_{x,i}-W_{x,y}+W_{R,i}-W_{R,y}))\\\
&=\frac{e^{\widetilde{{\mathcal{F}}}_{1-y}(x)}}{\sum_{i=1}^{m}e^{\widetilde{{\mathcal{F}}}_{i}(x)}}((W_{x,1-y}-W_{x,y}+W_{R,1-y}-W_{R,y}).\\\
\end{array}$

The last equality comes from $m=2$. Since
$||W_{x,i}-W_{x,j}||_{\infty}<\lambda$ and
$||W_{R,i}-W_{R,j}||_{\infty}>\lambda$ for $i\neq j$, we have

$\begin{array}[]{ll}{\hbox{\rm{sign}}}(\frac{\nabla
L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla
x})&={\hbox{\rm{sign}}}(W_{R,1-y}-W_{R,y}).\\\ \end{array}$

Then

$\begin{array}[]{ll}{\mathcal{C}}({\mathcal{F}},\rho)&=E_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}E_{W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}({\mathcal{A}}_{2}(x,\widetilde{{\mathcal{F}}},r))\neq\widehat{B}_{{\mathcal{F}}}(x))]\\\
&=E_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}E_{W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho\,{\hbox{\rm{sign}}}(W_{R,1-y}-W_{R,y}))\neq\widehat{B}_{{\mathcal{F}}}(x))]\\\
&=1/2^{n}E_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}\sum_{V\in\\{-1,1\\}^{n}}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho\,V)\neq\widehat{B}_{{\mathcal{F}}}(x))]\\\
&={\mathcal{C}}({\mathcal{F}},\rho).\end{array}$

The theorem is proved. ∎

###  4.3 Safety of direct attack under simpler distribution

Let ${\mathcal{U}}_{m,n}(\lambda)$ be the random matrices whose entries are in
${\mathcal{U}}(-\lambda,\lambda)$. In this section, we show that the result in
section 4.1 is true for $W_{R}\in{\mathcal{U}}_{m,n}(\lambda)$. We consider
the multi-step direct attack ${\mathcal{A}}_{3}$:

$\begin{array}[]{ll}x^{(0)}=x\\\
x^{(i)}=x^{(i-1)}+\frac{\rho}{k}\,{\hbox{\rm{sign}}}(\frac{\nabla{\mathcal{F}}_{\overline{y}}(x^{(i-1)})}{\nabla
x^{(i-1)}}-\frac{\nabla{\mathcal{F}}_{y}(x^{(i-1)})}{\nabla
x^{(i-1)}}),i\in[k]\\\ {\mathcal{A}}_{3}(x,{\mathcal{F}},\rho)=x^{(k)}\\\
\end{array}$ (14)

where $y$ is the label of $x$, $k\in{\mathbb{N}}_{>0}$ is a constant, and
$\overline{y}=\arg\max_{i\neq y}\\{{\mathcal{F}}_{i}(x)\\}$.

######  Theorem 4.3.

If $|\frac{\nabla{\mathcal{F}}(x)}{\nabla x}|_{\infty}<\mu/2$ and
$W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)$, then
${\mathcal{C}}(\widetilde{{\mathcal{F}}},{\mathcal{A}}_{3},{\mathcal{U}}_{m,n}(\lambda))\leq{\mathcal{C}}({\mathcal{F}},\rho)+\mu
a/\lambda$. If $\lambda>n\mu/\epsilon$, then
${\mathcal{C}}(\widetilde{{\mathcal{F}}},{\mathcal{A}}_{3},{\mathcal{U}}_{m,n}(\lambda))\leq{\mathcal{C}}({\mathcal{F}},\rho)+\epsilon$
for any $\epsilon\in{\mathbb{R}}_{>0}$, and in particular, if
$\lambda>na/(\epsilon{\mathcal{C}}({\mathcal{F}},\rho))$, then
${\mathcal{C}}(\widetilde{{\mathcal{F}}},{\mathcal{A}}_{3},{\mathcal{U}}_{m,n}(\lambda))\leq(1+\epsilon){\mathcal{C}}({\mathcal{F}},\rho)$.

The theorem implies that $\widetilde{{\mathcal{F}}}$ is close to information-
theoretically safe. We first prove a lemma.

######  Lemma 4.1.

Let $x_{1},x_{2}\sim U(-\lambda,\lambda)$ and $z=x_{1}-x_{2}$. Then for
$a\in[0,2\lambda]$, we have
$P(z<a)=P(z>-a)=T(\lambda,a)=1-\frac{(2\lambda-a)^{2}}{8\lambda^{2}}$.

###### Proof.

Let $f(z)$ be the density function of $z$. Then $f(z)=0$, if $z\geq 2\lambda$
or $z\leq-2\lambda$; $f(z)=\frac{2\lambda+x}{4\lambda^{2}}$, if $0\geq
z\geq-2\lambda$; $f(z)=\frac{2\lambda-x}{4\lambda^{2}}$, if $0\leq z\leq
2\lambda$. Hence, $P(z<a)=P(z>-a)=1-\frac{(2\lambda-a)^{2}}{8\lambda^{2}}$. ∎

Note that $T(\lambda,a)$ increases with $a$ and $T(\lambda,a)\in[0.5,1]$.

We give the proof of Theorem 4.2.

###### Proof.

Similar to (10), we have

$\begin{array}[]{ll}{\mathcal{A}}_{3}(x,\widetilde{{\mathcal{F}}},\rho)&=x+\frac{\rho}{k}\sum_{i=1}^{k}{\hbox{\rm{sign}}}(W_{x^{(i-1)},\overline{y}}-W_{x^{(i-1)},y}+W_{R,\overline{y}}-W_{R,y})\\\
&=x+\rho\sum_{i=1}^{k}{\hbox{\rm{sign}}}(W_{R,\overline{y}}-W_{R,y})\hbox{ if
}||W_{R,\overline{y}}-W_{R,y}||_{\infty}>\mu.\\\ \end{array}$

So by Lemma 4.1,

$\begin{array}[]{ll}{\mathcal{C}}(\widetilde{{\mathcal{F}}},{\mathcal{A}}_{3},{\mathcal{U}}_{m,n}(\lambda))\\\
=E_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}E_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}({\mathcal{A}}_{2}(x,\widetilde{{\mathcal{F}}},\rho))\neq\widehat{B}_{{\mathcal{F}}}(x))]\\\
\leq
E_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}E_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}[P(||W_{R,\overline{y}}-W_{R,y}||_{\infty}\leq\mu)+P(||W_{R,\overline{y}}-W_{R,y}||_{\infty}>\mu)[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}({\mathcal{A}}_{2}(x,\widetilde{{\mathcal{F}}}))\neq\widehat{B}_{{\mathcal{F}}}(x))]\\\
\leq(1-2^{n}(1-T(\lambda,\mu))^{n})+2^{n}(1-T(\lambda,\mu))^{n}E_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}\sum_{V\in\\{-1,1\\}^{n}}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho(W_{R,\overline{y}}-W_{R,y}))\neq\widehat{B}_{{\mathcal{F}}}(x))]\\\
\leq(1-2^{n}(1-T(\lambda,\mu))^{n})+2^{n}(1-T(\lambda,\mu))^{n}{\mathcal{C}}(\rho)\\\
=1-(1-{\mathcal{C}}(\rho))2^{n}(1-T(\lambda,\mu))^{n}\end{array}$

where $T(\lambda,\mu)=1-\frac{(2\lambda-\mu)^{2}}{8\lambda^{2}}$. We have
$2^{n}(1-T(\lambda,\mu))^{n}=(2-2+\frac{4\lambda^{2}+\mu^{2}-4\lambda\mu}{4\lambda^{2}})^{n}=(1-\frac{4\lambda\mu-\mu^{2}}{4\lambda^{2}})^{n}\geq
1-n\frac{4\lambda\mu-\mu^{2}}{4\lambda^{2}}\geq 1-n\mu/\lambda.$ So,

$\begin{array}[]{ll}{\mathcal{C}}_{{\mathcal{A}}_{2}}(\widetilde{{\mathcal{F}}})\\\
\leq 1-(1-{\mathcal{C}}(\rho))2^{n}(1-T(\lambda,\mu))^{n}\\\ \leq
1-(1-{\mathcal{C}}(\rho))(1-n\mu/\lambda)\\\
\leq{\mathcal{C}}(\rho)+n\mu/\lambda.\\\ \end{array}$

The theorem is proved. ∎

###  4.4 Safety of FGSM under simpler distribution

In this section, show that the result in section 4.2 is true for the simpler
distribution ${\mathcal{U}}_{m,n}(\lambda)$. Let ${\mathcal{A}}_{2}$ be the
attack in (13). Then we have

######  Theorem 4.4.

If $|\frac{\nabla{\mathcal{F}}(x)}{\nabla x}|_{\infty}<\mu/2$,
$W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)$, and $m=2$, then
${\mathcal{C}}(\widetilde{{\mathcal{F}}},{\mathcal{A}}_{2},{\mathcal{U}}_{m,n}(\lambda))\leq
e^{n\mu/\lambda}{\mathcal{C}}({\mathcal{F}},\rho)$. Furthermore if
$\lambda>n\mu/\ln(1+\epsilon)$, then
${\mathcal{C}}(\widetilde{{\mathcal{F}}},{\mathcal{A}}_{2},{\mathcal{U}}_{m,n}(\lambda))\leq(1+\epsilon){\mathcal{C}}({\mathcal{F}},\rho)$.

###### Proof.

Let $y\in\\{0,1\\}$ be the label of $x$. From the proof of Theorem 4.2, we
have

$\begin{array}[]{ll}\frac{\nabla L({{\mathcal{F}}}(x),y)}{\nabla
x}=\frac{e^{{{\mathcal{F}}}_{1-y}(x)}}{\sum_{i=1}^{m}e^{{{\mathcal{F}}}_{i}(x)}}(W_{x,1-y}-W_{x,y}),\\\
\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla
x}=\frac{e^{\widetilde{{\mathcal{F}}}_{1-y}(x)}}{\sum_{i=1}^{m}e^{\widetilde{{\mathcal{F}}}_{i}(x)}}((W_{x,1-y}-W_{x,y}+W_{R,1-y}-W_{R,y}).\\\
\end{array}$

Denote $a(x)=W_{x,1-y}-W_{x,y}$ and $b(y)=W_{R,1-y}-W_{R,y}$. Use
$\alpha(U,V)$ to denote the angle between two vector $U$ and $V$. We have

$\begin{array}[]{ll}\alpha({\hbox{\rm{sign}}}(\frac{\nabla
L({\mathcal{F}}(x),y)}{\nabla x}),{\hbox{\rm{sign}}}(\frac{\nabla
L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla
x})=\alpha({\hbox{\rm{sign}}}(a(x)),{\hbox{\rm{sign}}}(a(x)+b(y))).\\\
\end{array}$

For $i\in[n]$,
${\hbox{\rm{sign}}}(a_{i}(x))={\hbox{\rm{sign}}}(a_{i}(x)+b_{i}(y))$ if and
only if $(b_{i}(y)\leq-a_{i}(x)$ and $a_{i}(x)\leq 0$) or $(b_{i}(y)\geq-
a_{i}(x)$ and $a_{i}(x)\geq 0$), where $b_{i}(y),a_{i}(x)$ are respectively
the $i$-th coordinate of $b(y),a(x)$. Since
$W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)$, $b_{i}(y)=W_{R,1-y}-W_{R,y}$ is the
difference of two uniform distribution in $[-\lambda,\lambda]$. By Lemma 4.1,
we have $a_{i}(x)>0$ implies $P(b_{i}(y)\geq-
a_{i}(x))=T(\lambda,|a_{i}(x)|)<T(\lambda,\mu)$, and $a_{i}(x)<0$ implies
$P(b_{i}(y)\leq-a_{i}(x))=T(\lambda,|a_{i}(x)|)<T(\lambda,\mu)$. Hence, no
matter what is the value of $a(x)$, we always have
$P({\hbox{\rm{sign}}}(a(x))={\hbox{\rm{sign}}}(a(x)+b(y)))<T(\lambda,\mu)^{n}$.

Moreover, for $i\in[n]$, if
${\hbox{\rm{sign}}}(a_{i}(x))\neq{\hbox{\rm{sign}}}(a_{i}(x)+bv(y))$, we have
($b_{i}(y)>0$ when $a_{i}(x)<0$) or ($b_{i}(y)<0$ when $a_{i}(x)>0$). So,
$P({\hbox{\rm{sign}}}(a_{i}(x))\neq{\hbox{\rm{sign}}}(a_{i}(x)+b_{i}(y)))<1/2<T(\lambda,\mu)$.

Since $\\{b_{i}(y)\\}_{i\in[n]}$ is iid, by Lemma 4.1, for any
$V\in\\{-1,1\\}^{n}$ we have

$\begin{array}[]{ll}P_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}({\hbox{\rm{sign}}}(\frac{\nabla
L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x})=V)\\\
=P_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}({\hbox{\rm{sign}}}(a(x)+b(y))=V)\\\
=\prod_{i=1}^{n}P_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}({\hbox{\rm{sign}}}(a_{i}(x)+b_{i}(y))=V_{i})\\\
=\prod_{i=1}^{n}({\mathbf{I}}({\hbox{\rm{sign}}}(a_{i}(x))=V_{i})P_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}({\hbox{\rm{sign}}}(a_{i}(x))={\hbox{\rm{sign}}}(a_{i}(x)+b_{i}(y)))\\\
+{\mathbf{I}}({\hbox{\rm{sign}}}(a_{i}(x))\neq
V_{i})P_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}({\hbox{\rm{sign}}}(a_{i}(x))\neq{\hbox{\rm{sign}}}(a_{i}(x)+b_{i}(y))))\\\
\leq\prod_{i=1}^{n}({\mathbf{I}}({\hbox{\rm{sign}}}(a_{i}(x))=V_{i})T(\lambda,\mu)+{\mathbf{I}}({\hbox{\rm{sign}}}(a_{i}(x))\neq
V_{i})T(\lambda,\mu))\\\ =T(\lambda,\mu)^{n}.\\\ \end{array}$

For $V\in\\{-1,1\\}^{n}$, denote
$Q(x,V,\rho)={\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho
V)\neq\widehat{B}_{{\mathcal{F}}}(x))$. We have

$\begin{array}[]{ll}{\mathcal{C}}_{{\mathcal{A}}_{3}}(\widetilde{{\mathcal{F}}})&={\mathbb{E}}_{x\sim
D_{{\mathbb{O}}}}{\mathbb{E}}_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho{\hbox{\rm{sign}}}(\frac{\nabla
L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla
x}))\neq\widehat{B}_{{\mathcal{F}}}(x))]]\\\
&=\frac{1}{2^{n}}{\mathbb{E}}_{x\sim
D_{{\mathbb{O}}}}[\sum_{V\in\\{-1,1\\}^{n}}P_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}({\hbox{\rm{sign}}}(\frac{\nabla
L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x})=V)Q(x,V,\rho)]\\\
&\leq(T(\lambda,\mu)/2)^{n}{\mathbb{E}}_{x\sim
D_{{\mathbb{O}}}}[(\sum_{V\in\\{-1,1\\}^{n}}Q(x,V,\rho))]\\\
&\leq(2T(\lambda,\mu))^{n}{\mathcal{C}}({\mathcal{F}},\rho)\end{array}$

where $T(\lambda,\mu)=1-\frac{(2\lambda-\mu)^{2}}{8\lambda^{2}}$. We have
$(2T(\lambda,\mu))^{n}=(2-\frac{4\lambda^{2}+\mu^{2}-4\lambda\mu}{4\lambda^{2}})^{n}=(1+\frac{4\lambda\mu-\mu^{2}}{4\lambda^{2}})^{n}\leq(1+\frac{\mu}{\lambda})^{n}\leq
e^{n\mu/\lambda}$. Hence,
${\mathcal{C}}_{{\mathcal{A}}_{3}}(\lambda)<e^{n\mu/\lambda}{\mathcal{C}}({\mathcal{F}},\rho)$.
∎

##  5 Experiments

###  5.1 Accuracy of the bias classifier

In this section, we give the accuracy of the bias classifier using the MNIST
and CIFAR-10 data sets. We compare two models, whose detailed structure can be
found in the appendix.

${\mathcal{F}}^{(1)}$: trained with adversarial trianing (5).

${\mathcal{F}}^{(2)}$: trained with Algorithm 1.

Then, we use $B_{{\mathcal{F}}^{(2)}}(x)$ as the classifier. We test the
accuracy on the test set (TS) and the strong adversaries (SA, see [36]) and
the results are given in Table 2. From the table, we can see that the bias
classifiers achieve higher accuracies than ${\mathcal{F}}^{(1)}$ in most cases
and in particular for the more difficult strong adversaries.

Network | TS/MNIST | SA/MNIST | TS/CIFAT-10 | SA/CIFAT-10
---|---|---|---|---
${\mathcal{F}}^{(1)}$ | 99.19$\%$ | 51.5$\%$ | 81.23$\%$ | 19$\%$
$B_{{\mathcal{F}}^{(2)}}$ | 99.12$\%$ | 87.5$\%$ | 82.84$\%$ | 42$\%$
Table 2: Accuracies for MNIST and CIFAR-10

Moreover, for CIFAR-10, we compare the accuracy of our network and two other
networks ResNet18 and VGG19, all using adversarial training. From the results
in Table 3, our network ${\mathcal{F}}^{(1)}$ performs better than ResNet18
and VGG 19.

Network | Test Set | Strong adversaries
---|---|---
${\mathcal{F}}^{(1)}$ | 81.23$\%$ | 19$\%$
ResNet18 | 80.64$\%$ | 9$\%$
VGG19 | 78.92$\%$ | 12$\%$
Table 3: Accuracies for three networks on CIFAR-10.

As pointed out in [38], networks trained with adversarial training are usually
have lower accuracies, and the accuracies given in Tables 2 and 3 are about
the best ones for DNN models of similar size.

###  5.2 Robustness of the bias classifier against original-model attack

In this section, we check the robustness of the bias classifier against the
original-model attack given in Algorithm 2.

####  5.2.1 Experimental results

We use two more networks: ${\mathcal{F}}^{(3)}$ has the same structure with
${\mathcal{F}}^{(1)}$ given in Section 5.1, but trained with the first-order
regulation method [25], and ${\mathcal{F}}^{(4)}$ has the same structure with
${\mathcal{F}}^{(1)}$, but trained with the adversarial training by trades
[38]. Six kinds of adversaries are used:

$l_{\infty}$ adversaries: $1$-$i$ $(i=1,2,3)$. Each pixel of the sample
changes at most $0.i$. PGD [20] is used to attack: each step changes 0.01 and
moves $10i$ steps.

$l_{0}$ adversaries: $2$-$i$ $(i=40,60,80)$. Change at most $i$ pixels of the
sample JSMA [21] is used to attack: change $20i+20$ pixel and each of these
pixels can change at most 1.

The results are given in Tables 4 and 5. The first four rows are the creation
rates of adversaries for
${\mathcal{F}}^{(1)},{\mathcal{F}}^{(2)},{\mathcal{F}}^{(3)},{\mathcal{F}}^{(4)}$
with method PGD [20] for $l_{\infty}$ adversaries and JSMA [21] for $l_{0}$
adversaries. The last two rows are the generation rates of adversaries for the
original-model attack of the bias classifiers.

Network | 1-1 | 1-2 | 1-3 | 2-40 | 2-60 | 2-80
---|---|---|---|---|---|---
${\mathcal{F}}^{(1)}$ | $3\%$ | 17$\%$ | 55$\%$ | $55\%$ | $79\%$ | $87\%$
${\mathcal{F}}^{(2)}$ | $4\%$ | $22\%$ | $77\%$ | $62\%$ | 82$\%$ | 90$\%$
${\mathcal{F}}^{(3)}$ | $22\%$ | $78\%$ | $99\%$ | $75\%$ | 98$\%$ | 99$\%$
${\mathcal{F}}^{(4)}$ | 4$\%$ | 15$\%$ | 53$\%$ | 62$\%$ | 77$\%$ | 88$\%$
$B_{{\mathcal{F}}^{(1)}}$ | 2$\%$ | 7$\%$ | 13$\%$ | $35\%$ | $43\%$ | $46\%$
$B_{{\mathcal{F}}^{(2)}}$ | $2\%$ | $2\%$ | $3\%$ | 39$\%$ | 50$\%$ | 53$\%$
Table 4: Creation rates of adversaries for MNIST Network | 1-0.1 | 1-0.2 | 1-0.3 | 2-40 | 2-60 | 2-80
---|---|---|---|---|---|---
${\mathcal{F}}^{(1)}$ | $54\%$ | $77\%$ | $90\%$ | $72\%$ | $85\%$ | 96$\%$
${\mathcal{F}}^{(2)}$ | $54\%$ | $72\%$ | $85\%$ | $69\%$ | $88\%$ | 97$\%$
${\mathcal{F}}^{(3)}$ | $88\%$ | $92\%$ | $99\%$ | $89\%$ | $99\%$ | 99$\%$
${\mathcal{F}}^{(4)}$ | $49\%$ | $73\%$ | $85\%$ | $70\%$ | 89$\%$ | 97$\%$
$B_{{\mathcal{F}}^{(1)}}$ | $67\%$ | $70\%$ | $86\%$ | $70\%$ | $84\%$ | $91\%$
$B_{{\mathcal{F}}^{(2)}}$ | $41\%$ | $58\%$ | $77\%$ | $49\%$ | $73\%$ | 84$\%$
Table 5: Creation rates of adversaries for CIFAR-10

From the tables, we can see that the bias classifiers
$B_{{\mathcal{F}}^{(2)}}$ has significant lower creation rates of adversaries
than all other networks. For $l_{\infty}$ adversaries of MNIST,
$B_{{\mathcal{F}}^{(2)}}$ achieves near optimal results and the adversaries
almost disappear. For CIFAR-10, the creation rates of adversaries are still
quite high comparing to that of MNIST. We will explain the reason in Section
5.2.2.

####  5.2.2 Influence of adversarial training on the bias classifier

We use PGD [20] to create adversaries and show how $B_{{\mathcal{F}}_{y}}(x)$
and ${\mathcal{F}}_{y}(x)$ change along with the steps of the adversarial
training to show the results in Tables 4 and 5.

In Figure 1, we give the data of using the network Lenet-5 [17] for a sample
$x_{A}$ with label $y$ in MNIST. The blue, orange, green lines in the first
picture are Softmax${\mathcal{F}}_{y}(x)$, Softmax$B_{{\mathcal{F}}_{y}}(x)$,
Softmax$W_{{\mathcal{F}}_{y}}(x)$, respectively. The blue, orange, green lines
in the second picture are ${\mathcal{F}}_{y}(x)$, $B_{{\mathcal{F}}_{y}}(x)$,
$W_{{\mathcal{F}}_{y}}(x)$, respectively.

When the blue line decreases, we obtain an adversary for ${\mathcal{F}}$,
which is not an adversary of $B_{{\mathcal{F}}}$, because
Softmax$B_{{\mathcal{F}}_{y}}(x)$ does not reduce significiantly. For most
samples from MNIST, the pictures are almost like this one, so the values of
lines 4-5 in Table 4 are low.

Figure 1: Values of ${\mathcal{F}}_{y}(x)$, $B_{{\mathcal{F}}_{y}}(x)$ and
$W_{{\mathcal{F}}_{y}}(x)$ along with the adversarial training steps

Similar results are given in in Figures 2 for CIFAR-10 and network VGG-19
[26]. In this case, the adversary of ${\mathcal{F}}$ is also an adversary of
$B_{{\mathcal{F}}}$. This explains why the values of lines 4-5 in Table 5 are
higher than that of Table 4.

Figure 2: Values of ${\mathcal{F}}_{y}(x)$, $B_{{\mathcal{F}}_{y}}(x)$ and
$W_{{\mathcal{F}}_{y}}(x)$ along with the adversarial training steps

###  5.3 Safety against the original-model gradient-based attack

In this section, we use experimental results to validate Theorems 4.1 and 4.3.

####  5.3.1 Existence rates of adversaries

In this section, we give the approximate rates of a random sample in a small
neighbourhood of a sample in the training set to be an adversary. This
information will be used to show the robustness of the bias classifier.

Three ways to select random samples are used for a given sample $x$ in the
test set (In there, $x$ has been given the correct label by the network.).

R1: Randomly select 60 pixels of $x$ and change each pixel from $b$ to $1-b$.

R2: Each pixel of $x$ is added by a random number $0.2U(-1,1)$, where
$U(-1,1)$ is the binomial distribution of $1$ and $-1$.

The network $B_{{\mathcal{F}}^{(2)}}$ in Section 5.1 is compared with two
networks:

${\mathcal{N}}_{1}$: Lenet-5 for MNIST and VGG-19 for CIFAR-10, with normal
training (2).

${\mathcal{N}}_{2}$: Lenet-5 for MNIST and VGG-19 for CIFAR-10, with
adversarial training (5).

In Table 6, we give the average creation rates of adversaries. From the table,
we can see that the random adversary creation rates are quite low for networks
${\mathcal{N}}_{2}$ and $B_{{\mathcal{F}}^{(2)}}$ trained with the adversarial
training.

Network | R1/MNIST | R2/MNIST | R1/CIFAR-10 | R2/CIFAR-10
---|---|---|---|---
${\mathcal{N}}_{1}$ | 0.77$\%$ | 1.47$\%$ | 13.31$\%$ | 11.81$\%$
${\mathcal{N}}_{2}$ | 1.00$\%$ | 1.02$\%$ | 4.69$\%$ | 2.49$\%$
$B_{{\mathcal{F}}^{(2)}}$ | 0.85$\%$ | 1.64$\%$ | 4.28$\%$ | 1.67$\%$
Table 6: Random adversary creation rates.

####  5.3.2 Safety of the bias classifier against original-model gradient-
based attack

For MNIST, let ${\mathcal{F}}^{(5)}={\mathcal{F}}^{(2)}+W_{5}x$, where
${\mathcal{F}}^{(2)}$ is given in Section 5.1 and
$W_{5}\in{\mathbb{R}}^{10\times 784}$ is selected from
${\mathcal{U}}_{10,784}(\lambda)$ for $\lambda=100$.

For CIFAR-10, let ${\mathcal{F}}^{(6)}={\mathcal{F}}^{(2)}+W_{6}x$, where
${\mathcal{F}}^{(2)}$ is given in Section 5.1 and and
$W_{5}\in{\mathbb{R}}^{10\times 3072}$ is selected from
${\mathcal{U}}_{10,3072}(\lambda)$ for $\lambda=100$.

The creation rates of adversaries of the original-model gradient-based attack
are given in Table 7, where the adversaries are introduced in Section 5.2.1
and the data.

Network | 1-1 | 1-2 | 1-3 | 2-40 | 2-60 | 2-80
---|---|---|---|---|---|---
$B_{{\mathcal{F}}^{(5)}}$ for MNIST | $1\%$ | $2\%$ | $2\%$ | $2\%$ | $3\%$ | $4\%$
$B_{{\mathcal{F}}^{(6)}}$ for CIFAR-10 | $19\%$ | $20\%$ | $22\%$ | $21\%$ | $22\%$ | $24\%$
Table 7: Original-model gradient-based attack for MNIST and CIFAR-10

From the first row of Table 7, the bias classifier is safe against the
original-model gradient-based attack for MNIST. For MNIST, the adversarial
creation rates in Table 7 are near the adversarial rates of random samples in
Table 6. Furthermore, the results are also better than that given in Table 4,
especially for the $l_{\infty}$ adversaries.

From the second row of Table 7, the results are also near optimal for
CIFAR-10. First, comparing to the results of original-model attack in Table 5,
the adversary creation rates are decreased by half. Second, from Table 3, the
accuracy of the bias classifier is about $82\%$. The adversary creation rates
in Table 7 are about $20\%$-$24\%$. Combining these two sets of data, the real
adversary creation rates are about $1\%-6\%$ which are just above the random
creation rates of adversaries given in Table 6.

###  5.4 Black-box attack on the bias classifier

In this section, we use the transfer-based black-box attack [29] to compare
three networks: ${\mathcal{F}}^{(1)}$, ${\mathcal{F}}^{(3)}$,
${\mathcal{F}}^{(4)}$, $B_{{\mathcal{F}}^{(2)}}$ defined in Sections 5.1 and
5.2.1.

The transfer-based black-box attack for a network ${\mathcal{F}}$ works as
follows. A new network $\overline{{\mathcal{F}}}$ is trained with the training
set $\\{(x,{\mathcal{F}}(x))\\}$ for certain samples $x$. Then, we use PGD and
JSMA to create adversaries for $\overline{{\mathcal{F}}}$ and check wether
they are adversaries of ${\mathcal{F}}$. The results are given in Table 8. We
can see that, the bias classifiers performs better for most difficult
adversaries and in particular for $l_{\infty}$ adversaries. Also, the
adversary creation rates are about half of that of the original-model attack
in Tables 4 and 5. So the bias classifier has better robustness for black-box
attack in most cases.

Model | 1-1 | 1-2 | 1-3 | 2-40 | 2-60 | 2-80
---|---|---|---|---|---|---
${\mathcal{F}}^{(1)}$ | 1$\%$ | 2$\%$ | 18$\%$ | 28$\%$ | 35$\%$ | 40$\%$
${\mathcal{F}}^{(3)}$ | 6$\%$ | 12$\%$ | 28$\%$ | 38$\%$ | 45$\%$ | 50$\%$
${\mathcal{F}}^{(4)}$ | 1$\%$ | 3$\%$ | 21$\%$ | 24$\%$ | 39$\%$ | 46$\%$
$B_{{\mathcal{F}}^{(2)}}$ | 3$\%$ | 5$\%$ | 13$\%$ | 24$\%$ | 30$\%$ | 37$\%$
Table 8: Creation rates of adversaries for black-box attack of MNIST Model | 1-0.1 | 1-0.2 | 1-0.3 | 2-40 | 2-60 | 2-80
---|---|---|---|---|---|---
${\mathcal{F}}^{(1)}$ | 22$\%$ | 23$\%$ | 28$\%$ | 35$\%$ | 36$\%$ | 41$\%$
${\mathcal{F}}^{(3)}$ | 27$\%$ | 29$\%$ | 36$\%$ | 40$\%$ | 43$\%$ | 50$\%$
${\mathcal{F}}^{(4)}$ | 21$\%$ | 24$\%$ | 28$\%$ | 33$\%$ | 39$\%$ | 44$\%$
$B_{{\mathcal{F}}^{(2)}}$ | 21$\%$ | 23$\%$ | 24$\%$ | 33$\%$ | 36$\%$ | 41$\%$
Table 9: Creation rates of adversaries for black-box attack of CIFAR-10

###  5.5 Correlation attack

In this section, it is shown that the bias classifier is safe against the
correlation attack proposed in section 3.3. The network used here is
${\mathcal{F}}^{(2)}$ given in Section 5.1 and the data set is CIFAR-10. In
Table 10, we give the adversary creation rates for samples which are given the
correct label by $B_{{\mathcal{F}}^{(2)}}$. Comparing to results in Tables 5
and 9, we can see that the bias classifier is quite safe against the
correlation arrack.

Network | 1-0.1 | 1-0.2 | 1-0.3 | 2-40 | 2-60 | 2-80
---|---|---|---|---|---|---
$B_{{\mathcal{F}}^{(2)}}$ | $4\%$ | $11\%$ | $12\%$ | $8\%$ | $17\%$ | $21\%$
Table 10: Adversary creation rates for CIFAR-10 with the correlation attack

In Figure 3, we give the attack procedure. It can be seen that when
$(W_{x,y}-W_{x,i})x$ increases $B_{x,y}-B_{x,i}$ indeed decrease, but
$B_{x,y}-B_{x,i}$ doe not decrease enough to change the label, where $y$ is
the label of $x$ and $i\neq y$.

Figure 3:  The $x$-axis is number of steps of the attack. The blue line is
$(W_{x,9}-W_{x,0})x$ and the orange line $B_{x,9}-B_{x,0}$. We compare the
values for images of $9$ and $0$.

###  5.6 Comparison with other methods to defend adversaries

In this section, we compare our model with several existing models. We use
PGD-20 with $l_{\infty}$ bound $\epsilon=8/255$ to create adversaries on the
test set of CIFAR-10.

In Table 11, we give the adversary creation rates under various attacks. The
network structure of our model is ${\mathcal{F}}^{(2)}$ in section 5.1 and
ResNet-10 [13] for other networks. The results for other networks are from the
cited papers. Our model cannot use gradient directly, so we use the original-
model attack given in Section 3.2.

Attack Method | Adversary creation rates
---|---
ADV [20] | 57.1$\%$
TRADE [38] | 54.7$\%$
MMA [30] | 62.7$\%$
FOAR [25] | 67.7$\%$
SOAR [19] | 44.0$\%$
$B_{{\mathcal{F}}^{(2)}}$ in Sec. 5.1 | 41.1$\%$
$B_{{\mathcal{F}}^{(6)}}$ in Sec. 5.3.2 | $20\%$
Table 11: Adversary creation rates under various attacks for CIFAR-10

Although the structures of the networks are not the same and the way to attack
is not the same, this comparison give a rough idea of the performance that can
be achieved for various methods of defending adversaries. As we explained in
Section 5.3.2, $20\%$ is near the optimal results since the accuracy is about
$82\%$ for this dataset.

###  5.7 Summary of the experiments

We give a summary of the experiments in this section. From Table 6, we can see
that the bias classifier with a random first-degree part is safe against
adversaries.

From Tables 5, 9, 10, the original-model attack, the black-box attack, and the
correlation attack become weaker for creating adversaries, and the original
model attack is the best available attack for the bias classifier.

From Table 11, we see that the attack method SOAR [19] and the classifier
achieve the best results for creating lower rates of adversaries, which is
about the half of that the optimal rates achieved by
$B_{{\mathcal{F}}_{B}^{(6)}}$.

##  6 Concluding remarks

In this paper, we show that the bias part of a DNN can be effectively trained
as a classifier. The motivation to use the bias part as the classifier is that
gradients of the DNN seems to be inevitable to generate adversaries
efficiently and the bias part of a DNN with Relu as activation functions is a
piecewise constant function with zero gradient and is safe against direct
gradient-based attacks such as FGSM.

The bias classifier can be effectively trained with the adversarial training
method [20], because this training method increases the classification power
of the bias part and decreases the classification power of first-degree part
when a new loss function is used. Experimental results are used to show the
robustness of the bias classifier over the standard DNNs

Finally, adding a random first-degree part to the bias classifier, an
information-theoretically safe classifier is obtained, that is, its adversary
generate adversaries are almost the same as the rate of random samples to be
adversaries.

## References

  * [1] N. Akhtar and A. Mian. Threat of Adversarial Attacks on Deep Learning in Computer Vision: A Survey. arXiv:1801.00553v3, 2018.
  * [2] A. Athalye, N. Carlini, D. Wagner. Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples. Proc. ICML’2018, 274-283, 2018.
  * [3] A. Azulay and Y. Weiss. Why Do Deep Convolutional Networks Generalize so Poorly to Small Image Transformations? Journal of Machine Learning Research, 20, 1-25, 2019.
  * [4] T. Bai, J. Luo, J. Zhao. Recent Advances in Understanding Adversarial Robustness of Deep Neural Networks. ArXiv:2011.01539, 2020.
  * [5] M. Cisse, P. Bojanowski, E. Grave, Y. Dauphin, N. Usunier. Parseval Networks: Improving Robustness to Adversarial Examples. Proc. ICML’2017, 854-863, 2017.
  * [6] J. Cohen, E. Rosenfeld, Z. Kolter. Certified adversarial robustness via randomized smoothing. Proc. ICML’2019, PMLR, 1310-1320, 2019.
  * [7] G. Cybenko. Approximation by Superpositions of a Sigmoidal Function. Mathematics of control, signals and systems, 2(4), 303-314, 1989.
  * [8] C. Etmann, S. Lunz, P. Maass, C.B. Schönlieb. On the Connection Between Adversarial Robustness and Saliency Map Interpretability. arXiv preprint arXiv:1905.04172, 2019.
  * [9] O. Goldreich. Foundations of Cryptography, Volume II, Basic Tools. Cambridge University Press, 2009.
  * [10] I.J. Goodfellow, Y. Bengio, A. Courville. Deep Learning, MIT Press, 2016.
  * [11] I.J. Goodfellow, J. Shlens, C. Szegedy. Explaining and Harnessing Adversarial Examples. ArXiv:1412.6572, 2014.
  * [12] C. Guo, M. Rana, M. Cisse, L. van der Maaten. Countering Adversarial Images using Input Transformations. arXiv preprint arXiv:1711.00117, 2017.
  * [13] K. He, X. Zhang, S. Ren, J. Sun. Deep Residual Learning for Image Recognition. Proc. CVPR, 770-778, 2016.
  * [14] M. Hein and M. Andriushchenko. Formal Guarantees on the Robustness of a Classifier Against Adversarial Manipulation. Proc. NIPS, 2266-2276, 2017.
  * [15] G. Hinton, O. Vinyals, J. Dean. Distilling the Knowledge in a Neural Network. ArXiv:1503.02531, 2015.
  * [16] M. Lecuyer, V. Atlidakis, R. Geambasu, D. Hsu, S. Jana. Certified Robustness to Adversarial Examples with Differential Privacy. IEEE Symposium on Security and Privacy, 656-672, 2019.
  * [17] Y. LeCun, L. Bottou, Y. Bengio, P. Haffner. Gradient-based Learning Applied to Document Recognition. Proc. of the IEEE, 86(11), 2278-2324, 1998.
  * [18] Y. LeCun, Y. Bengio, G. Hinton. Deep Learning, Nature, 521(7553), 436-444, 2015.
  * [19] A. Ma, F. Faghri, N. Papernot, A.M. Farahmand. SOAR: Second-Order Adversarial Regularization. arXiv:2004.01832, 2020.
  * [20] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, A. Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks. ArXiv:1706.06083, 2017.
  * [21] N. Papernot, P. McDaniel, S. Jha, M. Fredrikson, Z.B. Celik, A. Swami. The Limitations of Deep Learning in Adversarial Settings. IEEE European symposium on security and privacy, 372-387, 2016.
  * [22] A. Sanyal, V. Kanade, P.H.S. Torr P.K. Dokania. Robustness via Deep Low-rank Representations. arXiv:1804.07090, 2018.
  * [23] A. Shafahi, W.R. Huang, C. Studer, S. Feizi, T. Goldstein. Are Adversarial Examples Inevitable? ArXiv:1809.02104, 2018.
  * [24] A. Shafahi, M. Najibi, A. Ghiasi, Z. Xu, J. Dickerson, C. Studer, L.S. Davis, G. Taylor, T. Goldstein. Adversarial Training for Free! ArXiv: 1904.12843, 2019.
  * [25] C.J. Simon-Gabriel, Y. Ollivier, L. Bottou L, D. Lopez-Paz. First-order Adversarial Vulnerability of Neural Networks and Input Dimension. ICML, 5809-5817, 2019.
  * [26] K. Simonyan and A. Zisserman. Very Deep Convolutional Networks for Large-scale Image Recognition. arXiv preprint arXiv:1409.1556, 2014.
  * [27] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I.J. Goodfellow, R. Fergus. Intriguing Properties of Neural Networks. ArXiv:1312.6199, 2013.
  * [28] F. Tramer, A. Kurakin, N. Papernot, I. Goodfellow, D. Boneh, P. McDaniel. Ensemble Adversarial Training: Attacks and Defenses. ArXiv: 1705.07204, 2017.
  * [29] F. Tramér, N. Papernot, I. Goodfellow, D. Boneh, P. McDaniel. The Space of Transferable Adversarial Examples. arXiv preprint arXiv:1704.03453, 2017.
  * [30] Z. Wang, C. Xiang, W. Zou, C. Xu. MMA Regularization: Decorrelating Weights of Neural Networks by Maximizing the Minimal Angles. arXiv:2006.06527, 2020.
  * [31] C. Xie, J. Wang, Z. Zhang, Z. Ren, A. Yuille. Mitigating Adversarial Effects Through Randomization. arXiv:1711.01991, 2017.
  * [32] C. Xie, Y. Wu, L.V.D. Maaten, A.L. Yuille, K. He. Feature Denoising for Improving Adversarial Robustness. CVPR, 501-509, 2019.
  * [33] H. Xu, Y. Ma, H.C. Liu, D, Deb, H. Liu J.L. Tang, A.K. Jain. Adversarial Attacks and Defenses in Images, Graphs and Text: A Review. International Journal of Automation and Computing, 17(2), 151-178, 2020.
  * [34] M. Wen, Y. Xu, Y. Zheng, Z. Yang, X. Wang. Sparse Deep Neural Networks Using $L_{1,\infty}$-Weight Normalization, Statistica Sinica, 31, 1397-1414, 2021
  * [35] L. Yu and X.S. Gao. Improve the Robustness and Accuracy of Deep Neural Network with $L_{2,\infty}$ Normalization. arXiv:2010.04912.
  * [36] L. Yu and X.S. Gao. A Robust Classification-autoencoder to Defend Outliers and Adversaries. arXiv preprint arXiv:2106.15927, 2021.
  * [37] X.Y. Zhang, C.L. Liu, C.Y. Suen. Towards Robust Pattern Recognition: A Review. Proc. of the IEEE, 108(6), 894-922, 2020.
  * [38] H. Zhang, Y. Yu, J. Jiao, E.P. Xing, L.E. Ghaoui, M.I. Jordan. Theoretically Principled Trade-off between Robustness and Accuracy. Proc. ICML, 2019.
  * [39] Moosavi-Dezfooli S M, Fawzi A, Frossard P. Deepfool: a simple and accurate method to fool deep neural networks[C]//Proceedings of the IEEE conference on computer vision and pattern recognition. 2016: 2574-2582.

## Appendix. Structures of DNN models used in the experiments

The network in section 5.1:

Networks ${\mathcal{F}}^{(1)}$ and ${\mathcal{F}}^{(2)}$ for MNIST have the
same structure:

Input layer: $N\times 1\times 28\times 28$, where $N$ is steps of training.

Hidden layer 1: a convolution layer with kernel $1\times 32\times 3\times 3$
with padding$=1$ $\to$ do a batch normalization $\to$ do Relu $\to$ use max
pooling with step=2.

Hidden layer 2: a convolution layer with kernel $32\times 64\times 3\times 3$
with padding$=1$ $\to$ do a batch normalization $\to$ do Relu $\to$ use max
pooling with step=2.

Hidden layer 3: a convolution layer with kernel $64\times 128\times 3\times 3$
with padding$=1$ $\to$ do a batch normalization $\to$ do Relu $\to$ use max
pooling with step=2.

Hidden layer 4: draw the output as $N\times 128\times 3\times 3$ $\to$ use a
full connection with output size $N\times 128\times 2$ $\to$ do Relu.

Hidden layer 4: use a full connection with output size $N\times 100$ $\to$ do
Relu.

Output layer: a full connection layer with output size $N\times 10$.

Networks ${\mathcal{F}}^{(1)}$ and ${\mathcal{F}}^{(2)}$ for CIFAR-10 have the
same structure:

Input layer: $N\times 3\times 32\times 32$, where $N$ is steps of training.

Hidden layer 1: a convolution layer with kernel $3\times 64\times 3\times 3$
with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 2: a convolution layer with kernel $64\times 64\times 3\times 3$
with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 3: a convolution layer with kernel $64\times 128\times 3\times 3$
with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 4: a convolution layer with kernel $128\times 128\times 3\times
3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu $\to$ use max
pooling with step=2.

Hidden layer 5: a convolution layer with kernel $128\times 256\times 3\times
3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 6: a convolution layer with kernel $256\times 256\times 3\times
3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 7: a convolution layer with kernel $256\times 256\times 3\times
3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu $\to$ use max
pooling with step=2.

Hidden layer 8: a convolution layer with kernel $256\times 512\times 3\times
3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 9: a convolution layer with kernel $512\times 512\times 3\times
3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 10: a convolution layer with kernel $512\times 512\times 3\times
3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu $\to$ use max
pooling with step=2.

Hidden layer 11: a convolution layer with kernel $512\times 512\times 3\times
3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 12: a convolution layer with kernel $512\times 512\times 3\times
3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 13: a convolution layer with kernel $512\times 512\times 3\times
3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu $\to$ use max
pooling with step=2.

Hidden layer 14: draw the output as $N\times 2048$ $\to$ a full connection
layer with output size $N\times 1024$ $\to$ do Relu.

Hidden layer 15: a full connection layer with output size $N\times 512$ $\to$
do Relu.

Hidden layer 16: a full connection layer with output size $N\times 128$ $\to$
do Relu.

Output layer: a full connection layer with output size $N\times 10$.