shine's dev log
[논문] Smoke Screener of Straight Shooter: Detecting Elite Sybil Attacks in User-Review Social Networks 본문
[논문] Smoke Screener of Straight Shooter: Detecting Elite Sybil Attacks in User-Review Social Networks
dong1 2022. 3. 8. 00:31논문 제목 : Smoke Screener of Straight Shooter: Detecting Elite Sybil Attacks in User-Review Social Networks
0. Abstract
아마존과 같은 User-Review Social Network (URSN) 사이트에서 대량으로 fake account를 생성하고 평점을 조작하는 Sybil attack 이 최근 자주 발생하고 있다.
본 논문에서는 elite Sybil attack 이라는 용어를 다음과 같이 정의한다. 유기적으로 highly-rated accounts들을 생성해 겉보기에 trustworthy 하고 realist-lokking한 review들을 생성해내는 공격이다.
elite Sybil attack은 accounts들이 large scale을 이루며 sparsely-knit 하게 구성되어 기존의 탐지 시스템을 무력화 시킨다.
본 논문에서는 ELSEDET 이라 불리는 elite sybil attack 탐지 시스템을 제안한다. ELSEDET은 3단계로 구성되어 있는데, 1) 의심스러운 그룹을 분리한 뒤, 2) campaign window를 식별하고 3) campaign 에 포함된 elite Sybil user를 찾아낸다.
본 연구에서는 Dianping에서의 수십만개의 review를 대상으로 실험을 진행했으며, elite sybil attack의 파급력과 탐지 방안을 보였다.
1. Introduction
일반적인 Sybil attack과는 다르게 elite sybil attack은 이미 특정 사이트에서 높은 평판을 가지고 있는 accounts를, 리더의 지휘 하에 조직적으로 review를 조작한다. 따라서 elite sybil attack을 탐지하거나 방지하는 것은 매우 힘든 일이다.
기존의 Online Social Networks(OSNs) 에서의 sybil attack 방지는 대표적으로 두가지 방식을 사용한다. 1) account의 social network connectivity를 파악하는 방식과 2) accounts의 feature를 통해 ML classifier를 활용하는 방식
이러한 방식들은 URSN 에서는 잘 통하지 않는데 그 이유는 다음과 같다.
1) URSNs의 node들은 OSN 만큼 잘 연결되어있지 않다. (팔로워 등의 개념이 거의 없으므로) 따라서 graph connectivity 방식은 효과적이지 않다.
2) URSNs에서의 elite sybil attack은 정교한 리뷰를 남기거나 사진을 남기기 때문에 일반적인 OSN에서보다 탐지 방법이 복잡하다.
3) 일반적인 sybil attack과 다르게 elite sybil attacker는 전체 리뷰 중 일부분의 리뷰만 sybil attack에 사용한다. 따라서 aggregate 한 탐지 방식은 효과적이지 않다.
이러한 elite sybil attack을 탐지하기 위해, 본 연구팀은 여러 sybil workers들이 특정 task를 수행하는 Sybil campaigns 에 집중하였다. 이러한 campaigns들은 특정 시간에 발생되므로, 해당 시간에 rewview를 올린 사용자들은 모두 용의자선상에 있다.
용의자 중에서 실제 sybils를 판단하기 위해 장기적인 관점에서 바라보았을 때, 더 많은 campaigns에 참여할수록 sybils 일 확률이 높아진다는 점을 이용한다.
ELSIEDET은 3가지 단계로 동작한다.
1단계) sybil community를 탐지한다. elite sybil group의 행동을 분석하여 sybil community를 탐지한다.
2단계) Sybil campaign time window를 결정한다. 새로운 방식의 campaign 탐지 알고리즘을 통해 특정 campaign의 시작과 끝을 정의함으로써 time window를 결정한다.
3단계) elite sybil user를 찾아낸다. 새롭게 정의된 metric인 Sybilness를 통해, 참여자가 참여하는 정도를 scoring 하여 slite sybil user를 찾아낸다.
또한 본 논문에서 수행한 Contributions는 다음과 같다.
1) Dianping이라는 URSN의 Sybils 들은 일반적인 centralized or simple distributed 구조가 아닌 하이브리드한 구조로 진화하고 있음을 알아냄.
2) elite Sybil users라는 새로운 개념의 Sybils를 정의함.
3) elite Sybil이라 불리는 사람들의 행동 특징을 파악했으며, 조기에 Sybil campaigns를 탐지하고 경고할 수 있는 시스템을 제안하였다.
4) ELSIEDET가 현재 Dianping의 필터링 시스템을 보완하며, Dianping으로부터 인정받음.
2. Background
우선 Dianping은 중국의 대표적인 User-Review Social Network사이트로, 특이하게 어느정도 리뷰가 많고 '믿을만한' 사용자에게 'senior level user'라는 타이틀을 주는데 이 사람들이 sybil attack에 이용되는 사람들이다.
sybil attack은 과거에는 단순히 인터넷 서비스에 타격이나 무리를 주는 공격에서 시작되어, 최근에는 트위터, 아마존과 같은 유명한 사이트에 금전적으로 피해를 입히기 시작했고, 그 방법도 점점 정교화되어 탐지에도 어려움을 겪고 있다. 특히 최근에는 URSN 사이트를 타깃으로 실제 소비자들에게도 피해를 입히고 있다.
3. Dissecting Elite Sybil Attacks
3.1. Terminology
1) Store
Store 'S'는 Dianping에서 많은 수의 리뷰를 가지고 있는 특정 웹사이트이다.
2) Community
Community 'C'는 특정 store에 리뷰와 평점을 남기는 사람들의 집합이다. 정상적인 사람들로 구성된 benign communities와 malicious한 사람들로 구성된 Sybil communities로 분류할 수 있다.
3) Campaign
(C, S, T_s, T_e) = (Community ID, Store ID, start Time, end Time)으로 표현되는 Campaign은 특정 community C의 사람들이 store S에 특정 시간동안 S의 prestige를 높이기 위해 리뷰를 다는 행위를 의미한다.
3.2. Elite Sybil Users
일반적인 Sybil user와는 다르게 Elite Sybil user들은 작정하고 Sybil 관련 task만 수행하는 것이 아니라, 평소에는 정상적으로 활동하다 (금전적인) 보상 등을 위해서 일부분 Sybil task를 수행하는 것이다. 따라서 이를 탐지하는 것은 기술적으로 굉장히 어렵다.
Elite Sybil user는 1) Sybil task에 속하지 않고 그냥 campaigns를 사용하기 위해 리뷰를 올리는 사용자와 2) 정상적인 사용자에게 속한 계정이라 account rating이 높지만, 보상을 위해 특정 campaign의 Sybil task 를 수행하는 계정이다.
또한 여러 사용자나 조직에 의해 관리되는 Sybil attack과 다르게 Elite Sybil user는 sybil leader라 불리는 특정 조직에 의해 관리된다.
3.3. Anatomy of Elite Sybil Attack Operations
본 연구팀에서 실제 Elite Sybil attack을 수행하는 집단에 들어가 그들의 조직을 파악해본 결과 (그림 1)과 같은 구조로 동작하고 있음을 알아냈다.
우선 자신의 상품의 평점이 오르길 원하는 Customers가 Agents에게 요청하면 Agents는 여러 Leader를 통해 Elite Sybil Accounts를 고용하고 그들에게 보상을 주는 형태로 동작하게 된다.
여기서 Agents는 Sybil campagins를 생성해내고, 실제 Elite Sybil accounts를 고용하고 관리하는 것은 Leader의 역할이다.
Elite Sybil attack의 work flow 는 아래 [그림 2]와 같다.
work flow는 크게 (a) Leader의 가이드에 맞춰 elite Sybil workers들이 직접 리뷰를 작성하는 Leader-supervised model 와 (b) Leader가 직접 리뷰를 workers에게 주고, workers들이 실제 사이트에 리뷰를 작성하는 Leader hands-on model로 분류할 수 있다.
실제 elite Sybil account를 생성하기 위해서는 account 가 생성된 후 성별, 생일 등의 프로필 정보를 Dianping 상에 업로드 해야하며, 정상적이고 퀄리티 높은 리뷰들을 여러개 작성하여 account의 rating을 올리는 작업이 선행되어야 한다.
4. ELSIEDET: Design and Implementation
앞서 말했듯이 ELSIEDET은 크게 3가지 단계로 동작한다.
1) detecting Sybil communities
2) determining campaign time windows
3) detecting elite Sybil users
4.1. Sybil community detection
Sybil community detection은 크게 3가지 단계로 구성된다.
1) Constructing Sybil Social Links via Collusive reviews
우선 특정 community에 속한 사용자 간에 Sybil social links를 그려야 한다.
그렇다고 community에 속한 모든 사용자를 다 이을수는 없고, 모든 사용자 쌍에 대하여 [그림 3]의 Sim(u, v) 수식을 계산하게 된다.
[그림 3]에서 R(u) = {(U, T1, S1, L1), (U, T2, S2, L2), ..., (U, Tn, Sn, Ln)} 으로 정의되는데, 각 튜플들은 사용자 u가 작성한 리뷰이다. U는 UserID, T는 리뷰 작성 시각, S는 리뷰 작성한 StoreID, L은 리뷰의 rating 정보이다.
해당 R(u)에서 두 리뷰가 같은 store에 작성되었고, 비슷한 시간대에 작성되었고, 별점이 1 또는 5점일 경우에만 P_u(k) = 1 을 만족하며, 나머지 경우에는 모두 0을 만족한다.
이렇게 [그림 3]과 같은 수식을 통해 Similariy를 구하고, 해당 값이 threshold 값을 넘어설 경우에, 두 user간에 Sybil social links를 그어주며, 두 user를 neighbors 라고 부르게 된다.
2) Community Clustering via the Louvain Method
다음으로 그어진 Sybil social links를 기반으로 Louvain method를 통해 Community의 users들을 Clustering 하는 과정을 거친다.
하지만, 단순히 Louvain-detected communities를 통해 수많은 Sybil users를 찾는 것은 충분치 않다고 생각이 되어, 다음 단계에서 Louvain-detected communities에 supervised ML 을 적용하였다.
3) Sybil Community Classification
clustering된 communities 중에서 benign 과 sybils 를 구별하기 위해 supervised ML을 적용하게 된다. 해당 ML 과정에 사용되는 features는 [그림 4]와 같다.
features는 총 3가지 카테고리에 8가지 features로 구성되어 있다.
전체 score의 분산을 나타내는 score deviation은 Sybils일 경우 더 커지게 된다. 또한 Entropy of the number of reviews in each chain stores 값은 발생한 리뷰의 개수를 측정함으로써 얻어질 수 있는, 각 chain store에 포함된 정보량의 기댓값이다.
또한 sybil community와 benign community는 [그림 5]와 같이 굉장히 다른 양상을 띄고 있기 때문에, Average similarity, Global clustering coefficient 의 features를 채택하게 되었다.
4.2. Campaign Window Detection
앞서 찾은 Sybil community 중에서 Sybil Campaign이 실행되는 시간 구역을 나타내는 Campaign Window를 찾기 위해, 리뷰의 rating이 갑자기 증가하는 때를 찾는 burst detection algorithm (예를 들면 Bayesian change point detection algorithm) 을 사용할 수도 있지만, 특정 프로모션 할인과 같은 이벤트때문에 rating이 갑자기 증가할 수도 있기 때문에 해당 방식은 문제가 있다.
본 연구팀에서는 이를 해결하기 위해 anomaly collaborative behaviors를 탐지하는 방향으로 진행하였다. 이를 위해 Sparse Review Interval을 찾아 쳐내는 방식을 채택하였다.
즉, 특정 store에 달린 리뷰를 주 별로 표시한 다음, 리뷰가 거의 없는 sparse review interval을 양 옆에서부터 잘라내서 더이상 sparse review interval 이 없어질 때까지 반복한다.
해당 알고리즘은 [그림 6]과 같으며, [그림 7]과 같이 전체 기간을 Sparse review interval 과 Campaign time window로 나눌 수 있게된다.
4.3. Elite Sybil User Detection
이제 얻어낸 Campaign Window 와 해당 Window에 참여한 사용자들 정보를 가지고 participation rate와 Sybilness 를 얻어내면 된다.
우선 participation rate를 계산하기 위해서는 [그림 8]에서 볼 수 있듯이 Nc(k)와 Nc_max를 구해야 한다.
Nc(k)는 community C의 k번째 time window에서 작성된 누적 리뷰 수이고, Nc_max는 C의 전체 time window 중 가장 많은 리뷰가 작성된 수 이다.
이제 k번째 time window에서 작성된 누적 리뷰 수 Nc(K)를 Nc_max로 나누어줌으로써 normalize를 해주게 된다. 이 normalize된 값 Pc(k) = Nc(k) / Nc_max 로 표현된다. 이 Pc(k) 값은 k번째 window의 중요도를 나타내주는 계수로 볼 수 있다.
또한 Nu_c(k)를 k번째 window에서 사용자 u가 작성한 리뷰의 개수라고 할 경우, community C에서 사용자 u의 weighted sum은 [그림 9]와 같이 나타낼 수 있다. 사용자 u의 weighted sum은 특정 Community C에서 사용자 u의 비중을 나타내주는 계수로 볼 수 있다.
이제 이 Nu_c(k) 값을 sigmoid 함수에 넣음으로써 community C에 대한 사용자 u의 participation rate (시그마 u) 을 구할 수 있다. participation rate를 구하는 수식은 [그림 10]과 같다.
Sybilness score는 사용자가 elite Sybil user일 가능성을 나타내주는 지표이다. 앞서 살펴본 participation rate은 특정 community C에 대한 사용자 u의 참여도를 나타낸 지표이므로 만약 elite Sybil user가 여러 community에 조금씩 참가할 경우, participation rate은 작게 나타날 것이다.
이를 해결하기 위해 Sybilness score를 고안하였으며, Sybilness score f() 는 단순히 모든 community C에 대하여 participation rate와 Nu_C를 더한 값이다. 이를 수식으로 나타내보면 [그림 11]과 같다.
5. Evaluation
실험에 사용된 데이터셋은 직접 Dianping 사이트의 여러 store와 review를 크롤링 하여 획득하였다. 총 32,933개의 store, 10,541,931개의 review, 3,555,154개의 users를 획득할 수 있었다.
community를 라벨링 하는데는 경험적인 직관에 의거한 기준 3가지를 두고 사람이 직접 labelling하였다.
ELSIEDET을 사용한 결과 데이터셋에서 총 710개의 community를 탐지할 수 있었다.
특정 community가 sybil 한지 benign 한지 판단하기 위해 다양한 ML 모델을 적용한 결과 [그림 12]와 같은 결과를 얻을 수 있었다.
그 결과 SVM 모델을 사용하고 5-fold cross-validation 을 사용한 모델이 가장 좋은 성능을 뽑아냄을 알 수 있었다.
다음으로, Elite Sybil user를 탐지하는데에는 두가지 기준을 적용시켰다.
1) 사용자 u가 어느 community에도 속해있지 않으며
2) 사용자의 user participation rate 시그마u가 0.5를 넘는 경우이다.
그 결과 총 12,292개의 elite Sybil users를 탐지할 수 있었다. 단순히 binary classification을 하는게 아니라, sybilness score를 기준으로 정렬하여 보여준다.
6. Measurement and analysis
일반적인 Sybil users 와 비교해보았을때 elite Sybil users는 [그림 13]과 같은 경향을 띈다.
우선 suspicious reviews 수는 Elite Sybil users - Sybil users - benign users 순으로 많았다. 이는 일반적인 Sybil users는 새롭게 account를 생성하고 바꾸는 것이 가능하기 때문에 elite Sybil users에 비해 낮게 나온 것으로 보인다.
또한 Percentage of fake reviews는 Regular Sybils 에 비해 elite Sybils가 훨신 낮게 나왔다. 이는 elite Sybil attack의 정의에 의하면 당연한 결과이다.
마지막으로 filtered 된 reviews의 비율은 Regular Sybils - elite Sybils - benign users 순으로 많았다. 이는 elite Sybils 가 일반적인 Sybils에 비해 필터링될 확률이 적다는 것을 의미한다.
또한 본 연구팀은 chain store 역시 Sybil attacks를 사용한다는 것을 밝혔으며, 7-day slide window를 사용해 elite Sybil users를 파악하고 이를 통해 조기에 elite Sybil attacks를 파악하는 방안 또한 제안하였다.
[그림 14]를 보면 3명의 elite Sybil users가 각각 ELSIEDET과 Dianping의 Sybil detection system 을 통해 필터링된 정도를 알 수 있다.
이를 통해 Elite Sybil users가 수많은 양의 리뷰를 올리면 aggregate nehavioral-based clustering 방식의 user activity similarity를 계산하는 방식의 탐지 시스템을 잘 우회하는 것으로 나타났다.
또한, Dianping의 Sybil 탐지 시스템은 너무 민감하여 falsely filtered 하는 경우가 많았다. 이는 [그림 14]의 (c)를 보면 알 수 있다.
7. Discussion and Limitation
우선 Sybilness score에 따라서 의심스러운 사용자에 대한 weight 를 바꿔주면 Sybil attack으로 인한 부정적인 영향을 완화시켜줄 수 있다. 예를들어 의심이 많이가는 사용자에게 더 낮은 weight를 할당해주면, Sybil organization은 rating을 조작하기 더 어려워질 것이다.
또한 elite Sybil users를 모두 찾으려는 것보다, Sybilness score가 높은 몇명의 사용자를 찾고, 해당 사용자가 참여해있는 그룹을 조사하면 보다 효과적으로 elite Sybil users를 탐지할 수 있다.
반면 본 연구팀에서는 Dianping 상에서 users 간의 social link를 조사하지 않았던 점, elite Sybil user가 여러 campaign에 조금씩 참여하는 경우에는 회피될 가능성이 있다는 점, 다른 URSN에 대해서는 실험하지 못했던 점을 한계로 꼽았다.
9. Conclusion
본 논문에서는 URSNs에 대해 elite sybil attack의 구조를 파악하고, 이를 탐지하고 조기에 필터링할 수 있는 시스템을 제안하였다. 또한 실제로 다양한 chain store에서도 자신들의 평점을 조작하기 위해서 elite sybil attack을 사용하고 있음을 보였다.
또한 temporal patterns를 가지고 정교하게 조작하는 것이 공격자가 회피하지 못하게 만드는 key임을 강조하며 본 논문을 마쳤다.
Reference
Haizhong Zheng, Minhui Xue, Hao Lu, Shuang Hao, Haojin Zhu, Xiaohui Liang, Keith Ross, "Smoke Screener or Straight Shooter: Detecting Elite Sybil Attacks in User-Review Social Networks." , arXiv e-prints, arXiv-1709, 2017
