Title: STATISTICAL VERIFICATION OF GENERAL PERTURBATIONS BY GAUSSIAN SMOOTHING

Abstract: We present a novel statistical certification method that generalizes prior work based on smoothing to handle richer perturbations. Concretely, our method produces a provable classifier which can establish statistical robustness against geometric perturbations (e.g., rotations, translations) as well as volume changes and pitch shifts on audio data. The generalization is non-trivial and requires careful handling of operations such as interpolation. Our method is agnostic to the choice of classifier and scales to modern architectures such as ResNet-50 on ImageNet.
In this work we consider parameterized transformations of data points x ∈ R n . We denote the smoothing transformation with parameter s ∈ R d by ψ s : R n → R n . Further we denote the attacker transformation φ δ : R n → R n with δ ∈ R d as the perturbation that the adversary can apply. We require that ψ and φ compose as ψ s • φ δ = ψ s+δ . Examples of attacker transformations are image rotations and translations as discussed in Section 4. Using this notion of transformation we now define a smoothed classifier: Definition 3.1 (Smoothed Classifier). Given a base classifier f : R n → {1, . . . , k} and a transformation ψ s : R n → R n with s ∈ R d we define a smoothed classifier g f ψ : R n → {1, . . . , k}: g f ψ (x) = arg max c P s (f (ψ s (x)) = c) , s ∼ N (0, Σ)

1. INTRODUCTION:

The success of deep neural networks (Krizhevsky et al., 2012; Silver et al., 2017) and their use in various application domains has triggered a concern to the sensitivity of these models to small, imperceptible perturbations, known as adversarial examples (Szegedy et al., 2014) . Over the last few years there has been substantial interest in finding adversarial examples (Carlini & Wagner, 2017) , empirically (Madry et al., 2018) and provably (Wong & Kolter, 2018; Mirman et al., 2018) defending against them as well as proving the neural network is robust to these (Gehr et al., 2018) . Much of the focus so far has been on restricted, norm-based perturbations and while these cover important attacker models, it has been shown that natural perturbations, e.g., image rotation, can trigger adversarial behaviors not covered by norm-based attacks (Engstrom et al., 2017) .

In this work we focus on certifying a neural network against a wider class of perturbations, by generalizing a recently presented statistical technique (Lecuyer et al., 2018; Cohen et al., 2019) , called smoothing, for creating classifiers that are provably robust against certain norm-based attacks. The basic idea behind smoothing is to sample many possible perturbations of the input, classify each of them, and use the aggregate information to make a final robust classification. Overall, the method provides statistical guarantees for l 2 -norm robustness around a given input (e.g., an image). In our work, we generalize this method to also handle perturbations of the parameters of a given transformation (e.g., the angle of a rotation). This generalization means that we can now apply and study the effectiveness of smoothing across a wider range of interesting perturbations (e.g., image rotation and translation), not previously possible. The generalization is non-trivial and requires careful handling of operations such as interpolation.

Our main contributions are:

• A generalization of the Gaussian smoothing framework to a richer class of perturbations, with a local robustness guarantee on the parameters of the perturbation.

• The first statistical verifier able to certify rotations and translations of images. The system scales to large input sizes and networks such as ImageNet classification. Concretelyamong other results -we are the first to create and certify a provable ImageNet classifier (with high confidence) for image translation and rotation.

• An evaluation showing the strengths and limitations of the smoothing approach across a richer class of perturbations than previously possible.

2. RELATED WORK:

We now survey the most closely related work in exact and statistical certification as well as richer perturbations beyond norm-based attacks.

Exact Certification: complete and incomplete methods To defend against l p norm bound adversarial examples, many techniques have been developed to verify that a classification is stable in the presence of an attacker. These techniques include complete methods which guarantee a proof of robustness or provide a counter example, such as SMT solvers (Ehlers, 2017; Katz et al., 2017; Bunel et al., 2018) , as well as incomplete methods which are sound but may suffer from false positives due to too much approximation error. Examples of these include abstract interpretation based methods (Gehr et al., 2018; Gowal et al., 2018; Singh et al., 2019) , linear relaxations (Zhang et al., 2018; Weng et al., 2018) and semi definite programming (Raghunathan et al., 2018) . Kurakin et al. (2017) ; Madry et al. (2018) train empirically robust networks by including adversarial examples in the training set. Wang et al. (2018a; b) replace the softmax layer to increase adversarial robustness.

While both methods improve empirical robustness, the method does not provide a formal certificate.

Provable defenses (which use incomplete methods) aim to address the issue to some degree by training networks in a way where they are more provable (Mirman et al., 2018; Wong & Kolter, 2018) . However, because complete methods are not scalable and incomplete methods lose precision (by design), exact formal certification and training of large-scale networks with good absolute guarantees is a challenging task and remains an active area of research.

Statistical Certification via Smoothing One can trade the absolute (exact) guarantees for probabilistic ones by using smoothed classifiers that scale to much larger networks (Lecuyer et al., 2018; Li et al., 2018; Cohen et al., 2019; Salman et al., 2019) . A smoothed classifier g can be built out of an ordinary classifier f by taking the majority vote among perturbed inputs x, i.e., f (x + δ) where δ is drawn from a probability distribution. Smoothing has the advantage that it scales to large models, however, it can suffer from an added overhead during inference time, and currently only provides l 2 robustness statistical certification on limited input perturbations (e.g., pixels of an image). In this space, Lecuyer et al. (2018) presented the first certified robustness method based on randomized smoothing. Later, Li et al. (2018) Certification of geometric transformations Beyond l p norm bound attacks, a more realistic attacker model includes perturbations such as geometric attacks, i.e., rotations, translations and shearing (Engstrom et al., 2017; Kanbak et al., 2018) . Work on certification against geometric attacks was performed by (Pei et al., 2017) using enumeration and (Singh et al., 2019) using abstract interpretation. Neither work scales to large networks and images. Thus, an interesting question is whether we can handle more complex perturbations (e.g., rotations) on larger networks. Towards this, in the rest of the paper, we show a generalization of the smoothing method to this richer class of transformations.

for a covariance matrix Σ (symmetric positive definite matrix).

Algorithm 1 for prediction

# evaluate g at x function PREDICT(f , Σ, x, n, α, ψ) counts ← SAMPLE(f , x, n, Σ, ψ) ĉA , ĉB ← top two indices in counts n A , n B ← counts[ĉ A ], counts[ĉ B ] if PVALUETEST(n A , n A + n B , 0.5) ≤ α return ĉA else return ABSTAIN Algorithm 2 for certification # certify the robustness of g around x function CERTIFY(f , Σ, x, n 0 , n, α, ψ) counts0 ← SAMPLE(f, x, n 0 , Σ, ψ) ĉA ← top index in counts0 counts ← SAMPLE(f, x, n, Σ, ψ) p A ← LBOUND(counts[ĉ A ], n, 1 -α) if p A > 1 2 return ĉA and R else return ABSTAIN

As it is usually clear from the context, we drop sub-and super-script and just write g.

Given this definition we state our main theorem on the robustness of the smoothed classifier w.r.t attacks φ. This is an adapted version of the main theorem presented in Cohen et al. (2019) :

Theorem 3.2. We assume a fixed but arbitrary data point x ∈ R n , base classifier f : R n → {1, . . . , k} and transformation ψ s : R n → R n . Further we allow an attacker to choose δ and apply

φ δ (x), s.t. ψ s • φ δ = ψ s+δ . Then: If P(f (φ s (x) = c A ) = p A ≥ p A ≥ p B = p B = max c B =c A P(f (φ s (x) = c B ) then g(ψ δ (x)) = c A for all δ such that √ δ T Σ -1 δ < Φ -1 (p A )-Φ -1 (p B ) 2 .

Proof. The proof is similar to the one given by Cohen et al. (2019) and is stated in Appendix A.

Throughout the paper we refer to

Φ -1 (p A )-Φ -1 (p B ) 2

as the certification radius R.

The key differences to Cohen et al. (2019) are: (i) we allow general transformations ψ rather than only additive noise, and (ii) we consider a full covariance matrix Σ rather than an isotropic one. Specifically for ψ s (x) = x + s and Σ = σ 2 I n , our theorem exactly recovers the statement from Cohen et al. (2019) . These two additions enable us to tackle many interesting transformations. Due to the similarity of Theorem 3.2 to their main theorem we can also use very similar versions of their algorithms, shown in Algorithms 1 and 2. Theorem 3.2 is a deterministic statement, as the only involved random variable s is integrated out. However in practice, the theorem only holds with a certain probability as we have finite amount of samples to estimate p A (or p A ) and p B (or p B ). The function SAMPLE(f , x, n, Σ, ψ) returns n samples of f (ψ s (x)), s ∼ N (0, Σ). These samples are then used in a statistical test to determine p A or test if it is > 1 2 with certainty 1 -α for a given α. In both algorithms p B = 1 -p A . The probability that Algorithm 1 returns a class other than g(x) is at most α and with probability of at least 1 -α Algorithm 2 does not abstain.

4. EXAMPLE PERTURBATIONS:

We now discuss several practical perturbations ψ which are important and can be handled by our generalization. Specifically, we will consider low parameter image transformations such as changes in contrast and brightening as well as geometric transformations such as rotation and translation, which require special attention to deal with interpolation. Further, we describe low parameter audio transformations such as changes in volume or pitch.

4.1. IMAGE PERTURBATIONS & INTERPOLATIONS:

Interpolation A major issue with image transformations such as rotation and translation (for noninteger offsets) is interpolation. A pixel in the transformed image maps to a location in the original image (not necessarily on the pixel grid) where the pixel value is taken from. To obtain the value, we need to interpolate it. Typical interpolations for images are nearest-neighbor interpolation, bilinear interpolation and bicubic interpolation. Further, if the transformation moves a coordinate outside of the original image, the pixel value is commonly set to (0, 0, 0)

T (black).

We explore the issues created by interpolation using the example of rotation, the same method applies to other geometric transformations. We denote the rotation and subsequent interpolation of an image x ∈ R n by an an angle β as rotate β (x). In general rotate β • rotate γ = rotate β+γ due to interpolation. Thus, if we choose ψ β := rotate β , this does not compose with an angle γ chosen by an attacker φ γ . To formalize this problem we write (rotate β • rotate γ )(x) = rotate β+γ (x) + β,γ (x) where β,γ (x) denotes the interpolation error.

Modeling Interpolation We address this by modeling the composition of two rotations as a single rotation together with addition of l 2 noise. The smoothing operation against an attacker utilizing rotation is

ψ s (x) = ψ β η (x) := rotate β (x) + η.

For ease of notation we write ψ β,η .

We will let the attacker choose δ = ( γ 0 ) but in truth apply δ = ( γ ω ) for a ω yet to be determined to offset the interpolation error. Thus we can model the overall attacking and smoothing process as:

(ψ β,η • φ γ,ω )(x) = ψ β+γ,η+ω (x) = rotate β+γ (x) + η + ω = rotate β • rotate γ (x) -β,γ (x) + η + ω.

(1)

Now choosing ω = β,γ (x) we can get rid of the introduced interpolation errors. Thus, our overall transformation ψ β,η • φ γ,ω recovers the semantic of ψ β,η • φ γ,0 without interpolation. Instantiating Theorem 3.2 with this transformation and Σ = σ 2 r 0 0 σ 2 i In , where I n denotes the n × n Identity matrix, we obtain the bound:

δT Σ -1 δ < R R>0 = == ⇒ δT Σ -1 δ < R 2 =⇒ σ -2 r γ 2 + σ -2 i ωT ω < R 2 =⇒ γ 2 < σ 2 r R 2 -σ -2 i β,γ (x) 2 2 =⇒ |γ| < σ r R 2 -σ -2 i E 2 (2)

with E upper bounding β,γ (x) 2 ≤ E. In the first step we also need to assume that R > 0. When R is negative (or term under the root is negative) we take the bound |γ| = 0.

Approach Using Eq. ( 2), we can derive an algorithm that certifies a range of rotation angles and extend CERTIFY to return |γ| rather than R. There are four ways one can proceed here:

Per-Input Global Optimization: If we are given a fixed image x and a range [γ min , γ max ] we can calculate the worst case interpolation error by performing global optimization over γ ∈ [γ min , γ max ] and β ∈ [-180, 180] . In CERTIFY we would first calculate E before proceeding with the rest of the procedure. This procedure can be improved by only considering β ∈ [-3σ r , 3σ r ], which likely simplifies the optimization problem and still covers 99.7% of possible angles.

Per-Input Sampling: Similar to the global optimization approach, we can, for a given x and a range [γ min , γ max ] sample different interpolation errors and obtain a probabilistic guarantee on E.

Training Set Global Optimization: If we assume that our x will come from the data distribution we can already pre-compute the maximal E over the training set.

Training Set Sampling: Again assuming that x follows the data distribution we can sample different E over the training set and rotation angles and take the maximum.

There are two major downsides here: (i) the global maximum of the error norm might be quite large even though the majority of values is actually quite small and (ii) approaches based on the training set or sampling might not find the correct maxima and only provide probabilistic guarantees.

In practice (see Fig. 2 ; discussed later) most error norms are small under certain assumptions. However, some are vast outliers. This effectively rules out taking the maximum of E (either for specific x or over the whole dataset) as it becomes essentially impossible to obtain a bound in Eq. ( 2). This rules out taking the global maxima of the error as E.

Further, we need to consider that sampling many interpolation errors for a specific image can be done but is expensive. Rotating an m × l color image with bilinear interpolation requires around 74 • l • m floating point operations which quickly becomes a bottleneck. This rules out creating a new set of samples for every image.

For these two reasons we see computing a probabilistic bound P(E ≤ t) ≤ ε over the training set offline as the only viable way. We treat each sample as a boolean random variable and obtain the Clopper-Pearson upperbound (Clopper & Pearson, 1934) ε with confidence 1 -ρ.

Probabilistic Guarantees Assume that in CERTIFY or PREDICT we observe ñA and ñB examples of classes c A and c B when taking n = ñA + ñB samples. As in Cohen et al. (2019) , we can estimate pA , the probability that we observe c A , and lower bound it by pA with confidence 1 -α.

Due to our probabilistic guarantee on E, there are samples that can not be trusted as Eq. ( 2) and subsequently the bound on δ in Theorem 3.2 is not satisfied. When estimating p A and p B we must account for these bad samples. Specifically we can assume that in the worst case all of these samples would have counted towards class c A and construct a conservative lower bound. We can model the real chance of observing clean samples from c A , denoted p A by using the union bound:

EQUATION

Since we had confidence 1-α and 1-ρ for pA and ε the confidence p A for 1-α-ρ. In Cohen et al. (2019) the authors note that the probability that PREDICT returns a wrong class and that CERTIFY abstains are both at most α, when p A was estimated with confidence 1 -α. The same applies to our probabilistic approach, but the failure rate becomes α + ρ. Fig. 1 shows the overall bound on |γ|.

Finally, as we obtained our probabilistic guarantee on E with sampling from γ ∈ U([-γ min , γ max ]), we need -in order to be sound -mention that we do not guarantee robustness for all γ covered by Theorem 3.2, but only those intersecting with [-γ min , γ max ].

4.2. INTERPOLATION-FREE PIXEL TRANSFORMATION:

While we mainly focus on dealing with image perturbations that introduce interpolation error, there are many that do not. A simple class here are perturbations that are additive operations in some color space (RGB, HSV, HSL, etc.). For example, to model brightness we consider the perturbation ψ β (x) = x + β • 1 in RGB space where 1 is the vector of ones with the same dimensions as the image x. The equation can easily be adapted to have different β per color channel or even per region of the image. We can also model multiplicative changes, by bounding them in the exp domain. As an example, we consider changes in contrast, ψ β (x) = 128 + e β (x -128)

ψ β • φ γ (x) = 128 + e β • e γ • (x -128) = 128 + e β+γ • (x -128) = ψ β+γ (x)

However we can not combine additive and multiplicative perturbations into linear transformations without additional assumptions about the order in which perturbations are applied.

The perturbation of the attacker is likely applied to the image in integer space (i.e., each pixel intensity value is an integer in {0, . . . , 255}). Thus after applying additive or multiplicative scaling the value might be rounded. Hence, to show that perturbations with value |β| are safe, we have to verify that in fact |β + 1| is safe (depending on the exact rounding behavior adding 1 2 might be sufficient). For multiplicative changes, a corresponding safety margin can be calculated.

4.3. AUDIO PERTURBATIONS:

The domain of audio data has similar challenges as the one for image processing. As before, we handle low parameter attacks like shifts in pitch or changes in volume:

Volume The volume of an audio signal can be changed by multiplying the signal with a constant. The smoothing operation is ψ β (x) := e β •x and similarly the adversary operation is φ γ (x) := e γ •x. We see that the composition is additive in the parameter space:

ψ β • φ γ (x) = e β • e γ • x = e β+γ • x = ψ β+γ (x),

where we clip values exceeding the range of the values of x back when needed. Pitch shifts We let DFT denote the discrete Fourier transform and IDFT is its inverse. The transformation that shifts an audio signal by β is ψ β (x) := IDFT(β + DFT(x)). Further, for an attacker φ γ := IDFT(γ + DFT(x)) the composition of these two is again additive in the parameter space:

ψ β • φ γ (x) = IDFT(β + DFT(IDFT(γ + DFT(x)))) = IDFT(β + γ + DFT(x)) = ψ β+γ (x)

, where we again neglected the frequencies exceeding the frequency range of the applied DFT. Further, β and γ are rounded to the frequency steps of the DFT, requiring bound similar to Section 4.2.

5. EVALUATION:

Setup We evaluated our algorithm on a machine with 16 CPU cores running at 3.5GHz and a GeForce RTX 2080 Ti. We run the perturbation on the images in parallel on CPU and evaluate the network on the GPU with a batch size of 64 in PyTorch (Paszke et al., 2017) .

ImageNet Pipeline and Interpolation Error:

In our evaluation we use the ImageNet classification dataset (Russakovsky et al., 2015) . While our algorithm works for general image datasets (with a few restrictions, discussed later in this section) we will specifically discuss this dataset as we require the specifics of the image classification pipleline to precisely model and discuss perturbations. The images in the ImageNet training dataset range in size from 20 × 17 to 7056 × 4488. Some classifiers are adaptive in the input size, but most neural network based methods are fixed to take images of size 224 × 224 (Krizhevsky et al., 2012; He et al., 2016) . Thus the standard procedure is to first resize the image such that the shorter side has length 256 and then take the 224 × 224 center of the image and run the classifier on this image. We denote all of this preprocessing as preprocess(x). A side effect of this preprocessing is that rotation of less than |γ| ≤ 8.13 degrees is applied to an image, then the preprocessed image will not have black corners, as tan -1 256-224 224 = 8.13 gives the largest angle for which this holds based on the resizing and cropping size.

Further, many image pipeline implementations can perform these perturbations on floating point images or 8-bit-integer-based images. In the integer case the result of the interpolation is rounded to the closest value in {0, . . . , 255}. In this work we assume the transformations are performed in integer space as this models a more realistic attacker. We let τ denote the function that maps images from the integer domain to the [0, 1] floating point domain, by dividing by 255. When adding noise, the pixel values might exceed their bounds, thus they are clamped to 0 and 255 or to 0 and 1 respectively, by the clamping function clamp. To facilitate faster training (Simonyan & Zisserman, 2015) the pixel intensities have their mean subtracted and are scaled to have a standard deviation of 1. This is known as normalization (normalize).

In general we can ignore all preprocessing and replace the base classifier f with f = f • normalize • clamp • τ • preprocess, but in this section we need to specifically look at the interactions between this and the smoothing procedure. While one would, based on everyday experience assume that interpolation errors are small, the l 2 norm can be surprisingly large. For a large sample of images x from the training and pairs of angles β, γ we measure the norm of the interpolation error β,γ (x) . We observed a mean error of 3.9 with a standard deviation of 3.3 and a maximum of 60.1 A key observation is, that larger images have lower errors. For example, taking a random 250 × 250 image x from the ImageNet training set and calculating (τ

•preprocess)(x)-(τ •preprocess • rotate -8 • rotate 8 )(x)

2 yields a value of 5.5, but still a very similar image. For comparison the largest l 2 perturbations considered in provable robustness are around 3.8 (Cohen et al., 2019; Salman et al., 2019) .

Scaling the image up by a factor of 4 before performing this routine reduces the error norm already to 1.49. This is not merely an artifact of scaling up the images, but that larger images in general have a quite low error, as can be seen for example in Fig. 2 which shows interpolation errors ˆ for images such that the shorter side is at least 2000 pixels long.

Rotation & Translation To apply rotation and translation we use the framework developed in Section 4. However, in practice we apply the rotation before any preprocessing (as this is where the real attacker would do), and the error-offsetting l 2 noise after, as preprocessing operations such as down-scaling and cropping tend to reduce it. This does not weaken the attacker, but is only a technical detail of the implementation. So specifically we consider a classifier f = f •normalize • clamp and a perturbation ψβ+γ,η+ω (x) = (τ

• preprocess • rotate β • rotate γ (x)) -ˆ + η + ω. where ˆ = (τ • preprocess • rotate β • rotate γ )(x) -(τ • preprocess • rotate β+γ )(x).

Replacing the perturbation and in Eq. ( 1) with these ultimately yields to a smaller bound on E in Eq. ( 2). Due to the size issues outlined before, we consider only images from ImageNet where the shorter side has at least 2000 pixels. Fig. 2 shows the distribution over ˆ over a sample of these images and different angles β ∼ N (0, 5 2 ), γ ∈ U ([-8, 8] ). We chose these distributions to model the errors, actually observed during the smoothing procedure: Here we assume an attacker to choose γ ∈ [-8, 8] and σ r = 5. Based on these samples we derive P(E ≤ t) listed in Table 1 . More details, including histograms for translations are given in Fig. 3 in the Appendix.

We now evaluate our algorithm on the images of the ImageNet test set, where the shorter side is at least 2000 pixels, of which there are 65. Since we are largely bound by the l 2 robustness of the classifier we use two classifiers from Salman et al. ( 2019), which were trained to be robust base classifiers for l 2 Gaussian smoothing: S 0.5 denotes a ResNet-50 (He et al., 2016) trained with SMOOTHADV PGD , σ = 0.5, = 1.0, which had the best approximate certified test accuracy for a noise levels of 1.0 and 1.5 and S 1.0 denotes the same model trained with σ = 1.0. While this has slightly worse performance it was trained with a higher σ (robustness to l 2 noise, allowing us to use a larger σ n . On our data the base classifier S 0.5 was correct on 36 samples and S 1.0 on 19. Further, we are using E = 1.25, σ n = 0.75, σ r = 5, α = 0.001, ρ = 0.001, n 0 = 100, n = 10000, and bilinear interpolation.

The results are shown in Table 2 where we consider the following evaluation metrics: (i) Abstained shows how often the classifier did not return a certified classification, (ii) Verified is how often a radius larger than 0 was proven to be correct for a class (note that the verification is approximate with the stated confidence), (iii) Accurately Verified shows how many samples could be verified for the same class as the base classifier predicted, and (iv) Correctly Verified shows how many samples were verified and also had the correct label to the dataset.

The biggest trade-off in these experiments is choosing σ n as large as possible, to obtain a good bound in Eq. ( 2). However, at the same time this lowers the accuracy and thus decreases the bound. Interestingly more samples don't necessarily help us as much as they do in Cohen et al. (2019) as our estimate of p A is fundamentally limited by Eq. (3).

For rotation with S 0.5 the mean ± standard deviation is 3.24 ± 0.77 degrees for the verified examples and 3.56 ± 0.50 degrees for S 1.0 . For transformation on S 0.5 , dx dy 2 ≤ 10.70 ± 3.60, where dx and dy denotes the offset in x and y direction respectively. To be sound we would need to limit dx and dy to at most ±2 as this was our assumption when obtaining E, but the distribution for larger changes is similar to the one obtained for ±2 so an argument for the full range can be made. The average run time to certify rotations with n = 10000 is 256.27s and for translations 250.02s.

We conclude that the main bottlenecks are the inequality Eq. ( 3), the accuracy of the base classifier and its robustness to l 2 allowing us to choose larger σ n .

Brightness and Contrast:

In contrast to the perturbations that perform interpolation we do not need to use Eq. ( 2) but can directly use Theorem 3.2. So for brightness changes and contrast changes we use Σ = σ (a scalar), and since for this task we don't specifically need an l 2 robust network, we use a standard ResNet-50 (He et al., 2016) from PyTorch Torchvsion (Paszke et al., 2017) , denoted as R, as well as S 0.5 from before. The results are shown in Tables 3 and 4 . For brightness we use σ = 12 and for contrast σ = 0.2 as well as σ = 0.4. For both we use n 0 = 100, n = 10000 and α = 0.001 and observe an average evaluation time for n = 10000 of 24.01 s. To be sound w.r.t. integer rounding we need to subtract 1 and 0.0008 from the β in Table 3 and Table 4 respectively. The results highlight how much the accuracy and robustness of the base classifier aid verification. R is much more accurate than S 0.5 allowing us to certify large ranges of brightness changes.

6. CONCLUSION:

We presented a way to extend the Gaussian Smoothing framework (Cohen et al., 2019) to interesting perturbations in application domains such as image and audio classification. In our evaluation we showed that the approach is applicable to complex tasks such as ImageNet classification, although we believe that improvements to classifiers and application domain specific insights can strongly improve the results. We believe that this work makes Gaussian Smoothing applicable outside the often considered l p -ball and will trigger further work in this direction.

Proof.

p s+δ (z) p s (z) = exp -1 2 (z -δ) T Σ -1 (z -δ) + 1 2 z T Σ -1 z = exp -1 2 z T Σ -1 z + z T Σ -1 δ -1 2 δ T Σ -1 δ + 1 2 z T Σ -1 z = exp z T Σ -1 δ -1 2 δ T Σ -1 δ

What is the lowest t if it exists such that p s+δ (z) ps(z) ≤ t?

p s+δ (z) p s (z) ≤ t ⇔ exp z T Σ -1 δ -1 2 δ T Σ -1 δ ≤ t ⇔ z T Σ -1 δ -1 2 δ T Σ -1 δ ≤ log t ⇔ z T Σ -1 δ ≤ log t + 1 2 δ T Σ -1 δ

Because z ∈ A, we know that

z T Σ -1 δ ≤ √ δ T Σ -1 δΦ -1 (p c ).

Does there exist a t such that both upper bound coincide? Yes, namely 

t = exp √ δ T Σ -1 δΦ -1 (p c ) -1 2 δ T Σ -1 δ .

The proof for Eq. ( 6) and Eq. ( 7) are analogous to the proofs for Eq. ( 4) and Eq. ( 5). Now we derive the conditions that lead to P(s + δ ∈ A) > P(s + δ ∈ B):

P(s + δ ∈ A) = P δ T Σ -1 (s + δ) ≤ √ δ T Σ -1 δΦ -1 (p c ) = P δ T Σ -1 ( √ ΣN (0, 1) + δ) ≤ √ δ T Σ -1 δΦ -1 (p c ) = P δ T √ Σ -1 N (0, 1) + δ T Σ -1 δ ≤ √ δ T Σ -1 δΦ -1 (p c ) = P √ δ T Σ -1 δN (0, 1) + δ T Σ -1 δ ≤ √ δ T Σ -1 δΦ -1 (p c ) = P N (0, 1) + √ δ T Σ -1 δ ≤ Φ -1 (p c ) = P N (0, 1) ≤ Φ -1 (p c ) - √ δ T Σ -1 δ = Φ(Φ -1 (p c ) - √ δ T Σ -1 δ)

Similarly, we have

P(s + δ ∈ B) = P N (0, 1) ≥ Φ -1 (1 -p c ) - √ δ T Σ -1 δ = Φ( √ δ T Σ -1 δ -Φ -1 (1 -p c ))

:



Figures and Tables:

Figure 1: Bound for |γ| in the case where the base classifier f returns the class c A for all samples for σ r = 1. Different values of σ r scale the bound multiplicatively.

Figure 2: Histogram of ˆ β,γ (x) 2 for bilinear interpolation after preprocessing for x sampled from the training set, s.t. its shorter side is at least 2000 pixels.

Next, we claim that forB := {z | δ T Σ -1 z ≥ √ δ T Σ -1 δΦ -1 (1 -p c )} holds that P(f • ψ s (x) = c ) ≤ P(s ∈ B) (6) P(f • ψ s+δ (x) = c ) ≤ P(s + δ ∈ B)

ε from samples via Clopper Pearson Interval bounds with 99.9% confidence.

Table content: <table><tr><td/><td colspan="4">interpolation P(E &lt; 1.00) P(E &lt; 1.25) P(E &lt; 1.50)</td></tr><tr><td/><td>nearest</td><td>0.51</td><td>0.71</td><td>0.83</td></tr><tr><td>rotation</td><td>bilinear</td><td>0.21</td><td>0.96</td><td>0.97</td></tr><tr><td/><td>bicubic</td><td>0.09</td><td>0.96</td><td>0.96</td></tr><tr><td/><td>nearest</td><td>0.56</td><td>0.55</td><td>0.60</td></tr><tr><td>translation</td><td>bilinear</td><td>0.21</td><td>0.99</td><td>0.99</td></tr><tr><td/><td>bicubic</td><td>0.07</td><td>0.90</td><td>0.99</td></tr></table>

Certification results for translation and rotation with 99.8% confidence.

Table content: <table><tr><td colspan="3">Transformation Model Abstained</td><td colspan="3">Verified Accurately verified Correctly verified</td></tr><tr><td>rotation</td><td>S 0.5</td><td colspan="2">23 (35%) 10 (15%)</td><td>8 (12%)</td><td>6 ( 9%)</td></tr><tr><td>rotation</td><td>S 1.0</td><td colspan="2">16 (25%) 10 (15%)</td><td>5 ( 8%)</td><td>3 ( 5%)</td></tr><tr><td>translation</td><td>S 0.5</td><td colspan="2">15 (23%) 20 (31%)</td><td>11 (17%)</td><td>9 (14%)</td></tr></table>

Certification for brightness changes and rotation with 99.9% confidence.

Table content: <table><tr><td colspan="2">Model Abstained</td><td colspan="3">Verified Accurately Verified Correctly Verified</td><td>β</td></tr><tr><td>R</td><td colspan="2">20 (20%) 80 (80%)</td><td>70 (70%)</td><td>64 (64%) 20.37 ± 14.59</td></tr><tr><td>S 0.5</td><td colspan="2">47 (47%) 53 (53%)</td><td>47 (47%)</td><td>25 (25%) 15.65 ± 12.61</td></tr></table>

Certification for contrast changes and rotation with 99.9% confidence.

Table content: <table><tr><td colspan="2">Model σ</td><td>Abstained</td><td colspan="3">Verified Accurately Verified Correctly Verified</td><td>β</td></tr><tr><td>R</td><td>0.2</td><td colspan="2">44 (44%) 56 (56%)</td><td>49 (49%)</td><td>45 (45%) 0.21 ± 0.17</td></tr><tr><td>R</td><td>0.4</td><td colspan="2">73 (73%) 27 (27%)</td><td>22 (22%)</td><td>19 (19%) 0.27 ± 0.21</td></tr><tr><td>S 0.5</td><td>0.2</td><td colspan="2">77 (77%) 23 (23%)</td><td>14 (14%)</td><td>14 (14%) 0.15 ± 0.10</td></tr><tr><td>S 0.5</td><td>0.4</td><td colspan="2">90 (90%) 10 (10%)</td><td>6 (6%)</td><td>5 (5%) 0.23 ± 0.18</td></tr></table>

Peer review (iclr2020):
In this paper, the authors generalize the randomized smoothing type of robustness certification to handle many types of attacks beyond norm-based attacks, e.g., geometric perturbation, volume change, pitch shifts on audio data. At the core of the proposed generalization is using some interpolation which I think is quite straightforward. 1. How about the scenario when both rotation and translation exist? 2. In experiments, can the authors consider the accuracy of the certified model under the adversarial setting, i.e., find the transformation that makes the deep nets performs worst? 3. Besides randomized smoothing on the input images, recently Wang et al showed that randomize the deep nets can also improve the deep nets and they gave it a nice theoretical interpretation. Here is the reference: Bao Wang, Binjie Yuan, Zuoqiang Shi, Stanley J. Osher. ResNets Ensemble via the Feynman-Kac Formalism to Improve Natural and Robust Accuracies, arXiv:1811.10745, NeurIPS, 2019 4. Interpolation idea has been used in improving robustness of deep nets, for example: 1). Bao Wang, Xiyang Luo, Zhen Li, Wei Zhu, Zuoqiang Shi, Stanley J. Osher. Deep Neural Nets with Interpolating Function as Output Activation, NeurIPS, 2018 2). Bao Wang, Alex T. Lin, Zuoqiang Shi, Wei Zhu, Penghang Yin, Andrea L. Bertozzi, Stanley J. Osher. Adversarial Defense via Data Dependent Activation Function and Total Variation Minimization, arXiv:1809.08516, 2018 3). B. Wang, S. Osher. Graph Interpolating Activation Improves Both Natural and Robust Accuracies in Data-Efficient Deep Learning, arXiv:1907.06800 In sum, this paper studies the problem of certifying a broad class of adversarial attacks which is decent, however, the novelty is quite limited. Please address my questions during rebuttal.