MaskedLARK: Timing side-channel via only sending false reports at attributionexpiry

[csharrison]

In MaskedLARK, the doc says:

In the existing aggregate reporting proposal, only actual conversions require reporting. To train a model, we require both positive samples and negative samples, meaning negative values (i.e., no conversion) also need to be sent to the ad server. We propose extending the scheduled reports framework to handle the negative cases, by sending a value when attributionexpiry is reached.

Unless real reports are also sent at the attributionexpiry, this allows distinguishing between false reports and real reports. In order to make this private we’d need to make sure both false reports and real reports are sent in a way that is indistinguishable.

In https://github.com/WICG/conversion-measurement-api/blob/main/event_attribution_reporting_views.md we do this by having a deterministic report time for both real and fake values. We could do the same in this proposal. However, this is very difficult to align with a desired use-case of getting reports quickly without much delay. If real reports are sent close to their conversion time, it is very difficult to make fake reports match that distribution. On the other hand, if attributionexpiry is short, we could suffer coverage loss.

Alternatively, you could allow some level of privacy loss if you submitted reports at a time that was protected with local differential privacy. One issue that comes up with this technique is that for true reports, the DP mechanism is only allowed to add positive noise (since time travel is not quite possible yet).

[appascoe]

@csharrison I want to make sure I understand this fully. What's the vector for privacy leakage here? I understand the potential issue through the Conversion Measurement API, but MaskedLARK seems more focused on the Aggregate Reporting API.

From my understanding, with ARAPI, the reports are encrypted locally before being sent to the DSP in an unauthenticated request. The helpers are responsible for decrypting, and any query has the ability to add noise for differential privacy, k-anonymity, and all that jazz.

At what point would a DSP have access to an information in an individual request that would allow them to know the originating timestamp for the attribution to determine that the label is a result of expiration or not?

[csharrison]

I may have misunderstood the proposal, but it seems to hook into the aggregate attributions flow via references to (e.g.) attributionexpiry. The issue here stems from the fact that aggregation keys are revealed in the clear. In order to make this privacy neutral, the keys themselves need to be public information (i.e. not a function of cross site data). In the proposal they attempt to do this by making keys a function of only 1P data (e.g. impression-side information only).

However, this does not fully solve the issue, since the presence or absence of keys can reveal cross site data (e.g. whether conversion occurred after an impression). In the proposal this is alleviated by sending reports unconditionally whether the user converted or not (and hiding whether a report represents a positive or negative example via secret sharing). This generally works, unless there is some other way of differentiating the positive and negative examples (or in other words, the real vs. fake conversions). This issue brings up one possible way of differentiating them, based on the timestamp the report is received on the ad-tech's servers.

@erik-anderson , let me know if I've misunderstood the proposal. I do think that this is a solvable problem, but there will likely be a cost somewhere in the system.

[dxcharles]

Thanks, Charlie for bringing this point up and it is a good one. We briefly discussed this during our meeting. Let me elaborate a bit more and we can also edit the description of the proposal to clarify this issue better.

A simplified description of the proposal could be that real and fake data are sent to helpers and a masking process cancels out the fake data in aggregation. Our proposal does not hide the aggregation keys, though they may be encrypted, (the values, on the other hand, are indistinguishable from random to helpers). If there’s a side-channel attack that can distinguish real data from fake, then one can learn whether a key participated in aggregation.

Here are some thoughts on the timing side-channel attacks.

Model training: We think our proposal only really handles dense features since the keys are not hidden. If we allow sparse vectors, then the sequence of the keys in each vector can act as a UserId which is not ideal. In the case of dense vectors, we can always generate fake events (since the dense vector can be generated at client) that completely cancel out for the gradient update. They can be generated at any time. Model updates need not be in sync with when the events actually occurred, since the model is just an explanation of the label given the feature vector and needs an update only if there’s distribution shift.

Aggregation: For aggregation, again fake data that fully cancels out in aggregation can be sent to helpers (again we need to be careful about timing here too). Since helpers see the key, we need to sample from the universe of actual keys according to their probability of being observed in the population. Things like sending random keys (each time) for aggregation that cancel out do not work. Since helpers can learn information by taking intersections of keys coming from a certain client and the fake keys will drop out. Also, if each client separately randomly generates keys, they will be disjoint with other clients unlike real keys. The cleaner solution seems to be to allow clients access to an oracle that samples from the universe of keys correctly. The ad network can help implementing this oracle. This works if we assume no collusion of ad network with the helpers. There are some ideas for the collusion case as well. The details of these need to be captured better in the proposal.

We will flesh this out and we can discuss this in one of our meetings.

[csharrison]

I have to say I feel more confused now.

Model training: We think our proposal only really handles dense features since the keys are not hidden. If we allow sparse vectors, then the sequence of the keys in each vector can act as a UserId which is not ideal. In the case of dense vectors, we can always generate fake events (since the dense vector can be generated at client) that completely cancel out for the gradient update.

Can you elaborate on how we distinguish dense/sparse features and why it matters for privacy? In the doc, model_features is a 100-float vector, certainly enough to embed a 1P user ID.

[fake events] can be generated at any time. Model updates need not be in sync with when the events actually occurred, since the model is just an explanation of the label given the feature vector and needs an update only if there’s distribution shift.

Why is this the case? It seems like a fake event can only be added after a given feature vector is constructed (e.g. at impression time).

Aggregation: For aggregation, again fake data that fully cancels out in aggregation can be sent to helpers (again we need to be careful about timing here too). Since helpers see the key, we need to sample from the universe of actual keys according to their probability of being observed in the population. Things like sending random keys (each time) for aggregation that cancel out do not work. Since helpers can learn information by taking intersections of keys coming from a certain client and the fake keys will drop out. Also, if each client separately randomly generates keys, they will be disjoint with other clients unlike real keys. The cleaner solution seems to be to allow clients access to an oracle that samples from the universe of keys correctly. The ad network can help implementing this oracle. This works if we assume no collusion of ad network with the helpers. There are some ideas for the collusion case as well. The details of these need to be captured better in the proposal.

I don't understand why we need to sample from the universe of actual keys. Why can't we do the same thing we do for model training and unconditionally send reports for aggregation for every attribution source, regardless of whether it actually triggers attribution or not? This way the set of all keys the helper sees is fully public knowledge and all the sensitive information is hidden in the shares.

[appascoe]

For Charlie's first point, I agree that there doesn't need to be a distinction of dense vs. sparse. The order of keys in a sparse vector can be subjected to a random permutation that would destroy any user identifier, without harming any of the mathematical properties.

[dxcharles]

Let me try to simplify the point I was trying to make. We are viewing real and fake events as creating vectors which are being aggregated, with the keys, aka names for the coordinates of the vector, sent in the clear. To hide which are real and fake events from helpers, the vectors we create in these cases should look similar (and additionally, times at which they are sent shouldn’t leak whether they are real or fake either).

In case vector is dense. Then the names for the coordinates are going to simply be 1…d, where d is the vector dimension which is fixed and remains the same for all users/clients. The task of creating a fake vector then boils down to choosing the values for each dimension. For instance, the client can pick coordinates randomly from some valid distribution for each coordinate to generate such vectors.

In the case of a sparse (still finite dimensional) vector, the name for a coordinate can have additional structure like “query = ‘car insurance’_X_advertiser = ‘Geico’.” If we had some public isomorphism to 1…d (d much larger here) from this space, we can probably do exactly what we did for dense vectors and focus on hiding the values. Otherwise, we should be careful about the coordinate names (what I'm calling keys) that are generated from a client. So that these keys don’t leak information about real vs. fake events. For example, if fake events had random <query, advertiser> pairs they may be distinguishable from real events. I was thinking about this case, where we do not have any public isomorphism to 1...d, in which case we need to pick from “legal looking” keys. [What is written above, still applies even if these are encrypted by ad network’s public key, so that helpers can’t read these keys per se.] Perhaps what Charlie wrote in his last paragraph is a way to do this, but I wanted to call out that there’s this aspect of creating legal looking keys which we also need to pay attention to in the sparse case. This is in addition to timing attacks.

[appascoe]

I just skimmed the spec again, and I don't see any indication of sending real and fake feature vectors. Certainly possible that I missed it because it was a pretty quick skim.

I believe the feature vector is fixed, but with two labels, one being real and one being fake. This results in two separate gradient vectors, with the effect that during gradient aggregation, the fake gradient updates get canceled out. But I think these gradient vectors should be providing updates in the same dimensions.

All that being said, the feature vectors could be subjected to noise, but that's different than sending spoofed ones.

[dxcharles]

Yes, it is mentioned almost in passing at the end of model training. We will call this out better. Though the more detailed example deals with hiding labels, the same idea can be used to cancel out all gradients for a feature vector or drop out terms in aggregation. These uses can have some nuances that need to be clarified a bit.

[appascoe]

Ah, the "Noisy Insertions" section, under "Other Considerations." I didn't realize this was intended to be an actual part of the spec, just an open question.

While there was a credible attack against it, so I haven't pushed on it further, MURRE includes some techniques that could get around this. If we use the hashing trick, we could guarantee that any keys have to fall in a given range, though it won't be an isomorphism anymore due to hash collisions. At that point, the browser could 1) drop certain features (encoded as integers), and 2) if the browser knows the domain (which it should since it can compute the hash), it can add integers to the set of features by randomly drawing from this domain.

Of course, the main attack against MURRE is still able to abuse this system unless the probability of dropping/adding features is very high: https://github.com/AdRoll/privacy/issues/1 . However, if in MaskedLARK, we're only talking about feature vectors on the order of 100 dimensions, this attack may not be as feasible as what MURRE was proposing (much higher dimensionality there). 100 dimensions would create a lot of hash collisions, but maybe this isn't too deleterious to a model... it really depends on the model.

Personally, I think this is an issue regarding any mechanism that provides arbitrary keys. I filed an issue on the Aggregate Reporting API relating similar attacks: https://github.com/csharrison/aggregate-reporting-api/issues/18