Long-term Data Sharing �under Exclusivity Attacks

​

​

ITCS, Shanghai University of Finance and Economics, April 2023

Kindly supported by ERC grant 740435

​

Moshe Tennenholtz

Technion, Israel

Yotam Gafni

Technion, Israel

Motivation: �A growing interest in building shared models…

Building shared models – a simple use case

• Two real estate marketplaces want to predict house prices
• Users randomly go to each, so the joint data should better predict
• They want to run linear regression of the price vs. square ft
• They want to keep updating the model as more data is added

Great… Where is the problem?

• There are works that study strategic data sharing:
• Disincentives to effort exertion in collecting data [Blum et. al 21’]
• Privacy concerns [Dwork et. al 06’, …]
• Mutually beneficial information design in competitive markets [Gradwohl & Tennenholtz 21’,22’]
• Partitioning into coalitions of shared model building [Donahue & Kleinberg 21’]

Other works study how competition changes the nature of individual learning (without sharing):

• Designing models to take over a submarket [Ben-Porat and Tennenholtz 19’]
• Trading off bias and variance when learning under competition [Feng et. al 22’]

​

We talk about a different security risk we call exclusivity attacks

• Exclusivity attack – by sending distorted data, a firm can learn the best model fit, but also mislead the other firm. (Though top priority is to learn the best model)
• This is an understudied attack [Shoham & Tennenholtz 2005] [Kantarcioglu and Jiang 2013]

Main Question:

• Given a communication protocol and learning algorithm,

where all agents report truthfully and accept the model estimation

can an attacker deviate successfully with an exclusivity attack?

​

Main Results:

• Continuous Protocol:

​

​

​

​

• Periodic Protocol: d-LR, k-Center are not vulnerable.

​

​

A successful attack with one-shot data sharing

• Max
• Agent 1 has the number 10.
• Agent 2 has the number 20.
• If they share truthfully, they both know the max is 20.
• If agent 1 sends 25 instead…
• Agent 2 now thinks the true max is 25
• Can agent 1 know the true max for sure?

A failed attack with one-shot data sharing

One-shot vs long-term

• Data collaboration is usually a long-term project with ongoing updates
• + Risk: An attacker has the option to submit multiple updates and learn more
• Simple example: [Kantarcioglu and Jiang 2013] show that average can not be learnt in one-shot. But with two samples, it can be.
• Sybil attacks make blocking this hard
• + Benefit: An attacker must consider future consequences of data corruption

​

Why long-term attacks are easier: �Learning average with two requests

Why long-term attacks are hard: �No ‘garbage’ attacks on max

Formal model – Continuous Protocol

‘Garbage Attack’ in the continuous protocol with Max

Revisiting max in the continuous protocol.

Here 90 < y < x.

Agent 1 is strategic. Agent 2 is truthful.

Observed history, Strategy and Vulnerability

Observed history, Strategy and Vulnerability (Cont.)

​

​

​

​

• We consider deviations from truthfulness, i.e., all other agents act truthfully.

​

K-center

• Among a set of points, choose k centers that minimize the maximal distance between any point and its closest center.

​

​

​

​

In this example:

• 1-center: {0}. 2-center: {-2,6}. 4-center: {-4,-2,0,6}

​

0

-2

-4

5

6

7

`Sneak attacks’: A Recipe for vulnerability

• General idea: The attacker identifies some special condition, and performs the attack.
• The attack misleads others, but the attacker can still infer true output. Later, the attacker is able to ``re-sync’’ the ledger

​

Sneak attack on k-center with k=3

Sneak attack on K-center (Cont.)

K-center and Vulnerable*

• Explicit-lie: A strategy that send a data point that does not factually exist.
• Omission: All other non-truthful strategies
• The sneak attack we just saw was an omission attack
• Vulnerable* requires explicit-lie
• There are full runs where j receives no factual update…

​

Set-choice algorithms

Attacks on set-choice algorithms with forceable winners can not explicitly lie

Linear regression

Challenge:

How to ‘reverse’ effects of fake points submitted?

A sneak attack

• What if the line of the last output and the new update (by itself) are the same?

Triangulation attacks

High level construction of triangulation for LR

Example of a triangulation attack (1-LR)

Under truth

Under triangulation

Example of a triangulation attack (2-LR)

The periodic communication model

In periodic model, LR is not vulnerable

Future directions, discussion

• Protocol hierarchy
• Non-truthful equilibria and behavior
• Decentralized implementation
• Approximate/Stochastic versions and mechanisms
• Temporal differences between agents

​

Future research preview: �What happens when we introduce noise?��Idea: Return the LR estimator with small additive noise

��Take away messages:�����Thanks for listening!

• Email me at - yotam.gafni@campus.technion.ac.il
• EC’22 version: https://dl.acm.org/doi/10.1145/3490486.3538311
• Mechanism Design for Data Science group - https://mdds.net.technion.ac.il/

​

• The choice of protocol matters for security against exclusivity attacks, and this might require sacrifice of high availability
• The # Sybils an attacker controls matters for the security of the system, and we derive exact bounds
• Implications for federated learning