Deterministic Certification to Adversarial Attacks via
Bernstein Polynomial Approximation

In practice, the best empirical defense is Adversarial Training (AT) (Goodfellow, Shlens, and Szegedy 2015) (Kurakin, Goodfellow, and Bengio 2017) (Madry et al. 2018). AT is operated by first generating the adversarial examples by projected gradient descent and then augmenting them into the training set. Although the classifier yielded based on AT is robust to most gradient-based attacks, it is still difficult to tell whether this classifier is undoubtedly robust. Moreover, adaptive attacks break most empirical defenses. A pioneering study (Athalye, Carlini, and Wagner 2018) showed that most of the methods are ineffective by using sophisticated designed attacks. To stop this arms race between attackers and defenders, some researchers try to focus on building a verification mechanism with a robustness guarantee.

Certified defenses can be divided into exact (a.k.a “complete”) methods and conservative (a.k.a “incomplete”) methods. Exact methods are usually based on Satisfiability Modulo Theories solvers (Katz et al. 2017a) (Katz et al. 2017b) or mixed-integer linear programming (Tjeng, Xiao, and Tedrake 2019), but they are computationally inefficient. Conservative methods are guaranteed to find adversarial examples if they exist but might mistakenly judge a safe data point as an adversarial one (false positive) (Wong and Kolter 2018) (Wong et al. 2018) (Salman et al. 2019b) (Wang et al. 2018b) (Wang et al. 2018a) (Dvijotham et al. 2018) (Raghunathan, Steinhardt, and Liang 2018a) (Raghunathan, Steinhardt, and Liang 2018b) (Croce, Andriushchenko, and Hein 2019)(Gehr et al. 2018) (Mirman, Gehr, and Vechev 2018) (Singh et al. 2018) (Weng et al. 2018) (Gowal et al. 2018) (Zhang et al. 2018).

Introducing randomness into neural network classifiers has been used as a heuristic defense method against adversarial perturbation. Some works (Liu et al. 2018) (Cao and Gong 2017) introduced randomness without provable guarantees. (Lecuyer et al. 2019) first used inequalities from differential privacy to prove robustness guarantees of $\ell_{2}$ and $\ell_{1}$ norm with Gaussian and Laplacian noises, respectively. Later on, (Li et al. 2019) used information theory to prove a stronger $\ell_{2}$ robustness guarantee for Gaussian noise. All these robustness guarantees are still loose. (Cohen, Rosenfeld, and Kolter 2019) provided a tight robustness guarantee for randomized smoothing.

(Salman et al. 2019a) integrated randomized smoothing with adversarial training to improve the performance of smoothed classifiers. (Zhai et al. 2020) (Feng et al. 2020) both considered natural and robust errors in their loss function. The authors tried to maximize the certified radius during training. These methods have great success using randomized smoothing but some researchers (Ghiasi, Shafahi, and Goldstein 2020) (Kumar et al. 2020) (Blum et al. 2020) raised concerns about randomized smoothing.

(Kumar et al. 2020) (Blum et al. 2020) claimed that extending the smoothing technique to defend against other attacks can be challenging, especially in the high-dimensional regime. The largest $\ell_{p}$-radius that can be certified decreases as $O(1/d^{\frac{1}{2}-\frac{1}{p}})$ with dimension $d$ for $p>2$. This means that the radius decreases due to the curse of dimensionality.

According to (Miyato et al. 2018), spectral normalization controls the Lipschitz constant of neural networks that were originally used in stabilizing the training of the discriminator in GANs. The formulation is stated as:

which is equivalent to being divided by the greatest singular value of $W_{i}$, the weights of $i$-th layer. Suppose that our feature extractor $G$ (see Figure 2) is the composition function composed of Lipschitz continuous functions $g_{i}(x^{(i)};W_{SN}^{(i)}):=ReLU(W_{SN}^{(i)}x^{(i)}+b^{(i)})$, where $x^{(i)}$ is the output of $g_{i-1}$ and $b^{(i)}$ is the bias for $i=1,2,\cdots,M$, $i.e.$,

where $x^{(1)}=I$ is the input data. For each $g_{i}$ we have

Given two input data $I$ and $I^{\prime}$, and by Equation (1), we have $\|W_{SN}^{(i)}\|_{2}=1$ for $i=1,2,\cdots,M$. We can derive that the Lipschitz constant of $G$ is one by Equation (2) and (3) as:

If $G(I)\neq G(I^{\prime})$, there exists an $R>0$ such that

We can further observe from Equation (4) that the upper bound of the certified radius is tighter in feature domain than that in the image domain.

Weierstrass approximation theorem asserts that a continuous function on a closed and bounded interval can be uniformly approximated on that interval by polynomials to any degree of accuracy. All of the formal definitions are described as follows (Davis 1975).

Bernstein proved the Weierstrass Approximation theorem in a probability approach (Bernstein 1912). The rationale behind Bernstein polynomial is to compute the expected value $\mathbb{E}[f(\eta/n)]$, where $\eta\sim Bin(n,x)$ and $Bin(n,x)$ is the binomial distribution. Note that the parameter $n$, relating to how it can be used to smooth the classifier, will be elaborated in detail later. The following Definition 1 and Theorem 2 are from (Bernstein 1912).

Back to Theorem 1, we can take it as a corollary of Theorem 2. Since the neural network is a multi-dimensional function, we have to generalize the one dimensional Bernstein polynomial (Definition 1) into a multi-dimensional version. The following is one kind of generalization which considers independent random variables expectation (Veretennikov and Veretennikova 2016).

To find the certified radius of the input data, different from (Cohen, Rosenfeld, and Kolter 2019), we are not trying to find a closed form solution. Instead, we propose to use numerical root-finding techniques to find an adversarial example in the feature domain.

We abbreviate the notation by setting $\beta_{i}=B_{n}(f_{i};x)$ and $S(\beta)_{i}=\exp(\beta_{i})/\sum_{j=1}^{K}\exp(\beta_{j})$, where $K$ is the number of classes. Note that $S(\beta)$ is the traditional softmax function which represents the probability vector. Also, recall that $d\leq K$ is the dimension of a feature vector $x_{0}$.

In the worst case analysis, the runner-up class is the easiest target for attackers. Hence, we assume that the closest point to a feature vector $x_{0}$ on the decision boundary between the top two predictions of the smoothed classifier $\tilde{f}(x)=\beta=[\beta_{1},\cdots,\beta_{K}]$ follows $\beta_{\rho(1)}=\beta_{\rho(2)}$, where $\rho$ is the mapping from ranks to predictions. Therefore, the nonlinear systems of equations for characterizing the points on the decision boundary of smoothed classifier $\tilde{f}(x)$ are described as:

where $\phi_{0}$ can be seen as the decision boundary between the top two predictions, and $\phi_{1}$ and $\phi_{2}$ are the probabilities of the top two predictions, respectively. The remaining equations indicate that the probabilities other than $\rho(1)$ and $\rho(2)$ are all zeros. The only thing we need to do is to start from the initial guess (feature vector $x_{0}$) and find the adversary nearest to it.

To solve Equation (9), we transform it into a minimization problem. We consider the function $\Phi:^{d}\rightarrow^{d}$, $\Phi=(\phi_{0},\phi_{1},\cdots,\phi_{d})$, and minimize $\frac{1}{2}\|\Phi(x)\|_{2}^{2}$ is equivalently to finding

where $F(x)=\frac{1}{2}\sum\limits_{i=0}^{d}(\phi_{i}(x))^{2}=\frac{1}{2}\|\Phi(x)\|_{2}^{2}.$

Suppose that $x^{*}$ is the optimal solution to Equation (9), that is, $\Phi(x^{*})=0$. According Equation (10), we have $F(x^{*})=0$ and $F(x)>0$ if $\Phi(x)\neq 0$. The details of how to solve Equation (10) are described in the Appendix. Let sol denote the solution of Equation (10), we can easily compute $R=\|x_{0}-\emph{sol}\|_{p}$ for $p>1$, which is known as the certified radius. Remark that this radius is computed in the feature domain (see Equation (4)). On the other hand, we prove that our method satisfies the following proposition specialized in norm independence.

The proof can be found in the Appendix.

Suppose that we have a pre-trained model for the purpose of either prediction or certification. The prediction is a simple substitution of a smoothed classifier for the base classifier. Hence, we mainly illustrate our smoothing and certification procedures in Algorithm 1 and 2, respectively.

We are interested in three significant metrics, natural accuracy, robust accuracy, and certified accuracy. Natural accuracy is the number of correctly identified clean testing examples divided by the number of total testing examples. Robust accuracy is the number of correctly identified adversarial testing examples divided by the number of total testing examples. Certified accuracy at radius $R$ is defined as the fraction of testing examples correctly predicted by the classifier and are provably robust within an $\ell_{2}$ ball of radius $R$. For brevity, we define the certified accuracies at all radii as “certified curve”.

The architecture of our method is illustrated in Figure 2. We trained the model by adding spectral normalization to every layer of feature extractor $G$ and reducing the feature vector’s dimension to a small number. According to (Salman et al. 2019a), they employ PGD adversarial training to improve the certified curve empirically. Hence, we aslo incorporated it into our model architecture at the expense of decreasing the natural accuracy slightly. As for inference, we applied the reduced feature $d$ to find the exact distance to the decision boundary by using root-finding algorithms from scipy.optimize package (Virtanen et al. 2020). Details of the algorithm we used will be further discussed in the Appendix.

We employed a 110-layer residual network as our base model for a reasonable comparison, which was also adopted in (Cohen, Rosenfeld, and Kolter 2019) and (Salman et al. 2019a). Furthermore, there are two primary hyperparameters: the parameter $n$ and the dimension $d$ of the feature vector, affecting our smoothed model.

We certified a subset of 500 examples from the CIFAR-10 test set, as done in (Cohen, Rosenfeld, and Kolter 2019) and (Salman et al. 2019a), that was released on the Github pages. Our method took 6.48 seconds to certify each example on an NVIDIA RTX 2080 Ti with $n=1$, while 15 seconds are required in (Cohen, Rosenfeld, and Kolter 2019) under the same setting.

We primarily compare with (Cohen, Rosenfeld, and Kolter 2019) and (Salman et al. 2019a) as they were shown to outperform all other provable $\ell_{2}$-defenses thoroughly. Recall that our method is norm-independent, as described in Proposition 1, we did the experiment in $\ell_{2}$ norm to compare with their results. As our work claims to maintain high natural accuracy, we utilized $\sigma=0.12$ and $\sigma=0.25$ from (Cohen, Rosenfeld, and Kolter 2019) and (Salman et al. 2019a), which lead to the top two natural accuracy of their results. For (Salman et al. 2019a), we took one of their results: PGD adversarial training with two steps and $\epsilon=64/255$ for comparison since it has the highest natural accuracy among all of their settings. Note that the results are directly taken from their GitHub pages.

Although we added additional components such as spectral normalization (SN) to the base model for training, the natural accuracy only dropped from 93.7% to 93.5%, which nearly carries no harm than adding Gaussian noise for data augmentation. Then, by applying PGD adversarial training with 20 steps and $\|\epsilon\|_{2}=0.1$ to the base model with SN, the accuracy dropped from 93.5% to 87.6%. We call the adversarial trained model “baseline” in Table 1. We applied our method with $n=1$ to the “baseline” model and got 87.4% accuracy, which is the highest accuracy among the methods used for comparison. As shown in Figure 4, we have the following observations for comparison results:

1. 1.

   Our method obtains a higher natural accuracy at $R=0$.

2. 2.

   Our method exhibits higher certified accuracies at lower radii ($R<0.5$) but still obtains non-zero accuracies at larger radii ($R>1.0$).

To check the rationality of our theoretical results, the empirical upper bounds of the certified curve obtained from practical attacks (PGD attack) were used for comparison. Although there are some uncertainties in root finding, the default of the sum of squares error and the approximate solution error are set to $1.49\times 10^{-8}$ which is an acceptable error. Therefore, we can observe from Figure 5 that our certification results approximate the empirical upper bounds. The errors caused by spectral normalization and other possible reasons are discussed in the Appendix.

We can observe from Algorithm 1, where $K$ is the number of the classes of a dataset, $n$ and $d$ are the parameters in Equation (7), the complexity is $O(Kn^{d})$. As $K$ increases, the algorithm may cost an unacceptable time. Therefore, due to the high computational complexity, ImageNet (Deng et al. 2009) was not considered in our results. The scalability of our work would be an interesting issue for future study.

Our method involves some issues, including dimension reduction, different model architectures, and hyperparameters, that may affect the performance. To explore the effectiveness of each part, we conduct ablation studies.

First, the robust accuracy should be proportional to the certified accuracy theoretically. We conducted an experiment to find $n$ that results in the best robust accuracy. From Table 1, we observe that as $n=1$ and $n=7$, the natural accuracy and the robust accuracy under PGD are the highest among all $n$s. Since our method with $n=1$ spends the lowest computation time, we used $n=1$ in all the other experiments. Remark that our method is a certification instead of a defense method. Thus, as we chose $n=1\sim 7$, natural accuracy and robust accuracy are slightly lower than the baseline. However, we discover an intriguing phenomenon in other datasets and models in that we may have better natural accuracy and robust accuracy than the baseline with a proper choice of $n$ (see Table 4 in the Appendix).

Second, on the left side of Figure 6, we show that adversarial training is still a useful heuristic strategy that improves the certified curve while sacrificing only limited natural accuracy at radius = $0$.

In addition, the dimension of the feature vector influences the certified curve a lot. We can observe from the right side of Figure 6 that the feature dimensions of length five and six lead to the best certified curve. However, the larger dimension, the longer the computation time. This is why the feature dimension is set to be five in our experiments. Since our feature domain is constrained in the $[0,1]^{d}$, there is an upper bound of the certified radius, which is the dimension’s square root if we choose $\ell_{2}$ norm.

Finally, we find that most black-box certification methods only exploit one model in their experiments, which is considered insufficient in some cases. Different model architectures may differ a lot in the certified curve. Hence, we employ several models, including ResNet, WideResNet, VGG, and DenseNet, to support our claim. (See Figure 8 in the Appendix.)

In a regression problem, one often has a large amount of features. To prevent over-fitting to the training dataset, feature engineering provides a sophisticated design. Most of them are based on statistical tools to select very few representative data. However, it might also not be able to prevent over-fitting and perform worse with respect to unseen data. Our method provides a post-processing step to smooth the original regression model and preserve its shape. Figure  7 shows an example to verify our claim.