Improving sybil detection in online social networks - Zhang, Huanhuan (2014)
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.