Improving sybil detection in online social networks

• Main Author: Zhang, Huanhuan
• Other Authors: Chang Kuiyu
• Format: Theses and Dissertations
• Language: English
• Published: 2014
• Subjects: DRNTU::Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/61788
• Institution: Nanyang Technological University

Due to open and anonymous nature, online social networks are particularly vulnerable to Sybil attack, where a malicious user can fabricate many dummy identities to target systems. Recently, there are a flurry of interests to leverage social network structure for Sybil defense. The rationale behind these approaches is to partition the whole social graph into honest and Sybil regions based on two core assumptions: (1) strong trust relationship among nodes, which makes it difficult for Sybil nodes to establish substantial social connections with non-Sybil nodes, even if they can easily recruit a large number of Sybil nodes and build arbitrary topology network among them. As a result, Sybil region connects to the main network via a small number of attack edges. (2) honest region is fast mixing, where random walks from an benign node can quickly reach a stationary distribution after O(log(n)) steps, compared to random walks from Sybil nodes. However, these anti-Sybil mechanisms are less effective than expected since real-world social networks do not conform to the above assumptions. In the thesis, the main theme is to explore additional topological features underlying social networks in designing secure and robust Sybil defense systems. In particular, this thesis is comprised of two studies. Firstly, graph pruning and regularization techniques are proposed to enhance existing network-based Sybil defense mechanisms. In particular, a novel perspective is provided to interpret Sybil defense as the problem of partially labelled classification. Then, based on such framework, graph pruning is introduced to enhance the robustness of current anti-Sybil schemes against target attacks, by utilizing the local structural similarity between neighboring nodes in a social network. Besides, a domain-specific graph regularization method is designed to further improve the performance of those mechanisms by exploiting the relational property of social networks. Experimental results on four popular online social network datasets demonstrate that the proposed techniques can significantly improve the detection accuracy over the original Sybil defense mechanisms. Secondly, an unified ranking mechanism based on trust and distrust is proposed for successfully combating Sybil attack. In this study, a Sybil seed selection algorithm is designed to produce reliable Sybil seeds by combining with current Sybil detectors. Then, to leverage trust and distrust, a unified ranking mechanism is designed to output an integrated trustworthiness for each node in the social graph. Nodes with lower trustworthy value are more likely to be Sybils. Experiments show that the proposed framework outperforms existing competitive methods for Sybil detection. To summarize, as the initiative attempt of considering different network features to address complex problems (i.e. mixing sensitivity, target attack and distrust utilization), this thesis serves to inspire the research community to build robust and secure Sybil defense mechanisms by exploring social topological features and applying them in real cases. Besides, this work mitigates the research gap between semi-supervised learning and social security fields, and thus is hoped to draw more attention towards this direction.