本周论文分享是一篇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
