SybilRank

Overview

The SybilRank algorithm ranks the trust of nodes by early-terminated random walks in the network, typically Online Social Network (OSN). The surge in popularity of OSNs has accompanied by the a rise in Sybil attacks, in which a malicious attacker creates multiple fake accounts (Sybils) to send spam, distribute malware, manipulate votes, inflate view counts for niche content, and so on.

SybilRank was proposed by Qiang Cao et al. in 2012, it is computationally efficient and can scale to large graphs.

• Q. Cao, M. Sirivianos, X. Yang, T. Pregueiro, Aiding the Detection of Fake Accounts in Large Scale Social Online Services (2012)

Concepts

Threat Model and Trust Seeds

SybilRank models an OSN as an undirected graph, where each node represents a user in the network, and each edge represents a mutual social relationship.

In the threat model of SybilRank, all nodes are divided into two disjoint sets: non-Sybils H, and Sybils S. Denote the non-Sybil region G_H as the subgraph induced by the set H, which includes all non-Sybils and edges among them. Similarly, the Sybil region G_S is the subgraph induced by S. G_H and G_S are connected by attack edges between Sybils and non-Sybils.

Some nodes identified as non-Sybils are designated as trust seeds for the operation of SybilRank. Seeding trust on multiple nodes makes SybilRank robust to seed selection errors, as incorrectly designating a node that is Sybil or close to Sybils as a seed causes only a small fraction of the total trust to be initialized and propagated in the Sybil region.

Below is an example of the threat model with trust seeds:

NOTE

An important assumption of SybilRank is that the number of attack edges is limited. Since SybilRank is designed for large scale attacks, where fake accounts are crafted and maintained at a low cost, and are thus unable to befriend many real users. It results in a sparse cut between G_H and G_S.

Early-Terminated Random Walk

In an undirected graph, if a random walk's transition probability to a neighbor node is uniformly distributed, when the number of steps is sufficient, the probability of landing at each node would converge to be proportional to its degree. The number of steps that a random walk needs to reach the stationary distribution is called the graph's mixing time.

SybilRank relies on the observation that an early-terminated random walk starting from a non-Sybil node (trust seed) has higher landing probability to land at a non-Sybil node than a Sybil node, as the walk is unlikely to traverse one of the relatively few attack edges. That is to say, there is a significant difference between the mixing time of the non-Sybil region G_H and the entire graph.

SybilRank refers to the landing probability of each node as the node’s trust. SybilRank ranks nodes according to their trust scores; nodes with low trust scores are ranked higher, indicating they are potential Sybil (fake) users.

Trust Propagation via Power Iteration

SybilRank uses the technique of power iteration to efficiently calculate the landing probability of random walks in large graphs. Power iteration involves successive matrix multiplications where each element of the matrix represents the random walk transition probability from one node to a neighbor node. Each iteration computes the landing probability distribution over all nodes as the random walk proceeds by one step.

In an undirected graph G = (V, E), initially a total trust T_G is evenly distributed among all trust seeds. During each power iteration, a node first evenly distributes its trust to its neighbors; it then collects trust distributed by its neighbors and updates its own trust accordingly. The trust of node v in the i-th iteration is:

where node u belongs to the neighbor set of node v, deg(u) is the degree of node u. The total amount of trust T_G remains unchanged all the time.

With sufficient power iterations, the trust of all nodes would converge to the stationary distribution:

However, SybilRank terminates the power iteration after a fixed number of steps, without waiting for full convergence, and it is suggested to be set as log2(|V|). This number of iterations is sufficient to reach an approximately stationary distribution of trust over the fast-mixing non-Sybil region G_H, but limits the trust escaping to the Sybil region G_S, thus non-Sybils will be ranked higher than Sybils.

NOTE

In practice, the mixing time of G_H is affected by many factors, so log2(|V|) is only a reference, but it must be less than the mixing time of the whole graph.

Considerations

• Each self-loop adds two degrees to its subject node.
• The SybilRank algorithm ignores the direction of edges but calculates them as undirected edges.
• SybilRank’s computational cost is O(n log n). This is because each power iteration costs O(n), and it iterates O(log n) times. It is not related with the number of trust seeds.

Example Graph

Run the following statements on an empty graph to define its structure and insert data:

GQLUQL
ALTER GRAPH CURRENT_GRAPH ADD NODE {
  user ()
};
ALTER GRAPH CURRENT_GRAPH ADD EDGE {
  link ()-[]->()
};
INSERT (H1:user {_id: "H1"}),
       (H2:user {_id: "H2"}),
       (H3:user {_id: "H3"}),
       (H4:user {_id: "H4"}),
       (H5:user {_id: "H5"}),
       (H6:user {_id: "H6"}),
       (H7:user {_id: "H7"}),
       (H8:user {_id: "H8"}),
       (H9:user {_id: "H9"}),
       (H10:user {_id: "H10"}),
       (S1:user {_id: "S1"}),
       (S2:user {_id: "S2"}),
       (S3:user {_id: "S3"}),
       (S4:user {_id: "S4"}),
       (S2)-[:link]->(H4),
       (S3)-[:link]->(H6),
       (S4)-[:link]->(S2),
       (S4)-[:link]->(S3),
       (S4)-[:link]->(H9),
       (H1)-[:link]->(H9),
       (H2)-[:link]->(H7),
       (H2)-[:link]->(H10),
       (H3)-[:link]->(H1),
       (H3)-[:link]->(H5),
       (H4)-[:link]->(H3),
       (H4)-[:link]->(H6),
       (H5)-[:link]->(H1),
       (H6)-[:link]->(H1),
       (H6)-[:link]->(H3),
       (H6)-[:link]->(H5),
       (H7)-[:link]->(H10),
       (H8)-[:link]->(H7);

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as my_hdc_graph:

GQLUQL
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static"
}

Parameters

Algorithm name: sybil_rank

File Writeback

UQL
algo(sybil_rank).params({
  projection: "my_hdc_graph",
  return_id_uuid: "id",
  total_trust: 100,
  // Assigns H2, H3, and H5 as trust seeds
  trust_seeds: [8214567919347040353, 16429133639670825060, 15060039352950194277],
  loop_num: 4
}).write({
  file: {
    filename: "sybil_rank"
  }
})

Result:

File: sybil_rank
_id,sybil_rank
S1,0
S4,3.61111
S2,4.45602
S3,4.71065
H9,5.0434
H8,5.09259
H4,6.66667
H10,7.87037
H5,8.67766
H1,9.59491
H2,9.9537
H7,10.4167
H3,11.305
H6,12.6013

DB Writeback

Writes the sybil_rank values from the results to the specified node property. The property type is float.

UQL
algo(sybil_rank).params({
  projection: "my_hdc_graph",
  return_id_uuid: "id",
  total_trust: 100,
  // Assigns H2, H3, and H5 as trust seeds
  trust_seeds: [8214567919347040353, 16429133639670825060, 15060039352950194277],
  loop_num: 4
}).write({
  db:{ 
    property: 'trust'
  }
})

Full Return

UQL
exec{
  algo(sybil_rank).params({
    return_id_uuid: "id",
    total_trust: 100,
    // Assigns H2, H3, and H5 as trust seeds
    trust_seeds: [8214567919347040353, 16429133639670825060, 15060039352950194277],
    loop_num: 4
  }) as trust
  return trust
} on my_hdc_graph

Result:

Stream Return

UQL
exec{
  algo(sybil_rank).params({
    return_id_uuid: "id",
    total_trust: 100,
    // Assigns H2, H3, and H5 as trust seeds
    trust_seeds: [8214567919347040353, 16429133639670825060, 15060039352950194277],
    loop_num: 4,
    limit: 4
  }).stream() as trust
  return trust
} on my_hdc_graph

Result: