SynchroTrap : 一个月内检测 200 万欺诈帐户

汪昊

haow85@outlook.com

互联网上泛滥着各种欺诈行为。特别是社交网络诞生以来，许多职业***和黑色产业链便通过欺诈行为谋生。一个常见的欺诈行为便是大量的同时虚假点赞行为，也就是会有大量的用户在短期内大量地给同一个页面点赞（Synchronized Attack）。针对这种特定的欺诈行为，学术界的研究者和工业界的工程师专门研究了一种叫做 SynchroTrap 的算法。这种算法被部署在 Facebook 和 Instagram 的系统中，在一个月的时间内检测出了 200 万欺诈帐户和 1156 次大规模网络***。

SynchroTrap 的算法非常简单, 最根本的原理就是利用 Jaccard 相似性挑选出在某一个时间窗口内行为特别相近的那些用户。

下面我们来直观的感受一下 Synchronized Attack 和正常用户行为之间的差异：

上图中 (a) 显示的是 Synchronized Attack ，可以看到大量的用户在很短的时间区间内几乎同时产生了某种行为；而图中 (b) 的用户行为更多的是一种随机的分布。

为了更好的理解 Synchronized Attack 这种欺诈行为，我们先来看一下欺诈行为的经济学约束条件：

1. 通常由于计算资源和运营成本的原因。欺诈用户通常在有限的时间内控制大量的用户。

2. 因为黑色经济的原因，欺诈行为通常都是任务性质的，也就是有任务时间限制的。

为了更好的解决 Synchronized Attack 问题，我们首先定义"匹配"的概念。所谓匹配是指：

其中 U 是用户 id ，C 是用户的行为集合，而 T 是行为集合产生的时间。

定义用户与用户之间的 Jaccard 相似度为：

其中：

计算完用户与用户之间的相似性后，我们得到了一张以用户为节点的图。然后我们采用单链接凝聚层次聚类的方法对用户进行聚类：

SynchroTrap 的时间复杂度是 O(rn^2)。

SynchroTrap 算法的原理非常的简单, 把检测 Synchronized Attack 问题

转化成了聚类问题。聚类问题不可避免的需要涉及到点和点之间距离的计算，SynchroTrap 的作者用常用的相似性距离计算度量 Jaccard Distance 来表示点和点之间的距离。然后采用了凝聚层次聚类的方法进行了聚类。整个算法的过程非常的简洁流畅。

上图显示的是在 11 周的时间里每周被检测的用户数。

原文：Uncovering Large Groups of Active Malicious Accounts in Online Social Networks

原文作者：Qiang Cao , Xiaowei Yang , Jieqi Yu , Christopher Palow