\section{Introduction}
Data poisoning \cite{biggio2012poisoning,jagielski2018manipulating,shafahi2018poison,steinhardt2017certified,zhu2019transferable}
is a training-time attack where the attacker is assumed to have access to the training data on which the victim will train the model.
The attacker can modify the training data
in a manner that the model trained on this poisoned data performs as the attacker desires.
The data hungry nature of modern machine learning methods make them vulnerable to poisoning attacks. Attackers can place the poisoned data online and wait for it to be scraped by victims trying to increase the size for their training sets.
Another easy target for data poisoning is data collection by crowd sourcing where malicious users can corrupt the data they contribute. In most cases, an attacker can modify only certain parts of the training data such as change the features or labels for a specific class or modify a small subset of the data from all classes.
In this work, we assume the attacker wants to affect the performance of the victim's models on a target class and modifies only the features of the points belonging to that class (without affecting the labels). To evade detection, the attacker is constrained to only add imperceptibly small perturbations to the points of the target class.
Many previous works \cite{munoz2017towards,shafahi2018poison,huang2020metapoison,koh2017understanding,zhu2019transferable,chen2017targeted,ji2017backdoor,turner2018clean} have shown the effectiveness of poisoning in affecting the accuracy of models trained on poisoned data compared to the accuracy achievable by training with clean data. In most works, the victim is assumed to use standard training by minimizing the empirical loss on the poisoned data to train the models and thus the attack is optimized to hurt the accuracy of standard training.
However, recent research on test-time evasion attacks \cite{carlini2017adversarial,athalye2018obfuscated,uesato2018adversarial,bulusu2020anomalous} suggests that models trained with standard training are not robust to adversarial examples, making the assumption of victim relying on standard training to train the models for deployment questionable.

\begin{figure*}[tb]
  \centering{\includegraphics[width=0.99\textwidth]{images/overview_c.pdf}}
  \caption{Overview of our poisoning against certified defenses (PACD) attack which generates poisoned data to reduce the certified robustness of the victim's model trained with methods such as Gaussian data augmentation(GA)\cite{cohen2019certified}, SmoothAdv\cite{salman2019provably} and MACER\cite{zhai2020macer} on a target class.

  }
  \label{fig:overview}
\end{figure*}

Thus, in a realistic scenario, where the aim of the victim is to deploy the model, it's better to assume that the victim will rely on training procedures that yield classifiers which are provably robust to test-time attacks.
Several recent works have proposed methods for training certifiably robust models whose predictions are guaranteed to be constant in a neighbourhood of a point. However, many of these methods \cite{raghunathan2018semidefinite,gowal2018effectiveness,huang2019achieving,xu2020automatic} do not scale to deep neural networks or large datasets, due to their high complexity. Moreover, the effect of training data quality on the performance of these certified defenses at test time remains largely unexplored.
Recently, randomized smoothing (RS) based certification methods \cite{lecuyer2019certified,li2019certified,cohen2019certified} were shown to be scalable to deep neural networks and high dimensional datasets enabling researchers to propose training procedures \cite{salman2019provably,zhai2020macer} that lead to models with high certified robustness.
Thus, we assume that a victim will rely on RS based certification methods to measure the certified robustness and use RS based training procedures to train the models.
The fact that a victim can train with a method that improves certified adversarial robustness is an immediate challenge for current poisoning attacks which optimize the poison data to affect the accuracy of models trained with standard training.
Table~\ref{Table:difficulty_of_poisoning} shows that poisons optimized against standard training can significantly reduce the accuracy of the victim's model (left to right) when the victim also uses standard training (1st and 5th row). However, this poison data is rendered ineffective when the victim uses a certifiably robust training method such as \cite{cohen2019certified,salman2019provably,zhai2020macer}.

\emph{Are certified defenses robust to data poisoning?}
We study this question and demonstrate that data poisoning is a serious concern even for certified defenses.
\begin{table}
  \caption{Failure of traditional data poisoning attacks optimized against standard training in affecting the test accuracy (of target class) of models trained with certifiably robust training procedures. Details of the experiment are present in Appendix~\ref{app:standard_acc}. Certifiably robust training methods \cite{cohen2019certified,salman2019provably,zhai2020macer} are trained with $\sigma$ = 0.25 and accuracy of their base classifiers are reported.

  }
  \label{Table:difficulty_of_poisoning}
  \centering
  \small
  \resizebox{0.9\columnwidth}{!}{
    \begin{tabular}{c|c|c|c}
    \toprule
    &\multirow{1}{*}{\makecell{Training method }} & \multicolumn{1}{c|}{\makecell{Model trained \\ on clean data}} & \multicolumn{1}{c}{\makecell{Model trained \\ on  poison data}} \\
    \midrule
    \multirow{4}{*}{\STAB{\rotatebox[origin=c]{90}{MNIST}}} &
    Standard & 	99.28$\pm$0.01 & 60.08$\pm$12.6 \\
    &\makecell{GA\cite{cohen2019certified}} & 	98.99$\pm$0.14  & 98.31$\pm$1.65\\
    &SmoothAdv \cite{salman2019provably}&  99.18$\pm$0.23  & 99.31$\pm$0.29\\
    &MACER \cite{zhai2020macer}&  99.21$\pm$0.56  & 98.31$\pm$0.58\\
    \midrule
    \midrule
    \multirow{4}{*}{\STAB{\rotatebox[origin=c]{90}{CIFAR10}}} &
    Standard &  92.71$\pm$1.31  & 0.36$\pm$0.37 \\
    &\makecell{GA \cite{cohen2019certified}} &  88.84$\pm$2.39  & 88.38$\pm$2.13\\
    &SmoothAdv \cite{salman2019provably} & 79.48$\pm$2.69   &	74.95$\pm$3.45\\
    &MACER \cite{zhai2020macer}& 	87.12$\pm$1.17  &	88.54$\pm$4.52\\
    \bottomrule
    \end{tabular}
    }
\end{table}
We propose a novel data poisoning attack that can significantly compromise the certified robustness guarantees achievable from training with robust training procedures. We formulate the Poisoning Against Certified Defenses (PACD) attack as a constrained bilevel optimization problem and theoretically analyze its solution for the case when the victim uses linear classifiers. Our theoretical analysis and empirical results suggests that the decision boundary of the smoothed classifiers (used for RS) learned from
the poisoned data is significantly different from the one learned from clean data there by causing a reduction in certified radius.
Our bilevel optimization based attack formulation is general since it can generate poisoned data against a model trained with any certifiably robust training method (lower-level problem) and certified with any certification procedure (upper-level problem). Fig.~\ref{fig:overview} shows the overview of the proposed PACD attack.

Unlike previous poisoning attacks that aim to reduce the accuracy of the models on a small subset of data, our attack can reduce the certified radius of an entire target class.
The poison points generated by our attack have clean labels and imperceptible distortion making them difficult to detect.
The poison data remains effective when the victim trains the models from scratch or uses data augmentation or weight regularization during training. Moreover, the attack points generated against a certified defense are transferable to models trained with other RS based certified defenses and to models with different architectures.
This highlights the importance of training-data quality and curation for obtaining meaningful gains from certified defenses at test time, a factor not considered by current certified defense research.

Our main contributions are as follows
\begin{itemize}
    \item We study the problem of using data poisoning attacks to affect the robustness guarantees of classifiers trained using certified defense methods. To the best of our knowledge, this is the first clean label poisoning attack that significantly reduces the certified robustness guarantees of the models trained on the poisoned dataset.

    \item We propose a bilevel optimization based attack which can generate poison data against several robust training and certification methods. We specifically use the attack to highlight the vulnerability of randomized smoothing based certified defenses to data poisoning.

    \item We demonstrate the effectiveness of our attack in reducing the certifiable robustness obtained using randomized smoothing on models trained with state-of-the-art certified defenses \cite{cohen2019certified,salman2019provably,zhai2020macer}. Our attack reduces the ACR of the target class by more than 30\%.

\end{itemize}

\vspace{-0.3cm}
\section{Background and related work}
{\bf Randomized smoothing:}
The RS procedure \cite{cohen2019certified} uses a smoothed version of the original classifier $f:\mathbb{R}^d \xrightarrow{} \mathcal{Y}$ and certifies the adversarial robustness of the new classifier. The smoothed classifier, $g(x) = \arg \max_c \mathbb{P}_{\eta \sim \mathcal{N}(0, \sigma^2I)}(f(x+\eta)=c)$, assigns $x$ the class whose decision region $\{x' \in \mathbb{R}^d: f(x') = c\}$ has the largest measure under the distribution $\mathcal{N}(x, \sigma^2I)$, where $\sigma$ is used for smoothing. Suppose that while classifying a point $\mathcal{N}(x, \sigma^2I)$, the original classifier $f$ returns the class $c_A$ with probability $p_A = \mathbb{P}(f(x + \eta) = c_A)$, and the “runner-up” class $c_B$ is returned with probability $p_B = \max_{c \neq c_A} \mathbb{P}(f(x + \eta) = c)$, then the prediction of the point $x$ under the smoothed classifier $g$ is robust within the radius $r(g;\sigma) = \frac{\sigma}{2}(\Phi^{-1}(p_A) - \Phi^{-1}(p_B)),$ where $\Phi^{-1}$ is the inverse CDF of the standard Normal distribution. In practice, Monte Carlo sampling is used to estimate a lower bound on $p_A$ and an upper bound on $p_B$ as its difficult to estimate the actual values for $p_A$ and $p_B$.
Since standard training of the base classifier does not achieve high robustness guarantees, \cite{cohen2019certified} proposed to use GA based training in which the base classifier is trained on Gaussian noise corruptions of the clean data. Recent works \cite{zhai2020macer,salman2019provably} showed that the certified robustness guarantees of RS can be boosted by using different training procedures. In particular, \cite{salman2019provably} proposed to train the base classifier using adversarial training where the adversarial examples are generated against the smoothed classifier.
Although effective at increasing the certified radius, the method can be slow to train due to the requirement of generating adversarial examples against the smoothed classifier at every step. Another recent work \cite{zhai2020macer} proposed a different training procedure which is significantly faster to train and relies on directly maximizing the certified radius for achieving high robustness guarantees. Due to their effectiveness in improving the certified robustness guarantees of machine learning models, we craft poison data against these methods. A recent attack method \cite{ghiasi2020breaking} showed that it is possible to fool a robust classifier to mislabel an input and give an incorrect certificate using perturbation large in $\ell_p$ norm at test-time.
Our work is different since we focus on train-time attacks against certified defenses using imperceptibly small perturbations to the poison data.

{\bf Bilevel optimization:}
A bilevel optimization problem has the form $\min_{u \in \mathcal{U}} \xi(u,v^*)\;\mathrm{s.t.}\;v^* = \arg\min_{v\in \mathcal{V}(u)}\;\zeta(u,v)$, where the upper-level problem is a minimization problem with $v$ constrained to be the optimal solution to the lower-level problem (see \cite{bard2013practical}). Our data poisoning attack is a constrained bilevel optimization problem. Although general bilevel problems are difficult to solve, under some simplifying assumptions their solution can be obtained using gradient based methods. Several methods for solving bilevel problems in machine learning have been proposed previously \cite{domke2012generic,pedregosa2016hyperparameter,franceschi2017forward,maclaurin2015gradient,shaban2018truncated,mehra2019penalty} (See Appendix~\ref{app:approxgrad} for an overview). We use the method based on approximating the hypergradient by approximately solving a linear system (ApproxGrad Alg.~\ref{alg:approxgrad} in Appendix~\ref{app:approxgrad}) in this work.
Previous works \cite{mei2015using,munoz2017towards,mehra2019penalty,huang2020metapoison,carnerero2020regularisation} have shown the effectiveness of solving bilevel optimization problem for data poisoning to affect the accuracy of models trained with standard training. Our work on the other hand proposes a bilevel optimization based formulation to generate a data poisoning attack against RS based certified defenses and shows its effectiveness against state-of-the-art robust training methods.

\section{Poisoning against certified defenses}
Here we present the bilevel formulation of our PACD attack for generating poisoned data to compromise the certified robustness guarantees of the models trained using certified defenses. Specifically, we discuss how to generate poison data against GA \cite{cohen2019certified}, SmoothAdv \cite{salman2019provably} and MACER \cite{zhai2020macer} and affect the certified robustness guarantees obtained using RS.

\subsection{General attack formulation}
Let $\mathcal{D^\mathrm{clean}} = \{(x_i^\mathrm{clean}, y_i^\mathrm{clean})\}_{i=1}^{N_{\mathrm{clean}}}$
be the clean, unalterable portion of the training set. Let $u=\{u_1,...,u_n\}$ denote the attacker's poisoning data which is added to the clean data.
For clean-label attack, we require that each poison example $u_i$ has a limited perturbation, for example, $\|u_i - x_i^\mathrm{base}\| =\|\delta_i\| \leq \epsilon$ from the base data $x_i^\mathrm{base}$ and has the same label $y_i^\mathrm{base}$, for $i=1,...,n$. Thus $\mathcal{D^\mathrm{poison}} = \{(u_i, y_i^\mathrm{base})\}_{i=1}^{N_{\mathrm{poison}}}$.
The goal of the attacker is to find $u$ such that when the victim uses $\mathcal{D^\mathrm{clean}} \bigcup \mathcal{D^\mathrm{poison}}$ to train a classifier,
the certified robustness guarantees of the model on the target class ($\mathcal{D^\mathrm{val}} = \{(x_i^\mathrm{val},y_i^\mathrm{val})\}_{i=1}^{N_\mathrm{val}}$) are significantly diminished compared to a classifier trained on clean data.
The attack can be formulated as follows:
\begin{equation}
    \begin{split}
        &\min_{u \in \mathcal{U}}\;\; \mathcal{R}(\mathcal{D}^\mathrm{val}; \theta^\ast) \\

        \mathrm{s.t.}\;\; \theta^* = \arg&\min_{\theta}\; \mathcal{L}_\mathrm{robust}(\mathcal{D^\mathrm{clean}} \bigcup \mathcal{D^\mathrm{poison}}; \theta).
    \end{split}
    \label{eq:bilevel_simple}
\end{equation}
The upper-level cost $\mathcal{R}$ denotes a certified robustness metric such as the certified radius from RS.
The goal of the upper-level problem is to compromise the certified robustness guarantees of the model trained on validation data $\mathcal{D}^\mathrm{val}$.
The solution to the lower-level problem $\theta^\ast$ are the parameters of the machine learning model learnt from $\mathcal{D^\mathrm{clean}} \bigcup \mathcal{D^\mathrm{poison}}$ using a robust training method with loss function $\mathcal{L}_\mathrm{robust}$.
The fact that any training method that achieves high certified robustness to test-time attacks and any certification procedure can be incorporated into this formulation by changing the lower- and upper-level problems, respectively, makes the attack formulation broadly applicable.
Recent works \cite{cohen2019certified,salman2019provably,zhai2020macer} have shown RS based methods to be effective at certifying and producing robust classifiers.
The scalability of these methods to large datasets and deep models make them useful for real-world application.
Thus, we focus on using our poisoning attack against these methods.

\subsection{Poison randomized smoothing based defenses}
For an input at test time, RS produces a prediction from the smoothed classifier $g$ and a radius in which this prediction remains constant.
Since the certified radius of a ``hard'' smooth classifier $g$ is non-differentiable, it cannot be directly incorporated in the upper-level of the attack formulation Eq.~(\ref{eq:bilevel_simple}).
To overcome this challenge, we use the ``soft'' smooth classifier $\tilde{g}$ as an approximation. Similar technique has been used in \cite{salman2019provably, zhai2020macer}.
Let $z_{\theta}:X\xrightarrow{}\mathcal{P}(K)$ be a classifier whose last layer is softmax with parameters $\theta$ and $\sigma > 0$ is the noise used for smoothing, then soft smoothed classifier $\Tilde{g}_{\theta}$ of $z_{\theta}$ is
\(\Tilde{g}_{\theta}(x) = \arg \max_{c \in Y} \mathbb{E}_{\eta \sim \mathcal{N}(0,\sigma^2I)}[z^c_{\theta}(x + \eta)].\)
It was shown in \cite{zhai2020macer} that if the ground truth of an input $x$ is $y$ and $\Tilde{g}_{\theta}$ classifies $x$ correctly
then $\tilde{g}_{\theta}$ is provably robust at $x$, with the certified radius $\tilde{r}(\tilde{g}_{\theta}; x, y, \sigma) = \frac{\sigma}{2}[\Phi^{-1}(\mathbb{E}_{\eta}[z^y_{\theta}(x + \eta)]) - \Phi^{-1}(\max_{y' \neq y}\mathbb{E}_{\eta}[z^{y'}_{\theta}(x + \eta)])].$
Assuming $\tilde{r}(\tilde{g}_{\theta}; x, y, \sigma) = 0$ when $x$ is misclassified, the ACR is $\tilde{R}(\tilde{g}_{\theta}; \mathcal{D}, \sigma) = \frac{1}{|\mathcal{D}|}\sum_{(x,y) \in \mathcal{D}} \tilde{r}(\tilde{g}_{\theta}; x, y, \sigma).$
Since $\tilde{R}$ is differentiable we can use it in the upper-level of Eq.~(\ref{eq:bilevel_simple}). The lower-level problem can be any robust training procedure and we focus on using \cite{cohen2019certified,zhai2020macer,salman2019provably} in this work.

{\bf Poisoning against GA \cite{cohen2019certified}.}
We start by showing how to generate poison data against models trained with GA \cite{cohen2019certified}, which was shown to yield higher certified robustness compared to models trained with standard training. In this method the classifier $f_{\theta}$ is obtained by optimizing the loss function $\mathcal{L}_\mathrm{GaussAug}(\mathcal{D};\theta,\sigma) = \frac{1}{|\mathcal{D}|}\sum_{(x_i,y_i) \in \mathcal{D}} l_{ce}(x_i+\eta,y_i;\theta)$, where $l_{ce}$ is the cross entropy loss and $\eta\sim \mathcal{N}(0,\sigma^2 I)$. To control the perturbation added to the poison data we used $\ell_\infty$-norm here but other norms can also be used. The bilevel formulation to generate poison data to reduce the certified robustness guarantees obtained using RS for a classifier trained with GA is as follows.
\begin{equation}
    \begin{split}
        &\min_{u}\;\; \tilde{R}(\tilde{g}_{\theta^*}; \mathcal{D}^\mathrm{val}, \sigma) \\
        &\mathrm{s.t.}\;\; \|\delta_i\|_{\infty} \leq \epsilon,\;\;  i=1,...,n,\;\;\mathrm{and} \\
        \theta^* = \arg&\min_{\theta}\; \mathcal{L}_\mathrm{GaussAug}(\mathcal{D^\mathrm{clean}} \bigcup \mathcal{D^\mathrm{poison}}; \theta,\sigma).
    \end{split}
    \label{Eq:Bilevel}
\end{equation}

\begin{figure*}[tb]
  \centering{\includegraphics[width=0.99\textwidth]{images/poisoning_two_cases_cropped.pdf}}
  \caption{Analytical solutions of problem (\ref{eq:bilevel_linear}) with linear classifiers. The poison distribution $(P^{-}_\mathrm{poison})$ can change the decision boundary (broken line) and reduce the ACR of the clean distribution $(P^{-})$ in two ways (Cases 1 and 2). Perturbation is exaggerated for illustration.}
  \label{fig:linear}
\end{figure*}

\begin{algorithm
\caption{Poisoning GA based certified defense \cite{cohen2019certified}
}
\label{alg:main}
\textbf{Input}: $\mathcal{D}^\mathrm{clean}, \mathcal{D}^\mathrm{base}, \mathcal{D}^\mathrm{val}, \mathrm{perturbation \;strength}\; \epsilon, \\ \mathrm{noise \;level}\; \sigma, \mathrm{number\; of\; noise\; samples}\; k, \\ \mathrm{inverse\; temperature}\;\alpha, \mathrm{total\; epochs}\; P,\\  \mathrm{lower-level\; epochs}\; T_1, \mathrm{epochs\; for \;linear\; system}\;T_2$ \\
\textbf{Output}: $\mathcal{D}^\mathrm{poison}$
\begin{algorithmic}
\STATE{$\mathcal{D}^\mathrm{poison} := \mathcal{D}^\mathrm{base}$}
\FOR{$p=0,\;\cdots\;,P\textrm{-}1$}
    \STATE{Sample a mini-batch $(x^\mathrm{clean}, y^\mathrm{clean}) \;\sim\; \mathcal{D}^\mathrm{clean}$}
    \STATE{Sample a mini-batch of $n$ points $(x^\mathrm{val}, y^\mathrm{val}) \;\sim\; \mathcal{D}^\mathrm{val}$}
    \STATE{Sample a mini-batch $(x^\mathrm{poison}, y^\mathrm{poison}) \;\sim\;\mathcal{D}^\mathrm{poison}$}
    \STATE{Pick the base samples for poison data $(x^\mathrm{base}, y^\mathrm{base})$}
    \STATE{For each $x^\mathrm{val}_{i}$, sample $k$ i.i.d. Gaussian samples}
    \STATE{$x^\mathrm{val}_{i_1}, \cdots , x^\mathrm{val}_{i_n} \sim \mathcal{N}(x^\mathrm{val}_{i}, \sigma^2I)$}

    \STATE{Compute $\tilde{z}_{\theta}(x^\mathrm{val}_i) \xleftarrow{} \frac{1}{k} \sum^k_{j=1} \alpha z_{\theta}(x^\mathrm{val}_{i_j})$ for each $i$}
    \STATE{$\mathcal{G_{\theta}} := \{(x^\mathrm{val}_i, y^\mathrm{val}_i): y^\mathrm{val}_i = \arg \max_{c \in \mathcal{Y}}\; \tilde{z}^c_{\theta}(x^\mathrm{val}_i)\}$}
    \STATE{}
    \STATE{For each $(x_i, y_i) \in \mathcal{G_{\theta}}$, compute $\tilde{y}_i$}
    \STATE{$\tilde{y}_i \xleftarrow{} \arg \max_{c \in \mathcal{Y}\textbackslash\{y_i\}} \tilde{z}^c_{\theta}(x_i)$}
    \STATE{For each  $(x_i, y_i) \in \mathcal{G_{\theta}}$, compute $\tilde{r}(x_i, y_i)$}
    \STATE{$\tilde{r}(x_i, y_i) = \frac{\sigma}{2}(\Phi^{-1}(\tilde{z}^{y_i}_{\theta}(x_i)) - \Phi^{-1}(\tilde{z}^{\tilde{y}_i}_{\theta}(x_i)))$}
    \STATE{}
    \STATE{$\xi :=  \frac{1}{n}\sum_{(x_i, y_i) \in \mathcal{G_{\theta}}}\tilde{r}(x_i, y_i)$}
    \STATE{$\zeta :=  \mathcal{L}_\mathrm{GaussAug}((x^\mathrm{clean}, y^\mathrm{clean}) \bigcup (x^\mathrm{poison}, y^\mathrm{poison}), \sigma)$}
    \STATE{$(x^\mathrm{poison}, y^\mathrm{poison}):=$ApproxGrad$(\xi, \zeta, 1, T_1, T_2,\epsilon,x^{base})$}
    \STATE{Update $\mathcal{D}^\mathrm{poison}$ with $(x^\mathrm{poison}, y^\mathrm{poison})$}
\ENDFOR
\end{algorithmic}
\end{algorithm}

{\bf Poisoning against MACER \cite{zhai2020macer}.} Another recent work proposed a method for robust training by maximizing the certified radius (MACER). Their approach uses a loss function which is a combination of the classification loss and the robustness loss of the soft smoothed classifier $\tilde{g}_\theta$. In particular, the loss of the smoothed classifier on a point $(x,y)$ is given by $l_{macer}(\tilde{g}_\theta; x, y) = -\mathrm{log} \;\hat{z}^y_{\theta}(x) + \frac{\lambda \sigma}{2} \mathrm{max}\{\gamma - \tilde{\xi}_{\theta}(x, y), 0\}\cdot\mathbf{1}_{\tilde{g}_{\{\theta}(x)=y\}}$. where $\eta_1, ..., \eta_k$ are $k$ i.i.d. samples from $\mathcal{N}(0, \sigma^2\mathbf{I})$, $\hat{z}^y_{\theta}(x) = \frac{1}{k}\Sigma^k_{j=1} z^y_{\theta}(x + \eta_j)$ is the empirical expectation of $z_{\theta}(x + \eta)$, $\tilde{\xi}_{\theta}(x, y) = \Phi^{-1}(\hat{z}^y_{\theta}(x)) - \Phi^{-1}(\mathrm{max}_{y \neq y} \hat{z}^{y'}_{\theta}(x))$, $\gamma$ is the hinge factor, and $\lambda$ balances the accuracy and robustness trade-off. Using this we can define $\mathcal{L}_\mathrm{macer}(\mathcal{D};\theta,\sigma) = \frac{1}{|\mathcal{D}|}\sum_{(x_i,y_i) \in \mathcal{D}} l_{macer}(\tilde{g}_{\theta};x_i,y_i)$. To generate poison data that reduces the robustness guarantees of classifier trained with MACER we can use the loss $\mathcal{L}_\mathrm{macer}(\mathcal{D};\theta,\sigma)$ in the lower-level problem in Eq.~(\ref{Eq:Bilevel}).

{\bf Poisoning against SmoothAdv \cite{salman2019provably}.}  It was shown that the certified robustness guarantees obtained from RS can be improved by training the classifiers using adversarial training with adversarial examples generated against the smooth classifier. In particular the classifier trained with SmoothAdv optimizes the following objective for a point $(x,y)$.
$\min_{\theta}\max_{\|x' - x\|_2 \leq \alpha} -\mathrm{log} \frac{1}{k}\Sigma^k_{j=1} z^y_{\theta}(x' + \eta_j)$ where $\eta_1, ..., \eta_k$ are $k$ i.i.d. samples from $\mathcal{N}(0, \sigma^2\mathbf{I})$ and $\alpha$ is the permissible $\ell_2$ distortion to $x$. To generate poisoning data against SmoothAdv we must use this objective as the lower-level problem in Eq.~(\ref{Eq:Bilevel}). To make it easier for bilevel solvers to solve this problem we use an approximation to the mini-max problem. For doing that we first compute the adversarial example
$x' = \arg\max_{\|x' - x\|_2 \leq \alpha} -\mathrm{log} \frac{1}{k}\Sigma^k_{j=1} z^y_{\theta}(x' + \eta_j)$ using PGD attack on the points in $\mathcal{D^\mathrm{clean}} \bigcup \mathcal{D^\mathrm{poison}}$ and then use these examples as our new dataset to train the model parameters in the lower-level as in Eq.~(\ref{Eq:Bilevel}). Specifically, the lower-level problem in Eq.~(\ref{Eq:Bilevel}) becomes $\arg\min_{\theta}\; \mathcal{L}_\mathrm{GaussAug}(\mathcal{D}^\mathrm{clean}_{adv} \bigcup \mathcal{D}^\mathrm{poison}_{adv}; \theta,\sigma)$ where $\mathcal{D}_{adv}$ denotes the adversarial examples generated against $\tilde{g}_{\theta}$. We update $\mathcal{D}_{adv}$ in every step of the bilevel optimization.
\vspace{-0.1cm}
\subsection{Generation and evaluation of poisoning attack}
In this work, we focus on creating a poisoned set to compromise the certified adversarial robustness guarantees of all points in a target class. We initialize the poison data with clean data from the target class (i.e., base data) and optimize the perturbation to be added to each point by solving the bilevel problem in Eq.~(\ref{Eq:Bilevel}) for attack against GA based training. We use a small value of $\epsilon$ to ensure the perturbations added are imperceptible and the poison points have clean labels when inspected visually (See Fig.~\ref{fig:attack_egs} in the Appendix). The bilevel optimization is solved using the ApproxGrad algorithm (Alg.~\ref{alg:approxgrad} in Appendix~\ref{app:approxgrad}). The full attack algorithm for generating poison data against GA \cite{cohen2019certified} is shown in Alg.~\ref{alg:main}. Attack against other methods are generated similarly by replacing the lower-level objective ($\zeta$ in Alg.~\ref{alg:main}) with the appropriate loss function for MACER~\cite{zhai2020macer} and SmoothAdv~\cite{salman2019provably}. We evaluate the effect of poisoning, by training the models from scratch using GA, MACER and SmoothAdv on their respective poisoned sets and report ACR and approximate certified accuracy (points with certified $\ell_2$ radius greater than zero) on the clean test points from the target class. Previous works \cite{huang2020metapoison, shafahi2018poison} had shown the effectiveness of poisoning by lowering the accuracy on specific target points from the test set. Our attack is also effective, under a similar setting, at reducing the certified radius for target points (Appendix~\ref{app:partial_poisoning}).

\vspace{-0.1cm}
\subsection{Analysis of poisoning with linear classifiers}
To gain a deeper insight into the effect of poisoning, we analyze the
analytical solution of our bilevel problem for the case of linear classifiers trained with GA.
Suppose we have a one-dimensional two-class problem and the attacker's goal is to poison the distribution of the \emph{negative} class $P^{-}$ so that the ACR ($\tilde{R}$) of the poisoned model on the test points of the \emph{negative} class is reduced.
Let $\epsilon$ be the the maximum permissible perturbation that can be added by the attacker to the points of the class $P^{-}$.
We do not assume any specific distributions for $P^{+}$ and $P^{-}$ here, but only that $\sum_i x_i^{-}<\sum_i x_i^{+}$ without loss of generality. Here $x_i^{+}$ and $x_i^{-}$ refer to the training points of the positive and the negative class, respectively.
A linear classifier in one-dimension is either $f(x)=1\;\mathrm{iff}\;x \geq t$ or $f(x)=-1\;\mathrm{iff}\;x \leq t$ parameterized by the threshold $t$.
For linear classifiers,
the smoothed classifier $g$ is the same as the unsmoothed classifier $f$ and the certified radius for a point is the distance to the decision boundary \cite{cohen2019certified}.
To make the problem analytically tractable, we use the squared-loss at the lower-level i.e., $f(x) = wx + b$ and $l(x,y;f)=(f(x) - y)^2$.
The bilevel problem for poisoning is as follows
\begin{equation}
    \begin{split}
        &\min_{u}\;\; \mathbb{E}_{{P}_{-}}[\max(\mathrm{sign}(w^\ast)(-b^\ast/w^\ast-x),0)]\\
        &\mathrm{s.t.}\;\; -\epsilon \leq u_i - x_i^{-} \leq \epsilon, \;\; \mathrm{for \;\; i = 1, ..., n}\\

        w^\ast,&b^\ast = \arg\min_{w, b}\; \frac{1}{2n}\big[\sum_{i=1}^{n}l(x_i^{+},1) + \sum_{i=1}^{n}l(u_i,-1)\big].
    \end{split}
    \label{eq:bilevel_linear}
\end{equation}

\begin{theorem}
\label{thm:linear}
If the perturbation is large enough, i.e., $\epsilon \geq \frac{\sum_i x_i^{+} - \sum_i x_i^{-}}{n}$ then there are two locally optimal solutions to (\ref{eq:bilevel_linear}) which are $u_i = x_i^{-} - \epsilon$ (Case 1) and $u_i = x_i^{-} + \epsilon$ (Case 2) for $i=1,...,n$.
Otherwise, there is a unique globally optimal solution $u_i = x_i^{-} - \epsilon$ (Case 1) for $i=1,...,n$.
\end{theorem}
Thus, optimal poisoning is achieved by shifting points of the $P^{-}$ class either towards left or right by the maximum amount $\epsilon$ (Fig.~\ref{fig:linear} and Appendix~\ref{app:isotropic_gaussian}). Moreover, the effect of poisoning an $\alpha$ fraction of points from the $P^{-}$ class with maximum permissible perturbation $\Tilde{\epsilon}$ is same as that of poisoning all points of $P^{-}$ class with $\epsilon = \alpha \Tilde{\epsilon}$ (Corollary~\ref{cor:partial_poisoning} in Appendix~\ref{app:proofs}).
Although a direct analysis is intractable for non-linear cases, we empirically observed that our attack moved the decision boundary of neural networks closer to the points of the target class as measured by the mean distance of points to the decision boundary of the smoothed classifier (Sec.~\ref{sec:exp_emp_robustness}).

\vspace{-0.1cm}
\section{Experiments}\label{sec:experiments}
In this section we present the results of our PACD\footnote{The code is available at \url{https://github.com/akshaymehra24/poisoning_certified_defenses}} attack on poisoning deep neural networks trained using methods that make the model certifiably robust to test-time attacks. All the results presented here are averaged over models trained with five random initialization.
We report the average certified radius (ACR) as the average of the certified radius obtained from the RS based certification procedure of \cite{cohen2019certified} for correctly classified points. Certified radius is zero for misclassified and abstained points.
The approximate certified accuracy (ACA) is the fraction of points correctly classified by the smoothed classifier ($\ell_2$ radius greater than zero). All results are reported over 500 randomly sampled images from the target classes.
We use the same value of $\sigma$ for smoothing during attack, retraining and evaluation. We compare our results to watermarking \cite{shafahi2018poison}
which has been used previously for clean label attacks (opacity 0.1 followed by clipping to make $\ell_{\infty}$ distortion equal to $\epsilon$),
and show that poison data generated using the bilevel optimization is significantly better at reducing the average certified radius.

\begin{table}[tb]
  \caption{Decrease in certified radius and certified accuracy of models trained with Gaussian augmentation \cite{cohen2019certified} on poison data compared to those of models trained on clean and watermarked data.

  }
  \label{Table:cohen_attack}
  \centering
  \small
  \resizebox{0.95\columnwidth}{!}{
    \begin{tabular}{c|c|c|cc}
    \toprule
    & \multirow{2}{*}{$\sigma$} & \multirow{2}{*}{Data} &  \multicolumn{2}{c}{\makecell{Certified robustness of target class}}\\
    & & & ACR & ACA(\%) \\

    \midrule
    \multirow{9}{*}{\STAB{\rotatebox[origin=c]{90}{MNIST}}} &
    \multirow{3}{*}{0.25} & Clean   & 0.896$\pm$0.01 &	98.92$\pm$0.32 \\
    & & Watermarked & 0.908$\pm$0.01 & 99.24$\pm$0.29 \\
    & & Poisoned & {\bf0.325}$\pm$0.10 &	{\bf71.96}$\pm$8.28 \\
    \cmidrule{2-5}
    &\multirow{3}{*}{0.5} & Clean & 1.481$\pm$0.02 &	99.16$\pm$0.34\\
    &  & Watermarked & 1.514$\pm$0.06 &	99.12$\pm$0.47\\
    & & Poisoned  & {\bf0.733}$\pm$0.10 &	{\bf90.68}$\pm$3.37 \\
    \cmidrule{2-5}
    &\multirow{3}{*}{0.75} & Clean & 1.549$\pm$0.11 & 98.48$\pm$0.35\\
    & & Watermarked & 1.566$\pm$0.06 &	98.36$\pm$0.39\\
    &  & Poisoned  & {\bf0.698}$\pm$0.13 &	{\bf84.92}$\pm$5.14 \\
    \midrule
    \midrule
    \multirow{6}{*}{\STAB{\rotatebox[origin=c]{90}{CIFAR10}}} &
    \multirow{3}{*}{0.25} & Clean   & 0.521$\pm$0.05 &	85.76$\pm$3.31 \\
    & & Watermarked & 0.470$\pm$0.01 &	83.22$\pm$1.41 \\
    & & Poisoned & {\bf0.059}$\pm$0.02 &	{\bf26.84}$\pm$6.04 \\
    \cmidrule{2-5}
    & \multirow{3}{*}{0.5} & Clean & 0.634$\pm$0.04 &	75.04$\pm$1.65\\
    & & Watermarked & 0.611$\pm$0.18 &	74.01$\pm$9.22\\
    & & Poisoned  & {\bf0.221}$\pm$0.04 &	{\bf42.28}$\pm$6.01 \\

    \bottomrule
    \end{tabular}
    }
\end{table}

We use our attack to poison MNIST and CIFAR10 dataset and use ApproxGrad to solve the bilevel optimization. The time complexity for ApproxGrad is $O(VT)$ where $V$ are the number of parameters in the machine learning model and $T$ is the number of lower-level updates. For datasets like Imagenet where the optimization must be performed over a very large number of batches, obtaining the solution to bilevel problems becomes computationally hard. Due to this bottleneck we leave the problem of poisoning Imagenet for future work. For the experiments with MNIST we randomly selected digit 8 and for CIFAR10 the class ``Ship'' as the target class for the attacker.
The attack results for other target classes are similar and are presented in the Appendix~\ref{app:additional_experiments}.
To ensure that the attack points satisfy the clean label constraint, the maximum permissible $\ell_{\infty}$ distortion is bounded by $\epsilon = 0.1$ for MNIST and $\epsilon = 0.03$ for CIFAR10 which is similar to the value used to generate imperceptible adversarial examples in previous works \cite{madry2017towards,goodfellow2014explaining}. We used  convolutional neural networks for our experiments on MNIST and Resnet-20 model for our experiments with CIFAR10. Model architectures, hyperparameters, generated attack examples (Fig.~\ref{fig:attack_egs} in Appendix), and additional results on transferability of our poisoned samples to models with different architectures
are presented in Appendix \ref{app:additional_experiments}.
Since models trained with standard training do not achieve high certified radius \cite{cohen2019certified}, we considered poisoning models trained with methods that improve the certified robustness guarantees to test time attacks.
For comparison, ACR on the target class ``Ship'' with Resnet-20 trained with standard training on clean CIFAR10 dataset is close to zero whereas for the same model trained with GA ($\sigma = 0.25$) ACR is close to 0.5.
Finally, we show that our attack can withstand the use of weight regularization, which has been shown to be effective at mitigating the effect of poisoning attacks \cite{carnerero2020regularisation}. The results of this experiment are present in Appendix~\ref{app:weight_reg}.

\begin{table}[tb]
  \caption{Decrease in certified radius and certified accuracy of models trained with MACER \cite{zhai2020macer} on poison data compared to those of models trained on clean and watermarked data.
  }
  \label{Table:macer_attack}
  \centering
  \small
  \resizebox{0.95\columnwidth}{!}{
    \begin{tabular}{c|c|c|cc}
    \toprule
    &\multirow{2}{*}{$\sigma$} & \multirow{2}{*}{Data} &
    \multicolumn{2}{c}{\makecell{Certified robustness of target class}}\\
    &&
    & ACR & ACA(\%) \\
    \midrule
    \multirow{9}{*}{\STAB{\rotatebox[origin=c]{90}{MNIST}}} &
    \multirow{3}{*}{0.25} & Clean   & 0.915$\pm$0.01	& 99.64$\pm$0.21\\
    & & Watermarked & 0.894$\pm$0.01 &	98.84$\pm$0.53\\
    & & Poisoned & {\bf0.431}$\pm$0.13 &	{\bf79.81}$\pm$9.26 \\
    \cmidrule{2-5}
    &\multirow{3}{*}{0.5} & Clean & 1.484$\pm$0.11 &	98.56$\pm$0.41\\
    & & Watermarked & 1.475$\pm$0.08 &	98.68$\pm$0.39\\
    & & Poisoned  & {\bf0.685}$\pm$0.16 &	{\bf84.36}$\pm$6.17 \\
    \cmidrule{2-5}
    &\multirow{3}{*}{0.75} & Clean & 1.353$\pm$0.13 &	93.81$\pm$2.08\\
    & & Watermarked & 1.415$\pm$0.11 &	94.52$\pm$1.58\\
    & & Poisoned  & {\bf1.008}$\pm$0.19 &	{\bf88.41}$\pm$4.64 \\

     \midrule
     \midrule
     \multirow{6}{*}{\STAB{\rotatebox[origin=c]{90}{CIFAR10}}} &
     \multirow{3}{*}{0.25} & Clean   & 0.593$\pm$0.05 &	83.84$\pm$2.26 \\
    & & Watermarked & 0.486$\pm$0.04 &	77.01$\pm$0.21 \\
    & & Poisoned & {\bf0.379}$\pm$0.11 &	{\bf72.41}$\pm$9.79\\
    \cmidrule{2-5}
    & \multirow{3}{*}{0.5} & Clean & 0.759$\pm$0.11 &	72.92$\pm$5.06\\
    & & Watermarked & 0.811$\pm$0.10	& 75.66$\pm$2.99\\
    & & Poisoned  & {\bf0.521}$\pm$0.11 &	{\bf65.24}$\pm$6.55 \\
    \bottomrule
    \end{tabular}
    }
\end{table}

\vspace{-0.1cm}
\subsection{Poisoning Gaussian data augmentation \cite{cohen2019certified}}
Here we show the effectiveness of our attack at compromise the certified robustness guarantees obtained with RS on a model trained using the GA. The results of the attack, present in Table~\ref{Table:cohen_attack}, show a significant decrease in the ACR and the certified accuracy of the target class of the model trained on poisoned data compared to the model trained on clean and watermarked data. Since the certified radius and certified accuracy are correlated, our poisoning attack which targets the reduction of certified radius (upper-level problem in Eq.~(\ref{Eq:Bilevel})) also causes a decrease in the certified accuracy. Significant degradation in average certified radius from 0.52 to 0.06 on CIFAR10 with imperceptibly distorted poison data shows the extreme vulnerability of GA to poisoning.

\vspace{-0.1cm}
\subsection{Poisoning MACER \cite{zhai2020macer}}
Here we use the bilevel formulation in Eq.~(\ref{Eq:Bilevel}) with $\mathcal{L}_\mathrm{macer}$ loss in the lower-level and generate poison data to reduce the certification guarantees of models trained with MACER. The poison data is generated with $k=2$, where $k$ are the number of noisy images used per training point to ease the bilevel optimization. However, during retraining $k=16$ is used, which is similar to the one used in the original work \cite{zhai2020macer}.
The ACR obtained using MACER is higher than that achievable using Gaussian augmentation based training consistent with \cite{zhai2020macer}. However, our data poisoning attack is still able to reduce the average certified radius of the method by more than 30\% (Table~\ref{Table:macer_attack}) even though the attack is evaluated against a much stronger defense ($k=16$ for retraining compared to $k=2$ for poisoning) than what the poison data was optimized against. This shows that the use of a larger number of noisy samples ($k$) cannot eliminate the effect of the attack, emphasising the importance of the threat posed by data poisoning.

\begin{table}[tb]
  \caption
  Decrease in certified radius and certified accuracy of models trained with SmoothAdv \cite{salman2019provably} on poison data compared to those of models trained on clean and watermarked data.

  }
  \label{Table:smoothadv_attack}
  \centering
  \small
  \resizebox{0.95\columnwidth}{!}{
    \begin{tabular}{c|c|c|cc}
    \toprule
    &\multirow{2}{*}{$\sigma$} & \multirow{2}{*}{Data} &
    \multicolumn{2}{c}{\makecell{Certified robustness of target class}}\\
    &&
    & ACR & ACA(\%) \\
    \midrule
    \multirow{9}{*}{\STAB{\rotatebox[origin=c]{90}{MNIST}}} &
    \multirow{3}{*}{0.25} & Clean   & 0.896$\pm$0.01 &	99.16$\pm$0.45 \\
    & & Watermarked & 0.906$\pm$0.01 &	99.28$\pm$0.16 \\
    & & Poisoned & {\bf0.672}$\pm$0.04 &	{\bf93.21}$\pm$1.92 \\
    \cmidrule{2-5}
   & \multirow{3}{*}{0.5} & Clean & 1.408$\pm$0.05 &	99.21$\pm$0.25\\
    & & Watermarked & 1.401$\pm$0.02 &	98.01$\pm$0.18\\
    & & Poisoned  & {\bf1.037}$\pm$0.06 &	{\bf93.81}$\pm$1.31 \\
   \cmidrule{2-5}
   & \multirow{3}{*}{0.75} & Clean & 1.262$\pm$0.05 &	95.68$\pm$0.47\\
    & & Watermarked & 1.433$\pm$0.03 &	97.21$\pm$0.13\\
    & & Poisoned  & {\bf0.924}$\pm$0.06 &	{\bf88.88}$\pm$0.18 \\
    \midrule
     \midrule
     \multirow{6}{*}{\STAB{\rotatebox[origin=c]{90}{CIFAR10}}} &
    \multirow{3}{*}{0.25} & Clean   & 0.504$\pm$0.02	& 78.76$\pm$0.81 \\
    & & Watermarked & 0.441$\pm$0.02 & 70.16$\pm$2.12 \\
    & & Poisoned & {\bf0.271}$\pm$0.02 &	{\bf55.78}$\pm$0.96 \\
    \cmidrule{2-5}
    &\multirow{3}{*}{0.5} & Clean & 0.479$\pm$0.07 &	65.84$\pm$4.81\\
    & & Watermarked & 0.473$\pm$0.02 &	62.51$\pm$2.12\\
   &  & Poisoned  & {\bf0.277}$\pm$0.02 &	{\bf49.11}$\pm$3.19 \\

    \bottomrule
    \end{tabular}
    }
\end{table}

\begin{figure}[tb]
  \centering
  \includegraphics[width=0.6\columnwidth]{images/teaser_c.pdf}
  \includegraphics[width=0.6\columnwidth]{images/attack_egs_c.pdf}
  \caption
  (Upper) ACR degrades more if larger perturbations are permitted to create poison data. But larger perturbation makes the poison points visibly distorted making them easier to detect with inspection (Lower).

  Poison data are generated with $\epsilon \in \{0,0.1,0.2,0.3\}$. We have used $\epsilon = 0.1$ for our attacks.}
  \label{fig:acr_vs_epsilon}
\end{figure}

\begin{figure*}[tb]
  \centering{
  \subfigure[Average certified radius of digit 8 in MNIST]{\includegraphics[width=0.775\columnwidth]{images/acr_mnist_c.pdf}}
  \hspace{0.15in}
  \subfigure[Approximate certified accuracy of digit 8 in MNIST]{\includegraphics[width=0.775\columnwidth]{images/aca_mnist_c.pdf}}
  \subfigure[Average certified radius of ``Ship'' in CIFAR10]{\includegraphics[width=0.775\columnwidth]{images/acr_cifar10_c.pdf}}
  \hspace{0.15in}
  \subfigure[Approximate certified accuracy of ``Ship'' in CIFAR10]{\includegraphics[width=0.775\columnwidth]{images/aca_cifar10_c.pdf}}
  \includegraphics[width=0.9\textwidth]{images/legend_c.pdf}
  }
  \caption{Successful transferability of our poisoned data when victim uses a training procedure different than the one used by the attacker to optimize the poison data. $\sigma = 0.5$ and $\sigma = 0.25$ are used for smoothing during training and evaluation for MNIST and CIFAR10.

  }
  \label{fig:transfer}
\end{figure*}

\begin{table}[tb]
  \caption{Decrease in the mean $\ell_2$-distortion needed to generate adversarial examples using PGD attack against the smooth classifier. This shows that the decision boundary of the smooth classifier is closer to the clean test points of the target class after poisoning.
  }
  \label{Table:empirical_robustness}
  \centering
  \small
  \resizebox{0.75\columnwidth}{!}{
    \begin{tabular}{c|c|c|c}
    \toprule
    & $\sigma$  & Clean data & Poisoned data\\
    \midrule
    \multirow{3}{*}{MNIST} & 0.25 & 3.271$\pm$0.10 & {\bf1.339}$\pm$0.16 \\

   & 0.5 & 3.637$\pm$0.15 & {\bf2.170}$\pm$0.09 \\

   & 0.75 & 3.961$\pm$0.18 & {\bf2.213}$\pm$0.31 \\
     \midrule
     \multirow{2}{*}{CIFAR10} &0.25 & 1.754$\pm$0.17 & {\bf0.132}$\pm$0.04 \\

    &0.5 & 1.996$\pm$0.09 & {\bf0.367}$\pm$0.06 \\
    \bottomrule
    \end{tabular}
    }
\end{table}

\subsection{Poisoning SmoothAdv \cite{salman2019provably}}
Here we present the results of our attack on models trained with SmoothAdv. To yield model with high certified robustness this training method requires the model parameters to be optimized using adversarial training of the smoothed classifier. We used 2 step PGD attack to obtain adversarial example of each point in the batch. We used a single noisy instance of the adversarial example while doing adversarial training. Although, using larger $k$ makes the certified robustness guarantees better, we used $k=1$ to save the computational time required for adversarial training. For bilevel training, we followed the similar procedure to generate adversarial examples for clean and poison data. The adversarial examples are then used as the data for the lower-level problem of Eq.~(\ref{Eq:Bilevel}) to do GA training for optimizing the network parameters. The batch of adversarial examples are recomputed against the updated model after each step of bilevel training. Note that this is an approximation to the actual solution of the minimax problem that has to be solved in the lower-level for generating poison data against SmoothAdv. However, the effectiveness of the attack (results in Table~\ref{Table:smoothadv_attack}) suggests that our approximation works well in practice and certified robustness guarantees achieved from SmoothAdv can be degraded by poisoning.

\subsection{Effect of the imperceptibility constraint}
Here we evaluate the effect of using different values of the perturbation strength $\epsilon$ which controls the maximum permissible distortion in Eq.~(\ref{Eq:Bilevel}). We use $\sigma = 0.25$ for smoothing and GA based training to generate and evaluate the attack. The results are summarized in Fig.~\ref{fig:acr_vs_epsilon}, which show that the ACR of the target class decreases as $\epsilon$ increases rendering certification guarantees useless. This is expected since larger $\epsilon$ creates a larger distribution shift among the target class data in the training and the test sets. However, larger permissible distortion to the data make the attack easier to detect by inspection. This is not be desirable from an attacker's perspective who wants to evade detection.

\subsection{Transferability of poisoned data}
Here we report the performance of the models trained on the poison data using different training procedures than the one assumed by the attacker for crafting poison data. We used $k=1$ and 2 steps of PGD attack to generate adversarial examples for SmoothAdv and $k=16$ for MACER during retraining.
The poison data generated against MACER was optimized using $k=2$.
The results are summarized in Fig.~\ref{fig:transfer}, which show that poisoned data optimized against any robust training procedure causes significant reduction in the certified robustness of models trained with a different training methods. Interestingly, poisoned data optimized against GA is extremely effective against other methods, considering the fact that it is the simplest of the three methods. The successful transferability of the poisoned data
across different training methods shows how brittle these methods can be when faced with a poisoned dataset.
We observe a similar success in transferability of the poison data to models with different architectures (Appendix~\ref{app:transfer_architecture}).

\if0
\begin{table*}
  \caption{Transfer-ability of the attack points when victim uses a different training procedure than used by the attacker to generate poison data for MNIST with digit 8 being the target class. $\sigma = 0.5$ is used for smoothing during training and evaluation. Certified robustness guarantees of each training method on clean data are present in the last row for reference.
  }
  \label{Table:mnist_transferability}
  \centering
  \small
  \resizebox{0.85\textwidth}{!}{
    \begin{tabular}{c|cc|cc|cc}
    \toprule
    \multirow{2}{*}{\makecell{Training method used for\\ generating poison data}} & \multicolumn{6}{c}{\makecell{Training method used for evaluation}}\\
    &\multicolumn{2}{c|}{\makecell{Gaussian Aug}} & \multicolumn{2}{c|}{\makecell{MACER \cite{zhai2020macer}}} & \multicolumn{2}{c}{\makecell{SmoothAdv \cite{salman2019provably}}}\\
    \midrule
    & ACR & ACA(\%) & ACR & ACA(\%) & ACR & ACA(\%)  \\
    \midrule
    Gaussian Aug & 0.733$\pm$0.10 &	90.68$\pm$0.03 &	0.741$\pm$0.09 &	87.88$\pm$0.04 &	1.116$\pm$0.12 &	96.91$\pm$0.01\\
    MACER \cite{zhai2020macer} & 0.881$\pm$0.03 &	93.10$\pm$0.01 &	0.685$\pm$0.16 &	84.45$\pm$0.06 &	1.036$\pm$0.05 &	94.65$\pm$0.01\\
    SmoothAdv \cite{salman2019provably} & 0.733$\pm$0.09 &	88.72$\pm$0.04 &	0.8732$\pm$0.23 &	88.68$\pm$0.09 &	1.037$\pm$0.06 &	93.81$\pm$0.01\\
    \midrule
    Clean data & 1.481$\pm$0.02 &	99.16$\pm$0.01&	1.484$\pm$0.11 &	98.56$\pm$0.01 &	1.408$\pm$0.05 &	99.21$\pm$0.01\\

    \bottomrule
    \end{tabular}
    }
\end{table*}
\fi

\if0
\begin{table*}
  \caption{Transferability of the attack points when victim uses a different training procedure than used by the attacker to generate poison data for CIFAR10 with class ``Ship'' being the target class. $\sigma = 0.25$ is used for smoothing during training and evaluation. Certified robustness guarantees of each training method on clean data are present in the last row for reference.
  }
  \label{Table:cifar10_transferability}
  \centering
  \small
  \resizebox{0.85\textwidth}{!}{
    \begin{tabular}{c|cc|cc|cc}
    \toprule
    \multirow{2}{*}{\makecell{Training method used for\\ generating poison data}} & \multicolumn{6}{c}{\makecell{Training method used for evaluation}}\\
    &\multicolumn{2}{c|}{\makecell{Gaussian Aug}} & \multicolumn{2}{c|}{\makecell{MACER \cite{zhai2020macer}}} & \multicolumn{2}{c}{\makecell{SmoothAdv \cite{salman2019provably}}}\\
    \midrule
    & ACR & ACA(\%) & ACR & ACA(\%) & ACR & ACA(\%)  \\
    \midrule
    Gaussian Aug & 0.059$\pm$0.01 &	26.84$\pm$0.06&	0.134$\pm$0.04&	41.08$\pm$0.08	&0.238$\pm$0.03&	55.01$\pm$0.05\\
    MACER \cite{zhai2020macer}& 0.235$\pm$0.02&	61.01$\pm$0.04&	0.379$\pm$0.10&	72.41$\pm$0.10&	0.3205$\pm$0.01 & 59.01$\pm$0.01\\
    SmoothAdv \cite{salman2019provably} & & & & &\\
    \midrule
    Clean data & 0.521$\pm$0.05 &	85.76$\pm$0.03 &	0.593$\pm$0.05 &	83.84$\pm$0.03 & 0.504$\pm$0.02	& 78.76$\pm$0.01 \\

    \bottomrule
    \end{tabular}
    }
\end{table*}
\fi

\vspace{-0.2cm}
\subsection{Empirical robustness of poisoned classifiers}\label{sec:exp_emp_robustness}
\vspace{-0.1cm}
Finally, we report the empirical robustness of the smoothed classifier where the base classifier is trained on clean and poisoned data using GA.
The poisoned data is generated against GA training in the lower-level as in Eq.~(\ref{Eq:Bilevel}). We report the mean $\ell_2$-distortion required to generate an adversarial example using the PGD attack \cite{salman2019provably} against the smoothed classifier using 200 and 100 randomly sampled test points of the target class from MNIST and CIFAR10, respectively, in Table~\ref{Table:empirical_robustness}.
We observe that our poisoning leads to a decrease in the empirical robustness of the smoothed classifier on clean test data.
This backs up our hypothesis
that the decision boundary of the smooth classifier must be changed to reduce the certified radius in nonlinear classifiers, similar to linear classifiers (Fig.~\ref{fig:linear}).

\if0
\begin{figure}[tb]
  \centering{
  \subfigure[]{\includegraphics[width=0.9\columnwidth]{images/acr_cifar10_c.pdf}}
  \subfigure[]{\includegraphics[width=0.9\columnwidth]{images/aca_cifar10_c.pdf}}
  }
  \caption{Transferability of the attack points when victim uses a different training procedure than used by the attacker to generate poison data for CIFAR10 with class ``Ship'' being the target class. $\sigma = 0.25$ is used for smoothing during training and evaluation.}
  \label{fig:transfer_cifar10}
\end{figure}
\fi

\vspace{-0.1cm}
\section{Conclusion}
\vspace{-0.15cm}
Certified robustness has emerged as a gold standard to gauge with certainty the susceptibility of machine learning models to test-time attacks.
In this work, we showed that these guarantees can be rendered ineffective by our bilevel optimization based data poisoning attack that adds imperceptible perturbations to the points of the target class.
Unlike previous data poisoning attacks, our attack can reduce the ACR of an entire target class and is even effective against models trained using training methods that have been shown to improve certified robustness. Our results suggests that data quality is a crucial factor in achieving high certified robustness guarantees but is overlooked by current approaches.

\vspace{-0.15cm}
\section{Acknowledgments}
\vspace{-0.15cm}
This work was supported by the NSF EPSCoR-Louisiana Materials Design Alliance (LAMDA) program \#OIA-1946231 and by LLNL Laboratory Directed Research and Development project 20-ER-014 (LLNL-CONF-817233).
This work was performed under the auspices of the U.S. Department of Energy by the Lawrence Livermore National Laboratory under Contract No. DE-AC52-07NA27344, Lawrence Livermore National Security, LLC.\footnote{The views and opinions of the authors do not necessarily reflect those of the U.S. government or Lawrence Livermore National Security, LLC neither of whom nor any of their employees make any endorsements, express or implied warranties or representations or assume any legal liability or responsibility for the accuracy, completeness, or usefulness of the information contained herein.}

\clearpage

{\small
\bibliographystyle{ieee_fullname}

\section{Introduction}
Data poisoning \cite{biggio2012poisoning,jagielski2018manipulating,shafahi2018poison,steinhardt2017certified,zhu2019transferable}
is a training-time attack where the attacker is assumed to have access to the training data on which the victim will train the model.
The attacker can modify the training data
in a manner that the model trained on this poisoned data performs as the attacker desires.
The data hungry nature of modern machine learning methods make them vulnerable to poisoning attacks. Attackers can place the poisoned data online and wait for it to be scraped by victims trying to increase the size for their training sets.
Another easy target for data poisoning is data collection by crowd sourcing where malicious users can corrupt the data they contribute. In most cases, an attacker can modify only certain parts of the training data such as change the features or labels for a specific class or modify a small subset of the data from all classes.
In this work, we assume the attacker wants to affect the performance of the victim's models on a target class and modifies only the features of the points belonging to that class (without affecting the labels). To evade detection, the attacker is constrained to only add imperceptibly small perturbations to the points of the target class.
Many previous works \cite{munoz2017towards,shafahi2018poison,huang2020metapoison,koh2017understanding,zhu2019transferable,chen2017targeted,ji2017backdoor,turner2018clean} have shown the effectiveness of poisoning in affecting the accuracy of models trained on poisoned data compared to the accuracy achievable by training with clean data. In most works, the victim is assumed to use standard training by minimizing the empirical loss on the poisoned data to train the models and thus the attack is optimized to hurt the accuracy of standard training.
However, recent research on test-time evasion attacks \cite{carlini2017adversarial,athalye2018obfuscated,uesato2018adversarial,bulusu2020anomalous} suggests that models trained with standard training are not robust to adversarial examples, making the assumption of victim relying on standard training to train the models for deployment questionable.

\begin{figure*}[tb]
  \centering{\includegraphics[width=0.99\textwidth]{images/overview_c.pdf}}
  \caption{Overview of our poisoning against certified defenses (PACD) attack which generates poisoned data to reduce the certified robustness of the victim's model trained with methods such as Gaussian data augmentation(GA)\cite{cohen2019certified}, SmoothAdv\cite{salman2019provably} and MACER\cite{zhai2020macer} on a target class.

  }
  \label{fig:overview}
\end{figure*}

Thus, in a realistic scenario, where the aim of the victim is to deploy the model, it's better to assume that the victim will rely on training procedures that yield classifiers which are provably robust to test-time attacks.
Several recent works have proposed methods for training certifiably robust models whose predictions are guaranteed to be constant in a neighbourhood of a point. However, many of these methods \cite{raghunathan2018semidefinite,gowal2018effectiveness,huang2019achieving,xu2020automatic} do not scale to deep neural networks or large datasets, due to their high complexity. Moreover, the effect of training data quality on the performance of these certified defenses at test time remains largely unexplored.
Recently, randomized smoothing (RS) based certification methods \cite{lecuyer2019certified,li2019certified,cohen2019certified} were shown to be scalable to deep neural networks and high dimensional datasets enabling researchers to propose training procedures \cite{salman2019provably,zhai2020macer} that lead to models with high certified robustness.
Thus, we assume that a victim will rely on RS based certification methods to measure the certified robustness and use RS based training procedures to train the models.
The fact that a victim can train with a method that improves certified adversarial robustness is an immediate challenge for current poisoning attacks which optimize the poison data to affect the accuracy of models trained with standard training.
Table~\ref{Table:difficulty_of_poisoning} shows that poisons optimized against standard training can significantly reduce the accuracy of the victim's model (left to right) when the victim also uses standard training (1st and 5th row). However, this poison data is rendered ineffective when the victim uses a certifiably robust training method such as \cite{cohen2019certified,salman2019provably,zhai2020macer}.

\emph{Are certified defenses robust to data poisoning?}
We study this question and demonstrate that data poisoning is a serious concern even for certified defenses.
\begin{table}
  \caption{Failure of traditional data poisoning attacks optimized against standard training in affecting the test accuracy (of target class) of models trained with certifiably robust training procedures. Details of the experiment are present in Appendix~\ref{app:standard_acc}. Certifiably robust training methods \cite{cohen2019certified,salman2019provably,zhai2020macer} are trained with $\sigma$ = 0.25 and accuracy of their base classifiers are reported.

  }
  \label{Table:difficulty_of_poisoning}
  \centering
  \small
  \resizebox{0.9\columnwidth}{!}{
    \begin{tabular}{c|c|c|c}
    \toprule
    &\multirow{1}{*}{\makecell{Training method }} & \multicolumn{1}{c|}{\makecell{Model trained \\ on clean data}} & \multicolumn{1}{c}{\makecell{Model trained \\ on  poison data}} \\
    \midrule
    \multirow{4}{*}{\STAB{\rotatebox[origin=c]{90}{MNIST}}} &
    Standard & 	99.28$\pm$0.01 & 60.08$\pm$12.6 \\
    &\makecell{GA\cite{cohen2019certified}} & 	98.99$\pm$0.14  & 98.31$\pm$1.65\\
    &SmoothAdv \cite{salman2019provably}&  99.18$\pm$0.23  & 99.31$\pm$0.29\\
    &MACER \cite{zhai2020macer}&  99.21$\pm$0.56  & 98.31$\pm$0.58\\
    \midrule
    \midrule
    \multirow{4}{*}{\STAB{\rotatebox[origin=c]{90}{CIFAR10}}} &
    Standard &  92.71$\pm$1.31  & 0.36$\pm$0.37 \\
    &\makecell{GA \cite{cohen2019certified}} &  88.84$\pm$2.39  & 88.38$\pm$2.13\\
    &SmoothAdv \cite{salman2019provably} & 79.48$\pm$2.69   &	74.95$\pm$3.45\\
    &MACER \cite{zhai2020macer}& 	87.12$\pm$1.17  &	88.54$\pm$4.52\\
    \bottomrule
    \end{tabular}
    }
\end{table}
We propose a novel data poisoning attack that can significantly compromise the certified robustness guarantees achievable from training with robust training procedures. We formulate the Poisoning Against Certified Defenses (PACD) attack as a constrained bilevel optimization problem and theoretically analyze its solution for the case when the victim uses linear classifiers. Our theoretical analysis and empirical results suggests that the decision boundary of the smoothed classifiers (used for RS) learned from
the poisoned data is significantly different from the one learned from clean data there by causing a reduction in certified radius.
Our bilevel optimization based attack formulation is general since it can generate poisoned data against a model trained with any certifiably robust training method (lower-level problem) and certified with any certification procedure (upper-level problem). Fig.~\ref{fig:overview} shows the overview of the proposed PACD attack.

Unlike previous poisoning attacks that aim to reduce the accuracy of the models on a small subset of data, our attack can reduce the certified radius of an entire target class.
The poison points generated by our attack have clean labels and imperceptible distortion making them difficult to detect.
The poison data remains effective when the victim trains the models from scratch or uses data augmentation or weight regularization during training. Moreover, the attack points generated against a certified defense are transferable to models trained with other RS based certified defenses and to models with different architectures.
This highlights the importance of training-data quality and curation for obtaining meaningful gains from certified defenses at test time, a factor not considered by current certified defense research.

Our main contributions are as follows
\begin{itemize}
    \item We study the problem of using data poisoning attacks to affect the robustness guarantees of classifiers trained using certified defense methods. To the best of our knowledge, this is the first clean label poisoning attack that significantly reduces the certified robustness guarantees of the models trained on the poisoned dataset.

    \item We propose a bilevel optimization based attack which can generate poison data against several robust training and certification methods. We specifically use the attack to highlight the vulnerability of randomized smoothing based certified defenses to data poisoning.

    \item We demonstrate the effectiveness of our attack in reducing the certifiable robustness obtained using randomized smoothing on models trained with state-of-the-art certified defenses \cite{cohen2019certified,salman2019provably,zhai2020macer}. Our attack reduces the ACR of the target class by more than 30\%.

\end{itemize}

\vspace{-0.3cm}
\section{Background and related work}
{\bf Randomized smoothing:}
The RS procedure \cite{cohen2019certified} uses a smoothed version of the original classifier $f:\mathbb{R}^d \xrightarrow{} \mathcal{Y}$ and certifies the adversarial robustness of the new classifier. The smoothed classifier, $g(x) = \arg \max_c \mathbb{P}_{\eta \sim \mathcal{N}(0, \sigma^2I)}(f(x+\eta)=c)$, assigns $x$ the class whose decision region $\{x' \in \mathbb{R}^d: f(x') = c\}$ has the largest measure under the distribution $\mathcal{N}(x, \sigma^2I)$, where $\sigma$ is used for smoothing. Suppose that while classifying a point $\mathcal{N}(x, \sigma^2I)$, the original classifier $f$ returns the class $c_A$ with probability $p_A = \mathbb{P}(f(x + \eta) = c_A)$, and the “runner-up” class $c_B$ is returned with probability $p_B = \max_{c \neq c_A} \mathbb{P}(f(x + \eta) = c)$, then the prediction of the point $x$ under the smoothed classifier $g$ is robust within the radius $r(g;\sigma) = \frac{\sigma}{2}(\Phi^{-1}(p_A) - \Phi^{-1}(p_B)),$ where $\Phi^{-1}$ is the inverse CDF of the standard Normal distribution. In practice, Monte Carlo sampling is used to estimate a lower bound on $p_A$ and an upper bound on $p_B$ as its difficult to estimate the actual values for $p_A$ and $p_B$.
Since standard training of the base classifier does not achieve high robustness guarantees, \cite{cohen2019certified} proposed to use GA based training in which the base classifier is trained on Gaussian noise corruptions of the clean data. Recent works \cite{zhai2020macer,salman2019provably} showed that the certified robustness guarantees of RS can be boosted by using different training procedures. In particular, \cite{salman2019provably} proposed to train the base classifier using adversarial training where the adversarial examples are generated against the smoothed classifier.
Although effective at increasing the certified radius, the method can be slow to train due to the requirement of generating adversarial examples against the smoothed classifier at every step. Another recent work \cite{zhai2020macer} proposed a different training procedure which is significantly faster to train and relies on directly maximizing the certified radius for achieving high robustness guarantees. Due to their effectiveness in improving the certified robustness guarantees of machine learning models, we craft poison data against these methods. A recent attack method \cite{ghiasi2020breaking} showed that it is possible to fool a robust classifier to mislabel an input and give an incorrect certificate using perturbation large in $\ell_p$ norm at test-time.
Our work is different since we focus on train-time attacks against certified defenses using imperceptibly small perturbations to the poison data.

{\bf Bilevel optimization:}
A bilevel optimization problem has the form $\min_{u \in \mathcal{U}} \xi(u,v^*)\;\mathrm{s.t.}\;v^* = \arg\min_{v\in \mathcal{V}(u)}\;\zeta(u,v)$, where the upper-level problem is a minimization problem with $v$ constrained to be the optimal solution to the lower-level problem (see \cite{bard2013practical}). Our data poisoning attack is a constrained bilevel optimization problem. Although general bilevel problems are difficult to solve, under some simplifying assumptions their solution can be obtained using gradient based methods. Several methods for solving bilevel problems in machine learning have been proposed previously \cite{domke2012generic,pedregosa2016hyperparameter,franceschi2017forward,maclaurin2015gradient,shaban2018truncated,mehra2019penalty} (See Appendix~\ref{app:approxgrad} for an overview). We use the method based on approximating the hypergradient by approximately solving a linear system (ApproxGrad Alg.~\ref{alg:approxgrad} in Appendix~\ref{app:approxgrad}) in this work.
Previous works \cite{mei2015using,munoz2017towards,mehra2019penalty,huang2020metapoison,carnerero2020regularisation} have shown the effectiveness of solving bilevel optimization problem for data poisoning to affect the accuracy of models trained with standard training. Our work on the other hand proposes a bilevel optimization based formulation to generate a data poisoning attack against RS based certified defenses and shows its effectiveness against state-of-the-art robust training methods.

\section{Poisoning against certified defenses}
Here we present the bilevel formulation of our PACD attack for generating poisoned data to compromise the certified robustness guarantees of the models trained using certified defenses. Specifically, we discuss how to generate poison data against GA \cite{cohen2019certified}, SmoothAdv \cite{salman2019provably} and MACER \cite{zhai2020macer} and affect the certified robustness guarantees obtained using RS.

\subsection{General attack formulation}
Let $\mathcal{D^\mathrm{clean}} = \{(x_i^\mathrm{clean}, y_i^\mathrm{clean})\}_{i=1}^{N_{\mathrm{clean}}}$
be the clean, unalterable portion of the training set. Let $u=\{u_1,...,u_n\}$ denote the attacker's poisoning data which is added to the clean data.
For clean-label attack, we require that each poison example $u_i$ has a limited perturbation, for example, $\|u_i - x_i^\mathrm{base}\| =\|\delta_i\| \leq \epsilon$ from the base data $x_i^\mathrm{base}$ and has the same label $y_i^\mathrm{base}$, for $i=1,...,n$. Thus $\mathcal{D^\mathrm{poison}} = \{(u_i, y_i^\mathrm{base})\}_{i=1}^{N_{\mathrm{poison}}}$.
The goal of the attacker is to find $u$ such that when the victim uses $\mathcal{D^\mathrm{clean}} \bigcup \mathcal{D^\mathrm{poison}}$ to train a classifier,
the certified robustness guarantees of the model on the target class ($\mathcal{D^\mathrm{val}} = \{(x_i^\mathrm{val},y_i^\mathrm{val})\}_{i=1}^{N_\mathrm{val}}$) are significantly diminished compared to a classifier trained on clean data.
The attack can be formulated as follows:
\begin{equation}
    \begin{split}
        &\min_{u \in \mathcal{U}}\;\; \mathcal{R}(\mathcal{D}^\mathrm{val}; \theta^\ast) \\

        \mathrm{s.t.}\;\; \theta^* = \arg&\min_{\theta}\; \mathcal{L}_\mathrm{robust}(\mathcal{D^\mathrm{clean}} \bigcup \mathcal{D^\mathrm{poison}}; \theta).
    \end{split}
    \label{eq:bilevel_simple}
\end{equation}
The upper-level cost $\mathcal{R}$ denotes a certified robustness metric such as the certified radius from RS.
The goal of the upper-level problem is to compromise the certified robustness guarantees of the model trained on validation data $\mathcal{D}^\mathrm{val}$.
The solution to the lower-level problem $\theta^\ast$ are the parameters of the machine learning model learnt from $\mathcal{D^\mathrm{clean}} \bigcup \mathcal{D^\mathrm{poison}}$ using a robust training method with loss function $\mathcal{L}_\mathrm{robust}$.
The fact that any training method that achieves high certified robustness to test-time attacks and any certification procedure can be incorporated into this formulation by changing the lower- and upper-level problems, respectively, makes the attack formulation broadly applicable.
Recent works \cite{cohen2019certified,salman2019provably,zhai2020macer} have shown RS based methods to be effective at certifying and producing robust classifiers.
The scalability of these methods to large datasets and deep models make them useful for real-world application.
Thus, we focus on using our poisoning attack against these methods.

\subsection{Poison randomized smoothing based defenses}
For an input at test time, RS produces a prediction from the smoothed classifier $g$ and a radius in which this prediction remains constant.
Since the certified radius of a ``hard'' smooth classifier $g$ is non-differentiable, it cannot be directly incorporated in the upper-level of the attack formulation Eq.~(\ref{eq:bilevel_simple}).
To overcome this challenge, we use the ``soft'' smooth classifier $\tilde{g}$ as an approximation. Similar technique has been used in \cite{salman2019provably, zhai2020macer}.
Let $z_{\theta}:X\xrightarrow{}\mathcal{P}(K)$ be a classifier whose last layer is softmax with parameters $\theta$ and $\sigma > 0$ is the noise used for smoothing, then soft smoothed classifier $\Tilde{g}_{\theta}$ of $z_{\theta}$ is
\(\Tilde{g}_{\theta}(x) = \arg \max_{c \in Y} \mathbb{E}_{\eta \sim \mathcal{N}(0,\sigma^2I)}[z^c_{\theta}(x + \eta)].\)
It was shown in \cite{zhai2020macer} that if the ground truth of an input $x$ is $y$ and $\Tilde{g}_{\theta}$ classifies $x$ correctly
then $\tilde{g}_{\theta}$ is provably robust at $x$, with the certified radius $\tilde{r}(\tilde{g}_{\theta}; x, y, \sigma) = \frac{\sigma}{2}[\Phi^{-1}(\mathbb{E}_{\eta}[z^y_{\theta}(x + \eta)]) - \Phi^{-1}(\max_{y' \neq y}\mathbb{E}_{\eta}[z^{y'}_{\theta}(x + \eta)])].$
Assuming $\tilde{r}(\tilde{g}_{\theta}; x, y, \sigma) = 0$ when $x$ is misclassified, the ACR is $\tilde{R}(\tilde{g}_{\theta}; \mathcal{D}, \sigma) = \frac{1}{|\mathcal{D}|}\sum_{(x,y) \in \mathcal{D}} \tilde{r}(\tilde{g}_{\theta}; x, y, \sigma).$
Since $\tilde{R}$ is differentiable we can use it in the upper-level of Eq.~(\ref{eq:bilevel_simple}). The lower-level problem can be any robust training procedure and we focus on using \cite{cohen2019certified,zhai2020macer,salman2019provably} in this work.

{\bf Poisoning against GA \cite{cohen2019certified}.}
We start by showing how to generate poison data against models trained with GA \cite{cohen2019certified}, which was shown to yield higher certified robustness compared to models trained with standard training. In this method the classifier $f_{\theta}$ is obtained by optimizing the loss function $\mathcal{L}_\mathrm{GaussAug}(\mathcal{D};\theta,\sigma) = \frac{1}{|\mathcal{D}|}\sum_{(x_i,y_i) \in \mathcal{D}} l_{ce}(x_i+\eta,y_i;\theta)$, where $l_{ce}$ is the cross entropy loss and $\eta\sim \mathcal{N}(0,\sigma^2 I)$. To control the perturbation added to the poison data we used $\ell_\infty$-norm here but other norms can also be used. The bilevel formulation to generate poison data to reduce the certified robustness guarantees obtained using RS for a classifier trained with GA is as follows.
\begin{equation}
    \begin{split}
        &\min_{u}\;\; \tilde{R}(\tilde{g}_{\theta^*}; \mathcal{D}^\mathrm{val}, \sigma) \\
        &\mathrm{s.t.}\;\; \|\delta_i\|_{\infty} \leq \epsilon,\;\;  i=1,...,n,\;\;\mathrm{and} \\
        \theta^* = \arg&\min_{\theta}\; \mathcal{L}_\mathrm{GaussAug}(\mathcal{D^\mathrm{clean}} \bigcup \mathcal{D^\mathrm{poison}}; \theta,\sigma).
    \end{split}
    \label{Eq:Bilevel}
\end{equation}

\begin{figure*}[tb]
  \centering{\includegraphics[width=0.99\textwidth]{images/poisoning_two_cases_cropped.pdf}}
  \caption{Analytical solutions of problem (\ref{eq:bilevel_linear}) with linear classifiers. The poison distribution $(P^{-}_\mathrm{poison})$ can change the decision boundary (broken line) and reduce the ACR of the clean distribution $(P^{-})$ in two ways (Cases 1 and 2). Perturbation is exaggerated for illustration.}
  \label{fig:linear}
\end{figure*}

\begin{algorithm
\caption{Poisoning GA based certified defense \cite{cohen2019certified}
}
\label{alg:main}
\textbf{Input}: $\mathcal{D}^\mathrm{clean}, \mathcal{D}^\mathrm{base}, \mathcal{D}^\mathrm{val}, \mathrm{perturbation \;strength}\; \epsilon, \\ \mathrm{noise \;level}\; \sigma, \mathrm{number\; of\; noise\; samples}\; k, \\ \mathrm{inverse\; temperature}\;\alpha, \mathrm{total\; epochs}\; P,\\  \mathrm{lower-level\; epochs}\; T_1, \mathrm{epochs\; for \;linear\; system}\;T_2$ \\
\textbf{Output}: $\mathcal{D}^\mathrm{poison}$
\begin{algorithmic}
\STATE{$\mathcal{D}^\mathrm{poison} := \mathcal{D}^\mathrm{base}$}
\FOR{$p=0,\;\cdots\;,P\textrm{-}1$}
    \STATE{Sample a mini-batch $(x^\mathrm{clean}, y^\mathrm{clean}) \;\sim\; \mathcal{D}^\mathrm{clean}$}
    \STATE{Sample a mini-batch of $n$ points $(x^\mathrm{val}, y^\mathrm{val}) \;\sim\; \mathcal{D}^\mathrm{val}$}
    \STATE{Sample a mini-batch $(x^\mathrm{poison}, y^\mathrm{poison}) \;\sim\;\mathcal{D}^\mathrm{poison}$}
    \STATE{Pick the base samples for poison data $(x^\mathrm{base}, y^\mathrm{base})$}
    \STATE{For each $x^\mathrm{val}_{i}$, sample $k$ i.i.d. Gaussian samples}
    \STATE{$x^\mathrm{val}_{i_1}, \cdots , x^\mathrm{val}_{i_n} \sim \mathcal{N}(x^\mathrm{val}_{i}, \sigma^2I)$}

    \STATE{Compute $\tilde{z}_{\theta}(x^\mathrm{val}_i) \xleftarrow{} \frac{1}{k} \sum^k_{j=1} \alpha z_{\theta}(x^\mathrm{val}_{i_j})$ for each $i$}
    \STATE{$\mathcal{G_{\theta}} := \{(x^\mathrm{val}_i, y^\mathrm{val}_i): y^\mathrm{val}_i = \arg \max_{c \in \mathcal{Y}}\; \tilde{z}^c_{\theta}(x^\mathrm{val}_i)\}$}
    \STATE{}
    \STATE{For each $(x_i, y_i) \in \mathcal{G_{\theta}}$, compute $\tilde{y}_i$}
    \STATE{$\tilde{y}_i \xleftarrow{} \arg \max_{c \in \mathcal{Y}\textbackslash\{y_i\}} \tilde{z}^c_{\theta}(x_i)$}
    \STATE{For each  $(x_i, y_i) \in \mathcal{G_{\theta}}$, compute $\tilde{r}(x_i, y_i)$}
    \STATE{$\tilde{r}(x_i, y_i) = \frac{\sigma}{2}(\Phi^{-1}(\tilde{z}^{y_i}_{\theta}(x_i)) - \Phi^{-1}(\tilde{z}^{\tilde{y}_i}_{\theta}(x_i)))$}
    \STATE{}
    \STATE{$\xi :=  \frac{1}{n}\sum_{(x_i, y_i) \in \mathcal{G_{\theta}}}\tilde{r}(x_i, y_i)$}
    \STATE{$\zeta :=  \mathcal{L}_\mathrm{GaussAug}((x^\mathrm{clean}, y^\mathrm{clean}) \bigcup (x^\mathrm{poison}, y^\mathrm{poison}), \sigma)$}
    \STATE{$(x^\mathrm{poison}, y^\mathrm{poison}):=$ApproxGrad$(\xi, \zeta, 1, T_1, T_2,\epsilon,x^{base})$}
    \STATE{Update $\mathcal{D}^\mathrm{poison}$ with $(x^\mathrm{poison}, y^\mathrm{poison})$}
\ENDFOR
\end{algorithmic}
\end{algorithm}

{\bf Poisoning against MACER \cite{zhai2020macer}.} Another recent work proposed a method for robust training by maximizing the certified radius (MACER). Their approach uses a loss function which is a combination of the classification loss and the robustness loss of the soft smoothed classifier $\tilde{g}_\theta$. In particular, the loss of the smoothed classifier on a point $(x,y)$ is given by $l_{macer}(\tilde{g}_\theta; x, y) = -\mathrm{log} \;\hat{z}^y_{\theta}(x) + \frac{\lambda \sigma}{2} \mathrm{max}\{\gamma - \tilde{\xi}_{\theta}(x, y), 0\}\cdot\mathbf{1}_{\tilde{g}_{\{\theta}(x)=y\}}$. where $\eta_1, ..., \eta_k$ are $k$ i.i.d. samples from $\mathcal{N}(0, \sigma^2\mathbf{I})$, $\hat{z}^y_{\theta}(x) = \frac{1}{k}\Sigma^k_{j=1} z^y_{\theta}(x + \eta_j)$ is the empirical expectation of $z_{\theta}(x + \eta)$, $\tilde{\xi}_{\theta}(x, y) = \Phi^{-1}(\hat{z}^y_{\theta}(x)) - \Phi^{-1}(\mathrm{max}_{y \neq y} \hat{z}^{y'}_{\theta}(x))$, $\gamma$ is the hinge factor, and $\lambda$ balances the accuracy and robustness trade-off. Using this we can define $\mathcal{L}_\mathrm{macer}(\mathcal{D};\theta,\sigma) = \frac{1}{|\mathcal{D}|}\sum_{(x_i,y_i) \in \mathcal{D}} l_{macer}(\tilde{g}_{\theta};x_i,y_i)$. To generate poison data that reduces the robustness guarantees of classifier trained with MACER we can use the loss $\mathcal{L}_\mathrm{macer}(\mathcal{D};\theta,\sigma)$ in the lower-level problem in Eq.~(\ref{Eq:Bilevel}).

{\bf Poisoning against SmoothAdv \cite{salman2019provably}.}  It was shown that the certified robustness guarantees obtained from RS can be improved by training the classifiers using adversarial training with adversarial examples generated against the smooth classifier. In particular the classifier trained with SmoothAdv optimizes the following objective for a point $(x,y)$.
$\min_{\theta}\max_{\|x' - x\|_2 \leq \alpha} -\mathrm{log} \frac{1}{k}\Sigma^k_{j=1} z^y_{\theta}(x' + \eta_j)$ where $\eta_1, ..., \eta_k$ are $k$ i.i.d. samples from $\mathcal{N}(0, \sigma^2\mathbf{I})$ and $\alpha$ is the permissible $\ell_2$ distortion to $x$. To generate poisoning data against SmoothAdv we must use this objective as the lower-level problem in Eq.~(\ref{Eq:Bilevel}). To make it easier for bilevel solvers to solve this problem we use an approximation to the mini-max problem. For doing that we first compute the adversarial example
$x' = \arg\max_{\|x' - x\|_2 \leq \alpha} -\mathrm{log} \frac{1}{k}\Sigma^k_{j=1} z^y_{\theta}(x' + \eta_j)$ using PGD attack on the points in $\mathcal{D^\mathrm{clean}} \bigcup \mathcal{D^\mathrm{poison}}$ and then use these examples as our new dataset to train the model parameters in the lower-level as in Eq.~(\ref{Eq:Bilevel}). Specifically, the lower-level problem in Eq.~(\ref{Eq:Bilevel}) becomes $\arg\min_{\theta}\; \mathcal{L}_\mathrm{GaussAug}(\mathcal{D}^\mathrm{clean}_{adv} \bigcup \mathcal{D}^\mathrm{poison}_{adv}; \theta,\sigma)$ where $\mathcal{D}_{adv}$ denotes the adversarial examples generated against $\tilde{g}_{\theta}$. We update $\mathcal{D}_{adv}$ in every step of the bilevel optimization.
\vspace{-0.1cm}
\subsection{Generation and evaluation of poisoning attack}
In this work, we focus on creating a poisoned set to compromise the certified adversarial robustness guarantees of all points in a target class. We initialize the poison data with clean data from the target class (i.e., base data) and optimize the perturbation to be added to each point by solving the bilevel problem in Eq.~(\ref{Eq:Bilevel}) for attack against GA based training. We use a small value of $\epsilon$ to ensure the perturbations added are imperceptible and the poison points have clean labels when inspected visually (See Fig.~\ref{fig:attack_egs} in the Appendix). The bilevel optimization is solved using the ApproxGrad algorithm (Alg.~\ref{alg:approxgrad} in Appendix~\ref{app:approxgrad}). The full attack algorithm for generating poison data against GA \cite{cohen2019certified} is shown in Alg.~\ref{alg:main}. Attack against other methods are generated similarly by replacing the lower-level objective ($\zeta$ in Alg.~\ref{alg:main}) with the appropriate loss function for MACER~\cite{zhai2020macer} and SmoothAdv~\cite{salman2019provably}. We evaluate the effect of poisoning, by training the models from scratch using GA, MACER and SmoothAdv on their respective poisoned sets and report ACR and approximate certified accuracy (points with certified $\ell_2$ radius greater than zero) on the clean test points from the target class. Previous works \cite{huang2020metapoison, shafahi2018poison} had shown the effectiveness of poisoning by lowering the accuracy on specific target points from the test set. Our attack is also effective, under a similar setting, at reducing the certified radius for target points (Appendix~\ref{app:partial_poisoning}).

\vspace{-0.1cm}
\subsection{Analysis of poisoning with linear classifiers}
To gain a deeper insight into the effect of poisoning, we analyze the
analytical solution of our bilevel problem for the case of linear classifiers trained with GA.
Suppose we have a one-dimensional two-class problem and the attacker's goal is to poison the distribution of the \emph{negative} class $P^{-}$ so that the ACR ($\tilde{R}$) of the poisoned model on the test points of the \emph{negative} class is reduced.
Let $\epsilon$ be the the maximum permissible perturbation that can be added by the attacker to the points of the class $P^{-}$.
We do not assume any specific distributions for $P^{+}$ and $P^{-}$ here, but only that $\sum_i x_i^{-}<\sum_i x_i^{+}$ without loss of generality. Here $x_i^{+}$ and $x_i^{-}$ refer to the training points of the positive and the negative class, respectively.
A linear classifier in one-dimension is either $f(x)=1\;\mathrm{iff}\;x \geq t$ or $f(x)=-1\;\mathrm{iff}\;x \leq t$ parameterized by the threshold $t$.
For linear classifiers,
the smoothed classifier $g$ is the same as the unsmoothed classifier $f$ and the certified radius for a point is the distance to the decision boundary \cite{cohen2019certified}.
To make the problem analytically tractable, we use the squared-loss at the lower-level i.e., $f(x) = wx + b$ and $l(x,y;f)=(f(x) - y)^2$.
The bilevel problem for poisoning is as follows
\begin{equation}
    \begin{split}
        &\min_{u}\;\; \mathbb{E}_{{P}_{-}}[\max(\mathrm{sign}(w^\ast)(-b^\ast/w^\ast-x),0)]\\
        &\mathrm{s.t.}\;\; -\epsilon \leq u_i - x_i^{-} \leq \epsilon, \;\; \mathrm{for \;\; i = 1, ..., n}\\

        w^\ast,&b^\ast = \arg\min_{w, b}\; \frac{1}{2n}\big[\sum_{i=1}^{n}l(x_i^{+},1) + \sum_{i=1}^{n}l(u_i,-1)\big].
    \end{split}
    \label{eq:bilevel_linear}
\end{equation}

\begin{theorem}
\label{thm:linear}
If the perturbation is large enough, i.e., $\epsilon \geq \frac{\sum_i x_i^{+} - \sum_i x_i^{-}}{n}$ then there are two locally optimal solutions to (\ref{eq:bilevel_linear}) which are $u_i = x_i^{-} - \epsilon$ (Case 1) and $u_i = x_i^{-} + \epsilon$ (Case 2) for $i=1,...,n$.
Otherwise, there is a unique globally optimal solution $u_i = x_i^{-} - \epsilon$ (Case 1) for $i=1,...,n$.
\end{theorem}
Thus, optimal poisoning is achieved by shifting points of the $P^{-}$ class either towards left or right by the maximum amount $\epsilon$ (Fig.~\ref{fig:linear} and Appendix~\ref{app:isotropic_gaussian}). Moreover, the effect of poisoning an $\alpha$ fraction of points from the $P^{-}$ class with maximum permissible perturbation $\Tilde{\epsilon}$ is same as that of poisoning all points of $P^{-}$ class with $\epsilon = \alpha \Tilde{\epsilon}$ (Corollary~\ref{cor:partial_poisoning} in Appendix~\ref{app:proofs}).
Although a direct analysis is intractable for non-linear cases, we empirically observed that our attack moved the decision boundary of neural networks closer to the points of the target class as measured by the mean distance of points to the decision boundary of the smoothed classifier (Sec.~\ref{sec:exp_emp_robustness}).

\vspace{-0.1cm}
\section{Experiments}\label{sec:experiments}
In this section we present the results of our PACD\footnote{The code is available at \url{https://github.com/akshaymehra24/poisoning_certified_defenses}} attack on poisoning deep neural networks trained using methods that make the model certifiably robust to test-time attacks. All the results presented here are averaged over models trained with five random initialization.
We report the average certified radius (ACR) as the average of the certified radius obtained from the RS based certification procedure of \cite{cohen2019certified} for correctly classified points. Certified radius is zero for misclassified and abstained points.
The approximate certified accuracy (ACA) is the fraction of points correctly classified by the smoothed classifier ($\ell_2$ radius greater than zero). All results are reported over 500 randomly sampled images from the target classes.
We use the same value of $\sigma$ for smoothing during attack, retraining and evaluation. We compare our results to watermarking \cite{shafahi2018poison}
which has been used previously for clean label attacks (opacity 0.1 followed by clipping to make $\ell_{\infty}$ distortion equal to $\epsilon$),
and show that poison data generated using the bilevel optimization is significantly better at reducing the average certified radius.

\begin{table}[tb]
  \caption{Decrease in certified radius and certified accuracy of models trained with Gaussian augmentation \cite{cohen2019certified} on poison data compared to those of models trained on clean and watermarked data.

  }
  \label{Table:cohen_attack}
  \centering
  \small
  \resizebox{0.95\columnwidth}{!}{
    \begin{tabular}{c|c|c|cc}
    \toprule
    & \multirow{2}{*}{$\sigma$} & \multirow{2}{*}{Data} &  \multicolumn{2}{c}{\makecell{Certified robustness of target class}}\\
    & & & ACR & ACA(\%) \\

    \midrule
    \multirow{9}{*}{\STAB{\rotatebox[origin=c]{90}{MNIST}}} &
    \multirow{3}{*}{0.25} & Clean   & 0.896$\pm$0.01 &	98.92$\pm$0.32 \\
    & & Watermarked & 0.908$\pm$0.01 & 99.24$\pm$0.29 \\
    & & Poisoned & {\bf0.325}$\pm$0.10 &	{\bf71.96}$\pm$8.28 \\
    \cmidrule{2-5}
    &\multirow{3}{*}{0.5} & Clean & 1.481$\pm$0.02 &	99.16$\pm$0.34\\
    &  & Watermarked & 1.514$\pm$0.06 &	99.12$\pm$0.47\\
    & & Poisoned  & {\bf0.733}$\pm$0.10 &	{\bf90.68}$\pm$3.37 \\
    \cmidrule{2-5}
    &\multirow{3}{*}{0.75} & Clean & 1.549$\pm$0.11 & 98.48$\pm$0.35\\
    & & Watermarked & 1.566$\pm$0.06 &	98.36$\pm$0.39\\
    &  & Poisoned  & {\bf0.698}$\pm$0.13 &	{\bf84.92}$\pm$5.14 \\
    \midrule
    \midrule
    \multirow{6}{*}{\STAB{\rotatebox[origin=c]{90}{CIFAR10}}} &
    \multirow{3}{*}{0.25} & Clean   & 0.521$\pm$0.05 &	85.76$\pm$3.31 \\
    & & Watermarked & 0.470$\pm$0.01 &	83.22$\pm$1.41 \\
    & & Poisoned & {\bf0.059}$\pm$0.02 &	{\bf26.84}$\pm$6.04 \\
    \cmidrule{2-5}
    & \multirow{3}{*}{0.5} & Clean & 0.634$\pm$0.04 &	75.04$\pm$1.65\\
    & & Watermarked & 0.611$\pm$0.18 &	74.01$\pm$9.22\\
    & & Poisoned  & {\bf0.221}$\pm$0.04 &	{\bf42.28}$\pm$6.01 \\

    \bottomrule
    \end{tabular}
    }
\end{table}

We use our attack to poison MNIST and CIFAR10 dataset and use ApproxGrad to solve the bilevel optimization. The time complexity for ApproxGrad is $O(VT)$ where $V$ are the number of parameters in the machine learning model and $T$ is the number of lower-level updates. For datasets like Imagenet where the optimization must be performed over a very large number of batches, obtaining the solution to bilevel problems becomes computationally hard. Due to this bottleneck we leave the problem of poisoning Imagenet for future work. For the experiments with MNIST we randomly selected digit 8 and for CIFAR10 the class ``Ship'' as the target class for the attacker.
The attack results for other target classes are similar and are presented in the Appendix~\ref{app:additional_experiments}.
To ensure that the attack points satisfy the clean label constraint, the maximum permissible $\ell_{\infty}$ distortion is bounded by $\epsilon = 0.1$ for MNIST and $\epsilon = 0.03$ for CIFAR10 which is similar to the value used to generate imperceptible adversarial examples in previous works \cite{madry2017towards,goodfellow2014explaining}. We used  convolutional neural networks for our experiments on MNIST and Resnet-20 model for our experiments with CIFAR10. Model architectures, hyperparameters, generated attack examples (Fig.~\ref{fig:attack_egs} in Appendix), and additional results on transferability of our poisoned samples to models with different architectures
are presented in Appendix \ref{app:additional_experiments}.
Since models trained with standard training do not achieve high certified radius \cite{cohen2019certified}, we considered poisoning models trained with methods that improve the certified robustness guarantees to test time attacks.
For comparison, ACR on the target class ``Ship'' with Resnet-20 trained with standard training on clean CIFAR10 dataset is close to zero whereas for the same model trained with GA ($\sigma = 0.25$) ACR is close to 0.5.
Finally, we show that our attack can withstand the use of weight regularization, which has been shown to be effective at mitigating the effect of poisoning attacks \cite{carnerero2020regularisation}. The results of this experiment are present in Appendix~\ref{app:weight_reg}.

\begin{table}[tb]
  \caption{Decrease in certified radius and certified accuracy of models trained with MACER \cite{zhai2020macer} on poison data compared to those of models trained on clean and watermarked data.
  }
  \label{Table:macer_attack}
  \centering
  \small
  \resizebox{0.95\columnwidth}{!}{
    \begin{tabular}{c|c|c|cc}
    \toprule
    &\multirow{2}{*}{$\sigma$} & \multirow{2}{*}{Data} &
    \multicolumn{2}{c}{\makecell{Certified robustness of target class}}\\
    &&
    & ACR & ACA(\%) \\
    \midrule
    \multirow{9}{*}{\STAB{\rotatebox[origin=c]{90}{MNIST}}} &
    \multirow{3}{*}{0.25} & Clean   & 0.915$\pm$0.01	& 99.64$\pm$0.21\\
    & & Watermarked & 0.894$\pm$0.01 &	98.84$\pm$0.53\\
    & & Poisoned & {\bf0.431}$\pm$0.13 &	{\bf79.81}$\pm$9.26 \\
    \cmidrule{2-5}
    &\multirow{3}{*}{0.5} & Clean & 1.484$\pm$0.11 &	98.56$\pm$0.41\\
    & & Watermarked & 1.475$\pm$0.08 &	98.68$\pm$0.39\\
    & & Poisoned  & {\bf0.685}$\pm$0.16 &	{\bf84.36}$\pm$6.17 \\
    \cmidrule{2-5}
    &\multirow{3}{*}{0.75} & Clean & 1.353$\pm$0.13 &	93.81$\pm$2.08\\
    & & Watermarked & 1.415$\pm$0.11 &	94.52$\pm$1.58\\
    & & Poisoned  & {\bf1.008}$\pm$0.19 &	{\bf88.41}$\pm$4.64 \\

     \midrule
     \midrule
     \multirow{6}{*}{\STAB{\rotatebox[origin=c]{90}{CIFAR10}}} &
     \multirow{3}{*}{0.25} & Clean   & 0.593$\pm$0.05 &	83.84$\pm$2.26 \\
    & & Watermarked & 0.486$\pm$0.04 &	77.01$\pm$0.21 \\
    & & Poisoned & {\bf0.379}$\pm$0.11 &	{\bf72.41}$\pm$9.79\\
    \cmidrule{2-5}
    & \multirow{3}{*}{0.5} & Clean & 0.759$\pm$0.11 &	72.92$\pm$5.06\\
    & & Watermarked & 0.811$\pm$0.10	& 75.66$\pm$2.99\\
    & & Poisoned  & {\bf0.521}$\pm$0.11 &	{\bf65.24}$\pm$6.55 \\
    \bottomrule
    \end{tabular}
    }
\end{table}

\vspace{-0.1cm}
\subsection{Poisoning Gaussian data augmentation \cite{cohen2019certified}}
Here we show the effectiveness of our attack at compromise the certified robustness guarantees obtained with RS on a model trained using the GA. The results of the attack, present in Table~\ref{Table:cohen_attack}, show a significant decrease in the ACR and the certified accuracy of the target class of the model trained on poisoned data compared to the model trained on clean and watermarked data. Since the certified radius and certified accuracy are correlated, our poisoning attack which targets the reduction of certified radius (upper-level problem in Eq.~(\ref{Eq:Bilevel})) also causes a decrease in the certified accuracy. Significant degradation in average certified radius from 0.52 to 0.06 on CIFAR10 with imperceptibly distorted poison data shows the extreme vulnerability of GA to poisoning.

\vspace{-0.1cm}
\subsection{Poisoning MACER \cite{zhai2020macer}}
Here we use the bilevel formulation in Eq.~(\ref{Eq:Bilevel}) with $\mathcal{L}_\mathrm{macer}$ loss in the lower-level and generate poison data to reduce the certification guarantees of models trained with MACER. The poison data is generated with $k=2$, where $k$ are the number of noisy images used per training point to ease the bilevel optimization. However, during retraining $k=16$ is used, which is similar to the one used in the original work \cite{zhai2020macer}.
The ACR obtained using MACER is higher than that achievable using Gaussian augmentation based training consistent with \cite{zhai2020macer}. However, our data poisoning attack is still able to reduce the average certified radius of the method by more than 30\% (Table~\ref{Table:macer_attack}) even though the attack is evaluated against a much stronger defense ($k=16$ for retraining compared to $k=2$ for poisoning) than what the poison data was optimized against. This shows that the use of a larger number of noisy samples ($k$) cannot eliminate the effect of the attack, emphasising the importance of the threat posed by data poisoning.

\begin{table}[tb]
  \caption
  Decrease in certified radius and certified accuracy of models trained with SmoothAdv \cite{salman2019provably} on poison data compared to those of models trained on clean and watermarked data.

  }
  \label{Table:smoothadv_attack}
  \centering
  \small
  \resizebox{0.95\columnwidth}{!}{
    \begin{tabular}{c|c|c|cc}
    \toprule
    &\multirow{2}{*}{$\sigma$} & \multirow{2}{*}{Data} &
    \multicolumn{2}{c}{\makecell{Certified robustness of target class}}\\
    &&
    & ACR & ACA(\%) \\
    \midrule
    \multirow{9}{*}{\STAB{\rotatebox[origin=c]{90}{MNIST}}} &
    \multirow{3}{*}{0.25} & Clean   & 0.896$\pm$0.01 &	99.16$\pm$0.45 \\
    & & Watermarked & 0.906$\pm$0.01 &	99.28$\pm$0.16 \\
    & & Poisoned & {\bf0.672}$\pm$0.04 &	{\bf93.21}$\pm$1.92 \\
    \cmidrule{2-5}
   & \multirow{3}{*}{0.5} & Clean & 1.408$\pm$0.05 &	99.21$\pm$0.25\\
    & & Watermarked & 1.401$\pm$0.02 &	98.01$\pm$0.18\\
    & & Poisoned  & {\bf1.037}$\pm$0.06 &	{\bf93.81}$\pm$1.31 \\
   \cmidrule{2-5}
   & \multirow{3}{*}{0.75} & Clean & 1.262$\pm$0.05 &	95.68$\pm$0.47\\
    & & Watermarked & 1.433$\pm$0.03 &	97.21$\pm$0.13\\
    & & Poisoned  & {\bf0.924}$\pm$0.06 &	{\bf88.88}$\pm$0.18 \\
    \midrule
     \midrule
     \multirow{6}{*}{\STAB{\rotatebox[origin=c]{90}{CIFAR10}}} &
    \multirow{3}{*}{0.25} & Clean   & 0.504$\pm$0.02	& 78.76$\pm$0.81 \\
    & & Watermarked & 0.441$\pm$0.02 & 70.16$\pm$2.12 \\
    & & Poisoned & {\bf0.271}$\pm$0.02 &	{\bf55.78}$\pm$0.96 \\
    \cmidrule{2-5}
    &\multirow{3}{*}{0.5} & Clean & 0.479$\pm$0.07 &	65.84$\pm$4.81\\
    & & Watermarked & 0.473$\pm$0.02 &	62.51$\pm$2.12\\
   &  & Poisoned  & {\bf0.277}$\pm$0.02 &	{\bf49.11}$\pm$3.19 \\

    \bottomrule
    \end{tabular}
    }
\end{table}

\begin{figure}[tb]
  \centering
  \includegraphics[width=0.6\columnwidth]{images/teaser_c.pdf}
  \includegraphics[width=0.6\columnwidth]{images/attack_egs_c.pdf}
  \caption
  (Upper) ACR degrades more if larger perturbations are permitted to create poison data. But larger perturbation makes the poison points visibly distorted making them easier to detect with inspection (Lower).

  Poison data are generated with $\epsilon \in \{0,0.1,0.2,0.3\}$. We have used $\epsilon = 0.1$ for our attacks.}
  \label{fig:acr_vs_epsilon}
\end{figure}

\begin{figure*}[tb]
  \centering{
  \subfigure[Average certified radius of digit 8 in MNIST]{\includegraphics[width=0.775\columnwidth]{images/acr_mnist_c.pdf}}
  \hspace{0.15in}
  \subfigure[Approximate certified accuracy of digit 8 in MNIST]{\includegraphics[width=0.775\columnwidth]{images/aca_mnist_c.pdf}}
  \subfigure[Average certified radius of ``Ship'' in CIFAR10]{\includegraphics[width=0.775\columnwidth]{images/acr_cifar10_c.pdf}}
  \hspace{0.15in}
  \subfigure[Approximate certified accuracy of ``Ship'' in CIFAR10]{\includegraphics[width=0.775\columnwidth]{images/aca_cifar10_c.pdf}}
  \includegraphics[width=0.9\textwidth]{images/legend_c.pdf}
  }
  \caption{Successful transferability of our poisoned data when victim uses a training procedure different than the one used by the attacker to optimize the poison data. $\sigma = 0.5$ and $\sigma = 0.25$ are used for smoothing during training and evaluation for MNIST and CIFAR10.

  }
  \label{fig:transfer}
\end{figure*}

\begin{table}[tb]
  \caption{Decrease in the mean $\ell_2$-distortion needed to generate adversarial examples using PGD attack against the smooth classifier. This shows that the decision boundary of the smooth classifier is closer to the clean test points of the target class after poisoning.
  }
  \label{Table:empirical_robustness}
  \centering
  \small
  \resizebox{0.75\columnwidth}{!}{
    \begin{tabular}{c|c|c|c}
    \toprule
    & $\sigma$  & Clean data & Poisoned data\\
    \midrule
    \multirow{3}{*}{MNIST} & 0.25 & 3.271$\pm$0.10 & {\bf1.339}$\pm$0.16 \\

   & 0.5 & 3.637$\pm$0.15 & {\bf2.170}$\pm$0.09 \\

   & 0.75 & 3.961$\pm$0.18 & {\bf2.213}$\pm$0.31 \\
     \midrule
     \multirow{2}{*}{CIFAR10} &0.25 & 1.754$\pm$0.17 & {\bf0.132}$\pm$0.04 \\

    &0.5 & 1.996$\pm$0.09 & {\bf0.367}$\pm$0.06 \\
    \bottomrule
    \end{tabular}
    }
\end{table}

\subsection{Poisoning SmoothAdv \cite{salman2019provably}}
Here we present the results of our attack on models trained with SmoothAdv. To yield model with high certified robustness this training method requires the model parameters to be optimized using adversarial training of the smoothed classifier. We used 2 step PGD attack to obtain adversarial example of each point in the batch. We used a single noisy instance of the adversarial example while doing adversarial training. Although, using larger $k$ makes the certified robustness guarantees better, we used $k=1$ to save the computational time required for adversarial training. For bilevel training, we followed the similar procedure to generate adversarial examples for clean and poison data. The adversarial examples are then used as the data for the lower-level problem of Eq.~(\ref{Eq:Bilevel}) to do GA training for optimizing the network parameters. The batch of adversarial examples are recomputed against the updated model after each step of bilevel training. Note that this is an approximation to the actual solution of the minimax problem that has to be solved in the lower-level for generating poison data against SmoothAdv. However, the effectiveness of the attack (results in Table~\ref{Table:smoothadv_attack}) suggests that our approximation works well in practice and certified robustness guarantees achieved from SmoothAdv can be degraded by poisoning.

\subsection{Effect of the imperceptibility constraint}
Here we evaluate the effect of using different values of the perturbation strength $\epsilon$ which controls the maximum permissible distortion in Eq.~(\ref{Eq:Bilevel}). We use $\sigma = 0.25$ for smoothing and GA based training to generate and evaluate the attack. The results are summarized in Fig.~\ref{fig:acr_vs_epsilon}, which show that the ACR of the target class decreases as $\epsilon$ increases rendering certification guarantees useless. This is expected since larger $\epsilon$ creates a larger distribution shift among the target class data in the training and the test sets. However, larger permissible distortion to the data make the attack easier to detect by inspection. This is not be desirable from an attacker's perspective who wants to evade detection.

\subsection{Transferability of poisoned data}
Here we report the performance of the models trained on the poison data using different training procedures than the one assumed by the attacker for crafting poison data. We used $k=1$ and 2 steps of PGD attack to generate adversarial examples for SmoothAdv and $k=16$ for MACER during retraining.
The poison data generated against MACER was optimized using $k=2$.
The results are summarized in Fig.~\ref{fig:transfer}, which show that poisoned data optimized against any robust training procedure causes significant reduction in the certified robustness of models trained with a different training methods. Interestingly, poisoned data optimized against GA is extremely effective against other methods, considering the fact that it is the simplest of the three methods. The successful transferability of the poisoned data
across different training methods shows how brittle these methods can be when faced with a poisoned dataset.
We observe a similar success in transferability of the poison data to models with different architectures (Appendix~\ref{app:transfer_architecture}).

\if0
\begin{table*}
  \caption{Transfer-ability of the attack points when victim uses a different training procedure than used by the attacker to generate poison data for MNIST with digit 8 being the target class. $\sigma = 0.5$ is used for smoothing during training and evaluation. Certified robustness guarantees of each training method on clean data are present in the last row for reference.
  }
  \label{Table:mnist_transferability}
  \centering
  \small
  \resizebox{0.85\textwidth}{!}{
    \begin{tabular}{c|cc|cc|cc}
    \toprule
    \multirow{2}{*}{\makecell{Training method used for\\ generating poison data}} & \multicolumn{6}{c}{\makecell{Training method used for evaluation}}\\
    &\multicolumn{2}{c|}{\makecell{Gaussian Aug}} & \multicolumn{2}{c|}{\makecell{MACER \cite{zhai2020macer}}} & \multicolumn{2}{c}{\makecell{SmoothAdv \cite{salman2019provably}}}\\
    \midrule
    & ACR & ACA(\%) & ACR & ACA(\%) & ACR & ACA(\%)  \\
    \midrule
    Gaussian Aug & 0.733$\pm$0.10 &	90.68$\pm$0.03 &	0.741$\pm$0.09 &	87.88$\pm$0.04 &	1.116$\pm$0.12 &	96.91$\pm$0.01\\
    MACER \cite{zhai2020macer} & 0.881$\pm$0.03 &	93.10$\pm$0.01 &	0.685$\pm$0.16 &	84.45$\pm$0.06 &	1.036$\pm$0.05 &	94.65$\pm$0.01\\
    SmoothAdv \cite{salman2019provably} & 0.733$\pm$0.09 &	88.72$\pm$0.04 &	0.8732$\pm$0.23 &	88.68$\pm$0.09 &	1.037$\pm$0.06 &	93.81$\pm$0.01\\
    \midrule
    Clean data & 1.481$\pm$0.02 &	99.16$\pm$0.01&	1.484$\pm$0.11 &	98.56$\pm$0.01 &	1.408$\pm$0.05 &	99.21$\pm$0.01\\

    \bottomrule
    \end{tabular}
    }
\end{table*}
\fi

\if0
\begin{table*}
  \caption{Transferability of the attack points when victim uses a different training procedure than used by the attacker to generate poison data for CIFAR10 with class ``Ship'' being the target class. $\sigma = 0.25$ is used for smoothing during training and evaluation. Certified robustness guarantees of each training method on clean data are present in the last row for reference.
  }
  \label{Table:cifar10_transferability}
  \centering
  \small
  \resizebox{0.85\textwidth}{!}{
    \begin{tabular}{c|cc|cc|cc}
    \toprule
    \multirow{2}{*}{\makecell{Training method used for\\ generating poison data}} & \multicolumn{6}{c}{\makecell{Training method used for evaluation}}\\
    &\multicolumn{2}{c|}{\makecell{Gaussian Aug}} & \multicolumn{2}{c|}{\makecell{MACER \cite{zhai2020macer}}} & \multicolumn{2}{c}{\makecell{SmoothAdv \cite{salman2019provably}}}\\
    \midrule
    & ACR & ACA(\%) & ACR & ACA(\%) & ACR & ACA(\%)  \\
    \midrule
    Gaussian Aug & 0.059$\pm$0.01 &	26.84$\pm$0.06&	0.134$\pm$0.04&	41.08$\pm$0.08	&0.238$\pm$0.03&	55.01$\pm$0.05\\
    MACER \cite{zhai2020macer}& 0.235$\pm$0.02&	61.01$\pm$0.04&	0.379$\pm$0.10&	72.41$\pm$0.10&	0.3205$\pm$0.01 & 59.01$\pm$0.01\\
    SmoothAdv \cite{salman2019provably} & & & & &\\
    \midrule
    Clean data & 0.521$\pm$0.05 &	85.76$\pm$0.03 &	0.593$\pm$0.05 &	83.84$\pm$0.03 & 0.504$\pm$0.02	& 78.76$\pm$0.01 \\

    \bottomrule
    \end{tabular}
    }
\end{table*}
\fi

\vspace{-0.2cm}
\subsection{Empirical robustness of poisoned classifiers}\label{sec:exp_emp_robustness}
\vspace{-0.1cm}
Finally, we report the empirical robustness of the smoothed classifier where the base classifier is trained on clean and poisoned data using GA.
The poisoned data is generated against GA training in the lower-level as in Eq.~(\ref{Eq:Bilevel}). We report the mean $\ell_2$-distortion required to generate an adversarial example using the PGD attack \cite{salman2019provably} against the smoothed classifier using 200 and 100 randomly sampled test points of the target class from MNIST and CIFAR10, respectively, in Table~\ref{Table:empirical_robustness}.
We observe that our poisoning leads to a decrease in the empirical robustness of the smoothed classifier on clean test data.
This backs up our hypothesis
that the decision boundary of the smooth classifier must be changed to reduce the certified radius in nonlinear classifiers, similar to linear classifiers (Fig.~\ref{fig:linear}).

\if0
\begin{figure}[tb]
  \centering{
  \subfigure[]{\includegraphics[width=0.9\columnwidth]{images/acr_cifar10_c.pdf}}
  \subfigure[]{\includegraphics[width=0.9\columnwidth]{images/aca_cifar10_c.pdf}}
  }
  \caption{Transferability of the attack points when victim uses a different training procedure than used by the attacker to generate poison data for CIFAR10 with class ``Ship'' being the target class. $\sigma = 0.25$ is used for smoothing during training and evaluation.}
  \label{fig:transfer_cifar10}
\end{figure}
\fi

\vspace{-0.1cm}
\section{Conclusion}
\vspace{-0.15cm}
Certified robustness has emerged as a gold standard to gauge with certainty the susceptibility of machine learning models to test-time attacks.
In this work, we showed that these guarantees can be rendered ineffective by our bilevel optimization based data poisoning attack that adds imperceptible perturbations to the points of the target class.
Unlike previous data poisoning attacks, our attack can reduce the ACR of an entire target class and is even effective against models trained using training methods that have been shown to improve certified robustness. Our results suggests that data quality is a crucial factor in achieving high certified robustness guarantees but is overlooked by current approaches.

\vspace{-0.15cm}
\section{Acknowledgments}
\vspace{-0.15cm}
This work was supported by the NSF EPSCoR-Louisiana Materials Design Alliance (LAMDA) program \#OIA-1946231 and by LLNL Laboratory Directed Research and Development project 20-ER-014 (LLNL-CONF-817233).
This work was performed under the auspices of the U.S. Department of Energy by the Lawrence Livermore National Laboratory under Contract No. DE-AC52-07NA27344, Lawrence Livermore National Security, LLC.\footnote{The views and opinions of the authors do not necessarily reflect those of the U.S. government or Lawrence Livermore National Security, LLC neither of whom nor any of their employees make any endorsements, express or implied warranties or representations or assume any legal liability or responsibility for the accuracy, completeness, or usefulness of the information contained herein.}

\clearpage

{\small
\bibliographystyle{ieee_fullname}