BagFlip: A Certified Defense Against Data Poisoning
Authors: Yuhao Zhang
Aws Albarghouthi
Loris D'Antoni
Venue: NeurIPS 2022 Accept (2022)
Keywords: data poisoning
certified defense
backdoor attack
trigger-less attack

Abstract: Machine learning models are vulnerable to data-poisoning attacks, in which an attacker maliciously modifies the training set to change the prediction of a learned model. In a trigger-less attack, the attacker can modify the training set but not the test inputs, while in a backdoor attack the attacker can also modify test inputs. Existing model-agnostic defense approaches either cannot handle backdoor attacks or do not provide effective certificates (i.e., a proof of a defense). We present BagFlip, a model-agnostic certified approach that can effectively defend against both trigger-less and backdoor attacks. We evaluate BagFlip on image classification and malware detection datasets. BagFlip is equal to or more effective than the state-of-the-art approaches for trigger-less attacks and more effective than the state-of-the-art approaches for backdoor attacks.

BagFlip: A Certified Defense against Data Poisoning
Yuhao Zhang University of Wisconsin-Madison yuhaozccs. wisc.edu edu
Aws Albarghouthi University Wisconsin-Madiin awsCcs wisc. edu
2.X. [cs.LG] 16 Oct 2022
Loris D' D'Antoni
University of Misconsin-Madisse loris@cs. wisc.
Abstract
Machine learning models are vulnerable to data-poisoning attacks, which an attacker maliciously modifies the training set change the prediction of a learned model. In a trigger-less attack, the attacker can modify the training set but not the test inputs, while in buckdoor attack the attacker can also modify test inputs. Existing model-agmostic defense approaches either cannot handle backdoor attacks or do not provide effective certificates (i.e., a proof of defense). We present BagFlip, a mmoeel-agnostie certified approach that can effectively defend against both trigger-less and backdoor attacks. We evaluate BagFlip on image classification and malware detection datasets. BagFlip is equal to or more effective than the state-of-the -ferhh-art approaches for trigger-less attacks and more effective than the state-of-the-an approaches for backdoor attacks.
1 Introduction
Recent works have shown that machine learning models are vulnerable to data-poisoning attacks, where the attackers maliciously modify the training set to influence the prediction of the victim model 11, the attacker can modify the training set 21 25 27 the attacker can also modify test inputs. Effective attack approaches have been proposed for various domains such as image recognition [12. sentiment analysis (25), and malware detection [30].
as they desire. In a trigger-less attack 42 24
but not the test inputs, while in backdoor attack 29 34
5
Consider the malware detection setting. An attacker can modify the training data by adding a special signature- e.g., line of code-te set of benign programs. The idea is to make the learned model correlate the presence of the signature with benign programs. Then, the attacker can sneak a piece of malware past the model by including the signature, fooling the model into thinking it is a benign program. Indeed, it has been shown that if the model is trained on dataset with only a few poisoned examples, a backdoor signature can be installed in the learned model (30 27). Thus, data- data-poisoning attacks are of great concern to the safety and security of machine learning models and systems, particularly training data is gathered from different sources, e.g., via web scraping.
Ideally, a defense against data poisoning should fulfill the following desiderata: (1) Construct effective certificates (proofs) of the defense. (2) Defend against both trigger-less and backdoor attacks. (3) Be model-agnostic. is quite challenging to fulfill all three desiderata; indeed, existing techniques
are forced to make tradeoffs. For instance, empirical approaches [10 40 20 26
36 13 33 9
cannot
construct certificates and are likely to be bypassed by new attack approaches [32 37 16. Some
certified approaches [39 35 provide ineffective certificates for both trigger-less and backdoor attacks.
Some certified approaches [15
22 38 provide effective certificates for trigger-less attacks
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

but not backdoor attacks. Other certification approaches algorithms, e.g.. decision trees.
14 23 23 are restricted to specific learning
This paper proposes BagFlip, a model-agnostic certified approach that uses randomized smoothing 6 18] to effectively defend against both trigger-less and backdoor attacks (Section [.. BagFlip novel smoothing distribution that combines bagging of the training set and noising of the training data and the test imput by randomly flipping features and labels.
Although both bagging-based and noise-based approaches have been proposed independently in the literature, combining them makes it challenging compute the certified radius, i.e., the amount of poisoning a learning algorithm can withstand without changing its prediction.
To compute the certified radius precisely, we apply the Peyasnn lemma to the sample space of BagFlip's s smoothing distribution. This lemma requires partitioning the outcomes in the sample space into subspaces such that the likelihood ratio in each subspace is constant. However, because our sample space is exponential in the number of features, we cannot naively apply the lemma. To address this problem, we exploit properties of our smoothing distribution to design an efficient algorithm that partitions the sample space into polynomially many subspaces (Section 5). Furthermore, we present relaxation of the Neyman-Pearsen lemma that further speeds up the computation (Section (6. Our evaluation against existing approaches shows that BagFlip is comparable to them or more effective for trigger-less attacks and more effective for backdoor attacks (Section 7)
2
Related Work
Our model-agnostic approach BagFlip uses randomized smoothing to compute effective certificates for both trigger-less and backdoor attacks. BagFlip focuses peture-and-label--lippiii perturbation functions that modify training examples and test inputs. We discuss how existing approaches differ.
Some model-agnostic certified approaches can defend against both trigger-less and backdoor attacks but cannot construct effective certificates. Wang et al. (35), Weber al. [39] defended feature- flipping poisoning attacks and 12-norm poisoning attacks, respectively. However, their certificates are practically ineffective due to the curse of dimensionality [17.
Some aones--anootic certified approaches construct effective certificates but cannot defend against backdoor attacks. Jia et al. [15] proposed to defend against general trigger-less attacks, i.e., the attackers can add/delete/modifyy examples in the training dataset, by bootstrap aggregating (bagging). Chen al. [ extended bagging by designing other selection strategies, e.g., selecting without replacement and with a fixed probability. Rosenfeld et al. (88 defended against label-flipping attacks and instantiated their framework on linear classifiers. Differential privacy 22 can also provide probabilistic certificates for trigger-less attacks, but it cannot handle backdoor attacks, and its certificates are ineffective. Levine and Feizi [19] proposed a deterministic partition aggregation (DPA) to defend against general trigger-less attacks by partitioning the training dataset using secret hash function. Wang al. (38] further improved DPA by introducing spread stage.
Other certified approaches construct effective certificates but are not model-agnostic. Jia et al. 14 provided deterministic certificates only for nearest neighborhood classifiers (kNN/tNN), but for both trigger-less and backdoor attacks. Meyer et al. [23]. Drews et al. 77] provided deterministic certificates only for decision trees but against general trigger-less attacks.
3 Problem Definition
We take a holistic view of training and inference as a single deterministic algorithm A. Given a dataset D = {(x,, ,1.,..., (X,, yn)} and (test) input x, we write A(D,x) x) to denote the prediction of algorithm A on the input x after being trained on dataset D.
We are interested in certifying that the algorithm will still behave "well" after training on a tampered dataset. Before describing what "well" means, to define our problem we need to assume a perturbation space-i.e. what possible changes the attacker could make to the dataset. Given a pair (x, y), we write क (x, y) to denote the set of perturbed examples that an attacker can transform the example (x, y) into. Given dataset D and radius r 2 O, we define the perturbation space as the set of

---

datasets that can be obtained by modifying up to examples in D using the perturbation x:
{ ((L, Til3: vi. (x; MA) E (x,;, Vi), Σ 1 (x..))4(x.1)) Sr }
(D) =
Threat models. We consider two attacks: one where an attacker can perturb only the training set (a trigger-less attack) and one where the attacker can perturb both the training set and the test input (a backdoor attack). We assume backdoor attack scenario where test input perturbation is the same as training one. If these two perturbation spaces can perturb examples differently, we can always over-approximate them by their union. In the following definitions, we assume that we are given perturbation space т,, a radius r 2 0, and a benign training dataset D and test input X.
We say that algorithm A is robust to trigger-less attack the test input x if A yields the same prediction on the input when trained on any perturbed dataset D and the benign dataset D. Formally,
Vn E (D). A(D,x) = x))
(1)
We say that algorithm A is robust to a backdoor attack the test input if the algorithm trained on any perturbed dataset D produces the prediction A(D, x) on any perturbed input x. Let I Txx y)1 denote the projection of the perturbation space π <xx, y) onto the feature space (the attack can only backdoor features of the test input). Robustness to backdoor attack defined as
vD E (D), & π(x v)1 A(D,x) = A(D.x)
(2)
Given a large enough radius breaking robustness for either kind of attack. Therefore, we will focus on computing the maximal radius r. for which we can prove that Eq and for given perturbation function x. We refer to this quantity as the certified radius. It infeasible to prove Eq and 2 by enumerating all possible D because ST (D) can be ridiculously large, e.g., (D)
attacker can always change enough examples and succeed at
(D) > 10a0 when |D| = 1000 and r = 10.
Defining the perturbation function. We have not yet specified the perturbation function i.e., how the attacker can modify examples. In this paper, we focus on the following perturbation spaces.
Given bound 2 0, a -attr--aan--a---llliiieee
perturbation, FL,, allows the attacker to modify the values of up to s features and the label in an example (x,y), where x E [K] (i.e., is a d-dimensional feature vector with each dimension having (0, 1,... K} categories). Formally,
FL, (x, y) = ((x.)) v/) ||x - Žllo + 1 v S {}
There are two special cases of FLg, seattre--flipinng perturbation F, and label-flipping pertur- bation L. Given a bound s 2 0, F, allows the attacker to modify the values of up to features in the input x but not the label. L only allows the attacker modify the label of a training example. Note that L cannot modify the test input's 's features, so it can only be used in trigger-less attacks.
Example 3.1. If D is a ciass--classfiication image dataset, where each pixel is either black or white, then the perturbation function F1 assumes the attacker can modify up one pixel per image.
The goal of this paper is to design a certifiable algorithm that can defend against trigger-less and backdoor attacks (Section 4 by computing the certified radius (Sections (). Given benign dataset D, our algorithm certifies that an attacker can perturb D by some amount (the certified radius) without changing the prediction. Symmetrically, if we suspect that D is poisoned, our algorithm certifies that even if an attacker had not poisoned D by up to the certified radius, the prediction would have been the same. The two views are equivalent, and we use the former in the paper.
4 BagFlip: Dual-Measure Randomized Smoothing
Our approach, which we call BagFlip, is a madel-agnostic certification technique. Given a learning algorithm A, we want to automatically construct a new learning algorithm A with certified poisoning- robustness guarantees (Eqs. (1) and 2 To do so, we adopt and extend the framework of randomized smoothing. Initially used for test-time robustness, randomized smoothing robustifies a function by carefully constructing noisy version and theoretically analyzing the guarantees of f.
3

---

Our approach, BagFlip, constructs noisy algorithm A by randomly perturbing the training set and the test input and invoking A on the result. Formally, if we have set of output labels C, we define the smoothed learning algorithm A as follows:
A(D.x) argmax Pr (A(D, v)
(3)
DEC (xxx
where is carefully designed probability distribution the smoothing distribution the training set and the test input (D, X are sampled dataset and a test input from the smoothing distribution).
We present two key contributions that enable BagFlip efficiently certify robustness up large poisoning radii. First, we define a smoothing distribution that combines bagging [TS] of the training set D. and noising [35] of the training set and the test input x (done by randomly flipping features and labels). This combination, described below, allows us to defend against trigger-less and backdoor attacks. However, this combination also makes it challenging to compute the certified radius due to the combinatorial explosion of the sample space. Our second contribution is partition strategy for the Neyman-Pearsee lemma that results in an efficient certification algorithm (Section) 5), as well as a relaxation of the Neyman- lemma that further speeds up certification (Section 66.
Smoothing distribution. We describe the smoothing distribution μ that defends against feature and label flipping. Given a dataset D = {(x, }4)} and a test input x, sampling from pi D,x) generates random dataset and test input in the following way: (1) Uniformly select &t examples from D with replacement and record their indices as wi,..., Wg. (2) Modify each selected example (X.. Bw.) and the test input x to (x'.. Kv,)) and x', respectively, as follows: For each feature, with probability 1 - p. uniformly change its value one of the other categories in {O...., , K). Randomly modify labels yo, in the same way. In other words, each feature will be flipped to another value from the domain with probability
1 where P E [o, 1] is the parameter controlling the noise level.
For F. (resp. L), we simply do not modify the labels (resp. features) of the k selected examples.
Example 4.1. Suppose we defend against F1 in trigger-less setting, then the distribution μ will not modify labels or the test imput. Let p 5, k: 1. Following Example 3.1 let the binary-classfficttinn image dataset D {(X1, y1), (X2, y2)}. where each image contain only one pixel. Then, one possible element of pD x) can be the pair (((x): 32)) x), where x² X2. The probability of this element is z x p 0.4 because uniformly select one out of two examples and do not flip any feature, that is, the single feature retains its original value.
A Precise Approach to Computing the Certified Radius
In this section, show how compute the certified radius of the smoothed algorithm Á given dataset D, a test input x, and a perturbation function æ. We focus on binary classification and provide the multi-class case in Appendix
Suppose that we have computed the prediction y" Ā(D, x). We want to show how many examples we can perturb in D to obtain any other D so the prediction remains y". Specifically, we want to find the largest possible radius such that
AD E (D). ă (ET((X))) V).
Pr (A(D,))= y²) > 0.5 (.
(4)
We first show how to certify that Eq Tholds for a given r and then rely on binary search to compute the largest r, i.e., the certified radius] In Section 5.1 we present the Neyman- lemma to certify Eq Jss as it is a common practice in randomized smoothing. In Section 5.2 we show how to compute the certified radius for the distribution μ and the perturbation functions F,, FL,, and
5.1 The Neyman-Pearson Lemma
Hereinafter, we simplify the notation and use to denote the pair (D. x) and A(o) to denote the prediction of the algorithm training and evaluating on o. We further simplify the distribution μ((D, x)
'It is difficult to get a closed-fore solution of the certified radius (as done in 15 39 in our setting because the distribution of BagFlip is complicated. We rely on binary search as it is also done in Wang et al, [3] Lee
al. (18). Appendix D shows loose closed-fom bound on the certified radius by KL-divergence

---

as f and the distribution μ1 (D, x) as jr. We define the performance of the smoothed algorithm A on dataset D, i.e. the probability of predicting y". as p* (A(o) =
The challenge of certifying Eq is that we cannot directly estimate the performance of the smoothed algorithm on the perturbed data, i.e., Pxo-a(((0) y because zi is universally quantified. To address this problem, we use the Neyman- lemma to find lower bound lb for Pro~a(((()) = y²). We do so by constructing a worst-case algorithm A and distribution jr. Note that we add the superseript' ? to denote a worst-case algorithm. Specifically, we minimize Pro-j (A' (o) = y²) while maintaining the algorithm''s 's performance on j., i.e., keeping Pro-e (A) = y²) p=. We use A to denote the set of all possible algorithms. We formalize the computation of the lower bound lb as the following constrained minimization objective:
lb A min Pr (A) = =²) s.l. Pr (A) =0) =p" and D E (T)) xxx,)) A'EA onig
(5)
It is easy to see that lb is the lower bound of Pronii (A(o) n²) in Eq. because A E A and A satisfies the minimization constraint. Thus, lb 0.5 implies the correctness of Eq.
We show how to construct A and jū greedily. For each outcome = (D, x) in the sample space Q.i.c.. the set of all possible sampled datasets and test inputs- we define the likelihood ratio of as n(o) (o(()/ Pp (p)).. where Pn and Pp are the PMFs of μ and fú, respectively.
The key idea is as follows: We partition 52 into finitely many disjoint subspaces Li...., such that the likelihood ratio in each subspace L, is some constant т) [0, so], i..., Vo E L.-n(o) di- We can sort and reorder the subspaces by likelihood ratios such that 7) 2 ... 2 7m. We denote the probability mass of μ on subspace L; as (f.).
Example 5.1. Suppose pp(or)= (= Pa (a
to: Pp ( 4. To- We can partition and 02 into one subspace C because 7(01)=n(02))
Py fo P
The construction of the A that minimizes Eq. (o) = y" for L1, L2.... until the budget p" is met. The worst-case ji can also be constructed greedily by maximizing the top-most likelihood ratios, and we can prove that the worst-case happens when the difference between j and jí is maximized, i..., and x are maximally perturbed. The following theorem adapts the Neyman Neyman-Pearson Pearson lemma to setting.
greedy process, which iteratively assigns
Theorem 5.1 (Neyman-Pearson Lemma for FL,, Fs, L). Let D and x be a maximally perturbed dataset and test input, i.e., [D DI each perturbed example (X,, (i) in D. Let in A argming Pp(L) 2 p². Then, lb
|| - -xllo = s, and ||X; x;llo + T.vu = s, for
E Pp() + (D' Pu(Cs)) /Mau.
We say that lb right due to the existence of the minimizer A and jı (see Appendix B
Example 5.2. Following Example 5.7 suppose
{01, {o........ o1] and we partition it into L1 {oz}. Le = {o1 )2 La = {ot). and m = 4, = 1, 0.25. Let pd = 0.95, then we have
ibb = 3 and 0.1 0.5 + (0.95 0.4 0.5)/0.25 = 0.8.
5.2 Computing the Certified Radius of BagFlip
To compute lb for BagFlip, we address the following two challenges: 1) The argmin of computing in and the summation of lb in Theorem 5.1 depend on the number of subspaces Ly's. We design a partition strategy that partitions Ω into polynomial number of subspaces (O(k=d)), Recall that k is the size of the bag sampled from D and is the number of features. 2) In Theorem 5.1 lb depends on (C,C) which according to its definition (Eq 8) can be computed in exponential time (O(kd2)), )). We propose an efficient algorithm that computes these two quantities in polynomial time (O + ddd)))
Computing the certified radius boils down to computing lb in Eq 5 using Theorem 5.1
We first show how to address these challenges for F& and then show how to handle FL, and L.
Partition strategy. We partition the large sample space Ω into disjoint subspaces Le,t that depend on c, the number of perturbed examples in the sampled dataset, and t, the number of features the clean data and the perturbed data differ on with respect to the sampled data. Intuitively, takes care
5

---

of the bagging distribution and takes care of the feature-flippen flipping distribution. Formally,
Le,t [[[(> m Mwr, Mw,
Xux Na =,
(6)
b X xui llo + 1|x' x|10
Σ X Xw,10 1|x xx x/1o =t]
Eq 6 means that there perturbed indices sampled in A (and A) in Eq counts how many features the sampled and the clean data (the perturbed data) differ on. The number of possible subspaces Ce,r, which disjoint by definition, is O(k2d) because
k: and [4] (k: 1)d.
The next theorems show how to compute the likelihood ratio of Le,t and (f
Theorem 5.2 (Compute Bo.t). Ne,t Py(Co,) pp (Lo.)) (7/p)², where 7 and p are parameters controlling the noise level in BagFlip's 's smoothing distribution
Theorem 5.3 (Compute (C..)))
Py(Ca,))
Pr (o satisfies Eq 6 omp
Pr (o satisfies Eq satisfies Eq b
orep
where Promp (o satisfies 6) Binom (c; 7) is the PMF of the binomial distribution and
T(c, t) Pr satisfies Eq o satisfies Eg
Σ
MA,, As,,
ony
& sd. veludl] Aa- Be=t
(8)
where L(A, (1A,,;s,d, d) is the same quantity defined in Lee et al. (18). Remark 5.1. We can compute Pal (f,,),) as MottP (Ce,) by the definition of No,t.
Efficient algorithm to compute Eq 8 The following algorithm computes Tíc, () efficiently in
time ( + k2:P): 1) Computing L(u, o: 8,8,d d) takes ( (see Appendix C for details). 2)
Computing T(0, t) by the definition Eq 8 takes O(kd²). 3) Computing ((c, 2) for c 2 by the
following equation takes (l.2
min(d.++od) Σ
t(c,t)
T(c 1,t11ttt t.)
(9)
$1 =m= (d,taa
Theorem 5,4 (Correctness of the Algorithm). T(c,t) in Eq is the same as the one in Eg
The above computation still applies to perturbation function FL, and L. Intuitively, flipping the label can be seen as flipping another dimension in the input features (Details in Appendix B.I.
Practical perspective. For each test input x, need to estimate p" for the smoothed algorithm Á given the benign dataset D. We use Monte Carlo sampling to compute p" by the Clopper- Pearson interval. We also reuse the trained algorithms for each test input in the test set by using Bonferroni correction. We memoize the certified radius by enumerating all possible p* beforehand so that checking Eq can be done in constant time in online scenario (details in Appendix B.2). We cannot use floating point numbers because some intermediate values are too small to store in the floating point number format. Instead, we use rational numbers which represent the nominator and denominator in large numbers.
6 An Efficient Relaxation for Computing a Certified Radius
Theorem 5.1 requires computing the likelihood ratio of a large number subspaces Lı, L.n- We propose generalization of the Pearsnn lemma that underapproxinates the subspaces by a small subset and computes a lower bound lbş for 1b. We then show how choose a subset of subspaces that yields a tight underapproximation.

---

A relaxation of the Neyman-Pearson lemma. The key idea is to use Theorem 5.1 to examine only a subset of the subspaces {Ci]. Suppose that we partition the subspaces { into two sets { hee and {Li ii using a set of indices B. We define new lower bound lbg by applying Theorem 5.1 to the first group (e and underapproximating p" in Theorem 5.1 as p" -Eng Py (L,). Intuitively,
the underapproximation ensures that any subspace in (.C))gB will not contribute the lower bound. even though these subspaces may have contributed to the precise lb computed by Theorem 5.1
The next theorem shows that lbş will be smaller than lb by error term ò that is function of the partition B. The gain is in the number of subspaces we have to consider, which is now [B].
Theorem 6.1 (Relaxation of the Lemma), Define for the subspaces Li..... L. as Theorem 5.7 Define lbs for {Li hie B as in Theorem [5.7 by underappraximating p" as p P (fi),, then we have Soundness: 1bş- S lb and 5-Tightness: Let 8 _ ΣigB (f.). then lbg + 2 lb.
Example 6.1. Consider L1, L2, and Las from Example 5.2 If we set B = 21 and underapproxi- mate pd as p* - Pp((3) = 0.85, then we have lbş- = 0.1 (0.85 0.4)/1 = 0.55, which can still certify Eq. + However, 1bş not close to the original Ib- 0.8 because the error ö 0.4 is large in this example. Nexi, we will show how to choose B as small as possible while still keeping 5 small.
Speeding up radius computation. The total time for computing lb consists of two parts, (1) the efficient algorithm (Eq 9 computes T(c, () in Old + k2dd). and (2) Theorem 5.1 takes O(k2d) for a given p" because there are (A2d) subspaces. Even though we have made the computation polynomial by the above two techniques in Section 5.2 it can still be slow for large bag sizes k, which can easily be in hundreds or thousands.
We will apply Theorem 6.1 to replace the bag size k with a small constant K. Observe that (Ca,)) and pp (L.,)), as defined in Section 5.2 are negligible for large c, i.e., the number of perturbed indices in the smoothed dataset. Intuitively, If only small portion of the training set is perturbed, it is unlikely
that we select a large number of perturbed indices the smoothed dataset. We underapproximate the full subspaces to
by choosing the set of indices B = {(c, t) S k. |t| S (c 1)d]. where K is constant controlling the eтror 8. which can be computed as 5 = EigB EigB (c.) =
1 - Er= c (cnom(c; k :). Theorem 6.1 reduces the number of subspaces to [B] = O(e²d). As
result, all the k appearing in previous time complexity can be replaced with k.
Example 6.2. Suppose k- = 150 and 0.5%, choosing 6 leads to 8 1.23 x 10-5. In other words, it speeds up almost 625X for computing T(c, t) and applying Theorem 5.7
7 Experiments
The implementation of BagFlip is publicly available In this section, evaluate BagFlip against trigger-less and backdoor attacks and compare Bag with existing work. Note that we apply the relaxation in Section 6 to BagFlip in all experiments and set d 10-4
Datasets. We conduct experiments on MNIST, CIFARIO, EMBER (2]. and Contagio (http:/ //c ntagiodump. blogspot...c.oom com). MNIST and CIFARIO 10 are datasets for image classification. EMBER and Contagio are datasets for malware detection, where data poisoning can lead to disastrous security consequences. To align with cxisting work, we select subsets of MNIST and CIFAR10 as MNIST-17, 17, MNIST-01, and CIFAR 10-02 in some experiments, e.g., MNIST-17 is subset of MNIST with classes 1 and 7. We discretize all the features when applying BagFlip. We use clean datasets except in the comparison with RAB (39, where we follow their experimental setup and use backdoored datasets
generated by BadNets 11). A detailed description of the datasets is in Appendix E.
Models. We train neural networks for MNIST, CIFARIO, EMBER and random forests for Contagio. Unless we specifically mention the difference in some experiments, whenever we compare BagFlip to an existing work, we will use the same network structures, byper-parameters, and data augmentation as the compared work, and we train N 1000 models and set the confidence level as 0.999 for each configuration. All the configurations we used can be found in the implementation.
Metrics. For each test input U:). algorithm Á will predict a label and the certified radius r;- Assuming that the attacker had poisoned R% of the examples in the training set, we define certified accuracy as the percentage of test inputs that are correctly classified and their certified radii are no
7

---

100
CentfaiN Accuracy
80
[a] MNIST Fi
[c) EMBER F1
RigFlip-n
Bugging
Baghlip-b
40
(b) MNIST Poc
(d) EMBER Poo
20
2
0.2
0.4
0.6
0.1
0.2
0.3
0
0.1
0.2
Poisoning Amount (36)
Figure 1: Coomparison to Bagging on MNIST and EMBER, showing the certified accuracy at different
poisoning amounts R. For MNIST: a = 0.9 and b = 0.8. For EMBER: a = 0.95 and = 0.9.
Table I: Certified accuracy on MNIST and EMBER with perturbations F1 and Fec. Note that the certified accuracies are the same poisoning amount R 0 because we reuse the trained models.
F1
Foo
R
0.5
1.0
1.5
2.0
2.5
0.13
0.27
0.40
0.53
0.83
MNNITT
Bagging
94.54
66.84
0
0
0
94.54
90.83
85.45
77.61
61.46
0
Bagging-0.99
93.58
71.11
93.58
89.80
84.92
78.60
68.11
0
Bag
93.62
75.95
27.73
4.02
0
93.62
89.45
83.62
74.19
56.65
0
BagFlip-O.8
90.72
73.94
46.20
33.39
24,23
5.07
90.72
84.11
74.50
60.56
39.21
0
R
0.07
0.13
0.20
0.27
0.33
0
0.05
0.10
0.15
0.20
0.25
EMBER
Bagging
82.65
75.11
66.01
82.65
76.30
72.94
61.78
0
Bagging- 0.95
79.06
75.32
70.19
14.74
0
79.06
76.23
73.50
68.45
14.74
0
BagFlip-0.95
79.17
75.93
69.30
57.36
0
0
79.17
76.83
72.41
62.04
30.36
0
Bag
78.18
69.40
62.11
41.21
13.89
1.70
78.18
70.79
63.16
41.24
11.64
0
less than R, i.e., Emh 1 A(D.x))=p: 8%% inputs that are correctly classified, i.e., Σ A(Dxx)==
We define normal accuracy as the percentage of test
28%
7.1 Defending Against Trigger-less Attacks
Two model-agnostic certified approaches, Bagging 15] and LabelFlip 28
defend against
trigger-less attacks. BagFlip outperforms LabelFlip (comparison in Appendix E.2). We evaluate BagFlip on the perturbation F, using MNIST, CIFAR10, EMBER, and Contagio and compare BagFlip to Bagging. We provide comparisons with Bagging on other perturbation spaces in Appendix E.2
We present BagFlip with different noise levels (different probabilities of when flipping), denoted as BagFlip--p When comparing to Bagging, we use the same k the size of sampled datasets, for fair comparison. Furthermore, we tune the parameter l: in Bagging to match the normal accuracy with the BagFlip-p setting, and denote this setting as Bagging-p. Concretely, we set k = 100, 1 1000, 300, 30 for MNIST, CIFARIO, EMBER. and Contagio respectively when comparing to Bagging. We tune k 80, 280 for Bagging-0.9 on MNIST and Bagging-0.95 on EMBER, respectively. And we set k 50 for MNIST when comparing to LabelFlip.
Comparison to Bagging. Bagging on a discrete dataset is a special case of BagFlip when p= i.e. no noise is added to the dataset. (We present the results of bagging on the original dataset (undiscretized) in Appendix E.2) Table [ and Fig [ show the results of BagFlip and Bagging on perturbations F, and F.x over MNIST and EMBER. The results of CIFAR10 10 and Contagio are similar and shown in Appendix F.2 Fi only allows the attacker to modify one feature in each training example, and Fo. allows the attacker to modify each training example arbitrarily without constraint. For F1 on MNIST, BagFlip-O.3 performs better than Bagging after == 0.19 and BagFlip-0.8 8 still retains non-zero certified accuracy R = 2.5 while Bagging's certified accuracy drops to zero after R = 0.66. We observe similar results on EMBER for F, in Table [ to Bagging-0.95, We argue that it is possible to tune a best combination of A and for BagFlip, like we tune lo for Bagging-0.95. and achieve a better result while maintaining similar normal accuracy. However, we do not conduct hyperparameter- tunnngg for BagFlip because of its computation cost. BagFlip achieves higher certified accuracy than Bagging when the poisoning amount is large for Fi.
except = 0. 13 when compared
For Foo on MNIST, Bagging performs better than BagFlip across all R because the noise added by BagFlip to the training set hurts the accuracy. However, we find that the noise added by BagFlip helps
8

---

100
Cariifable Accuracy
Bagging
Coniifable Accerayy
80
60
F2 60
40
40
Fa
Foc
Poisoming Amount (%)
Puisoning Amoun. it (%)
Figure 2: (a) BagFlip-O08 on MNIST against F, with different 8 almost overlaps with 00. (b) BagFlip-0.8 on MNIST and BagFlip-0.9 on Contagio against backdoor attack with Fj. Dashed lines show normal accuracy.
it perform better for Foo EMBER. Specifically, BagFlip achieves similar certified accuracy as Bagging at small radii and FagFlip performs better than Bagging after It 0.15. Bagging achieves higher certified accuracy than BagFlip for Fo.. Except in EMBER, BagFlip achieves higher certified accuracy than Bagging when the amount of poisoning is large.
We also study the effect of different in the perturbation function Fs. Figure 2(a) shows the result of BagFlip-O.8 on MNIST. BagFlip has the highest certified accuracy for F1. As s increases, the result monotonically converges to the curve of BagFlip-O.8 in Figure lb). Bagging neglects the perturbation function and performs the same across all 8. Bagging performs better than BagFlip-0.8 when 8. Other results for different datasets and different noise levels follow similar trend (see Appendix E.2 BagFlip performs best at F1 and monotonically degenerates to Foo as increases.
7.2 Defending Against Backdoor Attacks
Two model-agnostic certified approaches, FeatFlip 335 and RAB [39, can defend against backdoor attacks. We compare BagFlip to FeatFlip MNIST-17 perturbed using FL.1, and compare BagFlip to RAB on poisoned MNIST-01 and 1EFAR10-22 (by BadNets (12)) perturbed using F1. We further evaluate BagFlip the perturbation using MNIST and Contagio, which existing work is unable to compute a meaningful certified radius.
Comparison to FeatFlip. FeatFlip scales poorly compared BagFlip because com- putation of the certified radius is polynomial in size of training set. BagFlip's s compu- tation is polynomial in the size of the bag in- stead of the size of the whole training set, and
Table 2:
Compared to FeatFlip FL and RAB Fi with normal accuracy (Acc.) and certified accuracy at different poisoning amount R (CF@ It).
MNIST-117
Acc.
CF@0 CF@0.5 CF@ 1.0
FeatFlip
98
0
uses relaxation of the for further speed up. BagFlip more scalable than FeatFlip.
Pearson lemma
-agFlip-0.95
97
81
60
0
BagFlip-0.9
97
72
46
4
Acc.
CF@0
CF@ 1.5 CF@3.0
CIFAR10-02 MNIST-01
We directly cite FeatFlip's 's results from Wang et al. (35] and note that FeatFlip is evaluated on subset of MNIST-17. As shown in Ta- ble 2 BagFlip achieves similar normal accu- racy, but much higher certified accuracy across all R (see full results in Appendix F.2) than FeatFlip. BagFlip significantly outperforms FeatFlip against FL, MNIST-17.
RAB
100.0
74.4
0
BagFlip-0.8
99.6
98.4
96.5
84.6
BagFlip-0.7
99.5
98.0
95.8
91.9
Acc.
CF@0
CF@0.1
CF@0.2
RAB
73.3
0
0
BagFlip--08
73.1
16.8
11.0
6.8
BagFlip-0.7
71.7
41.0
34.6
29.2
Comparison RAB. RAB assumes a perturbation function that perturbs the input within an 42- norm ball of radius s. We compare BagFlip to RAB on F1, where the 4y-nrmm ball (our perturbation function) and l2 -orm ball are the same because the feature values are within [0, 1]. Since RAB targets single-test-inpus prediction, we do not use Bonferroni correction for BagFlip
fair comparison. We directly cite RAB's 's results from Weber et [39] Table shows that on MNIST-01 and CIFARI0-00 10-02, BagFlip achieves similar normal accuracy, but a much higher certified accuracy than RAB for all values of (detailed figures in Appendix E.2 BagFlip significantly outperforms RAB against
Fi on MNIST-01 and CIFAR10-02.

---

Results on MNIST and Contagio. Figure 2(b) Contagio. When fixing R, the certified accuracy for the backdoor attack is much smaller than the certified accuracy for the trigger-less attack (Figure and Figure3] in Appendix F.2) because backdoor attacks are strictly stronger than trigger-less attacks. BagHlip cannot provide effective certificates for backdoor attacks on the more complex datasets CIFAR 10 and EMBER, i.e., the certified radius almost zero. BagFlip can provide certificates against backdoor attacks on MNIST and Contagio, while BagFlip's certificates are not effective for CIFAR10 and EMBER.
shows the results of BagFlip on MNIST and
7.3 Computation Cost Analysis
We discuss the computation cost of BagFlip on the MNIST dataset and compare to other baselines.
Training. The cost of BagFlip during training is similar to all the baselines because BagFlip only adds noise in the training data. BagFlip and other baselines take about 16 hours on single GPU to train N = 1000 classifiers on the MNIST dataset.
Inference. At inference time, BagFlip first evaluates the predictions of N classifiers, and counts how many classifiers have the majority label (N1) and how many have the runner-up label (N2). Then, BagFlip uses prepared lookup table query the radius certified by Ni and N2. The inference time for each example contains the evaluation of N classifiers and an O(1) table lookup. Hence, there is no difference between BagFlip and other baselines.
Preparation. BagFlip needs to prepare a table of size O(N2) to perform efficient lookup at inference time. The time complexity of preparing each table entry is presented in Sections 5 and 6 On the MNIST dataset, BagFlip with the relaxation proposed in Section 6 (5 = 10-4) needs 2 hours to prepare the lookup table single core. However, the precise BagFlip proposed in Section 5 needs 85 hours to prepare the lookup table. Bagging also uses a lookup table that can be built in 16 seconds on MNIST (Bagging only needs to do binary search for each entry). FeatFlip needs approximately 8000 TB of memory to compute its table. Thus, FeatFlip is infeasible to run on the full MNIST subset of the MNIST-17 dataset containing only 100 training
dataset. FeatFlip only evaluated examples. RAB does not need to compute the lookup table because it has a closed-form solution for computing the certified radius.
BagFlip has similar training and inference time compared to other baselines. The relaxation technique in Section 6 is useful to reduce the preparation time from 85 hours to 2 hours. Even with the relaxation, BagFlip needs more preparation time than Bagging and RAB. We argue that the preparation of BagFlip is feasible because it only takes 12.5% of the time required by training.
Conclusion, Limitations, and Future Work
We presented BagFlip, a certified probabilistic approach that can effectively defend against both trigger-less and backdoor attacks. We foresee many future improvements to BagFlip. First, BagFlip treats both the data and the underlying machine learning models as closed boxes. Assuming specific data distribution and training algorithm can further improve the computed certified radius. Second, BagFlip uniformly flips the features and the label, while it is desirable to adjust the noise levels for the label and important features for better normal accuracy according to the distribution of the data. Third, while probabilistic approaches need to retrain thousands of models after a fixed number of predictions, the deterministic approaches can reuse models for every prediction. Thus, it is interesting to develop a deterministic model- -agnostic approach that can defend against both trigger- and backdoor attacks.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers and Anna P. Meyer for their thoughtful and generous comments and Gurindar S. Sohi for giving us access to his GPUs. This work is supported by the CCF-1750965. CCF-1918211, CCF- CCF-2106707, CCF-1652140, a Microsoft Faculty Fellowship, and gifts and awards from Facebook and Amazon.
10


Reviews:
[{"review_id": "_MO-8-hcQGO", "reviewer": "Reviewer_vQcS", "summary": "This paper proposes a certified defense against triggerless and backdoor data poisoning attacks. The authors consider a threat model where the attacker can poison training instances (and the test instance for the backdoor attack) by flipping up to s of the features/label per instance. The defense is based on randomized smoothing, where the smoothing operation involves bagging of the training set and random flipping of features/labels. The certificate provides a (probabilistic) guarantee that up to R instances can be poisoned without changing the model’s prediction on a test instance. The derivation and computation of the certificate (i.e. R) is quite involved, and various relaxations are considered to speed up the computation. Experimental results demonstrate improved certified accuracies compared to bagging alone for triggerless attacks, when the fraction of poisoned instances is high and the number of flips is small. Results for backdoor attacks vary depending on the dataset. ", "questions": "Is there a reason why the flipping approach by Wang, Cao, Jia & Gong (2020) was not considered as a baseline in the experiments?\n\nIn Section 7.2, BagFlip is not found to be effective against backdoor attacks for CIFAR10 and EMBER. Are the authors able to speculate why BagFlip doesn’t work for the higher-dimensional datasets?\n\nI noticed the use of a superscript “?” in line 171 and elsewhere. Is that intentional?", "limitations": "These are discussed adequately in Section 8.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Originality*\n\nThe BagFlip method proposed in this paper seems to be a hybrid of methods by Jia, Cao & Gong (2021) and Wang, Cao, Jia & Gong (2020), in the sense that it combines bagging and feature/label flipping. In this sense, it could be viewed as a more incremental paper. However the authors should be credited for the derivation of the certificate, which was quite complex in the bagging/flipping setting. Another benefit of their method is that it encompasses both triggerless and backdoor threat models.\n\n*Quality*\n\nI was generally impressed by the quality of the paper, although I was not able to check the derivations in Sections 5 and 6 carefully. It was good to see a variety of datasets were tested in the experiments, as the conclusions did vary in some cases.\n\n*Significance*\n\nThe proposed method (BagFlip) seems to perform similarly to Bagging (Jia, Cao & Gong, 2021) for triggerless attacks in regimes where the certified accuracy remains reasonably high (e.g. above 70%). Given this observation, it’s not clear whether BagFlip should be preferred over Bagging. For instance, if the smoothing operation and certificate for BagFlip is significantly more computationally demanding, then BagFlip may not be preferred. It would be interesting to investigate this further, e.g. by comparing the computational cost of BagFlip versus baselines. \n\n*Clarity*\n\nI enjoyed reading the paper. Sections 5 and 6 were somewhat challenging to read, but that is probably unavoidable due to the complexity of the analysis. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Otam2dF5op3", "reviewer": "Reviewer_qMzU", "summary": "The article proposes a model-agnostic certified method to handle data-poisoning attacks that maliciously modify the training dataset. The article addresses trigger-less and backdoor attacks, and solves them with a noising/smoothing approach on training datasets. The proposed method was evaluated on image and malicious portable executable datasets including MNIST, CIFAR10, and EMBER, and showed robust accuracy in trigger-less and backdoor attacks, respectively.", "questions": "1. Section 7.2 describes the differences in the proposed method compared to FeatFlip. However, considering that FeatFlip proposed a randomized smoothing strategy, utilizing additional noise to cope with trigger-less attack seems like a minor modification of FeatFlip. Compared to FeatFlip, what is the technical novelty of the proposed method?\n2. While it is true that inductive learning approaches (including machine learning and deep learning) are being explored, many malware detection software is still based on traditional search/traverse algorithms based on signatures. In terms of malware detection, are data poisoning attacks observed in the real world?\n", "limitations": "The proposed method uniformly flips features and labels regardless of data distribution.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "(strength)\nThe article is well-structured, easy-to-follow. The proposed method (BagFlip) is technically sound.\n(weakness)\nThe proposed method was compared only for a limited control group (FeatFlip[35] and RAB[39]). Considering that FeatFlip[35] proposed a randomized smoothing strategy, the technical novelty of the proposed method is weak.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-NpHci-nT5", "reviewer": "Reviewer_6p2x", "summary": "This paper presents BagFlip, a model-agnostic certified approach that utilizes bagging and randomized smoothing to defend against various types of poisoning and backdoor attacks. This paper formulates the theoretical way to compute the certified radius of BagFlip and ways to speed up the computation. This paper evaluates BagFlip in various settings to show its effectiveness. ", "questions": "See above.", "limitations": "See above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n+ Strong attack model. \n+ This paper provides a certified guarantee in defending against backdoor attacks. \n+ The threat model and the goals are formulated clearly. \n\nWeaknesses:\n- Potential runtime problem. Could authors provide empirical evaluations for the running time?\n\n- The explanations of experimental results are unclear. When compared with bagging, the same k is used for both bagging and BagFlip. However, BagFlip adds additional Gaussian noise to the k training examples. Therefore, the noise added by BagFlip is larger than bagging. As a result, the normal accuracy for bagging is higher compared with BagFlip. Could authors use a smaller k for bagging such that bagging and BagFlip have similar normal accuracy? Given the similar normal accuracy, we can compare the robustness of the two methods. This is also applicable in the comparison to FeatFlip and RAB.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept