# Sound randomized smoothing in floating-point arithmetics

Václav Voráček
University of Tübingen &Matthias Hein
University of Tübingen

###### Abstract

Randomized smoothing is sound when using infinite precision. However, we show
that randomized smoothing is no longer sound for limited floating-point
precision. We present a simple example where randomized smoothing certifies a
radius of $1.26$ around a point, even though there is an adversarial example
in the distance $0.8$ and extend this example further to provide false
certificates for CIFAR10. We discuss the implicit assumptions of randomized
smoothing and show that they do not apply to generic image classification
models whose smoothed versions are commonly certified. In order to overcome
this problem, we propose a sound approach to randomized smoothing when using
floating-point precision with essentially equal speed and matching the
certificates of the standard, unsound practice for standard classifiers tested
so far. Our only assumption is that we have access to a fair coin.

##  1 Introduction

Shortly after the advent of deep learning, it was observed in (Szegedy et al.,
2014) that there exist adversarial examples, i.e., small imperceptible
modifications of the input which change the decision of the classifier. This
property is of major concern in application areas where safety and security
are critical such as medical diagnosis or in autonomous driving. To overcome
this issue, a lot of different defenses have appeared over the years, but new
attacks were proposed and could break these defenses, see, e.g., (Athalye et
al., 2018; Croce and Hein, 2020; Tramer et al., 2020; Carlini et al., 2019).
The only empirical (i.e., without guarantees) method which seems to work is
adversarial training (Goodfellow et al., 2015; Madry et al., 2018) but also
there, a lot of defenses turned out to be substantially weaker than originally
thought (Croce and Hein, 2020).

Hence, there has been a focus on certified robustness. Here, the aim is to
produce certificates assuring no adversarial example exists in a small
neighborhood of the original image. This small neighborhood, typically called
a threat model, is usually established as an $\ell_{p}$ ball centered at the
original image. However, there also exist other choices for this, such as a
Wasserstein ball (Wong et al., 2019) or a ball induced by perceptual metrics
(Laidlaw et al., 2021).

The common certification techniques include (1) Bounding the Lipschitz
constant of the network, see (Hein and Andriushchenko, 2017; Li et al., 2019;
Trockman and Kolter, 2021; Leino et al., 2021; Singla et al., 2022) for
$\ell_{2}$ threat model and (Zhang et al., 2022) for $\ell_{\infty}$. (2)
Overapproximating the threat model by its convex relaxation (Admittedly,
bounding Lipschitz constant can also be interpreted this way), possibly
combined with mixed-integer linear programs or SMT; see, e.g., (Katz et al.,
2017; Gowal et al., 2018; Wong et al., 2018; Balunovic and Vechev, 2020). (3)
Randomized smoothing (Lecuyer et al., 2019; Cohen et al., 2019; Salman et al.,
2019), which is hitherto the only method scaling to ImageNet. We remark that
the concept of randomized smoothing may also be interpreted as a special case
of (1), see (Salman et al., 2019) for the details.

All of these certificates expect that calculations can be done with unlimited
precision and do not take into account how finite precision arithmetics
affects the certificates. For Lipschitz networks (1), the round-off error is
of the order of the lowest significant bits of mantissa, which we can estimate
to be in the orders of $\sim 10^{-8}$ for single-precision floating-point
numbers. Thus, we should assume that the adversary can also inject
$\ell_{\infty}$-perturbation bounded by $\sim 10^{-8}$ in every layer.
However, since the networks have small Lipschitz constants by definition,
those errors will not be significantly magnified. Although we cannot
universally quantify the numerical errors of Lipschitz networks, they will
likely be very small and in particular, can be efficiently traced during the
forward pass so that the certificates will be sound. For the verification
methods from category (2), previous works have shown that numerical errors may
lead to false certificates for methods based on SMT or mixed-integer linear
programming (Jia and Rinard, 2021; Zombori et al., 2021). However, it is
possible (and often done in practice) to adapt the verification procedure to
be sound w.r.t. floating-point inaccuracies (Singh et al., 2019); thus, the
problem is not fundamental, and these verification techniques can be made
sound. We are not aware of any work discussing the influence of numerical
errors on randomized smoothing certificates (3). The recent work of (Lin et
al., 2021) focuses on randomized smoothing when using only integer arithmetics
in neural networks for embedded devices, so they will, by definition, not have
problems with floating-point errors. On the other hand, it does not cover some
modern architectures, such as transformers. Furthermore, the way they
approximate sampling from the discrete normal distribution is not accurate;
thus, the certificates are not sound, see Appendix E.

In this paper, we make the following contributions.

  1. 1.

We perform a novel analysis of numerical errors in randomized smoothing
approaches when using floating-point precision and identify qualitatively new
problems.

  2. 2.

Building on the observations, we present a simple approach for developing
classifiers whose smoothed version will provide fundamentally wrong
certificates for chosen points.

  3. 3.

We propose a sound randomized smoothing procedure for floating-point
precision. The certification speed is essentially equal, and the certified
robust accuracy matches the one claimed by the standard (unsound) smoothing.
The code will be publicly available.

#### Manuscript organization:

We start with the definition of randomized smoothing in Section 2, then we
continue with the introduction of floating-point arithmetics following the
IEEE standard 754 (iee, 2008) in Section 3. Then, in Section 4 we exploit the
properties of floating-point arithmetics and present a simple classifier
producing wrong certificates, and we follow with the identification of the
implicit assumptions of randomized smoothing. In Section 5 we conclude the
main result by proposing a method of sound randomized smoothing in floating-
point arithmetics  and provide an experimental comparison of the old unsound
and the new sound certificates.

##  2 Randomized smoothing

Throughout the paper, we consider the problem of binary classification. Every
phenomenon we discuss can be easily transferred to the multiclass setting. We
define certificates with respect to a norm ball in the following.

######  Definition 2.1.

A classifier $F:\mathbb{R}^{d}\rightarrow\\{0,1\\}$ is said to be certifiably
robust at point $x\in\mathbb{R}^{d}$ with radius $r$, w.r.t. norm
$\left\|\cdot\right\|$ if the correct label at $x$ is $y\in\\{0,1\\}$, and
$\left\|x-x^{\prime}\right\|\leq r\implies F(x^{\prime})=y$.

One way to get a certificate is randomized smoothing which we introduce
following, e.g., (Cohen et al., 2019; Salman et al., 2019). We start with a
deterministic mapping $F:\mathbb{R}^{d}\rightarrow\\{0,1\\}$ and call it _base
classifier_. Its smoothed version is
$\hat{f}(x)=\mathbb{E}_{\epsilon\sim\mathcal{N}(0,\sigma^{2}I_{d})}F(x+\epsilon)$,
and the resulting hard classifier is
$\hat{F}(x)=\llbracket\hat{f}(x)>0.5\rrbracket$. Using the Neyman-Pearson
lemma the following result has been shown:

######  Theorem 2.2 ((Cohen et al., 2019)).

Suppose $p_{A}\in(\frac{1}{2},1]$ satisfies

$\mathbb{P}_{\epsilon\in\mathcal{N}(0,\sigma^{2}I)}(F(x+\epsilon)=c_{A})\geq
p_{A}.$

Then $\hat{F}(x+\delta)=c_{A}$ for all $\delta\in\mathbb{R}^{d}$ with
$\left\|\delta\right\|_{2}<\sigma\Phi^{-1}(p_{A})$.

We call in the following $r(x)=\sigma\Phi^{-1}(\hat{f}(x))$ the certified
$\ell_{2}$-radius of $\hat{F}$ at $x$.

We emphasize that we require the smoothed classifier $F$ to be deterministic
in the sense that its output for the same input is always the same and that
the output is dependent only on the current input and not on the inputs it has
observed before. This requirement is commonly satisfied, and we list it only
for the sake of completeness. It is easy to construct a mapping $F$ violating
this assumption and producing false certificates. E.g., take $F$ that returns
$0$ in the first $10^{6}$ calls and $1$ afterward.

For the majority of classifiers, it is intractable to evaluate $\hat{f}$
exactly; therefore, random sampling is used to estimate it. Thus, the
certificate is only probabilistic. Following the literature, $100~{}000$
samples are used to estimate $\hat{f}(x)$, then it is lower bounded by $p$ for
certifying class $1$ (resp. upper bounded for class $0$) allowing failure
probability, that is when $p>\hat{f}(x)$ (resp. $p<\hat{f}(x)$), to be
$0.001$. The value $p$ from $\hat{f}(x)$ can be computed using tail bounds or
classical Clopper-Pearson confidence intervals for the binomial distribution.
The actual certification procedure is described in Algorithm 1. However, to
keep the example below as simple as possible, in Listing 1, we computed $p$
using a simple Hoeffding bound. Although it produces a weaker certificate, it
is still sufficient for the demonstration. The allowed failure probability
corresponds to bad luck during the noise sampling to estimate $\hat{f}$. It
does not correspond to a bad choice of model $F$, or to a possibility of
unpleasant data distribution.

##  3 Computer representation of floating-point numbers

In this section, we introduce the floating-point representations and
arithmetic according to standard IEEE-754 (iee, 2008). For the sake of
clarity, in this section, we use $8$-bit floating-point number representation
instead of the usual $16,32,64$ bits, respectively for half, single, and
double precision.

Floating-point numbers are represented in memory using three different
sequences of bits. The split will be $1/3/4$ for our $8$-bit example and is
$1/8/23$ for the standard single precision representation. We will represent
the binary numbers as a binary string of $8$ numbers and start with an example
translating binary floating-point representation to the standard decimal one.
A reader familiar with the limitations of floating-point arithmetics may
consider jumping directly to Example 3.3 as this shows the essential problem
of randomized smoothing in floating-point precision that we will exploit.

######  Example 3.1.

Consider the binary number $1110~{}1010$. The _first bit is the sign bit_. The
number is negative iff the bit is set to $1$. In our example, the bit is $1$;
thus, the number is negative. The _next $3$ bits ($110$) determine the
exponent_. It is the integer value of this encoding minus $3$, thus, in our
example, the exponent is $6-3=3$. The subtraction of $3$ is here to ensure
that we can represent exponents $-3,-2,\dots,4$. The _last sequence is called
mantissa_ and encodes the number after the decimal point. There is also an
implicit (not written) $1$ before it. This is a so-called normalized form.
Thus, the encoded value of the mantissa is $1.1010$ in binary representation,
which is $1+1\cdot 0.5+0\cdot 0.25+1\cdot 0.125+0\cdot 0.0625=1.625$ in base
$10$.

The represented number is thus $-1.625\cdot 2^{3}=-13$ in base $10$.

In order to be self-contained, we discuss in Appendix D also subnormal
numbers, NaNs, and Inf in floating-point representation, but as they are not
relevant for this paper, we skip them here.

###  3.1 Operations with floating-point numbers

To distinguish the mathematical operations (infinite precision) from the
computer arithmetics ones, we will use $\oplus,\ominus$ instead of $+,-$ to
represent floating-point operations. When writing, e.g., $5\oplus 7=12$, we
mean that the floating-point representation of $5$ added to the floating-point
representation of $7$ results in a floating-point $12$. We also note that
$a\oplus-b=a\ominus b$.

The addition (or analogically subtraction) of two floating-point numbers is
performed in three steps. First, the number with the lower exponent is
transformed to the higher exponent; then the addition is performed (we assume
with infinite precision), and then the result is rounded to fit into the
floating-point representation. The standard allows for several rounding
schemes, but the common one is to round to the closest number breaking the
ties by rounding to the number with mantissa ending with $0$.

For the sake of completeness, we also mention the multiplication of floating-
point numbers. The multiplication is done in a way that exponents are added;
the mantissas are multiplied and consequently normalized. We will not use
(nontrivial) floating-point multiplication in our constructions.

Let us show an example of the floating-point addition.

######  Example 3.2.

Consider the addition of binary numbers, $1110~{}1010$, and $0101~{}0011$. The
first one we already decoded as $-1.1010\times 2^{3}$ and the other one is
$1.0011\times 2^{2}$; both in base $2$.

$\displaystyle 1110~{}1010\oplus 0101~{}0011$ $\displaystyle=-1.1010\times
2^{3}+1.0011\times 2^{2}=-1.1010\times 2^{3}+0.10011\times 2^{3},$
$\displaystyle=-1.00001\times 2^{3}\approx-1.0000\times 2^{3}=1110~{}0000.$

In base $10$, we would have $-13\oplus 4.75=-8$ due to the loss of the least
significant bits. This happened even though the exponents were different by
the smallest possible difference.Consider further $6.5\oplus 4.75=11$; Here,
the loss of precision appeared even with equal exponents.

Unsurprisingly, it also holds that $6.5\oplus 4.5=11$. Therefore, the addition
to $6.5$ is not injective and, as a consequence, it is not surjective.
Connecting this to randomized smoothing, we know that there are numbers which
cannot be smoothed from $6.5$ as the following example shows.

######  Example 3.3.

When observing $2.125$, it could not arise as $6.5\oplus a$ for any $a$.
Indeed, $6.5\oplus-4.5=2$, while $6.5\oplus-4.25=2.25$. The representations
are: $6.5\sim 0101~{}1010$, $2.125\sim 0100~{}0001$, $-4.25\sim 1101~{}0001$
and $-4.5\sim 1101~{}0010$. Here $-4.25$ is the smallest number bigger than
$-4.5$. Note again that the exponents of $6.5$ and $2.25$ differ only by the
smallest possible difference.

Another consequence is that floating-point addition is not associative. That
is, the following identity does not always hold $(a\oplus b)\oplus
c=a\oplus(b\oplus c)$.

######  Example 3.4.

Consider the numbers $a=2.375\sim 0100~{}0011$, $b=3.75\sim 0100~{}1110$, and
$c=3.25\sim 0100~{}1010$. Then $a\oplus b=6\sim 0101~{}1000$ and $(a\oplus
b)\oplus c=9\sim 0110~{}0010$. On the other hand, $b\oplus c=7\sim
0101~{}1100$ and $a\oplus(b\oplus c)=9.5\sim 0110~{}0011$; thus, the triple
$a,b,c$ serves as a counterexample for associativity of $\oplus$.

###  3.2 Connection to randomized smoothing

We have identified some unpleasant properties of floating-point arithmetics
that we will exploit in the following section to provide false certificates.
The construction will be based on the fact that given a number, we will try to
find out if it could be a smoothed version of a specific number or not. The
following observations will help us.

In (Reiser and Knuth, 1975), it is shown that if stable rounding is used, then
the identity $((x\oplus y)\ominus y)\oplus y=x\oplus y$ holds apart from
certain very111It occurs roughly once per $10^{8}$ random trials. rare cases,
and the identity $(((x\oplus y)\ominus y)\oplus y)\ominus y=(x\oplus y)\ominus
y$ holds always. On the other hand, there is no evidence that the equality
$(x\oplus y)\ominus y=x$ should hold. Indeed, consider $x$ to have a lower
exponent than $y$. Then during the addition, $x\oplus y$, the low bits of the
mantissa of $x$ would be lost. Similarly, if $x\oplus y$ has a different
exponent than $y$, then a loss of significance may occur during the second
rounding. Now, consider the case where $x=a\ominus y$, then the identity
$(x\oplus y)\ominus y=x$ would hold apart from the very rare cases.

Our idea is to make the classifier determine if the observed value $x$ could
be a smoothed version of $a$. This can be done precisely, but we only
approximate this using the previous observation. The reason is that it is
sufficient for the demonstration, and the resulting function (introduced in
Equation (1) in the next section) will be simple, suggesting that the
phenomenon may occur in standard networks.

##  4 Construction of classifiers with false certificates

We present an example of a function $F:\mathbb{R}\rightarrow\\{0,1\\}$ which
is prone to giving incorrect certificates via randomized smoothing; the whole
"experimental setup" is captured in Listing 1. The example is based on the
observation that we are able to determine if a floating-point number $x$ could
be a result of floating-point addition $a\oplus n$ where $a$ is known and $n$
is arbitrary. We construct a function $F_{a}$ whose behavior we analyzed in
Subsection 3.2.

$F_{a}(x)=\llbracket(x\ominus a)\oplus a=x\rrbracket.$ (1)

We take $F_{a}$ as a base classifier and consider the smoothed classifier
$\hat{f}_{a}$ it induces with $\sigma=0.5$. It holds that
$\hat{f}_{a}(a)\approx 1$, therefore if we have enough samples, we may obtain
a very large certified radius. Specially, in the example considered in Listing
1 with $100~{}000$ samples, we can certify222We can certify radius 1.9 with
the bounds of Clopper-Pearson.a $l_{2}$-radius of $1.26$ around $210/255$,
however $0=\hat{F}_{210/255}(0)\not=\hat{F}_{210/255}(210/255)=1$, and the
point $0$ is nowhere near the boundary of the certified ball. We emphasize
that this construction does not rely on the fact that $F_{a}(a+\epsilon)=1$
for $\epsilon\in\mathcal{N}(0,\sigma^{2})$ with very high probability, it only
serves as a striking example. Similarly, we get
$0=\hat{F}_{210/255}(0)\not=\hat{F}_{210/255}(200/255)=1$, despite every point
$0,1/255,\dots,255/255$ would be class $1$ according to the certificate even
with the simple Hoeffding tail bounds instead of Clopper-Pearson intervals.

⬇

1import numpy as np

2from scipy.stats import norm

3

4sigma = 0.5; num_samples = 100000; alpha = 0.001

5f = lambda x: (x - 210/255) + 210/255 == x

6noise = np.random.randn(num_samples)*sigma

7

8p1 = f(0+noise).sum()/num_samples # 0.46

9p2 = f(210/255+noise).sum()/num_samples # 1.0

10p = p2-(-np.log(alpha)/num_samples/2)**0.5

11r = sigma * norm.ppf(p) # 1.26

Listing 1: example of an incorrect randomized smoothing certificate

###  4.1 Consequences for real images

We stress that the simple construction generalizes to images. Indeed, we could
employ a function

$F_{a,i}(x)=\llbracket(x_{i}\ominus a)\oplus a=x_{i}\rrbracket,$ (2)

which takes a vectorised version of an image as an input. Using such function
in Listing 1 would certify that any image with intensity $210/255$ at position
$i$ is class $1$ with robust radius $1.26$, while any image with intensity $0$
at position $i$ would be classified as $0$; a clear contradiction. We take one
step further. Consider a function

$G_{a}(x)=\mathop{\rm min}\nolimits_{i=1}^{d}\llbracket(x_{i}\ominus
a_{i})\oplus a_{i}=x_{i}\rrbracket.$ (3)

It holds that
$\mathbb{E}_{\epsilon\sim\mathcal{N}(0,1)}G_{a}(a+\epsilon)\approx 1$; thus,
certifying "arbitrarily" high radius (to be specific, with $100~{}000$ samples
it is $3.8115$ in $\ell_{2}$ norm), and
$\mathbb{E}_{\epsilon\sim\mathcal{N}(0,1)}G_{a}(a^{\prime}+\epsilon)<0.5$ for
the vast majority of inputs $a\neq a^{\prime}$. We tried the following
experiment; For every image $a$ in the CIFAR10 test set, we created an image
$a^{\prime}$ by increasing the image intensity of $a$ by $1/255$ at $512$
random positions. Then it holds that
$\mathbb{E}_{\epsilon\sim\mathcal{N}(0,1)}G_{a}(a^{\prime}+\epsilon)\leq 0.2$
for every CIFAR image $a$, even though $\left\|a-a^{\prime}\right\|_{2}<0.09$.

Following this line of examples, let us introduce the following hard
classifier:

$H_{A}(x)=\mathop{\rm max}\nolimits_{a\in A}\mathop{\rm
min}\nolimits_{i=1}^{d}\llbracket(x_{i}\ominus a_{i})\oplus
a_{i}=x_{i}\rrbracket,$ (4)

where $A$ is a set of images. Therefore, when $A$ is the set of CIFAR10 test
set images, then we can certify the robustness of the smoothed version of
$H_{A}$ at every point of the CIFAR10 test set for large radii, even though it
is vulnerable even to small random perturbations. We remark that $H_{A}$ can
be implemented with a standard network architecture using only linear layers
and ReLU non-linearities. To conclude the examples, we state the findings in
the upcoming theorem. Since we introduced the machinery only for binary
classification, we treat CIFAR10 as a binary classification dataset.

######  Theorem 4.1.

There is a classifier with certified robust accuracy $100\%$ on the CIFAR10
test set $X\in[0,\frac{1}{255},\dots,1]^{3072}$ (where we define class $0$ to
include classes $0,1,2,3,4$ of CIFAR10 and class $1$ contains the other
classes) with $\ell_{2}$-robust radius of $3$ and failure probability $0.001$
using randomized smoothing certificates, while for every point $x\in X$ there
is an adversarial example $x^{\prime}$ with
$\left\|x-x^{\prime}\right\|_{2}\leq 1$.

###### Proof.

We take $X_{0}\subseteq X$ to be the set of all images from $X$ with class $0$
and $X_{1}=X\setminus X_{0}$. Then we construct a hard classifier

$M(x)=\begin{cases}$1$&\quad\text{if $H_{X_{1}}(x)=1$ or ( $H_{X_{0}}(x)=0$
and $x_{1}>\frac{127}{255}$)),}\\\ $0$&\quad\text{otherwise,}\\\ \end{cases}$

where we use $H_{A}$ from (4). Experimentally we conclude that for the
smoothed classifier of $M$ with $\sigma=1$, randomized smoothing certifies
robust radius $3$ in $\ell_{2}$ norm for every point $x$ of the test set. At
the same time, the perturbation
$p=(\alpha,\frac{1}{255},\frac{1}{255},\dots)\in\mathbb{R}^{3072}$ for
$\alpha\in\\{\pm\frac{240/255}{255}\\}$ yields
$H_{X_{1}}(x+p)=H_{X_{2}}(x+p)=0$ for any $x\in X$. Thus, we can choose
$\alpha$ so that $M(x)\neq M(x+p)$ and also $\left\|p\right\|_{2}\leq 1$. ∎

A similar construction will likely serve as an example for the ImageNet
dataset.

###  4.2 Implicit assumptions of randomized smoothing

The obvious questions after this negative result are: i) what is the key
underlying problem in floating-point arithmetics? ii) what are the implicit
assumptions in randomized smoothing?, and iii) how can we fix the problem?

The first assumption of randomized smoothing is that the samples from a normal
distribution are indeed i.i.d. samples. This is not true for floating-point
precision due to the rounding; Thus, the resulting distribution from which we
observe samples is uncontrolled, and for certification, we should not rely on
it. However, violation of this assumption is not the cause of the example
presented in Listing 1.

The intuition behind randomized smoothing is that the distributions
$D_{1}=\mathcal{N}(x,\sigma^{2}I)$ and
$D_{2}=\mathcal{N}(x+\epsilon,\sigma^{2}I)$ have non-trivial overlap for small
values of $\epsilon$. As a consequence, the smoothed classifier
$\hat{f}(x)=\mathbb{E}_{\epsilon\sim\mathcal{N}(0,\sigma^{2}I_{d})}F(x+\epsilon)$
evaluated at $x$ also carries information about its value at points near $x$.
However, the following observation will prove it wrong in the floating-point
arithmetics.

Roughly speaking, the supports of two high dimensional normal distributions
appear to be almost disjoint, although in one dimension the overlap may be
substantial. To support this claim, We performed the following experiment;
given point $a\in\\{0,1/255,\dots 255/255\\}$ and $\sigma>0$, find a point $b$
such that $b\in\\{a\ominus 2/255,\dots,a\oplus 2/255\\}$ which minimizes the
probability that for an $\epsilon_{1}\sim\mathcal{N}(0,\sigma^{2})$ there
exists a number $\epsilon_{2}$ such that
$a\oplus\epsilon_{1}=b\oplus\epsilon_{2}$? For example, if $a\geq 5/255$ and
$\sigma=1$, then the minimized probability is less than $0.99$, and for the
majority of $a\geq 5/255$ it is even smaller. In order to see that the
distributions are almost disjoint, consider an image, say from a CIFAR
dataset, $a\in\mathbb{R}^{3072}$ which has at least half of its channels with
intensities greater than $4/255$. According to the previous observation, we
can find an image $a^{\prime}$ such that
$\left\|a-a^{\prime}\right\|_{\infty}=2/255$ and that the probability that
smoothed $a$ at any (non black) position could be a smoothed version of
$a^{\prime}$ is at most $0.99$ (this can be exploited by function $F_{a,i}$
from Equation (2)). Therefore, the probability that a smoothed version of the
first image could also be a smoothed version of the second image is at most
$0.99^{3072/2}\approx 2\times 10^{-7}$ (this can be exploited by function
$G_{a}$ from Equation (3)). Thus, when we follow the standard practise and use
$10^{5}$ samples to estimate $\hat{f}(a)$ from base classifier $F$, the
chances that at least one of the samples belongs to the distribution from
which we sample to estimate $\hat{f}(a^{\prime})$ is at most in the orders
$10^{-2}$. Consequently, without any assumptions on the base classifier $F$,
$\hat{f}(a)$ carries almost no information about $\hat{f}(a^{\prime})$.

###  4.3  Potential revisions of randomized smoothing

The described experiment exploits the floating-point rounding. The errors are
in the order of the least significant bits, which are in the order of
$10^{-8}$ for single-precision and $10^{-4}$ for half-precision. Since these
numerical errors are not controlled, we should assume that the model is
adversarially attacked during smoothing, where the attacker’s budget is the
possible rounding error, denoted as $\mathcal{B}$; therefore, the smoothing
(for certifying class $1$) should be performed as:

$\hat{f}(x)=\mathbb{E}_{\epsilon\sim\mathcal{N}(0,\sigma^{2}I_{d})}\mathop{\rm
min}\nolimits_{\epsilon_{2}\in\mathcal{B}}F(x+\epsilon+\epsilon_{2}).$

To mitigate this problem, during estimating $\hat{f}(x)$, we should certify
$F(x+\epsilon)$. Although the attacker’s budget $\mathcal{B}$ is very small
for single accuracy and possibly noticeable for the half accuracy, it is not
clear how it should be certified, since in randomized smoothing, there are no
assumptions on $F$.

Consider $F$ to be a thresholded classifier $F(x)=\llbracket
f(x)>0.5\rrbracket$, where $f$ is a neural network, then we could certify that
$f$ is constant in $\mathcal{B}$-neighbourhood of the smoothed image. For
generic models, this can be done by either bounding the Lipschitz constant of
$f$ (w.r.t. an $\ell_{\infty}$-like norm), or by propagating a convex
relaxation (e.g., IBP) through the network. For smoothing, there are usually
used deep models. E.g., (Salman et al., 2019) used ResNet110 and ResNet50 for
certifying CIFAR10 and ImageNet respectively. The bound on the global
Lipschitz constant of a deep network by bounding the operator norms of each
layer is thus very weak ($\approx$ $10^{30}-10^{130}$, depending on the model)
and cannot certify $F(x+\epsilon)$ even under such a weak threat model as the
rounding errors in $\mathcal{B}$.

A possible defense against this problem would be to round the input on a
significantly larger scale than $\mathcal{B}$ before evaluating $F$. Let the
rounding be performed by a mapping $g$, then we would in fact smooth a
classifier $F\circ g$. If we consider $\mathcal{B}$ to be in the orders of
$10^{-8}$ and we would round it to orders $10^{-2}$, then the probability that
$x+\epsilon$ will be close to the boundary of rounding, i.e.,
$\exists\epsilon_{2}\in\mathcal{B}:g(x+\epsilon+\epsilon_{2})\neq
g(x+\epsilon)$ would be on the order of $10^{-6}$, which is then the
probability that the attack within the threat model $\mathcal{B}$ could indeed
change the input of $F$ at a single position. Consequently, the probability
that there is no $\epsilon_{2}\in\mathcal{B}$ which would change the result of
rounding is very roughly $\approx(1-10^{6})^{3072}\approx 0.997$ for CIFAR and
$\approx(1-10^{6})^{150528}\approx 0.86$ for ImageNet. This means that for
approximatelly $86\%$ of the smoothed ImageNet images we can guarantee that
$F(x+\epsilon+\epsilon_{2})=F(x+\epsilon)$ and for the others, we could e.g.,
set $\mathop{\rm
min}\nolimits_{\epsilon_{2}\in\mathcal{B}}F(x+\epsilon+\epsilon_{2})=0$. This
replacement of $F$ by $F\circ g$ during smoothing seem to solve the problem
for CIFAR and partially also for ImageNet for single precision. For half
precision, the problem will persist.

However, even if this adjustment solved the problem with numerical errors
satisfactorily during the addition of noise to images, the certificate will
still not be sound because we are unlikely to control the normal distribution
sampler’s performance. Thus, although we do not see a striking example of how
to exploit the imperfections of normal distribution samplers, a lack of a
counterexample is not enough to confirm the correctness of a certification
method.

##  5 Sound randomized smoothing for floating-point precision

In this section, we will derive a sound randomized smoothing certification
procedure for floating-point precision having comparable accuracy to the one
which the standard unsound randomized smoothing claims. Our only assumption is
the access to i.i.d. samples of a fair coin toss, which is equivalent to
having access to samples from the uniform distribution on integers
$0,\dots,2^{n}-1$ for some $n$. Thus, we assume to have access to uniform
samples from numbers representable by Long datatype, that is when $n=64$. We
further consider classification tasks where the input is quantized as it is
true for images. Throughout the section, we consider the input space to be
$\\{0,1,\dots,255\\}^{d}$, although it could also be
$\\{0,\frac{1}{255},\dots,1\\}$. This assumption is only for the convenience
of presentation and is not necessary.

As discussed in the previous section, it is appealing to quantize the smoothed
images before feeding them into the network. Thus, we prepend a mapping
$g_{k}:\mathbb{R}^{d}\rightarrow\\{-k,-k+1,\dots,k+255\\}$, for some positive
integer $k$ which rounds the input to the nearest integer from its range
before the function to be smoothed $F$; therefore, the smoothed classifier (of
$F\circ g_{k})$ is defined as:

$\hat{f}(x)=\mathbb{E}_{\epsilon\sim\mathcal{N}(0,\sigma^{2}I_{d})}\,F(g_{k}(x+\epsilon)),$

which we further equivalently rewrite as

$\hat{f}(x)=\mathbb{E}_{t\sim
g_{k}(x+\epsilon),\,\epsilon\sim\mathcal{N}(0,\sigma^{2}I_{d})}\,F(t).$

Now, $F$ is a deterministic function, regardless of possible numerical errors
occurring during evaluation of $F(t)$; thus, we only need to show how to
obtain i.i.d. samples from the discretized normal distribution
$\mathcal{N}_{D}^{k}(x,\sigma^{2})=g_{k}(x+\epsilon),\epsilon\sim\mathcal{N}(0,\sigma^{2})$,
from which we sample component-wise. The key observation is that we do not
need to obtain samples from $\mathcal{N}(0,\sigma^{2})$ anymore. The resulting
distribution from which we want to sample now is discrete. Concretely, we have

$\mathbb{P}_{t\sim\mathcal{N}^{k}_{D}(x,\sigma^{2})}\llbracket
t=a\rrbracket=\begin{cases}\int_{-\infty}^{-k+\frac{1}{2}}\frac{1}{\sqrt{2\pi\sigma^{2}}}~{}\,e^{-\frac{(x-u)^{2}}{2\sigma^{2}}}\,du&\quad\text{if
$a=-k$,}\\\
\int_{a-\frac{1}{2}}^{a+\frac{1}{2}}\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{(x-u)^{2}}{2\sigma^{2}}}\,du&\quad\text{if
$-k<a<k+255$,}\\\
\int_{k+255-\frac{1}{2}}^{\infty}\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{(x-u)^{2}}{2\sigma^{2}}}\,du&\quad\text{if
$a=k+255$.}\\\ \end{cases}$

The following proposition allows us to sample only from a single distribution
for all values of $x$.

######  Proposition 5.1.

Let $k$ be a positive integer and $x\in\\{0,1,\dots,255\\}$, then it holds
that $\mathcal{N}_{D}^{k}(x,\sigma^{2})=\mathop{\rm
max}\nolimits\\{-k,\mathop{\rm
min}\nolimits\\{k+255,t^{\prime}+x\\}\\},t^{\prime}\sim\mathcal{N}_{D}^{k+255}(0,\sigma^{2})$.

Thus, it is enough to have a sampler from
$\mathcal{N}_{D}^{k+255}(0,\sigma^{2})$. The value of $k$ is chosen such that
the vast majority of samples from $\mathcal{N}(x,\sigma^{2})$ falls into the
interval $[-k,k+255]$. The choice of $k$ does not affect the correctness of
certificates, but may affect the accuracy. In the experiments we chose
$k=6\sigma_{max}=6$ for inputs from $[0,1]^{d}$, so it corresponds to
$k=6\cdot 255$ in the notation of this section.

Let us denote the quantile function of $\mathcal{N}^{k}_{D}(0,\sigma^{2})$ as
$\Phi_{D,k}^{-1}$, then $\Phi_{D,k}^{-1}$ transforms i.i.d. samples from
uniform distribution on the interval $[0,1)$ =: $\mathcal{U}(0,1)$ to i.i.d.
samples from distribution $\mathcal{N}^{k}_{D}(0,\sigma^{2})$.

To sample from $\mathcal{N}^{k}_{D}(0,\sigma^{2})$, we first approximate the
samples from $\mathcal{U}(0,1)$ by samples from the discrete uniform
distribution on $\\{0,\dots,2^{n}-1\\}$ which we will interpret as uniform
distribution on $\\{0,\frac{1}{2^{n}},\dots,\frac{2^{n}-1}{2^{n}}\\}$ =:
$\mathbf{U}(0,1)$. Then we only need to compute the $2k+255$ probabilities
with high enough accuracy that we can claim the correctness of
$\Phi_{D,k}^{-1}(u)$ for
$u\in\\{0,\frac{1}{2^{n}},\dots,\frac{2^{n}-1}{2^{n}}\\}$. This can be done by
using symbolic mathematical libraries allowing computations in arbitrary
precision.

Since the distribution $\mathcal{N}^{k}_{D}(0,\sigma^{2})$ is supported on
$2k+256$ events, there will be $2k+255$ points
$x\in\\{0,\frac{1}{2^{n}},\dots,\frac{2^{n}-1}{2^{n}}\\}$ such that
$\Phi_{D,k}^{-1}(x)\neq\Phi_{D,k}^{-1}\left(x+\frac{1}{2^{n}}\right)$. Now,
consider the obvious mapping between samples from $\mathcal{U}(0,1)$ and
$\mathbf{U}(0,1)$ which rounds down a sample $u$ from the continuous real
interval $[0,1)$ to the closest point $v$ from the set
$\\{0,\frac{1}{2^{n}},\dots,\frac{2^{n}-1}{2^{n}}\\}$. Then it holds for the
probability
$\Phi_{D,k}^{-1}(u)\neq\Phi_{D,k}^{-1}(v)\leq\frac{255+2k}{2^{n}}\leq
2^{12-n}$ for a choice $k=7.5\times 255$. The probability that the produced
sample is not the actual i.i.d. sample is thus at most $2^{12-n}$ at one
position. Therefore, the probability that all the smoothed images, considering
ImageNet sized images with shape $3\times 224\times 224$, out of $100~{}000$
smoothed samples are indeed the correct i.i.d. samples from discrete normal
distribution is at least $1-2^{46-n}>0.999996$ for $n=64$, where we used the
facts that $\log_{2}(3\cdot 224\cdot 224\cdot 100~{}000)\leq 34$, and that
$(1-2^{a})^{2}=(1-2\cdot 2^{a}+2^{2a})>(1-2^{a+1})$. Therefore, the
probability of receiving a sample that might not be the actual i.i.d. sample
is negligible. Still, we can check if we receive such a potentially flawed
sample $x$ and in that case, we would set $F(x)=0$ when certifying class $1$
(resp. $F(x)=1$ when certifying $0$) for that particular sample. We postpone
an example of the sampling from $\mathcal{N}_{D}^{k}(x,\sigma^{2}I)$ to
Appendix B. We note that sampling is slightly more expensive since we need to
threshold the observed uniform samples, but this is only an implementation
issue. On the other hand, it is sufficient to sample i.i.d. noise for just one
image $100~{}000$ times and reuse it for all the other images. The
certificates will be valid, only the case of failure for different images will
not be independent, but it is not required. As we sample just once for the
whole data set, the time spent for sampling is negligible. We wrap up the
observations in the following corollary:

######  Corollary 5.2.

Let $F:\mathbb{R}^{d}\rightarrow\\{0,1\\}$ be a deterministic function, and
$g_{k}:\mathbb{R}^{d}\rightarrow\\{\frac{-k}{255},\frac{-k+1}{255},\dots\frac{k+255}{255}\\}$
maps input to the closest point of its range, breaking ties arbitrarily. Then
the following two functions are identical:

$\displaystyle\hat{f_{1}}(x)$
$\displaystyle=\mathbb{E}_{\epsilon\sim\mathcal{N}(0,\sigma^{2}I_{d})}\,F(g_{k}(x+\epsilon)),\qquad\hat{f}(x)=\mathbb{E}_{t\sim\mathcal{N}_{D}^{k}(x,\sigma^{2}I_{d})}\,F(t).$

Therefore, to certify $\hat{f}_{1}$ with base classifier $F\circ g_{k}$ using
randomized smoothing, we can estimate the value of $\hat{f}$ and use it for
the certification. Furthermore we can get i.i.d. samples from
${t\sim\mathcal{N}_{D}^{k}(x,\sigma^{2}I_{d})}$ with arbitrarily high
precision using exact arithmetics; thus, the certificate is sound.

######  Remark 5.3.

The empirical performance of the sound and unsound versions of randomized
smoothing are essentially equivalent in practice; see Table 1(b) and also
Appendix A for the evidence. However, it no longer incorrectly certifies the
example from Listing 1, where it only certifies a radius $0.6$, and the points
are distant $0.82$ from each other. Similarly, the smoothed classifier of $M$
from Theorem F does not contain the universal adversarial perturbations in the
certified balls around the points. See Appendix F for more details.

To summarize: we showed how to replace sampling from the normal distribution,
where one cannot trace the numerical errors, by sampling from the uniform
distribution on integers, where we can bound the failure probability in order
to obtain high probability estimates of the output of a smoothed classifier
with a prepended rounding mapping. See Algorithms 1, 2 for the comparison of
the standard and the proposed certification procedure. We also provide an
empirical comparison of the methods in Table 1(b) and in Appendix A.

##  6 Broader impact & Conclusions

In the paper, we described multiple simple ways how to construct models that
will be certifiably robust for points of our choice using the standard
randomized smoothing certification procedure, although there will be
adversarial examples in their close neighborhood.

We also described how to obtain a sound randomized smoothing procedure that
resolves the problem, essentially for free, with only a minor modification of
the standard certification procedure.

Table 1: Certified radii for a model $F$ smoothed with
$\mathcal{N}(0,\sigma^{2}I)$ on CIFAR10 test set. Evaluated on $500$ images
from the test set highlighting the differences. The model is taken from Salman
et al. (2019), more details in Appendix A. (a) Sound smoothing of $F\circ
g_{k}$ via Algorithm 2 for $k=6$

certified radius | 0 | 0.1 | 0.25 | 0.5 | 0.75 | 1 | 1.25 | 1.5 | 2.0
---|---|---|---|---|---|---|---|---|---
$\sigma=0.12$ | 0.878 | 0.848 | 0.778 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000
$\sigma=0.25$ | 0.836 | 0.808 | 0.746 | 0.600 | 0.466 | 0.000 | 0.000 | 0.000 | 0.000
$\sigma=0.5$ | 0.708 | 0.672 | 0.618 | 0.502 | 0.410 | 0.338 | 0.248 | 0.174 | 0.000
$\sigma=1$ | 0.512 | 0.492 | 0.448 | 0.380 | 0.316 | 0.278 | 0.230 | 0.182 | 0.112

(b) Standard smoothing of $F$ via Algorithm 1

certified radius | 0 | 0.1 | 0.25 | 0.5 | 0.75 | 1 | 1.25 | 1.5 | 2.0
---|---|---|---|---|---|---|---|---|---
$\sigma=0.12$ | 0.880 | 0.848 | 0.778 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000
$\sigma=0.25$ | 0.836 | 0.808 | 0.746 | 0.602 | 0.468 | 0.000 | 0.000 | 0.000 | 0.000
$\sigma=0.5$ | 0.706 | 0.672 | 0.618 | 0.502 | 0.408 | 0.338 | 0.248 | 0.174 | 0.000
$\sigma=1$ | 0.516 | 0.492 | 0.448 | 0.378 | 0.316 | 0.278 | 0.230 | 0.182 | 0.110

## References

  * iee (2008) IEEE standard for floating-point arithmetic.  _IEEE Std 754-2008_ , pages 1–70, Aug 2008.  doi: 10.1109/IEEESTD.2008.4610935.
  * Athalye et al. (2018) A. Athalye, N. Carlini, and D. Wagner.  Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples.  In _ICML_ , 2018.
  * Balunovic and Vechev (2020) Mislav Balunovic and Martin Vechev.  Adversarial training and provable defenses: Bridging the gap.  In _ICLR_ , 2020.  URL https://openreview.net/forum?id=SJxSDxrKDr.
  * Carlini et al. (2019) Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian Goodfellow, Aleksander Madry, and Alexey Kurakin.  On evaluating adversarial robustness.  _arXiv preprint arXiv:1902.06705_ , 2019.
  * Cohen et al. (2019) Jeremy M Cohen, Elan Rosenfeld, and J Zico Kolter.  Certified adversarial robustness via randomized smoothing.  In _NeurIPS_ , 2019.
  * Croce and Hein (2020) Francesco Croce and Matthias Hein.  Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks.  In _ICML_ , 2020.
  * Goodfellow et al. (2015) I. J. Goodfellow, J. Shlens, and C. Szegedy.  Explaining and harnessing adversarial examples.  In _ICLR_ , 2015.
  * Gowal et al. (2018) Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli.  On the effectiveness of interval bound propagation for training verifiably robust models.  _arXiv:1810.12715_ , 2018.
  * Hein and Andriushchenko (2017) M. Hein and M. Andriushchenko.  Formal guarantees on the robustness of a classifier against adversarial manipulation.  In _NeurIPS_ , 2017.
  * Jia and Rinard (2021) Kai Jia and Martin Rinard.  Exploiting verified neural networks via floating point numerical error.  In _International Static Analysis Symposium_ , 2021.
  * Katz et al. (2017) Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer.  Reluplex: An efficient smt solver for verifying deep neural networks.  In _CAV_ , pages 97–117, 2017.
  * Laidlaw et al. (2021) Cassidy Laidlaw, Sahil Singla, and Soheil Feizi.  Perceptual adversarial robustness: Defense against unseen threat models.  In _ICLR_ , 2021.
  * Lecuyer et al. (2019) Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana.  Certified robustness to adversarial examples with differential privacy.  In _IEEE Symposium on Security and Privacy (SP)_ , 2019.
  * Leino et al. (2021) Klas Leino, Zifan Wang, and Matt Fredrikson.  Globally-robust neural networks.  In _ICML_ , 2021.
  * Li et al. (2019) Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Jörn-Henrik Jacobsen.  Preventing gradient attenuation in lipschitz constrained convolutional networks.  _NeurIPS_ , 2019.
  * Lin et al. (2021) Haowen Lin, Jian Lou, Li Xiong, and Cyrus Shahabi.  Integer-arithmetic-only certified robustness for quantized neural networks.  In _ICCV_ , 2021.
  * Madry et al. (2018) A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Valdu.  Towards deep learning models resistant to adversarial attacks.  In _ICLR_ , 2018.
  * Reiser and Knuth (1975) John F. Reiser and Donald E. Knuth.  Evading the drift in floating-point addition.  _Information Processing Letters_ , 3(3):84–87, 1975.  ISSN 0020-0190.  doi: https://doi.org/10.1016/0020-0190(75)90022-8.  URL https://www.sciencedirect.com/science/article/pii/0020019075900228.
  * Salman et al. (2019) Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang.  Provably robust deep learning via adversarially trained smoothed classifiers.  _NeurIPS_ , 2019.
  * Singh et al. (2019) Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev.  An abstract domain for certifying neural networks.  In _POPL_ , 2019.  URL https://doi.org/10.1145/3290354.
  * Singla et al. (2022) Sahil Singla, Surbhi Singla, and Soheil Feizi.  Improved deterministic $l_{2}$ robustness on CIFAR-10 and CIFAR-100.  In _ICLR_ , 2022.  URL https://openreview.net/forum?id=tD7eCtaSkR.
  * Szegedy et al. (2014) C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus.  Intriguing properties of neural networks.  In _ICLR_ , pages 2503–2511, 2014.
  * Tramer et al. (2020) Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry.  On adaptive attacks to adversarial example defenses.  In _NeurIPS_ , 2020.
  * Trockman and Kolter (2021) Asher Trockman and J Zico Kolter.  Orthogonalizing convolutional layers with the cayley transform.  In _ICLR_ , 2021.  URL https://openreview.net/forum?id=Pbj8H_jEHYv.
  * Wong et al. (2018) Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J. Zico Kolter.  Scaling provable adversarial defenses.  In _NeurIPS_ , 2018.
  * Wong et al. (2019) Eric Wong, Frank Schmidt, and Zico Kolter.  Wasserstein adversarial examples via projected sinkhorn iterations.  In _ICML_ , 2019.
  * Zhang et al. (2022) Bohang Zhang, Du Jiang, Di He, and Liwei Wang.  Boosting the certified robustness of l-infinity distance nets.  In _ICLR_ , 2022.  URL https://openreview.net/forum?id=Q76Y7wkiji.
  * Zombori et al. (2021) Dániel Zombori, Balázs Bánhelyi, Tibor Csendes, István Megyeri, and Márk Jelasity.  Fooling a complete neural network verifier.  In _ICLR_ , 2021.  URL https://openreview.net/forum?id=4IwieFS44l.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [N/A]

    3. (c)

Did you discuss any potential negative societal impacts of your work? [Yes] We
introduced practises how to fool the randomized smoothing certification;
However, we also introduced the sound version which cannot be fooled.

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]

    2. (b)

Did you include complete proofs of all theoretical results? [Yes]

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]
We put them in supplementary materials, will be at URL later.

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [N/A]

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [N/A]

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix
A

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes] See
Appendix A

    2. (b)

Did you mention the license of the assets? [Yes] See Appendix A

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [Yes] See Appendix A

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [No] The codebase (see Appendix A) is publicly
available under MIT licence.

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

##  Appendix A Experiments

To run the experiments, we used the publicly available codebase of Salman et
al. (2019) which is distributed under MIT licence. Our modifications will be
publicly available under MIT licence. The experiments were run on a single
Tesla V100 GPU. The models we evaluated were chosen arbitrarily from the
models Salman et al. (2019) provide in their repository. Their identifications
are:

pretrained_models/cifar10/finetune_cifar_from_imagenetPGD2steps/PGD_10steps_30epochs_multinoise/2-multitrain/eps_64/cifar10/resnet110/noise_$\sigma$/checkpoint.pth.tar,

pretrained_models/cifar10/PGD_4steps/eps_255/cifar10/resnet110/noise_$\sigma$/checkpoint.pth.tar

pretrained_models/cifar10/PGD_4steps/eps_512/cifar10/resnet110/noise_$\sigma$/checkpoint.pth.tar

where $\sigma\in\\{0.12,0.25,0.50,1.00\\}$ for tables 1(b), 2(b) and 3(b)
respectively. In Table 1(b), $100~{}000$ samples are used, whereas for Tables
2(b), 3(b) we used only $10~{}000$ samples to evaluate the smoothed
classifier.

For Imagenet experiments, we used models:

pretrained_models/imagenet/replication/resnet50/noise_$\sigma$/checkpoint.pth.tar,
pretrained_models/imagenet/DNN_2steps/imagenet/eps_512/resnet50/noise_$\sigma$/checkpoint.pth.tar

where $\sigma\in\\{0.25,0.50,1.00\\}$ for tables 4(b) and 5(b) respectively.
Again, we used $10~{}000$ samples to evaluate the smoothed classifier.

###  A.1 Speed

We note that the speed is essentially equal for both of the methods, described
in Algorithm 1 and 2 respectively, because we compute the noise beforehand and
then we can use the same set of $n$ noises for every image, where $n$ is the
number of samples used to evaluate a smoothed classifier. The time needed to
generate the noise is in the order of minutes; thus, negligible compared to
the time needed to run the experiments.

Table 2: Certified radii for a model $F$ smoothed with
$\mathcal{N}(0,\sigma^{2}I)$ on CIFAR10 test set. Evaluated on $500$ images
from the test set highlighting the differences. The model is taken from Salman
et al. (2019). (a) Sound smoothing of $F\circ g_{k}$ via Algorithm 2 for $k=6$

certified radius | 0 | 0.1 | 0.25 | 0.5 | 0.75 | 1 | 1.25 | 1.5 | 2.0
---|---|---|---|---|---|---|---|---|---
$\sigma=0.12$ | 0.714 | 0.678 | 0.630 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000
$\sigma=0.25$ | 0.660 | 0.636 | 0.590 | 0.526 | 0.444 | 0.000 | 0.000 | 0.000 | 0.000
$\sigma=0.50$ | 0.554 | 0.538 | 0.500 | 0.442 | 0.386 | 0.340 | 0.284 | 0.204 | 0.000
$\sigma=1$ | 0.440 | 0.428 | 0.402 | 0.368 | 0.332 | 0.292 | 0.248 | 0.202 | 0.160

(b) Standard smoothing of $F$ via Algorithm 1

certified radius | 0 | 0.1 | 0.25 | 0.5 | 0.75 | 1 | 1.25 | 1.5 | 2.0
---|---|---|---|---|---|---|---|---|---
$\sigma=0.12$ | 0.712 | 0.678 | 0.630 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000
$\sigma=0.25$ | 0.664 | 0.638 | 0.592 | 0.522 | 0.444 | 0.000 | 0.000 | 0.000 | 0.000
$\sigma=0.50$ | 0.556 | 0.540 | 0.500 | 0.440 | 0.386 | 0.338 | 0.284 | 0.194 | 0.000
$\sigma=1$ | 0.440 | 0.428 | 0.402 | 0.366 | 0.330 | 0.290 | 0.248 | 0.204 | 0.164

Table 3: Certified radii for a model $F$ smoothed with
$\mathcal{N}(0,\sigma^{2}I)$ on CIFAR10 test set. Evaluated on $500$ images
from the test set highlighting the differences. The model is taken from Salman
et al. (2019). (a) Sound smoothing of $F\circ g_{k}$ via Algorithm 2 for $k=6$

certified radius | 0 | 0.1 | 0.25 | 0.5 | 0.75 | 1 | 1.25 | 1.5 | 2.0
---|---|---|---|---|---|---|---|---|---
$\sigma=0.12$ | 0.560 | 0.544 | 0.522 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000
$\sigma=0.25$ | 0.534 | 0.514 | 0.492 | 0.450 | 0.408 | 0.000 | 0.000 | 0.000 | 0.000
$\sigma=0.50$ | 0.466 | 0.458 | 0.440 | 0.414 | 0.378 | 0.342 | 0.306 | 0.258 | 0.000
$\sigma=1$ | 0.370 | 0.364 | 0.342 | 0.320 | 0.298 | 0.276 | 0.252 | 0.226 | 0.166

(b) Standard smoothing of $F$ via Algorithm 1

certified radius | 0 | 0.1 | 0.25 | 0.5 | 0.75 | 1 | 1.25 | 1.5 | 2.0
---|---|---|---|---|---|---|---|---|---
$\sigma=0.12$ | 0.558 | 0.544 | 0.522 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000
$\sigma=0.25$ | 0.534 | 0.514 | 0.492 | 0.450 | 0.410 | 0.000 | 0.000 | 0.000 | 0.000
$\sigma=0.50$ | 0.464 | 0.458 | 0.440 | 0.414 | 0.380 | 0.340 | 0.308 | 0.264 | 0.000
$\sigma=1$ | 0.372 | 0.364 | 0.344 | 0.318 | 0.298 | 0.274 | 0.250 | 0.222 | 0.168

Table 4: Certified radii for a model $F$ smoothed with
$\mathcal{N}(0,\sigma^{2}I)$ on Imagenet test set. Evaluated on $1000$ images
from the test set highlighting the differences. The model is taken from Salman
et al. (2019). (a) Sound smoothing of $F\circ g_{k}$ via Algorithm 2 for
$k=12$

certified radius | 0 | 0.1 | 0.25 | 0.5 | 0.75 | 1 | 1.25 | 1.5 | 2.0
---|---|---|---|---|---|---|---|---|---
$\sigma=0.25$ | 0.661 | 0.636 | 0.614 | 0.559 | 0.498 | 0.000 | 0.000 | 0.000 | 0.000
$\sigma=0.50$ | 0.597 | 0.586 | 0.549 | 0.509 | 0.460 | 0.428 | 0.383 | 0.330 | 0.000
$\sigma=1$ | 0.447 | 0.438 | 0.424 | 0.390 | 0.365 | 0.344 | 0.319 | 0.299 | 0.238

(b) Standard smoothing of $F$ via Algorithm 1

certified radius | 0 | 0.1 | 0.25 | 0.5 | 0.75 | 1 | 1.25 | 1.5 | 2.0
---|---|---|---|---|---|---|---|---|---
$\sigma=0.25$ | 0.660 | 0.635 | 0.614 | 0.559 | 0.497 | 0.000 | 0.000 | 0.000 | 0.000
$\sigma=0.50$ | 0.598 | 0.584 | 0.548 | 0.507 | 0.459 | 0.429 | 0.385 | 0.323 | 0.000
$\sigma=1$ | 0.447 | 0.439 | 0.424 | 0.390 | 0.365 | 0.344 | 0.320 | 0.297 | 0.240

Table 5: Certified radii for a model $F$ smoothed with
$\mathcal{N}(0,\sigma^{2}I)$ on Imagenet test set. Evaluated on $1000$ images
from the test set highlighting the differences. The model is taken from Salman
et al. (2019). (a) Sound smoothing of $F\circ g_{k}$ via Algorithm 2 for
$k=12$

certified radius | 0 | 0.1 | 0.25 | 0.5 | 0.75 | 1 | 1.25 | 1.5 | 2.0
---|---|---|---|---|---|---|---|---|---
$\sigma=0.25$ | 0.672 | 0.642 | 0.592 | 0.505 | 0.393 | 0.000 | 0.000 | 0.000 | 0.000
$\sigma=0.50$ | 0.580 | 0.566 | 0.534 | 0.484 | 0.425 | 0.378 | 0.331 | 0.268 | 0.000
$\sigma=1$ | 0.448 | 0.439 | 0.416 | 0.379 | 0.348 | 0.327 | 0.299 | 0.266 | 0.210

(b) Standard smoothing of $F$ via Algorithm 1

certified radius | 0 | 0.1 | 0.25 | 0.5 | 0.75 | 1 | 1.25 | 1.5 | 2.0
---|---|---|---|---|---|---|---|---|---
$\sigma=0.25$ | 0.672 | 0.641 | 0.593 | 0.503 | 0.389 | 0.000 | 0.000 | 0.000 | 0.000
$\sigma=0.50$ | 0.581 | 0.564 | 0.534 | 0.486 | 0.423 | 0.377 | 0.337 | 0.270 | 0.000
$\sigma=1$ | 0.449 | 0.440 | 0.418 | 0.380 | 0.349 | 0.324 | 0.299 | 0.268 | 0.211

##  Appendix B Example of sampling from $\mathcal{N}_{d}^{k}(x,\sigma^{2}I)$

######  Example B.1.

Let $n=8$ and the quantization levels for image intensities be $0,1,2,3,4$
(instead of the standard $0,1,\dots,255$). We use $\sigma^{2}=16$ (which
corresponds to $\sigma^{2}=1$ if we considered image intensities
$0,1/4,2/4,3/4,4/4$) and $k=2$. Now it holds that

$\mathcal{N}_{D}^{k}(x,16)=\mathop{\rm max}\nolimits\\{-k,\mathop{\rm
min}\nolimits\\{k+4,t^{\prime}+x\\}\\},t^{\prime}\sim\mathcal{N}_{D}^{k+4}(0,16).$

Following the Algorithm 2, we start with evaluating
$\mathbb{P}_{t\sim\mathcal{N}_{D}^{6}(0,16)}\llbracket t\leq i\rrbracket$ for
$i=-6,\dots 5$. We note that since the final sample will be $\mathop{\rm
min}\nolimits\\{-2,\mathop{\rm max}\nolimits\\{6,x+t\\}\\}$, then we don’t
need to evaluate $\mathbb{P}\llbracket t\leq a\rrbracket$ for $a>5$.

  * •

$\frac{21}{2^{8}}<\mathbb{P}_{t\sim\mathcal{N}_{D}(0,16)}\llbracket
t\leq-6\rrbracket=0.085<\frac{22}{2^{8}}$

  * •

$\frac{33}{2^{8}}<\mathbb{P}_{t\sim\mathcal{N}_{D}(0,16)}\llbracket
t\leq-5\rrbracket=0.130<\frac{34}{2^{8}}$

  * •

$\frac{48}{2^{8}}<\mathbb{P}_{t\sim\mathcal{N}_{D}(0,16)}\llbracket
t\leq-4\rrbracket=0.191<\frac{49}{2^{8}}$

  * •

$\frac{68}{2^{8}}<\mathbb{P}_{t\sim\mathcal{N}_{D}(0,16)}\llbracket
t\leq-3\rrbracket=0.266<\frac{69}{2^{8}}$

  * •

$\frac{90}{2^{8}}<\mathbb{P}_{t\sim\mathcal{N}_{D}(0,16)}\llbracket
t\leq-2\rrbracket=0.354<\frac{91}{2^{8}}$

  * •

$\frac{115}{2^{8}}<\mathbb{P}_{t\sim\mathcal{N}_{D}(0,16)}\llbracket
t\leq-1\rrbracket=0.450<\frac{116}{2^{8}}$

  * •

$\frac{140}{2^{8}}<\mathbb{P}_{t\sim\mathcal{N}_{D}(0,16)}\llbracket t\leq
0\rrbracket=0.550<\frac{141}{2^{8}}$

  * •

$\frac{165}{2^{8}}<\mathbb{P}_{t\sim\mathcal{N}_{D}(0,16)}\llbracket t\leq
1\rrbracket=0.648<\frac{166}{2^{8}}$

  * •

$\frac{187}{2^{8}}<\mathbb{P}_{t\sim\mathcal{N}_{D}(0,16)}\llbracket t\leq
2\rrbracket=0.734<\frac{188}{2^{8}}$

  * •

$\frac{207}{2^{8}}<\mathbb{P}_{t\sim\mathcal{N}_{D}(0,16)}\llbracket t\leq
3\rrbracket=0.809<\frac{208}{2^{8}}$

  * •

$\frac{222}{2^{8}}<\mathbb{P}_{t\sim\mathcal{N}_{D}(0,16)}\llbracket t\leq
4\rrbracket=0.870<\frac{223}{2^{8}}$

  * •

$\frac{234}{2^{8}}<\mathbb{P}_{t\sim\mathcal{N}_{D}(0,16)}\llbracket t\leq
5\rrbracket=0.915<\frac{235}{2^{8}}$

This set of _breaking-points_ is computed just once before the certification
procedure. In the experiment of Table 1(b), we used $k=6$ (considering image
intensities $[0,\dots 1]$, therefore computed $15\cdot 256-1$ breaking points.
We chose the mapping $g$ to quantize the images in the same way as they were
originally quantized (with a continuation outside of the interval). This was
an arbitrary choice, if we chose twice as dense quantization, we would need to
compute twice the number of breaking points, but the mapping $g$ would
resemble more the identity mapping.

Continuing with the example; We show how to smooth the image at a single
position. First, we obtain a sample from the uniform distribution:
$s\sim\text{Unif}\\{0,1,\dots 2^{8}-1\\}$ and transform it to sample from
(truncated) $\mathcal{N}_{D}^{6}(0,16)$.

$t=\begin{cases}$-6$&\quad\text{if $s\leq 21$,}\\\ $-5$&\quad\text{if $23\leq
s\leq 33$,}\\\ $-4$&\quad\text{if $177\leq s\leq 48$,}\\\ $-3$&\quad\text{if
$50\leq s\leq 68$,}\\\ $-2$&\quad\text{if $70\leq s\leq 90$,}\\\
$-1$&\quad\text{if $92\leq s\leq 115$,}\\\ $0$&\quad\text{if $117\leq s\leq
140$,}\\\ $1$&\quad\text{if $142\leq s\leq 165$,}\\\ $2$&\quad\text{if
$167\leq s\leq 187$,}\\\ $3$&\quad\text{if $189\leq s\leq 207$,}\\\
$4$&\quad\text{if $209\leq s\leq 222$,}\\\ $5$&\quad\text{if $224\leq s\leq
234$,}\\\ $6$&\quad\text{if $236\leq s$,}\\\ Failure&\quad\text{if
$s\in\\{22,34,49,69,91,116,141,166,188,208,223,235\\}$}\end{cases}$

Consequently, we evaluate the smoothed version of pixel $x$ as $x=\mathop{\rm
max}\nolimits\\{-2,\mathop{\rm min}\nolimits\\{6,x+t\\}\\}$. The Failure
corresponds to the fact that we are not able to produce the i.i.d. sample with
this random sample. However, the probability that it occurs is negligible for
$n=64$ as used in experiments.

We also note that it may happen that
$\mathbb{P}_{t\sim\mathcal{N}_{D}(0,16)}\llbracket t\leq k\rrbracket$ would be
actually equal to some quantized point for some $k$, say
$\mathbb{P}_{t\sim\mathcal{N}_{D}(0,16)}\llbracket t\leq
k\rrbracket=\frac{a}{2^{8}}$. In that case (or in a case where the used
precision is not enough to ensure that it is not the case), we would consider
observing both, $s=a$ and $s=a+1$ as a failure.

##  Appendix C Proof of Proposition5.1

Let us inspect the probability of observing some $a\in\\{-k+1,\dots,k+254\\}$.
In that case $\mathbb{P}_{t\sim\mathcal{N}^{k}_{D}(x,\sigma^{2})}\llbracket
t=a\rrbracket=\int_{a-0.5}^{a+0.5}\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{(x-u)^{2}}{2\sigma^{2}}}du$.
For the other distribution it holds that $t^{\prime}=a-x$ and
$\mathbb{P}_{t\sim\mathcal{N}^{k}_{D}(0,\sigma^{2})}\llbracket
t=a-x\rrbracket=\int_{a-x-0.5}^{a-x+0.5}\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{u^{2}}{2\sigma^{2}}}\,du$
and the change of the variable $u\rightarrow v-x$ concludes the proof of this
case. The other two cases are analogical.∎

##  Appendix D Floating-point numbers

###  D.1 Subnormal numbers, NaNs and infs

We continue the discussuion on floating point numbers from Section 3 where we
have omitted some details regarding the floating point numbers. Although it is
not important for understanding the results, we list it for the sake of
completeness.

We note that the introduced floating point representation in Section 3 is not
able to represent $0$ and the smallest representable positive number is
$0000~{}0000$ which is $0.125$ in base $10$. To represent even smaller
numbers, there are so-called subnormal numbers. That is, whenever the exponent
consists only of zeros, there is no implicit $1$ in the mantissa, but the
exponent is higher by one. That is, the exponents represented by bits $000$
and $001$ both correspond to $-2$. If our 8 bit toy arithmetics also used
subnormal numbers, then $0000~{}0000$ would be $0$ and $000~{}0001$ would be
$(0\cdot 1+0\cdot 0.5+0\cdot 0.25+0\cdot 0.125+1\cdot 0.0625)\cdot
2^{-2}=0.015625$. We note that there is a positive and a negative zero (and
also inf).

Similarly, floating-point numbers whose exponents consist only of ones are
special. If additionally the mantissa is all zeros, then it represents inf and
if the mantissa contains a non-zero bit, then it represents not-a-number (NaN)
and the set bits correspond to error messages.

##  Appendix E Integer-arithmetics-only certified robustness for quantized
neural networks

Here we describe why the technique of Lin et al. (2021) for sampling from the
discrete normal distribution and the consequent certification is not
sufficient for our purposes.

The definition of the discrete normal distribution from Lin et al. (2021) is
as follows:

$\mathbb{P}_{x\in\mathcal{N}_{H}(\mu,\sigma^{2})}\llbracket
x=a\rrbracket=Ze^{-\frac{(a-\mu)^{2}}{2\sigma^{2}}},$

where $Z$ is an appropriate normalization constant and the distribution is
supported on the set of integers. For the certification, similarly to the
standard smoothing, first, the lower bound $p$ on the probability of the
correct class for the smoothed classifier is estimated. Then, the robust
radius is computed as $\sigma\Phi_{\mathcal{N}_{H}}^{-1}(p)$, where
$\Phi_{\mathcal{N}_{H}}^{-1}$ is the inverse CDF of discrete Gaussian. This
can be seen at the very bottom of the second column on page 4 in Lin et al.
(2021). Note, in Algorithm $1$ of Lin et al. (2021) there is written only
$\Phi^{-1}$, which according to the neighbouring discussions (and according to
Thm 3.2 there) corresponds to $\Phi_{\mathcal{N}_{H}}^{-1}$. This certified
radius is clearly not exact, because the possible certified radii can only be
$\sigma$ multiples of the quantization levels because the smoothing
distribution is discrete. For $\sigma=1$, the possible robust radii are
$0,1,2,\dots$, while the actual robust radius may clearly be non-integral
which makes sense even when considering quantized inputs; e.g., consider the
perturbation $(1,1,0,\dots)$ which has distance $\sqrt{2}$. Therefore, the
smoothing as described in Lin et al. (2021) is restricted to certify only
integer radii which is a significant restriction.

However, we were not able to verify the correctness of the method proposed in
Lin et al. (2021). In the proof of Theorem 3.1, there is: "Notice that that
$p_{c_{A}}^{lb}=\mathbb{P}[X\in\mathcal{S}_{A}]$, where
$\mathcal{S}_{A}=\\{z:\left\langle
z-x,\delta\right\rangle\leq\sigma\left\|\delta\right\|_{2}\Phi_{\mathcal{N}_{\mathbb{H}}}^{-1}(p_{C_{A}}^{lb})\\}$".
Where $p_{c_{A}}^{lb}$ is the lower bounded probability of the target class.
However, since the smoothing distribution is discrete, the function
$\Phi_{\mathcal{N}_{\mathbb{H}}}^{-1}$ is piecewise constant, therefore there
are probabilities $p_{1}\neq p_{2}$ with
$\Phi_{\mathcal{N}_{\mathbb{H}}}^{-1}(p_{1})=\Phi_{\mathcal{N}_{\mathbb{H}}}^{-1}(p_{2})$,
thus they will both generate the same set $\mathcal{S}_{A}$, but using the
stated fact in the proof, it would yield
$p_{1}=\mathbb{P}[X\in\mathcal{S}_{A}]=p_{2}$, which is absurd. Since the fact
($p_{c_{A}}^{lb}=\mathbb{P}[X\in\mathcal{S}_{A}]$, where
$\mathcal{S}_{A}=\\{z:\left\langle
z-x,\delta\right\rangle\leq\sigma\left\|\delta\right\|_{2}\Phi_{\mathcal{N}_{\mathbb{H}}}^{-1}(p_{C_{A}}^{lb})\\}$)
is given without a proof, we are not able to determine if the obtained
certificates are indeed correct, but possibly weaker, or if they are only
approximate.

##  Appendix F Discussion on presented malicious examples

To reproduce the malicious examples from Section 4, it is important to carry
every computation in the same precision. We tested it for both, single and
double-precision, it likely holds also for the half-precision. If some
calculations are done in single, and some in double precision, then the
claimed results will probably not hold. Specially, if some calculation is
performed in the single precision (e.g., transforming images from
$\\{0,1,\dots,255\\}$ to $\\{0,1/255,\dots,1\\}$), casting it to double
precision afterwards is not sufficient because the low mantissa bits are
already lost. Although the codes are very simple, we enclose some of the
snippets in the supplementary materials. Specially, the classifier $M$ from
Theorem is simplified in a way that it considers only $1000$ random images
instead of $10000$, and the smoothing is performed by $50$ noise samples
instead of $100~{}000$ which we hope is sufficient for the demonstration.

##  Appendix G Algorithms

Here we compare the actual algorithms of the standard randomised smoothing 1,
and of the proposed method 2. The differences in the methods of the same name
are highlighted by colors. The algorithms assume input to be in
$\\{0,1/255,\dots,1\\}$. We emphasize that our method is a simple extension of
the standard randomized smoothing, where the two additional procedures in
Algorithm 2 can be evaluated just once before the certification; thus, they do
not slow down the method, neither it decreases the accuracy.

Algorithm 1 Randomized smoothing certification of Cohen et al. (2019)

1:procedure SampleUnderNoise($f,x,n,\sigma$)

2: $\texttt{counts}\leftarrow[0,0]$

3: for $i\leftarrow 1,n$ do

4: $\epsilon\leftarrow\mathcal{N}(0,\sigma^{2}I)$

5: $x^{\prime}\leftarrow x+\epsilon$

6: if $f(x^{\prime})>0.5$ then

7: $\texttt{counts}[1]\leftarrow\texttt{counts}[1]+1$

8: else

9: $\texttt{counts}[0]\leftarrow\texttt{counts}[0]+1$

10: return counts

11:

12:procedure Certify($f,\sigma,x,n_{0},n,\alpha$)

13: $\texttt{counts0}\leftarrow\textsc{SampleUnderNoise}(f,x,n_{0},\sigma)$

14: $\hat{c}_{A}\leftarrow\text{top index in }\texttt{counts0}$

15: $\texttt{counts}\leftarrow\textsc{SampleUnderNoise}(f,x,n,\sigma)$

16:
$p_{A}\leftarrow\textsc{LowerConfBound}(\texttt{counts}[\hat{c}_{A}],n,1-\alpha)$

17: if $p>\frac{1}{2}$ then

18: return prediction $\hat{c}_{A}$ and radius $\sigma\Phi^{-1}(p)$

19: else

20: return ABSTAIN

Algorithm 2 Sound randomized smoothing certification of $F\circ g_{k}$

1:procedure Precompute array of breaking
points($k,\sigma^{2}$)$\triangleright$ This function is evaluated only once

2: $\texttt{arr}\leftarrow[0,\dots,0]$ $\triangleright$ Array of $2\cdot
255\cdot k+256$ zeros

3: for $i=-255k,255k+254$ do

4: $\texttt{arr}[255k+i]\leftarrow\lceil
2^{64}\int_{-\infty}^{(i+0.5)/255}\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{x^{2}}{2\sigma^{2}}}\,dx\rceil$

5: $\texttt{arr}[2\cdot 255\cdot k+255]\leftarrow 2^{64}$

6: return arr

7:

8:procedure $\mathcal{N}_{D}^{k}$($0,\sigma^{2}I$, idx)$\triangleright$ This
function is evaluated only on the first call with given arguments and the
result is memorized. The relevant arguments are $k,\sigma,\text{idx}$.

9: $\texttt{arr}\leftarrow\text{Precomputed array of breaking points for
}\mathcal{N}_{D}^{k}(0,\sigma^{2})$

10: $\epsilon\leftarrow[0,\dots,0]$ $\triangleright$ Array of $d$ zeros

11: for $i\leftarrow 1,d$ do

12: $t\leftarrow\mathbf{U}(0,2^{64-1})$

13: for $j\leftarrow-255k,255(k+1)$ do

14: if $\texttt{arr}[j+255k]=t$ then

15: return Failure

16: else if $\texttt{arr}[j+k]>t$ then

17: $\epsilon_{i}\leftarrow j/255$

18: Break

19: return $\epsilon$

20:

21:procedure SampleUnderNoise($f,x,n,\sigma,k$)

22: $\texttt{counts}\leftarrow[0,0]$

23: for $i\leftarrow 1,n$ do

24:
${\color[rgb]{1,0,0}\epsilon\leftarrow\mathcal{N}_{D}^{k+1}(0,\sigma^{2},i)}$

25: if ${\color[rgb]{1,0,0}\epsilon\neq\texttt{Failure}}$ then

26: ${\color[rgb]{1,0,0}x^{\prime}\leftarrow\mathop{\rm
min}\nolimits\\{-k,\mathop{\rm max}\nolimits\\{k+1,x+\epsilon\\}\\}}$

27: if $f(x^{\prime})>0.5$ then

28: $\texttt{counts}[1]\leftarrow\texttt{counts}[1]+1$

29: else

30: $\texttt{counts}[0]\leftarrow\texttt{counts}[0]+1$

31: return counts

32:

33:procedure Certify($f,\sigma,x,n_{0},n,\alpha,k$)

34: $\texttt{counts0}\leftarrow\textsc{SampleUnderNoise}(f,x,n_{0},\sigma,k)$

35: $\hat{c}_{A}\leftarrow\text{top index in }\texttt{counts0}$

36: $\texttt{counts}\leftarrow\textsc{SampleUnderNoise}(f,x,n,\sigma,k)$

37:
$p_{A}\leftarrow\textsc{LowerConfBound}(\texttt{counts}[\hat{c}_{A}],n,1-\alpha)$

38: if $p>\frac{1}{2}$ then

39: return prediction $\hat{c}_{A}$ and radius $\sigma\Phi^{-1}(p)$

40: else

41: return ABSTAIN