SybilGuard: Defending Against Sybil Attacks by means of Social Networks

2013 days ago, 699 views
PowerPoint PPT Presentation

Presentation Transcript

Slide 1

SybilGuard: Defending Against Sybil Attacks through Social Networks Haifeng Yu Michael Kaminsky Phillip B. Gibbons Abraham Flaxman Presented by John Mak, Janet Yung

Slide 2

Outline Introduction to Sybil Attack Model & Problem definition Sybil Guard Overview Simulation Result & Analysis Conclusion Our perspectives

Slide 3

Introduction to Sybil Attack P2p and decentralized, appropriated frameworks especially defenseless Malicious client gets various fake personalities Gain vast impact by "out vote" legitimate clients

Slide 4

Introduction to Sybil Attack Malicious client acquires different fake characters Malicious conduct turns into a standard (e.g. Byzantine disappointments) Many conventions expect < 1/3 noxious hubs Easily make 1/3 hubs ��  Break guard

Slide 5

Introduction to Sybil Attack Centralized power: Control Sybil assault effectively Verify genuine certification Hard for worldwide to trust Single purpose of disappointment – bottleneck, DOS Scare away potential clients – requires delicate data

Slide 6

Introduction to Sybil Attack Decentralized approach is hard: Harvest (Steal) IP addresses No normal IP prefix ��  Hard to channel Advertise BGP course on unused piece of IP address Botnet - Co-pick expansive number of end-client machines

Slide 7

Introduction to Sybil Attack Not exceptionally fruitful safeguard approaches: Resource-challenge approach (computational riddles) Network arranges Reputation framework in light of chronicled conduct

Slide 8

Model & Problem Formulation Users: n legit clients: single personality 1+ malevolent client: numerous characters Identity: Also called "hub" Sybil personality: malignant client's character Defense framework Verifier hub V acknowledge another hub S Ideally, V just acknowledge fair hubs.

Slide 9

Model & Problem F ormulation Bounding no. of sybil gatherings Divide all hubs into at most g identicalness bunches Sybil Group: comparability amass contains no less than one Sybil hub Defense framework ensures no. of gatherings, without need to know whether the gathering is sybil

Slide 10

Model & Problem Formulation Bounding size of Sybil Group at most w hubs in a gathering point of confinement no. of sybil hubs acknowledged every hub can acknowledge Summary decentralized fair hub acknowledges, and is acknowledged by most other legit hubs legitimate hub acknowledges a limited number of sybil hubs.

Slide 11

Social Network Consists of clients (hubs) Human built up trust connections Nodes associated by an edge (companion) Real life relationship can bound both the number and size of sybil gatherings Usually degree ~ 30 Malicious client fools genuine client to trust him/her an assault edge associated a noxious client and a fair client

Slide 12

SybilGuard Overview Ensures legit client impart at most one edge to sybil hubs made by a malignant client A convention empowers legitimate hubs to acknowledge an expansive part of the other legit hubs SybilGuard does not increment or lessening the quantity of edges in the interpersonal organization as a consequence of its execution

Slide 13

SybilGuard Overview Random courses coordinate irregular stroll for all hubs Pre-figured arbitrary change balanced mapping from approaching edges to out-going edges Random courses joining property back-traceable property Multiple irregular courses of a specific length (w)

Slide 14

Random course Basis of SybilGuard Honest hub (verifier) chooses whether or not to acknowledge another hub (suspect ) Honest hub's irregular course exceedingly liable to remain inside the legit locale Highly liable to meet inside (w) steps If there are (g) assault edges, the quantity of sybil gatherings is limited by (g)

Slide 15

Fast blending property Assume informal communities have a tendency to be quick blending , which fundamentally implies that subsets of legit hubs have great availability to whatever is left of the informal community Assume the verifier is itself a legit hub

Slide 16

Attack edge

Slide 17

Key trade Each combine of well disposed hubs shares an extraordinary symmetric mystery key (secret word) called the edge Key appropriation is done out-of-band Each fair hub compels its degree inside some steady (e.g. 30) keeping in mind the end goal to keep the foe from expanding the quantity of assault edges (g) significantly

Slide 18

Limits assault edges Limited number of assault edges (g) Adding new assault edge needs out-of-band confirmation Malicious clients: Hard to persuade legit clients to be companions Quite hard to do on a vast scale

Slide 19

Common ways enemy may use to build g Befriending with legitimate clients, all things considered, Convince genuine hub to acknowledge sybil hubs as companions Compromises a substantial part of hubs in the framework. The foe does not have to dispatch a sybil assault. SybilGuard won't help here. Botnet Challenging to get a botnet containing numerous hubs that as of now in the framework.

Slide 20

Random course Convergence property Once two courses navigate a similar edge along a similar heading, they will union and remain blended (i.e. the meeting property) Back-traceable property Using a stage as the steering table further ensures that the arbitrary courses are back-traceable There can be one and only course with length (w) that crosses a similar area of course (e)

Slide 21

Problems of irregular course Loop (same edge more than once) Unlikely to shape in a quick blending chart Enters the sybil locale Unlikely as indicated by: THEOREM 1. For any associated and non-bipartite informal community, the likelihood that a length-w irregular walk beginning from a consistently arbitrary fair hub will ever cross any of the g assault edges is upper limited by gw/n. Specifically, when w = Θ( √n log n ) and g = o ( √n/log n ) , this likelihood is o (1) .

Slide 22

SybilGuard Design Use repetition Instead of performing one arbitrary highway A hub with degree (d) performs irregular courses along each of its edges Verifier V acknowledge suspect S If exist d/2 courses from the verifier hub One of V's course acknowledge S if that course cross with one of S's course

Slide 23

Registry table Each hub will keep up and proliferate one's registry tables and witness tables to its neighbors SybilGuard requires a hub to enlist with all (w) hubs along each of its courses by utilizing open key cryptography When a verifier V needs to confirm S, V will ask the convergence point between S's course and V's course whether S is in reality enrolled

Slide 24

Registry & Witness tables

Slide 25

Bandwidth utilization Studying a one million hubs informal organization w=2000 Data sent by every hub for registry table is little Bandwidth utilization satisfactory since the registry table upgrades are required just when social trust connections change

Slide 26

Witness table Propagated and overhauled in a comparative form as the registry table Backward Updated when a hub's IP address changes Can be done apathetically in the confirmation procedure

Slide 27

Verify handle For a hub V to confirm a hub S discover the crossing point hubs for the greater part of its courses by the witness tables downstream Authenticates the convergence hub one by one by the private key Ask that hub to check if S's open key is store in one of its registry tables. In the event that S's open key is found, that course of V will acknowledge S

Slide 28

Verify Process If more than half of the course from V acknowledge S, hub V will acknowledge hub S V will connect will S later according to popular demand S to encode its message by its private key For the sybil hubs area with (g) assault edges, Polluted sections in registry tables limited by g*w*w/2 still not as much as half of the aggregate number of passages n*d*w even with g*w tends to (n) with (d) being the level of every hub (d >= 2) and (n) being the aggregate number of hubs

Slide 29

Route length w Constraints: Must be adequately little to guarantee remains completely inside the legit district Must be adequately extensive to guarantee that courses will converge with high likelihood w identified with n Challenging on the grounds that we don't know n for a decentralized framework

Slide 30

Route length w Determine locally by testing Node A performs short arbitrary walk (e.g. 10 jumps) at hub B Assume B is straightforward (with high likelihood) A checks no. of jumps for crossing point with their irregular highways A requests the witness tables from B. Rehash above, figure middle esteem.

Slide 31

Sybil Guard under Dynamics Bypass disconnected hubs V check other hub S Probably various convergence focuses V have no less than one crossing point online Propagate registry & witness tables User creation/erasure/ip address change Infrequent changes Lookahead course table Store data of next K jumps

Slide 32

Sybil Guard under Dynamics Incremental steering table support Instead of re-make another stage Make changes in current stage Add X 1 ��  X 2 ��  X 3 ��  X 4 ��  (embed at end) X 1 ��  X 2 ��  (embed here) ��  X 4 ��  X 3 Delete "3" Before: X 1 ��  X 2 ��  X 3 ��  X 4 ��  X 5 After: X 1 ��  X 2 ��  X 5 ��  X 4

Slide 33

Attacks Exploiting Node Dynamics Potential assaults under Node Dynamics Malicious client M change open key to key2 Suppose D �� A�� B�� C Suppose repudiate key1 Random courses along all headings D's key3 will overwrite key2

Slide 34

Probability of Intersection Kleinberg's engineered interpersonal organization display a million-hub chart with normal hub level of 24

Slide 35

Results with no Sybil Attackers Probability of irregular courses being circles Loop r elicits successful length of arbitrary course Loop is exceptionally uncommon 99.3% of the courses don't frame circles in their initial 2500 bounces

Slide 36

Results with no Sybil Attackers Probably of legitimate hub being acknowledged no less than one crossing point on the web If no less than 10 on the web/disconnected crossing point focuses ��  confirmation prevails In 1 million-hub diagram w = 300 likelihood = 99.96% having >=10 convergences

Slide 37

Results with no Sybil Attackers Estimate arbitrary course length w Sampling system to decide w Node A pick a hub B