由於現今的網路世界中，加入的門檻甚低，每位使用者都可以輕易地申請帳號並且進入網路系統，因此大多數的社群網路的都處於一個容易遭受分身攻擊的狀態。為了偵測出這些惡意的使用者所申請的假帳號，很多的論文利用社群網路的朋友關係和拓樸資訊的性質去想出了一些解決辦法；然而，這些方法都假設惡意的朋友關係數量是很有限的，而這個假設在現今的社群網路中是不太真實的。這篇論文憑藉著一些數據以及我們自己的觀察打破了這個假設，接著我們利用這些資訊去模擬一個我們認為更符合現在社群網路的環境，並在這之中找出其他可以用來幫忙偵測分身帳號的特性。{em 在每個社群內的朋友數}以及{em 每個朋友關係的強度分布}是我們用來跑機器學習工具$SVM$的的參數；我們也嘗試著將兩種特性合併進而達到更好的表現。實驗結果顯示，我們的方法用在偵測分身帳號不管是在以前的環境抑或我們新提出來所比較符合現實的環境下，都能夠有令人滿意的結果。

Most existing large online social networks (OSNs) are vulnerable to {em Sybil attack} since every user in the world can join the system easily. To detect those malicious nodes in OSNs, many papers leverage the properties of network relationship and topology to bring out their schemes. However, the proposed methods all assume that the number of attack edges is limited which is not such realistic today. This thesis breaks this assumption according to some statistics provided by other works and our observations. Thus, We use the above information to simulate the more realistic topology with Sybil nodes and find out that there are still other features that can help distinguish Sybil nodes in this scenario. {em Number of friends per community} and {em Distribution of link strength} are the two features that we use to run Support Vector Machine (SVM) in our work. We also combine these two feature to make the performance better. The experiment results show that no matter the previous assumptions are hold or not, we can have a desirable performance on detecting Sybil nodes.

口試委員會審定書i
誌謝ii
摘要iii
Abstract iv
Contents v
List of Figures vi
List of Tables vii
1 Introduction 1
2 Related Work 3
3 System Model And Attack Model 5
4 Methodology Design 7
4.1 Number of friends per community . . . . . . . . . . . . . . . . . . . . . 7
4.2 Distribution of link strength . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.3 Combination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.4 Support Vector Machine . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5 Simulations 10
5.1 Dataset and Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . 10
5.1.1 Our scenario: More realistic . . . . . . . . . . . . . . . . . . . . 11
5.1.2 Previous scenario: Number of attack edge is limited . . . . . . . . 11
5.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.2.1 SVM with number of friends per community . . . . . . . . . . . 12
5.2.2 SVM with distribution of link strength . . . . . . . . . . . . . . . 14
5.2.3 SVM with hybrid features . . . . . . . . . . . . . . . . . . . . . 16
6 Conclusion 18
Bibliography 19

[1] J. R. Douceur., ``The sybil attack.'' IPTPS, 2002.
[2] H. Yu, M. Kaminsky, P. B. Gibbons, and A. Flaxman, ``SybilGuard: Defending
Against Sybil Attacks via Social Networks,'' in Proc., ser. SIGCOMM ''06.
New York, NY, USA: ACM, 2006, pp. 267--278. [Online]. Available: http:
//doi.acm.org/10.1145/1159913.1159945
[3] H. Yu, P. Gibbons, M. Kaminsky, and F. Xiao, ``SybilLimit: A Near-Optimal Social
Network Defense Against Sybil Attacks,'' Networking, IEEE/ACM Transactions on,
vol. 18, no. 3, pp. 885--898, 2010.
[4] N. Tran, B. Min, J. Li, and L. Subramanian, ``Sybil-Resilient Online Content Rating,''
in Proceedings of the 6th USENIX symposium on Networked systems design and
implementation, ser. NSDI''09. Berkeley, CA, USA: USENIX Association, 2009,
pp. 15--28. [Online]. Available: http://dl.acm.org/citation.cfm?id=1558977.1558979
[5] N. Tran, J. Li, L. Subramanian, and S. Chow, ``Optimal Sybil-resilient node admission
control,'' in INFOCOM, 2011 Proceedings IEEE, 2011, pp. 3218--3226.
[6] W. Wei, F. Xu, C. Tan, and Q. Li, ``SybilDefender: Defend Against Sybil Attacks in
Large Social Networks,'' in INFOCOM, 2012 Proceedings IEEE, 2012, pp. 1951--
1959.
[7] G. Danezis and P. Mittal, ``SybilInfer: Detecting Sybil Nodes using Social Networks,''
2009.
[8] L. Bilge, T. Strufe, D. Balzarotti, and E. Kirda, ``All Your Contacts Are
Belong to Us: Automated Identity Theft Attacks on Social Networks,'' in
Proceedings of the 18th international conference on World wide web, ser. WWW
''09. New York, NY, USA: ACM, 2009, pp. 551--560. [Online]. Available:
http://doi.acm.org/10.1145/1526709.1526784
[9] M. Mitzenmacher and E. Upfal., ``Probability and Computing,'' Cambridge University
Press, 2005.
[10] Z. Yang, C. Wilson, X. Wang, T. Gao, B. Y. Zhao, and Y. Dai, ``Uncovering
Social Network Sybils in the Wild,'' in Proceedings of the 2011 ACM SIGCOMM
conference on Internet measurement conference, ser. IMC ''11. New York, NY,
USA: ACM, 2011, pp. 259--268. [Online]. Available: http://doi.acm.org/10.1145/
2068816.2068841
[11] S. Ghorbani and Y. Ganjali, ``Will You Be My Friend? Privacy Implications of Accepting
Friendships in Online Social Networks,'' in Information Society (i-Society),
2012 International Conference on, 2012, pp. 340--345.
[12] J. Yang and J. Leskovec, ``Defining and Evaluating Network Communities based on
Ground-truth,'' CoRR, vol. abs/1205.6233, 2012.