\begin{document}

\title{On the Perils of Cascading Robust Classifiers}

\begin{abstract}

Ensembling certifiably robust neural networks is a promising approach for improving the \tilde{p}h{certified robust accuracy} of neural models. 
Black-box ensembles that assume only query-access to the constituent models (and their robustness certifiers) during prediction are particularly attractive due to their modular structure. 
Cascading ensembles are a popular instance of black-box ensembles that appear to improve certified robust accuracies in practice. 
However, we show that the robustness certifier used by a cascading ensemble is unsound. 
That is, when a cascading ensemble is certified as locally robust at an input $x$ (with respect to ${\epsilon}ilon$), there can be inputs $x'$ in the ${\epsilon}ilon$-ball centered at $x$, such that the cascade's prediction at $x'$ is different from $x$ and thus the ensemble is not locally robust. 
Our theoretical findings are accompanied by empirical results that further demonstrate this unsoundness. We present \tilde{p}h{cascade attack} (CasA), an adversarial attack against cascading ensembles, and show that: (1) there exists an adversarial input for up to 88\% of the samples where the 
ensemble claims to be certifiably robust and accurate; and (2) the accuracy of a cascading ensemble under our attack is as low as 11\% when it claims to be certifiably robust and accurate on 97\% of the test set. 
Our work reveals a critical pitfall of cascading certifiably robust models by showing that the seemingly beneficial strategy of cascading can actually hurt the robustness of the resulting ensemble. Our code is available at \url{https://github.com/TristaChi/ensembleKW}.

\end{abstract}

\section{Introduction}
\label{sec:intro}

Local robustness has emerged as an important requirement of classifier models. It ensures that models are not susceptible to misclassifications caused by small perturbations to correctly classified inputs.
A lack of robustness can be exploited by not only malicious actors (in the form of adversarial examples \citep{szegedy13}) but can also lead to incorrect behavior in the presence of natural noise \citep{gilmer19a}.
However, ensuring local robustness of neural network classifiers has turned out to be a hard challenge. Although neural networks can achieve state-of-the-art classification accuracies on a variety of important tasks,
neural classifiers with comparable certified robust accuracies\footnote{Percentage of inputs where the classifier is accurate and certified as locally robust.} ($\texttt{CRA}$, Def.~{\textnormal{e}}f{def:cra}) remain elusive, even when trained in a robustness-aware manner \citep{madry18,wong2018provable,cohen19,leino21}. 
In light of the limitations of robustness-aware training, ensembling certifiably robust neural classifiers has been shown to be a promising approach for improving certified robust accuracies \citep{wong2018scaling,yang2022on}. 
An ensemble combines the outputs of multiple base classifiers to make a prediction, and is a well-known mechanism for improving classification accuracy when one only has access to weak learners \citep{dietterich2000,bauer1999empirical}.

Ensembles designed to improve $\texttt{CRA}$ take one of two forms. 
\tilde{p}h{White-box ensembles} \citep{yang2022on,zhang2019enhancing,liu2020enhancing} assume white-box access to the constituent models. They calculate new logits by averaging the corresponding logits of the constituent classifiers. 
For local robustness certification, they treat the ensemble as a single, large model and then use off-the-shelf techniques  \citep{cohen19,weng18,wong2018provable,zhang18efficient} for certification.
\tilde{p}h{Black-box ensembles} \citep{wong2018scaling,blum2022boosting}, on the other hand, assume only query-access to the constituent classifiers during prediction, and are, therefore, agnostic to their internal details.
They re-use the prediction and certification outcomes of the constituent models to calculate the ensemble's prediction and certificate. Their black-box nature lends them modularity and permits any combination of constituent classifiers, irrespective of their individual certification mechanism, so we focus our efforts on them in this paper. 

\tilde{p}h{Cascading ensembles} \citep{wong2018scaling,blum2022boosting} are a particularly popular instance of black-box ensembles that appear to improve $\texttt{CRA}$ in practice. They evaluate the constituent classifiers (and their certifiers) in a fixed sequence.
The ensemble's prediction is the output of the first constituent classifier in the sequence that is certified locally robust, defaulting to the last classifier's output if no model can be certified.
Importantly, the cascading ensemble is itself certified locally robust only when at least one of the constituent classifiers is certified locally robust.

\begin{figure}
\caption{Visualizing classification results of 2D points for constituent models (a-c) and the corresponding Cascading Ensemble (d, Def.~{\textnormal{e}
\label{fig:2d-example}
\end{figure}

\textbf{Our contributions.} We show in this paper that the local robustness certification mechanism used by cascading ensembles is unsound even when the certifiers used by each of the constituent classifiers are sound (Theorem~{\textnormal{e}}f{thm:cascading_sound}). In other words, when a cascading ensemble is certified as locally robust at an input $x$, there can, in fact, be 
inputs $x'$ in the ${\epsilon}ilon$-ball centered at $x$, such that the cascade's prediction at $x'$ is different from $x$. 
Figure~{\textnormal{e}}f{fig:2d-example} demonstrates this visually on a toy dataset. The cascading ensemble can have points that are less than ${\epsilon}ilon$ away from the decision boundary, yet the ensemble is certified locally robust at such points (Figure~{\textnormal{e}}f{fig:2d-example}(d)).
As a consequence of our result, use of a cascading ensemble in any scenario requiring local robustness guarantees is unsafe and existing empirical results that report the $\texttt{CRA}$ of cascading ensembles are not valid.

Guided by our theoretical construction, we propose \tilde{p}h{cascade attack} (CasA, Algorithm~{\textnormal{e}}f{alg:attack}), an adversarial attack against cascading ensembles, and conduct an empirical evaluation with the cascading ensembles trained by \citet{wong2018scaling} for MNIST and CIFAR-10 datasets.
With CasA, we show that: (1) there exists an adversarial example for up to 88\% of the samples where the ensemble claims to be certifiably robust and accurate; (2) the empirical robust accuracy of a cascading ensemble is as low as 11\% while it claims to be certifiably robust and accurate on 97\% of the test set; and (3) viewing all experiments as a whole, the empirical robust accuracy of a cascading ensemble is almost always lower than even the $\texttt{CRA}$ of the single best model in the ensemble. Namely, a cascading ensemble is often less robust.
Our results conclusively demonstrate that the unsoundness of the cascading ensemble certification mechanism can be exploited in practice, and cause the ensemble to perform markedly worse than the single best constituent model.

We also present an alternate ensembling mechanism based on weighted voting that, like cascading ensembles, assumes only query-access to the constituent classifiers but comes with a provably sound local robustness certification procedure (Section~{\textnormal{e}}f{sec:defense}). 

We show through a thought experiment that it is possible for a voting ensemble to improve upon the $\texttt{CRA}$ of its constituent models (Section~{\textnormal{e}}f{sec:thought}), and observe that the key ingredient for the success of voting ensembles is a suitable balance between diversity and similarity of their constituents. 
We leave the design of training algorithms that balance the diversity and similarity of the constituent classifiers as future work.

\section{Cascading Ensembles}
\label{sec:unsound}

In this section, we introduce our notation and required definitions. We then show the local robustness certification procedure used by cascading ensembles is unsound.

\subsection{Certifiable Classifiers and Ensemblers}\label{sec:cascade-local-robustness}
We begin with our notation and necessary definitions. Suppose a neural network $f: \mathbb{R}^d {\textnormal{i}}ghtarrow \mathbb{R}^m$ takes an input and outputs the probability of $m$ different classes. The subscript $x_j$ denotes the $j$-th element of a vector $x$. When discussing multiple networks, we differentiate them with a superscript, e.g. $f^\id{1}, f^\id{2}$. Throughout the paper we use the upper-case letter $F$ to denote the prediction of $f$ such that $F(x) = \arg\max_{j \in \mathcal{Y}}\{f_j(x)\}$ where $f_j$ is the logit for class $j$ and $\mathcal{Y}=[m]$.\footnote{$[m]:=\{0, 1, ..., m-1\}$} 
The prediction $F(x)$ is considered ${\epsilon}ilon$-locally robust at $x$ if all neighbors within an ${\epsilon}ilon$-ball centered at $x$ receive the same predictions, which is formally stated in Def.~{\textnormal{e}}f{def:locally-robust}.

\begin{definition}[${\epsilon}ilon$-Local Robustness]\label{def:locally-robust}
A network, $F$, is ${\epsilon}ilon$-locally robust at $x$ w.r.t to norm, $||\cdot||$, if $\forall x' ~.~ ||x'-x|| \leq {\epsilon}ilon \Longrightarrow F(x') = F(x)$.

\end{definition}

Though local robustness certification of ReLU networks is NP-Complete \citep{katz17}, due to its importance, the problem has been receiving increasing attention from the community. Proposed certification methods rely on a variety of algorithmic approaches like  
solving corresponding linear~\citep{jordan19provable} or semi-definite programs~\citep{raghunathan2018certified}, interval propagations~\citep{gowal2018effectiveness, lee20lipschitz, zhang18efficient}, abstract interpretation~\citep{singh19}, geometric projections~\citep{fromherz20}, dual networks~\citep{wong2018provable}, or Lipschitz approximations~\citep{leino21,weng18}.

If a certification method is provided for a network $F$, we use ${\tt cert}\xspaceify{F}^{\epsilon}ilon: \mathbb{R}^d {\textnormal{i}}ghtarrow \mathcal{Y} \times \{0, 1\}$ to denote a \tilde{p}h{certifiable neural classifier} that returns a prediction according to $F$ and the outcome of the certification method applied to $F$ with respect to robustness radius ${\epsilon}ilon$. 
We use $\lab{{\tt cert}\xspaceify{F}^{\epsilon}ilon}(x)$ to refer to the prediction and $\cer{{\tt cert}\xspaceify{F}^{\epsilon}ilon}(x)$ to refer to the certification outcome.  
If $\cer{{\tt cert}\xspaceify{F}^{\epsilon}ilon}(x) = 0$, the accompanying robustness certification is unable to certify $F$ (i.e., $\lab{{\tt cert}\xspaceify{F}}$) as ${\epsilon}ilon$-locally robust at $x$. 
When ${\epsilon}ilon$ is clear from the context, we directly write ${\tt cert}\xspaceify{F}$. One popular metric to evaluate the performance of any ${\tt cert}\xspaceify{F}$ is Certified Robust Accuracy (\texttt{CRA}).

\begin{definition}[Certified Robust Accuracy]
	\label{def:cra}
		The certified robust accuracy ($\texttt{CRA}$) of a certifiable classifier ${\tt cert}\xspaceify{F} \in \mathbb{R}^d {\textnormal{i}}ghtarrow \mathcal{Y} \times \{0, 1\}$ on a given dataset $S_k \subseteq \mathbb{R}^d\times \mathcal{Y}$ with $k$ samples is given by $\texttt{CRA}({\tt cert}\xspaceify{F},S_k) := 1/k \sum_{(x_i,y_i) \in S_k}\mathds{1}[{\tt cert}\xspaceify{F}(x_i)=(y_i,1)] $.

	\end{definition}
For ${\tt cert}\xspaceify{F}$ and its \texttt{CRA}~to be useful in practice without providing false robustness guarantees, it must be \tilde{p}h{sound} to begin with (Def.~{\textnormal{e}}f{def:soundness-of-F_Tilde}). 

\begin{definition}[Certification Soundness]~\label{def:soundness-of-F_Tilde} A certifiable classifier, ${\tt cert}\xspaceify{F}: \mathbb{R}^d {\textnormal{i}}ghtarrow \mathcal{Y} \times \{0, 1\}$,  is sound if $\forall x \in \mathbb{R}^d ~.~ \cer{{\tt cert}\xspaceify{F}}(x) = 1  ~~\Longrightarrow~~ \lab{{\tt cert}\xspaceify{F}} \text{ is } {\epsilon}ilon\text{-locally robust at } x$.

\end{definition}
Notice that if there exist ${\epsilon}ilon$-close inputs $x, x'$ where ${\tt cert}\xspaceify{F}(x) = (y, 1)$ and ${\tt cert}\xspaceify{F}(x') = (y', 0)$, where $y \neq y'$, then it still means that ${\tt cert}\xspaceify{F}$ is not sound. We define an \tilde{p}h{ensembler} (Def.~{\textnormal{e}}f{def:ensembler}) as a function that combines multiple certifiable classifiers into a single certifiable classifier (i.e., an \tilde{p}h{ensemble}).
\begin{definition}[Ensembler]\label{def:ensembler}
	Let $\mathbb{{\tt cert}\xspaceify{F}} := \mathbb{R}^d {\textnormal{i}}ghtarrow \mathcal{Y} \times \{0, 1\}$ represent the set of all certifiable classifiers.
	An ensembler  $\mathcal{E}: \mathbb{{\tt cert}\xspaceify{F}}^N {\textnormal{i}}ghtarrow \mathbb{{\tt cert}\xspaceify{F}}$ is a function over $N$ certifiable classifiers that returns a certifiable classifier.
\end{definition}

A \tilde{p}h{query-access} ensembler formalizes our notion of a black-box ensemble.
\begin{definition}[Query-Access Ensembler]\label{def:qa_ensembler}
	Let $\mathbb{G} := (\mathcal{Y} \times \{0, 1\})^N {\textnormal{i}}ghtarrow \mathcal{Y} \times \{0, 1\}$.
	$\mathcal{E}$ is a query-access ensembler if,
	$ \forall {\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1} \in \mathbb{{\tt cert}\xspaceify{F}}~.~\exists G \in \mathbb{G}~.~\forall x \in \mathbb{R}^d.$ 
	$$
		 \mathcal{E}\left({\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1}{\textnormal{i}}ght)(x) ~=~ G\left({\tt cert}\xspaceify{F}^\id{0}(x), {\tt cert}\xspaceify{F}^\id{1}(x), \ldots, {\tt cert}\xspaceify{F}^\id{N-1}(x){\textnormal{i}}ght)
	$$
\end{definition}

Def.~{\textnormal{e}}f{def:qa_ensembler} says that if $\mathcal{E}$ is \tilde{p}h{query-access} its output ${\tt cert}\xspaceify{F}$ can always be re-written as a function over the outputs of the certifiable classifiers ${\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1}$. 
Put differently, ${\tt cert}\xspaceify{F}$ only has black-box or query-access to classifiers  ${\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1}$.

Finally, a \tilde{p}h{soundness-preserving} ensembler (Def.~{\textnormal{e}}f{def:sp_ensembler}) ensures that if the constituent certifiable classifiers are sound (as defined in Def.~{\textnormal{e}}f{def:soundness-of-F_Tilde}), the ensemble output by the ensembler is also sound.
\begin{definition}[Soundness-Preserving Ensembler]\label{def:sp_ensembler}
	An ensembler $\mathcal{E}$ is soundness-preserving if,
	$\forall {\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1} \in \mathbb{{\tt cert}\xspaceify{F}}, {\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1}~\text{are sound} ~~\Longrightarrow~~ \mathcal{E}({\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1})~\text{is sound}$.

\end{definition}

\subsection{Cascading Ensembler Is Not Soundness-Preserving}
\label{sec:cascade-unsoundness}
Cascading ensembles \citep{wong2018scaling, blum2022boosting} are a popular instance of black-box ensembles that appear to be practically effective in improving certified robust accuracies. However, we show that cascading ensembles are not sound.

We define a cascading ensemble to be the output of a \tilde{p}h{cascading ensembler} (Def.~{\textnormal{e}}f{def:cascading_ensembler}).
A cascading ensemble evaluates its constituent certifiable classifiers in a fixed sequence. For a given input $x$, the ensemble either returns the prediction and certification outcomes of the first constituent classifier ${\tt cert}\xspaceify{F}^\id{j}$ such that 
$\cer{{\tt cert}\xspaceify{F}}^\id{j}=1$ or of the last constituent classifier in case none of the constituent classifiers can be certified. Clearly, cascading ensemblers are query-access (formal proof in Appendix~{\textnormal{e}}f{sec:proofs}).

\begin{definition}[Cascading Ensembler]\label{def:cascading_ensembler}
    Let ${\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1}$ be $N$ certifiable classifiers. A cascading ensembler $\mathcal{E}_C: \mathbb{{\tt cert}\xspaceify{F}}^N {\textnormal{i}}ghtarrow \mathbb{{\tt cert}\xspaceify{F}}$ is defined as follows
    \begin{align*}
	    \mathcal{E}_C\left({\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1}{\textnormal{i}}ght)(x) ~:=~
        \begin{cases} 
		{\tt cert}\xspaceify{F}^\id{j}(x) & \text{if } \exists j \leq N-1~.~\texttt{c}(j)=1 \\
		{\tt cert}\xspaceify{F}^\id{{N-1}}(x) & \text{otherwise}
        \end{cases}
        \end{align*}
	where $\texttt{c}(j) := 1 \text{ if } (\cer{{\tt cert}\xspaceify{F}^\id{j}}(x) = 1) \text{ and } (\forall i < j, \cer{{\tt cert}\xspaceify{F}^\id{i}}(x) = 0)$, and 0 otherwise.
\end{definition}

Theorem~{\textnormal{e}}f{thm:cascading_sound} shows that cascading ensemblers are not soundness-preserving, and so a cascading ensemble can be unsound. We show this by means of a counterexample.
\begin{theorem}  
\label{thm:cascading_sound}
	The cascading ensembler $\mathcal{E}_C$ is not soundness-preserving. 
\end{theorem}
\begin{proof}
We can re-write the theorem statement as,
$\exists {\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1} \in \mathbb{{\tt cert}\xspaceify{F}}$ such that for ${\tt cert}\xspaceify{F} := \mathcal{E}_C({\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1}),
	    \exists x \in \mathbb{R}^d, \cer{{\tt cert}\xspaceify{F}}(x) = 1  ~\centernot{\Longrightarrow}~ \lab{{\tt cert}\xspaceify{F}} \text{ is } {\epsilon}ilon\text{-locally robust at } x$.

We prove by constructing the following counterexample. Consider a cascading ensemble ${\tt cert}\xspaceify{F}$ constituted of certifiable classifiers ${\tt cert}\xspaceify{F}^\id{0}$ and ${\tt cert}\xspaceify{F}^\id{1}$.
${\tt cert}\xspaceify{F}^\id{0}$ and ${\tt cert}\xspaceify{F}^\id{1}$ are such there exists an $x$ where

\begin{equation}
\label{eq:cas_sound1}
	\left(\cer{{\tt cert}\xspaceify{F}}^\id{0}(x) = 0{\textnormal{i}}ght)~\wedge~\left({\tt cert}\xspaceify{F}^\id{1}(x) = (y,1){\textnormal{i}}ght)
\end{equation}

Using Def.~{\textnormal{e}}f{def:cascading_ensembler}, it is true that ${\tt cert}\xspaceify{F}(x) = (y,1)$.

Without violating ({\textnormal{e}}f{eq:cas_sound1}), we can have another point $x'$ such that, 

\begin{equation}
\label{eq:cas_sound2}
	(||x-x'|| \leq {\epsilon}ilon)~\wedge~({\tt cert}\xspaceify{F}^\id{0}(x') = (y',1))~\wedge~({\tt cert}\xspaceify{F}^\id{1}(x') = (y,0))~\wedge~(y' \neq y)
\end{equation}

Using Def.~{\textnormal{e}}f{def:cascading_ensembler}, it is true that ${\tt cert}\xspaceify{F}(x') = (y',1)$.

Thus, for two points $x, x'$ constructed as above, we show that $\exists x, x', \text{ s.t. } ||x'-x|| \leq {\epsilon}ilon$, $\cer{{\tt cert}\xspaceify{F}}(x) = 1  ~~\centernot{\Longrightarrow}~~  \lab{{\tt cert}\xspaceify{F}}(x') = \lab{{\tt cert}\xspaceify{F}}(x)$,

which violates the condition of local robustness (Def.~{\textnormal{e}}f{def:locally-robust}).
\end{proof}

The counterexample constructed in Thm.~{\textnormal{e}}f{thm:cascading_sound} is not just hypothetical, but something that materializes on real models (see Figure~{\textnormal{e}}f{fig:2d-example} for a toy example and Section~{\textnormal{e}}f{sec:eval} for our empirical evaluation).

\section{Attacking Cascading Ensembles}
\label{sec:attack}
\begin{algorithm2e}[t]
\small
{\bm{s}}pace{0.5em}
	\KwIn{Ensemble ${\tt cert}\xspaceify{F} \in \mathbb{{\tt cert}\xspaceify{F}}$, constituent models ${\tt cert}\xspaceify{F}^\id{0}$, $\ldots$,  ${\tt cert}\xspaceify{F}^\id{N-1} \in \mathbb{{\tt cert}\xspaceify{F}}$, input $x \in \mathbb{R}^d$, 

	attack bound ${\epsilon}ilon \in \mathbb{R}$, and distance metric $\ell_p$}
\KwOut{An attack input $x' \in \mathbb{R}^d$}
{\bm{s}}pace{0.5em}
\Fn{\Fattack{${\tt cert}\xspaceify{F}, {\tt cert}\xspaceify{F}^\id{0}~,~\ldots~,~{\tt cert}\xspaceify{F}^\id{N-1}~,~x~,~{\epsilon}ilon~,~\ell_p$}}{
	$y ~:=~ \lab{{\tt cert}\xspaceify{F}}(x)$\;
	$\texttt{idxs} ~:=~ \{i~|~i \in [N] \wedge \lab{{\tt cert}\xspaceify{F}^\id{i}}(x) \neq y\}~\cup~\{N-1\}$\;
	\ForEach{$i \in \texttt{idxs}$}{
		\eIf{$i = N-1$}{
			$x^* ~:=~ x~+~\argmax\limits_{\delta \in \mathbb{B}_p(0,{\epsilon}ilon)}~\left(\mathcal{L}^{ce}(\textsf{one-hot}(\lab{{\tt cert}\xspaceify{F}^\id{i}}(x+\delta)),~\textsf{one-hot}(y))~+~\sum\limits_{k<i} (1 - \mathds{1}\left[\cer{{\tt cert}\xspaceify{F}^\id{k}}(x+\delta){\textnormal{i}}ght]){\textnormal{i}}ght)$\algnote\;

		}{
			$x^* ~:=~ x~+~\argmax\limits_{\delta \in \mathbb{B}_p(0,{\epsilon}ilon)}~\left(\mathds{1}\left[\cer{{\tt cert}\xspaceify{F}^\id{i}}(x+\delta){\textnormal{i}}ght]~+~\sum\limits_{k<i} (1 - \mathds{1}\left[\cer{{\tt cert}\xspaceify{F}^\id{k}}(x+\delta){\textnormal{i}}ght]){\textnormal{i}}ght)$\algnote\;

		}
		\If{$\lab{{\tt cert}\xspaceify{F}}(x^*) \neq y$}{
			\textbf{return} $x^*$\;
		}
	}
	\textbf{return} $x$\;
}
\caption{Cascade Attack (CasA)}
\label{alg:attack}
\end{algorithm2e}
\footnotetext{In our implementation, we use a surrogate version of this objective (see Section~{\textnormal{e}}f{sec:attack}).}

Section~{\textnormal{e}}f{sec:cascade-unsoundness} shows that a cascading ensemble does not provide a robustness guarantee.

We further show here how one can attack the cascading ensemble and find an adversarial example within the ${\epsilon}ilon$-ball centered at the input $x$.

\noindent\textbf{Overview of Attack.} Algorithm~{\textnormal{e}}f{alg:attack} describes the attack algorithm, \tilde{p}h{cascade attack} (CasA), inspired by the proof of Theorem~{\textnormal{e}}f{thm:cascading_sound}. Given an input $x$, the goal of the algorithm is to find an input $x'$ in the ${\epsilon}ilon$-ball centered at $x$ such that the predictions of the cascade at $x$ and $x'$ are different. 

The inputs to the algorithm are an ensemble ${\tt cert}\xspaceify{F}$, its constituent classifiers ${\tt cert}\xspaceify{F}^\id{0}$, $\ldots$,  ${\tt cert}\xspaceify{F}^\id{N-1}$,
the input $x$ to be attacked, and the attack distance bound ${\epsilon}ilon$ as well as distance metric $\ell_p$. The algorithm either returns a successful adversarial input $x'$ such that $||x-x'||_p \leq {\epsilon}ilon$ and $\lab{{\tt cert}\xspaceify{F}}(x) \neq \lab{{\tt cert}\xspaceify{F}}(x')$ or it returns the original input $x$ if no adversarial input was found. We use the following notations: $\mathcal{L}^{ce}$ stands for cross-entropy loss, $\textsf{one-hot}$ is the one-hot encoding function, $\mathds{1}$ is the indicator function, and $\mathbb{B}_p(0,{\epsilon}ilon)$ is the $\ell_p$-ball of radius ${\epsilon}ilon$ centered at $0$.
 
\noindent\textbf{Preparing Targets.} CasA gets the label $y$ predicted by the ensemble ${\tt cert}\xspaceify{F}$ at input $x$ (line 2) to select the constituent models it may attack. The attacker is only interested in a constituent model (by remembering its index $i$) if it predicts a label other than $y$ at $x$ or it is the last one (line 3). We are not interested in attacking a model ${\tt cert}\xspaceify{F}^\id{j}$ that predicts $y$ at $x$ because such an effort is bound to fail. ${\tt cert}\xspaceify{F}^\id{j}$ is still sound even though the ensemble is not; therefore, no point $x'$ assigned a label other than $y$ by ${\tt cert}\xspaceify{F}^\id{j}$ is such that it is both less than ${\epsilon}ilon$-away from $x$ and ${\tt cert}\xspaceify{F}^\id{j}$ is also certifiably robust at $x'$ (the second condition is necessary for ${\tt cert}\xspaceify{F}^\id{j}$ to be used for prediction at $x'$ by the ensemble).

However, the last model ${\tt cert}\xspaceify{F}^\id{N-1}$ is an exception and always remembered, i.e. $\texttt{idxs}$ always includes $N-1$. The reason is that, given an input $x'$, if all models ${\tt cert}\xspaceify{F}^\id{i};i<N-1$ fail to be certifiably robust at $x'$, the ensemble uses ${\tt cert}\xspaceify{F}^\id{N-1}$ for prediction at $x'$ irrespective of whether ${\tt cert}\xspaceify{F}^\id{N-1}$ is itself certifiably robust at $x'$ or not.
 
\noindent\textbf{Attacker's Steps.} For each model index in $\texttt{idxs}$, we try to find an adversarial example (lines 4-10). An attacker stops as soon as they find a valid adversarial example (lines 9-10). Lines 6 and 8 describe the objective an attacker minimizes to find the adversarial examples. If index $i \neq N-1$, the attacker optimizes $\delta$ such that, at input $x+\delta$, the model ${\tt cert}\xspaceify{F}^\id{i}$ is certified robust whereas all other models ${\tt cert}\xspaceify{F}^\id{k};k<i$ are not certified robust. This ensures that model ${\tt cert}\xspaceify{F}^\id{i}$ is used for prediction at input $x+\delta$ as it is certifiably robust at $x$.  If index $i = N-1$, we still require that all models ${\tt cert}\xspaceify{F}^\id{k};k<i$ are not certified robust at $x+\delta$. But instead of requiring that ${\tt cert}\xspaceify{F}^\id{i}$ is certified robust at $x+\delta$, we only require that the predicted label at $x+\delta$ be different from $y$. We solve the optimization problems on lines 6 and 8 using projected gradient descent (PGD)~\citep{madry18}.

\noindent\textbf{Surrogate Objectives.} For cases when the certification procedure, i.e. $\mathds{1}[\cer{{\tt cert}\xspaceify{F}^\id{i}}(x+\delta)]$, is not differentiable or too expensive to run multiple times, we provide the following cheap surrogate replacements. The intuition underlying the surrogate versions is that, given a model, the distance to the decision boundary from an input is correlated with the margin between the top logit scores of the model at that input. 

For the problem $\argmax_{\delta \in \mathbb{B}_p(0,{\epsilon}ilon)} \mathds{1}[\cer{{\tt cert}\xspaceify{F}^\id{i}}(x+\delta)]$, we try to increase the logit score associated with the desired prediction as much as possible. Then, a surrogate version of the problem is as follows (where $\logit{{\tt cert}\xspaceify{F}^\id{i}}$ represents the logit scores produced by model ${\tt cert}\xspaceify{F}^\id{i}$):
\begin{align}\label{eq:attack_surrogate1}
	\argmax_{\delta \in \mathbb{B}_p(0,{\epsilon}ilon)} -\mathcal{L}^{ce}(\logit{{\tt cert}\xspaceify{F}^\id{i}}(x+\delta),~\textsf{one-hot}(\lab{{\tt cert}\xspaceify{F}^\id{i}}(x)))
\end{align}
 For the problem $\argmax_{\delta \in \mathbb{B}_p(0,{\epsilon}ilon)} \sum_{k<i} (1 - \mathds{1}[\cer{{\tt cert}\xspaceify{F}^\id{k}}(x+\delta)])$, we want the input $x+\delta$ to be as close as possible to the decision boundaries for each of the models by ${\tt cert}\xspaceify{F}^\id{k}, k < i$ so that the robustness certifications will fail. The specific predictions $\lab{{\tt cert}\xspaceify{F}^\id{k}}(x+\delta)$ of these models do not matter. Towards that end, we aim to make the margin between the logit scores of any model ${\tt cert}\xspaceify{F}^\id{k}$ be as small as possible. This leads to the following surrogate problem (where $\textsf{unif}$ is a discrete uniform distribution):
\begin{align}\label{eq:attack_surrogate2}
	\argmax_{\delta \in \mathbb{B}_p(0,{\epsilon}ilon)} -\sum_{k<i} \mathcal{L}^{ce}(\logit{{\tt cert}\xspaceify{F}^\id{k}}(x+\delta),~\textsf{unif})
\end{align}

\section{Empirical Evaluation}
\label{sec:eval}

The goal of our empirical evaluation is to demonstrate the extent to which the unsoundness of the cascading ensembles manifests in practice and can be exploited by an adversary, i.e. CasA.

For our measurements, we use the $\ell_\infty$ and $\ell_2$ robust cascading ensembles constructed by \citet{wong2018scaling} for MNIST~\citep{lecun1998gradient} and CIFAR-10~\citep{krizhevsky09} datasets. 
The constituent classifiers in these cascades use a local robustness certification mechanism based on dual networks~\citep{wong2018scaling}. 
Each cascade includes between 2-7 certifiable classifiers with the same architecture (except for the $\ell_\infty$ robust, CIFAR-10 Resnet cascades that include only a single constituent model, and are hence not considered in our evaluation).

The training code and all the constituent models in the ensembles are made available by \citet{wong2018scaling} in a public repository~\citep{wongcode}.

We report the certified robust accuracy (\texttt{CRA}) and standard accuracy (\texttt{Acc}) for the cascading ensemble as well as the single best constituent model in the ensemble. While the certifier for a single model is sound,  the ensemble certifier is unsound and the reported ensemble $\texttt{CRA}$ is an over-estimate. We therefore measure the empirical robustness of the ensemble under CasA. Certifying with dual networks~\citep{wong2018scaling} is differentiable but extremely expensive. To run the attack more efficiently, we use the surrogate replacements in Section~{\textnormal{e}}f{sec:attack} and take 100 steps using PGD (other hyper-parameters to follow in Appendix~{\textnormal{e}}f{sec:hparams of tabel 1}) to empirically minimize the objectives. After the attack, we report the false positive rate (\texttt{FPR}), i.e. \% of test inputs for which an adversarial example is found within the ${\epsilon}ilon$-ball, and the empirical robust accuracy (\texttt{ERA}), i.e. \% of test set where the cascade is empirically robust (i.e., our attack failed). All our experiments were run on a pair of NVIDIA TITAN RTX GPUs with 24 GB of RAM each, and a 4.2GHz Intel Core i7-7700K with 64 GB of RAM.

\begin{table}[!t]
	\caption{Results on models pre-trained by \citet{wong2018scaling} for $\ell_\infty$ (top) and $\ell_2$ (bottom) robustness. \texttt{CRA}: \% of test set where model is certified robust and accurate. \texttt{Acc}: \% of test set where model is accurate. \texttt{FPR}: among all test inputs where cascade is certified robust and accurate, \% of inputs for which an adversarial example is found within the ${\epsilon}ilon$-ball using our ensemble attack (i.e., false positive rate). \texttt{ERA}: \% of test set where the cascading is empirically robust (i.e., our attack failed) and accurate (\texttt{ERA}~of a single model is always greater or equal to its~\texttt{CRA}~because of \tilde{p}h{soundness} and therefore not included). The unsoundness of cascade certification is shown by the high false positive rates (\texttt{FPR}).}
    \label{tab:ensemble_attack}
    \centering
    {\textnormal{e}}sizebox{0.9\textwidth}{!}{
    \begin{tabular}{ c c c | c c | c c c c }
    \toprule
    \toprule
    {$\ell_\infty$} & {} & {} & \multicolumn{2}{c}{Single Model} & \multicolumn{4}{|c}{Cascading Ensemble} \\
	    Dataset & Model & ${\epsilon}ilon$ & \texttt{CRA}(\%) & \texttt{Acc}(\%) & unsound \texttt{CRA}(\%) & \texttt{FPR}(\%)&  \texttt{Acc}(\%) & \texttt{ERA}(\%) \\
    \midrule
	    MNIST & Small, Exact
	    & 0.1 & 95.54 & 98.96 & 96.33 & 88.71&96.62 &11.17 \\
    MNIST & Small & 0.1 & 94.94 & 98.79 & 96.07 & 81.93&96.24 &17.51\\
    MNIST & Large & 0.1 & 95.55 & 98.81 & 96.27 & 86.37&96.42  &13.27\\
    \midrule
    MNIST & Small & 0.3 & 56.21 & 85.23 & 65.41 & 88.87&65.80  &7.67\\
    MNIST & Large & 0.3 & 58.02 & 88.84 & 65.50 &85.27 &65.50  &9.65\\
    \midrule
    CIFAR10 & Small & 2/255 & 46.43 & 60.86 & 56.65 & 11.51&56.65  &50.13\\
    CIFAR10 & Large & 2/255 & 52.65 & 67.70 & 64.87 & 10.47&65.13   & 58.15\\

    \midrule
    CIFAR10 & Small & 8/255 & 20.58 & 27.60 &28.32 &16.00 &28.32 & 23.79\\
    CIFAR10 & Large & 8/255 & 16.04 & 19.01 & 20.83 &17.67&20.83   &17.15\\
    \bottomrule\\
    \end{tabular}}
    {\textnormal{e}}sizebox{0.9\textwidth}{!}{
    \begin{tabular}{ c c c | c c | c c c c }
    \toprule
    \toprule
    {$\ell_2$} & {} & {} & \multicolumn{2}{c}{Single Model} & \multicolumn{4}{|c}{Cascading} \\
	    Dataset & Model & ${\epsilon}ilon$ & \texttt{CRA}(\%) & \texttt{Acc}(\%) & unsound \texttt{CRA}(\%) & \texttt{FPR}(\%)&  \texttt{Acc}(\%) & \texttt{ERA}(\%) \\
    \midrule
	    MNIST & Small, Exact
	    & 1.58 & 43.52 & 88.14 & 75.58 & 44.72&80.43& 43.46\\
    MNIST & Small & 1.58 & 43.34 & 87.73 & 74.66 & 40.93&79.07 &45.73\\
    MNIST & Large & 1.58 & 43.96 & 88.39 & 74.50 & 51.95&74.99  &35.81\\
    \midrule
    CIFAR10 & Small & 36/255 & 46.05 & 54.39 & 49.89 & 3.61 & 51.37  &49.27\\
    CIFAR10 & Large & 36/255 & 50.26 & 60.14 & 58.72 & 2.70 & 58.76  &57.17 \\
    CIFAR10 & Resnet & 36/255 & 51.65 & 60.70 &58.65 &3.41 & 58.69 & 56.68\\
    \bottomrule\\
    \end{tabular}}
\end{table}

Table~{\textnormal{e}}f{tab:ensemble_attack} shows the results for $\ell_\infty$ robustness (top) and $\ell_2$ robustness (bottom).
Each row in the table represents a specific combination of dataset (MNIST or CIFAR-10), architecture (Small or Large convolutional networks), and ${\epsilon}ilon$ value used for local robustness certification. 
The structure of the table is the same as Tables 2 and 4 in~\citep{wong2018scaling}, except we add the columns reporting $\texttt{FPR}$ and $\texttt{ERA}$. 

\textbf{Summary of Results.}
We see from Table~{\textnormal{e}}f{tab:ensemble_attack} that, irrespective of the dataset, model, ${\epsilon}ilon$ value, or $\ell_p$ metric under consideration, our attack can find false positives, with false positive rates (\texttt{FPR}) as high as 88.87\%.
In other words, there always exist test inputs where the ensemble is accurate and declares itself to be certified robust, but our attack is able to find an adversarial example. 
This result demonstrates that the unsoundness of the cascading ensemble certification mechanism is not just a problem in theory but it can be exploited by adversaries in practice. 
More strikingly, the empirical robust accuracy (\texttt{ERA}) of the ensemble is often significantly lower than the certified robust accuracy (\texttt{CRA}) of the best constituent model. 
Since the $\texttt{ERA}$ of a model is an upper-bound of its $\texttt{CRA}$, the actual $\texttt{CRA}$ of the ensemble can be no larger than the reported $\texttt{ERA}$. This result shows that the use of a cascading ensemble can actually hurt the robustness instead of improving it. 

\textbf{Attack Efficiency.} In Table~{\textnormal{e}}f{tab:the efficiency of the attack}, we compare the attack results of CasA using the original objectives, i.e. dual networks~\citep{wong2018scaling}, and using surrogate replacements. Because the ensemble on MNIST contains more constituent models, it uses more memory with dual networks compared to CIFAR10. Our report of run time and memory usage shows that using surrogate replacements allows us to run attacks with larger batch size, less memory and time to reach the same level of performance.

\begin{table}[!t]
	\caption{Run time and peak memory usage of CasA. Results are reported on one Titan RTX.}
    \label{tab:the efficiency of the attack}
    \centering

    {\textnormal{e}}sizebox{\textwidth}{!}{
    \begin{tabular}{ c c c c c c c c c c}
    \toprule
    \toprule

	Dataset & Model & \# of Models & ${\epsilon}ilon$ & Objective &unsound \texttt{CRA}(\%)  & \texttt{ERA}(\%) & Batch Size & Mem./Batch (MB) & Time/Batch (Min) \\
    \midrule
	MNIST & Small & 7 & 0.3 ($\ell_\infty$) & dual networks & 65.41 & 4.93 & 32 & 12565 & 4.34 \\
	MNIST & Small & 7 & 0.3 ($\ell_\infty$) & our surrogates & 65.41 & 7.67 & 32 & 4548 & 0.06\\
    \midrule
	CIFAR10 & Small & 5 & 2/255 ($\ell_\infty$) & dual networks & 28.32 & 23.79 & 32 & 10124 & 2.43 \\
	CIFAR10 & Small &5 & 2/255 ($\ell_\infty$) & our surrogates & 28.32  &22.92 & 32 & 4898 & 0.06\\
    \bottomrule\\
    \end{tabular}}
\end{table}

\section{A Query-Access, Soundness-Preserving Ensembler}
\label{sec:defense}

We present a query-access, soundness-preserving ensembler based on weighted voting in this section.
Voting is a natural choice for the design of a query-access ensembler but ensuring that the ensembler is soundness-preserving can be subtle.
Section~{\textnormal{e}}f{sec:voting_ensemble} defines our ensembler and proves that it is soundness-preserving.

In Section~{\textnormal{e}}f{sec:thought}, we present a thought experiment demonstrating that it is possible for a voting ensemble to significantly improve upon the $\texttt{CRA}$ of its constituent models.
Appendix~{\textnormal{e}}f{sec:learn_weights} describes our algorithm for learning the weights to be used in weighted voting, and Appendix~{\textnormal{e}}f{sec:more_eval} presents initial empirical results with the voting ensemble.
Our results show that improving the $\texttt{CRA}$ via a voting ensemble can be difficult on realistic datasets since it requires the ensemble to demonstrate a suitable balance between diversity and similarity of its constituents, but we believe that this is a fruitful direction for future research.

\subsection{Weighted Voting Ensemble}
\label{sec:voting_ensemble}

Voting ensembles run a vote amongst their constituent classifiers to make a prediction. 
In the simplest case, each constituent has a single vote that gets assigned to their predicted label. The label with the maximum number of votes is chosen as the ensemble's prediction. 
More generally, weighted voting allows a single constituent to be allocated more than one vote. The decimal number of votes allocated to each constituent is referred to as its \tilde{p}h{weight}. 
For simplicity, we assume that weights of the constituents in an ensemble are normalized so that they sum up to 1. 
We use weighted voting to not only choose the ensemble's prediction but to also decide its certification outcome. The interaction between voting and certification is subtle and needs careful design to ensure that the certification procedure is sound.

\paragraph{Extra Notations.} 

Let $v_x^w(j, c)$ denote the total number of votes allocated to certifiable classifiers, ${\tt cert}\xspaceify{F}^\id{i}$, in the ensemble that output $(j, c)$.
More formally, for an input $x$, label $j \in \mathcal{Y}$, certification outcome $c \in \{0,1\}$,weight $w \in [0,1]^N$, and a set of constituent certifiable classifiers, ${\tt cert}\xspaceify{F}^\id{0}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1}$,
let $v_x^w(j, c) := \sum_{i = 0}^{N-1} w_i * \mathds{1}[{\tt cert}\xspaceify{F}^\id{i}(x) = (j, c)]$.

We find it useful to use $v_x^w(*, c)$ to denote the number of votes for any class with certificate, $c$; i.e., $v_x^w(*, c) = \sum_{j\in\mathcal{Y}} v_x^w(j, x)$.
Likewise, we will use $v_x^w(j)$ to denote the number of votes for class $j$ regardless of certificate; i.e., $v_x^w(j) = v_x^w(j, 0) + v_x^w(j, 1)$. 

\begin{definition}[Weighted Voting Ensembler]\label{def:voting_ensembler}
    Let ${\tt cert}\xspaceify{F}^\id{1}, ..., {\tt cert}\xspaceify{F}^\id{N}$ be $N$ certifiable classifiers. 
    A weighted voting ensembler, $\mathcal{E}_V^w: \mathbb{{\tt cert}\xspaceify{F}}^N {\textnormal{i}}ghtarrow \mathbb{{\tt cert}\xspaceify{F}}$ is defined as follows
    $$
	{\tt cert}\xspaceify{F}(x) := \mathcal{E}_V^w({\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1})(x) :=
	\big(\lab{{\tt cert}\xspaceify{F}}(x), \cer{{\tt cert}\xspaceify{F}}(x)\big), \quad	\lab{{\tt cert}\xspaceify{F}}(x) := \argmax_j\Big\{v_x^w(j)\Big\}\footnote{In case of a tie, we assume that the label corresponding to the logit with the lowest index is returned.}
    $$
    $$ \text{where  }
	\cer{{\tt cert}\xspaceify{F}}(x) := \begin{cases}
		1 & \text{if $\forall j \neq \lab{{\tt cert}\xspaceify{F}}(x)$ ~.~ $v_x^w(\lab{{\tt cert}\xspaceify{F}}(x), 1) > v_x^w(*, 0) + v_x^w(j, 1)$} \\
    0 & \text{otherwise}
    \end{cases}
    $$
\end{definition}

The prediction of the weighted voting ensemble is the label receiving the maximum number of votes regardless of the certificate.
However, for the certification outcome, the ensemble has to consider the certificates of the constituent models. 
The ensemble should be certified robust only if its prediction outcome, i.e., the label receiving the maximum number of votes (regardless of the certificate), can be guaranteed to not change in an ${\epsilon}ilon$-ball.
The condition under which $\cer{{\tt cert}\xspaceify{F}}(x) = 1$ ensures this is the case, and allows us to prove that weighted voting ensemblers are soundness-preserving (Theorem~{\textnormal{e}}f{thm:voting_sound}).
A key observation underlying the condition is that only constituent classifiers that are not certified robust at the current input can change their predicted label in the ${\epsilon}ilon$-ball, and, in the worst case, transfer all their votes ($v_x^w(*, 0)$) to the label with the second highest number of votes at $x$. We believe that our proof of soundness-preservation is of independent interest.
We also note that weighted-voting ensemblers are query-access (formal proofs in Appendix~{\textnormal{e}}f{sec:proofs}).

\begin{theorem}
\label{thm:voting_sound}
The weighted voting ensembler $\mathcal{E}_V^w$ is soundness-preserving.
\end{theorem}

\begin{definition}[Uniform Voting Ensembler]\label{def:unif_voting_ensembler}
    Let ${\tt cert}\xspaceify{F}^\id{0}, ..., {\tt cert}\xspaceify{F}^\id{N-1}$ be $N$ certifiable classifiers. 
	The uniform voting ensembler, $\mathcal{E}_U: \mathbb{{\tt cert}\xspaceify{F}}^N {\textnormal{i}}ghtarrow \mathbb{{\tt cert}\xspaceify{F}}$ is a weighted voting ensembler that assigns equal weights to each classifier, i.e. $\mathcal{E}_U = \mathcal{E}_V^w$ where $\forall i \in \{0,\ldots,N-1\}. w_i = 1/N$.
\end{definition}

\subsection{Effectiveness of Voting: A Thought Experiment}
\label{sec:thought}

Voting ensembles require the constituents to strike the right balance between diversity and similarity to be effective.
In other words, while the constituents should be accurate and robust in different regions of the input space (diversity), these regions should also have some overlap (similarity).
We conduct a thought experiment using a simple hypothetical example (Example.~{\textnormal{e}}f{ex:voting_improve}) where such a balance is struck.
The existence of this example provides evidence and hope that voting ensembles can improve the $\texttt{CRA}$.
We present the example informally here. The detailed, rigorous argument is in Appendix~{\textnormal{e}}f{sec:proofs}.

\begin{example}  
\label{ex:voting_improve}

Assume that we have a uniform voting ensemble ${\tt cert}\xspaceify{F}$ with three constituent classifiers ${\tt cert}\xspaceify{F}^\id{0}$, ${\tt cert}\xspaceify{F}^\id{1}$, and ${\tt cert}\xspaceify{F}^\id{2}$. 
Assume that on a given dataset $S_k$ with 100 samples, each of the constituent classifiers has $\texttt{CRA}$ equal to 0.5.
	Let's say that the samples in $S_k$ are ordered such that ${\tt cert}\xspaceify{F}^\id{0}$ is accurate and robust on the first 50 samples (i.e., samples 0-49),
${\tt cert}\xspaceify{F}^\id{1}$ is accurate and robust on samples 25-74, and ${\tt cert}\xspaceify{F}^\id{2}$ on samples 0-24 and 50-74.
Then, for each of the first 75 samples, two out of three constituents in the ensemble are accurate and robust. 
	Therefore, by Def.~{\textnormal{e}}f{def:voting_ensembler}, the ensemble ${\tt cert}\xspaceify{F}$ is accurate and robust on samples 0-74, and has $\texttt{CRA}$ equal to 0.75.
\end{example}

\section{Related Work}
\label{sec:related}

Ensembling is a well-known approach for improving the accuracy of models as long as the constituent models are suitably diverse \citep{dietterich2000}. 

In recent years, with the growing focus on \tilde{p}h{robust accuracy} as a metric of model quality, a number of ensembling techniques have been proposed for improving this metric.
Depending on whether an ensemble is query-access or not (i.e., does not or does require access to the internal details of the constituent models for prediction and certification), it can be classified as a \tilde{p}h{white-box} or a \tilde{p}h{black-box} ensemble. The modularity of black-box ensembles is attractive as the constituent classifiers can each be from a different model family (i.e., neural networks, decision trees, support vector machines, etc.) and each use a different mechanism for robustness certification. 
The constituents of white-box ensembles, on the other hand, tend to be from the same model family but this provides the benefit of tuning the ensembling strategy to the model family being used. 

\textbf{White-box ensembles.} 

Several works \citep{yang2022on,zhang2019enhancing,liu2020enhancing} present certifiable ensembles where the ensemble logits are calculated by averaging the corresponding logits of the constituent classifiers. 
Needing access to the logits of the constituent classifiers, and not just their predictions, is one aspect that makes these ensembles white-box. 
More importantly, the approaches used by these ensembles for local robustness certification are also in violation of our definition of query-access ensembles (Def.~{\textnormal{e}}f{def:qa_ensembler}). For instance, randomized smoothing~\citep{cohen19} is used in
\citep{yang2022on,liu2020enhancing} to certify the ensemble, which requires evaluating the constituent models on a large number of inputs for each prediction, and not just one input. 

Other approaches \citep{zhang2019enhancing} use interval bound propagation (IBP)~\citep{gowal2018effectiveness,zhang18efficient} to certify the ensemble. Calculating the interval bounds requires access to the architecture and weights of each of the constituent models, violating the requirements of a query-access ensemble.
A number of white-box ensembling techniques \citep{pang2019improving, yang2020dverge, kariyappa2019improving, Sen2020EMPIR, pmlr-v162-zhang22aj} only aim to improve \tilde{p}h{empirical} robust accuracy, i.e., these ensembles do not provide a robustness certificate. 
As before, the ensemble logits are calculated by averaging the corresponding logits of the constituent models. 
These approaches differ from each other in the training interventions used to promote diversity in the constituent models.

\textbf{Black-box ensembles.}

Cascading ensembles \citep{wong2018scaling, blum2022boosting} are the most popular example of certifiably robust black-box ensembles. 
While \citet{wong2018scaling} empirically evaluate their cascading ensemble, the results of \citet{blum2022boosting} are purely theoretical. However, as we show in this work, the certification mechanism used by cascading ensembles is unsound.
\citet{cheng2020voting, Sen2020EMPIR} present a black-box voting ensemble but, unlike our voting ensemble, their ensemble does not provide robustness certificates. Nevertheless, they are able to show improvements in the empirical robust accuracy with the voting ensemble.

\section{Conclusion}
\label{sec:conclusion}
In this paper, we showed that the local robustness certification mechanism used by cascading ensembles is unsound.

As a consequence, 
existing empirical results that report the certified robust accuracies (\texttt{CRA}) of cascading ensembles are not valid.
Guided by our theoretical results, we designed an attack algorithm against cascading ensembles and demonstrated that their unsoundness can be easily exploited in practice. In fact, the performance of the ensembles is markedly worse than their single best constituent model.
Finally, we presented an alternate black-box ensembling mechanism based on weighted voting that we prove to be sound, and, via a thought experiment, showed that voting ensembles can significantly improve the $\texttt{CRA}$ if the constituent models have the right balance between diversity and similarity.

\section*{Ethics Statement}
\label{sec:ethics}
Our work sheds light on existing vulnerabilities in state-of-the-art certifiably robust neural classifiers.
The presented attacks can be used by malicious entities to adversarially attack deployed cascading ensembles of certifiably robust models. 
However, by putting this knowledge out in the public domain and making practitioners aware of the existence of the problem, we hope that precautions can be taken to protect existing systems.
Moreover, it highlights the need to harden future systems against such attacks.

\section*{Reproducibility Statement}
\label{sec:repro} 

To examine our theoretical results, the proof of Theorem~{\textnormal{e}}f{thm:cascading_sound} directly follows the body of the theorem in Section~{\textnormal{e}}f{sec:cascade-unsoundness} while the proof of Theorem~{\textnormal{e}}f{thm:voting_sound} is delayed to Appendix~{\textnormal{e}}f{sec:proofs} and~{\textnormal{e}}f{sec:permutation_ensembler}, together with the proofs of other theorems that only appear in the appendix, i.e. Theorem~{\textnormal{e}}f{thm:cascading_qa}, ~{\textnormal{e}}f{thm:voting_qa} (Appendix~{\textnormal{e}}f{sec:proofs}) and Theorem~{\textnormal{e}}f{thm:permutation} (Appendix~{\textnormal{e}}f{sec:permutation_ensembler}). All the datasets used in our work are publicly available with links in their corresponding reference.  Our experimental code is uploaded in the supplementary material with a detailed README file and weights of models to reproduce the results in Table~{\textnormal{e}}f{tab:ensemble_attack}, {\textnormal{e}}f{tab:the efficiency of the attack},~{\textnormal{e}}f{tab:l_inf_ensembles},~{\textnormal{e}}f{tab:l_2_ensembles}, ~{\textnormal{e}}f{tab:l_inf_new}, and~{\textnormal{e}}f{tab:l_2_new}. Moreover, hyper-parameters used in these table are also documented in Appendix~{\textnormal{e}}f{sec:hparams of tabel 1} and~{\textnormal{e}}f{sec:learn_weights}. The hardware information used in all experiments is reported in Section~{\textnormal{e}}f{sec:eval}.

\marginpar{NEW}page
\appendix

\section{Proofs}
\label{sec:proofs}

\noindent
\textbf{Theorem~{\textnormal{e}}f{thm:voting_sound}.}
\textit{ The weighted voting ensembler $\mathcal{E}_V^w$ is soundness-preserving.}

\begin{proof}
Let ${\tt cert}\xspaceify{F}^\id{0}, ..., {\tt cert}\xspaceify{F}^\id{N-1}$ be $N$ certifiable classifiers, which we assume are sound.
Let ${\tt cert}\xspaceify{F} := \mathcal{E}_V^w({\tt cert}\xspaceify{F}^\id{0}, ..., {\tt cert}\xspaceify{F}^\id{N-1})$; i.e., ${\tt cert}\xspaceify{F}$ is given by Definition~{\textnormal{e}}f{def:voting_ensembler}.

	Assume for the sake of contradiction $\exists x, x'$ s.t. $||x-x'|| \leq {\epsilon}ilon$, ${\tt cert}\xspaceify{F}(x) = (j_1, 1)$, and $\lab{{\tt cert}\xspaceify{F}}(x') = j_2$ where $j_2 \neq j_1$.

Since ${\tt cert}\xspaceify{F}(x) = (j_1, 1)$, by Definition~{\textnormal{e}}f{def:voting_ensembler}., $\forall j \neq j_1$, $v_x^w(j_1, 1) > v_x^w(*, 0) + v_x^w(j, 1)$, and thus, in particular, Equation~{\textnormal{e}}f{eq:soundness_proof:ineq_1} holds.
\begin{equation}
\label{eq:soundness_proof:ineq_1}
v_x^w(j_1, 1) > v_x^w(*, 0) + v_x^w(j_2, 1)
\end{equation}

Consider the votes on $x'$. 
The models that contribute to $v_x^w(j_1, 1)$ are all locally robust\footnote{The models are known to be locally robust because they are \tilde{p}h{sound} and their output matches $(*, 1)$.} at $x$, so each of these models must output the label $j_1$ on $x'$, which is at distance no greater than ${\epsilon}ilon$ from $x$; thus Equation~{\textnormal{e}}f{eq:soundness_proof:ineq_2} holds.
\begin{equation}
\label{eq:soundness_proof:ineq_2}
v_{x'}^w(j_1) \geq v_x^w(j_1, 1)
\end{equation}

Conversely, only points that are non-robust at $x$ can change labels on $x'$, thus we obtain Equation~{\textnormal{e}}f{eq:soundness_proof:ineq_3}.
\begin{equation}
\label{eq:soundness_proof:ineq_3}
v_{x'}^w(j_2) \leq v_x^w(*,0) + v_x^w(j_2, 1)
\end{equation}

Putting things together we have
\begin{align*}
v_{x'}^w(j_1) &\geq v_x^w(j_1, 1) &\text{by ({\textnormal{e}}f{eq:soundness_proof:ineq_2})} \\
            &> v_x^w(*,0) + v_x^w(j_2, 1) &\text{by ({\textnormal{e}}f{eq:soundness_proof:ineq_1})} \\
            &\geq v_{x'}^w(j_2) &\text{by ({\textnormal{e}}f{eq:soundness_proof:ineq_3})}
\end{align*}

	Thus, since $v_{x'}^w(j_1) > v_{x'}^w(j_2)$, $\lab{{\tt cert}\xspaceify{F}}(x')$ cannot be $j_2$ \lightning.
\end{proof}

\noindent
\textbf{Example~{\textnormal{e}}f{ex:voting_improve}.}

{\itshape
We want to show that,
	$\exists {\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1} \in \mathbb{{\tt cert}\xspaceify{F}}, w \in [0,1]^N$ such that for ${\tt cert}\xspaceify{F} := \mathcal{E}_C^w({\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1}),$

	$$\exists S_k \subseteq \mathbb{R}^d \times \mathcal{Y}.~\forall i \in \{0,\ldots,N-1\}.~\texttt{CRA}({\tt cert}\xspaceify{F},S_k) > \texttt{CRA}({\tt cert}\xspaceify{F}^\id{i},S_k)$$

Consider a weighted voting ensemble ${\tt cert}\xspaceify{F}$ constituted of certifiable classifiers ${\tt cert}\xspaceify{F}^\id{0}$, ${\tt cert}\xspaceify{F}^\id{1}$, and 
	${\tt cert}\xspaceify{F}^\id{2}$ with weights $w = (\frac{1}{3},\frac{1}{3},\frac{1}{3})$, i.e., ${\tt cert}\xspaceify{F}$ is a uniform voting ensemble.

Suppose $k=100$, i.e., $S_k$ is a dataset with 100 samples. Moreover, lets say that $\texttt{CRA}({\tt cert}\xspaceify{F}^\id{0},S_k) = \texttt{CRA}({\tt cert}\xspaceify{F}^\id{1},S_k) = \texttt{CRA}({\tt cert}\xspaceify{F}^\id{2},S_k) = 0.5$.
	Also, suppose that the samples in $S_k$ are arranged in a fixed sequence $S_k = (x_0,y_0), \ldots, (x_{k-1},y_{k-1})$ such that,
	\begin{align}
		\forall i \in [0,49].~{\tt cert}\xspaceify{F}^\id{0}(x_i) = (y_i,1) \label{eq:vot_im1}\\
		\forall i \in [25,74].~{\tt cert}\xspaceify{F}^\id{1}(x_i) = (y_i,1) \label{eq:vot_im2}\\
		\forall i \in [0,24] \cup [50,74].~{\tt cert}\xspaceify{F}^\id{2}(x_i) = (y_i,1) \label{eq:vot_im3}
	\end{align}
	where $[i,j]$ is the set of integers from $i$ to $j$, $i$ and $j$ included. 
	{\textnormal{e}}f{eq:vot_im1}, {\textnormal{e}}f{eq:vot_im2}, and {\textnormal{e}}f{eq:vot_im3} are consistent with the fact that certified robust accuracy of each model is 0.5.
	
	From {\textnormal{e}}f{eq:vot_im1}, {\textnormal{e}}f{eq:vot_im2}, {\textnormal{e}}f{eq:vot_im3}, and Definition~{\textnormal{e}}f{def:voting_ensembler},
	\begin{align}	
		\forall i \in [0,74].~\lab{{\tt cert}\xspaceify{F}}(x_i) = \argmax_j\Big\{v_{x_i}^w(j)\Big\} = y_i \label{eq:vot_im4}\\
		\forall i \in [0,74].~\forall j \neq y_i ~.~ v_{x_i}^w(y_i, 1) > v_{x_i}^w(*, 0) + v_{x_i}^w(j, 1) \label{eq:vot_im5}
	\end{align}

	From {\textnormal{e}}f{eq:vot_im5} and Definition~{\textnormal{e}}f{def:voting_ensembler},
	\begin{align}
		\forall i \in [0,74].  \cer{{\tt cert}\xspaceify{F}}(x_i) = 1 \label{eq:vot_im6}
	\end{align}

	From {\textnormal{e}}f{eq:vot_im4}, {\textnormal{e}}f{eq:vot_im6}, and Definition~{\textnormal{e}}f{def:cra},
	\begin{align}
		\texttt{CRA}({\tt cert}\xspaceify{F},S_k) = 0.75 \label{eq:vot_im7}
	\end{align}
}

\begin{theorem}
\label{thm:cascading_qa}
The cascading ensembler $\mathcal{E}_C$ is query-access.
\end{theorem}
\begin{proof}
	Let ${\tt cert}\xspaceify{F} := \mathcal{E}_C({\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1})$.
	Let $g^\id{0}, g^\id{1}, \ldots, g^\id{N-1} \in \mathcal{Y} \times \{0, 1\}$. We use $g_2^\id{j}$ to refer to the second element in the pair $g^\id{j}$.
	Define $G$ as follows,
	\begin{align*}
	    G(g^\id{0}, g^\id{1}, \ldots, g^\id{N-1}) := 
        \begin{cases} 
		g^\id{j} & \text{if } \exists j \leq N-1.~\texttt{c}(j)=1 \\
		g^\id{{N-1}} & \text{otherwise}
        \end{cases}
        \end{align*}
	where $\texttt{c}(j) := 1 \text{ if } (g_2^\id{j} = 1) \wedge (\forall i < j, g_2^\id{i} = 0)$ and 0 otherwise.

	Then, by Def.~{\textnormal{e}}f{def:cascading_ensembler}, ${\tt cert}\xspaceify{F}(x) = G({\tt cert}\xspaceify{F}^\id{0}(x), {\tt cert}\xspaceify{F}^\id{1}(x), \ldots, {\tt cert}\xspaceify{F}^\id{N-1}(x))$.
	Then, by Def.~{\textnormal{e}}f{def:qa_ensembler}, cascading ensembler is query-access.
\end{proof}

\begin{theorem}
\label{thm:voting_qa}
The weighted voting ensembler $\mathcal{E}_V^w$ is query-access.
\end{theorem}
\begin{proof}
	Let ${\tt cert}\xspaceify{F} := \mathcal{E}_V^w({\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1})$.
	Let $g^\id{0}, g^\id{1}, \ldots, g^\id{N-1} \in \mathcal{Y} \times \{0, 1\}$. We use $\bar{g}$ to refer to the set $\{g^\id{0}, g^\id{1}, \ldots, g^\id{N-1}\}$. 
	Define $G$ as follows,
    $$
	 G(g^\id{0}, g^\id{1}, \ldots, g^\id{N-1}) := 
	\big(G_1(g^\id{0}, g^\id{1}, \ldots, g^\id{N-1}), G_2(g^\id{0}, g^\id{1}, \ldots, g^\id{N-1}))
    $$
	where
    $$
	\hat{j} = G_1(g^\id{0}, g^\id{1}, \ldots, g^\id{N-1}) := \argmax_j\Big\{v_{\bar{g}}^w(j,*)\Big\},
    $$
    $$
	G_2(g^\id{0}, g^\id{1}, \ldots, g^\id{N-1}) := \begin{cases}
		1 & \text{if $\forall j \neq \hat{j}$ ~.~ $v_{\bar{g}}^w(\hat{j}, 1) > v_{\bar{g}}^w(*, 0) + v_{\bar{g}}^w(j, 1)$} \\
    0 & \text{otherwise}
    \end{cases}
    $$
	and 
    $$
	v_{\bar{g}}^w(j, c) = \sum_{i = 0}^{N-1} w_i * \mathds{1}\left[g^\id{i} = (j, c){\textnormal{i}}ght]
    $$
	Then, by Def.~{\textnormal{e}}f{def:voting_ensembler}, ${\tt cert}\xspaceify{F}(x) = G({\tt cert}\xspaceify{F}^\id{0}(x), {\tt cert}\xspaceify{F}^\id{1}(x), \ldots, {\tt cert}\xspaceify{F}^\id{N-1}(x))$.
	Then, by Def.~{\textnormal{e}}f{def:qa_ensembler}, weighted voting ensembler is query-access.
\end{proof}

\section{Hyper-parameters of Table~{\textnormal{e}}f{tab:ensemble_attack}}\label{sec:hparams of tabel 1}
In Table~{\textnormal{e}}f{tab:attack_hparams}, we report hyper-parameters used to run CasA to reach the statistics reported in Table~{\textnormal{e}}f{tab:ensemble_attack}. Notice that if a normalization is `$\mu=$[0.485, 0.456, 0.406], $\sigma=$0.225', we divide the ${\epsilon}ilon$ and step size by $\sigma$ during the experiment. We use SGD as the optimizer for all experiments. 

\begin{table}[!t]
    \caption{Hyper-parameters Used for CasA in Table~{\textnormal{e}}f{tab:ensemble_attack}}
    \label{tab:attack_hparams}
    \centering
    {\textnormal{e}}sizebox{0.8\textwidth}{!}{
    \begin{tabular}{ c c c  c c c}
    \toprule
    \toprule
    Dataset & Norm & ${\epsilon}ilon$ & Normalization & Max Steps & Step Size  \\
    \midrule
	MNIST & $\ell_\infty$ & 0.1 & [0,1] & 100 & 0.004 \\
	MNIST & $\ell_\infty$ & 0.3 & [0,1] & 100 & 0.012 \\
	MNIST & $\ell_2$ & 1.58 & [0,1] & 100 & 0.03 \\
    \midrule
	CIFAR10 & $\ell_\infty$ & 2/255 & $\mu=$[0.485, 0.456, 0.406], $\sigma=$0.225 & 100 & 0.0003 \\
	CIFAR10 & $\ell_\infty$ & 8/255 & $\mu=$[0.485, 0.456, 0.406], $\sigma=$0.225 & 100 & 0.00124 \\
	CIFAR10 & $\ell_2$ & 36/255 & $\mu=$[0.485, 0.456, 0.406], $\sigma=$0.225 & 100 & 0.0003 \\
    \bottomrule\\
    \end{tabular}}
\end{table}

\section{Weighted Voting Ensemble: Learning Weights}
\label{sec:learn_weights}

The weights $w$ in $\mathcal{E}_V^w$ determines the importance of each constituent classifier in the ensemble. 

Given a set of $k$ labeled inputs, $S_k$ (e.g. the training set), we would like to learn the optimal weights $w$ that maximize the ensembler's $\texttt{CRA}$ (Def.~{\textnormal{e}}f{def:cra}) over $S_k$. When $S_k$ resembles the true distribution of the test points, the learned $w$ is expected to be close to the optimal weights that maximizes the $\texttt{CRA}$ of the test set. Weight optimization over $S_k$ naturally takes the following form.
\begin{align}
	\max_{w \in [0, 1]^N} ~~\frac{1}{k}\sum_{(x_i,y_i) \in S_k}\mathds{1}\left[\mathcal{E}_V^w({\tt cert}\xspaceify{F}^\id{0}, ..., {\tt cert}\xspaceify{F}^\id{N-1})(x_i)=(y_i,1) {\textnormal{i}}ght]\label{eq:learn-weigths-01-loss}
\end{align}
For the indicator to output 1, it is required that the margin of votes be greater than 0, i.e. $\Delta^w_{x_i}(y_i) := v^w_{x_i}(y_i, 1) - v^w_{x_i}(*, 0) -\max_{j \neq y_i} \{v^w_{x_i}(j, 1)\} >0$. Namely, the votes for the class $y_i$, i.e. $v^w_{x_i}(y_i, 1)$, must be greater than the votes for all other classes i.e. $\max_{j \neq y_i} \{v^w_{x_i}(j, 1)\}$ plus the votes for non-robust predictions $v^w_{x_i}(*, 0)$ as discussed in Def.~{\textnormal{e}}f{def:voting_ensembler}. 

Eq.({\textnormal{e}}f{eq:learn-weigths-01-loss}) then becomes:
\begin{align}
    \max_{w \in [0, 1]^N} ~~\frac{1}{k}\sum_{(x_i,y_i) \in S_k}\mathds{1}\left[\Delta^w_{x_i}(y_i) >0 {\textnormal{i}}ght] \label{eq:learn-weigths-hard-margin}
\end{align}

The indicator function is not differentiable so we replace it with a differentiable and monotonically increasing function $s$, which leads to Eq.~{\textnormal{e}}f{eq:learn-weigths-soft-margin}.
\begin{align}
    \max_{w \in [0, 1]^N} ~~\frac{1}{k}\sum_{(x_i,y_i) \in S_k}s(\Delta^w_{x_i}(y_i))  \label{eq:learn-weigths-soft-margin}
\end{align}

In this paper, we choose $s$ to be the sigmoid function $\sigma_{t}$ where $t$ is the temperature only for negative inputs, i.e., $\sigma_{t}(x) := \sigma(x) \text{ if } x > 0 \text{ and } \sigma(x/t) \text{ otherwise}$, where $\sigma$ is the standard sigmoid function. 
Sigmoid is non-negative so margins with opposite signs do not cancel, and it also avoids biasing training towards producing larger margins on a small number of points.
Indeed, vanishing gradients are useful on points around large positive margins, so the temperature is only applied on negative inputs.
This leads us to Eq.~{\textnormal{e}}f{eq:learn-weigths-sigmoid-margin}, the optimization objective we solve for optimal weights $w^*$.
\begin{align}
    w^* = \argmax_{w \in [0, 1]^N} ~~\frac{1}{k}\sum_{(x_i,y_i) \in S_k}\sigma_t(\Delta^w_{x_i}(y_i))\label{eq:learn-weigths-sigmoid-margin}
\end{align}

\section{Weighted Voting Ensemble: Empirical Results}
\label{sec:more_eval}

The goal of these experiments is to evaluate the efficacy of our sound voting ensemble.
For our experiments, we use the pre-trained ensemble constituent models made available by \citet{wong2018scaling} to construct three kinds of ensembles, namely, cascading ensembles, uniform voting ensembles, and weighted voting ensembles.
The weights for the weighted voting ensemble are learned in the manner described in Appendix~{\textnormal{e}}f{sec:learn_weights}. 
We report certified robust accuracy ($\texttt{CRA}$) and standard accuracy ($\texttt{Acc}$) for each ensemble as well as for the best constituent model.
Note that all these ensembles are query-access but only the uniform voting and weighted voting ensembles are soundness-preserving. 
Consequently, the $\texttt{CRA}$ reported for the cascading ensemble grossly overestimates the actual $\texttt{CRA}$ as demonstrated by our attack results.

We always set the temperature to 1e5 and learning rate to 1e-2 when learning the weights as described in Appendix~{\textnormal{e}}f{sec:learn_weights}.

\begin{table}[!t]
    \caption{Results on models pre-trained by \citet{wong2018scaling} for $\ell_\infty$ robustness.}
    \label{tab:l_inf_ensembles}
    \centering
    {\textnormal{e}}sizebox{\textwidth}{!}{
    \begin{tabular}{ c c c  c c | c c | c c | c c }
    \toprule
    \toprule
    {} & {} & {} & \multicolumn{2}{c}{Single Model} & \multicolumn{2}{|c|}{Cascading} & \multicolumn{2}{|c}{Uniform Voting} & \multicolumn{2}{|c}{Weighted Voting} \\
	    Dataset & Model & ${\epsilon}ilon$ & \texttt{CRA}(\%) & \texttt{Acc}(\%) & \texttt{CRA}(\%) & \texttt{Acc}(\%) & \texttt{CRA}(\%) & \texttt{Acc}(\%) & \texttt{CRA}(\%) & \texttt{Acc}(\%) \\
    \midrule
	    MNIST & Small, Exact
	    & 0.1 & 95.54 & 98.96 & 96.33 & 96.62 & 0.01 & 61.68 & 95.54 & 61.68 \\
    MNIST & Small & 0.1 & 94.94 & 98.79 & 96.07 & 96.24 & 9.29 & 65.85 & 94.94 & 98.79 \\
    MNIST & Large & 0.1 & 95.55 & 98.81 & 96.27 & 96.42 & 10.12 & 63.89 & 95.55 & 98.81 \\
    \midrule
    MNIST & Small & 0.3 & 56.21 & 85.23 & 65.41 & 65.80 & 11.48 & 56.46 & 56.21 & 85.23 \\
    MNIST & Large & 0.3 & 58.02 & 88.84 & 65.50 & 65.50 & 26.95 & 65.97 & 58.02 & 88.84 \\
    \midrule
    CIFAR10 & Small & 2/255 & 46.43 & 60.86 & 56.65 & 56.65 & 18.58 & 40.88 & 46.43 & 60.86 \\
    CIFAR10 & Large & 2/255 & 52.65 & 67.70 & 64.88 & 65.14 & 18.07 & 48.92 & 52.65 & 67.70 \\
    \midrule
    CIFAR10 & Small & 8/255 & 20.58 & 27.60 & 28.32 & 28.32 & 10.78 & 24.11 & 19.00 & 23.78 \\
    CIFAR10 & Large & 8/255 & 16.04 & 19.01 & 20.83 & 20.83 & 5.18 & 21.01 & 16.04 & 19.01 \\
    \bottomrule\\
    \end{tabular}}
\end{table}

\begin{table}[!t]
    \caption{Results on models pre-trained by \citet{wong2018scaling} for $\ell_2$ robustness.}
    \label{tab:l_2_ensembles}
    \centering
    {\textnormal{e}}sizebox{\textwidth}{!}{
    \begin{tabular}{ c c c  c c | c c | c c | c c }
    \toprule
    \toprule
    {} & {} & {} & \multicolumn{2}{c|}{Single Model} & \multicolumn{2}{|c|}{Cascading} & \multicolumn{2}{|c}{Uniform Voting} & \multicolumn{2}{|c}{Weighted Voting}\\
	    Dataset & Model & ${\epsilon}ilon$ & \texttt{CRA}(\%) & \texttt{Acc}(\%)  & \texttt{CRA}(\%)  & \texttt{Acc}(\%)  & \texttt{CRA}(\%)  & \texttt{Acc}(\%)  & \texttt{CRA}(\%)  & \texttt{Acc}(\%)  \\
    \midrule
    MNIST & Small, Exact & 1.58 & 43.52 & 88.14 & 75.58 & 80.43 & 06.42 & 74.25 & 43.52 & 88.14 \\
    MNIST & Small & 1.58 & 43.34 & 87.73 & 74.66 & 79.07 & 06.74 & 74.24 & 43.34 & 87.73 \\
    MNIST & Large & 1.58 & 43.96 & 88.39 & 74.50 & 74.99 & 06.35 & 65.99 & 43.96 & 88.39 \\
    \midrule
    CIFAR10 & Small & 36/255 & 46.05 & 54.39 & 49.89 & 51.37 & 11.47 & 38.74 & 46.05 & 54.39 \\
    CIFAR10 & Large & 36/255 & 50.26 & 60.14 & 58.72 & 58.76 & 10.56 & 39.74 & 50.26 & 60.14 \\
    CIFAR10 & Resnet & 36/255 & 51.65 & 60.7 & 58.65 & 58.69 & 22.74 & 46.71 & 51.65 & 60.7  \\
    \bottomrule\\
    \end{tabular}}
\end{table}

Table ~{\textnormal{e}}f{tab:l_inf_ensembles} shows the results for $\ell_\infty$ robustness. 
Each row in the table represents a specific combination of dataset (MNIST or CIFAR-10), architecture (Small or Large convolutional networks or Resnet), and ${\epsilon}ilon$ value used for local robustness certification. 

Table~{\textnormal{e}}f{tab:l_2_ensembles}  shows the results for $\ell_2$ robustness using constituent models pre-trained by \citet{wong2018scaling}. 

\textbf{Summary of Results.}
We see from Tables~{\textnormal{e}}f{tab:l_inf_ensembles} and~{\textnormal{e}}f{tab:l_2_ensembles} that while the cascading ensemble appears to improve upon the $\texttt{CRA}$ of the single best model in the ensemble, these numbers are misleading due to the unsoundness of the certification mechanism. The $\texttt{CRA}$ for the uniform voting and weighted ensembles are consistently lower than that reported by the cascading ensemble, and in many cases, significantly so. 
Uniform voting ensembles stand-out for their low $\texttt{CRA}$ but there is a simple explanation for these results. 
The constituent models are trained by \citet{wong2018scaling} in a cascading manner, i.e., later constituent models are trained on only those points that cannot be certified by the previous models. 
This strategy causes the subset of inputs labeled correct and certifiably robust by each constituent model to have minimal overlap. 

However, voting ensembles need these input subsets to strike the right balance between diversity and overlap for improving the $\texttt{CRA}$ . 

Another interesting observation is that, in most cases, the $\texttt{CRA}$ of the weighted voting ensemble and the single best constituent model are the same.
This is again a consequence of the cascaded manner in which the constituent models are trained. The first model in the cascade typically vastly outperforms the subsequent models.
Moreover, as already mentioned, the constituent models have almost no overlap in the input regions where they perform well, and their presence only ends up harming the performance of the voting ensemble. 
As a consequence, the optimal normalized weights, learned by solving the optimization problem described in Appendix~{\textnormal{e}}f{sec:learn_weights}, typically assign all the mass to the first model.
The detailed weights for each of the weighted voting ensemble are given in Tables~{\textnormal{e}}f{tab:l_inf_ensembles_weights},~{\textnormal{e}}f{tab:l_2_ensembles_weights},~{\textnormal{e}}f{tab:l_inf_new_weights}, and~{\textnormal{e}}f{tab:l_2_new_weights}.

These results suggest two takeaway messages. 
First, the cascaded strategy of \citet{wong2018scaling} for training constituent models is in conflict with the requirement that constituent models overlap in their behavior for voting ensembles to be effective.

This gives up hope that if the constituent models are suitably trained, voting ensembles can improve the $\texttt{CRA}$. We leave this exploration for future work.
Second, even if the constituent models do not show the right balance between diversity and similarity, our weight learning procedure ensures that the performance of the weighted voting ensemble is no worse than the single best constituent model. 
Ideally, we would like the weights to be equally distributed since this conveys that every constituent in the ensemble has something to contribute. 
But, in the worst case, the weights play the role of a model selection procedure, assigning zero weights to constituent models that do not contribute to the ensemble.

\textbf{Non-Sequential Training.}
We conduct another set of experiments where instead of using the constituent models pre-trained by \citet{wong2018scaling}, we train them ourselves in a non-sequential manner.
That is, each constituent model is trained on the entire train dataset, and each constituent only differs due to the randomness of initialization and of stochastic gradient descent during training.
Besides this difference, the code, architecture, hyperparameters, and data used for training are the same as that used by \citet{wong2018scaling}. 
For every combination of dataset, architecture, and ${\epsilon}ilon$ value, we train three constituent models, and use them to construct cascading, uniform voting, and weighted voting ensembles.

\begin{table}[!t]
    \caption{Results on non-sequentially trained models for $\ell_\infty$ robustness.}
    \label{tab:l_inf_new}
    \centering
    {\textnormal{e}}sizebox{\textwidth}{!}{
    \begin{tabular}{ c c c  c c | c c | c c | c c }
    \toprule
    \toprule
    {} & {} & {} & \multicolumn{2}{c}{Single Model} & \multicolumn{2}{|c|}{Cascading} & \multicolumn{2}{|c}{Uniform Voting} & \multicolumn{2}{|c}{Weighted Voting} \\
	    Dataset & Model & ${\epsilon}ilon$ & \texttt{CRA}(\%) & \texttt{Acc}(\%) & \texttt{CRA}(\%) & \texttt{Acc}(\%) & \texttt{CRA}(\%) & \texttt{Acc}(\%) & \texttt{CRA}(\%) & \texttt{Acc}(\%) \\
    \midrule
    MNIST & Small, Exact & 0.1 & 95.61 & 99.02 & 97.07 & 99.14 & 95.56 & 99.16 & 95.54 & 98.96 \\
    MNIST & Small & 0.1 & 94.94 & 98.79 & 96.25 & 98.69 & 94.46 & 98.78 & 94.94 & 98.79 \\

    \midrule
    MNIST & Small & 0.3 & 56.21 & 85.23 & 66.09 & 84.77 & 55.24 & 85.02 & 56.21 & 85.23 \\

    \midrule
    CIFAR10 & Small & 2/255 & 46.43 & 60.86 & 55.49 & 62.06 & 43.48 & 62.79 & 42.35 & 61.09 \\

    \midrule
    CIFAR10 & Small & 8/255 & 21.04 & 28.29 & 25.11 & 27.73 & 20.44 & 28.32 & 21.04 & 28.29 \\

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

\begin{table}[!t]
    \caption{Results on non-sequentially trained models for $\ell_2$ robustness.}
    \label{tab:l_2_new}
    \centering
    {\textnormal{e}}sizebox{\textwidth}{!}{
    \begin{tabular}{ c c c  c c | c c | c c | c c }
    \toprule
    \toprule
    {} & {} & {} & \multicolumn{2}{c|}{Single Model} & \multicolumn{2}{|c|}{Cascading} & \multicolumn{2}{|c}{Uniform Voting} & \multicolumn{2}{|c}{Weighted Voting}\\
	    Dataset & Model & ${\epsilon}ilon$ & \texttt{CRA}(\%) & \texttt{Acc}(\%)  & \texttt{CRA}(\%)  & \texttt{Acc}(\%)  & \texttt{CRA}(\%)  & \texttt{Acc}(\%)  & \texttt{CRA}(\%)  & \texttt{Acc}(\%)  \\
    \midrule
    MNIST & Small, Exact & 1.58 & 43.52 & 88.14 & 47.42 & 87.78 & 42.71 & 88.19 & 43.52 & 88.14 \\
    MNIST & Small & 1.58 & 43.34 & 87.73 & 47.40 & 87.50 & 42.87 & 87.99 & 43.34 & 87.73 \\

    CIFAR10 & Small & 36/255 & 46.05 & 54.39 & 52.33 & 55.88 & 37.07 & 57.40 & 42.12 & 54.65 \\

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

Table~{\textnormal{e}}f{tab:l_inf_new} shows the results for $\ell_\infty$ robustness using non-sequentially trained constituent model ands Table~{\textnormal{e}}f{tab:l_2_new} shows the results for $\ell_2$ robustness.

We observe that, for non-sequentially trained models, the $\texttt{CRA}$ of uniform voting and weighted voting ensembles are comparable, and similar to the $\texttt{CRA}$ of the single best constituent model in the ensemble. In this case, the constituent models have too much overlap and almost no diversity. These results reaffirm our observation that voting ensembles require a balance between diversity and similarity to be effective.

\begin{table}[!t]
    \caption{Learned weights for weighted voting ensemble with models pre-trained by \citet{wong2018scaling} for $\ell_\infty$ robustness.}
    \label{tab:l_inf_ensembles_weights}
    \centering
    {\textnormal{e}}sizebox{\textwidth}{!}{
    \begin{tabular}{ c c c c | c }
    \toprule
    \toprule
	{} & {} & {} & number of & {} \\
	Dataset & Model & ${\epsilon}ilon$ & models & weights \\
    \midrule
	MNIST & Small, Exact & 0.1 & 6 & [0.996, 0.003, 0.000, 0.001, 0.000, 0.000] \\
    MNIST & Small & 0.1 & 7 & [0.996, 0.000, 0.000, 0.003, 0.000, 0.000, 0.001] \\
    MNIST & Large & 0.1 & 5 & [0.996, 0.002, 0.001, 0.000, 0.001] \\
    \midrule
    MNIST & Small & 0.3 & 3 & [0.995, 0.003, 0.002] \\
    MNIST & Large & 0.3 & 3 & [0.948, 0.008, 0.044]\\
    \midrule
    CIFAR10 & Small & 2/255  & 5 & [0.995, 0.002, 0.001, 0.001, 0.001]  \\
    CIFAR10 & Large & 2/255 & 4 & [0.994, 0.003, 0.001, 0.002]\\

    \midrule
    CIFAR10 & Small & 8/255 & 3 & [0.003, 0.995, 0.002]\\
    CIFAR10 & Large & 8/255 & 3 & [0.995, 0.002, 0.003]\\

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

\begin{table}[!t]
    \caption{Learned weights for weighted voting ensembles with models pre-trained by \citet{wong2018scaling} for $\ell_2$ robustness.}
    \label{tab:l_2_ensembles_weights}
    \centering
    {\textnormal{e}}sizebox{\textwidth}{!}{
    \begin{tabular}{ c c c c | c }
    \toprule
    \toprule
	{} & {} & {} & number of & {} \\
	Dataset & Model & ${\epsilon}ilon$ & models & weights \\
    \midrule
	MNIST & Small, Exact & 1.58 & 6 & [0.995, 0.001, 0.001, 0.000, 0.003, 0.001] \\
    MNIST & Small & 1.58 & 6 & [0.995, 0.001, 0.002, 0.001, 0.001, 0.000] \\
    MNIST & Large & 1.58 & 6 & [0.996, 0.000, 0.001, 0.002, 0.000, 0.001] \\
    \midrule
    CIFAR10 & Small & 36/255  & 2 & [0.994, 0.006] \\
    CIFAR10 & Large & 36/255 & 6 & [0.994, 0.002, 0.001, 0.001, 0.001, 0.001]\\
    CIFAR10 & Resnet & 36/255 & 4 & [0.994, 0.004, 0.001, 0.001]\\
    \bottomrule\\
    \end{tabular}}
\end{table}

\begin{table}[!t]
    \caption{Learned weights for weighted voting ensemble with non-sequentially trained models for $\ell_\infty$ robustness.}
    \label{tab:l_inf_new_weights}
    \centering

    \begin{tabular}{ c c c c | c }
    \toprule
    \toprule
	{} & {} & {} & number of & {} \\
	Dataset & Model & ${\epsilon}ilon$ & models & weights \\
    \midrule
	MNIST & Small, Exact & 0.1 & 3 & [0.710, 0.131, 0.159] \\
	MNIST & Small & 0.1 & 3 & [0.694, 0.154, 0.152] \\

    \midrule
	MNIST & Small & 0.3 & 3 & [0.908, 0.061, 0.031] \\

    \midrule
	CIFAR10 & Small & 2/255 & 3 & [0.011, 0.956, 0.0323]  \\

    \midrule
	CIFAR10 & Small & 8/255 & 3 & [0.042, 0.087, 0.871] \\

    \bottomrule\\
    \end{tabular}

\end{table}

\begin{table}[!t]
    \caption{Learned weights for weighted voting ensembles with  non-sequentially trained models for $\ell_2$ robustness.}
    \label{tab:l_2_new_weights}
    \centering

    \begin{tabular}{ c c c c | c }
    \toprule
    \toprule
	{} & {} & {} & number of & {} \\
	Dataset & Model & ${\epsilon}ilon$ & models & weights \\
    \midrule
	MNIST & Small, Exact & 1.58 & 3 & [0.695, 0.159, 0.146] \\
    MNIST & Small & 1.58 & 3 & [0.660, 0.196, 0.144] \\

    CIFAR10 & Small & 36/255  & 3 & [0.003, 0.002, 0.995] \\

    \bottomrule\\
    \end{tabular}

\end{table}

\section{An Alternate Formulation of Uniform Voting Ensembler}
\label{sec:permutation_ensembler}

\begin{definition}[Permutation-based Cascading Ensembler]\label{def:permutation_based_cascading_ensembler}
    Let ${\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1}$ be $N$ certifiable classifiers and $N$ is odd. Suppose $\Pi$ is the set of all permutations of $\{0, 1, \ldots, N-1\}$.
A permutation-based cascading ensembler $\mathcal{E}_P: \mathbb{{\tt cert}\xspaceify{F}}^N {\textnormal{i}}ghtarrow \mathbb{{\tt cert}\xspaceify{F}} $ is defined as follows
    \begin{align*}
	    \mathcal{E}_P({\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1})(x) := 
        \begin{cases} 
            	{\tt cert}\xspaceify{F}^\id{\pi_0}(x) & \text{if $\exists \pi \in \Pi$. \texttt{c2}}(\pi) = 1 \\
		(\lab{{\tt cert}\xspaceify{F}}^\id{\pi_0}(x),0) & \text{if $\not\exists \pi' \in \Pi$. \texttt{c2}}(\pi')= 1~\wedge~\exists \pi \in \Pi.~\texttt{c1}(\pi) = 1\\
		(*,0) & \text{otherwise}
        \end{cases}
        \end{align*}
    where $*$ is a random label selected from $\mathcal{Y}$\footnote{One can also return the plurality prediction of all models for the consideration of clean accuracy but the choice of $*$ will not change the relevant theorems. 

	}
	,$\pi_0$ refers to the first element of the permutation $\pi$,
        \begin{align}
            &\text{\texttt{c1}}(\pi) := \begin{cases} 
		    1 & \text{if } \exists j.~(\frac{N+1}{2} \leq j \leq N-1) \wedge (\forall i<j.~\lab{{\tt cert}\xspaceify{F}}^\id{\pi_i}(x) = \lab{{\tt cert}\xspaceify{F}}^\id{\pi_j}(x) ) \\
                0 & \text{otherwise}
            \end{cases}\\
            &\text{\texttt{c2}}(\pi) := \begin{cases} 
		    1 & \text{if } \exists j.~(\frac{N+1}{2} \leq j \leq N-1) \wedge (\forall i<j.~{\tt cert}\xspaceify{F}^\id{\pi_i}(x) = {\tt cert}\xspaceify{F}^\id{\pi_j}(x)) \wedge (\cer{{\tt cert}\xspaceify{F}}^\id{\pi_j}(x) = 1) \\
                0 & \text{otherwise}
            \end{cases}
        \end{align} and $i, j \in \{0, 1, ..., N-1\}$.

\end{definition}

\begin{theorem}\label{thm:permutation}
	The permutation-based cascading ensembler $\mathcal{E}_P$ is a soundness-preserving ensembler.

\end{theorem}

\begin{proof}
Let ${\tt cert}\xspaceify{F} := \mathcal{E}_P({\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, \ldots, {\tt cert}\xspaceify{F}^\id{N-1})$.
For ${\tt cert}\xspaceify{F}$ we want to show that,
\begin{align}
	\forall x \in \mathbb{R}^d, \cer{{\tt cert}\xspaceify{F}}(x) = 1  \Longrightarrow \lab{{\tt cert}\xspaceify{F}} \text{ is } {\epsilon}ilon\text{-locally robust at } x.
\end{align}

	W.L.O.G suppose $ \lab{{\tt cert}\xspaceify{F}}(x) = y$. If $ {\tt cert}\xspaceify{F}(x) = (y,1)$, let us assume that $\pi$ is the permutation such that $\texttt{c2}(\pi) = 1$. Let $k$ be the integer that makes \texttt{c2}$(\pi)=1$ to be true. Thus

\begin{align}
	{\tt cert}\xspaceify{F}(x) = (y,1) \Longrightarrow (\frac{N+1}{2} \leq k \leq N-1) \wedge (\forall i<k, {\tt cert}\xspaceify{F}^\id{\pi_i}(x) = {\tt cert}\xspaceify{F}^\id{\pi_{k}}(x) = (y, 1))
\end{align}

By our assumptions that ${\tt cert}\xspaceify{F}^\id{0}, {\tt cert}\xspaceify{F}^\id{1}, ..., {\tt cert}\xspaceify{F}^\id{N-1}$ are sound, which are invariant to the permutation of these models. Therefore, by Def.~{\textnormal{e}}f{def:soundness-of-F_Tilde}, $\forall i\leq k$,

\begin{align}
	{\tt cert}\xspaceify{F}^\id{\pi_i}(x) = (y,1) \Longrightarrow (\forall x'.~ ||x'-x||\leq {\epsilon}ilon \Longrightarrow \lab{{\tt cert}\xspaceify{F}}^\id{\pi_i}(x') = \lab{{\tt cert}\xspaceify{F}}^\id{\pi_i}(x) = y) \label{Eq:y}
\end{align}

Eq.~({\textnormal{e}}f{Eq:y}) implies that $\forall x' \text{ s.t. } ||x'-x||\leq {\epsilon}ilon$, the following statement is true

\begin{align}
	(\frac{N+1}{2} \leq k \leq N-1) \wedge (\forall i\leq k, \lab{{\tt cert}\xspaceify{F}}^\id{\pi_i}(x) = \lab{{\tt cert}\xspaceify{F}}^\id{\pi_k}(x') = y) \label{Eq:x_prime}
\end{align}

Plug the condition~({\textnormal{e}}f{Eq:x_prime}) into Def.~{\textnormal{e}}f{def:permutation_based_cascading_ensembler}, we find that
	$\texttt{c1}(\pi)=1$ for $x'$. Moreover, there cannot be a permutation $\pi'$ such that $\texttt{c1}(\pi')=\texttt{c2}(\pi')=1 \wedge \lab{{\tt cert}\xspaceify{F}}^\id{\pi'_0} \neq y$ since $k \geq \frac{N+1}{2}$.
	Therefore, $\lab{{\tt cert}\xspaceify{F}}(x')=\lab{{\tt cert}\xspaceify{F}}^\id{\pi_0}(x') = y$, and we arrive at the following statement,
\begin{align}
	\forall x'.~||x'-x||\leq {\epsilon}ilon \Longrightarrow \lab{{\tt cert}\xspaceify{F}}(x') = \lab{{\tt cert}\xspaceify{F}}(x) = y
\end{align} which completes the proof for the soundness of $\lab{{\tt cert}\xspaceify{F}}$ at any $x$.

\end{proof}

\end{document}