Transcript Buffer Aggregation

SybilGuard: Defending
Against Sybil Attacks
via Social Networks
Presented by: Sailesh Kumar
Overview

Introduction to sybil attack

Graph Theoretic Model and Problem Formulation

Overview of SybilGuard

Complete Design

Simulation Results and Analysis

Conclusion
‹#› - Sailesh Kumar - 7/16/2015
Introduction to the Problem

As the scale of a decentralized distributed system
increases
» Malicious behavior become a norm
» If 1/3 nodes are malicious => no guarantee
» Sybil attacks: a user takes multiple identities
– Can easily create n/3 sybil nodes

Using Central Authority
» Can Control Sybil attacks
» Worldwide trusted central authority is problematic
» Central authority may become the bottleneck
– DoS
» May scare away potential users

Defending against sybil attacks is difficult
» IP address harvesting
» Intelligent adversary
‹#› - Sailesh Kumar - 7/16/2015
Problem Formulation and Objective

Social network
» n honest human users
» 1+ malicious users : multiple sybil identities

Devise a defense system against sybil attacks
» SybilGuard enables an honest node to identify other nodes
» Verifier node V can verify if suspect node S is malicious

Guaranteed bound on number of sybil groups
» Divides n nodes into m equivalence classes
» A group is sybil if it contains 1+ sybil nodes

Guaranteed bound on size of sybil groups
» In a group, at most w sybil nodes

Completely decentralized
» An honest node accepts honest nodes with high probability
» Rejects malicious nodes with high probability
» Accepts bounded number of sybil nodes
‹#› - Sailesh Kumar - 7/16/2015
Social Network


Millions of users (nodes)
Friends are connected by an edge (friends)
» Usually degree of a nodes is small (~30)

A malicious user fools an honest user
» Creates an attack edge

SybilGuard limits number of attack edges
» Independent of number of sybil identities
– Friends share a secret edge key
– Edge keys are assigned out-of-band
‹#› - Sailesh Kumar - 7/16/2015
Trends


Social networks are fast mixing
Many sybil nodes disrupts this property
» Creates a low quotient cut in the graph

We assume that number of attack edges are few
» Out-of-band edge creation
» In real life a malicious user can not create many real friends
» Multiple identities are not useful

SybilGuard does not try to
detect low quotient cuts
but rather proposes an
effective decentralized
approach
‹#› - Sailesh Kumar - 7/16/2015
Random Routes



Foundation of SybilGuard: different from random walk
Random route begins at a random edge of a node
At every node
» For an incoming edge i, there is a unique outgoing edge j
» Thus, input to output is one-to-one mapped


A node A with d neighbors uniformly randomly
chooses a permutation “x1,x2, . . . ,xd” among all
permutations of 1,2, . . . ,d.
If a random route comes from the ith edge, A uses
edge xi as the next hop.
‹#› - Sailesh Kumar - 7/16/2015
Properties of Random Routes

Convergence
» Once two routes merge, they will remain merged




Routes are back-traceable
There can be only one route with length w that
traverses e along the given direction at its ith hop
If two random routes ever share an edge in the same
direction, then one of them must start in the middle
of the other
Cycles can exist, but with low probability
» Prob. (diameter k cycle) = 1/d(k-2)
‹#› - Sailesh Kumar - 7/16/2015
SybilGuard Algorithm

node V: verify node S
» V computes d random routes (length w)
» S computes d random routes (length w)
» If d/2 random routes intersects, accept S
» Else reject S


If few attack edges, then a sybil node’s random route
is less likely to reach honest region
And vice-versa
‹#› - Sailesh Kumar - 7/16/2015
SybilGuard Design



Decentralized design
Each node performs d random routes
A node registers with all nodes along its random
routes
» Registration is done using public-private key
‹#› - Sailesh Kumar - 7/16/2015
SybilGuard Design

Witness tables
» Reverse registration table
» Stores all downstream nodes along a random route
– Registration table stores upstream nodes
» This table also contains IP addresses of the nodes
– Will see why?
‹#› - Sailesh Kumar - 7/16/2015
Validation Process (V verifies S)



S sends all its witness tables to V
V intersects its own witness tables with those of S
If intersection point X
» V contacts X (using IP address in witness table)
» Authenticates with private key of X
» Checks if V is present in X’s registry table
» If yes, then this route accepts S

If d/2 routes accept S, then V accepts S
V
X
S
‹#› - Sailesh Kumar - 7/16/2015
Length of Random Routes

It has been shown that
» If w = Θ(√nlogn), then honest routes will intersect with high
probability
» Also the probability that a honest random route will reach sybil
region is low

Nodes locally determine w
» Node A does small random walk and lets say reaches node B
» A and B intersects their witness table
» The distance m of first intersection point determines w
» w = 2.1m
» 2.1 is derived from analysis of Birthday Paradox distributions
‹#› - Sailesh Kumar - 7/16/2015
SybilGuard Dynamics

Dealing with offline nodes
» Bypass them
» Use lookahead routing tables
– Store information about next k hops

Incremental routing table maintenance
» New nodes only slightly changes current routing permutation
» Like DHT
‹#› - Sailesh Kumar - 7/16/2015
Probability of Intersection

Probability of intersection of honest routes
» 1 million nodes
» Node degree = 24
‹#› - Sailesh Kumar - 7/16/2015
24 random routes,
Accept if 10 intersections
Probability of False Detection

Probability that honest routes remain in honest region
‹#› - Sailesh Kumar - 7/16/2015
Discussion

An honest node accepts other honest nodes with
99.8% prob?
» How about remaining 0.2% probability?

How to apply SybilGuard to completely virtual social
networks where there are few real friends?

Compromised computers
» Hundreds of thousands
» Millions of attacks edges
» SybilGuard will fail

Are Social networks indeed big or small?
‹#› - Sailesh Kumar - 7/16/2015