SynchroTrap:Uncovering Large Groups of Active Malicious Accounts in Online Social Networks(论文笔记)
SynchroTrap
互联网上泛滥着各种欺诈行为。特别是社交网络诞生以来,许多职业黑客和黑色产业链便通过欺诈行为谋生。一个常见的欺诈行为便是大量的同时虚假点赞行为,也就是会有大量的用户在短期内大量地给同一个页面点赞(Synchronized Attack)。针对这种特定的欺诈行为,学术界的研究者和工业界的工程师专门研究了一种叫做 SynchroTrap 的算法。这种算法被部署在 Facebook 和 Instagram 的系统中,在一个月的时间内检测出了 200 万欺诈帐户和 1156 次大规模网络攻击。
Synchronized Attack 和正常用户行为之间的差异:
示例一:Facebook上上传图片行为
x 轴是用户上传照片的时间,y轴代表用户ID,点 代表某用户在某时刻发生的上传照片行为, 颜色代表此次行为使用的IP地址。
从下图可以看出:
恶意用户(图a)行为较集中、持续,而且使用到的IP资源较少 ;
正常用户(图b)的行为比较随机,且使用大量不同的IP。
示例二:Instagram
图中 (a) 显示的是 Synchronized Attack ,可以看到大量的用户在很短的时间区间内几乎同时产生了某种行为;而图中 (b) 的用户行为更多的是一种随机的分布。
用户行为(user action)
时间轴上的一个垂直箭头表示用户在Online Social Network上的一种操作,不同类型的箭头表示不同类型的操作(例如,点赞,转发,上传照片…)
通常每个用户一天当中的操作是不同的,如左图,但是Malicious Accounts组织通常是接受了某个任务,需要在规定时间内完成指定的操作,所以会出现右图矩形框中的情况,他们在时间轴上的箭头是完全同步的。
怎样定义一个用户?
- UID:用户ID
- Timestamp:user action发生的时间戳
- AppID:user action所属功能类别,如发帖、评论、上传照片等;
- AssocID:user action作用对象ID,如某页面、某USER、某照片;
- IP address:user action发生时使用的IP地址
将一个用户行为(user action)抽象为一个三元组<U,T,C>,U是user ID,T是timestamp,C是constraint object
用户相似度度量
Jaccard similarity
如果两个用户相似,则:
以计算出的两两用户之间的用户相似度为权重,构建连接两个用户的边。
Single-linkage hierarchical clustering algorithm(单链接层次聚类算法)
初始化:为每个节点指定一个簇。逐步合并高相似度的簇:若两个簇间用户相似度最小值超过某一个阈值,则合并。
connected components algorithm
由于单链层次聚类依赖自下而上构建树,还是难以并行。
采用等价的连通分量算法:计算完用户相似度后,并不是把计算出的相似度都用于构建边,而是事先就过滤低于某阈值的边,然后执行连通子图算法。