Today we'll look at two papers from ACM CCS, one about to be presented at CCS 2017, and one presented at CCS 2015 two years ago. Both are chiefly about deep learning and privacy, but they touch on differential privacy, and so I thought it would be good to talk through the two of them. The two papers are somewhat in opposition, which means there is unlikely to be a happy resolution.
The first paper is Privacy-Preserving Deep Learning, from ACM CCS 2015. The paper describes an approach to deep learning in which participants do not share their raw data, but instead share only partial information about how their raw data affect the training process. From their abstract:
In this paper, we design, implement, and evaluate a practical system that enables multiple parties to jointly learn an accurate neural-network model for a given objective without sharing their input datasets.
The second paper is Deep Models Under the GAN: Information Leakage from Collaborative Deep Learning, to appear at ACM CCS 2017. This paper demonstrates an attack on collaborating learning approaches, and demonstrate specifically that the method proposed in CCS 2015 is pretty broken. From their abstract (emphasis theirs):
In particular, we show that a distributed, federated, or decentralized deep learning approach is fundamentally broken and does not protect the training sets of honest participants.
My interest is somewhat peripheral; the first paper considers the addition of differentially private noise to the learning process (yay) and the second paper concludes that differential privacy is not helpful (boo); from the abstract of CCS 2017:
Interestingly, we show that record-level differential privacy applied to the shared parameters of the model, as suggested in previous work, is ineffective (i.e., record-level DP is not designed to address our attack).
Clearly there is going to be something of a train wreck here, because these two papers can't both be correct. The first one says that they do collaborative deep learning while preserving privacy, and the second says you can't do collaborative deep learning while preserving privacy. One of the two of them has to be wrong, right?
Well, at least one of the two of them has to be wrong. Just because they can't both be right doesn't mean they can't both be wrong, which to my reading they both are.
The first paper (henceforth "CCS 2015") proposes a relatively natural approach based on federated learning, and then adds some flavor in the name of privacy. First, let's talk about federated learning (or read the link, which is good).
In traditional "centralized" learning, a large pile of training examples are assumed to exist in some convenient location. A clever person describes a cunning algorithm, and it goes to work using all of the training examples as inputs. This can be a bit stressful if you feel that the training data you would contribute are sensitive. You might not want all of your photos, or all of the text you type in your email client, or whatever to be uploaded and stored by Google, even in the name of delivering better advertisements to you.
The "federated" learning approach does away with the centralized store of information, and instead restricts itself to computations that can be performed in part locally (on your device, say), and in part centrally (aggregating results from multiple devices). One common example is Stochastic Gradient Descent, where some common set of parameters describe a model, and each participant repeatedly suggests a direction the parameters should move to provide better classification or prediction or whatever. The gradients are not data themselves, and so having your device share them seems to be a more palatable approach to things, privacy-wise.
The CCS 2015 paper proposes federated learning as a privacy-friendly way to do machine learning. Roughly, they propose to do distributed stochastic gradient descent, where each participant has the option to randomly discard some of their parameter updates, and to obscure them with differential privacy if that is your sort of thing.
Our key technical innovation is the selective sharing of model parameters during training. This parameter sharing, interleaved with local parameter updates during stochastic gradient descent, allows participants to benefit from other participants’ models without explicit sharing of training inputs. Our approach is independent of the specific algorithm used to construct a model for a particular task. Therefore, it can easily accommodate future advances in neural-network training without changing the core protocols.
To summarize their claims about this approach, let me quote them again:
Even without additional protections, our system already achieves much stronger privacy, with negligible utility loss, than any existing approach. Instead of directly revealing all training data, the only leakage in our system is indirect, via a small fraction of neural-network parameters. To minimize even this leakage, we show how to apply differential privacy to parameter updates using the sparse vector technique, thus mitigating privacy loss due to both parameter selection (i.e., choosing which parameters to share) and shared parameter values. We then quantitatively measure the tradeoff between accuracy and privacy.
This paragraph sounds pretty sweet, but it starts to get at where the authors get into trouble, which is with a quantification of privacy. There are clear claims of "stronger" privacy, and quantitative measurement of privacy, and we are going to try and chase these down and see what they mean. They also claim "negligible utility loss", which is going to come up again.
Unfortunately, nothing I have read in their paper suggests that you can't just read the source data (photos, let's say) back out of the gradients that the participants report. Weren't those gradients not the data? As it turns out, for at least one of the deep learning network topologies some of the gradients are just scaled versions of your input after all.
One of the models that the authors consider is the multilayer perceptron, which connects multiple perceptrons (details in a moment) into a larger, deeper network. Each individual perceptron works by taking a collection of source signals, think real-valued numbers like maybe pixel intensities, multiplying each source signal by some weight, and then adding up the results. If you think of the input signals as high-dimensional vector, the perceptron does its classification by taking an inner product with a vector of weights. These weights are the model parameters, and they are what need to be updated if it turns out the model isn't yet doing a good job.
A multilayer perceptron is a bunch of perceptrons stacked in layers, typically with some non-linear function applied to the aggregation (like the logistic function). This allows the multilayer perceptron to learn interesting non-linear functions of the input data. Of course, we still have to attach some first layer of perceptrons to the image itself; note: multiple perceptrons attached to the input (e.g. pixels).
So, how does the multilayer perceptron gradient update work? Mostly commonly through backpropagation. Backpropagation is an approach for training networks where you supply an input, observe the activations it produces (the inner products then non-linear functions, for each layer), and then check the result the network produces against the output you wanted (e.g. "picture of Frank, or of goat?"). There will probably be some error, so you then propagate the error backwards, updating the weights that you used to take the inner products to make the inner product larger when you need larger and smaller when you need smaller. How do you do that? Usually, you add some multiple (positive or negative) of the vector of activations.
This is all great abstractly, but if your input is an image the those "activations" for the input layer are the pixels of your input image, just scaled a bit to indicate just how happy you were with the result you saw (e.g. "more of my image!" or "less of my image!"). Up to that one scaling factor, the gradients for the input layer are your image.
You could drop out all but 1% of the parameter updates, as the authors propose, so now you are only revealing 1% of the pixels in your image for each perceptron update. Unfortunately, the multilayer perceptron is "fully connected", which means that there are several perceptrons attached to your image, and each of them are going to be updating their weights with some multiple of your input image. If you have 100 such internal nodes, then dropping 1% of the gradient updates still leaves you with about 1/e of your pixels revealed. The ambiguous scaling factor doesn't save you either, because there are likely to be pixels in common, and you can solve for the scaling that was applied.
Gradient updates can reveal much of your source data in the clear. Just dropping a few of the updates doesn't help. Note that the above isn't a demonstration of an attack, which would be much clearer about whether I am making this up, but it should at least convince you that "releasing gradients, not data" is not especially indirect leakage.
What you could do, and what the authors do eventually discuss, is adding noise to the updates shaped to provide differential privacy. These updates are going to be accumulated, and so your noise should cancel with all the noise other people have added.
You absolutely can do differentially private perceptron updates, something we described way back in the SuLQ paper before we had even named "differential privacy". We didn't do it "federated" or anything, but it all works out. You need to calibrate the amount of noise that you add to the gradient updates by the norm of the largest input (so, work on normalized images, as I believe the authors do), but this guarantees that you leak at most epsilon differential privacy with each update to a perceptron.
Of course, there are many perceptrons going on here, many more than just one. Still, you can add Laplace noise to each of the gradient updates that you submit, which provides differential privacy for that single gradient update. Here is an example figure from their evaluation.
The x-axis is "privacy budget per parameter", which turns out to be the overall differential privacy guarantee for the gradient update, divided by the number of parameters submitted. So when they say 0.1, you should think "wow something much, much larger". The number of parameters in the models the authors use are in the hundreds of thousands, so to get the privacy cost you would multiply the number of the x-axis by the fraction of parameters submitted (their theta, which are various negative powers of ten) by the number of parameters (for MNIST CNN it is 105,506).
epsilon = per-parameter * theta * 105,506
The line the authors are trying to beat is the flat line labeled "standalone", where each participant just uses their own data, with no sharing. The measurements where the "differential privacy" lines cross that horizontal baseline all have privacy guarantees of (using the formula above) 10,550.6 differential privacy. That's not so great.
Also, this is only the per-epoch differential privacy cost. They run multiple (unspecified) epochs to get the accuracy they report.
I don't think the techniques the authors propose provide "privacy", in any sense other than that you don't literally directly reveal your naughty photos to everyone, which might remove some of the social awkwardness. Except that you mostly do, if you use the multilayer perceptron. The "fractions of gradients reported" is probably not a valuable privacy quantification, in that the multilayer perceptron gives each pixel multiple chances to be revealed, and what we probably want is the total number of parameters updated. The "per-parameter differential privacy" guarantee is similarly problematic, in that you still have to multiply by the number of parameters revealed each epoch, and then by the number of epochs (which are not reported).
This sounds a bit grim, so I'm happy to slot in any further illumination the authors would like to provide. It is possible that I've misread something, of course. If the "negligible utility loss" comes with either "releasing pixels in the clear" or "10,550.6 differential privacy", it doesn't seem like a great trade-off yet.
The second paper we are looking at today (henceforth: "CCS 2017") stands in opposition to CSS 2015. In fact they take a quite strong position that any collaborative deep learning approach is susceptible to their privacy attack.
Unfortunately, we show that any privacy-preserving collaborative deep learning is susceptible to a powerful attack that we devise in this paper.
Unfortunately, we will see that this isn't entirely true. Unless "susceptible" means something I don't think it means. Moreover, later in the paper (page 3) they do have a clarifying concession:
The results of our attack may or may not be regarded as privacy violations.
Perhaps susceptible means "may or may not be a violation", in the same way that all banks are susceptible to my powerful "I am bank prezident; please give all the monies" attack, which may or may not result in all the monies.
The attack of CCS 2017 is conceptually relatively simple: they install an adversary as a participant, whose job it is to learn representative examples from one of the classes that the honest participants are trying to learn. For example, if you all have pictures and are trying to learn "cat" versus "dog", the adversary picks one of "cat" or "dog" and uses Generative Adversarial Networks (GAN) techniques to learn representative examples of that class.
At this point the authors of CCS 2017 announce success, because it could be that you are the only person with pictures labeled "dog" and you really wanted to keep them secret. And it actually could be that this is the case, and you would be right to be upset.
There are a few issues with this line of reasoning.
First, there is a fundamental difference between attacking a "class" and attacking a "participant". The former is learning statistical information about the training data, and the second is learning specific information about a participant. It could certainly happen to be that these are the same, but it has to happen to be; the authors' attack cannot make it happen if it is not the case. It's a bit like how learning the median salary in a US Census tract could be a privacy violation if you happen to be the only person there; it could be the case, but it would be a bit much to then claim that all of statistics "is fundamentally broken and does not protect the training sets of honest participants".
Second, the authors imagine that the learning approach is obliged to correctly reveal the details of the class, even if it has only a single member. If the learning approach fails to do so, the authors imply that this means that the learning approach is somehow defective. In fact, it makes a great deal of sense for any learning approach to avoid overfitting to specific inputs, and to only provide detailed information about classes for which there is broad statistical support. Many (if not most) reasonable learning approaches will not continue to fit the description of a class to a single training example, which seems to deflect the proposed attack.
While it is reasonable to worry about the first concern, the remedy is simply to properly address the second concern. Many learning mechanisms do so informally when they avoid overfitting, and those that use differential privacy (among perhaps other techniques) do so quite formally. Theorems and everything.
Said differently, where the authors claim
Our attack works whenever the model can accurately classify a class and will generate representatives of that class.
What I think they should have said is
Our attack works whenever the model must accurately classify a class and will generate representatives of that class.
What the authors show, and it is a not-unreasonable thing to observe, is that an over-fitting federated learning approach, one that can be relied upon to continue to fit a single-member class to exhaustion, can be encouraged by an adversary to reveal a detailed view of members isolated in their own classes. Experimentally, CCS 2017 shows that CCS 2015 is such an over-fitting learning approach, and ACM CSS generally should learn never to do such a thing ever again.
This is however a far cry from their claim that
[A] distributed, federated, or decentralized deep learning approach is fundamentally broken and does not protect the training sets of honest participants.
I don't see any sense in which the breadth of this claim is justified.
As a final analogy, perhaps closer to ACM CCS's core expertise, imagine that instead of "deep learning" the paper was about "password-based access control". The hypothetical abstract asserts that any password-based access control is susceptible to a powerful attack the authors devise, and it is not until Section 7 that you learn that the "attack" is brute-forcing the password. The access-control mechanism is obviously obliged to respond to password requests indefinitely, so say the authors, and so they simply try everything out. The possibility that the access control mechanism might stop responding to requests after a few failed attempts is mentioned in the final paragraph of the conclusions, and is left "for future work".
This isn't a perfect analogy; it would be a better analogy if instead of rejecting a password the mechanism responded with "warmer" or "colder", allowing an efficient attack to reconstruct the password. At the same time, I suspect the collected ACM CCS community would still wonder why terminating access after a few failed attempts wasn't at the front of the authors' minds. Would they comfortably accept that "all password-based access control mechanisms are fundamentally broken" without caveats? Probably not, right?
Throughout the paper, the authors repeatedly remark that their attack works even when one applies differential privacy.
The attack we devise is also effective when parameters are obfuscated via differential privacy. We emphasize that it is not an attack against differential privacy but only on its proposed use in collaborative deep learning. In practice, we show that differentially private training as applied in [77] and [1] (example/record-level differential privacy) is ineffective in a collaborative learning setting under our notion of privacy.
It has taken a frustratingly large amount of reading to unpack why I think they are wrong.
The CCS 2017 paper repeatedly refers to "record-level" differential privacy, which is typically used to refer to privacy guarantees made of individual records in input collections, rather than higher-level entities that they might represent. For example, if your cell phone has 1,000 pictures on it, I could use differential privacy to mask the presence or absence of each picture from your phone, but I might reveal a statistical trend about pictures on your phone, which could reveal information about you the phone's owner. On the other hand, if I am a hospital I may have records about 1,000 patients, at which point it may be reasonable to only provide privacy guarantees about these records, rather than about my collection of records. So "record-level" differential privacy does typecheck here.
However, CCS 2015 (citation [77]) does not propose using record-level differential privacy. To quote from CCS 2015 (emphasis mine):
Let the total privacy budget for each epoch of DSSGD for each participant i be ε.
Pretty clear. To quote from CCS 2017 (emphasis mine):
For each epoch (iteration) of the collaborative learning process, [CCS 2015] define a total privacy budget ε for each participant.
So both papers agree that the differential privacy budget is set by per participant, rather than per record. And, to the best of my understanding, the CCS 2017 evaluation uses the code from CCS 2015, which uses a per-participant privacy budget (at least, in each epoch). So where does the "record-level differential privacy" come from?
It's hard to tell. CCS 2017's citation [1], Deep Learning with Differential Privacy does use record-level differential privacy, but doesn't seem to advocate for it in contrast to participant-level privacy. But this seems almost immaterial in that the attacked system doesn't use record-level privacy budgets; if it were redesigned to do so, you could plausibly lay the blame on the record-level calibration, but to do so for a system that doesn't use the calibration seems wrong.
A better source of concern is that both CCS 2015 and CCS 2017 use utterly ridiculous settings for the per-participant privacy levels. We've seen how large the privacy costs were for CCS 2015, but CCS 2017 ramps them up even higher.
On Figures 11 and 14, we provide results for a privacy budget per parameter (ε/c) of 100 and 10 and varying upload rate (θu).
Remember this is per-parameter budgets, which still need to be multiplied by the number of release parameters, in the ten thousand range.
To give a sense for 100-differential privacy, imagine you have a 64bit floating point number representing your computed gradient that you would like to release with 100-differential privacy. Here is one way you can do that:
- Generate two independent uniformly random 64 bit floating point numbers.
- If the two random numbers are equal release their common value, otherwise release the true data.
The probability of releasing anything other than the true answer is 1/2^64, and the probability of releasing any specific value (other than the true answer) is 1/2^128. The probability of releasing the true answer is 1 - 1/2^64 + 1/2^128, which is basically one. When we take the natural logarithm of 2^128, the factor by which the probability of any output changes when the true answer is changed, we get
epsilon = ln(2^128) = 128 * ln(2) = 88.722839111673
This release mechanism has 88.8 differential privacy, and is nonetheless pretty much guaranteed (probability 1 - 1/2^64) to release the "secret" number in the clear.
Differential privacy does a fine job protecting the data of participants, especially when privacy budgets are set at the per-participant level.The problem with CCS 2015 is that it does not provide sane differential privacy bounds (e.g. 10,550.6-DP), and that the per-participant bounds need to be multiplied by the number of epochs, not that the budgets are set at the record level.
Another conclusion the authors of CCS 2017 reach is that if you set epsilon to be non-enormous, then the results are miserable. Let's look at a figure from their paper
The value of epsilon is still really quite large here (because the 0.01 needs to be multiplied by both the number of gradients released and epochs performed), and the GAN seems to have produced meaningless results. The authors claim that this is because the model accuracy does not increase, but it would have been best to present that data (e.g. misclassification rates). If the collaborative learning was working fine and only the GAN was failing then there isn't really a problem.
Nonetheless, I do believe them that no learning is happening, because .. well let's have them explain their set-up.
To demonstrate that record-level differential privacy is ineffective against an active adversary, we ran the collaborative learning process between the two participants (A and V) with differential privacy enabled. We kept the datasets of the participants distinct: In MNIST experiments, V had only records of classes from 0 to 4 and A had records of classes from 5 to 9 plus the artificial class that A introduces.
Here A is the adversary and V is the single non-adversarial participant. CSS 2017 evaluates a deep learning approach with just one honest participant, whose gradients are noised with a per-participant privacy budget calibrated to conceal each gradient contribution (except not really because 100-DP). It is not a wonder that nothing works.
Now, I don't know that things should work. Distributed stochastic gradient descent for deep learning does just about everything you wouldn't want to do to make differential privacy work well: (i) gradient updates are treated as public and must be noised by participants (rather than centrally), (ii) the dimensionality of the gradients is high meaning participants must scale their noise up proportionately, and (iii) you perform some unknown number of iterations to make progress.
Based on these properties, I would say that distributed stochastic gradient descent for deep learning is perhaps the least-suited problem for differential privacy; it is great to study, but I'm not at all bummed out to hear that it doesn't work.
EDIT: I mentioned this to Kunal Talwar who gleefully pointed me at their recent work Learning Differentially Private Language Models Without Losing Accuracy, which demonstrates differentially privacy federated learning using per-participant privacy budgets, apparently without losing accuracy. Their secret? Use more than one participant! Many more, in fact; they use 763,430 participants in their headline results. Nonetheless, their paper seems to be a very concrete refutation of the main thesis of CCS 2017, that federated deep learning is fundamentally broken.
Kunal also mentioned that while it is easy to be flip about "don't overfit", deep learning generally does overfit, and differential privacy is one of the few known counter-measures here. To the extent that CCS 2017 is a cautionary tale broadening the class of learning algorithms that can be attacked, that is worth understanding. But it is also worth understanding that there are techniques that by definition prevent these attacks, and muddying that water is counterproductive.
What the heck is going on in ACM CCS? Combined with the Differential Privacy as a Mutual Information Constraint paper from ACM CCS 2016, this is three years in a row where there are papers at least in part about differential privacy that seem seriously flawed. I'm a bit worried that it is CCS's reviewing rather than federated deep learning that is fundamentally broken.
As mentioned above, this is all conditional on my interpretation of the technical statements in these papers being correct. Many of the technical statements were subject to interpretation, which is something of a bug itself, but if there is some re-interpretation of the results of either paper that are less deranged than I've presented them, I'd love to know. Presumably the CCS program committee at least had high confidence in the less deranged interpretations as part of their review process, so someone out there can clear things up, right?
I solicited input on the text from Kunal Talwar and Ilya Mironov, who are both former colleagues of mine but are also authors on [1]. They clearly have some bias towards the belief that privacy-preserving deep learning is possible, in part because they have papers demonstrating as much (caveat: [1] was published in ACM CCS 2016, but it seems to have skipped the curse).