Run-Off Election: Improved Provable Defense against Data Poisoning Attacks

Certified robustness has been widely studied in the literature and prior works have considered various notions of robustness, such as label-flipping (Rosenfeld et al., 2020) and distributional robustness (Lai et al., 2016; Diakonikolas et al., 2016, 2019). Recent works have also studied the poisoning problem theoretically using a PAC learning model (Blum et al., 2021; Gao et al., 2021; Balcan et al., 2022; Hanneke et al., 2022). In this work, we focus on (pointwise) certified robustness against data poisoning and assume a general poisoning model where the adversary may insert, delete, or modify any images.

Most closely related to our work, are the DPA (Levine & Feizi, 2020) and the FA methods (Wang et al., 2022b) that use an ensemble of classifiers to obtain deterministic robustness certificates. A similar line of work (Chen et al., 2020; Jia et al., 2021) considers stochastic robustness certificates. As mentioned, we improve on these works, establishing a new state-of-the-art for (pointwise) certified robustness. Following prior work, we use certified fraction, i.e., the fraction of (test) data points that are certifiable correct, to measure robustness. A similar but slightly different notion is studied by (Chen et al., 2022) who certify the test accuracy without certifying any specific data point.

Our work is closely related to the smoothing technique of (Cohen et al., 2019). that has been extensively studied both in terms of its applications (Raghunathan et al., 2018; Singla & Feizi, 2019, 2020; Chiang et al., 2020) and known limitations (Yang et al., 2020; Kumar et al., 2020; Blum et al., 2020). The original DPA method is inspired by derandomized smoothing (Levine & Feizi, 2020). Smoothing can also be directly applied to data poisoning attacks (Weber et al., 2020), though this requires strong assumptions on the adversary.

As mentioned in the introduction, our method can be seen as a two-round election, where each model corresponds to a voter, and each class corresponds to a candidate. Given a test sample $x$, and an ensemble of $k$ models $\{f_{i}\}_{i=1}^{k}$, our election consists of the following two rounds.

• •

  Round 1. We first obtain the top two classes as measured by the number of models “voting” for each class. Formally, the setting,

  $\displaystyle N^{\text{{R1}}}_{c}:=\sum_{i}\mathds{1}\left[f_{i}(x)=c\right],$

  (1)

  we calculate the top two classes $c_{1}^{R1}:=\operatorname*{arg\,max}_{c}N^{\text{{R1}}}_{c}$ and $c_{2}^{R1}:=\operatorname*{arg\,max}_{c\neq c_{1}^{R1}}N^{\text{{R1}}}_{c}$.

• •

  Round 2. We collect the votes of each model in an election between $c_{1}^{R1}$ and $c_{2}^{R1}$. Formally, for $(c,c^{\prime})\in\{(c_{1}^{R1},c_{2}^{R1}),(c_{2}^{R1},c_{1}^{R1})\}$, we set

  $\displaystyle N^{\text{{R2}}}_{c}:=\sum_{i=1}^{k}\mathds{1}\left[f_{i}^{\text{logits}}(x,c)>f_{i}^{\text{logits}}(x,c^{\prime})\right],$

  and output $\textnormal{ROE}(D,x):=\operatorname*{arg\,max}_{c\in\{c_{1},c_{2}\}}N^{\text{{R2}}}_{c}$.

We assume that $\operatorname*{arg\,max}$ breaks ties by favoring the class with the smaller index. The formal pseudocode of ROE is provided in Algorithm 1.

Reliability of the logits layer. Our method implicitly assumes that the information in the logits layer of the models is reliable enough to be useful for prediction purposes. This may seem counter-intuitive because many of the models do not even predict one of the top-two classes. In fact, these are precisely the models that were underutilized by DPA. We note however that we only use the logits layer for a binary classification task in Round 2, which easier than multi-class classification. Furthermore, even though the logits layer information may be less reliable than the choice of the top class, it is still useful because it provides more information, making the attack problem more difficult for an adversary. As we will see in Section 4, the clean accuracy of the model may slightly decrease when using our defense, but its robustness improves significantly for larger attack budgets.

We now present two possible choices of the ensembles $\{f_{i}\}_{i=1}$. We begin by considering a disjoint partitioning scheme based on DPA and then consider a more sophisticated overlapping partitioning scheme based on FA. We denote the methods by DPA+ROE and FA+ROE, respectively.

DPA+ROE. In this method, training data is divided into several partitions and a separate base classifier $f_{i}$ is trained on each of these partitions. Formally, given a hash function $h:\mathcal{X}\to[k]$, the training set $D$ is divided into $k$ partitions $\{D_{i}\}_{i=1}^{k}$, where $D_{i}:=\{x\in D:h(x)=i\}$, and the classifiers $\{f_{i}\}_{i=1}^{k}$ are obtained by training a base classifier on these partitions, i.e., $f_{i}:=f_{D_{i}}$. For instance, when classifying images, $f_{i}$ can be a standard ResNet model trained on $D_{i}$.

FA+ROE. In this method, we use two hash functions $h_{\text{spl}}:\mathcal{D}\to[kd]$ and $h_{\text{spr}}:[kd]\to[kd]^{d}$. We first split the datasets into $[kd]$ “buckets” using $h_{\text{spl}}$. We then create $kd$ partitions by spreading these buckets, sending each bucket to all of the partitions specified by $h_{\text{spr}}$. Formally, for $i\in[kd]$, we define $D_{i}$ as $D_{i}:=\{x\in D:i\in h_{\text{spr}}(h_{\text{spl}}(x))\}.$ We then train a separate classifier $f_{i}:=f_{D_{i}}$ for each $D_{i}$. A pseudocode of training FA is shown in Algorithm 3.

Since our aggregation method is more involved than taking a simple majority vote, the adversary can affect the decision-making process in more ways. Calculating the prediction certificate thus requires a more careful argument compared to prior work. In order to present a unified argument, we introduce the concept of 1v1 and 2v1 certificates. A 1v1 certificate bounds the number of poisoned samples required for one class to beat another class while a 2v1 certificate extends this idea and bounds the number of poisoned samples required for two classes to beat another class.

We will show that as long as the 1v1 and 2v1 certificates can be calculated efficiently, we can use them to calculate a prediction certificate (Theorem 3.4). The reduction ensures that our approach is general and works for any choice of ensemble, as long as 1v1 and 2v1 certificates can be calculated. We then provide an implementation of how to calculate those certificates for DPA+ROE (Lemmas 3.5 and 3.6) and FA+ROE (Lemmas 3.7 and 3.8).

We begin by defining the notion of the gap between two classes.

We will omit the dependence of gap on $\{f_{i}\}_{i=1}^{k}$ and $x$ when it is clear from context. We say that $c$ beats $c^{\prime}$ if $\textnormal{gap}(c,c^{\prime})>0$. If the adversary wants the class $c^{\prime}$ to beat $c$, it needs to poison the training set $D$ until $\textnormal{gap}(c,c^{\prime})$ becomes non-positive. We can therefore use this notion to reason on the optimal behaviour of the adversary.

We define a 1v1 certificate as follows.

We note that if $\textnormal{gap}(D,x,c,c^{\prime})\leq 0$, then Certv1 can only be zero.

We similarly define a 2v1 certificate as follows.

Assuming these certificates can be calculated efficiently, we can obtain a prediction certificate, as we outline below. Let $c^{\textnormal{pred}}$ denote the predicted and $c^{\textnormal{sec}}$ the runner-up class. The adversary can change the model’s prediction in one of the following two ways.

1. 1.

   It can eliminate $c^{\textnormal{pred}}$ in Round 1. This means it needs to choose two classes $c_{1},c_{2}\in\mathcal{C}\backslash\{c^{\textnormal{pred}}\}$ and ensure that $c_{1}$ and $c_{2}$ both have more votes than $c^{\textnormal{pred}}$ in Round 1. By definition, this requires as least $\texttt{Certv2}{}{}(c^{\textnormal{pred}},c_{1},c_{2})$. Since the adversary can choose $c_{1},c_{2}$, we can lower bound the number of poisoned samples it needs with

   $\displaystyle\texttt{Cert}^{\textnormal{R1}}:=\min_{c_{1},c_{2}\in\mathcal{C}\backslash\{c^{\textnormal{pred}}\}}\texttt{Certv2}{}{}(c^{\textnormal{pred}},c_{1},c_{2}).$

2. 2.

   It can eliminate $c^{\textnormal{pred}}$ in Round 2. Letting $c$ denote the class that is ultimately chosen, this requires that $c$ makes it to Round 2 and beats $c^{\textnormal{pred}}$ in Round 2. For $c$ to make it to Round 2, the adversary needs to ensure that it beats either $c^{\textnormal{pred}}$ or $c^{\textnormal{sec}}$ in Round 1. Given the previous case, we can assume that $c^{\textnormal{pred}}$ makes it to Round 2, which means $c$ needs to beat $c^{\textnormal{sec}}$. The number of poisoned samples required for this is at least

   $\displaystyle\texttt{Cert}^{\textnormal{R2}}_{c,1}:=\texttt{Certv1}{}(\{f_{i}\}_{i=1}^{k},c^{\textnormal{sec}},c).$

   Note that this also includes the special case $c=c^{\textnormal{sec}}$ as $\texttt{Certv1}{}(c^{\textnormal{sec}},c^{\textnormal{sec}})=0$.

   As for $c$ beating $c^{\textnormal{pred}}$ in Round 2, let $g_{i}^{c}:\mathcal{X}\to\{c,c^{\textnormal{pred}}\}$ denote the binary $c^{\textnormal{pred}}$ vs $c$ classifier obtained from $f_{i}$. Formally, we set $g_{i}^{c}(x)$ to $c$ if $f_{i}^{\text{logits}}(x,c)>f_{i}^{\text{logits}}(x,c^{\textnormal{pred}})$ and set it to $c^{\textnormal{pred}}$ otherwise. We can lower bound the number of poisoned samples the adversary requires with

   $\displaystyle\texttt{Cert}^{\textnormal{R2}}_{c,2}:=\texttt{Certv1}{}(\{g_{i}^{c}\}_{i=1}^{k},c^{\textnormal{pred}},c).$

   Overall, since the adversary can choose the class $c$, we obtain the bound

   $\displaystyle\texttt{Cert}^{\textnormal{R2}}:=\min_{c\neq c^{\textnormal{pred}}}\max\{\texttt{Cert}^{\textnormal{R2}}_{c,1},\texttt{Cert}^{\textnormal{R2}}_{c,2}\}.$

Given the above analysis, we obtain the following theorem, a formal proof of which is provided in Appendix E.2.

We now show how we can obtain 1v1 and 2v1 certificates for DPA+ROE and FA+ROE.

Certificate for DPA+ROE. We start with calculating $\texttt{Certv1}{}(c,c^{\prime})$. Since each poisoned sample can affect at most one model, the optimal action for the adversary is to “flip” a vote from $c$ to $c^{\prime}$. The adversary, therefore, requires at least half of the gap between the votes of $c$ and $c^{\prime}$. Formally, we use the following lemma, the proof of which is provided in Appendix E.3.1.

Calculating $\texttt{Certv2}{}(c,c_{1},c_{2})$ is more complex as the adversary’s optimal action choice is less clear. Intuitively, while the adversary should always change votes from $c$ to either $c_{1}$ or $c_{2}$, it is not clear which class it should choose. To solve this issue, we use dynamic programming. Defining $\textnormal{gap}_{i}:=\max\{0,\textnormal{gap}(c,c_{i})\}$ for $i\in\{1,2\}$, we calculate Certv2 as a function of $\textnormal{gap}_{1},\textnormal{gap}_{2}$. As long as $\textnormal{gap}_{1},\textnormal{gap}_{2}>2$, an optimal adversary should first choose a poison to reduce one of the gaps and then continue the poisoning process. This leads to a recursive formulation which we solve efficiently using dynamic programming. Formally, we fill a matrix dp of size $[k+2]^{2}$ where if $\min(i,j)\geq 2$ we set

and if $\min(i,j)\leq 1$, we set $\textnormal{dp}[i,j]:=\left\lceil\frac{\max(i,j)}{2}\right\rceil$. We obtain the following lemma, the proof of which is in Appendix E.3.2.

Certificate for FA+ROE. We start with the 1v1 certificate. Consider a poisoned sample of the adversary and assume it falls in some bucket $i$. By definition of buckets, this can only affect the models $f_{j}$ satisfying $j\in h_{\text{spr}}(i)$. If model $j$ votes for $c$, this can reduce the gap by at most two, and if the model votes for some class $\tilde{c}\notin\{c,c^{\prime}\}$, it can reduce the gap by 1. This allows us to bound the effect of poisoning each bucket on the gap. As we will see, the effect of poisoning multiple buckets is, at most, the sum of the effects of each bucket. Formally, we obtain the following lemma, the proof of which is in Appendix E.4.1.

Formal pseudocode for obtaining Certv1 is provided in Algorithm 4.

In order to calculate $\texttt{Certv2}{}(c,c_{1},c_{2})$, we first observe that the adversary needs at least $\max_{i}(\texttt{Certv1}{}(c,c_{i}))$ poisoned samples since both $c_{1}$ and $c_{2}$ need to beat $c$. This is not necessarily enough, however, as making $c_{1}$ and $c_{2}$ beat $c$ simultaneously may be more difficult than making each beat $c_{i}$ individually. In order to obtain a stronger bound, we use an approach inspired by duality and consider the conical combination of the constraints. Defining $\textnormal{gap}_{i}:=\max\{0,\textnormal{gap}(c,c_{i})\}$, we observe that if $\textnormal{gap}_{1}$ and $\textnormal{gap}_{2}$ both become non-positive, then so does every combination $\lambda\textnormal{gap}_{1}+\lambda^{\prime}\textnormal{gap}_{1}$ for $\lambda,\lambda^{\prime}\geq 0$. As a special case, this includes $\textnormal{gap}^{+}:=\textnormal{gap}_{1}+\textnormal{gap}_{2}$. We can bound the number of poisoned samples for making $\textnormal{gap}^{+}$ non-positive using a similar argument as the 1v1 certificate. Each bucket $b$ can only affect models $j$ such that $j\in h_{\text{spr}}(b)$. If $j$ votes for $c_{1}$ or $c_{2}$, the gap cannot be reduced. If $j$ votes for $c$, the gap can be reduced by at most $3$ and if $j$ votes for some $\tilde{c}\notin\{c,c_{1},c_{2}\}$, the gap can be reduced by at most $1$. We Define the total poisoning power of each bucket as

where we hide the dependence on $c,c_{1},c_{2}$ for brevity. We obtain the following lemma, the proof of which is in Appendix E.4.2.

We consider the same setup as prior work (Levine & Feizi, 2020; Wang et al., 2022b) and evaluate our method on MNIST (LeCun et al., 1998), CIFAR-10 (Krizhevsky et al., 2009) and GTSRB (Stallkamp et al., 2012) datasets. We similarly use Network-In-Network (Lin et al., 2013) architecture, to be trained with the set of hyperparameters from (Gidaris et al., 2018). Wang et al. (2022a) observe that the accuracy of ensemble methods can be further improved by having better base classifiers, i.e., base classifiers that have better classification accuracy. They improve over the original DPA by training base classifiers on the augmented version of datasets. As we want to have a fair comparison to the FA baseline, we train classifiers of both DPA and FA as Wang et al. (2022b).

As in prior work, we consider certified fraction (CF) as our performance metric. Given a budget $B$ for the adversary, the certified fraction of the dataset denotes the fraction of test samples that are provably classified correctly as long as the dataset is not altered by more than $B$ points.

As baselines, we use the Deep Partition Aggregation (DPA) method of Levine & Feizi (2020) and the Finite Aggregation (FA) method of Wang et al. (2022b). As discussed in Wang et al. (2022b), FA is effectively a generalization of DPA that uses overlapping partitions. Compared to DPA, FA takes an additional parameter $d$ and uses $d$ times as many base models. When using $d=1$, FA coincides with DPA. While larger values of $d$ increase the robustness of the model, this comes at the cost of increased computation; the training cost for FA is $d$ times the training cost for DPA.

Boosted DPA. Given the increased computational cost of FA, in order to obtain a fair comparison, we also consider a “boosted” variant of DPA which we denote by DPA^∗.³³3We thank an anonymous referee of the paper for proposing this method. For each partition $D_{i}$ of the dataset, we train $d$ models $\{f_{i,j}\}_{j=1}^{d}$ on the partition using different seed values. At test time, we average the logits layer of these models. In other words, each model $f_{i}$ in DPA^∗is itself an ensemble of $d$ “submodels”. The approach effectively makes the predictions more robust to the noisiness of the training process. The certificate for the model is calculated using the same technique as the certificate for DPA as outlined in Section 3.3. We note that the case $d=1$ corresponds to DPA.

Our results are shown in Tables 1, 2, 3, 4, 5 and Figures 2, 3. We do not report error bars as the variation caused by training noise is negligible (See Appendix D). As seen in Table 1, when we apply our aggregation method to FA, it can remarkably improve the certified accuracy of the original Finite Aggregation (we compare these two methods with the same $d$). Improvements can be up to $3\%$ or $4\%$. More interestingly, by applying our technique to DPA^∗, we observe significant improvement which can be up tp $27\%$ in some cases. This implies that DPA^∗+ROE is the new state-of-the-art in provable defense.

Overall, the results show that no matter choice of base classifiers is, applying ROE improves the certified robustness. The results of applying ROE to DPA can be seen in Table 3. We obtain improvements in certified accuracy by up to $4.73\%,3.14\%$, and $3.18\%$ on MNIST, CIFAR-10, and GTSRB, respectively. Improvements of using ROE on DPA^∗ is reported in Table 2. DPA^∗+ROE improves robustness of DPA^∗ on MNIST, CIFAR-10, and GTSRB by up to $3.49\%,3.70\%$, and $3.44\%$, respectively.

Perhaps more impressively, as seen in Table 4, DPA+ROE also competes with, and for larger values of $B$ outperforms FA while it significantly needs less training cost as its training cost is equivalent to that of DPA. For example, on CIFAR-10 dataset when $k=250$, by using a single NVIDIA GeForce RTX 2080 Ti GPU, the total training time of classifiers used in DPA+ROE is around $3$ hours while it takes around $47.3$ hours to train classifiers needed in FA with $d=16$. Roughly speaking, the training of FA with parameter $d$, takes $d$ time more than that of DPA, or DPA+ROE.

Although DPA+ROE uses less training time, it obtains a higher certified accuracy for larger values of $B$, e.g., on the standard CIFAR-10 dataset when $k=50$, it obtains a higher certified fraction than FA with $d=32$ when $B\geq 15$ even though it uses 32 times less computation in training. A similar comparison of DPA+ROE and DPA^∗ in Table 5 shows that in some cases, DPA+ROE can outperform DPA^∗as well while it uses significantly less training cost.

The increased accuracy of the models depends on the setting; one may choose DPA+ROE, FA+ROE or DPA^∗+ROE as each have their advantages. DPA+ROE has the advantage that it uses less computational resources while DPA^∗+ROE and FA+ROE obtain better accuracy. We note that the benefit of DPA^∗+ROE and FA+ROE compared to DPA+ROE seem to come from two different sources; DPA^∗+ROE uses increased computation to make each model more robust while FA+ROE uses a more complex partitioning scheme. As such, it can be expected that either of the methods may be preferable depending on the setting and this is observed in our experiments, though generally DPA^∗+ROE seems to have higher accuracy. Visual comparison of different methods can be seen in Figures 2 and 3. While these distinctions are interesting, they are orthogonal to the focus of our paper; we show that using ROE improves robustness in all of these settings without increasing the training cost.

Effect of the budget $B$. Our results show that ROE methods are especially useful for larger values of the adversary’s budget $B$. Intuitively, ROE is utilizing base classifiers that were previously discarded. As such, for a fixed budget $B$, the ratio of the poisoned samples to the utilized models is considerably smaller for our method, which allows us to obtain improved results. We note that this is in strong contrast to FA, where for larger values of $B$, the accuracy gains compared to DPA diminish and eventually cease to exist. Indeed, as seen in Figure 2, FA can actually be worse than DPA for large budgets, while our method remains strongly favorable, as we achieve 5% higher certified fraction on the standard CIFAR-10 dataset.

While our aggregation method performs well when the adversary’s budget is high, we see a slightly lower certified fraction in Figures 2 and 3 when $B$ is relatively small. In these cases, the certified fraction is close to clean accuracy, i.e., accuracy of the model when training data is not poisoned. Intuitively, the drop is because of the (slightly) lower reliability of the logits-layer information as discussed in Section 3.1. ROE methods have slightly lower clean accuracy because they involve all models in prediction, even models which are not accurate for a sample test. On the other hand, when the model’s prediction is correct, involving more models makes the adversary’s task harder.