온라인 소셜 네트워크 그래프에 내포된 시스템-차원 시빌-저항 신뢰도 추출 = Extraction of System-Wide Sybil-Resistant Trust Value embedded in Online Social Network Graph

국문 초록 (Abstract)

인터넷의 발달의 주요 요인 중 하나인 익명성은 다수 사용자들의 자유로운 개인 의사 표현을 도와 다양한 인터넷 기반 분산시스템을 활성화하는데 있어 큰 도움이 되어 왔다. 하지만, 익명성은 개인의 정보가 외부로 알려지지 않는 다는 점 때문에 악용될 소지도 다분하다. 특히 분산시스템은 한 명의 악의적인 사용자가 다수의 가짜 신분을 생성하고 조정하는 시빌 어택(Sybil Attack)에 매우 취약하게 된다. 시빌 어택을 막기 위해서 분산시스템 상에서 신분 생성 작업의 복잡도를 높이는 방식이나 시스템상의 신분과 현실상의 신분의 연결 고리를 만드는 방법을 생각 할 수 있다. 하지만 복잡도를 높이는 방식은 가짜 신분이 만들어지는 시간을 늘리는 효과만 있을 뿐, 일단 가짜 신분이 만들어진 이후에 대한 대응법이 부족하다. 또한, 현실상의 신분과의 연결을 사용할 경우 온라인 사용자의 익명성이 훼손당할 우려가 있다. 최근 온라인 소셜 네트워크의 대중화와 함께 소셜 네트워크 그래프 정보를 사용해 시빌 어택에 대응하기 위한 기법들이 연구되고 있다. 이 논문에서는 온라인 소셜 네트워크 그래프에 내포된 특성을 이용해 임의의 사용자에 대한 시스템 차원 시빌-저항 신뢰도(System-wide Sybil-resistant trust value) 추출 방법을 제안한다. 제안하는 기법은 온라인 소셜 네트워크 전체 그래프를 이해 할 수 있는 서비스 제공자들을 위한 방법으로, 샘플링 및 판단방법에 따라 3가지 종류의 세부 기법들을 제안한다. Facebook에서 추출한 온라인 소셜 네트워크 샘플 그래프를 이용하여 제안된 기법들의 성능을 분석 및 비교한다. 또한 시빌 어택의 특성을 이해하기 위해 서로 다른 노드 특성을 가지는 노드들이 시빌 어택에 의해 받는 영향을 분석한다.

다국어 초록 (Multilingual Abstract)

Anonymity is the one of main reasons for substantial improvement of Internet. It encourages various users to express their opinion freely and helps Internet based distributed systems vitalize. But, anonymity can cause unexpected threats because personal information of an online user is hidden. Especially, distributed systems are threatened by Sybil attack, where one malicious user creates and manages multiple fake online identities. To prevent Sybil attack, the traditional solutions include increasing the complexity of identity generation and mapping online identities to real-world identities. But, even though the high complexity of identity generation increases the generation cost of Sybil identities, eventually they are generated and there is no further way to suppress their activity. Also, the mapping between online identities and real identities may cause high possibility of losing anonymity. Recently, some methods using online social network to prevent Sybil attack are researched. In this paper, a new method is proposed for extracting a user`s system-wide Sybil-resistant trust value by using the properties embedded in online social network graphs. The proposed method can be categorized into 3 types based on sampling and decision strategies. By using graphs sampled from Facebook, the performance of the 3 types of the proposed method is evaluated. Moreover, the impact of Sybil attack on nodes with different characteristics is evaluated in order to understand the behavior of Sybil attack.

참고문헌 (Reference)

1 Kyungbaek Kim, "Using multiple verifiers to detect Sybils in a social network graph" 2013

2 J. R. Douceur, "The sybil attack. In Proceedings of IPTPS 2002"

3 S. D. Kamvar, "The EigenTrust Algorithm for Reputation Management in P2P Networks" 2003

4 H. Yu, "SybilLimit:A Near-Optimal Social Network Defense against Sybil Attacks" 3-17, 2008

5 H. Yu, "SybilGuard: Defending Against Sybil Attacks via Social Networks" 2006

6 Kyungbaek Kim., "Sybil-Resistant Trust Value of Social Network Graph" 2012

7 Michael Sirivianos, "SocialFilter: Introducing Social Trust to Collaborative Spam Mitigation" 2011

8 M. Mitzenmacher, "Probability and Computing" Cambridge University Press 2005

9 A.G.P. Rahbar, "PowerTrust: A Robust and Scalable Reputation System for Trusted Peer-to-Peer Computing" 18 (18): 2007

10 Nguyen Tran, "Lakshiminarayanan Subramanian, and Sherman S.M. Chow. Optimal Sybil-resilient node admission control" 2011

11 Petar Maymounkov, "Kademlia: A Peer-to-peer Information System Based on the XOR Metric" 2002

12 Luis von Ahn, "CAPTCHA: Using Hard AI Problems for Security" Springer 2003

13 Kyungbaek Kim, "Assessing the impact of properties of a node to OSN based Sybil detection" 2013

14 Michael Sirivianos, "Assessing the Veracity of Identity Assertions via OSNs" 2012