金柔作者萝卜兔整理

论文分享 | 经典图模型欺诈检测系统BotGraph

本周论文分享是一篇2009年的论文《Botgraph: Large scale spamming botnet detection》。这篇文章虽然年代比较久远,但是仔细剖析依然有很多值得借鉴的地方。另外,文章详细介绍了一个反欺诈算法从算法设计、工程实现到业务应用的整个链路,对于刚接触反欺诈算法的同学是一个很好的入门资料。

这篇文章的作者有DataVisor的创始人谢映莲和俞舫女士,这是她们在微软研究院时期发表的论文。关于DataVisor的无监督算法在以后的文章中会进行解析,在这里先挖一个坑。下面言归正传,我们来逐步解读这篇文章。

背景

论文是为了解决一种名为“僵尸网络”(botnet)的攻击,这种攻击一般是通过僵尸程序控制很多台“肉鸡”,通过这些“肉鸡”注册大量的邮箱账号(bot-users/bot-accounts)并发送垃圾邮件。我们希望通过算法找到这些bot-users。

算法设计

由于“肉鸡”是在统一的spammer指挥下进行邮件发送等动作的,因此bot-users之间会存在一些行为的同步性或者资源上的公用。论文提出的算法是基于botuser的注册、登录、发送邮件等操作时共享的IP地址,建立botuser之间的关系。

第一步:构建User-User图

以每一个bot-user为图上的顶点,以两个bot-user共享的IP数量作为边的权重

第二步:层次聚类(自上而下)

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

该核心算法是一个自上而下的层次聚类,随着层数的加深聚类条件越来越严格,第一层为原始图无约束条件,而第二层的团体必须满足w>=T,以此类推。

第三步:剪枝(pruning)

根据第二步得到团体后,需要对团体的置信度进行评价,即该团体的嫌疑度到底有多大。论文中采用的规则是团体中80%的成员日均发送邮件数>3,若团体满足该条件则认为是一个候选的botuser团体。

需要注意的是这里的删除操作可以认为是独立针对每一个节点的。父节点删除其子节点不一定会删除;同理子节点删除,父节点也不一定会删除。关于这一点,在最后的讨论中会再谈。

第四步:成团(Grouping)

第三步得到的候选嫌疑团体之后,还要做一次树的遍历。该步是为了解决如果父节点和子节点都是嫌疑团体,那么应该取哪一个的问题。遍历的方法是:

1)若父节点(成员数为N)至少存在一个子节点团体包含的成员数量为o(N),则向下遍历;

2)若父节点(成员数为N)所有子节点团体包含的成员数量都不超过o(log N),那么停止遍历。

前四步的算法实施过程可以用下图来形象化表示:

第一层是最原始的user-user图R;

第二层是由R分解的A和B两个大规模团体(子图)和其他小规模团体(或者孤立点),子图A和B中的边都满足w>=T并且成员数>M;

第三层则是由A和B进一步分解的大规模团体C、D、E,这些团体的边都满足w>=T+1并且成员数>M;

第四层则是由C、D、E分解的若干小规模团体(或者孤立点),这时已经没有团体满足w>=T+2并且成员数>M。

下面则是成团操作:

A满足向下遍历条件到C,C满足停止遍历条件则停止,A由一个giant group(C)和其他一些小规模团体(或者孤立点)组成,因此A是一个bot-user团体(C属于团体A)。

B满足向下遍历条件到D和E,D和E满足停止遍历条件则停止,B由两个giant group(C)和其他一些小规模团体(或者孤立点)组成,因此B不是一个bot-user团体(D和E是)。

第五步:验证

这一步是从更多的角度去验证团体是否正确,如团体中的账户昵称是否有相同的模式等。

工程实现

工程实现部分主要讲的是如何用分布式算法建图。

第一种简单的数据并行化方法:Map阶段,根据IP进行分区,对于每个分区维护一个以(Ui,Uj)为key的HashTable,生成(Ui,Uj,1);Reduce阶段,以(Ui,Uj)为key作hash partition,聚合weight。

第二种则是采用了过滤的方法:Map阶段,根据UserID进行分区;对于分区p,生成该分区中出现IP的一个List,将这个IP List分发到其他各分区,对于其他分区中的User若使用IP List中的IP数量小于w那么在图中肯定形成不了边,于是将其过滤掉,将剩下的(U,IP)传输到原分区p中。

问题和讨论

对于一个算法工程师,仅仅达到读懂论文的程度是远远不够的。为了能将经典论文在实际业务中借鉴和应用,一些背后蕴藏的问题需要认真思考。下面我列举一下读完这篇论文中后发现的问题:

1. 在剪枝步骤中,为什么团体节点的处理是独立的、与层级结构无关?

2. 两种并行化建图方法各有什么优劣,我们如何根据自己的实际情况进行选择?

3. 在算法第四步中确定团体(grouping)的时候,为什么A是一个图体、但是B不是?这样处理会不会造成一些遗漏?

4. 可以建立User-IP的异构图进行连通图聚类吗?与这样做与建立User-User图的区别在哪里?

5. 团体的层级结构应该采用什么样的数据结构存储比较好?

6. 对若干规模不等的子图做连通图聚类时如何设计并行算法效率最高?


大家可以积极参与思考和讨论,共同成长哦~

资源地址论文链接:https://www.usenix.org/legacy/events/nsdi09/tech/full_papers/zhao/zhao.pdf
原文地址:https://zhuanlan.zhihu.com/p/57479763
极验
极验

极验是全球顶尖的交互安全技术服务商,于2012年在武汉成立。全球首创 “行为式验证技术” ,利用生物特征与人工智能技术解决交互安全问题,为企业抵御恶意攻击防止资产损失提供一站式解决方案。

理论算法反欺诈
相关数据
微软机构

微软是美国一家跨国计算机科技公司,以研发、制造、授权和提供广泛的计算机软件服务为主。总部位于美国华盛顿州的雷德蒙德,最为著名和畅销的产品为Microsoft Windows操作系统和Microsoft Office办公室软件,以及Xbox的游戏业务。微软是美国《财富》杂志2015年评选的世界500强企业排行榜中的第95名。

https://www.microsoft.com/en-us/about
权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

剪枝技术

剪枝顾名思义,就是删去一些不重要的节点,来减小计算或搜索的复杂度。剪枝在很多算法中都有很好的应用,如:决策树,神经网络,搜索算法,数据库的设计等。在决策树和神经网络中,剪枝可以有效缓解过拟合问题并减小计算复杂度;在搜索算法中,可以减小搜索范围,提高搜索效率。

层次聚类技术

层次聚类通过对数据集在不同层次进行划分,从而形成树形的聚类结构。数据集的划分可采用“自底向上”的聚合(agglomerative)策略,也可采用“自顶向下”的分拆(divisive)策略。“自底而上”的算法开始时把每一个原始数据看作一个单一的聚类簇,然后不断聚合小的聚类簇成为大的聚类。“自顶向下”的算法开始把所有数据看作一个聚类,通过不断分割大的聚类直到每一个单一的数据都被划分。

聚类技术

将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合,这些对象与同一个簇中的对象彼此相似,与其他簇中的对象相异。“物以类聚,人以群分”,在自然科学和社会科学中,存在着大量的分类问题。聚类分析又称群分析,它是研究(样品或指标)分类问题的一种统计分析方法。聚类分析起源于分类学,但是聚类不等于分类。聚类与分类的不同在于,聚类所要求划分的类是未知的。聚类分析内容非常丰富,有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。

DataVisor机构

DataVisor成立于2013年美国硅谷,2016年正式进入中国,同时在东南亚、欧洲等地均有业务部署。DataVisor 是硅谷知名反欺诈企业,DataVisor一站式用户分析平台为当下复杂多变的欺诈问题提供了最先进的反欺诈技术解决方案。 DataVisor的优势在于基于 Spark 大数据平台独创的无监督欺诈检测算法,每小时可分析数十亿用户事件。能够对新型多变的欺诈进行提前预警,提前发现恶意欺诈行为,能够帮助客户大大降低欺诈损失。截止到目前,DataVisor全球累计处理超过8干亿的用户事件,检测超过2亿的坏用户,保护超过41亿来自全球大型公司的用户。

https://www.datavisor.com/
推荐文章
暂无评论
暂无评论~