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在适用场景上有什么不同。
大家有什么疑问,加我一起交流。
长按关注公众号 长按加作者好友