SumUp: Sybil-Resilient Online Content Voting

New! Digg data available for download

Overview Online voting system likes Diggs, YouTube, eBay, Amazon, ets are known to be susceptible to Sybil attack in which the attacker creates many accounts to cast bogus votes for an object. SumUp leverages social network underline the accounts to defend against such attack. By using a novel capacity assignment on the social links and collecting votes in an approximate max-flow fashion, SumUp can successfully limits the number of bogus votes casted by the attacker to the number of attack edges (e_A) with high probability. SumUp also leverage users' feedback to further reduce the number of bogus votes casted by the attacker if the attacker keeps doing that for different objects. Using SumUp on Digg voting trace, we found evidences of Sybil attacks in real world.

 

vote2.jpg

Figure 1

SumUp SumUp computes a set of approximate max-flow paths in the trust graph from the vote collector to all voters on a given object. Each vote flow consumes one unit of capacity along each link traversed. Figure 1 gives an example of the resulting flows from the collectors to voters A, B, C, D. Straight lines denote trust links and curly dotted lines represent the vote flow paths along multiple links.  Vote flow paths to honest voters are ``congested'' at links close to the collector while paths to Sybil voters are also congested at far-away attack edges.

 

In order to collect as many as honest votes and as few as potentially bogus votes, we propose the adaptive vote flow technique addresses this tradeoff by exploiting two basic observations.

·      The number of honest users voting for an object, even a popular one, is significantly smaller than the total number of users. For example, 99% of popular articles on Digg have fewer than 4000 votes which represents 1% of active users.

·      Vote flow paths to honest voters tend to be only ``congested'' at links close to the vote collector while paths to Sybil voters are also congested at a few attack edges. Figure 1 illustrates the congestion of votes from Sybils.

The adaptive vote flow computation uses three key ideas. First, the algorithm restricts the maximum number of votes collected on an object to a value C_max . As C_max is used to assign the overall capacity in the trust graph, a small C_max results in less capacity for the attacker. SumUp can adaptively adjust C_max to collect a large fraction of honest votes on any given object. When the number of honest voters is na where a < 1, the expected number of bogus votes is limited to 1 + o(1) attack edge.

 

The second important aspect of SumUp relates to capacity assignment, i.e. how to assign capacities to each trust link in order to collect a large fraction of honest votes and only a few bogus ones?  In SumUp, the vote collector distributes C_max tickets downstream in a breadth-first search manner within the trust network. The capacity assigned to a link is the number of tickets distributed along the link plus one. As Figure 2 illustrates, the ticket distribution process introduces a vote envelope around the vote collector s; beyond the envelope all links have capacity 1.  The vote envelope contains C_max nodes that can be viewed as entry points. There is enough capacity within the envelope to collect C_max votes from entry points. On the other hand, an attack edge beyond the envelope can propagate at most 1 vote regardless of the number of Sybil identities behind that edge. SumUp re-distributes tickets based on feedback to deal with attack edges within the envelope.

envelope.jpg

Figure 2

The final key idea in SumUp is to leverage user feedback to penalize attack edges that continuously propagate bogus votes. One cannot penalize individual identities since the attacker may always propagate bogus votes using new Sybil identities. Since an attack edge is always present in the path from the vote collector to a malicious voter, SumUp re-adjusts capacity assignment across links to reduce the capacity of penalized attack edges.

 

People:

Nguyen Tran

 

Bonan Min

 

Jinyang Li

 

Lakshminarayanan Subramanian

Papers:

Sybil-Resilient Online Content Voting [PDF]
Nguyen Tran, Bonan Min, Jinyang Li, Lakshminarayanan Subramanian
Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI), Boston, April 2009.

Data:

Digg User Names: digg_users.gz(12MB), digg_users_format.txt.

Digg User Links: digg_edges.gz(63MB), digg_edges_format.txt.

 

Diggs Trace (12/1/2004 - 9/21/2008): 1100-1110.tar.gz(1.7MB), 1110-1120.tar.gz(5.7MB), 1120-1130.tar.gz(38MB), 1130-1140.tar.gz(68MB), 1140-1160.tar.gz(255MB), 1160-1180.tar.gz(406MB), 1180-1200.tar.gz(468MB), 1200-1220.tar.gz(588MB), 1220-1222.tar.gz(78MB), diggs_trace_format.txt.

 

Buries Trace (8/13/2008 - 9/26/2008): raw_buries.gz(30MB), raw_buries_format.txt.