近年來社群網路 (Social Network) 的普及化與便利性，造就社群網站使用人數逐年呈現爆炸性的成長，使得如Facebook、Google+與Line等平台成為人們日常生活中非常重要的一部分。而其中在某些社群平台上 (如eBay、Google與Yahoo拍賣等網站) 會擁有評分或是投票的機制，以藉此建立使用者雙方之間的信譽評比，我們稱之為信賴系統 (Reputation System)。而為了影響信賴系統的正常運作，惡意使用者(Malicious User) 會利用大量多重虛擬身分企圖控制信賴系統的評比結果，此攻擊類型稱之為女巫攻擊 (Sybil Attack)，此類型攻擊會影響正常使用者的信譽評比，並藉此獲得不當利益，在社群網路蓬勃發展的情況下，操控使用者於網路上信譽評比的攻擊行為，已儼然成為一個不可輕忽的重大議題。本研究主要目的是發展應用於社群網路上的女巫攻擊偵測機制，利用社群網路中使用者間的友誼關係，進而計算其關係強度並針對使用者進行分群，最後利用群體結構驗證的方式特性進行惡意使用者的偵測。本研究將所提出之偵測機制應用於真實社群網路環境中進行驗證，可將正常使用者與惡意使用者成功辨別，系統針對惡意使用者之偵測準確率達到95%以上，顯示本研究針對社群網路中的女巫攻擊可以有效偵防，並對於社群平台的使用者提供一更加安全可靠的使用環境。

Recently, social network has become more popular in the Internet. In some social network, such as eBay, Google+ ... etc, have a score mechanism that scores for a set of objects (e.g. service providers, services, goods or entities). We call that the reputation system. A malicious user use a lot of multiple virtual identity attempt to influence the operation of the trust system that called Sybil Attack. We also call these nodes which the malicious user created are Sybil Nodes. The thesis proposed the different approach to detect the Sybil Nodes in social network. The defense strategies developed by the relationship in the social network. We calculate the similarity as the relations strength between nodes by these relationships and clustering the all nodes. After the clustering, we identify the group by Spectral analysis. By using the method, we could identify the Sybil group in the social network, the detect Sybil Nodes rate is above 95 %.

[1] http://focustaiwan.tw/news/aeco/201402270030.aspx
[2] http://math.nist.gov/javanumerics/jama/
[3] http://snap.stanford.edu/data/
[4] http://www.statisticbrain.com/facebook-statistics/
[5] http://www.twnic.net.tw/ibnews.php.
[6] B. Mohar, “The Laplacian Spectrum of Graphs,” Wiley, pp. 871-898, 1991.
[7] B. M. Waxman, “Routing of multipoint connections,” IEEE J. Select. Areas Communication, vol.6, no.9, pp. 1617-1622, December 1988.
[8] D. A. Spielman, “Algorithms, Graph Theory, and Linear Equations in Laplacian Matrices,” in Proc. of the International Congress of Mathematicians, August 2010.
[9] E. Jaho, M. Karaliopoulos, I.Stavrakakis, “Iscode: a framework for interest similarity-based community detection in social networks,” in IEEE INFOCOM Workshops, April 2011.
[10] F. Chung, “Eigenvalues and the Laplacian of a Graph,” American Mathematical Society, ch.1, pp. 1-14, 1997.
[11] F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, I. Stoica, “Wide-Area Cooperative Storage with CFS,” in Proceedings of the eighteenth ACM symposium on Operating systems principles, October 2001.
[12] F. Radicci, C.Castellano, F.Cecconi, V.Loreto, D.Parisi, “Defining and identifying communities in networks,” in Proceedings of the National Academy of Sciences, January 2004.
[13] G. Danezis and P. Mit, “SybilInfer: Detecting sybil nodes using socialnetworks,” in Network and Distributed System Security Symposium, February 2009.
[14] H. Yu, M. Kaminsky, P. B. Gibbons, and A. Flaxman, ”SybilGuard: Defending against sybil attacks via social networks,” in SIGCOMM, June 2008.
[15] 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, May 2008.
[16] J. R. Douceur, ”The sybil attack,” in International workshop on Peer-To-Peer Systems, March 2002.
[17] J. Vegelius, S. Janson, and F. Johansson, ”Measures of similarity between distributions,” Quality and Quantity, vol.20, no.4, pp.437-441, December 1986.
[18] K. Wehmuth and A. Ziviani, “Distributed location of the critical nodes to network robustness based on spectral analysis,” in Proceedings of the Latin American Network Operations and Management Symposium, October 2011.
[19] K. Wehmuth and A. Ziviani, ”Distributed assessment of network centrality,” in CoRR, August 2011.
[20] M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” in Proc. Natl. Acad. Sci. USA, vol.99, no.12, pp. 8271–8276, 2002.
[21] R. Kannan, S. Vempala, and A. Vetta., “On clusterings: Good, bad and
Spectral,” Foundations of Computer Science, pp. 367-378, 2000.
[22] W. K. Hastings, “Monte carlo sampling methods using markov chains and their applications,” Biometrika, vol.57, no.1, pp.97-109, April 1970.
[23] W. Wei, F. Xu, C. C. Tan, and Q. Li, ”Sybildefender: Defend against sybil attacks in large social networks,” in IEEE INFOCOM, March 2012.