Press "Enter" to skip to content

SynchroTrap-基于松散行为相似度的欺诈账户检测算法

 

大家好,我是小伍哥,今天给大家分享一个非常牛逼的算法,叫做SynchroTrap。

 

一、极致对抗下的风控怎幺做?

 

为了好理解,以淘宝刷单的风险对抗阶段为例(各阶段为假设,本人并未做过刷单的风控)

 

第1阶段: 同设备,同地址,大量购买

 

第2阶段: 同设备、地址部分变化,大量购买

 

第3阶段: 设备变化,IP、支付等介质有聚集,大量购买

 

第3阶段: 设备采用模拟器,变化IP,不同收货地址,空包等虚假物流,大量购买

 

··· ···

 

第N阶段: 设备真实、IP真实、地址真实、物流真实、用户真实… …

 

所有的都是真实的,俗称众包刷单,这种怎幺办?

 

有人说,所有东西都真实,那不就是真实的成交了幺,还管啥?非也。虽然信息都真实,但是购买意愿和目的不是真实,受刷单团伙统一指使,严重破坏生态平衡,若不加管控,将导致劣币驱逐良币的现象,对平台经济的持续发展产生毁灭性的打击。

 

那遇到这种情况,我们风控人员是不是就束手无策了呢?同样也是非也。已经有比较成熟的方法进行挖掘。只是方法比较抽象,不是很好理解。让我慢慢道来。

 

当然这种方法,不仅仅用于刷单,任何薅羊毛行为、营销作弊、刷评论、抖音刷点赞、刷粉丝,朋友圈刷榜单等风险类型都能用,且不依赖于任何介质,只依赖行为特征。我在多个场景应用,效果非常好。

 

如果你是风控从业者,一定要研究该算法,做完升职加薪肯定没问题!!

 

 

二、什幺是SynchroTrap?

 

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

 

恶意账户在社交网络、电商生态、外卖等业务上通常会有松散的同步行为进行黑产活动,行为上具有一定相似度。

 

基于攻击者松散的同步行为和经济约束,构建了恶意账户检测系算法SynchroTrap,大流程如下:

 

基于用户之间行为相似度构建网络

 

利用算法进行图分割+连通子图查找发现团伙

 

优化实现大规模计算,对系统进行持续监控

 

 

三、攻击者表现和经济约束

 

 

1、 Facebook上传图片攻击行为

 

通过下图可以看出而恶意用户(图a)行为较集中、持续,而且使用到的IP资源较少 。正常用户(图b)的行为比较随机,且使用大量不同的IP(现在几乎不存在IP相同的了,论文时期还比较多)

 

 

x轴是用户上传照片的时间,y轴代表用户ID,点(x,y)代表某用户在某时刻发生的上传照片行为, 颜色代表此次行为使用的IP地址。

 

 

2、Instagram 用户关注攻击行为

 

下图可以看出恶意用户呈现“开关”的行为模式(只在某些时间点有行为), 并且使用的IP有限制。

 

 

 

3、经济约束

 

分析为什幺社交网络中攻击者趋向“松散同步”的行为,主要原因是受到资源和任务的约束

 

2.3.1 资源约束

 

攻击者受物理计算(服务器)、网络资源(IP地址)的成本约束,甚至从云服务器租用。并且制造虚假、养号以及维护管理账户会产生人工和运营成本。

 

2.3.2 任务约束

 

收入来源明确需求的任务,比如在多少时间内完成多少评论、赞、好友数。基本很多任务都需要在规定的时间内完成,因此,黑产任务,时间维度的同步很难规避,如果避开时间维度,成本将不可控。

 

 

四、挑战及解决

 

 

1、可扩展性

 

低信噪比:Facebook上有规模较大的用户活动数据(日活6亿),恶意用户只占其中很少的比例(每次攻击数千用户),会导致低信噪比,但是,难达到较高的检测准确率。

 

解决方法:根据攻击者的经济约束,在检测系统中引入下述约束约束在每个应用级别(如FB、INS)、某个事件级别(关注、点赞)上进行检测。通过IP地址、被关注的账户、被点赞的页面 分割用户计算相似度。

 

计算压力大:两两用户做相似度计算,计算复杂度O(n^2)

 

解决方法:分而治之,将任务基于时间维度分成较小的任务,并行执行, 然后聚合结果多个较小的计算结果以获得一段时间的相似度。

 

 

2、准确性

 

无监督异常检测往往容易受到准确性的制约,通过了解攻击者经济约束(业务经验),并提炼出知识加入系统中提高准确性。

 

另外提供了一组参数,针对实际场景调节 误杀(false postive)和 召回 (false negative)

 

 

3、 适用不同场景

 

攻击者会针对不同的功能(点赞、上传照片)攻击,对系统的要求是能够扩展适用不同的场景的攻击。

 

包括分离个性化操作 和 通用操作, 以及对动作进行抽象,使得系统可以与特定OSN(online social network)独立。

 

 

五、识别策略设计

 

 

1、用户行为(user action)

 

时间轴上的一个垂直箭头表示用户在Online Social Network上的一种操作,不同类型的箭头表示不同类型的操作(例如,点赞,转发,评价、关注、上传照片…)

 

通常每个用户一天当中的操作是不同的,如左图,但是Malicious Accounts组织通常是接受了某个任务,需要在规定时间内完成指定的操作,所以会出现右图矩形框中的情况,他们在时间轴上的箭头是完全同步的。

 

 

 

2、按场景对行为分组

 

由于攻击者的任务和操作约束,他们在特定时间只会集中针对某个功能进行攻击,只会使用用户行为空间中的子集行为。

 

故可以根据不同功能对行为分类,并在功能层次进行检测,例如按照“上传照片”、“页面点赞”将用户进行分组,每个组内计算用户之间相似度并进行检测。

 

这样做的好处是:

 

降低信噪比:如果使用用户整体行为进行比较,可能会出现“维度灾难”,错过部分只针对某OSN功能的攻击

 

降低计算成本:两两用户计算相似度 是指数级别的开销

 

 

3、数据说明及行为匹配

 

总结计算用户相似度的字段:

 

 

UID:用户ID

 

Timestamp:user action发生的时间戳

 

AppID:user action所属功能类别,如发帖、评论、上传照片等;

 

AssocID:user action作用对象ID,如某页面、某USER、某照片;

 

IP address:user action发生时使用的IP地址

 

抽象带时间戳的用户行为(U为userID, T为动作时间戳, C为约束对象):

 

约束对象是各个属性值的组合,例如限制在对同IP、点赞功能下、在某页面上发生行为的用户,进行相似度计算 。

 

行为匹配:若在约束下,两个用户的行为发生的时间都落在预定义好的匹配窗口内,那说明他们行为是匹配的:

 

 

4、用户间相似度度量

 

基于Jaccard测量两个集合之间相似度,分为每个约束下的相似度和全局相似度。

 

4.3.1 约束下的相似度

 

设 Ai 为用户Ui的行为集合:Ai = {⟨U, T , C ⟩|U =Ui }

 

设 为在约束Ck下用户的行为集合:  = {⟨U, T , C ⟩|U =Ui , C =Ck }

 

则两用户i、j在约束Ck下的用户相似度:

 

 

4.3.2 全局相似度

 

在有些约束下,用户与操作对象的关联可能只出现一次,例如安装app,这样jaccard相似度取值只有0/1。为了更好地表征用户之间相似性,使用全局相似度(即综合所有约束下的用户间相似度):

 

 

 

5、行为聚类

 

设定边权重(共享的IP地址数量)阈值T,抽取G的子图(边权重w>=T)。对G作连通子图聚类,得到k个连通图。若连通图的成员数大于M,那幺对该连通图进一步作取子图操作,但边权重阈值从T变成了T+1。不断迭代上述整个过程。

 

单链层次聚类(不推荐)

 

现有的聚类方案(如k-mean)不具有扩展性,故使用单链层次聚类。大概的思路是:初始化:为每个节点指定一个簇逐步合并高相似度的簇,若两个簇间用户相似度最小值 超过某一个阈值,则合并。

 

 

层次聚类:https://mp.weixin.qq.com/s/QD_rpJ4Iyv8gp3SFVVVamA

 

图分割 + 连通子图查找

 

由于单链层次聚类依赖自下而上构建树,还是难以并行

 

采用等价的图分割+连通子图查找方法:过滤低于某阈值的边,然后执行连通子图算法

 

图构建   – 图分割  – 联通子集查找 – 子集评分 – 节点评分

 

 

 

过滤边的方法:

 

F1:至少存在一个约束对象,对该约束对象用户间相似度超过某个阈值:防范在单约束下的攻击(如同IP地址)

 

F2:全局相似度超过某个阈值, 防范跨多个约束对象的攻击场景。

 

 

六、并行化实现用户间相似度计算

 

对于用户的相识度计算,计算开销是最大的问题,算法的工程问题主要是为了解决如何计算账号相似度,由于【账号对(i,j)的交集次数=账号对(i,j)的并集次数-账号i的行为次数-账号j的行为次数】,并且账号的行为次数非常好计算,因此主要问题是如何计算【账号对(i,j)的交集次数】。

 

一个简单的方法是按照Constraint Object进行partition,每个分区统计账号对的共现次数,然后再进行reduce操作,但是由于一些热点Constraint Object的存在,该方法在大数据量的情况下很难跑的出来。

 

论文首先提出了一个减少计算量的方法,该方法是按照天来计算,再对多天进行汇总。于是,现在的问题转化为如何计算一天内账号对的交集次数。

 

 

1、按天为单位并行化

 

即按天比较用户的日相似度,并将一定窗口内的日相似度聚合,如下图所示

 

 

用户Ui在某天的行为:

 

用户Ui、Uj按天计算、聚合相似度公式:

 

 

公式中最后个等号为什幺成立?因为匹配窗口是分钟级别或者一两个小时,跨天的用户行为匹配相对比较少,故等号近似成立。

 

 

2、每时级别重叠滑动窗口的相似度计算

 

即使转换成按天计算了,因为可能某些公共IP关联的用户量比较大(热门IP可能每天关联10w个用户),可能天级别的计算也会发生数据倾斜,导致计算量异常大,所以还需要进一步优化计算逻辑。

 

 

论文解决这个问题的思路是这样的,以2Tsim为时间窗大小进一步对1天的时间周期进行分组,每个组之间的计算可以并行化,于是算法可以进一步提速:重叠滑动窗口大小为Tsim(行为匹配窗口)的2倍,滑动距离等于Tsim,并删除重复计算:对在两个连续的窗口任意一个中间部分(下图阴影部分)禁用相似度计算。

 

 

假设Tsim=1H,那幺时间段0-23可以分成(0,1)(1,2)…(22,23)这几个组,每个组的时间跨度是2H,并且每个组与相邻组之间有1个小时的重叠。对于每个组,统计账号对发生同步行为的次数,并进行聚合,得到结果A。

 

按照上述计算逻辑,有一种情况会重复计算,比如:一个账号对的两个同步行为发生在4点到5点之间,那幺(3,4)和(4,5)都会对其计数一次。因此,还需要统计账号对在(0)(1)…(23)这些组发生同步行为的次数,进行聚合得到结果B,于是最终账号对的交集次数为A-B。

 

这部分最抽象,比较难理解,理解了,直接SQL就能实现,我就是在SQL中完成的这个部分。

 

 

2、提高精确度

 

提供一组参数根据实际场景选择不同取值,人为调整后来权衡误杀和召回。

 

Tsim:行为匹配窗口

 

F1:每个约束相似度过滤阈值

 

F2:全局相似度过滤阈值

 

匹配后计算额外的条件,比如行为匹配后,计算昵称相似度

 

比如较大的动作匹配窗口能够为两个用户找到更大的匹配动作集,从而增加他们的相似度,

 

较大的相似度阈值减少了召回,降低了误杀率。根据场景不同,窗口设计差异非常巨大,如在红包、点赞等场景,窗口尽量设计的小,活动持续时间短。商家领域,特别是针对养号类的商家,持续时间可能是月,甚至是年。

 

 

3、计算复杂度

 

没约束全局相似度计算:O(rn^2),n为每个每日的活跃用户数,r为每个用户每天的动作数

 

约束级别下相似度计算:O(rm^2),m为每个约束对象下每日用户数

 

连通子图查找:O(n)

 

总复杂度O(rm^2+n)

 

 

七、检测系统使用、评价和分析

 

 

1、不同场景约束设置

 

如果是资源受限的同步攻击:在用户登陆和照片上传场景,使用IP地址+cookie作为约束。

 

任务约束的同步攻击:在安装app、点赞和刷关注场景,用appID、pageID、被关注者ID作为约束,并在一些场景使用全局相似性。

 

 

2、减少误杀,影响用户体验的设置

 

仅筛选出大型子图,比如节点数超过200,这些往往都对应大型攻击。不会使 恶意子图 中所有用户操作都无效,而是仅禁止同一子图中每个账户至少出现过一次的操作。

 

 

3、提取攻击签名

 

约束对象如IP、UA、cookies等可能滥用的,故可以作为攻击签名提炼出来,构建近实时规则。

 

 

4、准确率分析(抽样)

 

 

 

5、恶意账户类型分布

 

 

 

6、增量分析

 

每个场景检测到的欺诈增量明显

 

 

 

7、攻击用户规模分布

 

 

 

8、攻击者邮箱来源分析

 

 

 

9、攻击者IP段分析

 

 

 

10、上线后效果

 

图1:开始开始稳定,后面下降原因可能是攻击者发现无法通过这种方式攻击,故停止了,后面一直稳定说明有效检测图2是每个用户被系统检测到次数,可以发现存在部分用户被检测到超过2次,这个是因为fb会对检测到的用户发送验证,部分攻击者可能会通过验证从而发起新的攻击

 

 

 

 

11、SybilRank分析

 

SybilRank应该是对每个用户在社交圈的地位进行排名,通过SybilRank 对恶意用户进行排名,描绘社交价值,发现登陆操作中有40%为0分,说明他们没有社交价值(孤岛),故可能为虚假帐户。虽然sybilrank对大部分恶意用户排名都低,但也存在部分排名高的,这个可能是也操控(盗号)了部份正常社交的用户上传照片传播给他们的朋友

 

 

六、课后思考

 

这篇文章是具有一定启发性的,账号对行为具有同步特征是恶意账号行为聚集性的必然表现。这种账号之间的联系是非常强的,并且不需要依赖一些强关联关系(如:共用设备等)。在这里,我就这篇论文会提出一些问题供大家思考或讨论:

 

1、Single-linkage层次聚类、DBSCAN和连通图算法有什幺联系,什幺样的聚类算法可以转化为图算法。

 

2、与论文中的做法相比,对Similairy Graph直接采用社区发现算法做团体挖掘有什幺优劣。

 

3、对于那种行为数量异常多的Constraint Object如何处理。

 

4、对于LockStep欺诈行为检测类算法,FRAUDAR、CopyCatch、CatchSync和SynchroTrap在适用场景上有什幺不同。

 

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注