On SNS (Social Networking Services), detecting Sybils is an urgent demand. The most famous approach is called “SybilRank” scheme where each node evenly distributes its trust value starting from honest seeds and detects Sybils based on the trust value. Furthermore, Zhang et al. propose to avoid trust values from being distributed into Sybils by pruning suspicious relationships before performing SybilRank. However, we point out that the above two schemes have shortcomings that must be remedied. In the former scheme, seeds are concentrated on the specific communities because they are selected from nodes that have largest number of friends, and thus the trust value is not evenly distributed. In the latter one, a sophisticated attacker can avoid graph pruning by making relationships between Sybil nodes. In this paper, we propose a robust seed selection and graph pruning scheme to detect Sybil nodes more accurately. To more evenly distribute trust value into honest nodes, we first detect communities in the SNS and select honest seeds from each detected community. And then, by leveraging the fact that Sybils cannot make dense relationships with honest nodes, we also propose a graph pruning scheme based on the density of relationships between trusted nodes. We prune the relationships which have sparse relationships with trusted nodes and this enables robust pruning malicious relationships even if the attackers make a large number of common friends. By the computer simulation with real dataset, we show that our scheme improves the detection accuracy of both Sybil and honest nodes.
Shuichiro HARUTA
Keio University
Kentaroh TOYODA
Keio University
Iwao SASASE
Keio University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Shuichiro HARUTA, Kentaroh TOYODA, Iwao SASASE, "Trust-Based Sybil Nodes Detection with Robust Seed Selection and Graph Pruning on SNS" in IEICE TRANSACTIONS on Communications,
vol. E99-B, no. 5, pp. 1002-1011, May 2016, doi: 10.1587/transcom.2015AMP0004.
Abstract: On SNS (Social Networking Services), detecting Sybils is an urgent demand. The most famous approach is called “SybilRank” scheme where each node evenly distributes its trust value starting from honest seeds and detects Sybils based on the trust value. Furthermore, Zhang et al. propose to avoid trust values from being distributed into Sybils by pruning suspicious relationships before performing SybilRank. However, we point out that the above two schemes have shortcomings that must be remedied. In the former scheme, seeds are concentrated on the specific communities because they are selected from nodes that have largest number of friends, and thus the trust value is not evenly distributed. In the latter one, a sophisticated attacker can avoid graph pruning by making relationships between Sybil nodes. In this paper, we propose a robust seed selection and graph pruning scheme to detect Sybil nodes more accurately. To more evenly distribute trust value into honest nodes, we first detect communities in the SNS and select honest seeds from each detected community. And then, by leveraging the fact that Sybils cannot make dense relationships with honest nodes, we also propose a graph pruning scheme based on the density of relationships between trusted nodes. We prune the relationships which have sparse relationships with trusted nodes and this enables robust pruning malicious relationships even if the attackers make a large number of common friends. By the computer simulation with real dataset, we show that our scheme improves the detection accuracy of both Sybil and honest nodes.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.2015AMP0004/_p
Copy
@ARTICLE{e99-b_5_1002,
author={Shuichiro HARUTA, Kentaroh TOYODA, Iwao SASASE, },
journal={IEICE TRANSACTIONS on Communications},
title={Trust-Based Sybil Nodes Detection with Robust Seed Selection and Graph Pruning on SNS},
year={2016},
volume={E99-B},
number={5},
pages={1002-1011},
abstract={On SNS (Social Networking Services), detecting Sybils is an urgent demand. The most famous approach is called “SybilRank” scheme where each node evenly distributes its trust value starting from honest seeds and detects Sybils based on the trust value. Furthermore, Zhang et al. propose to avoid trust values from being distributed into Sybils by pruning suspicious relationships before performing SybilRank. However, we point out that the above two schemes have shortcomings that must be remedied. In the former scheme, seeds are concentrated on the specific communities because they are selected from nodes that have largest number of friends, and thus the trust value is not evenly distributed. In the latter one, a sophisticated attacker can avoid graph pruning by making relationships between Sybil nodes. In this paper, we propose a robust seed selection and graph pruning scheme to detect Sybil nodes more accurately. To more evenly distribute trust value into honest nodes, we first detect communities in the SNS and select honest seeds from each detected community. And then, by leveraging the fact that Sybils cannot make dense relationships with honest nodes, we also propose a graph pruning scheme based on the density of relationships between trusted nodes. We prune the relationships which have sparse relationships with trusted nodes and this enables robust pruning malicious relationships even if the attackers make a large number of common friends. By the computer simulation with real dataset, we show that our scheme improves the detection accuracy of both Sybil and honest nodes.},
keywords={},
doi={10.1587/transcom.2015AMP0004},
ISSN={1745-1345},
month={May},}
Copy
TY - JOUR
TI - Trust-Based Sybil Nodes Detection with Robust Seed Selection and Graph Pruning on SNS
T2 - IEICE TRANSACTIONS on Communications
SP - 1002
EP - 1011
AU - Shuichiro HARUTA
AU - Kentaroh TOYODA
AU - Iwao SASASE
PY - 2016
DO - 10.1587/transcom.2015AMP0004
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E99-B
IS - 5
JA - IEICE TRANSACTIONS on Communications
Y1 - May 2016
AB - On SNS (Social Networking Services), detecting Sybils is an urgent demand. The most famous approach is called “SybilRank” scheme where each node evenly distributes its trust value starting from honest seeds and detects Sybils based on the trust value. Furthermore, Zhang et al. propose to avoid trust values from being distributed into Sybils by pruning suspicious relationships before performing SybilRank. However, we point out that the above two schemes have shortcomings that must be remedied. In the former scheme, seeds are concentrated on the specific communities because they are selected from nodes that have largest number of friends, and thus the trust value is not evenly distributed. In the latter one, a sophisticated attacker can avoid graph pruning by making relationships between Sybil nodes. In this paper, we propose a robust seed selection and graph pruning scheme to detect Sybil nodes more accurately. To more evenly distribute trust value into honest nodes, we first detect communities in the SNS and select honest seeds from each detected community. And then, by leveraging the fact that Sybils cannot make dense relationships with honest nodes, we also propose a graph pruning scheme based on the density of relationships between trusted nodes. We prune the relationships which have sparse relationships with trusted nodes and this enables robust pruning malicious relationships even if the attackers make a large number of common friends. By the computer simulation with real dataset, we show that our scheme improves the detection accuracy of both Sybil and honest nodes.
ER -