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

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

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

enter image description here

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

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

1.通常由于计算资源和运营成本的原因。欺诈用户通常在有限的时间内控制大量的用户。 2.因为黑色经济的原因,欺诈行为通常都是任务性质的,也就是有任务时间限制的。

为了更好的解决 Synchronized Attack 问题,我们首先定义“匹配”的概念。所谓匹配是指: enter image description here

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

定义用户与用户之间的 Jaccard 相似度为: enter image description here

其中:

enter image description here

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

SynchroTrap 的时间复杂度是 O(r*n^2)。

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

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

原文:Uncovering Large Groups of Active Malicious Accounts in Online Social Networks   原文作者:Qiang Cao , Xiaowei Yang , Jieqi Yu , Christopher Palow