Trust-based collection of information in distributed reputation networks

ABSTRACT

Distributed reputation systems establish trust among strangers in online communities and provide incentives for users to contribute. In these systems, each user monitors the interactions of others and computes the reputations accordingly. Collecting information for computing the reputations is challenging for the users due to their vulnerability to attacks, their limited resources, and the burst of their interactions. The low cost of creating accounts in most reputation systems makes them popular to million of users, but also enables malicious users to boost their reputations by performing Sybil attacks. Furthermore, the burst of user interactions causes an information overload. To avoid the impact of malicious users and information overload, we propose EscapeLimit, a sybil attack-resistant, computationally simple, and fully distributed method for information collection. EscapeLimit leverages user interactions as indicators of trust and similarity between the corresponding users, and collects relevant and trusted information by limiting the escape probability into the Sybil area. We evaluate it by emulating interaction patterns derived from synthetic and real-world networks. Our evaluation shows EscapeLimit's effectiveness in terms of its resilience to Sybil attacks, its scalability, and its ability to provide relevant information to each user.

References

1. The distributed asci supercomputer 4. http://www.cs.vu.nl/das4/, 2014.
2. C. Ballester and M. Vorsatz. Random walk based segregation measures. Review of Economics and Statistics, 2011.
3. A. L. Barabási and R. Albert. Emergence of Scaling in Random Networks. Science, pages 509--512, 1999.
4. Z. Burda, J. Duda, J. M. Luck, and B. Waclaw. Localization of the Maximal Entropy Random Walk. Physical Review Letters, 102(16):160602--4, 2009.
5. Z. Burda, J. Duda, J. M. Luck, and B. Waclaw. The various facets of random walk entropy. Acta Phys. Polon. B, 2010.
6. G. C., M. M., and S. A. Random walks in peer-to-peer networks: algorithms and evaluation. Perform. Eval., 2006.
7. Q. Cao, M. Sirivianos, X. Yang, and T. Pregueiro. Aiding the detection of fake accounts in large scale social online services. In NSDI, 2012.
8. R. Chakravorty, S. Agarwal, and S. Banerjee. Mob: A mobile bazaar for wide-area wireless services. In ACM MobiCom, 2005.
9. G. Danezis and P. Mittal. SybilInfer: Detecting Sybil Nodes using Social Networks. In NDSS, 2009.
10. R. Delaviz, J. Pouwelse, and D. Epema. Targeted and scalable information dissemination in a distributed reputation mechanism. In Proceedings of the seventh ACM Workshop on Scalable Trusted Computing (ACM STC), 2012.
11. R. Delaviz, N. Zeilemaker, J. Pouwelse, and D. Epema. A network science perspective of a distributed reputation mechanism. IFIP Networking, 2013.
12. P. Felber, A.-M. Kermarrec, L. Leonini, É. Rivière, and S. Voulagris. PULP: an Adaptive Gossip-Based Dissemination Protocol for Multi-Source Message Streams. Peer-to-Peer Networking and Applications, Springer, 2011.
13. M. Feldman, K. Lai, I. Stoica, and J. Chuang. Robust incentive techniques for peer-to-peer networks. In ACM EC, 2004.
14. D. Gkorou, T. Vinkó, J. Pouwelse, and D. Epema. Leveraging node properties in random walks for robust reputations in decentralized networks. In IEEE P2P Computing, 2013.
15. W. K. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1):97--109, 1970.
16. S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina. The eigentrust algorithm for reputation management in p2p networks. In WWW, 2003.
17. A. Mohaisen, N. Hopper, and Y. Kim. Keep your friends close: Incorporating trust into social network-based sybil defenses. In INFOCOM, 2011.
18. P. Papadimitriou, A. Dasdan, and H. Garcia-Molina. Web graph similarity for anomaly detection. J. Internet Services and Applications, 2010.
19. M. Piatek, T. Isdal, A. Krishnamurthy, and T. Anderson. One hop reputations for peer to peer file sharing workloads. In NSDI'08, 2008.
20. J. A. Pouwelse, P. Garbacki, J. Wang, A. Bakker, J. Yang, A. Iosup, D. H. J. Epema, M. Reinders, M. R. van Steen, and H. J. Sips. Tribler: a social-based peer-to-peer system. Concurr. Comput.: Pract. Exper., 2008.
21. D. Quercia and S. Hailes. Sybil attacks against mobile users: friends and foes to the rescue. In INFOCOM, 2010.
22. R. Sinatra, J. Gómez-Gardeñes, R. Lambiotte, V. Nicosia, and V. Latora. Maximal-entropy random walks in complex networks with limited information. In Phys. Rev. E, 2011.
23. H. Tong, C. Faloutsos, and J.-Y. Pan. Fast random walk with restart and its applications. In ICDM, 2006.
24. N. Tran, B. Min, J. Li, and L. Subramanian. Sybil-resilient online content voting. In NSDI, 2009.
25. B. Viswanath, A. Mislove, M. Cha, and K. P. Gummadi. On the evolution of user interaction in facebook. In ACM WOSN, 2009.
26. C. Wilson, B. Boe, A. Sala, K. P. Puttaswamy, and B. Y. Zhao. User interactions in social networks and their implications. In Proceedings of the 4th ACM European Conference on Computer Systems, EuroSys, 2009.
27. Z. Yang, C. Wilson, X. Wang, T. Gao, B. Y. Zhao, and Y. Dai. Uncovering social network sybils in the wild. IMC, 2011.
28. H. Yu, P. B. Gibbons, M. Kaminsky, and F. Xiao. Sybillimit: A near-optimal social network defense against sybil attacks. In IEEE Symposium on Security and Privacy, 2008.
29. H. Yu, M. Kaminsky, P. B. Gibbons, and A. Flaxman. Sybilguard: defending against sybil attacks via social networks. In SIGCOMM, 2006.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Human-centered computing

  • Human computer interaction (HCI)

    • Interaction paradigms

      • Web-based interaction

• Security and privacy

• Social and professional topics

  • Computing / technology policy

    • Computer crime

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles