Towards trustworthy computing on social networks: measurements and new applications.

Abstract

In this work we study social networks by measurements and verification of assumption widely and blindly used for building security and communication services on top of these networks. We measure the mixing time---a major property used for building trustworthy systems on social networks, the expansion, and the betweenness in social graphs. We show that some of these properties do not hold, whereas others hold with less quality than assumed in the literature. From there, we propose to proceed to study these properties in different settings. We propose to study one of these widely properties, the mixing time, under several conditions used widely as practices for modifying social graphs: graph sampling and omission of graph directions. We explore reasons behind the quality of the mixing time, and propose several heuristics to improve it. Motivated by the lack of work on accounting for differential trust in social network-based applications---Sybil defenses in particular, we develop four designs and use them to account for trust in a benchmark technique of Sybil defense (SybilLimit). We show empirically that our designs improve the security of this defense at some reasonable cost. We propose to extend these algorithms to other applications, Sybil defenses as well as other routing and information dissemination applications on top of social networks and rely on trust and social graphs' structure in their operation. Finally, we use social networks for building two types of applications that make use of new properties discovered in these networks. The first application is a distributed computing service (called socialcloud) that does not make any direct use of a global property of social graphs (such as the mixing time or the expansion). We show that nodes in socialcloud finish computing tasks relatively quickly even when as much as 30% of the nodes in the system are outsourcing computations. The second system we design is DynaMix, an anonymous communication service that incorporates dynamics in the social graph for anonymity. We show that dynamics of these networks can be used to improve anonymity of users.