#  $\varepsilon$-weakened Robustness of Deep Neural Networks

Pei Huang  State Key Laboratory of Computer ScienceInstitution of Software,
CASBeijingChina<EMAIL_ADDRESS>,  Yuting Yang  Key Laboratory of
Intelligent Information Institute of Computing Technology, CASBeijingChina
<EMAIL_ADDRESS>,  Minghao Liu  State Key Laboratory of Computer
ScienceInstitution of Software, CASBeijingChina<EMAIL_ADDRESS>,  Fuqi Jia
State Key Laboratory of Computer ScienceInstitution of Software,
CASBeijingChina<EMAIL_ADDRESS>,  Feifei Ma  State Key Laboratory of Computer
ScienceInstitution of Software, CASBeijingChina<EMAIL_ADDRESS>and  Jian Zhang
State Key Laboratory of Computer ScienceInstitution of Software,
CASBeijingChina<EMAIL_ADDRESS>
###### Abstract.

This paper introduces a notation of $\varepsilon$-weakened robustness for
analyzing the reliability and stability of deep neural networks (DNNs). Unlike
the conventional robustness, which focuses on the “perfect” safe region in the
absence of adversarial examples, $\varepsilon$-weakened robustness focuses on
the region where the proportion of adversarial examples is bounded by user-
specified $\varepsilon$. Smaller $\varepsilon$ means a smaller chance of
failure. Under such robustness definition, we can give conclusive results for
the regions where conventional robustness ignores. We prove that the
$\varepsilon$-weakened robustness decision problem is PP-complete and give a
statistical decision algorithm with user-controllable error bound.
Furthermore, we derive an algorithm to find the maximum $\varepsilon$-weakened
robustness radius. The time complexity of our algorithms is polynomial in the
dimension and size of the network. So, they are scalable to large real-world
networks. Besides, We also show its potential application in analyzing quality
issues.

deep neural network, robustness, reliability, testing, statistical method

##  1\. Introduction

Deep neural networks (DNNs) have been broadly applied in various domains.
However, many studies have shown that these state-of-the-art models can be
easily compromised by adding small perturbations (Szegedy et al., 2014a;
Goodfellow et al., 2015; Chen et al., 2018), i.e., visually imperceptible
image perturbations can cause the misclassification of neural networks. Such
unstable properties have raised serious concerns about the reliability of the
application based on DNNs. Addressing for safe adoption of DNNs requires
robustness metrics and efficient analyzing methods to understand the
reliability and vulnerability of neural networks.

In recent years, a large body of prior work has focused on robustness which is
defined on the absence of adversarial examples around a given point. These
robust regions are absolutely safe against any malicious attacks. However, it
is not enough to understand the reliability and stability of neural networks,
we notice that: (1) The “perfect” safe regions are usually very small for the
real-world random perturbations. Take an example, for ImageNet task, more than
90% regions of a well-trained ResNet are unsafe under the condition of the
perturbation radius $2/255$ (Wong et al., 2020). In the real environment, a
drop of rain on the input camera or the changes in light and shade can often
shift the input out of these “perfect” safe regions. In this situation, such
robustness analyzing can not provide a conclusion about whether an NN can
resist these perturbations well. (2) The definition of conventional robustness
can suffer from the “curse of dimensionality”, which means, in high-
dimensional space, the majority part of the safe region around a given point
can be ignored (Sec.3). (3) The robustness radius is strongly related to the
location of a given point. So we cannot make a comprehensive judgment on the
reliability of the NN in that region (Sec.3).

Unlike traditional programs, there is no basic theory to guarantee the
correctness of deep neural networks. Even if a concept is PAC-learnable
(Valiant, 1984), the learning algorithm can only learn a close approximation
to the target concept with generalization error. In 2019, David .et.al (Stutz
et al., 2019) point out that on-manifold robustness is essentially
generalization and adversarial examples are generalization errors. As the
generalization error cannot be eliminated, it is difficult to eliminate all
adversarial examples around a point at this stage. These adversarial examples
distributed everywhere and make almost all the perfect safe regions in norm
bounds too small, as if the network is just robust at the given test points.
Many studies show that improving such robustness a little is usually
accompanied by a sharp decline in accuracy (Wong et al., 2020; Shafahi et al.,
2019) and make NN inapplicable in practice. So the pursuit of error-free
robustness sometimes can be too severe for many applications.

In this paper, we study the robustness from the perspective of quantification.
We formalize a robustness metric called $\varepsilon$-weakened robustness
($\varepsilon$-robustness in short) which allows some adversarial examples
around a test data point but the proportion is bounded by a user-specified
$\varepsilon$. Smaller $\varepsilon$ indicates a smaller failure rate or the
smaller chance that the neural network yields to non-crafted perturbations.
For many practical applications, safety standards are defined on the specified
low failure rates. For instance, in autonomous robotics and self-driving
settings where there is some environment model and we would like to bound the
probability of an adverse outcome (Kalra and Paddock, 2016; Koopman and Osyk,
2019). Thus, analyzing the $\varepsilon$-robustness of neural networks is very
helpful for building a reliable system in deployment.

After introducing $\varepsilon$: (1) we can draw analysis results about the
reliability of neural networks when the real-word perturbations often shift
the inputs out of the perfect safe regions. (2) It is also helpful to
alleviate the “curse of dimensionality” in conventional robustness analysis
and reduce the dependence of analysis results on the locations of test points.
(3) It not only can be applied to analyze whether the region around a
correctly classified point is “good” enough to resist perturbations, but also
to analyze whether the region around a misclassified point is so “bad”. (4) It
can be extended to the multi-labels version for analyzing the risk. Sometimes
misclassification does not mean disaster. If the network recognizes a car as a
truck, the self-driving car can still make a right decision to avoid it. The
extended version $\varepsilon$-robustness can be applied to analyzing the risk
of not recognizing a car as a vehicle by a neural network.

We call determining whether a region is $\varepsilon$-robust as
$\varepsilon$-weakened robustness decision problem and finding the maximum
$\varepsilon$-robust radius as $\varepsilon$-weakened robustness evaluation
problem. We prove that the $\varepsilon$-robustness decision problem is PP-
complete, so it is not feasible to tackle these problems with precise methods
for real-world large DNNs. Thus, we apply a statistical inference method with
user-controllable error bounds (or confidence) $\alpha$ and $\beta$. $\alpha$
is the probability of false positives and $\beta$ is the probability of false
negative. Such simulations and statistical inference can be promising in
analyzing deep learning systems because each execution of a neural network
takes a little time even when the model has millions of parameters. Besides,
many potential executions can be simulated in parallel easily.

Our contributions can be summarized as follows:

  * •

We analyze the limitation of conventional robustness in reliability analysis
and formalize $\varepsilon$-weakened robustness for DNNs. It can provide a
more comprehensive analysis of the reliability and risk of DNN models.

  * •

We prove that $\varepsilon$-weakened robustness decision problem is
$PP$-complete.

  * •

We propose a probabilistic algorithm for $\varepsilon$-weakened robustness
decision problem with provable guarantees w.r.t $\alpha$ and $\beta$. The
algorithm is polynomial in input dimension and size of the network.

  * •

We propose an algorithm to tackle $\varepsilon$-weakened robustness evaluation
problem under the framework of querying decision oracle.

  * •

We evaluate our methods on the popular neural networks and data sets. They are
scalable to large DNNs with more than 100 layers. Furthermore, we conduct some
experiments to show its potential applications in analyzing the quality issues
of deep learning systems.

##  2\. Preliminaries

###  2.1. Neural Networks and Local Robustness

Let $f:\mathbb{D}^{n}\rightarrow\mathbb{R}^{m}$ be a neural network classifier
such that, for a given input $x\in\mathbb{D}^{n}$,
$f(x)=\\{o_{1}(x),o_{2}(x),...,o_{m}(x)\\}\in\mathbb{R}^{m}$ represents the
confidence values for $m$ classification labels. The prediction of $x$ is
given as $F(x)=\mathop{\arg\max}_{1\leq i\leq m}o_{i}(x)$.

###### Definition 2.1 (Local Robustness).

Given a test point $x_{*}$ with predicted label $l_{*}$, the neural network is
locally robust at point $x_{*}$ with respect to a distortion radius $r$ if the
following formula holds:

(1) $\forall x_{*}^{\prime}.\ x_{*}^{\prime}\in B_{p}(x_{*},r)\Rightarrow
F(x_{*}^{\prime})=l_{*}$

where $B_{p}(x_{*},r)=\\{x_{*}^{\prime}\
|\left\|x_{*}^{\prime}-x_{*}\right\|_{p}\leq r\\}$ is an $\ell_{p}$-norm ball.

It means that any perturbed examples of $x_{*}$ with $\ell_{p}$-distortion
$\Delta_{p}\leq r$ will not change the classification results.

The Local Robustness Evaluation (LRE) problem over an input $x_{*}$ aims at
finding the maximum radius of a safe $\ell_{p}$-norm ball with the center
$x_{*}$. It can be formalized as an optimization problem:

(2) $\begin{split}&\mathbf{max}\ \ r\\\ &\mathbf{s.t}\ \ \forall
x_{*}^{\prime}.\ x_{*}^{\prime}\in B_{p}(x_{*},r)\Rightarrow
F(x_{*}^{\prime})=l_{*}\end{split}$

We call the maximized $r$ as robustness radius. Limited by computational
complexity, finding the maximum radius is very difficult and most of the work
is devoted to giving a lower bound.

###### Definition 2.2 (Lipschitz continuity).

Let $S\subset\mathbb{R}^{n}$ be a convex bounded closed set and let
$f(x):S\rightarrow\mathbb{R}$ be a function on an open set containing $S$.
Then $f$ is Lipschitz continuous if there exists a real constant $K>0$ such
that $\forall x,y\in S$:

$\forall x,y\in S,|f(y)-f(x)|\leq K\left\|y-x\right\|_{p}$

###### Definition 2.3 (Continuity).

Let $S\subset\mathbb{R}^{n}$ be a convex bounded closed set and let
$f(x):S\rightarrow\mathbb{R}$ be a function on an open set containing $S$.
Then $f$ is continuous at point $x_{0}$ if $\forall\xi>0$, $\exists\eta>0$:

$\forall x\in S,\left\|x-x_{0}\right\|_{p}<\eta\Rightarrow|f(x)-f(x_{0})|<\xi$

Lipschitz continuity implies continuity.

###### Lemma 2.4.

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ be a neural network continuous
at each point of the domain $S$ and $x_{*}$ is an input. The prediction of the
network is given by $l=\mathop{\arg\max}_{1\leq i\leq m}o_{i}(x_{*})$. If
$\forall i\in\\{1,2...m\\}$, $o_{l}(x_{*})>o_{i}(x_{*})$ where $i\neq l$
holds, then there exists $\eta$ such that:

$\forall x\in S,\left\|x-x_{*}\right\|_{p}<\eta\Rightarrow F(x)=l$

###### Proof.

Let $g_{i}(x)=o_{l}(x)-o_{i}(x)$ ($i\neq l$), we have $g_{i}(x)$ is continuous
at point $x_{*}$ and $g_{i}(x_{*})>0$. Assume $g_{i}(x_{*})=\xi_{i}$, based on
the definition of continuity there exist $\eta_{i}$ such that:

$\forall x\in
S,\left\|x-x_{*}\right\|_{p}<\eta_{i}\Rightarrow|g_{i}(x)-g_{i}(x_{*})|<\xi_{i}$

which implies that

$\forall x\in S,\left\|x-x_{*}\right\|_{p}<\eta_{i}\Rightarrow g_{i}(x)>0$

Let $\eta=\min_{i\neq l}{\\{\eta_{i}\\}}$, we have for all $i$ over ($i\neq
l$):

$\forall x\in S,\left\|x-x_{*}\right\|_{p}<\eta\Rightarrow o_{l}(x)>o_{i}(x)$

So, there exists $\eta>0$, the classification result will not change when
$\left\|x-x_{*}\right\|_{p}<\eta$ ∎

Lemma 2.4 states several facts about continuous neural network and test point
satisfying $o_{l}(x_{*})>o_{i}(x_{*})$: (1) If a point is predicted correctly,
there must be a neighborhood such that all points in it will be predicted
correctly. (2) If we find an adversarial example, there must be a neighborhood
such that all points in it will be predicted incorrectly.

Almost all neural networks defined on $\mathbb{R}^{n}$ are continuous unless
discontinuous activation functions (e.g. step function) are used. Furthermore,
convolution, softmax, max pooling, and contrast normalization, fully connected
layer with ReLU, sigmoid, hyperbolic tangent activation functions are proved
to be Lipschitz continuous (Szegedy et al., 2014b; Ruan et al., 2018).

##  3\. Limitations of Conventional Robustness

The conventional robustness can help to understand the ability of the NN to
resist attacks. But it has some limitations in understanding the reliability
and building a reliable system in practice.

In machine learning, a class of hypotheses $\mathcal{H}$ (or possible models
$f_{\Theta}$) is PAC learnable if for any pair ($\varepsilon$, $\delta$) with
$0<\varepsilon$, $\delta\leq 0.5$, the learning algorithm produces a high
accuracy hypothesis (model) $f_{\theta}\in\mathcal{H}$ with high probability:

$P(|R(f_{\theta})-\hat{R}(f_{\theta})|\leq\varepsilon)\geq 1-\delta$

where $R$ is generalization error and $\hat{R}$ is training error. Even a
concept is PAC learnable, we cannot expect an algorithm to learn it exactly.
The only realistic expectation of a good learner is that it will learn a close
approximation to the target concept with high probability. Moreover, we cannot
always expect a learner to learn a close approximation to the target concept
since sometimes the training set does not represent unseen examples. There may
be many concepts consistent with the available data, and unseen examples may
have any label. On-manifold robustness is essentially generalization. We
cannot eliminate the generalization error and adversarial examples can be
everywhere. These adversarial examples make almost all the perfect safe
regions in norm bounds too small. Even after improving, they still cannot meet
the needs of real-world perturbations. In addition, the improvement is usually
accompanied by a sharp drop in accuracy. So only considering robustness with
error-free sometimes can be too severe for many applications.

(a)

(b)

Figure 1. (a) Situation 1: the majority part in safe region is out of the safe
norm ball because of the “curse of dimensionality”. (b) Situation 2: the safe
norm ball is very small as the given point is located near the boundary of the
safe region.

Besides, we notice that the definition of conventional robustness can suffer
from the “curse of dimensionality” and is strongly related to the location of
the given test point.

For example, Figure 1(a) shows the optimal safe norm ball $B_{2}(x_{*},r)$
around point $x_{*}$. Suppose the real safe region around the point $x_{*}$ is
$S_{2}$, then we have:

$\lim\limits_{n\rightarrow\infty}\frac{Vol(S_{2})-Vol(S_{1})}{Vol(S_{2})}=1$

where $n$ is the dimension of the space and $Vol(\cdot)$ is the volume. It
implies that the majority of points are located at the edge of $S_{2}$. This
means that as the dimensionality grows $S_{1}$ is like a “hollow ball”.
Actually, computing the optimal norm ball is very difficult, and existing
methods can only give lower bounds. We cannot expect to evaluate $S_{2}$
accurately, because it is usually a high-dimensional non-convex region.

Sometimes, a given point may be near the edge of real-world data distribution
in that region. Figure 1 (b) shows the situation where given $x_{*}$ is
located in a “bad” position. The robustness analysis result reveals that the
safe region is very small. However, the real safe region can be much bigger
than the safe norm ball. In such a situation, we may draw a biased evaluation
result about the safe region because the analysis results are only based on
the radius of the safe norm ball.

##  4\.  $\varepsilon$-Weakened Robustness

First, we define an indicative function $T(F,x,\Omega)$. $\Omega$ is designed
for multi-labels extension.

###### Definition 4.1.

Consider a neural classifier $F(x)$. Given a test point $x$ with a label set
$\Omega$, the indicative function $T(F,x,\Omega)$ is defined as:

(3) $T(F,x,\Omega)=\left\\{\begin{aligned} 1&&F(x)\in\Omega\\\
0&&F(x)\notin\Omega\end{aligned}\right.$

###### Definition 4.2 ($\varepsilon$-weakened robustness).

Consider a neural classifier $F(x)$. Given a test point $x_{*}$ with the gold
label $l_{*}$ and a $p$-norm ball with radius $r$, if the formula:

(4) $\frac{\mu(\\{x|x\in B_{p}(x_{*},r)\wedge
T(F,x,\Omega)=1\\})}{\mu(B_{p}(x_{*},r))}>1-\varepsilon$

holds for a measure $\mu$ and parameter $\varepsilon$, then $F(x)$ is said to
be $\varepsilon$-weakened robust at point $x_{*}$ with respect to the radius
$r$. $\mu(\cdot)\in[0,+\infty)$, $\Omega=\\{l_{*}\\}$, $p\in\\{1,2,\infty\\}$
and $\varepsilon\in(0,1)$ is a fixed-length computer representable binary
number (e.g., float 64 or 32).

We briefly denote it as $\varepsilon$-robustness. It can be seen as a
relaxation of formula (1). Deciding whether formula (4) is “SAT” is called
$\varepsilon$-weakened robustness decision problem. If the input space
$\mathbb{D}^{n}$ is defined on a countable set, $\mu$ is the counting measure
(i.e., the cardinality of the set). If the input space is $\mathbb{R}^{n}$,
$\mu$ is the volume. Based on the property depicted in lemma 2.4, volume is a
reasonable measure.

Figure 2. $\varepsilon$-weakened robustness

###### Definition 4.3.

$\varepsilon$-weakened robustness evaluation problem is an optimization
problem:

(5) $\begin{split}&\mathbf{max}\ \ r\\\ &\mathbf{s.t}\ \
\varepsilon\text{-}robust(x_{*},r)\end{split}$

where $\varepsilon$-$robust(x_{*},r)$ denotes the classifier $F(x)$ is
$\varepsilon$-robust at point $x_{*}$ w.r.t. the radius $r$.

After introducing $\varepsilon$, we can provide conclusive analysis results
about the regions which are not “perfect” safe. Besides, the majority of a
safe region around a given point is considered. Introducing $\varepsilon$ also
helps to alleviate the dependence of analysis results on the locations of
given points as the norm bound can go outside the “perfect” safe region.

###  4.1. Computational Complexity

Actually, it is better to compute $\mu(\\{x|x\in B_{p}(x_{*},r)\wedge
T(F,x,\Omega)=1\\})$. However, this problem is #P-hard and even the Monte
Carlo approximation is exponential in the dimensionality for the worst case
when the error bound is fixed (Simonovits, 2003). As an alternative, answering
whether the formula (4) is true is computationally easier.

###### Theorem 4.4.

$\varepsilon$-robustness decision problem is $PP$-complete.

We only show a proof skeleton here and full details are provided in the
appendix (see supplementary material). First, we prove that the
$\varepsilon$-robustness decision problem is in $PP$. We give a polynomial-
time probabilistic algorithm with an error probability of less than 1/2, which
is a simplified version of Algorithm 1 (In sec. 6.1). Then we prove
MAJSAT($\geq 2^{n-1}$), which asks if a CNF (or SAT) formula has at least half
of the possible truth assignments, can be reduced to $\varepsilon$-robustness
decision problem. The MAJSAT($\geq 2^{n-1}$) is known to be PP-complete(III,
1974). We use polynomial-size neurons with ReLU function to simulate negation
operators and clauses. In this context, MAJSAT can be transformed to the
$1/2$-robustness decision problem of a binary classification network.

##  5\. Methodology

It is known that $NP\subseteq PP\subseteq\\#P$. Although introducing
$\varepsilon$ helps to reduce computational complexity, the $PP$-completeness
of the problem still means that we must expect the worst-case performance of
the exact algorithm to be poor. So we provide a statistical inference method
to tackle the $\varepsilon$-robustness decision problem with user-controllable
error bounds (or confidence). In most cases, such a provable guarantee can
meet the needs of software engineering.

We put the $\varepsilon$-robustness decision problem in the framework of
hypothesis testing, and explain how to control the error bounds.

###  5.1. Reduction to hypothesis testing

Let

$p_{r}=\frac{\mu(\\{x^{\prime}|x^{\prime}\in B_{p}(x_{*},r)\wedge
T(F,x^{\prime},\Omega)=1\\})}{\mu(B_{p}(x_{*},r))}\ $

then the $\varepsilon$-robustness decision problem is to determine whether
$H_{0}$ or $H_{1}$ is true:

$H_{0}:p_{r}>1-\varepsilon\ \ \ \ H_{1}:p_{r}\leq 1-\varepsilon$

$H_{0}$ is called null hypothesis which means the NN is $\varepsilon$-robust
and $H_{1}$ is called alternative hypothesis which is the opposite.

A procedure which is based on the value of a statistic, usually the sample
mean $\overline{y}$, for deciding whether to accept or reject $H_{0}$ is
called a _test of a statistical hypothesis_. It is also a method for measuring
the strength of the evidence against the null hypothesis contained in the
experimental data. The set of values

$\mathcal{C}=\\{\overline{y}:y\leq c\\}$

is called the rejection region of the test, since $H_{0}$ is rejected when
$\overline{y}$ falls in $\mathcal{C}$. Two types of errors can occur in this
statistical decision-making process, and they are shown in Table 1.

Table 1. Null and alternative hypothesis, decision rules, type I and type II errors. $\overline{y}$ | $H_{0}\ is\ true$ | $H_{1}\ is\ true$
---|---|---
$\overline{y}>c$ (accept $H_{0}$) | $Correct\ decision$ | $Type\ II\ error$
$\overline{y}\leq c$ (reject $H_{0}$) | $Type\ I\ error$ | $Correct\ decision$

A type $I$ error occurs when $H_{0}$ is actually true but one rejects $H_{0}$
(accepts $H_{1}$). A type $II$ error occurs when $H_{0}$ is actually false but
one accepts $H_{0}$ (rejects $H_{1}$).

  * •

The probability of type $I$ error (false positive) is defined as:

$P(\text{Reject }H_{0}|H_{0}\text{ is true})=P(\overline{Y}\leq c|H_{0}\text{
is true})$

  * •

The probability of type $II$ error (false negative) is defined as:

$P(\text{Accept }H_{0}|H_{0}\text{ is false})=P(\overline{Y}>c|H_{0}\text{ is
false})$

Terminology: The significance level of the test is the probability of a type I
error.

We can answer the hypothesis $H_{0}$ with uniform sampling in
$B_{p}(x_{*},r)$. We know that the satisfaction of $T(F,x_{*},\Omega)=1$ is
binomial distribution. We take random samples of sizes $N$ from the space
$B_{p}(x_{*},r)$ independently, and denote their possible outcomes as
independent random variables $Y_{1},Y_{2},...,Y_{N}$ where $Y_{i}\sim
Bernoulli(p_{r})$.

If $N$ satisfies

$N>N(1-\varepsilon)+3\sqrt{N\varepsilon(1-\varepsilon)}$ (6) $\text{or
}\sqrt{N}>3\sqrt{\frac{1-\varepsilon}{\varepsilon}}$

then a “large-sample” test is done. Based on central limit theorem, if
$\overline{Y}=(\sum\nolimits_{i=1}^{N}Y_{i})/N$, $\sigma=p_{r}(1-p_{r})$ we
have:

(7) $Z=\frac{(\overline{Y}-p_{r})}{\sigma/\sqrt{N}}\sim\mathcal{N}(0,1)$

where $\mathcal{N}(0,1)$ is a Gaussian distribution.

###  5.2. Controlling Type II Error

We first introduce how to control the probability of committing a type $II$
error. Because it is very important for answering the $\varepsilon$-robustness
decision problem. We do not hope the network is not $\varepsilon$-robust but
the algorithm often answers “SAT”.

The probability of a type $II$ error is as follows:

$\displaystyle P(\overline{Y}>c|H_{0}\text{ is false})$ $\displaystyle\leq
P(\overline{Y}>c|p_{r}=1-\varepsilon)$
$\displaystyle=P(\frac{\overline{Y}-p_{r}}{\sigma/\sqrt{N}}>\frac{c-p_{r}}{\sigma/\sqrt{N}}|p_{r}=1-\varepsilon)$
$\displaystyle=P(\frac{\overline{Y}-p_{r}}{\sigma/\sqrt{N}}>\frac{c-(1-\varepsilon)}{\sigma/\sqrt{N}})$
$\displaystyle=P(Z>\frac{c-(1-\varepsilon)}{\varepsilon(1-\varepsilon)/\sqrt{N}})$

So, if we expect the probability of committing a type $II$ error is less than
$\beta$, we have :

$P(Z>\frac{c-(1-\varepsilon)}{\varepsilon(1-\varepsilon)/\sqrt{N}})\leq\beta$
$\Rightarrow\frac{c-(1-\varepsilon)}{\varepsilon(1-\varepsilon)/\sqrt{N}}\geq
z_{1-\beta}$

$z_{1-\beta}$ is the $1-\beta$ quantile of $\mathcal{N}(0,1)$ and we have:

(8)
$c\geq\frac{\varepsilon(1-\varepsilon)z_{1-\beta}}{\sqrt{N}}+(1-\varepsilon)$

When $c$ satisfies formula (8), the probability of committing a type $II$
error is smaller than $\beta$.

###  5.3. Controlling Type I Error

The probability of type $I$ error follows:

$\displaystyle P(\overline{Y}\leq c|H_{0}\text{ is true})$
$\displaystyle=P(\overline{Y}\leq c|p_{r}>1-\varepsilon)$
$\displaystyle=P(\overline{Y}\leq c|p_{r}\geq 1-\varepsilon^{\prime})$
$\displaystyle\leq P(\overline{Y}\leq c|p_{r}=1-\varepsilon^{\prime})$
$\displaystyle=P(\frac{\overline{Y}-p_{r}}{\sigma/\sqrt{N}}\leq\frac{c-p_{r}}{\sigma/\sqrt{N}}|p_{r}=1-\varepsilon^{\prime})$
$\displaystyle=P(Z\leq\frac{c-(1-\varepsilon^{\prime})}{\sigma/\sqrt{N}})$

$\varepsilon^{\prime}$ is the closest machine number where
$\varepsilon>\varepsilon^{\prime}$.

So, the probability of committing a type $I$ error being less than $\alpha$
can be given by:

$\displaystyle
P(Z\leq\frac{c-(1-\varepsilon^{\prime})}{\sigma/\sqrt{N}})\leq\alpha$
$\displaystyle\Rightarrow\frac{c-(1-\varepsilon^{\prime})}{\varepsilon^{\prime}(1-\varepsilon^{\prime})/\sqrt{N}}\leq
z_{\alpha}$

where $z_{\alpha}$ is the $\alpha$ quantile of $\mathcal{N}(0,1)$.

Let $c=(\varepsilon(1-\varepsilon)z_{1-\beta})/\sqrt{N}+(1-\varepsilon)$, we
have:

(9)
$\sqrt{N}\geq\frac{\varepsilon(1-\varepsilon)z_{1-\beta}-\varepsilon^{\prime}(1-\varepsilon^{\prime})z_{\alpha}}{\varepsilon-\varepsilon^{\prime}}$

Based on (6) and (9), the sample size $N$ is given by:

(10)
$\sqrt{N}\geq\max\\{\frac{\varepsilon(1-\varepsilon)z_{1-\beta}-\varepsilon^{\prime}(1-\varepsilon^{\prime})z_{\alpha}}{\varepsilon-\varepsilon^{\prime}},3\sqrt{\frac{1-\varepsilon}{\varepsilon}}\\}$

If the sample size $N$ satisfies formula (10), then the probability of
committing a type $I$ error is smaller than $\alpha$. It is also called a test
with significant level at $\alpha$.

In practice, controlling the type I error and type II error simultaneously can
be a heavy burden for computation. In order to improve efficiency, we strictly
control II error and loosen the other one as an alternative. For robustness
decision problem, strictly controlling type II error is more important.
Because when the network is not robust, the algorithm answering “SAT” can be
dangerous. So we let $\varepsilon^{\prime}$ smaller than $\varepsilon$ e.g.,
$\varepsilon^{\prime}=\varepsilon-\min(\sigma,0.005)$ where
$\sigma\approx\varepsilon(1-\varepsilon)$. It means we strictly control
$P(\text{reject }H_{0}|p_{r}\geq 1-\varepsilon^{\prime})$ to be less than
$\alpha$.

##  6\. Algorithms

In this section, we present a probabilistic algorithm for
$\varepsilon$-robustness decision problem and analyze the time complexity.
Then, we give an algorithm to find the maximum $\varepsilon$-robustness
radius.

###  6.1. $\varepsilon$-Robustness Decision Algorithm

Based on the theory described in Sec.5, the decision algorithm is outlined in
Algorithm 1 and the sampling methods are in appendix.

Input: $F$\- network classifer, $x_{*}$\- test point, $r$-distortion radius,
$p$\- $p$ norm $\varepsilon$\- weakening parameter, $\alpha$-type $I$ error ,
$\beta$-type $II$ error

Output: $SAT$ or $UNSAT$.

1 $\Omega\leftarrow\\{l_{*}-\text{label of }x_{*}\\}$;

2 $Construct\ function\ T(F,x,\Omega)$;

3 $z_{\alpha}\leftarrow\Phi^{-1}(\alpha)$ ; /* $\Phi$ is the CDF of
$\mathcal{N}(0,1)$ */

4$z_{1-\beta}\leftarrow\Phi^{-1}(1-\beta)$;

5 $\varepsilon^{\prime}=\varepsilon-\min(\varepsilon(1-\varepsilon),0.005)$;

6
$N\leftarrow\lceil\max\\{(\frac{\varepsilon(1-\varepsilon)z_{1-\beta}-\varepsilon^{\prime}(1-\varepsilon^{\prime})z_{\alpha}}{\varepsilon-\varepsilon^{\prime}})^{2},9\frac{1-\varepsilon}{\varepsilon}\\}\rceil$;

7
$c\leftarrow\frac{\varepsilon(1-\varepsilon)z_{1-\beta}}{\sqrt{N}}+(1-\varepsilon)$;

8 $\overline{y}\leftarrow 0$;

9 for  _$i\leftarrow 1$ to $N$_ do

10 $y_{i}\leftarrow sample\ a\ point\ uniformly\ in\ B_{p}(x_{*},r)$ ;

11 if  _$T(F,y_{i},\Omega)=1$_ then

12 $\overline{y}\leftarrow\overline{y}+1$;

13

14 end if

15 if  _$\overline{y}\geq c\cdot N$_ then return $SAT$;

16 if  _$\overline{y} <(c-1)\cdot N+i$_ then return $UNSAT$;

17

18 end for

Algorithm 1 Probabilistic algorithm for $\varepsilon$-weakening robustness
decision problem (Is-$\varepsilon$-robust())

The input parameter $\varepsilon$ can be specified by the safety requirements.
The probabilities of false positive and false negative,$\alpha$ and $\beta$,
are controllable to users. In theory, $p$ can take any positive integer, but
it is difficult to give an efficient uniform sampling algorithm when dimension
$n$ is large. The time complexity of the naive rejection sampling method is
exponential in dimension $n$. $\varepsilon^{\prime}$ can be any value in
$(0,\varepsilon)$ customized by the balance between precision requirements and
running time.

The time complexity of uniformly sampling in $\ell_{1}$-norm ball is
$\mathcal{O}(n\log n)$ in average and $\mathcal{O}(n^{2})$ in the worst case.
Each component of a sampling point is constructed by mutually independent
random variables over $[0,r]$. The time complexity of uniformly sampling in
$\ell_{2}$-norm ball is $\mathcal{O}(n)$. It was first proposed by Muller
(Muller, 1958). The algorithm makes use of a strong property of the Gaussian
distribution that the exponent part is the same as the expression for
calculating the $\ell_{2}$-norm distance. The time complexity of uniformly
sampling in $\ell_{\infty}$-norm ball is $\mathcal{O}(n)$.

We use $t_{s}(n)$ to denote the running time of sampling algorithm and
$t(|F|)$ to denote the execution time of NN for an input. $t(|F|)$ is a
polynomial function of the size of network. So the time complexity of
Algorithm 1 is $\mathcal{O}(N\cdot(t_{s}(n)+t(|F|)))$. Based on statistical
evidence, we can infer the final result before sampling $N$ times (line 14-15
in Algorithm 1). Thus Algorithm 1 can take less time than the theoretical
upper bound.

Next, we analyze the influence of the parameters on Algorithm 1.

  * •

Based on Eq. (6), when $\varepsilon\rightarrow 0$ the sample size
$N\rightarrow\infty$. $N$ is a polynomial function of $1/\varepsilon$.

  * •

When $\varepsilon^{\prime}\rightarrow\varepsilon$, the sample size
$N\rightarrow\infty$ (line 6 of the Algorithm 1 or Eq. (9)). In practical,
when $(\varepsilon-\varepsilon^{\prime})=$$\sigma$ or $0.005$, the number of
samples is about tens of thousands.

  * •

When $\beta\rightarrow 0$, $z_{1-\beta}\rightarrow\infty$. Based on Eq. (9),
we have the sample size $N\rightarrow\infty$. The smaller the probability of
committing a type $II$ error we expect, the more sampling points we need, and
we cannot eliminate the error. The relationship between $\beta$ and $N$ cannot
be expressed by an elementary function, but the increase of $N$ is relatively
flat because of the good properties of the Gaussian distribution.

  * •

When $\alpha\rightarrow 0$, $z_{\alpha}\rightarrow-\infty$. Based on Eq. (9),
we have the sample size $N\rightarrow\infty$. It is similar to $\beta$.

The implementation of our algorithm is parallel on the GPUs.

###  6.2. $\varepsilon$-Robustness Evaluation Algorithm

In this subsection, we present an algorithm for $\varepsilon$-weakened
robustness evaluation problem. It can be tackled on the framework of Turing
reduction. In sec 6.1, we have shown how to decide whether a neural network is
$\varepsilon$-robust for a given radius $r$. So the maximum value of $r$ can
be searched by querying this decision oracle iteratively. This framework can
be used to solve many optimization problems in theory. However, whether it
works in practice depends on the complexity of the decision oracle.

It can be realized in incremental or decremental search but they are not
efficient in practice. We assume that the number of adversarial examples will
increase as the radius increases. Although it has not been rigorously proven,
it is usually the case. Based on this assumption, we can realize an efficient
binary search version such as Algorithm 5.

Input: $F$\- neural classifer, $x_{*}$\- test point, $R$-upper bound for
distortion radius, $p$\- $p$ norm $\varepsilon$\- weakening parameter,
$\alpha$-type $I$ error , $\beta$-type $II$ error

Output: $r_{*}$

1 $r_{min}\leftarrow 0$;

2 $r_{max}\leftarrow R$;

3 while  _$r_{max}-r_{min} >precision$ and $r_{max}\neq 0$ and $r_{min}\neq
R$_ do

4 $r=(r_{max}-r_{min})/2$;

5 if  _Is- $\varepsilon$-robust$(F,x_{*},r,p,\varepsilon,\alpha,\beta)=SAT$_
then

6 $r_{min}\leftarrow r$;

7 else

8 $r_{max}\leftarrow r$;

9 end if

10

11 end while

return $r_{*}\leftarrow r_{min}$

Algorithm 2 Algorithm for $\varepsilon$-weakening robustness evaluating
problem

##  7\. Multi-label Extension

Sometimes, the misclassification of a neural network does not necessarily lead
to disaster. For example, in a self-driving system, if the neural network
recognizes a car as a truck, this situation may not be dangerous. Another
example is that if the neural network recognizes an 80 km speed limit sign as
a 60 km one, the vehicle is safe at this time. Our evaluating method can be
compatible with this situation. We just need to add multiple labels to the set
$\Omega$.

###### Example 7.1.

A point $x_{*}$ is a car and $l_{0}$ is its label. We denote the label of
trucks as $l_{1}$ and minivans as $l_{2}$. Then, let
$\Omega=\\{l_{0},l_{1},l_{2}\\}$, we can evaluate the $\varepsilon$-weakening
robustness of recognizing the possible vehicles.

This extension is inapplicable for conventional robustness, because the
regions of different predictions may not be contiguous. So the robustness
radius can be no change compared with the single label one.

##  8\. Experiments

We implemented our algorithms with Python3. We use the PyTorch deep learning
platform to train and test DNNs. The hardware setups are as follows. CPU:
Intel Xeon Gold 6154 @3.00GHz. GPU: GeForce RTX 2080TI. OS: Ubuntu 18.04.3.

  * •

EWRD is the name of our $\varepsilon$-Weakened Robustness Decision tool111The
link of the tools will be given after the double-blind review..

  * •

EWRE is the name of our $\varepsilon$-Weakened Robustness Evaluation tool1.

ERAN(Singh et al., 2019) which is the state-of-the-art robustness verification
tool for neural networks is used as a reference in our experiment.

MNIST, CIFAR-10, MiniImageNet are used in experiments. The MNIST dataset
consists of handwritten digital images with size 28$\times$28 in 10 classes.
CIFAR-10 dataset consists of color images with size 32$\times$32$\times$3 in
10 classes. MiniImageNet dataset consists of color images with input size
224$\times$224$\times$3 in 100 classes. The value of each pixel is in
$[0,255]$ and the perturbation is considered on the original input images.
$\alpha$ and $\beta$ are set to 0.001 by default in all experiments.

###  8.1. $\varepsilon$-Robustness & Reliability

Q1: _How about the reliability of NNs under the premise of allowing the
existence of some adversarial examples?_

We first compare the $\varepsilon$-robustness with conventional robustness on
CIFAR-10 of a convolutional network which has 4 layers and 7154 neurons. The
experiment is conducted in the context of $\ell_{\infty}$-perturbations
because ERAN does not support other norms. Fig 3(3(a)) shows the robustness
curve given by ERAN. Fig 3(3(b)) shows the robustness curve given by our EWRD
for various $\varepsilon$. We can see that for most regions, perfect safe
radii reported by ERAN are usually smaller than $2$. ERAN uses the abstract
interpretation technique, which is an over-approximation method, so the radius
that can be verified to be safe is usually smaller than the real one. Based on
(Wong et al., 2020; Shafahi et al., 2019), almost all regions of the most
popular NNs will be attacked successfully at $r=8$ on CIFAR-10. However, if a
small proportion of adversarial examples is allowed, the “robust” regions will
become much bigger. When perturbation radius is $18.49$, 70% regions are
$0.001$-robust.

Then we show the experimental results on four popular DNNs: ResNet18 (He et
al., 2016), RegNetX (Radosavovic et al., 2020), DenseNet121 (Huang et al.,
2017b) and DPN92 (Dual Path Networks) (Chen et al., 2017). These networks are
difficult for conventional robustness verification tools. So we omit the
results about conventional robustness. We apply EWRD to these networks on
CIFAR-10 for $\varepsilon\in\\{0.01,0.1,0.15,0.2\\}$. The robustness curves
are shown in Fig 4. Take ResNet18 in Fig 4 (4(a)) for an example, when
perturbation radius $r$ is smaller than $12.75$, more than 90% test points
satisfy $0.01$-robustness. That means most areas (90%) of the network can
perform well against a perturbation within distance $12.75$ and the
probability of misclassification is less than $0.01$. However, when we
increase perturbation $r$ to $76.5$, there are only 25% regions satisfying
$0.2$-robustness. In other words, most areas (75%) of the network are
vulnerable to such perturbations. They may yield to a perturbation with a
probability of more than 20%. We also find that when the radius is greater
than a certain threshold, the number of adversarial examples will increase
sharply. So the distance among curves of $\varepsilon=0.1,0.15,0.2$ is very
close.

(a) ERAN

(b) EWRD

Figure 3.  Comparing the robustness and $\varepsilon$-robustness curves of the
same neural network on CIFAR-10 ($p=\infty$). $x$-axis is the given radius $r$
and $y$-axis is the percent of regions reported to be
robust/$\varepsilon$-robust.

(a) ResNet18

(b) RegNetX

(c) DenseNet121

(d) DPN92

Figure 4.  The $\varepsilon$-robustness curves of different neural networks on
CIFAR-10 ($p$=$\infty$). $x$-axis is the given radius $r$ and $y$-axis is the
percent of regions reported to be $\varepsilon$-robust.

We also compare the reliability performance under different settings of norm
($p=\\{1,2,\infty\\}$) and apply EWRE to pretrained networks in Pytorch (VGG19
(Simonyan and Zisserman, 2015) and AlexNet (Krizhevsky et al., 2017) on
ImageNet) as shown in Figure 5. With the increase of dimension $n$, we have:

$\lim\limits_{n\rightarrow\infty}\frac{Vol(B_{1}(x_{*},r))}{Vol(B_{2}(x_{*},r))}=0\
\ and\\\
\lim\limits_{n\rightarrow\infty}\frac{Vol(B_{2}(x_{*},r))}{Vol(B_{\infty}(x_{*},r))}=0$

So, the values of $\varepsilon$-robustness radius decrease greatly as $p$
increases in $\\{1,2,\infty\\}$. However, their changing trends are almost the
same.

(a) $\ell_{1}\ (p=1)$

(b) $\ell_{2}\ (p=2)$

(c) $\ell_{\infty}\ (p=\infty)$

Figure 5.  (ImageNet) The $\varepsilon$-robustness radii ($y$-axis) of the
same input point for VGG19 and AlexNet while the values of $\varepsilon$ vary
from $0.001$ to $0.8$.

###  8.2. $\varepsilon$-Robustness & The Quality of NNs

Q2: _Can $\varepsilon$-robustness be used to reveal some potential problems
about the quality of neural networks?_

In this experiment, we study whether $\varepsilon$-robustness analysis results
can reveal the quality differences among the NNs with similar structure and
reported accuracy. We trained 5 convolutional networks with almost the same
structure on MNIST and they report almost the same accuracy on the test set.

  * •

Conv-Base achieves 98.97% accuracy. It is a well-trained baseline model
consisting of two convolutional layers, two fully connected layers, and
176,650 neurons in all.

  * •

Conv-Overfit achieves 98.88% accuracy. We overtrain the Cov-Base so that the
training error is close to 0. It simulates the overfitting situation.

  * •

Conv-NoPooling achieves 99.03% accuracy. We remove the max-pooling layer which
is designed to improve the robustness of neural networks.

  * •

Conv-NoNorm achieves 98.41% accuracy. We remove the normalization operation.
It simulates a situation where a programmer forgot it.

  * •

Conv-Imbalance report 98.66% accuracy. We remove 90% training and testing data
in class ‘5’. It simulates the situation that a network is trained and tested
on an imbalanced data set.

From the view of their reported accuracies on the test set, it is difficult to
distinguish their quality differences. We study their $\varepsilon$-robustness
performances further. We set $\varepsilon=0.02$. Figure 6 shows the results of
$0.02$-robustness radii evaluated by EWRE. From it, we observe that: (1) The
mean values of $0.02$-robustness radius on the Conv-Overfit, Conv-NoPooling,
and Conv-NoNorm are smaller than that of the baseline model, Conv-Base. For
the other values of $\varepsilon$, the relative relationship is consistent and
this has been shown in the previous experiment. (2) The $0.02$-robustness
radii decrease most by lack of the normalization operation (Conv-NoNorm).
Usually, normalization is the first step for proceeding with various computer
vision tasks. In some sense, our $\varepsilon$-robustness metric can provide
evidence to support that it indeed plays an important role.

Figure 7 presents the scatter plots of $0.02$-robustness radius $r$ for Conv-
Imbalance and the images of the same class are rearranged together. For class
‘5’, the $0.02$-robustness radii of points are distributed in the
significantly lower value area and its mean value (marked by a triangle) is
the smallest compared with other classes. It demonstrates that the unbalanced
experimental situation can decrease the $\varepsilon$-robustness radius of the
neural network for the unbalanced class. Our method has the potential to
detect such problems.

(a) Conv-Base

(b) Conv-Overfit

(c) Conv-NoPooling

(d) Conv-NoNorm

Figure 6.  $\varepsilon$-robustness radii distribution on 1000 (random 100 for
each class) test images of MNIST for four neural networks ($p$=$2$). Green
(middle) lines mark means. Upper (lower) red lines mark the mean plus (minus)
twice the standard deviation.

(a) Conv-Imbalance (p=2)

(b) Conv-Imbalance (p=$\infty$)

Figure 7.  $\varepsilon$-robustness radii on 1000 (random 100 for each class)
test images of MNIST for the neural network trained on imbalanced data set.
Each color represents a class. Points in class ‘5’ are in red color and
circled. Black triangles denote their means.

###  8.3. $\varepsilon$-Robustness of Misclassified Points

Q3: _How about the $\varepsilon$-robustness of the regions around
misclassified points or adversarial examples?_

Conventional robustness analysis can not be applied to the regions around
misclassified points adversarial examples because these regions are not robust
according to the definition. In practical application, an input is possibly in
the regions around some misclassified points, which are also worthy to be
analyzed. Thus, we designed the experiments to analyze the
$\varepsilon$-robustness of four popular DNNs (ResNet18, RegNetX, DenseNet121
and DPN92) in the regions around misclassified points for CIFAR-10.

First, we evaluate the average $\varepsilon$-robustness radii of these four
neural networks via EWRE for correctly-classified points and the results are
shown in Table 2. Then, for each neural network, we run EWRD on all
misclassified points in the test set and assign $r$ to the average
$\varepsilon$-robustness radius. Figure 8 shows the percent of
$\varepsilon$-robust regions around misclassified points. We observe that the
performance of neural networks in these regions is not necessarily very poor.
Take RegNetX as an example, 4.18% adversarial examples satisfy
$0.01$-robustness with perturbation radius 52.86. That means although RegNetX
commits errors at the centers of these regions, it often (with
probability¿99%) works well in the neighborhoods. Besides, as we expected,
there will be more regions satisfying $\varepsilon$-robustness if we can
tolerate more adversarial examples.

It is worth mentioning that EWRE can not be directly applied to the
misclassified points, because it will invalidate the premise of binary search.
Although the decremental search (gradually decreasing the radius) can be
applied in theory, its practical efficiency is very low. Therefore, for such
misclassified points, the radius should be set in advance according to
application requirements.

Table 2. (CIFAR-10) The average $\varepsilon$-robustness radii ($\ell_{\infty}$). Networks | $\varepsilon=0.01$ | $\varepsilon=0.1$ | $\varepsilon=0.15$ | $\varepsilon=0.20$
---|---|---|---|---
ResNet18 | 59.47 | 68.53 | 71.24 | 73.49
RegNetX | 52.86 | 67.45 | 70.27 | 72.68
DenseNet121 | 41.17 | 62.36 | 64.31 | 61.75
DPN92 | 34.44 | 49.19 | 54.87 | 59.83
Figure 8. The percentage of regions reported to be $\varepsilon$-robustness
around misclassified points.

###  8.4. Efficiency

Q4: _How about the efficiency of EWRD and EWRE?_

In this section, we test the efficiency of our algorithms for various networks
and parameter settings. Firstly, we compared the efficiency of EWRD with ERAN
on the same networks only for reference as they focus on different problems.
When the value of $\varepsilon$ is very small, the $\varepsilon$-robustness
decision problem and conventional robustness verification problem are very
close. So we compare the running time via setting
$\varepsilon\in\\{0.0001,0.001\\}$ in our experiment. Table 3 shows the
results of the average running time. We observe that EWRD performs much more
efficiently than ERAN. For conventional robustness verification problem, the
soundness methods may encounter efficiency problems for large-scale networks
and datasets.

Table 3. The average running time of EWRD and ERAN on different neural
networks. ($p$=$\infty$)

Networks | Information | EWRD(s) | ERAN(s)
---|---|---|---
#Layers | #Neurons | $\varepsilon=0.0001$ | $\varepsilon=0.001$
FullyCon-MNIST | 4 | 3,072 | 4.80 | 0.38 | 26.90
ConvBig-MNIST | 6 | 48,064 | 2.68 | 0.55 | 3.03
ConvSuper-MNIST | 6 | 88,544 | 5.16 | 0.63 | 32.04
FullyCon-CIFAR10 | 7 | 6,144 | 5.87 | 0.51 | 529.89
ConvBig-CIFAR10 | 6 | 62,464 | 5.03 | 0.51 | 94.83
ResNet18-CIFAR10 | 18 | 558,080 | 40.07 | 3.34 | 2971.37

Next, we test the average running time (seconds) of EWRD and EWRE for
different $\varepsilon$ values on different networks and data sets which are
shown in Table 4. We can see that the dimensionality of inputs has the
greatest impact on running time. Even for the Alexnet on ImageNet, which
contains much fewer layers compared with DenseNet121 on CIFAR-10, EWRD and
EWRE take much more running time. With the increase of $\varepsilon$, the
running time decreases first and then increases, which is consistent with the
functional relationship between $N$ and $\varepsilon$ in Algorithm 1.

Table 4. The average running time of EWRD and EWRE on different neural
networks. ($p$=$\infty$)

Networks | Information | $\varepsilon=0.001$ | $\varepsilon=0.01$ | $\varepsilon=0.10$ | $\varepsilon=0.20$
---|---|---|---|---|---
#Layers | Data sets | EWRD(s) | EWRE(s) | EWRD(s) | EWRE(s) | EWRD(s) | EWRE(s) | EWRD(s) | EWRE(s)
FullyCon | 4 | MNIST | 0.31 | 3.56 | 0.02 | 0.35 | 0.41 | 4.97 | 1.38 | 16.19
Conv1 | 4 | MNIST | 0.73 | 8.60 | 0.06 | 0.79 | 0.98 | 11.63 | 3.16 | 37.87
ResNet18 | 18 | CIFAR-10 | 3.34 | 40.85 | 0.30 | 3.40 | 4.05 | 50.12 | 12.89 | 153.40
RegNetX | 20 | CIFAR-10 | 4.03 | 46.84 | 0.37 | 4.33 | 5.47 | 63.90 | 17.52 | 208.30
DPN92 | 92 | CIFAR-10 | 7.50 | 90.02 | 0.71 | 8.54 | 10.11 | 118.04 | 30.68 | 405.11
DenseNet121 | 121 | CIFAR-10 | 8.60 | 101.45 | 0.91 | 9.71 | 12.06 | 133.32 | 35.80 | 437.68
Alexnet | 8 | ImageNet | 34.2 | 393.34 | 3.38 | 38.86 | 44.73 | 525.13 | 165.50 | 1942.96
VGG19 | 19 | ImageNet | 49.43 | 544.03 | 4.86 | 54.36 | 64.30 | 738.65 | 216.80 | 2706.32
ResNet50 | 50 | ImageNet | 46.31 | 462.19 | 4.42 | 45.35 | 63.30 | 602.64 | 227.88 | 2169.50

We further study the effect of $\alpha$ and type $\beta$ on the execution
efficiency of Algorithm 1. The smaller $\alpha$ and $\beta$ are, the more
sampling points the algorithm needs. Figure 9 shows that, with the exponential
decrease of $\alpha$ and $\beta$, the execution time of the algorithm does not
increase exponentially which is attributed to the good property of the normal
distribution. Although the sampling points $N\rightarrow\infty$ when
$\alpha\rightarrow 0$ and $\beta\rightarrow 0$, this trend is not so fast.
Besides, for different values of $p$, the execution efficiency of the sampling
algorithm is also different as the time complexities are different as
described in section 6.1. For $p$=$1$, EWRE and EWRD consume the longest time
compared with other norms.

Figure 9.  Comparing the running time of EWRD with respect to different values
of $\alpha$ and $\beta$ on a given input. When $\alpha$ varies, $\beta=0.001$.
When $\beta$ changes, $\alpha=0.001$. The $x$-axis is in logarithmic scale.
Network: RegNetX. Data set: CIFAR-10.

###  8.5. Multi-labels Extension

Q5: _How about the $\varepsilon$-robustness in multi-labels extension?_

In practical application, a neural network can make a mistake but it does not
mean a disaster. Figure 10 shows two examples in which ResNet18 recognizes a
car as a truck and a plane respectively under random perturbations. When
misclassifying a car as a truck, there may be no dangers for a self-driving
system to make a decision to avoid the vehicle ahead. But it may be dangerous
for the second case (misclassifying a car as a plane) as the self-driving
system will make a wrong decision of no evasive action. Figure 11 shows the
values of the $\varepsilon$-robustness radius of a given input image (labeled
‘Car’) on ResNet18 calculated by EWRE when
$\Omega=\\{`Car^{\prime},`Truck^{\prime}\\}$. Compared with the case of
$\Omega=\\{`Car^{\prime}\\}$, the $\varepsilon$-robustness radius of the
multi-label extension ($\Omega=\\{`Car^{\prime},`Truck^{\prime}\\}$) is
significantly improved. When the $\varepsilon$-robustness radius is $42.21$,
the risk of recognizing the car as a label out of $\Omega$ is less than
$0.001$ under a random perturbation.

Figure 10. Adversarial examples on ResNet18 generated by adding random
perturbation to images with label ‘Car’. Figure 11. $\varepsilon$-robustness
radii for a given image with the real label ‘Car’ on ResNet18. ($p$=$\infty$)

##  9\. Related Work

In recent years, there have been a lot of works on certifying or evaluating
the robustness of NNs.

Conventional robustness verification can be mainly divided into three
categories. (1) Precise methods are based on Mixed Integer Linear Programming
(MLP) (Fischetti and Jo, 2018; Dutta et al., 2018) or SMT (Katz et al., 2017;
Ehlers, 2017). For specific types of NN, these methods have both completeness
and soundness. It means that if the decision procedure returns “robust”, the
neural network is robust w.r.t. the specified perturbation radius, otherwise,
there exist adversarial examples. However, these methods can only tackle small
networks at present; (2) Incomplete methods which apply overapproximation
techniques to scale up to medium-sized networks, which are sound but may fail
to prove robustness even if it holds, such as abstract interpretation (Gehr et
al., 2018; Singh et al., 2018; Singh et al., 2019), linear approximations(Weng
et al., 2018a; Wong and Kolter, 2018), semidefinite relaxations (Raghunathan
et al., 2018) or search space discretization (Huang et al., 2017a). These
methods suffer from a loss of precision when the neural networks are deep.
Besides, they are limited to the types of networks and norms. (3) Estimation
methods, including the method based on extreme value theory (Weng et al.,
2018b) and randomized smoothing (Cohen et al., 2019; Jia et al., 2020), can
scale to large networks (e.g. ImageNet classifier). These methods have neither
soundness nor completeness which means when the decision procedure returns
“robust”, the network can be either robust or have adversarial examples.
Although randomized smoothing provides a probability guarantee, the radius
which can be verified around a point vanishes when $p>2$ as recent studies
(Hayes, 2020; Kumar et al., 2020) show.

In quantitative analysis or verification, some methods are proposed to
estimate the proportion of inputs violating a property. So they also can be
applied to estimate the proportion of adversarial examples. Webb et al. (Webb
et al., 2019) use a multi-level splitting sampling method to estimate the
proportion of adversarial examples. However, it has no formal guarantees about
the estimation results. In 2019, Baluta et al.(Baluta et al., 2019) proposed a
white-box verification approach based on the model counting technique. It can
be used to estimate the interval of adversarial examples’ numbers with a
formal guarantee. However, this approach is limited to binarized neural
networks and takes 20 hours to verify robustness for a point when the network
has more than 50, 000 parameters. These works focus on quantitative analysis
(computing the number or proportion of adversarial examples) which is
#$P$-hard. Moreover, the estimated value can not be directly used to determine
whether a system meets safety standards because the real value can be either
over or below the threshold and the probability of making a wrong decision is
unknown. After introducing $\varepsilon$, we reduce the computational
complexity to $PP$. In this context, we can provide an efficient method to
answer whether the proportion of adversarial examples is less than
$\varepsilon$ with provable guarantees.

Our statistical approach to $\varepsilon$-robustness decision problem also can
be regarded as statistical model checking (Clarke et al., 2008; Clarke and
Zuliani, 2011). Statistical model checking is traditionally used to reason
about properties specified in a stochastic temporal logic for analyzing the
behavior of complex stochastic systems. To our best knowledge, it has not been
applied to analyze neural networks. Besides, there is no general method that
can determine the sample size required for an arbitrary system (Agha and
Palmskog, 2018) and the time complexity of the decision procedure is related
to the system and properties.

##  10\. Conclusion

We formalize a robustness metric named $\varepsilon$-weakened robustness which
can be used to analyze the reliability and stability of deep neural networks.
Compared with the conventional robustness analysis, $\varepsilon$-robustness
analysis can provide conclusive results about more regions of NNs. As the
$\varepsilon$-robustness decision problem is $PP$-complete, we propose a
probabilistic algorithm with user-controllable error bound to solve it. Based
on the decision oracle, we further provide an efficient algorithm to find the
maximum $\varepsilon$-robustness radius. The time complexity of our algorithm
is polynomial in the dimension and size of the network. Experimental results
present the scalability of our methods to large neural networks.

##  11\. Notification

This work was completed in November 2020, but the paper was not published. The
patent was applied in 2020.

## References

  * (1)
  * Agha and Palmskog (2018) Gul Agha and Karl Palmskog. 2018.  A Survey of Statistical Model Checking.  _ACM Trans. Model. Comput. Simul._ 28, 1 (2018), 6:1–6:39.
  * Baluta et al. (2019) Teodora Baluta, Shiqi Shen, Shweta Shinde, Kuldeep S. Meel, and Prateek Saxena. 2019.  Quantitative Verification of Neural Networks and Its Security Applications. In _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, London, UK, November 11-15, 2019_. 1249–1264.
  * Chen et al. (2018) Pin-Yu Chen, Yash Sharma, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. 2018.  EAD: Elastic-Net Attacks to Deep Neural Networks via Adversarial Examples. In _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018_. 10–17.
  * Chen et al. (2017) Yunpeng Chen, Jianan Li, Huaxin Xiao, Xiaojie Jin, Shuicheng Yan, and Jiashi Feng. 2017\.  Dual Path Networks. In _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA_. 4467–4475.
  * Clarke et al. (2008) Edmund M. Clarke, James R. Faeder, Christopher James Langmead, Leonard A. Harris, Sumit Kumar Jha, and Axel Legay. 2008.  Statistical Model Checking in BioLab: Applications to the Automated Analysis of T-Cell Receptor Signaling Pathway. In _Computational Methods in Systems Biology, 6th International Conference, CMSB 2008, Rostock, Germany, October 12-15, 2008. Proceedings_. 231–250.
  * Clarke and Zuliani (2011) Edmund M. Clarke and Paolo Zuliani. 2011.  Statistical Model Checking for Cyber-Physical Systems. In _Automated Technology for Verification and Analysis, 9th International Symposium, ATVA 2011, Taipei, Taiwan, October 11-14, 2011. Proceedings_. 1–12.
  * Cohen et al. (2019) Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. 2019\.  Certified Adversarial Robustness via Randomized Smoothing. In _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_. 1310–1320.
  * Dutta et al. (2018) Souradeep Dutta, Susmit Jha, Sriram Sankaranarayanan, and Ashish Tiwari. 2018.  Output Range Analysis for Deep Feedforward Neural Networks. In _NASA Formal Methods - 10th International Symposium, NFM 2018, Newport News, VA, USA, April 17-19, 2018, Proceedings_. 121–138.
  * Ehlers (2017) Rüdiger Ehlers. 2017\.  Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks. In _Automated Technology for Verification and Analysis - 15th International Symposium, ATVA 2017, Pune, India, October 3-6, 2017, Proceedings_. 269–286.
  * Fischetti and Jo (2018) Matteo Fischetti and Jason Jo. 2018.  Deep neural networks and mixed integer linear optimization.  _Constraints An Int. J._ 23, 3 (2018), 296–309.
  * Gehr et al. (2018) Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen, Petar Tsankov, Swarat Chaudhuri, and Martin T. Vechev. 2018.  AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation. In _2018 IEEE Symposium on Security and Privacy, SP 2018, Proceedings, 21-23 May 2018, San Francisco, California, USA_. 3–18.
  * Goodfellow et al. (2015) Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. 2015.  Explaining and Harnessing Adversarial Examples. In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * Hayes (2020) Jamie Hayes. 2020\.  Extensions and limitations of randomized smoothing for robustness guarantees. In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR Workshops 2020, Seattle, WA, USA, June 14-19, 2020_. 3413–3421.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016\.  Deep Residual Learning for Image Recognition. In _2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016_. 770–778.
  * Huang et al. (2017b) Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. 2017b.  Densely Connected Convolutional Networks. In _2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017_. 2261–2269.
  * Huang et al. (2017a) Xiaowei Huang, Marta Kwiatkowska, Sen Wang, and Min Wu. 2017a.  Safety Verification of Deep Neural Networks. In _Computer Aided Verification - 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part I_. 3–29.
  * III (1974) John T. Gill III. 1974\.  Computational Complexity of Probabilistic Turing Machines. In _Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1974, Seattle, Washington, USA_ , Robert L. Constable, Robert W. Ritchie, Jack W. Carlyle, and Michael A. Harrison (Eds.). ACM, 91–95.
  * Jia et al. (2020) Jinyuan Jia, Xiaoyu Cao, Binghui Wang, and Neil Zhenqiang Gong. 2020\.  Certified Robustness for Top-k Predictions against Adversarial Perturbations via Randomized Smoothing. In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_.
  * Kalra and Paddock (2016) Nidhi Kalra and Susan M Paddock. 2016.  Driving to safety: How many miles of driving would it take to demonstrate autonomous vehicle reliability?  _Transportation Research Part A: Policy and Practice_ 94 (2016), 182–193.
  * Katz et al. (2017) Guy Katz, Clark W. Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. 2017\.  Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks. In _Computer Aided Verification - 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part I_. 97–117.
  * Koopman and Osyk (2019) Philip Koopman and Beth Osyk. 2019.  Safety argument considerations for public road testing of autonomous vehicles.  _SAE International Journal of Advances and Current Practices in Mobility_ 1, 2019-01-0123 (2019), 512–523.
  * Krizhevsky et al. (2017) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. 2017\.  ImageNet classification with deep convolutional neural networks.  _Commun. ACM_ 60, 6 (2017), 84–90.
  * Kumar et al. (2020) Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. 2020.  Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness. In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_. 5458–5467.
  * Muller (1958) Box G. E. P.and Mervin E. Muller. 1958\.  A Note on the Generation of Random Normal Deviates.  _The Annals of Mathematical Statistics_ 29, 2 (1958), 610–611.
  * Radosavovic et al. (2020) Ilija Radosavovic, Raj Prateek Kosaraju, Ross B. Girshick, Kaiming He, and Piotr Dollár. 2020\.  Designing Network Design Spaces. In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020_. 10425–10433.
  * Raghunathan et al. (2018) Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. 2018\.  Semidefinite relaxations for certifying robustness to adversarial examples. In _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada_. 10900–10910.
  * Ruan et al. (2018) Wenjie Ruan, Xiaowei Huang, and Marta Kwiatkowska. 2018\.  Reachability Analysis of Deep Neural Networks with Provable Guarantees. In _Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden_. 2651–2659.
  * Shafahi et al. (2019) Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John P. Dickerson, Christoph Studer, Larry S. Davis, Gavin Taylor, and Tom Goldstein. 2019.  Adversarial training for free!. In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_. 3353–3364.
  * Simonovits (2003) Miklós Simonovits. 2003\.  How to compute the volume in high dimension?  _Mathematical programming_ 97, 1-2 (2003), 337–374.
  * Simonyan and Zisserman (2015) Karen Simonyan and Andrew Zisserman. 2015.  Very Deep Convolutional Networks for Large-Scale Image Recognition. In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * Singh et al. (2018) Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin T. Vechev. 2018\.  Fast and Effective Robustness Certification. In _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada_. 10825–10836.
  * Singh et al. (2019) Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin T. Vechev. 2019.  An abstract domain for certifying neural networks.  _Proc. ACM Program. Lang._ 3, POPL (2019), 41:1–41:30.
  * Stutz et al. (2019) David Stutz, Matthias Hein, and Bernt Schiele. 2019\.  Disentangling Adversarial Robustness and Generalization. In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019_. 6976–6987.
  * Szegedy et al. (2014a) Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. 2014a.  Intriguing properties of neural networks. In _2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings_.
  * Szegedy et al. (2014b) Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. 2014b.  Intriguing properties of neural networks. In _2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings_.
  * Valiant (1984) Leslie G. Valiant. 1984\.  A Theory of the Learnable. In _Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA_. 436–445.
  * Webb et al. (2019) Stefan Webb, Tom Rainforth, Yee Whye Teh, and M. Pawan Kumar. 2019.  A Statistical Approach to Assessing Neural Network Robustness. In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_.
  * Weng et al. (2018a) Tsui-Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane S. Boning, and Inderjit S. Dhillon. 2018a.  Towards Fast Computation of Certified Robustness for ReLU Networks. In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_. 5273–5282.
  * Weng et al. (2018b) Tsui-Wei Weng, Huan Zhang, Pin-Yu Chen, Jinfeng Yi, Dong Su, Yupeng Gao, Cho-Jui Hsieh, and Luca Daniel. 2018b.  Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach. In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_.
  * Wong and Kolter (2018) Eric Wong and J. Zico Kolter. 2018.  Provable Defenses against Adversarial Examples via the Convex Outer Adversarial Polytope. In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_. 5283–5292.
  * Wong et al. (2020) Eric Wong, Leslie Rice, and J. Zico Kolter. 2020.  Fast is better than free: Revisiting adversarial training. In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_.

##  12\. Appendices

###  12.1. Complexity Proof

First, we will introduce a PP-complete problem called MAJORITY SAT
(MAJSAT($\geq 2^{n-1}$)): given a CNF-formula $\varphi$ with $n$ variables
$\\{x_{1}...x_{n}\\}$, is it satisfied by at least half of the possible truth
assignments? To facilitate follow-up proof, we denote the variant version as
MAJSAT’($>2^{n-1}$) which can be easily reduced from MAJSAT in polynomial
time. Let

$\displaystyle\psi=$ $\displaystyle x_{1}\vee(\neg x_{1}\wedge
x_{2}\wedge...\wedge x_{n})$ $\displaystyle(x_{1}\vee
x_{2})\wedge...\wedge(x_{1}\vee x_{n}))$

We know that $\psi$ has $2^{n-1}+1$ truth assignments.

$\varphi^{\prime}=(\neg p\wedge\varphi)\vee(p\wedge\psi)$

where $p$ is an added variable and $\varphi^{\prime}$ can be easily
transformed to CNF in polynomial time via distributive law. Assuming $\varphi$
has $m$ truth assignments. So $\varphi^{\prime}$ has $m+2^{n-1}+1$ truth
assignments and $n+1$ variables. We can query MAJSAT’ whether
$\varphi^{\prime}$ is satisfied by at least $(2^{n+1}/2=2^{n})$ assignments.
If yes, we have $m+2^{n-1}+1>2^{n}$ which can be rewritten as $m\geq 2^{n-1}$.
Otherwise, we have $m<2^{n-1}$.

###### Theorem 12.1.

If the input space $\mathbb{D}^{n}$ is a countable set,
$\varepsilon$-robustness decision problem is $PP$-complete.

###### Proof.

We first show that the problem is in PP. We prove that the
$\varepsilon$-robustness decision problem is solvable by a probabilistic
algorithm in polynomial time, with an error probability of less than $1/2$ for
all instances. Consider a probabilistic algorithm that, chooses an $x$
uniformly at random in $B_{p}(x_{*},r)$. Then, the algorithm tosses a coin
that every outcome is equal.

  * •

If the coin comes up heads, chooses an $x$ uniformly at random in
$B_{p}(x_{*},r)$. Then, check if $x$ makes $T(F,x,\Omega)=1$. If yes, output
SAT. If no, output UNSAT.

  * •

If the coin comes up tails, the algorithm will outputs SAT with probability
$(\varepsilon-1/|\mathbb{D}|^{n+1})$ and UNSAT with probability
$(1-\varepsilon+1/|\mathbb{D}|^{n+1})$.

If the neural network is $\varepsilon$-robust, $p_{r}>1-\varepsilon$ and it is
equivalent to $p_{r}\geq 1-\varepsilon+1/|\mathbb{D}|^{n}$. The algorithm will
always output SAT with probability:

(11)
$\displaystyle\frac{1}{2}(1-\varepsilon+\frac{1}{|\mathbb{D}|^{n}})+\frac{1}{2}(\varepsilon-\frac{1}{|\mathbb{D}|^{n+1}})$
$\displaystyle=\frac{1}{2}+\frac{1}{2}(\frac{1}{|\mathbb{D}|^{n}}-\frac{1}{|\mathbb{D}|^{n+1}})>\frac{1}{2}$

If the neural network is not $\varepsilon$-robust, $p_{r}\leq 1-\varepsilon$.
The algorithm will always output SAT with probability:

(12)
$\displaystyle\frac{1}{2}(1-\varepsilon)+\frac{1}{2}(\varepsilon-\frac{1}{|\mathbb{D}|^{n+1}})$
$\displaystyle=\frac{1}{2}-\frac{1}{2}\frac{1}{|\mathbb{D}|^{n+1}}<\frac{1}{2}$

Thus this algorithm puts $\varepsilon$-weakened robustness decision problem in
PP.

Next, we show the reduction from the MAJSAT’($>2^{n-1}$). Any SAT formula
$\varphi=C_{1}\wedge C_{2}\wedge...\wedge C_{m}$ can be transformed into a DNN
with ReLUs. Input variables are mapped to each $t_{i}$ node according to the
definition of clause $C_{i}$ and $y_{i}$ will be equal to 1 if clause $C_{i}$
is satisfied, and will be 0 otherwise. Fig 12 shows the method to construct a
“Not” gadget and a clause $C_{m}$. The clause gadget can be regarded as
calculating the expression:

$y_{m}=1-\max(0,1-\sum_{j=1}^{k}l_{j})$

Then, we add an extra output node $o_{2}$ with input 1 and set edge weight to
$m-0.5$ in the last layer (Fig 13 is a schematic). If $o_{1}>o_{2}$, the
network outputs lable $l_{1}$. Otherwise, it outputs lable $l_{2}$. Therefore,
the output will be $l_{1}$ if and only if all clauses are simultaneously
satisfied.

Let $\Omega=\\{l_{1}\\}$, $p=\infty$, $r=1$,$\varepsilon=1/2$ and
$x_{*}=[0,0,...,0]$. Then we have that the SAT formula $\varphi$ has at least
$2^{n-1}$ assignments if and only if the neural network is $1/2$-weakened
robust. ∎

Figure 12. The “Not” gadget and “Clause” gadget. Figure 13. The network

###  12.2. Sampling Algorithms

In this section, uniform sampling algorithms in $\ell_{1}$, $\ell_{2}$ and
$\ell_{\infty}$-norm balls are given.

Algorithm 1 outlines the method to sample a point uniformly in
$B_{1}(x_{*},r)$.

Input: $x_{*}$\- test point, $r$-distortion radius

Output: $y=(y^{(1)}...y^{(n)})$

1 $y^{\prime}\leftarrow(y^{\prime(0)}...y^{\prime(n)})$;

2 $y^{\prime(0)}\leftarrow 0$;

3 for  _$i\leftarrow 1$ to $n$_ do

4 $y^{\prime(i)}\sim\mathcal{U}(0,r)$ // Uniform distribution

5 end for

6$y^{\prime(1)}...y^{\prime(n)}\leftarrow
Sort(y^{\prime(1)}...y^{\prime(n)})$; // Ascending order

7for  _$i\leftarrow 1$ to $n$_ do

8 $y^{(i)}\leftarrow RandomSign\cdot(y^{\prime(i)}-y^{\prime(i-1)})$;

9

10 end for

11$y\leftarrow y+x_{*}$;

return $y$

Algorithm 3 Sample a point uniformly in $B_{1}(x_{*},r)$

Algorithm 1 makes use of the uniform spacings to construct the random sampling
point (Devroye86). We know that
$\sum_{i=1}^{n}|y^{\prime(i)}-y^{\prime(i-1)}|=y^{\prime(n)}\leq r$, so the
sample point is in $B_{1}(x_{*},r)$. The average-case time complexity of
Algorithm 1 is $\mathcal{O}(n\log n)$ and the worst case is
$\mathcal{O}(n^{2})$.

Algorithm 2 outlines the method to sample a point uniformly in
$B_{2}(x_{*},r)$.

Input: $x_{*}$\- test point, $r$-distortion radius

Output: $y=(y^{(1)}...y^{(n)})$

1 $y^{\prime}\leftarrow(y^{\prime(1)}...y^{\prime(n)})$;

2 for  _$i\leftarrow 1$ to $n$_ do

3 $y^{\prime(i)}\sim\mathcal{N}(0,1)$;

4

5 end for

6$s\leftarrow\sum\nolimits_{i=1}^{n}(y^{\prime(i)})^{2}$; //
$\left\|y^{\prime}\right\|_{2}^{2}$

7$\kappa\leftarrow\Gamma(n/2,s/2)^{\frac{1}{n}}$; // Incomplete gamma function

8for  _$i\leftarrow 1$ to $n$_ do

9 $y^{(i)}\leftarrow\frac{r\cdot\kappa\cdot y^{\prime(i)}}{\sqrt{s}}$;

10

11 end for

12$y\leftarrow y+x_{*}$;

return $y$

Algorithm 4 Sample a point uniformly in $B_{2}(x_{*},r)$

This algorithm was first proposed by Muller (Muller, 1958). It makes use of a
strong property that the exponent part of joint Gaussian distribution is the
same as the expression for calculating the $\ell_{2}$-norm. The time
complexity of this method is $\mathcal{O}(n)$.

Algorithm 3 outlines the method to sample a point uniformly in
$B_{\infty}(x_{*},r)$ and the time complexity is $\mathcal{O}(n)$.

Input: $x_{*}$\- test point, $r$-distortion radius

Output: $y=(y^{(1)}...y^{(n)})$

1 for  _$i\leftarrow 1$ to $n$_ do

2 $y^{(i)}\sim\mathcal{U}(-r,r)$;

3

4 end for

5$y\leftarrow y+x_{*}$;

return $y$

Algorithm 5 Sample a point uniformly in $B_{\infty}(x_{*},r)$