A collusion mitigation scheme for reputation systems



Data and Network Security Lab. (DNSL), Department of Computer Engineering, Sharif University of Technology, Azadi Ave., Tehran, I.R. Iran


Reputation management systems are in wide-spread use to regulate collaborations in cooperative systems. Collusion is one of the most destructive malicious behaviors in which colluders seek to affect a reputation management system in an unfair manner. Many reputation systems are vulnerable to collusion, and some model-specific mitigation methods are proposed to combat collusion. Detection of colluders is shown to be an NP-complete problem. In this paper, we propose the Colluders Similarity Measure (CSM) which is used by a heuristic clustering algorithm (the Colluders Detection Algorithm (CDA)) to detect colluders in O (n2m + n4) in which m and n are the total number of nodes and colluders, respectively. Furthermore, we propose an architecture to implement the algorithm in a distributed manner which can be used together with compatible reputation management systems. Implementation results and comparison with other mitigation methods show that our scheme prevents colluders from unfairly increasing their reputation and decreasing the reputation of the other nodes.


[1] Sepandar D. Kamvar, Mario T. Schlosser, and Hector Garcia-Molina. The Eigentrust algorithm for reputation management in P2P networks. In Proceedings of the 12th international conference on World Wide Web, pages 640-651, Budapest, Hungary, 2003. ACM Press Press.

[2] Li Xiong and Ling Liu. Peertrust: Supporting reputation-based trust for peer-to-peer electronic communities. IEEE Transactions on Knowledge and Data Engineering, 16(7):843-857, 2004.

[3] Anupam Das and Mohammad Mahfuzul Islam. Securedtrust: a dynamic trust computation model for secured communication in multia-gent systems. Dependable and Secure Computing, IEEE Transactions on, 9(2):261-274, 2012.

[4] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms, volume 2. MIT Press, Cambridge, MA, USA, 2001.

[5] Audun Jøsang, Roslan Ismail, and Colin Boyd. A survey of trust and reputation systems for online service provision. Decision support systems, 43(2):618-644, 2007.

[6] Xinlei Wang, Kannan Govindan, and Prasant Mohapatra. Collusion-resilient quality of information evaluation based on information provenance. In Proceedings of the 8th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), pages 395-403, Salt Lake City, UT, USA, 2011. IEEE.

[7] Audun Jøsang, Ross Hayward, and Simon Pope. Trust network analysis with subjective logic. In Proceedings of the 29th Australasian Computer Science Conference-Volume 48, pages 85-94. Australian Computer Society, Inc., 2006.

[8] Kevin Hoffman, David Zage, and Cristina Nita-Rotaru. A survey of attack and defense techniques for reputation systems. ACM Computing Surveys (CSUR), 42(1):1, 2009.

[9] Félix Gómez Mármol and Gregorio Martínez Pérez. Security threats scenarios in trust and reputation models for distributed systems. Computers & Security, 28(7):545-556, 2009.

[10] Xiaoning Jiang and Lingxiao Ye. Reputation-based trust model and anti-attack mechanism in p2p networks. In Proceedings of the Second International Conference on Networks Security Wireless Communications and Trusted Computing (NSWCTC), volume 1, pages 498-501, Wuhan, Hubei, China, 2010. IEEE.

[11] Mudhakar Srivatsa, Li Xiong, and Ling Liu. TrustGuard: countering vulnerabilities in reputation management for decentralized overlay networks. In Proceedings of the 14th International Conference on World Wide Web, pages 422-431, Chiba, Japan, 2005. ACM Press Press.

[12] Runfang Zhou and Kai Hwang. Powertrust: A robust and scalable reputation system for trusted peer-to-peer computing. IEEE Transactions on Parallel and Distributed Systems, 18(4):460-473, 2007.

[13] Ze Li, Haiying Shen, and K. Sapra. Collusion detection in reputation systems for peer-to-peer networks. In Parallel Processing (ICPP), 2012 41st International Conference on, pages 98-107, Sept 2012.

[14] Gayatri Swamynathan, KevinC. Almeroth, and BenY. Zhao. The design of a reliable reputation system. Electronic Commerce Research, 10(3-4):239-270, 2010.

[15] Ze Li, Haiying Shen, and K. Sapra. Leveraging social networks to combat collusion in reputation systems for peer-to-peer networks. In Parallel Distributed Processing Symposium (IPDPS), 2011 IEEE International, pages 532-543, May 2011.

[16] Reid Kerr and Robin Cohen. Detecting and identifying coalitions. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 3, AAMAS '12, pages 1363-1364, Richland, SC, 2012. International Foundation for Autonomous Agents and Multiagent Systems.

[17] Gianluca Ciccarelli and Renato Lo Cigno. Collusion in peer-to-peer systems. Computer Networks, 55(15):3517-3532, 2011.

[18] Bao Yu, Cao Tianjie, and Zeng Guosun. Resisting collusion by game in culture web. In Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE), 2011 20th IEEE International Workshops on, pages 262-267, June 2011.

[19] Roberto Aringhieri, Ernesto Damiani, Sabrina De Capitani di Vimercati, Stefano Paraboschi, and Pierangelo Samarati. Fuzzy techniques for trust and reputation management in anonymous peer-to-peer systems. Journal of the American Society for Information Science and Technology, 57(4):528-537, 2006.

[20] Ayman Tajeddine, Ayman Kayssi, Ali Chehab, and Hassan Artail. Fuzzy reputation-based trust model. Applied Soft Computing, 11(1):345-355, 2011.

[21] Victor E. Lee, Ning Ruan, Ruoming Jin, and Charu Aggarwal. A survey of algorithms for dense subgraph discovery. In Managing and Mining Graph Data, pages 303-336. Springer, USA, 2010.

[22] Yunpeng Zhao, Elizaveta Levina, and Ji Zhu. Community extraction for social networks. Proceedings of the National Academy of Sciences, 108(18):7321-7326, 2011.

[23] Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12):7821-7826, 2002.

[24] Gaoxia Wang, Yi Shen, and Ming Ouyang. A vector partitioning approach to detecting community structure in complex networks. Computers & Mathematics with Applications, 55(12):2746-2752, 2008.

[25] Xutao Wang, Guanrong Chen, and Hongtao Lu. A very fast algorithm for detecting community structures in complex networks. Physica A: Statistical Mechanics and its Applications, 384(2):667-674, 2007.

[26] Mark E. J. Newman. Detecting community structure in networks. The European Physical Journal B-Condensed Matter and Complex Systems, 38(2):321-330, 2004.

[27] Rui Xu and Donald C. Wunsch II. Survey of clustering algorithms. IEEE Transactions on Neural Networks, 16(3):645-678, 2005.

[28] Audun Jøsang, Roslan Ismail, and Colin Boyd. A survey of trust and reputation systems for online service provision. Decision Support Systems, 43(2):618-644, 2007.

[29] Wang Miao, Xu Zhijun, Zhang Yujun, and Zhang Hongmei. Modeling and analysis of peertrust-like trust mechanisms in p2p networks. In Global Communications Conference (GLOBE-COM), 2012 IEEE, pages 2689-2694. IEEE, 2012.