This week, I will be attending the NSERC Internetworked Systems Security Network (ISSNet) Annual Workshop at Victoria, BC, Canada. I will present our latest work on Graph-based Sybil Detection in Social and Information Systems (see technical report here). In this work, we show that these algorithms should be designed to find local community structures around known honest (non-Sybil) nodes, while incrementally keeping track of changes in the graph in order to detect Sybils before they “strongly-connect” to honest nodes. This, to some extent, introduces a paradigm shift from graph statistics to dynamics.
On March 7, I’ll be giving a talk at GRAND NCE Workshop under the general subject of Emerging Digital Media Technologies, Methodologies and Practices: Developer Solutions, Industry Needs and Approaches to Collaboration. The talk will be on emergent security and privacy issues in online social media, including our attempts towards improving the security of the social web.
The aim of the workshop is to provide a forum for the communication of research results and to highlight the development of innovative graphics, animations and new digital media emerging from Canada’s research universities. In addition, the workshop offers industry an opportunity to network with researchers and a platform for future collaboration on key graphic, animation and digital media problems and needs.
As technology transfer is a major issue for research community and industry alike, the workshop will identify the challenges and rewards of licencing technology from Canada’s universities and include discussions on IP protection and technology transfer/commercialization avenues.
First of all, happy new year everyone! This is going to be a lengthy update.
The last year was full of research fun. We built on top of our initial socialbots research success, and explored for the first time its economic side (see here) as well as its defence side (see here). After great research internships at Sophos and Facebook, I’m back on track working on building an effective and efficient defence scheme against the threat of malicious socialbots.
Before delving into the detail of how one could build such a defence system, it is important to characterize and evaluate existing plethora of Sybil node detection schemes that utilize the social graph, especially against the adversary model used by socialbots. A Sybil node is a forged identity in an identity-based system. For example, each socialbot in an OSN is a Sybil node, which is controlled along with all other socialbots by a “social” adversary.
Social graph-based Sybil detection algorithms such as SybilGuard, SybilLimit, SybilInfer, GateKeeper, and others try to detect Sybils in the social graph by analyzing the graph’s structure based on three assumptions: (1) the defender knows at least one non-Sybil node (called honest), (2) looking at the social graph as two regions, the Sybil region consisting of Sybil nodes and the honest region consisting of honest nodes, the two regions are loosely connected in the sense that the adversary cannot establish arbitrarily many social ties with honest nodes, and finally, (3) the honest region is fast-mixing, meaning that it is well-connected and random walks in the region quickly reach the stationary distribution.
Now, the adversary model of socialbots is unique in the sense that the second assumption does not hold. There will be far more non-genuine social ties between Sybils and honest nodes than the number of Sybils in the graph, which is becoming a widely observed phenomena not only in Facebook but in other real-world OSNs such as Twitter.
Our current research deals with this issue. How do these detection algorithms behave under such “social adversary model?” And in case they perform badly, is there an inherent observation about large-scale infiltration that can be useful to propose new a class of social graph-based Sybil detection algorithms which perform well in practice?
As a first step towards tackling these questions, we are working on an open-source evaluation framework for graph-based Sybil detection algorithms in social and information networks. We call this framework SyPy, and it’s designed to evaluate the effectiveness or the detection performance of these algorithms, not their efficiency. This means that it is not indented to benchmark algorithms on graphs consisting of millions of nodes; detection accuracy only demands a valid input at a reasonable scale (say, thousands of nodes). Designing scalable algorithms, on the other hand, is an interesting but orthogonal field of research.
SyPy is still a work-in-progress. Stay tuned!