Robustness of Locally Differentially Private Graph Analysis Against Poisoning Jacob Imola UC San DiegoAmrita Roy Chowdhury

2025-05-03 0 0 1.87MB 22 页 10玖币

侵权投诉

Robustness of Locally Differentially Private Graph Analysis Against Poisoning

Jacob Imola∗

UC San Diego

Amrita Roy Chowdhury∗

UC San Diego

Kamalika Chaudhuri

UC San Diego

Abstract

Locally differentially private (LDP) graph analysis allows

private analysis on a graph that is distributed accross multiple

users. However, such computations are vulnerable to data

poisoning attacks where an adversary can skew the results by

submitting malformed data. In this paper, we formally study

the impact of poisoning attacks for graph degree estimation

protocols under LDP. We make two key technical contribu-

tions. First, we observe LDP makes a protocol more vulnera-

ble to poisoning – the impact of poisoning is worse when the

adversary can directly poison their (noisy) responses, rather

than their input data. Second, we observe that graph data is

naturally redundant – every edge is shared between two users.

Leveraging this data redundancy, we design robust degree

estimation protocols under LDP that can signiﬁcantly reduce

the impact of data poisoning and compute degree estimates

with high accuracy. We evaluate our proposed robust degree

estimation protocols under poisoning attacks on real-world

datasets to demonstrate their efﬁcacy in practice.

1 Introduction

Federated analytics enable a data analyst to glean useful infor-

mation from data distributed across multiple users, without the

need for centrally pooling the data. An important class of tasks

in federated analytics constitutes computing statistics over

graph data, which has wide-spread applications ranging from

market value prediction [38], fake news detection [8] to drug

development [27]. More often than not, the graph encodes

sensitive user information, such as social network data, which

raises privacy concerns. Additionally, recent privacy regula-

tions, such as GDPR [3] and CCPA [4], have made it legally

obligatory for organizations to updold data privacy. To this

end, local differential privacy (LDP) is currently the most pop-

ular model for achieving data privacy for federated analytics.

LDP has been deployed by major commercial organizations,

such as Google [24,26], Apple [28] and Microsoft [21].t*

*The ﬁrst two authors have made equal contributions.

<latexit sha1_base64="vHJlzNlNbmXQOyxFuDi0QsChg1Q=">AAAB6nicbVBNS8NAEJ3Ur1q/qh69LBbBU0mqoMeiF48V7Qe0oWy2k3bpZhN2N0IJ/QlePCji1V/kzX/jts1BWx8MPN6bYWZekAiujet+O4W19Y3NreJ2aWd3b/+gfHjU0nGqGDZZLGLVCahGwSU2DTcCO4lCGgUC28H4dua3n1BpHstHM0nQj+hQ8pAzaqz0IPpev1xxq+4cZJV4OalAjka//NUbxCyNUBomqNZdz02Mn1FlOBM4LfVSjQllYzrErqWSRqj9bH7qlJxZZUDCWNmShszV3xMZjbSeRIHtjKgZ6WVvJv7ndVMTXvsZl0lqULLFojAVxMRk9jcZcIXMiIkllClubyVsRBVlxqZTsiF4yy+vklat6l1Ua/eXlfpNHkcRTuAUzsGDK6jDHTSgCQyG8Ayv8OYI58V5dz4WrQUnnzmGP3A+fwD6p42Y</latexit>

R(l1)

<latexit sha1_base64="Pa3beMgPzbtSwGlSJdkptk2uGU8=">AAAB7XicbVBNSwMxEJ2tX7V+VT16CRahXspuK+ix6MVjFfsB7VKyabaNzSZLkhXK0v/gxYMiXv0/3vw3pu0etPXBwOO9GWbmBTFn2rjut5NbW9/Y3MpvF3Z29/YPiodHLS0TRWiTSC5VJ8CaciZo0zDDaSdWFEcBp+1gfDPz209UaSbFg5nE1I/wULCQEWys1Lov87533i+W3Io7B1olXkZKkKHRL371BpIkERWGcKx113Nj46dYGUY4nRZ6iaYxJmM8pF1LBY6o9tP5tVN0ZpUBCqWyJQyaq78nUhxpPYkC2xlhM9LL3kz8z+smJrzyUybixFBBFovChCMj0ex1NGCKEsMnlmCimL0VkRFWmBgbUMGG4C2/vEpa1YpXq1TvLkr16yyOPJzAKZTBg0uowy00oAkEHuEZXuHNkc6L8+58LFpzTjZzDH/gfP4AY8WOWQ==</latexit>

R(l2)

<latexit sha1_base64="q30aT1P1i/a0OEihv8mKeYxGXgo=">AAAB7XicbVBNSwMxEJ2tX7V+VT16CRahXspuK+ix6MVjFfsB7VKyabaNzSZLkhXK0v/gxYMiXv0/3vw3pu0etPXBwOO9GWbmBTFn2rjut5NbW9/Y3MpvF3Z29/YPiodHLS0TRWiTSC5VJ8CaciZo0zDDaSdWFEcBp+1gfDPz209UaSbFg5nE1I/wULCQEWys1Lov8371vF8suRV3DrRKvIyUIEOjX/zqDSRJIioM4VjrrufGxk+xMoxwOi30Ek1jTMZ4SLuWChxR7afza6fozCoDFEplSxg0V39PpDjSehIFtjPCZqSXvZn4n9dNTHjlp0zEiaGCLBaFCUdGotnraMAUJYZPLMFEMXsrIiOsMDE2oIINwVt+eZW0qhWvVqneXZTq11kceTiBUyiDB5dQh1toQBMIPMIzvMKbI50X5935WLTmnGzmGP7A+fwBZUqOWg==</latexit>

R(ln)

<latexit sha1_base64="mg4fwP97CEvNcQA/nhbSuN0ApAQ=">AAAB7XicbVBNSwMxEJ2tX7V+VT16CRahXspuK+ix6MVjFfsB7VKyabaNzSZLkhXK0v/gxYMiXv0/3vw3pu0etPXBwOO9GWbmBTFn2rjut5NbW9/Y3MpvF3Z29/YPiodHLS0TRWiTSC5VJ8CaciZo0zDDaSdWFEcBp+1gfDPz209UaSbFg5nE1I/wULCQEWys1Lov87447xdLbsWdA60SLyMlyNDoF796A0mSiApDONa667mx8VOsDCOcTgu9RNMYkzEe0q6lAkdU++n82ik6s8oAhVLZEgbN1d8TKY60nkSB7YywGellbyb+53UTE175KRNxYqggi0VhwpGRaPY6GjBFieETSzBRzN6KyAgrTIwNqGBD8JZfXiWtasWrVap3F6X6dRZHHk7gFMrgwSXU4RYa0AQCj/AMr/DmSOfFeXc+Fq05J5s5hj9wPn8AwHaOlg==</latexit>

<latexit sha1_base64="cGrDOFyL5pGKO3TAZPX9es7d10c=">AAAB6nicbVBNS8NAEJ3Ur1q/qh69LBbBU0mqoMeiF48V7Qe0oWy2k3bpZhN2N0IJ/QlePCji1V/kzX/jts1BWx8MPN6bYWZekAiujet+O4W19Y3NreJ2aWd3b/+gfHjU0nGqGDZZLGLVCahGwSU2DTcCO4lCGgUC28H4dua3n1BpHstHM0nQj+hQ8pAzaqz0IPq1frniVt05yCrxclKBHI1++as3iFkaoTRMUK27npsYP6PKcCZwWuqlGhPKxnSIXUsljVD72fzUKTmzyoCEsbIlDZmrvycyGmk9iQLbGVEz0sveTPzP66YmvPYzLpPUoGSLRWEqiInJ7G8y4AqZERNLKFPc3krYiCrKjE2nZEPwll9eJa1a1buo1u4vK/WbPI4inMApnIMHV1CHO2hAExgM4Rle4c0Rzovz7nwsWgtOPnMMf+B8/gD8K42Z</latexit>

<latexit sha1_base64="0Hy/XpvHXA+f7+UFXWowhanbZu8=">AAAB6nicbVBNS8NAEJ3Ur1q/qh69LBbBU0mqoMeiF48V7Qe0oWy2m3bpZhN2J0IJ/QlePCji1V/kzX/jts1BWx8MPN6bYWZekEhh0HW/ncLa+sbmVnG7tLO7t39QPjxqmTjVjDdZLGPdCajhUijeRIGSdxLNaRRI3g7GtzO//cS1EbF6xEnC/YgOlQgFo2ilB9lX/XLFrbpzkFXi5aQCORr98ldvELM04gqZpMZ0PTdBP6MaBZN8WuqlhieUjemQdy1VNOLGz+anTsmZVQYkjLUthWSu/p7IaGTMJApsZ0RxZJa9mfif100xvPYzoZIUuWKLRWEqCcZk9jcZCM0ZyokllGlhbyVsRDVlaNMp2RC85ZdXSatW9S6qtfvLSv0mj6MIJ3AK5+DBFdThDhrQBAZDeIZXeHOk8+K8Ox+L1oKTzxzDHzifP1cqjdU=</latexit>

User%1

User%2

User%n

Data%

Aggregator

<latexit sha1_base64="el+ant67oFU9GIKpYdQ05/L4FLQ=">AAAB63icbVBNS8NAEJ3Ur1q/qh69LBbBU0mqoMeiF48V7Ae0oWy2m3bp7ibuToRS+he8eFDEq3/Im//GpM1BWx8MPN6bYWZeEEth0XW/ncLa+sbmVnG7tLO7t39QPjxq2SgxjDdZJCPTCajlUmjeRIGSd2LDqQokbwfj28xvP3FjRaQfcBJzX9GhFqFgFDPpse+V+uWKW3XnIKvEy0kFcjT65a/eIGKJ4hqZpNZ2PTdGf0oNCib5rNRLLI8pG9Mh76ZUU8WtP53fOiNnqTIgYWTS0kjm6u+JKVXWTlSQdiqKI7vsZeJ/XjfB8NqfCh0nyDVbLAoTSTAi2eNkIAxnKCcpocyI9FbCRtRQhmk8WQje8surpFWrehfV2v1lpX6Tx1GEEziFc/DgCupwBw1oAoMRPMMrvDnKeXHenY9Fa8HJZ47hD5zPHzdljbE=</latexit>

<latexit sha1_base64="F1SLfhxyjKG+7GV4ARO6+vL7XGk=">AAAB63icbVBNS8NAEJ3Ur1q/qh69LBbBU0mqoMeiF48V7Ae0oWy2m3bp7ibuToRS+he8eFDEq3/Im//GpM1BWx8MPN6bYWZeEEth0XW/ncLa+sbmVnG7tLO7t39QPjxq2SgxjDdZJCPTCajlUmjeRIGSd2LDqQokbwfj28xvP3FjRaQfcBJzX9GhFqFgFDPpsV8r9csVt+rOQVaJl5MK5Gj0y1+9QcQSxTUySa3tem6M/pQaFEzyWamXWB5TNqZD3k2ppopbfzq/dUbOUmVAwsikpZHM1d8TU6qsnagg7VQUR3bZy8T/vG6C4bU/FTpOkGu2WBQmkmBEssfJQBjOUE5SQpkR6a2EjaihDNN4shC85ZdXSatW9S6qtfvLSv0mj6MIJ3AK5+DBFdThDhrQBAYjeIZXeHOU8+K8Ox+L1oKTzxzDHzifPzjqjbI=</latexit>

<latexit sha1_base64="M2vvY5tdvNAOpgsSxu0oqpxgX/k=">AAAB63icbVBNS8NAEJ3Ur1q/qh69LBbBU0mqoMeiF48V7Ae0oWy2m3bp7ibuToRS+he8eFDEq3/Im//GpM1BWx8MPN6bYWZeEEth0XW/ncLa+sbmVnG7tLO7t39QPjxq2SgxjDdZJCPTCajlUmjeRIGSd2LDqQokbwfj28xvP3FjRaQfcBJzX9GhFqFgFDPpsa9L/XLFrbpzkFXi5aQCORr98ldvELFEcY1MUmu7nhujP6UGBZN8VuollseUjemQd1OqqeLWn85vnZGzVBmQMDJpaSRz9ffElCprJypIOxXFkV32MvE/r5tgeO1PhY4T5JotFoWJJBiR7HEyEIYzlJOUUGZEeithI2oowzSeLARv+eVV0qpVvYtq7f6yUr/J4yjCCZzCOXhwBXW4gwY0gcEInuEV3hzlvDjvzseiteDkM8fwB87nD5QWje4=</latexit>

Input Local%

Randomizer

Response Degree

Estimates

d=hˆ

d1,..., ˆ

dni

<latexit sha1_base64="0GA89mo5mDnjW0Cyd3i7xYIxfDw=">AAACJ3icbVDLSsNAFJ3UV62vqEs3g0VwUUpSBd0oRTcuK9gHNKVMJpN26GQSZm6EEvo3bvwVN4KK6NI/MWmDaOuBgcM553LnHjcSXINlfRqFpeWV1bXiemljc2t7x9zda+kwVpQ1aShC1XGJZoJL1gQOgnUixUjgCtZ2R9eZ375nSvNQ3sE4Yr2ADCT3OSWQSn3zEjsBgaHrJ86QQOJNJheOIHIgGM6Fvl3BjvBC0JUfSTpqmin1zbJVtabAi8TOSRnlaPTNF8cLaRwwCVQQrbu2FUEvIQo4FWxScmLNIkJHZMC6KZUkYLqXTO+c4KNU8bAfqvRJwFP190RCAq3HgZsms6P0vJeJ/3ndGPzzXsJlFAOTdLbIjwWGEGelYY8rRkGMU0Ko4ulfMR0SRSik1WYl2PMnL5JWrWqfVGu3p+X6VV5HER2gQ3SMbHSG6ugGNVATUfSAntArejMejWfj3fiYRQtGPrOP/sD4+gaguKZi</latexit>

Figure 1: Graph analysis in the LDP setting

However, the distributed nature of the federated analyt-

ics setting makes it vulnerable to data poisoning attacks in

practice. An adversary can inject fake users into the system

and skew the data analyst’s statistical estimates by sending

carefully crafted malformed data from the fake users. The

adversary can also tamper with statistics that pertain to only

the honest users. Impact of data poisoning under LDP for

graph analysis is largely unexplored; prior work has focused

only on tabular data [13,17,37].

In this paper, we initiate a formal study on the impact

of such data poisoning attacks on LDP protocols for graph

statistics. We focus on the task of degree estimation, one of the

most fundamental tasks in graph analysis that is vulnerable

to practical poisoning attacks. Consider, for example, a data

analyst who is interested in hiring the most inﬂuential nodes

(users) of a graph to disseminate advertisements for their

product and uses a node’s degree as its measure of inﬂuence.

Here, an adversary might want to promote a speciﬁc malicious

node (user) to be selected as an inﬂuencer or prevent an honest

node from being selected as an inﬂuencer and poison the data

(see Section 3.1 for details).

We observe that data poisoning can signiﬁcantly skew the

results of standard LDP protocols. For instance, consider the

Laplace mechanism where every user directly submits their

(noisy) degree to the analyst (Fig. 1). However, a malicious

arXiv:2210.14376v1 [cs.CR] 25 Oct 2022

user can ﬂagrantly lie and respond with

n−1

, skewing their

response by as much as the number of users. We address this

challenge and design robust degree estimation protocols. Our

protocols are based on the key observation – graph data is

naturally redundant. Speciﬁcally, the presence (or absence)

of edge

ei j

is shared by both users

and

. This introduces

data redundancy which we leverage to provide robustness – as

long as at least one of

is honest, the analyst can check

for consistency between the two bits obtained from

and

. We illustrate this using the following degree-estimation

protocol. For the ease of exposition, we assume no privacy.

Consider a protocol where the users send in their (true) ad-

jacency lists. Here for every edge

ei j

, the analyst receives

two copies of the same bit from users

and

– in case

there is inconsistency

in the two reported bits, the analyst

can safely conclude that one party is malicious and act accord-

ingly. Thus, we see that the natural data redundancy in graphs

can be leveraged to perform robust data analysis. However,

LDP requires randomization which makes the user’s reports

probabilistic. Consequently, the aforementioned simple con-

sistency check cannot be applied to LDP protocols. To this

end, we design novel degree estimation protocols that enable

a data analyst to employ consistency checks and detect mali-

cious users even under LDP. Our proposed protocols provide

formal robustness guarantees against data poisoning attacks

that signiﬁcantly reduce the impact of poisoning and compute

degree estimates with high accuracy.

In summary, we make the following contributions:

•

We propose a formal framework for analyzing the robust-

ness of a protocol. The framework quantiﬁes the impact

of poisoning attacks on both honest and malicious users.

•

Based on the proposed framework, we study the impact

of poisoning attacks on private degree estimation in the

LDP setting. We observe that LDP makes a degree estima-

tion protocol more vulnerable to poisoning – the impact

of poisoning is worse when the adversary can directly

poison their (noisy) responses (Fig. 3), rather than their

input data (Fig. 2). The former utilizes the characteristics

of LDP while the latter is independent of LDP.

•

Leveraging the redundancy in graph data, we design ro-

bust degree estimation protocols under LDP that signif-

icantly reduce the impact of adversarial poisoning and

compute degree estimates with high accuracy.

•

We evaluate our proposed robust degree estimation pro-

tocols under poisoning attacks on real-world datasets to

demonstrate their efﬁcacy in practice.

2 Background

We start by outlining the notation we use in the paper followed

by the necessary preliminaries on LDP for graph analysis.

For the ease of exposition, we disregard errors due to machine failures.

Notation.

In the following and throughout this paper, let

G= (V,E)

be an undirected graph with

and

representing

the set of nodes (vertices) and edges, respectively. We assume

a graph with

n∈N

nodes, i.e.,

V= [n]

where

[n]

denotes the

set {1,2,··· ,n}. Let Gdenote the domain of all graphs with

nodes. Each node

i∈V

corresponds to a user

. Let

li∈

{0,1}nbe the adjacency list for Ui,i∈[n]where bit li[j],j∈

[n]

encodes the edge

ei j

between a pair of users

and

Speciﬁcally,

li[j] = 1

ei j ∈E

and

ei j =0

otherwise. Note

that

is the

-th row of the adjacency matrix

of the graph

. Let

d=hd1,...,dni ∈ Rn

denote the vector of degrees in

G.mdenotes the number of malicious users.

2.1 Local Differential Privacy for Graphs

Differential privacy (DP) is a quantiﬁable measure of the sta-

bility of the output of a randomized mechanism to changes

to its input. One of the most popular models of DP is known

as local model the which is the focus of our paper. The local

model consists of a set of individual users (U) and an un-

trusted data aggregator (analyst); each user perturbs their data

using a (local) DP algorithm and sends it to the aggregator

which uses these noisy data to estimate certain statistics of

the entire dataset. Thus, the LDP model allows gleaning of

useful information from the dataset without requiring the data

owners to trust any third-party entity.

2.1.1 Privacy Deﬁnitions

Relationship DP.

As noted above, the knowledge of an

edge in a graph is shared between two users. Motivated by

this observation, recent work [30,31] has introduced a new

notion of DP called relationship DP that considers both the

users’ outputs and hides an edge in a graph during the entire

computation. Formally, we have:

Deﬁnition 1

(

-relationship DP)

For

i∈[n]

, let

Ri:{0,1}n7→

be the local randomizer of user

that takes their adja-

cency list

as input. We say

hR1(·),··· ,Rn(·)i

provides

relationship DP if for any two neighboring graphs

G,G0∈G

that differ in one edge and for any S ⊆Xn,

Pr[(R1(l1),··· ,Rn(ln)) = S]≤eεPr[(R1(l0

1),··· ,Rn(l0

n)) = S],

where

(respectively,

) is the

-th row of the adjacency

matrix of graph G (respectively, G0).

Relationship DP is closely connected to the notion of edge

LDP which is one of the most popular privacy guarantee for

graphs [41,43] in the LDP setting. Formally:

Deﬁnition 2

(

-edge LDP)

Let

R:{0,1}n7→ X

be a ran-

domized algorithm that takes an adajcency list

li∈ {0,1}n

as input. We say

R(·)

provides

-edge LDP if for any two

neighboring lists

l,l0∈ {0,1}n

that differ in one bit (i.e., one

edge) and any output s ∈X,

PrR(l) = s≤eεPrR(l0) = s

Thus,

-edge LDP protects the information about an edge

ei j

from the adjacency list

of a single user

. On the other

hand, relationship DP consider the outputs from both users

and

and hides the edge as a whole. The following

theorem formalizes the connection between edge LDP and

relationship DP.

Theorem 1

(Edge LDP and relationship DP [30])

If each of

the local randomizers

Ri(·),i∈[n]

satisfy

-edge LDP, then

(R1(),··· ,Rn()) satisﬁes 2ε-relationshiop DP.

The factor of two in Thm. 1 comes from the fact that

adding/removing an edge affects at most two neighboring

lists. For the rest of the paper, we consider

-relationship

DP degree estimation algorithms.

2.1.2 Privacy Mechanisms

Randomized Response.

We now illustrate a simple LDP

mechanism that we will use throughout this paper. Random-

ized Response (

RRρ(·)

) [48] releases a bit

b∈ {0,1}

by ﬂip-

ping it with probability

ρ=1

1+eε

. We extend the mechanism

to inputs in

{0,1}n

by ﬂipping each bit independently with

probability

(depicted by Algorithm 1). It is easy to ver-

ify that Algorithm 1 satisﬁes

-edge LDP, and thereby,

2ε

relationship DP (by Thm. 1).

Algorithm 1 RRρ:{0,1}n7→ {0,1}n

Parameters: ε- Privacy parameter;

Input: l∈ {0,1}n- True adjacency list;

Output: q∈ {0,1}n- Reported (noisy) adjacency list;

1: ρ=1

1+eε

2: for i∈[n]\tdo

3: q[i] = RRρ(l[i])

return q

Laplace Mechanism.

The Laplace mechanism is a stan-

dard algorithm to achieve DP [23]. In this mechanism, in order

to output

f(l),l∈ {0,1}n

where

f:{0,1}n7→ R

, an

-edge

LDP algorithm

RLap(·)

publishes

f(l) + η,η∼Lap∆f

ε

where

∆f=maxl,l0||f(l)−f(l0)||1

is known as the sensitiv-

ity of the function. The probability density function of

Lap(b)

is given by

f(x) = 1

2be−|x|

b

. The sensitivity of

f(·)

is the max-

imum magnitude by which an individual’s data can change

f(·)

. Intuitively, it captures the uncertainty to be introduced in

the response in order to hide the participation of one individ-

ual. The sensitivity for degree estimation for a single user for

edge LDP is 1. Hence, a mechanism (depicted by Algorithm

2) that outputs a noisy estimate

di=di+η,η∼Lap(1

ε)

from

each user Uisatisﬁes 2ε-relationship DP (by Thm. 1).

Algorithm 2 RLap :{0,1}n7→ R

Parameters: ε- Privacy parameter;

Input: l∈ {0,1}n- True adjacency list;

Output: ˜

d∈R- Reported (noisy) degree estimate;

1: d=∑n

i=1l[i]

2: ˜

d=d+η,η∼Lap(1

ε)

3: return ˜

3 Framework for Robust Degree Estimation

In this section, we present our formal framework for analyzing

the robustness of a protocol for degree estimation. First, we

describe the protocol setup we consider in the paper. Next, we

discuss how to formally quantify the robustness of a protocol.

3.1 Protocol Setup

Problem Statement.

We consider single round, non-

interactive protocols in which users evaluate pre-speciﬁed

randomizers on their adjacency lists

, and send the responses

to a data aggregator who computes the ﬁnal degree estimates.

To this end, a protocol Pconsists of the tuple

P= (D,{R1,...,Rn}).

Each user

Ui,i∈[n]

runs the local randomizer

Ri:

{0,1}n→X

for some output space

. Finally, the data ag-

gregator applies a function

D:Xn→(N∪{⊥})d

to produce

ﬁnal degree estimates. Note that the aggregator is allowed to

output a special symbol

⊥

for a user

if they believe the

estimate

to be invalid (i.e.,

is malicious). We elaborate

on this in the following section. The protocol

is executed by

the users and the analyst to produce degree estimates, given

by ˆ

d=hˆ

d1,..., ˆ

dni) = D(R1(l1),...Rn(ln)).

Here, ˆ

diis the aggregator’s estimate for difor user Ui.

Threat Model.

In the execution of a protocol

, a

subset of users

M∈[n]

may be malicious and carry out

a poisoning attack on

. We characterize an attack by the

following tuple:

A=M,{Ai(·):i∈M}.

The functions

Ai:{0,1}n→X

are allowed to be arbitrary

functions instead of the randomizers speciﬁed by

. The

protocol

executes the same way, except that a malicious user

Ui,i∈M

responds with

Ai(li)

instead of the true randomized

response

Ri(li)

. Thus, the aggregator outputs a manipulated

degree estimate given by

DegP,A(G) = D˜

R1(l1),..., ˜

Rn(ln),(1)

where

Ri(·) = Ai(·)

i∈M

and

Ri(·) = Ri(·)

otherwise.

|M|

denotes the number of malicious users. We refer to

[n]\Mas the set of honest users.

Algorithm 3 A0:{0,1}n7→ {0,1}n

Parameters: t∈M- Malicious target user whose

degree needs to be inﬂated;

ε- Privacy parameter;

Input: l∈ {0,1}n- True adjacency list;

Output: q∈ {0,1}n- Reported adjacency list;

1: q[t] = 1BSet the bit corresponding to Utto be 1

2: ρ=1

1+eε

3: for i∈[n]\tdo

4: q[i] = RRρ(l[i])

return q

Examples.

We illustrate the power of the above formaliza-

tion with the following two example attacks. We consider

the attacks in the context of the task of inﬂuential node

identiﬁcation – the goal of the data aggregator is to identify

certain nodes with a high measure of “inﬂuence". This is

useful for various applications where the inﬂuential nodes

are selected for disseminating information/advertisement.

Here, we consider the simplest measure of inﬂuence – degree;

nodes with the top-kdegrees are selected as the inﬂuencers.

Example 1. Consider an attack given by

Ai f =M,{At(·):=A∗(·);Ai(·):=A0(·),i∈M\t}

where

A∗(·)

and

A0(·)

is given by Algorithms 5 and 3,

respectively. The above attack considers a malicious user

Ut,t∈M

known as the target who wants to stage a poisoning

attack and get themselves selected as an inﬂuential node. For

this,

colludes with a set of other users (for instance, by

injecting fake users) and the attack strategy is to maximize the

degree estimate

. To this end, all the non-target malicious

users

Ui,i∈M\t

report

for the edges corresponding to

Additionally,

sends in an all-one list. We name this the

degree inﬂation attack.

Example 2. Consider an attack

Ad f =M,{Ai(·):=A00(·),i∈M}

where

A00(·)

is given by Algorithm 4. In this attack, the target

is an honest user

Ut,t∈H

who is being victimized by a set

of malicious users –

wants to ensure that

is not selected

as an inﬂuential node. The attack strategy is to decrease the

aggregators degree estimate

for

. For this, the malicious

users report

for the edges corresponding to

. We refer to

this as the degree deﬂation attack.

3.2 Quantifying Robustness

The robustness of a protocol can be measured along two

dimensions, correctness (for honest users) and soundness (for

malicious users) as now described.

Algorithm 4 A00 :{0,1}n7→ {0,1}n

Parameters: t∈H- Honest target user whose

degree needs to be deﬂated;

ε- Privacy parameter;

Input: l∈ {0,1}n- True adjacency list;

Output: q∈ {0,1}n- Reported adjacency list;

1: q[t] = 0BSet the bit corresponding to Utto be 0

2: ρ=1

1+eε

3: for i∈[n]\tdo

4: q[i] = RRρ(l[i])

return q

Algorithm 5 A∗:{0,1}n7→ {0,1}n

Input: l∈ {0,1}n- True adjacency list;

Output: q∈ {0,1}n- Reported adjacency list;

1: q= [1,1,··· ,1]

2: return q

Correctness (For Honest Users).

Malicious users can

adversely affect an honest user Ui,i∈Hby

•

tampering with the value of

’s degree estimate

(by

introducing additional error), or

•

attempting to mislabel

as malicious (by inﬂuencing the

aggregator to report ˆ

di=⊥)

Note that a malicious user

can tamper with

since it can

manipulate the shared edge

ei j

. The correctness of a protocol

assesses its resilience to manipulation of an honest user’s

estimator and is formally deﬁned as:

Deﬁnition 3

(

Correctness

)

Let

be a local protocol for

degree estimation, let

be an attack on

with honest users

, and let

(ˆ

d1,..., ˆ

dn) = DegP,A(G)

be the poisoned degree

estimates for an arbitrary graph

. Then,

is deﬁned to be

(α1,δ1)-correct with respect to Aif, for all graphs G ∈G,

∀Ui∈H,PrAˆ

di=⊥ ∨| ˆ

di−di| ≥ α1≤δ1.(2)

The parameter

α1

dictates the accuracy of the estimate

, and the parameter

δi

dictates the chance of failure—that

either of the aforementioned conditions fail to hold. Thus, if a

protocol

(α1,δ1)

-correct, it means that with probability

at least (1−δ1),

•

the degree estimate

for any honest user

Ui,i∈H

has

error at most α1, and

•Uiis guaranteed to be not mislabeled as malicious.

Complementary to the above deﬁnition, we introduce the

notion of

α1

-tight correctness. A protocol

is deﬁned to

α1

-tight correct w.r.t an attack

if, there exists a graph

G∈G, such that

∃Ui∈H,PrAˆ

di=⊥ ∨| ˆ

di−di|=α1=1 (3)

Thus, an attack is

α1

-tight correct is there exists a graph such

that Ais guaranteed to either

•get at least one honest user mislabeled as malicious, or

•

skew the the degree estimate of at least one honest user

by exactly α1.

Lower the value of

α1

and

δ1

, better is the robustness of the

protocol for honest users.

Soundness (For Malicious Users).

For malicious users, the

poisoning can result in

•

a misestimation of their degrees without being detected

by the aggregator (i.e., ˆ

di6=⊥)

The soundness of an algorithm assesses its ability to restrict

adversarial manipulations of a malicious user’s estimator and

is formally deﬁned as follows:

Deﬁnition 4

(

Soundness

)

Let

be a local protocol for de-

gree estimation, let

be an attack on

with malicious users

, and let

(ˆ

d1,..., ˆ

dn) = DegP,A(G)

be the poisoned degree

estimates for an arbitrary graph

. Then,

is deﬁned to be

(α2,δ2)-sound with respect to Aif, for all graphs G,

∀i∈M,PrAˆ

di6=⊥ ∧| ˆ

di−di| ≥ α2≤δ2.(4)

Like with correctness, the parameter

α2

dictates the accu-

racy of the estimate

, and

δ2

dictates the chance of failure.

As an important distinction, note that the failure event is when

is both

6=⊥

and is inaccurate, as stated above. Thus, the

∨

used in the deﬁnition of correctness is replaced by a

∧

. In

other words, a protocol

(α1,δ2)

-sound if for any mali-

cious user Ui,i∈M,P

•fails to identify Uias malicious, and

•reports its degree estimate ˆ

diwith error greater than α2

with probability at most δ2.

As a complementary deﬁnition, we deﬁne a protocol

α2

-tight sound w.r.t to an attack

if there exists a graph

G∈Gsuch that,

∃i∈M,PrAˆ

di6=⊥ ∧| ˆ

di−di|=α2=1 (5)

In other words, an attack

α2

-tight sound if at least one

malicious user is guaranteed to have their degree estimate

misestimated by exactly

α1

without getting detected. This is

especially important in our context since every attack is triv-

ially

(n−1,0)2

-correct/sound. Thus, a

(n−1)

-tight sound/cor-

rect attack represents the strongest possible attack – an user’s

estimate can always be skewed by the worst-case amount.

Lower the value of

α2

and higher the value of

δ2

, better is

the robustness of the protocol for malicious users.

2We do not consider self-edges or loops in the graph.

Algorithm 6 Ainput :{0,1}n7→ {0,1}n

Parameters: ε- Privacy parameter;

Input: l∈ {0,1}n- True adjacency list;

Output: q∈ {0,1}n- Reported adjacency list;

1: Choose a poisoned adjacency list l0∈ {0,1}n

2: ρ=1

1+eε

3: for i∈[n]do

4: q[i] = RRρ(l0[i])

return q

R(l1)

R(ln)

User%1

User%2

User%n

Data%Aggregator

𝑙2𝑅(𝑙2)

Poisoning

Figure 2: Input Poisoning Attack

4 Poisoning Attacks on Graphs

In this section, we introduce the two types of poisoning attacks

to LDP protocols, input and response poisoning.

4.1 Types of Poisoning Attacks

Note that for LDP there is a clear distinction between a user’s

input and their response. Speciﬁcally for

R(li) = qi

repre-

sents the original input for user

and

denotes the response

or message sent to the aggregator (after passing through ran-

domizer R(·)).

•Input Poisoning.

In this case, the malicious users falsify

their underlying input data, i.e., for a malicous user

Ui,i∈

, their original data is changed from

and then,

carries out the protocol honestly on

instead (Fig. 2). In

other words,

reponds with

R(l0

instead of

R(li)

. This

attack applies to any protocol, private or not. Algorithm 6

formalizes the attack.

•Response Poisoning.

This is a more powerful form of

attack where the user can completely bypass the random-

izer and submit an arbitrary response

(Fig. 3) to the

aggregator. The example attacks discussed in Section 3.1

are response manipulation attacks.

Although response poisoning attacks, by deﬁnition, subsumes

all input poisoning attacks, it is important to distinguish be-

tween them for the following two reasons. First, the distinc-

tion between an user’s input and their response is a character-

istic of LDP which results in a separation in the efﬁcacy of the

two types of attacks (see Section 5.2 for details). Second, the

distinction is important from a practical point of view as well.

Sometimes in practice, the malicious users might be restricted

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

RobustnessofLocallyDifferentiallyPrivateGraphAnalysisAgainstPoisoningJacobImolaUCSanDiegoAmritaRoyChowdhuryUCSanDiegoKamalikaChaudhuriUCSanDiegoAbstractLocallydifferentiallyprivate(LDP)graphanalysisallowsprivateanalysisonagraphthatisdistributedaccrossmultipleusers.However,suchcomputationsarevulner...

展开>> 收起<<

Robustness of Locally Differentially Private Graph Analysis Against Poisoning Jacob Imola UC San DiegoAmrita Roy Chowdhury.pdf

共22页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Robustness of Locally Differentially Private Graph Analysis Against Poisoning Jacob Imola UC San DiegoAmrita Roy Chowdhury

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: