Temporal Robustness against Data poisoning
Authors: Wenxiao Wang
Soheil Feizi
Venue: NeurIPS 2023 poster (2023)
Keywords: Robustness
Data Poisoning
Security
Machine Learning
Backdoor
Adversarial
TL;DR: A novel threat model for data poisoning that incorporates temporal concepts, along with a benchmark for evaluation and a baseline defense with provable robustness.

Abstract: Data poisoning considers cases when an adversary manipulates the behavior of machine learning algorithms through malicious training data. Existing threat models of data poisoning center around a single metric, the number of poisoned samples. In consequence, if attackers can poison more samples than expected with affordable overhead, as in many practical scenarios, they may be able to render existing defenses ineffective in a short time. To address this issue, we leverage timestamps denoting the birth dates of data, which are often available but neglected in the past. Benefiting from these timestamps, we propose a temporal threat model of data poisoning with two novel metrics, earliness and duration, which respectively measure how long an attack started in advance and how long an attack lasted. Using these metrics, we define the notions of temporal robustness against data poisoning, providing a meaningful sense of protection even with unbounded amounts of poisoned samples when the attacks are temporally bounded. We present a benchmark with an evaluation protocol simulating continuous data collection and periodic deployments of updated models, thus enabling empirical evaluation of temporal robustness. Lastly, we develop and also empirically verify a baseline defense, namely temporal aggregation, offering provable temporal robustness and highlighting the potential of our temporal threat model for data poisoning.

Temporal Robustness against Data Poisoning
Wenxiao Wang
Soheil Feizi
Department of Computer Science University of Maryland College Park, MD 20742 wwxBumd. edu
Department Computer Science University of Maryland
College Park, MD 20742 sfeizi @umd edu
Abstract
Data poisoning considers cases when an adversary manipulates the behavior of machine learning algorithms through malicious training data. Existing threat models of data poisoning center around single metric, the number of poisoned samples. In consequence, if attackers can poison more samples than expected with affordable overhead, as in many practical scenarios, they may be able to render existing defenses ineffective in short time. To address this issue, we leverage timestamps denoting the birth dates of data, which are often available but neglected in the past. Benefiting from these timestamps, we propose temporal threat model of data poisoning with two novel metries, earliness and duration, which respectively measure how long attack started in advance and how long an attack lasted. Using these metrics, we define the notions of temporal robustness against data poisoning, providing meaningful sense of protection even with unbounded amounts of poisoned samples when the attacks are temporally bounded. We present benchmark with evaluation protocol simulating continuous data collection and periodic deployments of updated models, thus enabling empirical evaluation of temporal robustness. Lastly, we develop and also empirically verify baseline defense, namely temporal aggregation, offering provable temporal robustness and highlighting the potential of our temporal threat model for data poisoning.
1 Introduction
Many applications of machine learning rely on training data collected from potentially malicious sources, which motivates the study of data poisoning. Data poisoning postulates an adversary who manipulates the behavior of machine learning algorithms [11] through malicious training data.
great variety of poisoning attacks have been proposed challenge the reliability of machine learning with unreliable data sources, including triggerless attacks 2 22 15|
30 46
10) and backdoor
attacks [8 35| 29
required at inference time. At the same time, diverse defenses are proposed, some of which aim at detecting/filterin 44, some of which aim robustifying models trained with
4
32
45 depending whether input modifications
poisoned samples 33 25
34 37
23
poisoned samples 41 36
27
16
1 14
26, 38 40).
The number of poisoned samples is absolutely key metric among existing threat models of data poisoning, and defenses are typically designed for robustness against bounded numbers of poisoned samples. However, the number of poisoned samples defenses may tolerate can be quite limited (e.g.
< 0.1% of the dataset size), as supported empirically by 3 4 32 Furthermore, explicit bound the number of poisoned samples scenarios and therefore it can be possible for attacks to render existing defenses ineffective a short time. For example, when data are scraped from the internet, an attacker can always post more poisoned samples online; when data are contributed by users, a single attacker may pose itself as
10
5 and theoretically by [40]. available in many practical
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

timeline
duration of the attack
Temporal dobustness
earliness of the attack clean sample*
robustness to poisoning atks with bounded earliness duration
sample removed by the attacker
x sample inserted by the attacker poisoned sample
end of data collection
Figure An illustration of our temporal modeling of data poisoning. Every sample, no matter whether it is clean poisoned. is associated with birth date, i.c. timestamp denoting when the sample becomes available for collection. Two temporal metrics are proposed to characterize data poisoning attack: Earliness, how long the poisoning attack started in advance, is determined by the earliest timestamp of all poisoned samples; Duration, how long the poisoning attack lasted, is defined as the time passed from the earliest to the latest timestamps of all poisoned samples.
multiple users to poison a lot more training samples. In these cases, the robustness notions in existing threat models of data poisoning fail to provide meaningful sense of protection.
Is there any option other than the number of poisoned samples? Yes! When collecting data, there usually corresponding timestamps available but neglected previously in modeling data poisoning. For instance, company can keep track of the actual creation time of user data; online contents often come with publication date indicating when they are posted. While attackers may create poisoned samples of many kinds, they typically have direct way addition, temporally bounded poisoning attacks have been proposed in couple specific scenarios These motivate to use time as a new dimension for defenses against data poisoning.
the values of these timestamps. In
28 5).
To summarize, we make the following contributions:
proposing a novel threat model for data poisoning along with the notions of temporal robustness, providing meaningful protections with potentially unbounded amounts of poisoned samples when the attacks are temporally bounded;
designing a benchmark with an evaluation protocol that simulates continuous data collection with periodic model updates, enabling empirical evaluation of temporal robustness;
developing and verifying a baseline defense with provable temporal robustness.
2 Temporal Modeling of Data Poisoning
2.1 Background: Threat Models that Center Around the Number of Poisoned Samples
Here recap typical threat model depending heavily the number of poisoned samples.
Let X' be the input space, y be the label space and (X' )) be the space of all possible training sets. Let f D x + ) be a learner that maps input to label conditioning on training set. Given training set D. learner f D x X' + y and a target sample Ho E X' with corresponding ground truth label E ), the attack succeeds and the defense fails when poisoned training set D' E found such that D @ D' < and J(D', mo) # yo- Here D + D' = [(D) \ D'' D)] is the symmetric distance between two training sets, which is equal to the minimum number of insertions removals needed to change to D'. T the attack budget denoting the maximum number of poisoned samples allowed.

---

2.2 Proposal: Temporal Modeling of Data Poisoning
In existing threat models for data poisoning, the key characteristic of an attack the number of poisoned samples: Attacks try to poison (i.e. insert or remove) fewer samples to manipulate model behaviors and defenses try to preserve model utility assuming a bounded number of poisoned samples.
As result, if attackers can poison more samples than expected with affordable overhead, which is possible in many practical scenarios, they may render existing defenses ineffective short time. Towards addressing this issue, we incorporate the concepts of time in modeling data poisoning.
Definition 2.1 (Timeline). The timeline T is simply the set of all integers Z, where smaller integers denote earlier points in time and the difference of two integers is associated with the amount of time between them.
Notably, we use notions of discrete timelines in this paper.
Definition 2.2 (Data with Birth Dates), Let X be the input space, y be the label space, every sample is considered to have the form of (x, y. f), where x E X is its input, y E y is its label and t E 'T is timestamp, namely birth date, denoting when the sample becomes available for collection. We use Dr = (X x y T) to denote the space of all possible training sets with timestamps.
In practice, the birth dates of samples determined in the data collection process. For example, company may set the birth dates to the actual creation time of its users' data; When scraping data from the internet, one may use upload dates available third-part hird-partty websites; In cases of continuous data collection, the birth dates can also be simply set to the time that samples are first seen.
Definition 2.3 (Temporal Data Poisoning Attack). Let Delean E Dr be the clean training set, i.e. the training set that would be collected if there were attacker. The attacker can insert a of samples D inssen E Dr to the training set and remove set of samples D Dremove S Deleun from the training set, following Assumption 2.4 but with no bound on the numbers of samples inserted or removed. Let D' = Deeenn \ D Dremeve] U Disee be the resulted, poisoned training set and J DD x X + y be learner that maps an input
label conditioning on training set with timestamps. Given larget sample To E X with a corresponding ground truth label yo E y, the attack succeeds and the defense fails when f(D', 22) & yo-
Assumption 2.4 (Partial Reliability of Birth Dates). The altacker has capability to directly set the birth dates of samples.
In another word, Assumption 2.4 means that no poisoned sample can have a birth date falling outside
the active time of the attacker:
an attack starts at time tg. no poisoned sample can have a timestamp smaller than to (i.c. t 2 to for all (I, y, E Dremove U Dissen;
If attack ends at time 1,, no poisoned sample have timestamp larger than t (i.e. f S f for all (I. y, f) E D Dremove U misen).
worth noting that this does not mean that the attacker has no control over the birth dates of samples. For instance, an attacker may inject poisoned samples at a specific time to control their birth dates or change the birth dates of clean samples by blocking their original uploads (i.e. removing them from the training set) and re- re-inserting them later.
With the above framework, now introduce two temporal metrics, namely earliness and duration, that are used as attack budgets in our temporal modeling of data poisoning. An illustration of both concepts included in Figure
Definition 2.5 (Farliness). Earliness measures how long poisoning attack started in advance (iee how early it is when the attack started). The earliness of an attack is defined as
1) +1,
Tearliness = tend
mhin
where lond is the time when the data collection ends, Dpoison D Dremave Dinser is the set of poisoned samples, containing all samples that are inserted or removed by the attacker. The earliness of an attack is determined by the poisoned sample with the earliest birth date.
3

---

Definition 2.6 (Duration). Duration measures how long a poisoning attack lasted. The duration of an attack is defined
1) ()
min ( 1)+1.
1) +
dduration
max (
where Dpoison D Dremove U Dissen is the set of all poisoned samples. The duration of attack is determined by the time passed from the earliest birth date of poisoned samples to the latest one.
These notions for earliness and duration of attacks enable the description of the following new form of robustness that is never available without incorporating temporal concepts.
Definition 2.7 (Temporal Robustness against Data Poisoning). Let Detean E Dr be the clean training set and f Dr x X' + y be a learner that maps an input to a label conditioning on a training set with timestamps. For a given target sample ig E X with the ground truth label yo-
f is robust against data poisoning with a maximum earliness of for all Dinsers and D remave with Tearliness S T, [(eeeln remove) V Dinsert, Tu)
y/o
*f is robust against data poisoning with a maximum duration of for all Dinsert and D Dremove with T, [((Delean \ Dremove)
Tduration
D Dinserty Wo) yoo
Informally, learner or a defense offers temporal robustness against data poisoning if all poisoning attacks with earliness or duration bounded by cannot manipulate its behavior.
Temporal robustness against data poisoning can be more desirable than existing notions, especially for scenarios where attackers may poison more and more samples with affordable overhead: The number of poisoned samples is no longer a good measure of attack efforts, but the proposed concepts of earliness and duration are closely tied to the difficulty of conducting the attack as long as time travels remain fictional.
3 A Temporal Robustness Benchmark
In this section, we present benchmark to support empirical evaluations of temporal robustness by simulating continuous data collection and periodic deployments of updated models.
3.1 Dataset
We use News Category Dataset 220 21 the base of our benchmark, which contains news headlines from 2012 to 2022 published on HufiPost (https://www.hull)) every headline is associated with a category where it was published and a publication date. Notably, this setting is well aligned with our Assumption 2.4 Partial Reliability of Birth Dates, as potential attacker may capable of submitting a poisoned headline but cannot set a publication date that is not its actual date of publication.
m. In News Category Dataset,
Following the recommendation by 220 use only samples within the period of 2012 to 2017 extensive archive of news articles in 2018. To be spe- eific, we preserve only news headlines dated from 2012-02-01 to 2017-12-31 and the result- ing dataset contains in total 191939 headlines and 41 categories, temporally spanning over Amonth months. For better intuitions, we include examples of headlines with categories and publication dates in Table D and the counts headlines in each month in Figure 2 In addition, while natural distribution shifts over time are not the main focus of this work, it is worth noting that such natural shifts exist evidently, as shown in Figure 3 where we can observe that most categories only active for subset of months.
Heudline
Category
Date
HuffPost stopped maintaining
The Good, the Bad and the Beautiful How To Overcome Post. Travel Rlues Who The Real Shande For Di Goyin?
WELLNESS
2012-02-08
FIFTY
2015-04-29
TRAVEL
2016-06-26
POLITICS
2017-08-27
Table 1: Examples of headlines with categories and publication dates from News Category Dataset 20

---

Month
3000
Count
2000
1000
Index of Month
Figure 2: Counts of headlines published in each month. On average, 2703 headlines are pub- lished per month.
Figure 3: Presences of news categories in dif- ferent months. Marked positions indicate cate- gories published in the corresponding month.
3.2 Evaluation Protocol
denote every sample in the form of (x, y, t), where x E X is the headline, y E y is its corresponding category and E is its publication date.
Following the notations from Section 2.2
We use D; to denote the set of all samples published in the i-th month for 0 < < Amonth = 71.
Let f: DD X' be learner (i.e. function that maps headline category conditioning a training set with timestamps). Recalling the notion of temporal robustness from Definition 2.7 for given target sample Tn with the ground truth label you use
Fraiins [f, D, (zo, yo)] to denote whether is robust against data poisoning with maximum earliness of when Delenn D;
Trazsim ST [f, D, (zo, yo)] to denote whether f is robust against data poisoning with maximum duration of T when Delean D.
With these notions, define robust fractions corresponding to bounded earliness and duration of poisoning attacks, which serve as robustness metrics of the temporal robustness benchmark.
Definition 3.1 (Robust Fraction). For given Rstor which denotes the first month for testing.
the robust fraction of a learner f corresponding to a maximun earliness of T is defined as
E Di=nam
Ela.t.tED Tr D
1 j=naar Dj
the robust fraction of a learner corresponding a maximum duration of is defined as
Σ Prroet T
Exeg,D)D T St
S.U D3s (x.
U Mhnssll i=
Dj
Intuitively, here we are simulating a continuous data collection with periodic deployments of updated models, where models be updated monthly with access data newly arrived this month and all previous data. In another word, each month of samples will be used as test data individually, and when predicting the categories of samples from the i-th month, the model to be used will be the one trained from only samples of previous months (i.e. from the O-th to the (i - 1)-th month). The first Mssant months excluded from test data avoid performance variation due to the scarcity of training samples. Here, with momoth = 71 months of data available, we set Nsstatt
36, which is about half of
months. The resulted test set contains a total 91329 samples, i.e. Prrenth
D3 91329.

---

timeline
0
4 f-o
base classifier
f a training data
aggregation of classifiers
ИИクПИ f-1 AAMMA REAMA f
Figure 4: An illustration of temporal aggregation with base coverage 2 and aggregation size k (i.e. 2 periods of training data per base classifier and 5 base classifiers per aggregation).
Baseline Defense with Provable Temporal Robustness
4.1 Temporal Aggregation
Here we present temporal aggregation, a very simple baseline defense with provable temporal robust- ness, deliberately designed for periodic model updates with continuous data collection, to corroborate the usability of our temporal threat model. Considering a process of periodic model updates with continuous data collection, where is the index of the current period, use Do, Di.-.., D; to denote respectively the sets of samples collected in each all finished data collection periods. For simplicity, we use D,,t = U Dj to denote the union of D, through D,-
Definition 4.1 (Temporal Aggregation). Given a deterministic learner f that maps training set D E Dr to a classifier J' + y (i.e. a function mapping the input space X the label space ))), temporal aggregation with base coverage n and aggregation size k computes the prediction for test sample X as follows:
arg max yEy j=i-k41
Σ
1[f(z)= = v),
where fj = fDz-mes., is the base classifier obtained by applying the deterministic learner f to jjn22:..... Dj. 1[x] denotes the indicator function and ties in arg max are
the union of broken by returning the label with smaller index.
An illustration of temporal aggregation with base coverage = 2 and aggregation size k = 5 is included Figure 4 In short, for every updating period of temporal aggregation, one trains only one new base model using data collected in the last periods and uses the majority votes of the latest k base models for predictions. Such efficient updates are favorable practice.
4.2 Provable Temporal Robustness against Poisoning
Intuitively, temporal aggregation offers temporal robustness by limiting the influence of training data within certain intervals of time the aggregations at inference time. Now we present theoretical results showing its provable temporal robustness. For simplicity, we use 'period' as the unit of time in this section and use TA([Do, .., D,), .)) denote the prediction of temporal aggregation on the input x E X, assuming Du.... D, are sets of samples collected in previous periods.
Theorem 4.2 (Provable Temporal Robustness against Data Poisoning with Bounded Earliness). Let Do, Dr,..., D, be sets of samples collected in different periods, where i is the index of the current period. Let n and k be the base coverage and aggregation size of temporal aggregation. For any X, let TA.Do,.... ..., D)), For any E if for all v/ E y {v).
Σ 1+1
(x))(x) v)
Σ j=
[.,(x) = v/1 min(7, r, B) + 1 vl,
(1)

---

then we have (D:....... D. = for any D/, ....... D reachable from Du.... ... Dj after some data poisoning attack with a maximum earliness of T.
Proof. The idea of this proof is straightforward. Given maximum earliness of T, only data from the last T periods may be poisoned and thus only the last T base classifiers may behave differently after such an attack. With this observation, it is clear that the left-hand side of Inequality
1 - (z) = y] is lower bound for the number of base classifiers in the aggregation that predicts label Similarly, Ej 1 (x)
1
(x) = y/] + min(T, k) is an upper bound for the number of base classifiers in the aggregation that predicts label y'. since no more than min(T, k) base classifiers in the aggregation can be affected. The remaining term in Inequality [ 1[y > y'l is due to the tie- tie-breaking rule of temporal aggregation. Thus when Inequality I holds for y', we know TA (T......... Di]. x) + y'. Since Inequality holds for all y * y, we have TA([D....... D(]. x) and the proof is completed.
Theorem 4.3 (Provable Temporal Robustness against Data Poisoning with Bounded Duration). Let Do, Di...., Dr be sets of samples collected in different periods. where i is the index of the current period. Let n and & be the base coverage and aggregation size of temporal aggregation. For any E X, let y TA D.................
For any T E N, if for all y' y \ {y} and all E with
i i k - 1 1- S8si i,
Σ
1ff(z) = =1
Σ
[[f(()= = yl
j=strta-1
Σ (0]0x)=11++
Σ (f((x) = 5'1 + min(T + n - 1, + 1ly > 1/1 (2)
j=i-k+1
j=str+n-1
then we have TA(DD: ...... D1) = for any Do...., Dj reachable from Do...., Dj after some data poisoning allack with a maximum duration T.
Proof. With upper bound of 7 for the duration, attack cannot affect simultaneously any two periods that are at least periods away from each other, and therefore no two base classifiers that at least 7 + n 1 away from each other be both poisoned. Thus, if assuming first base classifier affected by the attack, fj with i - k + < < 1 or j 2 8 + T + n - must be free from any impact of the attack, and therefore the left-hand side of Inequality [ is natural lower bound for the number of base classifiers in the aggregation that predicts label y. In addition, since no two base classifiers that are at least T + n
is the
away from each other can be y/] Σ 2j=strtn-1 1 [f, (a) s/] + min(r + n - 1, on the right-hand side of Inequality [ becomes an upper bound for the number of base classifiers in the aggregation that predicts label y². Again, 1[y > y' is due to the tie- beebbra rule of temporal aggregation. Consequently, we know that Inequality 2 is true for a certain y' and certain s suggests TA (A( .... D.).z) 2) # y'. assuming the first base classifier affected is fs. Since it it true for all V' * y and all 8, we have TA(D",...... D!], = y and the proof is completed.
both poisoned, - 1 (z)
The key conditions used in these two theorems, Inequality [ [2] are both computationally easy given predictions from base classifies: For any sample at inference time, by simply examining the predictions from base classifiers, one can obtain lower bounds for both earliness and duration of data poisoning attacks that stand chance of changing the prediction from temporal aggregation.
Implications and applications of Theorem and 4.3:
In addition, it is worth noting that Theorem 4.2 and 4.3 do not assume whether Do...., Dj are all clean or potentially poisoned. Given that in the temporal threat model of data poisoning, DY..... D reachable from Du, D, after some poisoning attack with a maximum earliness (or duration) of r if and only if Do...., D, is also reachable from D',.... ... D/ after some poisoning attack with a maximum earliness (or duration) of т, these theorems can be applied regardless of whether the training sets are considered clean or potentially poisoned: With clean training data, we obtain lower bounds of earliness and duration required for a hypothetical poisoning attack to be effective; With potentially poisoned data, we get lower bounds of earliness and duration required for past poisoning attack be effective. this work, we apply them for evaluation of temporal aggregation on the temporal robustness benchmark from Section 3 where data are assumed poison-free.
7

---

besetinn clean BOQUEES.
besedin cleup BEOMEO
Roleat Fraddon (S4
10
Bound of Eniliress (mond)))
Usper Board Dunsion (manii)
(a) robust fraction with respect to bounded earliness
(b) robust fraction with respect bounded duration
Figure 5: An overview of the performance and temporal robustness of temporal aggregation with with base coverage f1,3, 6, 9, 12) and aggregation size & {6, 12, 18, 24]. total of 20 combinations of hyperparameters. Detailed views individual runs can found in Figure 66 and Figure
Evaluation of the Baseline Defense
5.1 Evaluation Setup
Given that the temporal robustness benchmark simulates a setting with monthly updated models, we consider each month separate period for temporal aggregation (i.e. one base classifier per month) and use 'month' as the unit of time. For the base learner (i.e. the learning of each base classifier), we feature extractor, mapping each
use the pre-trained RoBERTa 17 with a BERT-base architecture headline into a vector with 768 dimensions. We optimize a linear classification head over normalized RoBERTa features with AdamW optimizer [18] for 50 epochs, using learning rate of 1c-3 and batch size of 256. To make the base learner deterministic, we set the random seeds explicitly and disable all nondeterministic features from PyTorch [24]
5.2 Establishing Baseline Accuracy
To establish baselines for assessing the perfor- mance and temporal robustness of temporal ag-
Caregory
3
1
01
gregation, we present in Table 2 clean accuracy, ie. robust fraction from Definition 3.I with 0, of the base learner trained on varying months of latest data. Corroborating the effects of natural distribution shifts, among settings evaluated, the average clean accuracy over all categories reaches its peak when using the latest one month of data for training, thus we use the corresponding value, 54.09% as the baseline clean accuracy in our evaluation. In addition, here we observe that different categories can have different degrees of temporal distribution shifts and different data availability: For some categories including WORLD NEWS/POLITICS, training on earlier data reduces accuracy, indicating effects of temporal distribution shifts; For some categories including TRAVEL/COLLEGE, training on earlier data improves accuracy, indicating the effects from using more data.
54.09%
53.77%
53.47%
53.43%
53.15%
WORLD NEWS
59.00%
46.59%
36.79%
31.39%
25.56%
POLITICS
62.13%
57.52%
368
54.31%
53.06%
TRAVEL
$2.30%
56.65%
39.45%
6143%
62.26%
COLLEGE
42.30%
49. 49.309
51. 689
54. 20%
$7.29%
Table 2: Clean accuracy of the base learner trained the latest n months of samples.
5.3 Performance and Robustness
In Figure 5 we include an overview the performance and robustness of temporal aggregation with base coverage 3, 6, 9, 12) and aggregation size & E {6. 12, 18, 24). total of 20 combinations of hyperparameters. For clarity, we defer the study of hyperparameters to Section
From Figure 5 we observe that temporal aggregation is capable of providing decent temporal
robustness with minimal loss of clean accuracy. For example, with n = and = 24, is provably robust for sizable share (with respect to the baseline clean accuracy) of test samples against poisoning attacks that started no more than lasted for no more than 6 ~ 9 months (duration).
months in advance (earliness) and attacks that

---

2012
b417
kw1
ee0 ond
b-12
re 1-13
10
(a) n E f1,3,6, 6, 9, 12), ls 6
(b) n E 31,3, 9, 12). A: 12
Easaine
k-10
1x:44
In24
(r9 6-10
6-12
b-24
nr3 6x24
6-12
2
0
(c) n E (1,3,699 12). h= 18
(d) n (1,3, 9, 12). A: == 24
Figure 6: The effects of base coverage to the performance and temporal robustness.
Easaline OAT ACQERO
Easalits ACSUROO
and
09
1712
8 1712
Uppn Do of Ca yoor
Jpper Boandil Do ador 1o0n
Upol Bou Ca yoond)
Jpprr Doand sale moond)
(a) 12 1. E {6, 12, 18, 24}
(b) 12 3, l: E {6, 12, 18, 24)
Ievitimcc NODARO.
PCC
611
4% e112
Upon Dos of Cafinuas 1oordh
Jppnt Boancel Ca Soooor moor
Upon Doundef Cartnnus (rwrd)
Joow Dounc Do morrdh
(c) n = 6, E f6, 12, 18, 24}
(d) n = 9, E (6, 12, 18, 24}
Figure The effects of aggregation size k to the performance and temporal robustness.
5.4 Hyperparameters for Temporal Aggregation
The effects of base coverage n: In Figure 6 we compare the robust fraction of temporal aggregation with different base coverage n. Intuitively, the choice of involves a trade-off between training set size and distribution shifts: A larger n increases training set size, which is positive to clean accuracy, but also enlarges distribution shifts, as more samples from early-time will be included, which is negative to clean accuracy. In this case, however, we observe mild but negative impact from increasing n to performance, consistent with previous observations from Table again indicating the presence of strong natural distribution shifts over time. Regarding temporal robustness, Figure 6 suggests that a larger n significantly reduces temporal robustness of temporal aggregation against poisoning attacks with bounded duration, which is expected as an attacker can affect more base classifiers within the same duration.
The effects of aggregation size k: In Figure ? we present a comparison of temporal aggregation with different aggregation size ht where we observe that a larger has a rather mild negative impact on performance but greatly facilitates temporal robustness with both bounded earliness and duration. This is because, with a larger k, more base classifiers will be utilized the aggregation. On the one hand, these extra base classifiers are trained on earlier data with larger natural distribution shifts from

---

test distribution, hence the reduced clean accuracy: On the other hand, extra base classifiers dilute the impact from poisoned base classifiers to the aggregation, hence the improved robustness.
6 Related Work
The proposed defense, temporal aggregation, is inspired by aggregation-base certified defenses for the traditional modeling of data poisoning. with shared spirit of using voting for limiting the impacts of poisoned samples. [16 39 40 26 (88 assume deterministic base learners and guarantee
the stability of predictions with bounded numbers of poisoned samples. [14 6 provides probabilistic
guarantees of the same form with small, bounded error rates using potentially stochastic learners.
Discussion
Temporal Aggregation introduces little-to-none extra training cost in many practical cases. In reality with continuous data collection, a common practice is to re-train/update models using new data every once in while because model performance degrades time evolves. As mentioned in Section 44.1, to use Temporal Aggregation, one still only need to train one classifier per updating period since previous base classifiers can be reused, which incurs minimal/no extra training overhead.
The increase inference overhead can be small depending on the design of base classifiers. Naturally, using more base classifiers (i.e. using larger k) increases the inference overhead. However, the extra inference overhead can small depending on the designs base classifiers. An example design is to fine-tune only the last few layers of the model instead of training entirely from scratch. If one uses a shared, pre-trained feature extractor and only trains a task head for each base classifier (as in our Section 5). the shared feature extractor only needs to be forwarded once for inference and the extra overhead can be minimized.
Using both time and the number of poisoned samples to characterize attack budgets. While this work focuses on the benefits of incorporating temporal concepts, is worth noting that earliness and duration can be combined with the number of poisoned samples in bounding attack budgets. As an example, our baseline defense Temporal Aggregation is not only a provable defense against attacks with bounded earliness and duration but also a provable defense with respect to a bounded number of poisoned samples (when using a small base coverage n). This follows directly from previous aggregation defenses [16 39] targeting attacks with the number of poisoned samples bounded.
Potential opportunities for other defenses. The temporal threat model of data poisoning may offer new angles to improve the usability of existing poisoning defenses for different stages. For
detection- based defenses [3 25
targeting the early stages where the models have not been trained, the temporal threat model may delay the success of poisoning attacks and allow detection- poisoned samples after the attack succeeds [31] which targets later stages where the models have been deployed. If one can reverse poisoning attacks shortly after they succeed, incorporating the temporal threat model can help to prolong every attack process and may eventually ensure a low exploitability of poisoning attacks.
34
37
23
44
defenses to operate on more data. Another promising direction is to locate
8 Conclusion
Incorporating timestamps of samples that are often available but neglected in the past, we provide a novel, temporal modeling of data poisoning. With our temporal modeling, we derive notions of temporal robustness that offer meaningful protections even with unbounded amounts of poisoned samples, which never possible with traditional modelings. We design a temporal robustness benchmark to support empirical evaluations of the proposed robustness notions. We propose temporal aggregation, an effective baseline defense with provable temporal robustness. Evaluation verifies its temporal robustness against data poisoning and highlights the potential of the temporal threat model.
10

---

Acknowledgements
This project was supported in part by Meta grant 23010098, NSF CAREER AWARD 1942230, HR001 19S0026 (GARD), ONR YIP award N00014-22-1-2271, Army Grant No. INF22220007 NIST 60NANB20D134, the NSF award CCF2212458, a capital one grant and an Amazon Research Award.
References
[1] Hojjat Aghakhani, Dongyu Meng, Yu-Xiang Wang, Christopher Kruegel, and Giovanni Vigna. Bullseye polytope: A scalable clean-label poisoning attack with improved transferability. In IEEE European Symposium on Security and Privacy, EuroS&P 2021, Vienna, Austria, September 10, 2021, pages 159-178. IEEE, 2021. doi: 10.1 (t9////mmSSS119222220000002 htt.:httpp://ii /doi org/ / 10. oSt.9/ www../511199222220022222222
[2] Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. In Proceedings of the 29th International Conference Machine Learning. ICML 2012, Edinburgh, Scotland, UK. June 26 July 1, 2012. ieml.cc/ / Omnipress, 2012. URL
http:///cmm.cccc211////eaa/ http:////00//ppprr//80.0.000 pdf
[3] Nicholas Carlini. Poisoning the unlabeled dataset of semi-supervised learning. In Michael Bailey and Rachel Greenstadt, editors, 30th USENIX Security Symposium, USENIX Security 2021, August 11-13, 2021, pages 1577-1592. USENIX Association, 2021. BRLLhttps:/ //www usenix. org/
car htt.r/ettttatttoooaaaiiiiiiiiiee poissonigg
[4] Nicholas Carlini and Andreas Terzis. Poisoning and backdooring contrastive learning. In The Tenth International Conference Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL https:///pperrerieet net/forum?id
iCAUHbQ01Kp
[5] Nicholas Carlini, Matthew Jagielski, Christopher A. Phoquette-Choo Daniel Paleka, Will Pearce, Hyrum Anderson, Andreas Terzis, Kurt Thomas, and Florian Tramèr. Poisoning web- scale training datasets practical. CoRR, abs/2302. 10149, 2023, doi: 10.4850/ARXIV.230..
10149. URL httLhttt::/ddee org/10. 4.0.45555//rii 2302 10149
[6] Ruoxin Chen, Jie Li, Chentao Wu, Bin Sheng, and Ping Li. A framework of randomized selection based certified defenses against data poisoning attacks. CoRR, abs/2009.08734 2020. httpt://t///rttt org/ abs///////// 08739
[7] Ruoxin Chen, Zenan Li, Jie Li, Junchi Yan, and Chentao Wu. On collective robustness of bagging against data poisoning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Ma- chine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 3299-3319, PMLR, 2022. URL
https://proceeddngss mlr ppwss/v16/ chen22k. 2rress/. html
[8] Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks 2017. URL http!
on deep learning systems using data poisoning. CoRR,
// //aaxiv..oo org/ abs/ 1111/111100 05526
[9] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart. Sever: A robust algo-itgo for stochastic optimization. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 1596-1606. PMLR, 2019. http:tttt:///pceeeeiiie mlr. wwwppresssvviee http://///daaaaikkkaooaoooo 19a. html
[10] Jonas Geiping, Liam H. Fowl, W. Ronny Huang, Wojciech Czaja, Gavin Taylor, Michael Moeller, and Tom Goldstein. Witches' brew: Industrial scale data poisoning via gradient matching. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.nee, 2021. URL. ttttps://openreveee net/

---

[11] Micah Goldblum, Dimitris Tsipras, Chulin Xie, Xinyun Chen, Avi Schwarzschild, Dawn Song, Aleksander Madry, Bo Li, and Tom Goldstein. Dataset security for machine learning: Data poisoning, backdoor attacks, and defenses. CoRR, abs/2012.10544, 2020. URL https
//arxiv.org/aant 2012. 10544
[12] Sanghyun Hong, Varun Chandrasekaran, Yigitcan Kaya, Tudor Dumitras, and Nicolas Paper- not. On the effectiveness of mitigating data poisoning attacks with gradient shaping. CoRR, abs/2002. 14997, 1497, 2020. URL pattts://arxxxr wwweriii.o..ooooeoooooooo hwtg/ab//2002... 11497
[13] Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of nearest neighbors against data poisoning attacks. CoRR, abs/2012.03765, 2020. URL https://arxiv, org/ aba/2012 03765
[14] Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong, Intrinsic certified robustness of bagging against data poisoning attacks. In Thirty-Fifth AAAI Conference on Artificial Intelligence,
AAAI 2021, Phirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAl
2021, Virtual Event, February 2-9, 2021, pages 7961-7969 AAAI Press, 2021. URL.https
7/ojs. aaai. wwwo/oinneeeeeoe..oo php/ AAAI/ http://rttiieeeeeeeeeeeeeeeeeeee 16971
[15] Pang Wei Koh, Jacob Steinhardt, and Percy Liang. Stronger data poisoning attacks break data sanitization defenses. Mach. Learn., 111(1):1-47, 2022. doi: 10. 10.1007/1109944021-000111
URL httpttttp///oioooo
[16] Alexander Levine and Soheil Feizi Deep partition aggregation: Provable defenses against general poisoning attacks. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[17] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: robustly optimized bert pretraining approach. arXiv preprint arXiv: /907. 1692, 2019.
[18] Iya Loshchilov and Frank Hutter. Fixing weight decay regularization in adam. CoRR, abs/1711.051011 2017. URL http:://axxii....////// org/ abs wttp///wwww..or/////.....111 05101
[19] Yuzhe Ma, Xiaojin Zhu, and Justin Hsu. Data poisoning against differentially-prrinn learners: Attacks and defenses. In Sarit Kraus, editor, Proceedings of the TieettyFFigth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 4732 4738. ijeai.org, 2019. doi: (0.249633/jcai..2199666 /tL/attps:///oi..rr 24963/1jcai. 2208///7 2019/657
[20] Rishabh Misra. News category dataset. CoRR, abs/2209.112999. 2022. doi: 10.48550/arXiv. 1209.11429. URL [ttps::/ddoi www.:/i...rro.o1/ 2/550/1044555////a11..
11429
[21] Rishabh Misra and Jigyasa Grover. Sculpting Data ML: The first act of Machine Leurning.
01 2021. ISBN 9798585463570.
[22] Luis Muñoz-González, Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongras- samee, Emil C. Lupu, and Fabio Roli. Towards poisoning of deep learning algorithms with back-gradiese gradient optimization. In Bhavani Thuraisingham, Battista Biggio. David Man- dell Freeman, Brad Miller, and Arunesh Sinha, editors, Proceedings of the 10th ACM Work- shop Artificial Intelligence and Security, AlSec CCS 2017, Dallas, TX, USA, Novem- ber 3, 20/7 pages 27-38. ACM, 2017. doi: 10.1145/3128572.3144444 URL httpss //doi.org// 10. 1145 011128877.3144455
[23] Minzhou Pan, Yi Zeng, Lingjuan Lyu, Xue Lin, and Ruoxi Jia. ASSET: robust backdoor data detection across multiplicity of deep learning paradigms. CoRR, 0tbs/2302.11408 2023. doi: 10.485500/rXiw.22000 1408. //ttss///ooo org/10. 11w111....588888 arw.v. 2302. 11408
[24] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style,
12

---

high-performancee deep learning library. CoRR, abs/1912.01703, 2019. URL http://arxx org/abs//112.01703
[25] Andrea Paudice, Luis Muñoz-Gonzällle András György, and Emil C. Lupu. Detection of adver- sarial training examples in poisoning attacks through anomaly detection. CoRR, 100.00044,
2018.
URL BtLLhhttp///xxix http:p///aarii.orrraa/////////// wwrrg/abs18002 03041
[26] Keivan Rezaei, Kiarash Banihashem, Atoosa Malemir Chegini, and Soheil Feizi. Run-off election: Improved provable defense against data poisoning attacks. CoRR, abs/2302.02300, 2023. doi: 10.48550/arXXx.220022223 02300
htlphttts://doo org/ 10. 48550/arXiv 2302
[27] Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and J. Zico Kolter. Certified robustness to label-flpping attacks via randomized smoothing. In Proceedings of the 37th International
Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 6230-8241. PMLR, 2020. URL/htpp/ Ftress/v19///e http///111//1//eeeeee eld20b. html
//proceedings. www.preess/eee
[28] Benjamin IP Rubinstein, Blaine Nelson, Ling Huang, Anthony D Joseph, Shing- hon Lau, Satish Rao, and Nina Taft. Antidote: understanding and defending against poisoning of anomaly detectors. In Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement, pages 1-14, 2009.
[29]
Aniruddha Saha, Akshayvarun Subramanya, and Hamed Pirsiavash. Hidden trigger backdoor attacks. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Secone Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances Artificial Intelligence, EAA/ 2020, New York, NY, USA, February 7-12, 2020, pages 11957-11965. AAAI Press, 2020. URL https //aaai. org/ www/o///g//o///oooooooooooo/eo// wws//ndex...//o//ooo/oooeeo.oiam php/ whtppppppppapapaapppptwatwpaaa WtW.///aat.eeeee//////aaa
[30]
Ali Shafahi, W. Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumi- tras, and Tom Goldstein. Poison frogs! targeted clean-label poisoning attacks on neural networks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 6106 6116, 2018. URL http: ineuru neurips cc/ cc/paper// / 2018 B/was//haahhaae hwwhhhhhhhh2222 2ttpe/2222222331332 14006667776111666666666666
html
[31] Shawn Shan, Arjun Nitin Bhagoji, Haitao Zheng, and Ben Y Zhao. Poison forensics: Traceback of data poisoning attacks in neural networks. In 31st USENIX Security Symposium (USENIX Security 22), pages 3575-3592, 2022.
[32] Hossein Souri, Micah Goldblum, Liam Fowl, Rama Chellappa, and Tom Goldstein. Sleeper agent: Scalable hidden trigger backdoors for neural networks trained from scratch. CoRR, 00/22106.08970, 2021. URL htttps://arxiii org/ abs///bs///21 2116//06000000000
[33] Jacob Steinhardt, Pang Wei Koh, and Percy Liang. Certified defenses for data poisoning attacks. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 351 3517-3529292 2017, URL https: http::/://///pc/eoee/eeeee neurips cc/ paper/ 2017 hht.hhash//aaa wataash////// /ttp////31111t/ httaaa/eeee.aaaaaaoooooooo76766a Abst-Attsttattttaaaao
[34] Brandon Tran, Jerry Li, and Aleksander Madry. Spectral signatures in backdoor attacks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NewrlPS 2018, December 3-8, 2018, Montréal, Canada, pages 10021, 2018. URL httphhhttpp://prrcdddingg neurips cc ccc/pape//25 http///20////hh//aeee 044a9702888844444222222222276443
[35] Alexander Turner, Dimitris Tsipras, and Aleksander Madry. Label-consistent backdoor attacks. CoRR, 192.0777,, URL http:://rxxix
13

---

[36] Binghui Wang, Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. On certifying robustness against backdoor attacks via randomized smoothing. CoRR, abs/2002.11750. 2020. URL
https://arxixs http:://wwxvv..rr//../// org/ abs/202.. 11750
[37] Bolun Wang. Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Y. Zhao. Neural cleanse: Identifying and mitigating backdoor attacks in neural networks. In 2019 IEEE Symposium Security and Privacy. SP 2019, San Francisco, CA, USA. May 19-23, 2019, pages 707-723, IEEE, 2019. doi: 10.1109/5P2219.000011 URL https://doi. org/10. 1109/SP 2019.00031
[38] Wenxiao Wang and Soheil Feizi. On practical aspects of aggregation defenses against data poisoning attacks, 2023.
[39] Wenxiao Wang, Alexander Levine, and Soheil Feizi. Improved certified defenses against data poisoning with (deterministic) finite aggregation. CoRR, abs/2202.02628, 2022.
[40] Wenxiao Wang, Alexander Levine, and Soheil Feizi. Lethal dose conjecture on data poisoning. |ttps:s/:://ooi
CoRR, abs/2208.0333333 2022, doi: 10.48550/axx..2208..33333 18550/arXiv. 2ww.2222880038
[41] Maurice Weber, Xiaojun Xu, Bojan Karlas, Ce Zhang, and Bo Li. RAB: provable robustness against backdoor attacks. CoRR, abs/2003.08904, 2020. URL httpp::/aaxxi...rrrrr/re/ /abs/ 2003 08900
robustttcrbbusnssss
[42] Yi Zeng, Si Chen, Won Park, Z. Morley Mao, Ming Jin, and Ruoxi Jia. Adversarial unlearning of backdoors via implicit hypergradient. CoRR, abs/2110.00335,, 2021. URL https://arxiv
org/abs/2110.06
237.03335
[43] Yi Zeng, Won Park, Z. Morley Mao, and Ruoxi Jia. Rethinking the backdoor attacks' triggers: frequency perspective. CoRR, abs/2104.03413, 2021. httpt/ttt////iiiia abs/
[44] Yi Zeng, Minzhou Pan, Himanshu Jahagirdar, Ming Jin, Lingjuan Lyu, and Ruoxi Jia. How to sift out a clean data subset in the presence of data poisoning? CoRR, abs/2210.06516 2022. doi: 00.48550/rxii.22100.00
https://://d org/ 10. 48550/ arviv 2210. 06516
[45] Yi Zeng, Minzhou Pan, Hoang Anh Just, Lingjuan Lyu, Meikang Qiu, and Ruoxi Jia. Narcissus: A practical clean-label backdoor attack with limited information. CoRR, abs/2204.05253 05555, 2022, doi: 10.48550/arXiv.2205 22..:a......22.0.22222 05255.. URL httts::/t/o::i org/ 10. 48w.44455/aa555 2204. 05255
[46] Chen Zhu, W. Ronny Huang, Hengduo Li, Gavin Taylor, Christoph Studer, and Tom Goldstein. Transferable clean-label poisoning attacks on deep neural nets. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 761 7614-7623. PMLR, 2019. URL /ppp:p///cocceenss mlr. press/v97 /t////uu119 html
14


Reviews:
[{"review_id": "eeb9uNe3nd", "reviewer": "Reviewer_NyPv", "summary": "The paper considers \"temporal robustness\", an extension to traditional data poisoning threat models which considers the \"birthdate\" of training examples. This extension gives more power to a defender, by permitting defenses against adversaries limited in the duration or earliness of their attack. The paper proposes a simple defense, temporal aggregation, which provides provable temporal robustness, and evaluates it on a benchmark derived from the News Category dataset.\n\nI appreciate the authors' response and will keep my score.", "questions": "I've left multiple questions in the strengths and weaknesses section. Here's a summary:\n\n1. Can bounded earliness defenses be simpler by never considering the samples after the earliness threshold?\n\n2. When is assumption 4.2 needed? Are there any modifications of it that would also make sense?", "limitations": "There isn't really discussion of limitations in the paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper proposes an interesting, well thought out threat model. I enjoyed reading section 2. One comment is that it is unclear when assumption 4.2 is used. Are there other versions of Section 4.2 that might be possible in different applications, or does modifying the assumption in any way prevent any guarantees?\n\nTemporal aggregation is a natural defense here. Figure 4 is a nice description of the technique.\n\nThe threat model seems nicely amenable to the continual training setting, and I'd enjoy reading followup applying it there.", "weaknesses": "There is only one dataset. I appreciate that the setting necessitates constructing new benchmarks, but the ultimate benchmark here seems to be not enough to promote future research. I would encourage the authors to think about what properties of a temporal robustness benchmark could make defenses challenging, or more straightforward. After thinking briefly, some that come to mind are seasonality in the data, and distribution drift. Larger amounts of both seem like they could make attacks easier, and it would be interesting to evaluate benchmarks with differing levels of both properties. Right now, it doesn't appear that either property is present, given the very small amount of performance degradation when training on other months' data.\n\nThe paper provides limited motivation about temporally bounded adversaries. While the idea of birthdates is very natural, and their existence is well motivated in the paper, it's not very clear from the paper why an adversary would have a bounded duration. I can imagine more settings with bounded earliness, but the paper should still include examples. This also is reflected in the benchmark, which doesn't really justify why this setting might run into temporal robustness.\n\nTemporal aggregation seems to be overkill for a bounded earliness adversary. Why not just train on all but the last tau sections of the dataset? Then you wouldn't need the min(tau, k) term.\n\nComments:\n\nThe Antidote paper [x1] considers temporally bounded adversaries. There is a recent paper [x2] on poisoning web datasets which considers temporally bounded adversaries which may be of interest.\n\nPlease don't use [xx] to cite, prefer e.g. \"Jia et al. [11] do xxx\" to \"[11] do xxx\".\n\nAssumption 2.4 is used in Definition 2.3, before the assumption is introduced.\n\n[x1] - https://dl.acm.org/doi/pdf/10.1145/1644893.1644895\n\n[x2] - https://arxiv.org/abs/2302.10149", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you! We are glad that you find our threat model interesting and well thought out. Our answers to your questions are as follows and **we will incorporate them in our paper as they can be interesting to future readers as well**.\n\n**1. distribution drift in the benchmark:**\n\nThe benchmark we presented is in fact rich in distribution drifts. In the paper, we presented in Figure 3 the changes of category presences in different months as support, and we add more evidence here to explain why ‘*the very small amount of performance degradation when training on other months' data*’ does not mean missing distribution drifts.\n\nHere we have the accuracy of the based learner trained on the latest n months with varying n, but evaluated on individual categories:\n\n| Category | n=1 | n=3 | n=6 | n=9 | n=12 |\n|:----------:|:------:|:------:|:------:|:------:|:------:|\n| WORLD NEWS | 59.00% | 46.59% | 36.79% | 31.39% | 25.56% |\n| POLITICS | 62.13% | 57.52% | 55.36% | 54.31% | 53.96% |\n|      |    |    |    |    |    |\n| TRAVEL  | 52.30% | 56.65% | 59.46% | 61.63% | 62.26% |\n| COLLEGE  | 42.30% | 49.30% | 51.68% | 54.20% | 57.28% |\n\nHere we see that for categories WORLD NEWS/POLITICS, training on earlier data reduces accuracy, indicating distribution drifts; for categories TRAVEL/COLLEGE, training on earlier data improves accuracy, where the increase of data contributes primarily. Thus the mild degradation of accuracy in Table 2 is a joint effect of both natural distribution drifts and varying numbers of data (i.e. data quality v.s. data quantity). \n\nWe will include these (and other) per-class accuracies and the discussions in our paper to better illustrate the distribution shifts in our benchmark. Thank you for bringing it up!\n\n\n**2. motivations about temporally bounded adversaries**\n\nConceptually, the main motivation for considering temporally bounded adversaries is that time is an important and limited resource, thus as humans, assuming the same rewards, our instincts would prefer instant rewards over rewards that require waiting and would prefer rewards that require less time of work than rewards that require more time of work, especially if the scales come to months or years. \n\nIn the case of poisoning, for attackers, the easier target is probably a system that can be broken soon rather than a system that won’t be broken for at least another several months (hopefully years with more progress in temporal defenses). This motivates the use of earliness.\n\nMeanwhile, if the target system is not robust to attacks that end promptly, one can poison enough samples shortly and then just wait. But if the defense is robust to attacks with bounded durations, the attacker would have to put effort for a longer time range (e.g. poison some samples for more months). We believe ‘duration’ characterizes such preference.\n\nIn addition, while the threat model is new, existing attacks usually are bounded temporally since it always takes time to make attacks earlier or longer (no shortcut). In fact, the additional references [x1, x2] you provided that involve temporally bounded attackers can be helpful as a background. We will discuss them in the paper.\n\nFor the benchmark, we select the News Category Dataset mostly due to its natural distribution shifts over time. Classifying the categories of news is indeed not typically considered a critical task that can result in serious damages after being attacked. However, since similar situations apply to other benchmarks used in data poisoning such as MNIST, CIFAR-10, and GTSRB, we believe our benchmark is a good start for research purposes. We will look into ways to construct better benchmarks in future work.\n\n**3. Can bounded earliness defenses be simpler by never considering the samples after the earliness threshold?**\n\nThe goal of the temporal threat model is to utilize temporal concepts to raise the attack cost (i.e. time spent on poisoning and waiting). While ignoring the latest samples is a simpler defense for poisoning attacks with bounded earliness, it is potentially vulnerable to attacks with small durations, i.e. an attack may inject enough poisoning samples shortly and wait for the defense to be broken.\n\nOn the other hand, the baseline defense we have in our paper is in fact a single solution (and we believe it is fairly simple) serving as provable defenses with respect to two budgets, earliness and duration, i.e. an attack must have both sufficient earliness (starts early enough) and sufficient duration (lasts long enough) in order to have a chance of breaking the defense. \n\nIn addition, our baseline defense is also a provable defense with a bounded number of poisoned samples when using small n, which follows directly from previous aggregation defenses like DPA [13] for existing poisoning threat models. This is an additional advantage compared to simply ignoring the latest samples.\n\n[13] Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defenses against general poisoning attacks. ICLR 2021\n\n**4. Regarding assumption 2.4**\n\nIn assumption 2.4, we assume the attacker has no capability to directly set the birth dates of samples. The role of assumption 2.4 is to connect the temporal metrics of attacks (i.e. earliness and duration) with the actual cost of attackers: If an attacker wants to increase the earliness or duration of its attack, it has to actually start early or poison for a longer period. \n\nWhile we believe assumption 2.4 is natural and practical, it is not the only working assumption. For example, the threat model remains meaningful if the attacker can set the timestamps but there are some constraints on the values (e.g. it cannot be too far away from the actual time).\n\n**For your comments:** Thank you for providing additional references and suggestions for paper formatting. We will include them in our paper.\n\n**Thanks again for your services. We look forward to hearing your comments on our answers and welcome any follow-up.**\n\n"}, {"review_id": "J1ZINL2b7W", "reviewer": "Reviewer_TaU1", "summary": "The paper discusses the concept of data poisoning, wherein adversaries manipulate machine learning algorithms through the inclusion of malicious training data. The existing threat models in this domain primarily revolve around a single metric, namely the number of poisoned samples. However, if attackers can introduce a greater number of poisoned samples than expected, while incurring reasonable overhead, they can swiftly render existing defense mechanisms ineffective. In order to address this challenge, the authors propose leveraging timestamps associated with the creation dates of data, which have been overlooked in prior research. By capitalizing on these timestamps, the authors introduce a temporal threat model for data poisoning, introducing two novel metrics: earliness and duration. The earliness metric measures the time interval before an attack is initiated, while the duration metric quantifies the duration of an attack. By utilizing these metrics, the authors define the concept of temporal robustness against data poisoning, which offers meaningful protection even in scenarios with an unrestricted number of poisoned samples. To facilitate empirical evaluation of temporal robustness, the authors present a benchmark with an evaluation protocol that emulates continuous data collection and periodic deployment of updated models. Finally, the authors propose and empirically verify a baseline defense mechanism called temporal aggregation, which provides verifiable temporal robustness and underscores the potential of the proposed temporal threat model in combating data poisoning.", "questions": "Please kindly refer to the comments in limitations.", "limitations": "- The practicality of the threat model requires further evaluation. \n     - First, this paper emphasizes temporal data poisoning and considers long-term poisoning attacks on ML models by adversaries within reasonable overhead. However, it would be helpful to provide a bit more context on the practical scenarios in which affordable overhead allows attackers to poison more samples than expected. Elaborating on such scenarios would enhance the understanding of the problem's significance. \n    - Second, the authors need to further elaborate on the background of the attacker, the knowledge of the attacker, the limitations of the attacker, and the capabilities of the attacker. \n    - Last, the reviewer is a bit curious about how an adversary can achieve continuous poisoning data injection without the timestamp being disturbed by other data sources. For example, when the adversary is injecting poisoned data according to the timestamp, other benign users are also inserting data. In this case, can it be understood that the poisoned data has been diluted? If the above assumptions are true, such an attack seems to be difficult to pose a substantial threat to the ML model.\n\n-  Evaluations are still incomplete in terms of attack strategies and benchmark datasets. This paper uses the News Category Dataset to evaluate the robustness of temporal data poisoning. Such an approach has the following limitations: \n    - First, in order to more fully evaluate the robustness of temporal data poisoning, the authors should add more benchmark datasets to verify the authors' claims. \n    - Second, the reviewers are more curious about whether the time series data set can better evaluate temporal data poisoning, such as IoT time series data, financial time series data, etc. \n    - Last, did the authors consider extreme cases such as continuous and long-term poisoning data injection by an adversary? The reason is that this can experimentally illustrate the bounds of the robustness of temporal data poisoning.\n\n- The novelty of the designed defense strategy still needs to be further strengthened. Although the temporal aggregation proposed in this paper is a baseline solution, there are still the following problems to be solved:\n    - First, in order to more comprehensively verify the provable temporal robustness of temporal data poisoning, the authors should consider multiple naive schemes, such as validation set testing, ensemble learning, weighted aggregation, etc.\n    - Second, the paper still lacks an evaluation of edge cases, which is helpful to understand the limits of defense schemes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ An interesting and novel temporal threat model for data poisoning is formalized and proposed.\n+ Two new metrics, earlyness and duration, are designed to represent the temporality of data poisoning.\n+ Tailor the concept of temporal robustness to data poisoning and develop and empirically validate a baseline defense, temporal aggregation.\n+ Provides a comprehensive benchmark evaluation for temporal data poisoning.", "weaknesses": "- The practicality of the threat model requires further evaluation.\n- Evaluations are still incomplete in terms of attack strategies and benchmark datasets.\n- The rationality of the attack scenario still needs further clarification.\n- The novelty of the designed defense strategy still needs to be further strengthened.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for reviewing. We are glad that you find the threat model interesting. Meanwhile, there may be misunderstandings since our work does **NOT** involve *making poisoning attacks long-term so that there will be more and more poisoned samples over time to break defenses*. Thus we want to recap our contributions briefly.\n\n>**Recap of contributions**\n>\n>\n>The purpose of this work is to propose a **new threat model** for defenses against data poisoning. Most existing threat models use the number of poisoned samples for attack budgets. What we do is measure the attacker’s effort by **how early when the attack started** (earliness) and **how long the attack lasted** (duration), so that we have other tools when the number of poisoned samples is insufficient to characterize the efforts of the attackers.\n>\n>\n>Then we define robustness notions similarly to existing threat models by replacing attack budgets with upper bounds for earliness and duration. We design a benchmark for empirical evaluations and propose a baseline defense to show that such robustness is achievable.\n>\n>\n>**In short**, we are proposing a new threat model for cases that are particularly challenging to the existing ones, with its usability supported by both an empirical benchmark and a certifiably robust baseline defense.\n\nWe believe some of your questions should be naturally resolved with this clarification, and we will address the others for you.\n\n**1. practicality of the threat model**\n\n**1.1. the significance**\n\nThe need for new metrics of attack budgets originates from the difficulty of defending against poisoning attacks relying on the old metric, i.e. the number of poisoned samples. The issue here is that the numbers of poisoned samples we can tolerate are still limited that requiring attackers to poison more samples than we can tolerate may not enforce much cost to them. \nThis is supported both theoretically [1] and empirically [2, 3, 4] by existing work. \n\n[1] Wang et.al., Lethal Dose Conjecture on Data Poisoning.\n\n[2] Souri et.al., Sleeper Agent: Scalable Hidden Trigger Backdoors for Neural Networks Trained from Scratch. \n\n[3] Geiping et.al., Witches' Brew: Industrial Scale Data Poisoning via Gradient Matching.\n\n[4] Carlini et.al., Poisoning Web-Scale Training Datasets is Practical.\n\n**1.2. on the knowledge/capabilities of the attacker**\n\nAs we mentioned above in the essence of our work, we are proposing new metrics of attack budgets for defenses of data poisoning. Thus regarding assumptions on the attacker’s knowledge and capabilities, the proposed threat model is in fact compatible with most (if not all) settings from existing data poisoning threat models, i.e. one can also consider attackers with varying knowledge of the defenses/tasks/data and varying resources. \n\nFor the baseline defense, as we prove in Section 4, it is robust to all attacks with bounded earliness/duration, regardless of the knowledge/resources of the attackers.\n\n**2. 'Evaluations are still incomplete'**\n\n**2.1 attack strategies and benchmarks** \n\nRecall in our recap that the main goal of the baseline defense is to show that the temporal robustness notions can be provided. Since it is a certified defense, one can compute the minimal attack budgets (earliness and duration in this case) for **any** attack to have a chance of breaking it. Thus following existing work with certified defenses(e.g. [3, 11, 13, 23, 33, 34] cited in the paper), we evaluate their certified accuracy/fraction (robust fraction in our paper) rather than against specific attack methods.\n\nRegarding benchmarks, since this is a brand new threat model for data poisoning, there was no existing benchmark available. We construct a benchmark for empirical evaluations from the News Category Dataset due to both its availability and its natural distribution shifts over time. We believe our benchmark is a good start for research purposes but we will look into ways to construct better benchmarks in future work.\n\n**2.2 whether the time series data set can better evaluate temporal data poisoning** \n\nAlthough the time series data naturally involves temporal concepts, they are different from the timestamps we incorporate here in the temporal threat model of data poisoning (i.e. timestamps denoting the birth dates of individual samples). Thus while the temporal threat model applies to tasks with time series data if the data collection process can associate each sample with its birth date, existing time series datasets are not necessarily better candidates for research benchmarks than what we have already. We would like to hear your insight if possible.\n\n**3. novelty of the designed defense strategy**\n\nWe argue that the novelty of the baseline defense is not the key contribution of this work, in fact, the technique itself is primarily adapted from aggregation defenses in the existing threat model of data poisoning, with minimal modifications. The major novelty of this work is from the novel threat model of data poisoning that utilizes temporal concepts, and the simple baseline defense supports the threat model by showing that (provable) temporal robustness is achievable.\n\n**3.1 'should consider multiple naive schemes, such as validation set testing, ensemble learning, weighted aggregation, etc.'** \n\nWe are not sure how to interpret these terms as naive schemes for temporal poisoning robustness. Could you please elaborate more?\n\n**3.2 'lacks an evaluation of edge cases'**\n\nAs clarified earlier, since the baseline defense is provable, one can compute the minimal attack budgets (earliness and duration in this case) for **any** attack to have a chance of breaking it. Thus following existing work with certified defenses(e.g. [3, 11, 13, 23, 33, 34] cited in the paper), we evaluate certified accuracy/fraction (robust fraction in our paper) rather than against specific attack methods.\n\n**Thanks again for your review.**\n\n**Please let us know if any of your questions/concerns remain after rebuttal.**"}, {"review_id": "aylkMzeDo1", "reviewer": "Reviewer_EzrD", "summary": "This paper considers temporal information for data poisoning attacks, i.e., when an attack is crafted, and how long it lasts. The authors further propose a temporal aggregation defense (similar to data aggregation defenses), which relies on training a number of base classifiers (on data within a certain period of time), such that the aggregation of clean classifiers would outweigh that of poisoned classifiers to assure robustness of a specific test sample. ", "questions": "Please see my questions in the above section.", "limitations": "Limitations are not addressed. ", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- the idea of considering birthdates and duration of data samples is interesting;\n- Figure 1 and Figure 4 clearly illustrate the main idea of this paper;\n- The temporal aggregation algorithm is a simple but intriguing idea.\n\n\n", "weaknesses": "**Practicality of the temporal aggregation defense**: \n- It seems that training many base classifiers is quite expensive, especially on large models and datasets. I am wondering if there is a trade-off between extra time costs and certified robustness with respect to the choice of $n$ and $k$?\n- Similar to the data aggregation algorithm, I assume that the temporal aggregation algorithm might also reduce the final test accuracy. However, in the experiments, the authors do not show \"clean\" accuracy (i.e., normal training on the entire dataset) and I do not see a clear comparison or tradeoff. \n- Following the above question, Table 2 indeed shows an accuracy $\\approx 50$%. Is this the normal result you would get by training on this dataset? In this case, the results on a weak classifier seem not very convincing to me.\n\n**Experiments do not verify all the claims**:\n- The authors claim that \"temporal aggregation provides protection against unbounded amounts of poisoned samples\". This seems not true as the defense would only succeed (or provide certified robustness) if the number of clean base classifiers outweighs that of poisoned classifiers. If there are infinite poisoned samples (thus your training set contains poisoned data only in the extreme case), we can easily verify that temporal aggregation would not provide any protection. \n- In Figures 5 and 6, it seems that the proposed algorithm can only certify 60% of the test data at most, which is also contradictory to the \"unbounded\" claim.\n- From lines 275-278, the authors say \"it Is provably robust...\", what do you mean by provably robust in this case? Does a 60% robust fraction count as provably robust?\n- Finally, the authors claim to study data poisoning attacks but do not examine the defense against any real attacks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you! Glad to know that the ideas about birth dates of data are found interesting and our baseline defense is considered simple and intriguing. We also appreciate your questions as they indicate where we can improve our presentations. Below are our answers.\n\n**1. Practicality of the temporal aggregation defense**\n\n**1.1 ‘trade-off between extra time costs and certified robustness to n and k?’**\n\nThe message is three-fold: \n>(1) The baseline defense introduces little-to-none extra training cost in many practical cases; \n>\n>(2) Overall, using more base classifiers tends to improve certified robustness while increasing inference overhead; \n>\n>(3) The increase of inference overhead can be small depending on the design of base classifiers (e.g. a shared pre-trained feature extractor + different task heads for different base classifiers).\n\n(1) For training cost: In reality with continuous data collection, a common practice is to re-train/update models using new data every once in a while because the old models’ performance degrades as time evolves. As we mentioned in lines 190-192 of the paper, one only needs to train one new base classifier per updating period since most of the previous base classifiers can be reused, which incurs minimal/no extra training overhead.\n\n(2) As discussed in Section 5.4, the choice of n involves a trade-off between training set size and distribution shifts (supported by Figure 6) and a larger k tends to improve certified robustness (supported by Figure 7). Meanwhile, a larger k indeed increases the inference overhead as we use more base classifiers.\n\n(3) However, the extra inference overhead can be small depending on the designs. For instance, another common practice is to fine-tune only the last few layers of the model instead of re-training entirely from scratch. If one uses a shared, pre-trained feature extractor and only trains a task head for each base classifier (as we do in our experiments), the shared feature extractor only needs to be forwarded once for inference, minimizing the extra overhead.\n\nWhile the baseline defense is already practical to some extent, we agree that it is not yet ideal and look forward to improvements. We will discuss these in the paper.\n\n**1.2 ‘do not show \"clean\" accuracy'; 'do not see a clear comparison or tradeoff’; ‘the results on a weak classifier**\n\nWe apologize for the confusion but we do include the clean accuracy, labeled ‘ baseline clean accuracy’ in Figure 5,6,7 and we discuss it in Section 5.2 and Table 2. \n\nRegarding the ‘low’ accuracy, it attributes to the task difficulty rather than ‘a weak classifier’.\nFirst, for your reference, we provide the performance obtained by others on an **easier** version of this dataset. In [1], they only keep the 11 categories that appear in all years out of a total of 41 categories, and the best accuracies among the 11 methods evaluated are about 70% (Table 2 in [1]). While this is not directly comparable to our numbers because we include all 41 categories and the evaluation protocols vary, it supports the claim that the News Category dataset is challenging.\n\nWhy is this challenging? It can be the distribution shifts, which is also partially why the trade-off is different from other data aggregations. Here we have the accuracy of the based learner trained on the latest n months evaluated on individual categories (also included in another rebuttal):\n\n| Category | n=1 | n=3 | n=6 | n=9 | n=12 |\n|:----------:|:------:|:------:|:------:|:------:|:------:|\n| WORLD NEWS | 59.00% | 46.59% | 36.79% | 31.39% | 25.56% |\n| POLITICS | 62.13% | 57.52% | 55.36% | 54.31% | 53.96% |\n|   |  |  |  |  |  |\n| TRAVEL | 52.30% | 56.65% | 59.46% | 61.63% | 62.26% |\n| COLLEGE | 42.30% | 49.30% | 51.68% | 54.20% | 57.28% |\n\nHere we see that for categories WORLD NEWS/POLITICS, training on earlier data reduces accuracy, indicating distribution drifts; for categories TRAVEL/COLLEGE, training on earlier data improves accuracy, where the increase of data contributes primarily. The diversity among different categories also increases the difficulty for learners. \n\nIn addition, since the category of this dataset is in fact where the news is published, there can be more than one proper category, which also increases the difficulty. \n\n[1] Yao et al. Wild-time: A benchmark of in-the-wild distribution shift over time. https://arxiv.org/abs/2211.14238\n\n**2. Experiments do not verify all the claims: ‘against unbounded amounts of poisoned samples’; ‘what do you mean by provably robust’; ‘do not examine the defense against any real attacks’;…**\n\nIn our threat model, we introduce earliness and duration to measure attack budgets, which are parallel to the number of poisoned samples. As we proved in Section 4.2, the baseline defense is provably robust (i.e. its prediction will not change) against poisoning attacks as long as the attacks’ earliness/duration is bounded by certain amounts. Notably, when the earliness/duration of the attack is bounded, while the number of total poisoned samples can be arbitrarily large, they cannot cover the entire timeline and therefore it won’t be the case where all samples are poisoned.\n\nThe baseline defense computes the minimal attack budgets (earliness and duration in this case) that **any** attack needs to change the prediction on an input. For any given budget (earliness/duration), the defense is provably robust on a sample if the above threshold is larger than the budget and the prediction is correct (i.e. the prediction will be correct and unchanged after any attack within this earliness/duration, regardless of how many samples are poisoned, **supporting the ‘unbounded’ claim**). \n\nFollowing existing work with certified defenses(e.g. [3, 11, 13, 23, 33, 34] cited in the paper), we evaluate certified accuracy/fraction (robust fraction in ours) rather than against specific attack methods. \n\n**Please let us know if you find any of the answers unclear. Looking forward to your reply!**\n"}, {"review_id": "q0UxkeAFkT", "reviewer": "Reviewer_exCr", "summary": "This paper considers provable defenses in a threat model where attackers can inject arbitrarily many poisoning points. Traditional defenses that rely on the assumption of dealing with a low fraction of poisoning points can then be easily broken in the new threat model. Regarding this issue, the authors propose to leverage the birth date of the data collected and defined two temporal metrics of earliness and duration of an attack. Then, for attacks with bounded earliness and duration, the proposed temporal framework can provide a provable certificate on predictions, even when the attackers can inject arbitrarily many poisoning samples. The authors empirically validated the performance of the defense by establishing a baseline on the news category dataset.", "questions": "This paper is easy to read and raises an interesting research question on poisoning defense in a new dimension. However, I have a major concern about the threat model.\n1. Will the considered threat model be realistic in practice? The authors claimed that it is possible for attackers to post more poisoning points online, but this is based on the assumption that the generation of individual poisoning points is very cheap and can be automated at a low cost. I could not think of a practical application scenario where this is likely to be true. In fact, all poisoning points need to be modified deliberately to be effective with some decent optimization strategies, and so this process can be costly. In addition, the generated poisoning points may also need to be coordinated, making the task harder for full automation. Recent work shows how poisoning can be practical [1], but the key assumption is these attacks are feasible to manipulate a low fraction of poisoning points and controlling exceedingly many numbers of poisoning points would be practically infeasible.   \n\n2. The considered threat model allows any cautious attacker to start the attack early as possible and continue to poison the dataset as long as possible. The provable defense can be helpful for the initial period of time, as there can be some leverage from datasets that are sampled prior to the start of the attack. However, this leverage will be completely lost later. So, it is unclear to me how significant the result can be, as it means in the end, there are exceedingly many poisoning points available and any viable defenses can be broken. \n\nTow minor questions are:\n1. what is the main motivation behind making the base learner deterministic in the experiments?  \n2. the authors mention that the birth date is partially reliable. I am wondering if the fact that attackers can block the collection of clean samples (and hence their birth dates) will increase the effectiveness of the attack (e.g., making the attack start early in a passive manner). My current understanding is whatever strategy is used (e.g., injection of new points or blocking and inserting clean points later) are all considered as the start of the attack, and therefore, the robustness guarantee will be the same. \n\n[1] Carlini et al., \"Poisoning Web-Scale Training Datasets is Practical\", ArXiv.\n\n--------------------------------------\n\nThis is to acknowledge that I have read the authors rebuttals carefully and my concerns are addressed.", "limitations": "N/A", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The presentation of the paper is clear. \n2. The proposed claims are well-supported through both theoretical and empirical validations.", "weaknesses": "1. It is unclear how realistic the considered threat model is in practice. \n2. The considered threat model allows the existence of strong attackers that continuously inject poisoning points with unbounded earlierness and duration and make the provable defenses completely fail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing our paper as clear and well-supported! We value your comments a lot in improving the presentation of our paper.\n\n**1. ‘The authors claimed that it is possible for attackers to post more poisoning points online, but this is based on the assumption that the generation of individual poisoning points is very cheap and can be automated at a low cost’**\n\nWe understand your confusion and we will revise the expressions to better reflect our positions. To clarify, by ‘attackers in many practical scenarios can poison more and more samples with fairly affordable overhead’ and the following examples, what we want to emphasize is that they can poison more samples than **what existing defenses can tolerate**, rather than that they can indeed poison astronomical amounts of samples (i.e. what we wanted to mean is that the poisoned samples are exceedingly many ONLY when being compared with the numbers we can defend against so far).\n\nNotably, the fractions/numbers of poisoned samples defenses may tolerate can be quite limited (supported empirically by [1, 2, 3] and theoretically by [4], just for examples).\n\nWe see how our existing descriptions can be confusing, and we will incorporate your comments for revisions.\n\n[1] Carlini et.al., Poisoning Web-Scale Training Datasets is Practical.\n\n[2] Souri et.al., Sleeper Agent: Scalable Hidden Trigger Backdoors for Neural Networks Trained from Scratch. \n\n[3] Geiping et.al., Witches' Brew: Industrial Scale Data Poisoning via Gradient Matching.\n\n[4] Wang et.al., Lethal Dose Conjecture on Data Poisoning.\n\n**2. 'The considered threat model allows the existence of strong attackers that continuously inject poisoning points with unbounded earlierness and duration and make the provable defenses completely fail'**\n\nSince the key of our threat model is to use earliness and/or duration to measure attack budgets, it is natural that poisoning attacks with unbounded budgets (essentially no limit at all) can break the provable defenses. However, we believe this, *by itself*, does not constitute a weakness of our threat model since similar arguments apply to essentially any threat model (e.g. there will also be infinitely broken points for previous data poisoning threat models if one has no constraint on the number of poisoned samples).\n\nWe suggest a different angle to inspect the usefulness of our threat model v.s. existing ones, by considering what different metrics (earliness, duration, and number of poisoned samples) mean from the eyes of an attacker. \n\nFirst, we consider the number of poisoned samples, as in previous threat models for data poisoning. As we previously mentioned, the number of poisoned samples existing defenses can tolerate can be quite limited (supported empirically by [1, 2, 3] and theoretically by [4]). Admittedly, there can be some cases where the attacker simply cannot meet the requirement, but it is unlikely unless it is a very simple task (e.g. MNIST) or the victim has (or has the clean data to train) a strong pre-trained model available that is assumed clean. In other cases where the attacker can inject the required amounts of poisoned samples, the attack will succeed as soon as the victim’s next round of model updates.\n\nThe role of earliness is to delay the success of the attack when the number of poisoned samples cannot stop the attack entirely. In our evaluations, the earliness requirement for successful attacks varies from a couple of months to almost a year, which we hope can be further increased with better defenses. If I were the attacker, the need to wait for many months (and maybe years depending on tasks and future improvements on defenses) can not only be emotionally painful but also prohibits attack goals that are sensitive to timing (e.g. sabotage new models from competitors to promote one’s own) and increases the difficulty of adjusting attack methods based on attack results. Duration, on the other hand, enforces attackers to be active for a longer period of time, which not only increases their workload but also potentially makes them leave more traces so that they have to cost more to keep the attacks unnoticed.\n\nIn addition, earliness and duration can be used jointly with the number of poisoned samples to raise the cost/difficulty of successful poisoning attacks. As an example, our baseline defense, while being a provable defense against attacks with bounded earliness and duration, is also a provable defense with respect to a bounded number of poisoned samples when using small n. This follows directly from previous aggregation defenses like DPA [5] for existing poisoning threat models. \n\n[5] Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defenses against general poisoning attacks. ICLR 2021\n\n**3. ‘what is the main motivation behind making the base learner deterministic in the experiments?’**\n\nAs discussed in Section 6 of the paper, the baseline defense is inspired by aggregation-based defenses for the traditional threat model of data poisoning (i.e. using the number of poisoned samples to measure attack budgets). We follow [13, 23, 33, 34] cited in the paper, which are all defenses that use deterministic base learners. By making the base learner deterministic, we can make the entire algorithm deterministic and the computed certified robustness can be deterministic, which improves overall efficiency by not requiring Monte Carlo sampling to estimate the mean of output distributions.\n\n**4. ‘My current understanding is whatever strategy is used (e.g., injection of new points or blocking and inserting clean points later) are all considered as the start of the attack, and therefore, the robustness guarantee will be the same’**\n\nYes, we believe your understanding here is accurate. Injecting a new sample and removing (blocking) an existing sample are both considered the start of the attack.\n\n\n**We look forward to your follow-up comments.** \n\n**Thank you for helping us improve our paper.**\n"}]

Author rebuttal:

Meta-review: The paper considers a novel angle to study poisoning attacks and defenses by considering the temporal dimension and defining two corresponding metrics other than just considering the fraction of poisoning samples the attacker can control. The rebuttal has clarified the major issues raised by the reviewers; however, the threat model is still somewhat unconvincing. Thus, the authors should clarify it and provide additional motivation behind it when preparing the final version.
Decision: Accept (poster)