# universal_multiparty_poisoning_attacks__9527fd0c.pdf

Universal Multi-Party Poisoning Attacks

Saeed Mahloujifar 1 Mohammad Mahmoody 1 Ameer Mohammed 2

In this work, we demonstrate universal multiparty poisoning attacks that adapt and apply to any multi-party learning process with arbitrary interaction pattern between the parties. More generally, we introduce and study (k, p)-poisoning attacks in which an adversary controls k [m] of the parties, and for each corrupted party Pi, the adversary submits some poisoned data T i on behalf of Pi that is still (1 p)-close to the correct data Ti (e.g., 1 p fraction of T i is still honestly generated). We prove that for any bad property B of the final trained hypothesis h (e.g., h failing on a particular test example or having large risk) that has an arbitrarily small constant probability of happening without the attack, there always is a (k, p)-poisoning attack that increases the probability of B from µ to by µ1 p k/m = µ+Ω(p k/m). Our attack only uses clean labels, and it is online, as it only knows the the data shared so far.

1. Introduction

Learning from a set T = {d1 = (a1, b1), . . . , dn = (an, bn)} of training examples in a way that the predictions generalize to instances beyond T is a fundamental problem in learning theory. The goal here is to produce a hypothesis h in such a way that h(a), with high probability, predicts the correct label b, where the pair (a, b) = d is sampled from the target (test) distribution d. In the most natural setting, the examples in the training data set T are also generated from the same distribution d, however this is not always the case (e.g., due to noise in the data).

Poisoning attacks. Many previous works studying noise in the data allow it to be adversarial and maliciously cho-

1University of Virginia. Supported by NSF CAREER award CCF-1350939, and University of Virginia s SEAS Research Innovation Award. {saeed, mohammad}@virginia.edu 2University of Kuwait. ameer.mohammed@ku.edu.kw. Correspondence to: Saeed Mahloujifar <saeed@virginia.edu>.

Proceedings of the 36 th International Conference on Machine Learning, Long Beach, California, PMLR 97, 2019. Copyright 2019 by the author(s).

sen against the learner (Valiant, 1985; Kearns & Li, 1993; Bshouty et al., 2002). A tightly related and more recent approach to the problem of learning under adversarial noise is the framework of so-called poisoning (aka causative) attacks (Barreno et al., 2006; Biggio et al., 2012; Papernot et al., 2016), in which the adversary s goal is not necessarily to completely prevent the learning, but perhaps it simply wants to increase the risk of the hypothesis produced by the learning process or make it more likely to fail on a particular test instance (i.e., getting a targeted poisoning attack (Barreno et al., 2006; Shen et al., 2016)).

Multi-party poisoning. In the distributed setting (Mc Mahan & Ramage, 2017; Mc Mahan et al., 2016; Bonawitz et al., 2017; Koneˇcn y et al., 2016), the training data T might be coming from various sources; e.g., it can be generated by m data providers P1, . . . , Pm in an online way, while at the end a fixed algorithm, called the aggregator G, generates the hypothesis h based on T . The goal of P1, . . . , Pm is to eventually help G construct a hypothesis h that does well (e.g. in the case of classification) in predicting the label b of a given instance a, where (a, b) d is sampled from the final test distribution. The data provided by each party Pi might even be of different type , so we cannot simply assume that the data provided by Pi is necessarily sampled from the same distribution d. To model this more general setting, we let di model the distribution from which the training data Ti (of Pi) is sampled. Poisoning attacks can naturally be defined in the distributed setting as well (Fung et al., 2018; Bagdasaryan et al., 2018; Blanchard et al., 2017; Hayes & Ohrimenko, 2018) to model adversaries who partially control the training data T . These works, however, focus on attacking and defending specific learning tasks. This leads us to the central question of this work.

What is the inherent provable power of poisoning attacks in the multi-party setting?

Answering the above question is critical for understanding the limits of provable security against multi-party poisoning.

1.1. Our Contribution

We first formalize a new general model multi-party poisoning. We then prove the existence of universal data poisoning attacks in the multi-party setting that apply to any task.

Universal Multi-Party Poisoning Attacks

New attack model: (k, p)-poisoning attacks. our first contribution of this work is to formalize a general notion that covers multi-party poisoning attackers that corrupt k out of m data provider parties and furthermore, for each message sent by a corrupted party, the adversary still generates data that is close to the honestly generated data. More formally, a (k, p)-poisoning attacker Adv can first choose to corrupt k of the parties. Then, if a corrupted e Pi is supposed to send the next message, then the adversary will sample d ed for a maliciously chosen distribution ed that is guaranteed to be p to the original distribution di in total variation distance. Our (k, p)-poisoning attacks include the so called p-tampering attacks of (Mahloujifar et al., 2018a) as special case by letting k = m (m is the number of parties). Moreover, (k, p)-attacks also include the standard model of k static corruption in secure multi-party computation (in cryptography) letting p = 1. Our main result in this works is to prove the universal power of (k, p)-poisoning as follow. We show that in any m-party learning protocol, there exist a (k, p)-poisoning adversary that increases probability of the produced hypothesis h having a bad property B (e.g., failing on a particular target instance known to the adversary).

(For the formal version of Theorem 1.1, see Theorem 2.4.)

Theorem 1.1 (Power of (k, p)-poisoning attacks informal). Let Π = (P1, . . . , Pm) be an m-party learning protocol for an m-party learning problem. Also let B be a bad property defined over the output of the protocol. There is a polynomial time (k, p)-poisoning attack Adv such that, given oracle access to the data distribution of the parties, Adv can increase the probability of B from µ to µ1 kp/m.

Example. By corrupting half of the parties (i.e., p = 1, k = m/2) the adversary can increase the probability of any bad event B from 1/100 to 1/10.

Universal nature of our attack. Our attacks are universal in the sense that they could be applied to any learning algorithm for any learning task, and they are dimensionindependent as they applied to any data distribution. On the other hand, our universal attacks rely on an initial vulnerability of arbitrary small constant probability that is then amplified through the poisoning attack. As a result, although recent poisoning attacks (e.g., see (Koh et al., 2018)) obtain stronger bounds in their attack against specific defenses, our attacks apply to any algorithm with any built in defenses.

Deriving attacks on federated learning as special case. Since we allow the distribution of each party in the multiparty case to be completely dependent on that party, our attacks cover the case of model poisoning in federated learning (Bagdasaryan et al., 2018; Bhagoji et al., 2018), in which each party sends something other than their plain share of data, as special case. In fact, multiple works have already demonstrated the power of poisoning attacks and defences

in the federated learning setting (e.g., see (Fung et al., 2018; Bhagoji et al., 2018; Chen et al., 2018; 2017; Guerraoui et al., 2018; Yin et al., 2018; Tomsett et al., 2019; Cirincione & Verma, 2019; Han & Zhang, 2019)). Some of these attacks obtain stronger quantitative bounds in their attacks, however this is anticipated as these works investigate attacks on specific learners, while a crucial property of our attack is that our attacks come with provable bounds and are universal in that they apply to any learning task and any hypothesis class (including neural nets as special case), if there is an initial Ω(1) vulnerability (for some bad property) over the generated hypothesis.

Note that, our attacks actually do not need the exact history of examples that are used by parties, and only need to know the updates sent by the parties during the course of protocol. Suppose an uncorrected party randomizes its local model (e.g., for differential privacy purposes) and shares an update ui with the server. Knowledge of ui is enough for our attacker. One might go even further and ask what if the updates are sent in a secure/private way? Interestingly, our attack work in that model too as it only needs to know the effect of the updates on the central model at the end of round i 1 (because all attack wants is to perform a random continuation on the intermediate model).

It also worth mentioning that our attack requires sampling oracles from distributions of all the parties. This might seem that we are giving the adversary too much power. However, we think the right way to define security of federated learning is by giving the adversary everything that hat might be leaked to them. This way of defining security is inspired by cryptography. For instance, when modeling the chosen plaintext security of encryption schemes, adversary is given access to an encryption oracle, while one might question how realistic it is. Analogously, In federated learning, the adversary can potentially gather some statistics about the distribution of other parties and learn them over time. However, as mentioned above, we do not need to give adversary access to the actual data of honest parties. Only the public effect of them on the shared model is needed.

Further Related Work. Recent breakthroughs of Diakonikolas et al. (Diakonikolas et al., 2016) and Lai et al. (Lai et al., 2016) demonstrated the surprising power of algorithmic robust learning over poisoned training data with limited risk that does not depend on the dimension of the distribution (but still depends on the fraction of poisoned data). These works led to an active line of work (e.g., see (Charikar et al., 2017; Diakonikolas et al., 2017; 2018b;a; Prasad et al., 2018; Diakonikolas et al., 2018c; Steinhardt et al., 2017) and references therein) exploring the possibility of robust statistics over poisoned data with algorithmic guarantees. The works of (Charikar et al., 2017; Diakonikolas et al., 2018b), followed by (Balcan et al., 2008), performed list-decodable

Universal Multi-Party Poisoning Attacks

learning, and (Balakrishnan et al., 2017; Diakonikolas et al., 2018a; Prasad et al., 2018) studied supervised learning.

On the negative side, Mahloujifar, Mahmoody and Diochnos (Mahloujifar & Mahmoody, 2017; Mahloujifar et al., 2018b) studied (universal) poisoning attacks that apply to any learning task and any hypothesis class and showed that such attacks can indeed increase the error of any classifiers for any learning problem by a constant probability, so long as there is an initial constant error probability. The attack model used in (Mahloujifar & Mahmoody, 2017; Mahloujifar et al., 2018b), called p-tampering, was a generalization of a similar model introduced in Austrin et al. (Austrin et al., 2014) in the bitwise setting in a cryptographic context. These attacks (like the ones in our work) were universal in the sense that they could be applied to any learning algorithm for any learning task, and dimension-independent as they applied to any data distribution. On the other hand, these universal attacks rely on an initial vulnerability of arbitrary small constant probability that is then amplified through the poisoning attack. That is why such universal attacks (inclugin our attacks in the multi-party setting) are not in contradiction with positive results mentioned above.

1.2. Technical Overview

Previous universal poisoning attacks of (Mahloujifar & Mahmoody, 2017; Mahloujifar et al., 2018b) for the single party case are designed in a setting in which each training example is chosen by the adversary with independent probability p. We first describe where exactly the ideas of these works come short of extending to the multiparty case, and then we explain how to borrow ideas from attacks on coin-tossing protocols in cryptography (Ben-Or & Linial, 1989; Haitner & Omri, 2014) and obtain the desired attacks of this work.

p-tampering attacks and their shortcoming. For starters, let us assume that the adversary gets to corrupt and control k randomly selected parties. In this case, it is easy to see that, at the end every single message in the protocol Π between the parties P1, . . . , Pm is controlled with exactly probability p = k/m by the adversary Adv (even though these probabilities are correlated). Thus, at a high level it seems that we should be able to use the p-tampering attacks of (Mahloujifar & Mahmoody, 2017; Mahloujifar et al., 2018b) to degrade the quality of the produced hypothesis. However, the catch is that the proof of p-tampering attacks of (Mahloujifar & Mahmoody, 2017; Mahloujifar et al., 2018b) (and the bitwise version of (Austrin et al., 2017)) crucially rely on the assumption that each message (which in our context corresponds to a training example) is tamperable with independent probability p, while corrupting k random parties, leads to tamperable messages in a correlated way.

We prove our main results by first proving a general result about the power of biasing adversaries whose goal is to

increase the expected value of a random process by controlling each incoming segment (aka block) of the random process with probability q (think of q as p k/m). These segments/blocks correspond to single or multiple training examples shared during the learning. As these biasing attacks generalize p-tampering attacks, we simply call them generalized p-tampering attacks. We now describe this attack model and clarify how it can be used to obtain Theorem 1.1.

Generalized p-tampering: new model for biasing attacks. In this work we introduce generalized p-tampering (biasing) attacks that are defined for any random process x (x1, . . . , xn) and a function f(x) [0, 1] defined over this process. In order to explain the attack model, first consider the setting where there is no attacker. Now, given a prefix x1, . . . , xi 1 of the blocks, the next block xi is simply sampled from its conditional probability distribution (xi | x1, . . . , xi 1). (Looking ahead, think of xi as the i th training example provided by one of the parties in the interactive learning protocol.) Now, imagine an adversary who enters the game and whose goal is to increase the expected value of a function f(x1, . . . , xn) defined over the random process x by tampering with the block-by-block sampling process of x described above. Before the attack starts, there will be a a list S [n] of tamperable blocks that is not necessarily known to the Adv in advance, but will become clear to him as the game goes on. Indeed, this set S itself will be first sampled according to some fixed distribution S, and the crucial condition we require is that Pr[i S] = p holds for all i [n]. After S S is sampled, the sequence of blocks (x1, . . . , xn) will be sampled block-by-block as follows. Assuming (inductively) that x1, . . . , xi 1 are already sampled so far, if i S, then Adv gets to fully control xi and determine its value, but if i S, then xi is simply sampled from its original conditional distribution (xi | x1, . . . , xi 1). At the end, the function f is computed over the (adversarially) sampled sequence.

We now explain the intuitive connection between generalized p-tampering attacks and (k, p)-poisoning attacks. The main idea is that we will use a generalized q-tampering attack for q = p k/m over the random process that lists the sequence of training data provided by the parties during the protocol. Let S be the distribution over [n] that picks its members through the following algorithm. First choose a set of random parties {Q1, . . . , Qk} {P1, . . . , Pm}, and then for each message xj that belongs to Qi, include the corresponding index j in the final sampled S S with independent probability p. It is easy to see that S eventually picks every message with (marginal) probability q = p k/m, but it is also the case that these inclusions are not independent events. Finally, to use the power of generalized p-tampering attacks over the described S and the random process of messages coming from the parties to get the results of Theorem 1.1, roughly speaking, we

Universal Multi-Party Poisoning Attacks

let a function f model the loss function applied over the produced hypothesis. Therefore, to prove Theorem 1.1 it is sufficient to prove Theorem 1.2 below which focuses on the power of generalized p-tampering biasing attacks.

Theorem 1.2 (Power of generalized p-tampering-informal). Suppose x (x1, . . . , xn) is a joint distribution such that, given any prefix, the remaining blocks could be efficiently sampled in polynomial time. Also let f : Supp(x) 7 [0, 1]. Then, for any set distribution S for which Pr[i S] = p for all i, there is a polynomial-time generalized p-tampering attack (over tampered blocks in S) that increases the average of f over its input from µ to µ µ p E[f(x)1+p]. In particular, if f is boolean function µ µ1 p.

(The formal statement of Theorem 1.2 above follows from Theorem 3.5 and Lemma 3.6.)

Bitwise vs. blockwise attacks. It is easy to see that in the definition of generalized p-tampering attacks, it does not matter whether we define the attack bit-by-bit or block-byblock. The reason is that, even if we break down each block into smaller bits, then still each bit shall eventually fall into the set of tamperable bits, and the model allows correlation between the inclusion and exclusion of each block/bit into the final tamperable set. This is in contrast to the ptampering model for which this equivalence is not true. In fact, optimal bounds achievable by bitwise p-tampering as proved in (Austrin et al., 2017) are impossible to achieve in the blockwise p-tampering setting (Mahloujifar & Mahmoody, 2017). Despite this simplification, we still prefer to use a blockwise presentation of the random process, as this way of modeling the problem allows better tracking measures for the attacker s sample complexity.

Ideas Behind the Tampering Attack of Theorem 1.2. To prove Theorem 1.2 we use ideas from (Haitner & Omri, 2014; Ben-Or & Linial, 1989) in the context of coin-tossing attacks and generalize them using new techniques to obtain our generalized p-tampering attacks.

Rejection sampling attack. The simplified version of our attack can be described as follows. Based on the nature of this attack, we call it the rejection sampling (RS) attack. For any prefix of already sampled blocks (x1, . . . , xi 1), suppose the adversary is given the chance of controlling the next i th block. The RS tampering then works as follows:

1. Let x i, . . . , x n be a random continuation of the random process, conditioned on (x1, . . . , xi 1).

2. If s = f(x1, . . . , xi 1, x i, . . . , x n), then if s = 1 output yi, and otherwise (i.e., if s = 0) go to Step 1 and repeat the sampling process.

The above attack is inspired by the two-party attack of (Haitner & Omri, 2014). Our main contribution is to do the

following steps. (1) First, analyze this attack in the generalized tampering setting and show its power, which implies the multiparty case as special case. This already gives an alternative, and in our eyes simpler, proof of the classic result of (Ben-Or & Linial, 1989) (2) We then extend this attack and its analysis to the real-output setting. (3) Finally, we show how to approximate this attack in polynomial time.

2. Multi-Party Poisoning Attacks: Definitions and Main Results

Notation. We use bold font (e.g., x, S, α) to represent random variables, and usually use same non-bold letters for denoting samples from these distributions. We use d d to denote the process of sampling d from the random variable d. By E[α] we mean the expected value of α over the randomness of α, and by V[α] we denote the variance of random variable α. We might use a processed version of α, and use E[f(α)] and V[f(α)] to denote the expected value and variance, respectively, of f(α) over the randomness of α. A learning problem (A, B, d, H) is specified by the following components. The set A is the set of possible instances, B is the set of possible labels, d is distribution over A B.1 The set H BA is called the hypothesis space or hypothesis class. An example s is a pair s = (a, b) where x A and y B. We consider loss functions Loss: B B 7 R+ where Loss(b , b) measures how different the prediction y (of some possible hypothesis h(a) = y ) is from the true outcome y. We call a loss function bounded if it always takes values in [0, 1]. A natural loss function for classification tasks is to use Loss(b , b) = 0 if y = y and Loss(b , b) = 1 otherwise. The risk of a hypothesis h C is the expected loss of h with respect to d, namely Risk(h) = E(a,b) d[Loss(h(a), b)]. The average error which quantifies the total error of the protocol is defined as Err(d) = Prh Π,(a,b) d[Loss(h(a), b)].

Definition 2.1 (Multi-party learning protocols). An m-party learning protocol Π for the m-party learning problem (D, H) consists of an aggregator function G and m (interactive) data providers P = {P1, . . . , Pm}. For each data provider Pi, there is a distribution di D that models the (honest) distribution of labeled samples generated by Pi, and there is a final (test) distribution d that P, G want to learn jointly. The protocol runs in r rounds and at each round, based on the protocol Π, one particular data owner Pi broadcasts a single labeled example (a, b) di.2 In the last round, the aggregator function G maps the the messages to an output hypothesis h H.

1By using joint distributions over A B, we jointly model a set of distributions over A and a concept class mapping A to B (perhaps with noise and uncertainty). 2We can directly model settings where more data is exchanged in one round, however, we stick to the simpler definition w.l.o.g.

Universal Multi-Party Poisoning Attacks

Now, we define poisoning attackers that target multi-party protocols. We formalize a more general notion that includes p-tampering attacks and k-party corruption as special case.

Definition 2.2 (Multi-party (k, p)-poisoning attacks). A (k, p)-poisoning attack against an m-party learning protocol Π is defined by an adversary Adv who can control a subset C [m] of the parties where |C| = k. The attacker Adv shall pick the set C at the beginning. At each round j of the protocol, if a data provider Pi C is supposed to broadcast the next example from its distribution di, the adversary can partially control this sample using the tampered distribution ed such that |ed di| p in total variation distance. Note that the distribution ed can depend on the history of examples broadcast so far, but the requirement is that, conditioned on this history, the malicious message of adversary modeled by distribution ed, is at most p-statistically far from di. We use ΠAdv to denote the protocol in presence of Adv. We also define the following notions. Adv is a plausible adversary, if it always holds that Supp(ed) Supp(di). Adv is efficient if it runs in polynomial time in the total length of the messages exchanged during the protocol (from the beginning till end).

Remark 2.3 (Static vs. adaptive corruption). Definition 2.2 focuses on corrupting k parties statically. A natural extension of this definition in which the set C is chosen adaptively (Canetti et al., 1996) while the protocol is being executed can also be defined naturally. In this work, however, we focus on static corruption, and leave the possibility of improving our results in the adaptive case for future work.

We now formally state our result about the power of (k, p)- poisoning attacks.

Theorem 2.4 (Power of efficient multi-party poisoning). In any m-party protocol Π for parties P = {P1, . . . , Pm}, for any p [0, 1] and k [m], the following hold where M is the total length of the messages exchanged.

1. For any bad property B : H {0, 1}, there is a plausible (k, p)-poisoning attack Adv that runs in time poly(M/ε) and increases the probability of B from µ (in the no-attack setting) to

2. If the (normalized) loss function is bounded (i.e., it outputs in [0, 1]), then there is a plausible, (k, p)- poisoning Adv that runs in time poly(M/ε) and increases the average error of the protocol as

Err Adv(d) Err(d) p E h Π[Risk(h, d)1+p]

Err(d) + p k

where ν = Vh Π[Risk(h, d)] and V[ ] is the variance.

Allowing different distributions in different rounds. In Definition 2.2, we restrict the adversary to remain close to di for each message sent out by one of the corrupted parties. A natural question is: what happens if we allow the parties distributions to be different in different rounds. For example, in a round j, a party Pi might send multiple training examples D(j) = d(j) 1 , d(j) 2 , . . . , d(j) k , and we want to limit the total statistical distance between the distribution of the larger message D(j) from dk i (i.e., k iid samples from di).3

We emphasize that, our results extend to this more general setting as well. In particular, the proof of Theorem 2.4 directly extends to a more general setting where we can allow the honest distribution di of each party i to also depend on the round j in which these messages are sent. Thus, we can use a round-specific distribution d(j) i to model the joint distribution of multiple samples D(j) = d(j) 1 , d(j) 2 , . . . , d(j) k

that are sent out in the j th round by the party Pi. This way, we can obtain the stronger form of attacks that remain statistically close to the joint (correct) distribution of the (multi-sample) messages sent in a round. In fact, as we will discuss shortly D(j) might be of completely different type.

Allowing randomized aggregation. The aggregator G is a simple function that maps the transcript of the exchanged messages to a hypothesis h. A natural question is: what happens if we generalize this to the setting where G is allowed to be randomized. We note that in Theorem 2.4, Part 2 can allow G to be randomized, but Parts 1 and 3 need deterministic aggregation. The reason is that for those parts, we need the transcript to determine the confidence and average error functions. One general way to make up for randomized aggregation is to allow the parties to inject randomness into the transcript as they run the protocol by sending messages that are not necessarily learning samples from their distribution di. As described above, our attacks extend to this more general setting as well. Otherwise, we will need the adversary to be able to also depend on the randomness of G, but that is also a reasonable assumption if the aggregation is used using public beacon that could be obtained by the adversary as well.

Before proving Theorem 2.4, we need to develop our main result about the power of generalized p-tampering attacks. In Section 3, we develop such tools, and then in Section 3.2 we prove Theorem 2.4.

3. Multi-Party Poisoning via Generalized p-Tampering

To prove our Theorem 2.4 we interpret the multi-party learning protocol as a coin tossing protocol in which the final

3Note that, even if each block in d(j) 1 , d(j) 2 , . . . , d(j) k remains p-close to di, their joint distribution could be quite far from dk i .

Universal Multi-Party Poisoning Attacks

bit is 1 if h has the (bad) property B. We define a corresponding attack model in coin tossing protocols that can be directly used to obtain the desired goal; this model is called generalized p-tampering. Below, we formally state our main result about the power of generalized p-tampering attacks. We start by formalizing some notation and definitions.

Notation. By x y we denote that the random variables x and y have the same distributions. Unless stated otherwise, by using a bar over a variable, we emphasize that it is a vector. By x (x1, x2, . . . , xn) we refer to a joint distribution over vectors with n components. For a joint distribution x (x1, . . . , xn), we use x i to denote the joint distribution of the first i variables x (x1, . . . , xi). Also, for a vector x = (x1 . . . xn) we use x i to denote the prefix (x1, . . . , xi). For a randomized algorithm L( ), by y L(x) we denote the randomized execution of L on input x outputting y. For a distribution (x, y), by (x | y) we denote the conditional distribution (x | y = y). By Supp(d) = {d | Pr[d = d] > 0} we denote the support set of d. By T d( ) we denote an algorithm T( ) with oracle access to a sampler for d that upon every query returns fresh samples from d. By dn we denote the distribution that returns n iid samples from d. Definition 3.1 (Valid prefixes). Let x (x1, . . . , xn) be an arbitrary joint distribution. We call x i = (x1, . . . , xi) a valid prefix for x if there exist xi+1, . . . , xn such that (x1, . . . , xn) Supp(x). Val Pref(x) denotes the set of all valid prefixes of x. Definition 3.2 (Tampering with random processes). Let x (x1, . . . , xn) be an arbitrary joint distribution. We call a (potentially randomized and possibly computationally unbounded) algorithm T an (online) tampering algorithm for x if given any prefix x i 1 Val Pref(x), we have

Pr xi T(x i 1)[x i Val Pref(x)] = 1 .

Namely, T(x i 1) outputs xi such that x i is again a valid prefix. We call T an efficient tampering algorithm for x if it runs in time poly(N) where N is maximum bit length to represent any x Supp(x). Definition 3.3 (Online samplers). We call On Sam an online sampler for x (x1, . . . , xn) if for all x i 1 Val Pref(x), On Sam(n, x i 1) xi. Moreover, we call x (x1, . . . , xn) online samplable if it has an online sampler that runs in time poly(N) where N is maximum bit length of any x Supp(x).

Notation for tampering distributions. Let x (x1, . . . , xn) be an arbitrary joint distribution and T a tampering algorithm for x. For any subset S [n], we define y x T, S to be the joint distribution that is the result of online tampering of T over set S, where y (y1, . . . , yn) is sampled inductively as follows. For every i [n], suppose y i 1 is the previously sampled block.

If i S, then the ith block yi is generated by the tampering algorithm T(y i 1), and otherwise, yi is sampled from (xi | xi 1 = y i 1). For any distribution S over subsets of [n], by x T, S we denote the random variable that can be sampled by first sampling S S and then sampling y x T, S .

Definition 3.4 (p-covering). Let S be a distribution over the subsets of [n]. We call S a p-covering distribution on [n] (or simply p-covering, when n is clear from the context), if for all i [n], Pr S S[i S] = p.

The following theorem states the power of generalized ptampering attacks.

Theorem 3.5 (Biasing of bounded functions through generalizing p-tampering). Let S be a p-covering distribution on [n], x (x1, . . . , xn) be a joint distribution, f : Supp(x) 7 [0, 1], and µ = E[f(x)]. Then, for any ε [0, 1], there exists a tampering algorithm Tε that, given oracle access to f and any online sampler On Sam for x, it runs in time poly(N/ε), where N is the bit length of any x x, and for yε x Tf,On Sam ε , S , it holds that

E [f(yε)] µ p E f(x)1+p ε .

Special case of Boolean functions. When the function f is Boolean, we get µ p E[f(x)1+p] = µ1 p µ(1+Ωµ(p)), which matches the bound proved in (Ben-Or & Linial, 1989) for the special case of p = k/n for integer k [n] and for S that is uniformly random subset of [n] of size k. (The same bound for the case of 2 parties was proved in (Haitner & Omri, 2014) with extra properties). Even for this case, compared to (Ben-Or & Linial, 1989; Haitner & Omri, 2014) our result is more general, as we can allow S with arbitrary p [0, 1] and achieve a polynomial time attack given oracle access to an online sampler for x. The work of (Haitner & Omri, 2014) also deals with polynomial time attackers for the special case of 2 parties, but their efficient attackers use a different oracle (i.e., OWF inverter), and it is not clear whether or not their attack extend to the case of more then 2 parties. Finally, both (Ben-Or & Linial, 1989; Haitner & Omri, 2014) prove their bound for the geometric mean of the averages for different S S, while we do so for their arithmetic mean, but we emphasize that this is enough for all of our applications.

The bounds of Theorem 3.5 for both cases rely on the quantity µ = µ p E[f(x)1+p]. A natural question is: how large is µ compared to µ? As discussed above, for the case of Boolean f, we already know that µ µ, but that argument does not apply to the real-output f. A simple application of Jensen s inequality shows that µ µ in general, but that still does not mean that µ µ.

General case of real-output functions: relating the bias to the variance. If V[f(x)] = 0, then no tampering attack

Universal Multi-Party Poisoning Attacks

can achieve any bias, so any gap achieved between µ and µ shall somehow depend on the variance of f(x). In the following, we show that this gap does exist and that µ µ Ω(p V[f(x)]). similar results (relating the bias the the variance of the original distribution) were previously proved (Mahloujifar et al., 2018b; Mahloujifar & Mahmoody, 2017; Austrin et al., 2014) for the special case of p-tampering attacks (i.e., S chooses every i [n] independently with probability p). Here we obtain a more general statement that holds for any p-covering set structure S.

Using Lemma 3.6 below for α f(x), we immediately get Ω(p V[f(x)]) lower bounds for the bias achieved by (both versions of) the attackers of Theorem 3.5 for the general case of real-valued functions and arbitrary p-covering set distribution S. See full version of paper for the proof.

Lemma 3.6. Let α be any real-valued random variable over Supp(α) [0, 1], and p [0, 1]. Let µ = E[α] be the expected value of α, ν = V[α] be the variance of α. Then, it holds that

µ p E[α1+p] µ p (p + 1)

3.1. Proving Theorem 3.5 For Computationally Unbounded Adversaries.

The construction below describes a computationally unbounded biasing algorithm that achieves the bounds of Theorem 3.5. Please see the full version of paper for the proof of computationally bounded setting where we carefully approximate the construction bellow by a computationally bounded polynomial-time biasing adversary.

Construction 3.7 (Rejection-sampling tampering). Let x (x1, . . . , xn) and f : Supp(x) 7 [0, 1]. The rejection sampling tampering algorithm Rej Samf works as follows. Given the valid prefix y i 1 Val Pref(x), the tampering algorithm would do the following:

1. Sample y i (x i | y i 1) by using the online sampler for f.

2. If s = f(y1, . . . , yn), then with probability s output yi, otherwise go to Step 1 and repeat the process.

We will first prove a property of the rejection sampling algorithm when applied on every block.

Definition 3.8 (Notation for partial expectations of functions). Suppose f : Supp(x) 7 R is defined over a joint distribution x (x1, . . . , xn), i [n], and x i Val Pref(x). Then, using a small hat, we define the notation ˆf(x i) = Ex (x|x i)[f(x)]. (In particular, for x = x[n], we have ˆf(x) = f(x).)

Claim 3.9. If x Rej Samf, [n] y[n] (y1, . . . , yn). Then, for every valid prefix y i Val Pref[x],

Pr[y i = y i] Pr[x i = y i] = ˆf(y i)

Proof. Based on the description of Rej Samf, for any y i Val Pref(x) the following equation holds for the probability of sampling yi conditioned on prefix y i 1.

Pr[yi = yi | y i 1] = Pr[xi = yi | y i 1] ˆf(y i)

+ (1 ˆf(y i 1)) Pr[yi = yi | y i 1].

The first term in this equation corresponds to the probability of selecting and accepting in the first round of sampling and the second term corresponds to the probability of selecting and accepting in any round except the first round. Therefore we have

Pr[yi = yi | y i 1] = ˆf(y i) ˆf(y i 1) Pr[xi = yi | y i 1] ,

which implies that

Pr[y i = y i] = Y

ˆf(y j) ˆf(y j 1)

Pr[x i = y i]

µ Pr[x i = y i] .

Now, we prove two properties for any tampering algorithm (not just rejection sampling) over a p-covering distribution.

Lemma 3.10. Let S be p-covering for [n] and y Supp(x). For any S Supp(S) and an arbitrary tampering algorithm T for x, let y S x T, S . Then,

Pr[y S = y]

Pr[y[n] = y]

Proof. For every y i Val Pref(y[n]) Val Pref(x) define ρ[y i] as

ρ[y i] = Pr[y[n] i = xi | y[n] i 1 = y i 1]

Pr[xi = xi | x i 1 = y i 1] .

Then, for all y Val Pref(y S) Val Pref(x) we have

Pr[y S = y] = Pr[x = y] Y

i S ρ[y i] .

Universal Multi-Party Poisoning Attacks

Therefore we have

Pr[y S = y]

i [n] ρ[y i]

Claim 3.11. Suppose S is p-covering on [n], y S x T, S for any S S, and y x T, S for an arbitrary tampering algorithm T for x. Then, it holds that

y Supp(x) Pr[x = y] f(y)

Pr[y[n] = y]

Proof. Let h S,y = Pr[y S=y]

Pr[x=y] . Also let Z Supp(x). Note that Supp(y S) Z for any S [n]. Therefore, we have E[f(y)] = ES S Ey y S [f(y)] is equal to

S 2[n] Pr[S = S] X

y Z Pr[y S = y] f(y)

S 2[n] Pr[S = S] X

y Z h S,y Pr[x = y] f(y)

y Z Pr[x = y] f(y) X

S 2[n] Pr[S = S] h S,y

(by AM-GM inequality)

y Z Pr[x = y] f(y) Y

S 2[n] h Pr[S=S] S,y

(by p-covering of S and Lemma 3.10)

y Z Pr[x = y] f(y)

Pr[y[n] = y]

We now prove the main result using the one-rejection sampling tampering algorithm and also relying on the p-covering property of S. In particular, if y x Rej Samf, S , then by Claims 3.11 and 3.9 we have

Pr[y[n] = y]

Pr[x = y] f(y)

(by Claim 3.9)

p Pr[x = y] f(y)

y Supp(x) Pr[x = y] f(y)1+p

= µ p E[f(x)1+p] .

3.2. Obtaining (k, p)-Poisoning Attacks: Proof of Theorem 2.4 using Theorem 3.5

In this section, we formally prove Theorem 2.4 using Theorems 3.5. We first prove the first part of theorem about the boolean property.

Proof of Theorem 2.4 part 1. For a subset C [m] let PC = {Pi; i C} and RC be the subset of rounds where one of the parties in PC sends an example. Also for a subset S [n], we define Bion(S, p) to be a distribution over all the subsets of S, where each subset S S hast the probability p|S | (1 p)|S| |S |. Now, consider the covering S of the set [n] which is distributed equivalent to the following process. First sample a uniform subset C of [m] of size k. Then sample and output a set S sampled from Bion(RC, p). S is clearly a (p k

m)-covering. We use this covering to prove the theorem. For j [n] let w(j) be the index of the provider at round j and let dw(j) be the designated distribution of the jth round and let x = dw(1) dw(n).

We define a function f : Supp(x) {0, 1}, which is a Boolean function and is 1 if the output of the protocol has the property B, and otherwise it is 0. Now we use Theorem 3.5. We know that S is a (p k

m)-covering for [n]. Therefore of Theorem 3.5, there exist an poly(m/ε) time tampering algorithm Tε that changes x to y x Tf,On Sam ε , S where E[f(y)] E[f(y)]1 pk/m ε.

By an averaging argument, we can conclude that there exist a set C [m] of size k for which the distribution Bion(RC, p) produces average output at least E[f(y)]1 pk/m ε. Note that the measure of empty set in Bion(RC, p) is exactly equal to 1 p which means with probability 1 p the adversary will not tamper with any of the blocks, therefore, the statistical distance |x x Tf,On Sam ε , Bion(RC, p) | is at most p. This concludes the proof.

Now we prove the second part using Theorem 3.5 and Lemma 3.6.

Proof of Theorem 2.4 part 2. Now we prove the second part. The second part is very similar to first part except that the function that we define here is a real valued function. Consider the function f2 : Supp(x) [0, 1] which is defined to be the risk of the output hypotheses. Now by Theorem 3.5 and Lemma 3.6, we know that there is tampering algorithm Tε that changes x to y x Tf2,On Sam ε , S such that

E[f2(y)] µ2 + p k

By a similar averaging argument we can conclude the proof.

Universal Multi-Party Poisoning Attacks

Austrin, P., Chung, K.-M., Mahmoody, M., Pass, R., and Seth, K. On the impossibility of cryptography with tamperable randomness. In International Cryptology Conference, pp. 462 479. Springer, 2014.

Austrin, P., Chung, K.-M., Mahmoody, M., Pass, R., and Seth, K. On the impossibility of cryptography with tamperable randomness. Algorithmica, 79(4):1052 1101, Dec 2017. ISSN 14320541. doi: 10.1007/s00453-016-0219-7. URL https://doi.org/10.1007/s00453-016-0219-7.

Bagdasaryan, E., Veit, A., Hua, Y., Estrin, D., and Shmatikov, V. How to backdoor federated learning. ar Xiv preprint ar Xiv:1807.00459, 2018.

Balakrishnan, S., Du, S. S., Li, J., and Singh, A. Computationally efficient robust sparse estimation in high dimensions. In Conference on Learning Theory, pp. 169 212, 2017.

Balcan, M.-F., Blum, A., and Vempala, S. A discriminative framework for clustering via similarity functions. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 671 680. ACM, 2008.

Barreno, M., Nelson, B., Sears, R., Joseph, A. D., and Tygar, J. D. Can machine learning be secure? In Proceedings of the 2006 ACM Symposium on Information, computer and communications security, pp. 16 25. ACM, 2006.

Ben-Or, M. and Linial, N. Collective coin flipping. Randomness and Computation, 5:91 115, 1989.

Bhagoji, A. N., Chakraborty, S., Mittal, P., and Calo, S. Analyzing federated learning through an adversarial lens. ar Xiv preprint ar Xiv:1811.12470, 2018.

Biggio, B., Nelson, B., and Laskov, P. Poisoning attacks against support vector machines. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pp. 1467 1474. Omnipress, 2012.

Blanchard, P., Guerraoui, R., Stainer, J., et al. Machine learning with adversaries: Byzantine tolerant gradient descent. In Advances in Neural Information Processing Systems, pp. 119 129, 2017.

Bonawitz, K., Ivanov, V., Kreuter, B., Marcedone, A., Mc Mahan, H. B., Patel, S., Ramage, D., Segal, A., and Seth, K. Practical secure aggregation for privacypreserving machine learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175 1191. ACM, 2017.

Bshouty, N. H., Eiron, N., and Kushilevitz, E. PAC learning with nasty noise. Theoretical Computer Science, 288(2): 255 275, 2002.

Canetti, R., Feige, U., Goldreich, O., and Naor, M. Adaptively secure multi-party computation. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 639 648. ACM, 1996.

Charikar, M., Steinhardt, J., and Valiant, G. Learning from untrusted data. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 47 60. ACM, 2017.

Chen, L., Wang, H., Charles, Z., and Papailiopoulos, D. Draco: Byzantine-resilient distributed training via redundant gradients. In International Conference on Machine Learning, pp. 902 911, 2018.

Chen, Y., Su, L., and Xu, J. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):44, 2017.

Cirincione, G. and Verma, D. Federated machine learning for multi-domain operations at the tactical edge. In Artificial Intelligence and Machine Learning for Multi-Domain Operations Applications, volume 11006, pp. 1100606. International Society for Optics and Photonics, 2019.

Diakonikolas, I., Kamath, G., Kane, D. M., Li, J., Moitra, A., and Stewart, A. Robust estimators in high dimensions without the computational intractability. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pp. 655 664. IEEE, 2016.

Diakonikolas, I., Kane, D. M., and Stewart, A. Statistical query lower bounds for robust estimation of highdimensional Gaussians and Gaussian mixtures. In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, pp. 73 84. IEEE, 2017.

Diakonikolas, I., Kamath, G., Kane, D. M., Li, J., Steinhardt, J., and Stewart, A. Sever: A robust metaalgorithm for stochastic optimization. ar Xiv preprint ar Xiv:1803.02815, 2018a.

Diakonikolas, I., Kane, D. M., and Stewart, A. Listdecodable robust mean estimation and learning mixtures of spherical Gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1047 1060. ACM, 2018b.

Diakonikolas, I., Kong, W., and Stewart, A. Efficient algorithms and lower bounds for robust linear regression. ar Xiv preprint ar Xiv:1806.00040, 2018c.

Universal Multi-Party Poisoning Attacks

Fung, C., Yoon, C. J., and Beschastnikh, I. Mitigating sybils in federated learning poisoning. ar Xiv preprint ar Xiv:1808.04866, 2018.

Guerraoui, R., Rouault, S., et al. The hidden vulnerability of distributed learning in byzantium. In International Conference on Machine Learning, pp. 3518 3527, 2018.

Haitner, I. and Omri, E. Coin flipping with constant bias implies one-way functions. SIAM Journal on Computing, 43(2):389 409, 2014.

Han, Y. and Zhang, X. Robust federated training via collaborative machine teaching using trusted instances. ar Xiv preprint ar Xiv:1905.02941, 2019.

Hayes, J. and Ohrimenko, O. Contamination attacks and mitigation in multi-party machine learning. In Advances in Neural Information Processing Systems, pp. 6604 6615, 2018.

Kearns, M. J. and Li, M. Learning in the Presence of Malicious Errors. SIAM J. on Computing, 22(4):807 837, 1993.

Koh, P. W., Steinhardt, J., and Liang, P. Stronger data poisoning attacks break data sanitization defenses. ar Xiv preprint ar Xiv:1811.00741, 2018.

Koneˇcn y, J., Mc Mahan, H. B., Yu, F. X., Richt arik, P., Suresh, A. T., and Bacon, D. Federated learning: Strategies for improving communication efficiency. ar Xiv preprint ar Xiv:1610.05492, 2016.

Lai, K. A., Rao, A. B., and Vempala, S. Agnostic estimation of mean and covariance. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pp. 665 674. IEEE, 2016.

Mahloujifar, S. and Mahmoody, M. Blockwise p-Tampering Attacks on Cryptographic Primitives, Extractors, and Learners. In Theory of Cryptography Conference, pp. 245 279. Springer, 2017.

Mahloujifar, S., Diochnos, D. I., and Mahmoody, M. Learning under p-Tampering Attacks. In ALT, pp. 572 596, 2018a.

Mahloujifar, S., Diochnos, D. I., and Mahmoody, M. Learning under p-tampering attacks. In Algorithmic Learning Theory, pp. 572 596, 2018b.

Mc Mahan, B. and Ramage, D. Federated learning: Collaborative machine learning without centralized training data. Google Research Blog, 2017.

Mc Mahan, H. B., Moore, E., Ramage, D., Hampson, S., et al. Communication-efficient learning of deep networks from decentralized data. ar Xiv preprint ar Xiv:1602.05629, 2016.

Papernot, N., Mc Daniel, P., Sinha, A., and Wellman, M. Towards the science of security and privacy in machine learning. ar Xiv preprint ar Xiv:1611.03814, 2016.

Prasad, A., Suggala, A. S., Balakrishnan, S., and Ravikumar, P. Robust estimation via robust gradient estimation. ar Xiv preprint ar Xiv:1802.06485, 2018.

Shen, S., Tople, S., and Saxena, P. A uror: defending against poisoning attacks in collaborative deep learning systems. In Proceedings of the 32nd Annual Conference on Computer Security Applications, pp. 508 519. ACM, 2016.

Steinhardt, J., Koh, P. W. W., and Liang, P. S. Certified defenses for data poisoning attacks. In Advances in neural information processing systems, pp. 3517 3529, 2017.

Tomsett, R., Chan, K., and Chakraborty, S. Model poisoning attacks against distributed machine learning systems. In Artificial Intelligence and Machine Learning for Multi-Domain Operations Applications, volume 11006, pp. 110061D. International Society for Optics and Photonics, 2019.

Valiant, L. G. Learning disjunctions of conjunctions. In IJCAI, pp. 560 566, 1985.

Yin, D., Chen, Y., Ramchandran, K., and Bartlett, P. Byzantine-robust distributed learning: Towards optimal statistical rates. ar Xiv preprint ar Xiv:1803.01498, 2018.