本次分享的反欺诈算法论文：
论文|
Uncovering Large Groups of Active Malicious Accounts in Online Social Networks
作者|
Qiang Cao,Xiaowei Yang@杜克大学；Jieqi Yu,Christopher Palow@Facebook
来源|
users.cs.duke.edu/~qiangcao/publications/synchrotrap.pdf
关于异常检测算法内容及实践的介绍，大家可以多读读@小伍哥聊风控写的文章。
以下为论文的主要内容：
摘要
在线社交网络的成功吸引了很多攻击者，这些攻击者通常控制着大量恶意账户包括虚假(fake)和被盗(compromised)的真实用户帐户，用来发起诸如传播垃圾邮件消息、传播恶意软件、发起社会工程攻击，或操纵在线投票结果等攻击活动，为此我们设计并实现了一个名为 SynchroTrap 的恶意帐户检测系统。
恶意帐户通常在各种社交网络环境中执行松散同步的操作(loosely synchronized acitions)，
SynchroTrap 根据用户行为的相似度对用户账户进行聚类，可以发现大量恶意账户。我们将 SynchroTrap 开发在
Hadoop 和 Giraph 上运行，以便有效地处理大型 OSN 中的海量用户活动数据，而且
在 Facebook 和 Instagram 中作了部署，结果显示
SynchroTrap 能够在一个月内揭露超过 200 万个恶意帐户和 1156 个大型攻击活动。
1. 论文内容介绍
Facebook、Google+、Twitter 或 Ins 等 OSN 是网络攻击的热门目标。以前防御攻击的大部分做法旨在直接识别攻击者控制的虚假或被盗帐户，通常有两种做法，一种是使用一个帐户的社交网络连接来推断它是否是假的，这种方法能够揭露与真实社交网络几乎没有联系的虚假账户，但很难识别被盗的真实账户或已获得许多社交联系的维护良好的虚假账户。另一种在实践中广泛采用的方法是构建机器学习分类器来推断恶意帐户，可以有效地对具有一组已知恶意特征的恶意账户进行分类，但可能会漏掉许多具有未知特征的恶意账户。
在这种挑战下，Wang 等人在 2013 年探索了一种新方法。他们分析了社交网络账户的总体行为模式，以区分恶意账户和合法账户，比如分析来自虚假帐户的 http 请求与来自真实帐户的 http 请求有何不同，并使用此功能来识别假帐户，再比如研究发现恶意帐户倾向于在大致相同的时间向欺诈性 Facebook 页面发布虚假喜欢，并设计 CopyCatch 来检测此类同步帖子。这种做法推进了使用聚合行为模式(aggregate behavioral patterns)来发现恶意帐户的最新技术。受 CopyCatch 的启发，我们发现恶意帐户倾向于在各种社交网络环境中共同行动。除了发布虚假赞之外，他们还可能以松散同步的方式登录、安装APP、上传垃圾照片等。
接下来就是 SynchroTrap 的面世了，它可以发现大量以松散同步方式运行的恶意帐户。SynchroTrap 的研究也面临许多挑战，这些挑战使其有别于该领域的先前尝试(即CopyCatch和Clickstream)。首先，与 CopyCatch 不同，SynchroTrap 旨在为广泛的社交操作检测松散同步的行为，因此不能假设用户只能执行一次恶意操作，即用户只能对特定页面点赞一次，这种目标差异大大增加了它的算法复杂性。其次，检测恶意账户的行为其实是一种异常检测问题。恶意行为仅占总用户行为的一小部分。例如 Facebook 每天有超过 6 亿活跃用户，他们每天执行数十亿次操作，而攻击活动中涉及的恶意帐户数量通常在数千个量级，如何才能从大量嘈杂的数据中准确地检测出如此微弱的信号呢？第三，最终目标是在 Facebook 等 OSN 上部署 SynchroTrap 系统，因此检测算法必须能够每天处理几 TB 的数据，而许多现成的异常检测算法或以前的做法如Clickstream，不能扩展到这种大小的数据。
为此我们开发了几种简单但实用的应对技术。首先，将恶意帐户检测问题建模为聚类问题，比较特定时间段内的成对用户操作，并将大致同时采取类似操作的用户分组到集群中，并将大小超过可调阈值的集群标记为恶意。这是因为从真实的社交网络中观察到，合法用户会随着时间的推移采取不同的行动。其次，为了使聚类算法易于计算，进一步使用攻击者的网络资源约束如控制的 IP 地址的数量，或攻击者的目标如欺诈性 Ins 帐户，以减少成对比较每个 IP 地址和每个目标对象。最后，将用户行为数据划分为每天或每小时的小块(chunks)。我们设计算法来聚合这些小块之间的比较结果，以检测更长时期（例如一周）内的恶意行为。这种技术使我们能够以增量处理方式实现 SynchroTrap，使其能够部署在大型 OSN 上。
我们已在脸书和 Ins 部署 SynchroTrap 十多个月，在对一个月数据的详细研究中，发现了超过 200 万个恶意帐户和 1156 个恶意活动。随机抽取了 SynchroTrap 捕获的恶意帐户子集，并请安全专家检查结果的准确性，检查显示系统达到了高于 99% 的精度。SynchroTrap 平均每周捕获约 274K 恶意帐户。同时在脸书的 200 台机器集群上评估了 SynchroTrap 的性能，结果显示系统能够处理脸书和 Ins 的用户数据，处理每日数据需要几个小时，处理每周聚合作业需要 15 个小时。
诚然，攻击者可能会尝试传播恶意帐户的行为以逃避 SynchroTrap 的检测，但分析显示 SynchroTrap 可以有效地限制攻击者的恶意行为率，即使他们控制了无限数量的恶意账户。此外我们提供了一组参数，调整这些参数以在误报和漏报之间实现权衡，在严格的设置下，SynchroTrap 的误报率几乎为零。
SynchroTrap 研究的工作可总结如下：
- 观察到恶意账户倾向于在各种社交网络环境中共同行动。
- 设计、实施和部署 SynchroTrap。解决了使用松散同步操作来发现恶意社交网络帐户的几个实际挑战。
对检测到的恶意账户的特征进行了初步分析。这种分析可以为其他基于特征的恶意帐户检测系统提供思路。
2. 两个真实攻击示例
2.1 Facebook 恶意上传照片
图1：Facebook恶意图片上传示例
x 轴为账号上传照片的时间，y 轴为账号 ID，图中一个点(x，y)表示 ID 为 y 的账户在时间 x 上传了一张照片。点的颜色编码操作的 IP 地址，相同颜色的照片上传来自相同的 IP 地址。
图 1(a) 绘制了一周内来自一组 450 个恶意帐户的带有时间戳的照片上传情况，他们通过上传垃圾照片来宣传减肥药，这些恶意帐户使用几个 IP 地址上传了许多垃圾照片。水平色条表示它们在一周内在一小组 IP 地址之间切换。图 1(b) 显示了 450 个随机选择的帐户的照片上传情况，这些帐户为从未被标记为恶意帐户的普通用户，这些操作在时间上更加分散，并且来自更多样化的 IP 地址集。
2.2 Instagram 虚假关注
图 2：Ins用户关注示例
x 轴是帐户后续操作的时间戳，y 轴是帐户 ID，点(x, y)表示账户 y 在时间 x 关注目标账户。点的颜色编码了关注帐户的 ID，相同颜色的操作来自相同的帐户。
图 2 比较了 1000 名恶意用户和 1000 名普通用户之间的用户关注活动，恶意账户是从涉及 7K 账户的攻击活动中抽取的，用来达到快速涨粉目的。
2.3 攻击者的经济约束
为什么各种社交网络攻击倾向于松散同步发生？我们推测可能受到经济限制。
计算和运营资源的成本。攻击者的物理计算资源有限，尽管可以购买或控制机器（例如僵尸网络），甚至可以从云计算服务中租用，但会产生财务成本。此外，这些计算资源的运行时间有限，因为被控的机器可能随时离线、恢复甚至被隔离，并且机器租赁通常根据消耗的计算效用收费。另一个运营成本是伪造或盗用真实账户以及维护和管理账户的人力。在这些操作限制下，攻击者通常会在有限的时间内从一组机器控制他的恶意帐户。
完成特定任务才能有收入。OSN 攻击者通常深根于地下市场，例如 BlackHat World 和 Freelancer。大部分任务都有特定要求的，通常包括客户追求的level of prevalence以及完成期限。例如 Freelancer 中的许多社交网络任务在 Y 天内征求 X 个脸书朋友关注和在看，类似的任务还包括关注、发帖、评论等。这些要求迫使攻击范围只能局限在受害者的某些特定项并在截止日期之前采取行动。
对这些经济约束的理解以及它们随后在受控账户活动中的表现有助于直接攻击攻击者的弱点，使其难以逃避检测。
3. SynchroTrap 系统
SynchroTrap 是一个通用且可扩展的框架，可以有效地限制 OSN 中的大量恶意帐户，其主要思想是使用聚类分析来大规模检测来自恶意帐户的松散同步操作。首先测量成对的用户行为相似性，然后使用层次聚类算法将在较长时间内具有相似行为的用户分组在一起。
可扩展性：首先，大量用户活动数据导致信噪比低，难以实现高检测精度，对此我们按照 OSN applications 划分用户操作并在每个 applications 的基础上进行检测。通过关联的目标或源对象（例如IP地址、关注者ID和页面 ID）进一步划分用户操作，以捕获攻击者的约束。其次，庞大的活动数据量使得那些通用处理难以实现。由于对硬件容量（例如内存）的要求，在脸书这种规模的服务中进行大型和复杂的批量计算会使得资源共享变得非常困难并且故障恢复成本高昂。为此我们采用了分而治之的方法，将用户对比的计算沿时间维度划分为较小的作业，并使用并行性进行扩展，然后我们聚合多个较小计算的结果以获得周期长的用户相似度。
准确性：正常用户行为的多样性和恶意活动的隐蔽性阻碍了高精度检测，异常检测方案难免地会产生误报和漏报。为了降低误报率和漏报率，我们基于对攻击者经济约束的理解设计了 SynchroTrap。由于这两个比例通常成反比，SynchroTrap 在其设计中提供了一组可调参数，调整这些参数可获得较好的权衡。
对新applications的适用性：由于用户操作属性（例如用户与其他 OSN 对象之间的关联）在不同的applications中可能会有所不同，因此针对一个applications优化的检测方案可能不适用于其他应用程序。例如CopyCatch可检测欺诈性页面点击喜欢（仅一次操作），但不能用于发现来自同一 IP 地址的重复垃圾照片上传。对此我们将相似性度量与聚类算法分离，这样就能够处理一次性操作和其他通用操作。此外我们用元组抽象表示一个操作，包括时间戳维度和攻击者约束维度。这种抽象使系统设计独立于 OSN applications。
4. 系统设计
我们根据 OSN applications（第 4.1 节）对用户操作进行分类，并在每个applications的基础上执行检测。我们为带有时间戳的用户操作定义了一个通用匹配指标（第 4.2 节），并使用匹配操作的比例来量化用户对的相似性（第 4.3 节）。我们使用单链接层次聚类算法根据成对用户相似度对用户进行分组（第 4.4 节）。在第 4.5 节中，我们将用户对比较的计算并行化以解决大数据挑战。
OSN 通常以 OSN applications 的形式提供许多特性和功能，例如照片上传、消息传递等。恶意帐户通常不会攻击所有平台上有的功能，为了降低运营成本，攻击者会专注于他的任务并仅针对用户的部分行为，例如上传垃圾照片、推广流氓应用程序等。因此，使用所有用户操作数据的方案可能会错过仅针对特定 OSN 功能的恶意用户。这个问题让人想起聚类高维数据时的“维度灾难”。为了减轻不相关操作的影响，我们根据用户所属的applications将用户的操作分类为子集，称之为application contexts，然后在每个application contexts中检测恶意帐户。例如我们将照片上传和页面喜欢application分开，以分别对抗这两个操作。接下来将描述如何为OSN application收集这些用户操作。
在 SynchroTrap 中，将带有时间戳的用户操作抽象为元组，每个元组都有一个明确的约束字段，表达资源约束和任务约束。每个用户操作都有许多属性，如表 1 中，AppID 可以包括应用层网络协议（例如HTTP）的标识符，可表示细粒度的application类别。AssocID 可以是相关 OSN 对象（例如照片、页面、用户等）的标识符。我们将前面提到的元组表示为 <U,T,C>，其中 U，T 和 C 表示分别是用户 ID、操作时间戳和约束对象。约束对象可以是某些操作属性的组合，例如 AssocID、源 IP 地址等集合。
表 1：用户操作的属性及其含义
对用户操作的元组抽象，使 SynchroTrap 能够快速适应applications中的特定攻击，前提是正确指定约束字段。例如可以选择关注者标识符（AssocID 的一种）作为约束字段，以击败 Ins 上的泛滥用户。
基于元组抽象，我们定义操作匹配，用”≈”表示。如果不同用户的两个操作属于同一个约束对象并且它们的时间戳落入预定义长度Tsim(例如1小时)的相同时间窗口，则认为它们匹配，也就是说只有当两个用户操作发生在 Tsim 的匹配窗口内时，它们才可能匹配。
4.3 Pairwise user similarity metrics
计算两个用户在时间段 Tp（例如一周）内匹配行为的占比来量化两个用户的相似度，采取 Jaccard 相似度作为相似度度量方式，对应取值范围从 0 到 1，接近 1 的值表示高相似度。
每个约束的相似度(Per-constraint similarity)。引入约束相似度来衡量单个约束对象（例如单个源IP地址）上匹配操作的比例。令 Ai 为用户 Ui 执行的操作集合，即。由于要求用户操作的约束字段完全匹配，我们进一步根据约束字段的值将 Ai 分解为不相交的子集，即其中。如下所示，使用Jaccard相似度推导单个约束对象上的用户相似度。通过前面提到的”≈”计算来获得集合交集和集合并集。
4.4 Scalable user clustering
由于其有效性和可扩展性，选择单链接层次聚类算法来聚类用户，其他聚类方案要么依赖于距离度量（例如k-means中的欧几里德距离），要么不可扩展。此外，我们也没使用图分区算法，即使是广泛使用的图分区工具，如 METIS也需要花费数小时来处理只有数百万个节点的图。而我们的目标是将检测方案转换为可以扩展到大型 OSN 的聚类算法。
单链接层次聚类。采用凝聚(agglomerative)方法，从每个用户作为不同的cluster开始，迭代地合并相似度高的聚类，产生更大的聚类。该算法生成一个聚类合并树状图，显示聚类的合并层次结构和每个级别的相似度。通过在期望水平上阻断树状图，可以获得多个簇，其中簇内用户相似度超过某个特定阈值。因为该算法依赖于顺序过程以自下而上的方式构建整个树状图，所以简单的实现很难扩展。
图 3：分两步将单链接层次聚类算法转换为连通分量算法。边代表用户之间的相似性，由较粗边缘连接的用户对具有更高的相似度。
使算法适合并行实现。单链接层次聚类的关键特性是两个cluster的相似度取决于从每个不同cluster中抽取的所有成对用户之间的最大相似度。cluster相似度度量将每次迭代中的一组相邻clusters合并为用户相似度图中的一个更大的连通分量(connected component)，其中节点是用户，如果一对用户的相似度高于某个阈值，则在它们之间存在undirected edge。使用此属性，我们将该算法调整为并行版本。首先设置相似度阈值并过滤掉低于该阈值的用户对，则所需的用户clusters正是修剪后的用户相似度图中的连通分量。从而我们可以采用有效的图算法来搜索连通分量，图 3 说明了我们对单链接聚类算法的两步调整。我们选择去适应连通分量算法，因为它固有的并行性而在海量图上具有高度可扩展性。
User-pair过滤功能
。使用过滤功能来选择在某些行为有一定相似度的用户对，为此引入了两个标准。
- F1：存在至少一个约束对象，用户对其每个约束的相似度都高于某个阈值
- F2：它们的全局相似度高于某个阈值
第一个过滤标准揭示了在一组单一约束对象（例如IP地址）上表现出松散同步行为的恶意用户对。在某些情况下，恶意帐户甚至可能将其行为分散到多个约束对象上。我们使用标准 F2 来比较用户在每个约束对象下只能执行特定操作的applications的用户相似度。
4.5 Parallelizing user-pair comparison
采取增量处理巨量的用户活动数据流。我们将用户对比较的大型计算划分为时间维度上的一系列较小的计算，存储中间结果并在特定时间段内汇总它们。这种处理管道大大减少了单个作业量，从而减少了它的硬件消耗，使 SynchroTrap 在实践中成为一种更具可扩展性和可管理性的解决方案。
4.5.1 Daily comparison
图4：脸书的SynchroTrap processing pipeline
对用户比较的计算进行切片，在日常作业中根据用户活动日志生成相似的用户对。SynchroTrap会在持续的一段时间内检测到松散同步的活动，因此可以汇总每日相似度指标并定期（例如每周）进行聚类。如图 4 所示，箭头表示数据流，由于聚合作业可以复用日常作业的结果，因此新的聚合作业不会导致重新执行日常作业。
我们通过分解几天内的长期用户相似度来设计日常任务和聚合任务之间的可聚合data interface，如下所示。令
表示用户 Ui 在第 t 天对约束对象 Ck 执行的一组操作，即
。对于一个用户对(Ui, Uj ) 和一个约束对象 Ck，生成并存储他们的每日操作匹配数
，以及他们每个人每天执行的总操作数，即
和
。
通过汇总每日结果，可以得到一段时间内的用户相似度。最后一个等式成立，是因为用户操作在几天内很少能匹配上的，因为选择的匹配窗口的大小大约是几分钟或几小时。
4.5.2 Hourly comparison with sliding windows
图 5：脸书登录时IP地址上的用户分布
日常工作中的Stragglers。用户匹配工作通过MapReduce来实现，而其生成的job完成时间可能会被散乱的reducers延长。这种straggler问题是因为用户操作在约束对象下呈现出高度倾斜的分布。即使按天来看，也存在与大量操作/用户相关的热门对象。图 5 显示了脸书一天内通过 IP 地址登录的用户数量分布。虽然大多数 IP 地址并没有被很多用户（少于 100 个）使用，但每个 IP 上的用户分布是长尾的，每天有超过 10 万活跃用户使用少数几个流行的 IP 地址可能会导致reducers运行数天。
使用重叠滑动窗口进行缓解。通过进一步对不同操作的用户进行分区来缓解这个问题。如果分区中的用户数量减少了 1/f (f > 1) 的因子，则执行时间可以减少 1/f^2，因为我们执行了二次用户对相似度计算。挑战是有效地划分用户操作数据，同时保留准确捕获操作匹配的能力。将用户操作在时间维度上划分为重叠的滑动窗口，并并行处理不同的滑动窗口。这种方法不仅提供更小的数据块来缓解straggler问题，而且在成对比较之前有效地过滤掉驻留在不同滑动窗口中的不匹配操作。
滑动窗口设置。如果未正确设置滑动窗口大小和重叠周期，则重复数据删除可能会很复杂。为了在每个滑动窗口内平衡数据量有效性的弱化和去重操作匹配的复杂性，我们选择使用大小为 2Tsim 的滑动窗口和长度为 Tsim 的重叠周期，通过简单地丢弃每个滑动窗口的第二（或前）半部分内即图中阴影部分数据来实现单次计数。
图 6：SynchroTrap中重叠滑动窗口的设置
图 6 中不同标记代表不同的用户操作。原则上，滑动窗口大小>Tsim并且重叠周期≥Tsim可以覆盖所有用户操作匹配情况，因为前者确保了任何具有最大跨度周期Tsim的用户操作匹配都可以被滑动窗口覆盖；后者确保滑动窗口足够密集，以覆盖窗口中的所有匹配情况。
通过仅在每个滑动窗口中独立计数，可以准确计算所有用户操作匹配情况。假设有一系列滑动窗口SWi = [iTsim, (i+2)Tsim) (i≥0)，用 t1 和 t2 表示两个匹配上的用户操作的时间戳，其中 t2 ∈ [t1, t1 + Tsim]。假设 t1 ∈ [jTsim,(j + 1)Tsim) (j ≥ 0)，就可以得到 t2 < (j + 2)Tsim。关于action pair的位置存在两种情况：a) t2 < (j +1)Tsim。t1和t2都属于区间[jTsim,(j+1)Tsim)，正是是两个连续滑动窗口SWj-1和SWj的重叠区域，因为我们丢弃了每个后半窗口内的操作匹配，所以操作对在 SWj 中仅计算一次；b) t2 ∈ [(j + 1)Tsim,(j + 2)Tsim)。只有SWj 涵盖了t1 和t2，因为t1∈ [jTsim,(j + 1)Tsim)，因此action pair在 SWj 中是单一计数的。我们总是在最后一个滑动窗口之后附加一个空的半窗口，以应对数据流末尾的极端情况。
4.6 提升准确率
首先，恶意行为的数量和同步级别在不同的 OSN applications中有所不同。攻击者可能会随着时间的推移改变策略以规避现有的检测方案。其次，作为影响用户体验的系统，SynchroTrap必须使用保守的参数来最小化误报率，即不将任何合法用户标记为恶意用户。
SynchroTrap允许调整一组参数，以在误报和漏报之间实现所需的权衡。主要参数包括操作匹配窗口大小Tsim和每个约束相似度 (Simpc)和全局相似度 (Simoverall)的过滤阈值。这些参数的设置对错误率有单调的影响：更大的操作匹配窗口使 SynchroTrap 能够为两个用户找到更大的匹配操作集，从而增加他们在约束对象下的相似度；另一方面，较大的用户相似度阈值会减少被认为相似的用户对的数量，并降低两个用户被聚集在一起的可能性。这些单调效应简化了设置参数过程并减少了人工干预的需要，可以根据当前设置的误报率选择向上或向下调整参数值。
4.7 计算成本
理论上，SynchroTrap 的计算成本为O(rn^2)，其中 n 是每个application的日活跃用户数，r 是每个用户的每日操作数。在实践中可以显着降低这种计算成本，因为只需要比较属于同一目标对象或来自同一源对象的用户操作，每日计算成本实际为O(rm^2)，其中 m 是每个application每个目标或源对象（即每个活动目标或每个IP地址）的每日活跃用户数。每周聚合的成本与日常作业生成的用户对数量成线性关系。在用户相似度图中搜索连通分量的成本是O(n)。因此总体计算成本为 O(rm^2 + n)。
5. 开发
我们在脸书的 Hadoop MapReduce 堆栈之上构建了 SynchroTrap。我们在 Hadoop上实现了每日user comparison模块和每周aggregation 模块，在 Giraph 上实现了clustering模块，这是一个基于批量同步并行(BSP)模型的大图处理平台。Giraph提供了连接connected components的并行实现。除了脸书基础架构支持的基本功能外，SynchroTrap 开发包含了 2500 行 Java 代码和 1500 行 Python 代码。
6. 安全性分析
在不同对抗策略下SynchroTrap的安全性分析。
扩频攻击。攻击者可能会试图隐藏 SynchroTrap检测到的同步信号，我们称之为扩频攻击。给定目标数量的滥用行为，攻击者可以统计地在更长的时间段或更多的约束对象（例如IP地址和活动目标）上传播攻击行为。由于资源成本增加和活动收入减少，此类攻击的利润较低。即使攻击者控制了无限数量的帐户，SynchroTrap能够限制攻击带来的损害，我们提供了关于攻击者在特定时间段内可以对约束对象执行的操作总数的上限分析。
假设我们的检测窗口 Tp（例如一周）包含 w 个长度为 Tm（例如1小时）的操作匹配窗口。因为每个账户的速率会被限制，我们假设一个账户在每个操作匹配窗口内最多可以执行 L 个操作。尽管每个帐户的操作数量受 wL 的限制，但如果没有SynchroTrap，如果攻击者可以控制大量恶意帐户，则恶意操作总数仍然是无限的。相比之下，SynchroTrap会限制对约束对象（例如IP地址）的滥用行为总数，而与攻击者控制的恶意帐户数量无关。在 SynchroTrap 下，攻击者必须将其帐户的操作分散到匹配窗口上，这样一对帐户就不会有很多匹配的操作。因此给定 w 个匹配窗口，可以同时作用于约束对象的恶意帐户的数量是有限的。
具体来说，SynchroTrap 使用 Jaccard 相似度来评估两个用户的操作集。为了逃避检测，恶意账户 Ui 和 Uj 的匹配操作比例必须低于某个阈值 p (0 < p < 1)：|Ai ∩ Aj | ≤ p × |Ai| 和|Ai ∩ Aj |≤ p×|Aj |。一个最优的攻击策略是根据具有最大基数的action集 {Ai} 调度一组帐户，以最小化两个恶意帐户在同一个集群中被捕获的机会。寻找具有最大基数的 {Ai} 仍然是交叉集理论中的一个悬而未决的问题，这对攻击者提出了挑战。
我们通过计算其超集的最大大小来给出这样一个集合 {Ai} 的基数上限。我们找到这样一个超集 {Bi}，其中 Bi ⊆ Bj 只有当 Bi = Bj 时。也就是说，在 {Bi} 中没有一个集合包含在另一个集合中。因为集合 {Bi} 不需要 |Bi ∩ Bj | 中的阈值，它放宽了集合 {Ai} 的条件，因此放宽了 {Ai} ⊂ {Bi} 的条件。如果匹配阈值 p 设置为接近 1，则集合 {Bi} 逼近集合 {Ai}。在集合论中，{Bi} 被称为集合的反链，其中没有一个集合是另一个集合的子集。根据 Sperner 定理，假设检测窗口包含 w 个匹配窗口，最大反链的大小满足，因此我们有，它指定每个约束对象的活动恶意帐户数的上限。因此，假设所有帐户在检测窗口 Tp 期间保持活动状态，则来自该恶意帐户组的操作总数进一步受的限制。
激进的攻击。可以通过控制账户在短时间内执行批量操作来发起激进的攻击。如果用户操作集大小或用户配对相似度不符合 SynchroTrap 用户配对过滤功能的标准，SynchroTrap 可能会检测不到此类攻击。然而此类攻击一直是现有对策的重点，这些对策旨在寻找用户操作的突然变化。SynchroTrap系统可与现有的异常检测方案一起工作，并通过应对更隐蔽的攻击对其进行补充。
7. 部署
我们在脸书和 Ins 部署了 SynchroTrap，并将其集成到脸书的站点保护堆栈中。
7.1 在脸书和Ins上的五个用例
我们根据绑定攻击活动的约束来展示 SynchroTrap 的用例。对于每种类型的攻击方约束，我们在 Facebook 和 Instagram 展示了几个用例。
Resource-constrained synchronization。我们使用的资源约束是针对发起攻击的源 IP 地址。在 Facebook 用户登录和照片上传时使用此配置部署了 SynchroTrap。OSN 提供商还可以将某些安全 cookie 包含到 SynchroTrap 的约束中，从而能够以更精细的粒度检测资源受限的攻击。
Mission-constrained synchronization。我们使用的任务约束是目标对象 ID，分别包括 Facebook 应用 ID、页面 ID 和 Ins 关注者 ID 作为约束字段。我们在 Facebook 应用程序安装和page like,以及 Ins 用户following context部署了 SynchroTrap，这些案例中使用的都是全局相似度。
7.2 攻击者签名和响应(Signatures and response)
攻击签名。SynchroTrap 提取可疑帐户组的共同约束对象。这些约束对象指向的 OSN 实体可能是滥用的，因此可以用作攻击签名。它们包括流氓 Facebook apps、包含不当内容的脸书页面、滥用 Ins 帐户以征求过多关注者等。通过追溯完整的用户操作日志，SynchroTrap 甚至可以提供攻击者机器的指纹，包括 IP 地址，用户代理、浏览器 cookie 等。所有上述签名都可用于构建快速分类器，以近乎实时地抑制未来的攻击，并采取适当的响应。
8. 评估
我们在 2013 年 8 月使用 Facebook 的一个月执行日志评估 SynchroTrap。通过回答以下问题显示出 SynchroTrap 为大型OSN提供了实用的解决方案：
SynchroTrap 能否准确检测恶意帐户，同时产生低误报率？
SynchroTrap 在发现新攻击方面的效果如何？
SynchroTrap 能否扩展到 Facebook 大小的 OSN？
8.1 验对已识别出的帐户
我们在 Facebook 安全团队的支持下验证恶意帐户。继续对已确认的帐户进行调查，以了解对手如何设法控制它们。此外我们研究了检测到的攻击的网络级特征，包括恶意帐户使用的电子邮件域和 IP 地址。
表 2：已识别帐户和精度，精确度是已识别帐户中被确认为恶意的部分
验证方法。在这一个月内，SynchroTrap 发现了数百万个帐户，全部作验证不现实，也因为大部分检测到的帐户没有被其他方法捕获，不可能将这些帐户与其他现有 Facebook 对策交叉验证，因此选择在人工协助下随机抽取部分账户作为代表性样本来进行验证。
精确度。表 2 显示 SynchroTrap 共检测到 1156 个大型活动，涉及超过 200 万个恶意帐户，准确率高于 99%，此外大型攻击活动由数百万用户操作组成。在五个部署的applications中，攻击者在页面喜欢和用户关注方面更加活跃，可能是因为这种活动更有利可图。通过发现大型活动，SynchroTrap 可使数百万恶意用户操作无效。
误报Post-processing 。误报不利于用户体验。除了在设置参数的过程中增加人工外，还可通过后期处理进一步减少误报。首先，我们丢弃小用户集群，只筛选出更可能来自大型攻击的大型集群。根据系统的经验，Facebook 安全团队将阈值设置为 200，超过该阈值的每个集群中的几乎所有用户都被发现是恶意的。其次，我们不会使恶意帐户在检测窗口 Tp 期间执行的所有操作无效，而是保守地关注那些与同一集群中每个其他帐户的至少一个操作匹配的操作。此后处理步骤有助于排除用户帐户在受到威胁时可能已发生的有效操作。
活动的规模。图 7 显示了虽然 80% 的活动涉及不到 1000 个帐户，但也发现了一些非常大的活动，其中攻击者操纵了数千个帐户。
图 7：与参与用户数量相关的活动CDF
如何控制恶意账户？Facebook 安全团队发现这些控制手段包括使用欺诈性用户信息创建虚假帐户，通过恶意软件破坏用户帐户，通过社会工程窃取用户凭据等，如表3显示这三者是主要的恶意帐户来源，占检测到的帐户的 90% 以上。
表 3：在脸书应用安装中检测到的恶意帐户分类
网络级特征。我们研究了恶意用户使用的电子邮件域和IP地址。OSN帐户通常与联系电子邮件地址相关联，如图 8 所示，受控账户使用的电子邮件凭据主要来自五个领域，包括雅虎、Hotmail 和 Gmail 等主要电子邮件域。可以从地下市场获得帐户的电子邮件域很可能被用于为受控帐户提供欺诈性邮件地址。尽管Gmail帐户根据调查显示会给攻击者带来更高的成本，但发现一小部分已识别帐户使用 Gmail 地址。此外还有部分邮件地址来自域 *.ru。由于识别出的帐户使用了不同的电子邮件地址集，因此该结果表明仅电子邮件域并不是检测恶意帐户的可靠标准。
图 8：与每个application中恶意帐户关联的主要电子邮件域
我们进一步研究检测到的恶意活动的源 IP 地址。我们发现检测到的 200 万个账户总共使用了 120 万个 IP 地址。图 9 可以看出，攻击集中在 IPv4 的三个地址域：36.67.* – 44.99.*、77.246.*–125.226.*和170.226.*–207.78.*。不同application中的IP地址分布相互接近，只是APP安装中的攻击者更密集地使用77.246.*–125.226.*区域的IP。我们随机抽取了其中部分 IP 地址，通过 WHOIS 服务器来查询域名注册信息。许多 IP 地址由世界各地的大型区域 ISP 管理（例如巴西的Global Village Telecom和沙特阿拉伯的沙特电信），部分 IP 地址用于提供共享 Internet 访问（例如，=用于网络代理或公共Internet访问点）。我们还观察到，IP地址中有很大一部分来自托管服务，如GoDaddy和 Singlehop，以及来自大型云计算服务如亚马逊AWS。这一观察表明，基于云服务为互联网入侵开辟了另一条途径，这与传统的基于僵尸网络(botnet-based)的攻击形成鲜明对比。
图 9：application中已识别攻击活动使用的IPv4地址分布
8.2 在恶意账户上的新发现
为了评估 SynchroTrap 发现以前无法检测到的恶意活动的能力，我们将 SynchroTrap 检测到的恶意账户与 Facebook 内部现有方法检测到的恶意账户进行比较。在 Facebook，大量现有方法通过监控某些类型的用户活动的突然变化来应对攻击。在每个部署的application中，将 SynchroTrap 在 2013 年 8 月检测到的帐户与同期其他方法检测到的帐户进行比较。
表 4：SynchroTrap的新发现
因 SynchroTrap 是第一个专门针对 Facebook 中app安装和照片上传的对策尝试，没有可以从以前的工作中获得的数据进行比较。表 4 可以看出，SynchroTrap 识别出大量以前未知的恶意账户。具体来说，在每个application中至少 70% 的已识别帐户未被现有方法发现。相信在更多 OSN 对象（例如浏览器 cookie 的某些字段）上的每个应application中全面部署 SynchroTrap 可以产生更多新发现并实现更高的恶意帐户召回率。特别是，大量以前未被发现的恶意账户表明，松散同步的攻击在现有的对策中被低估了。SynchroTrap 通过有效发现此类攻击来补充现有的 OSN 对策。
8.3 恶意账户的社交连接
基于社交图的防御机制引起了研究界的广泛关注。我们通过将已识别帐户与 SybilRank 生成的排名列表进行比较来检查已识别帐户的社会连接性。SybilRank 可以识别以较低的单户成本创建的批量账户，它根据社交图中的连接程度对用户进行排名，与合法用户的连接有限的可疑用户排名较低。
图 10：检测到的账户相对SybilRank生成的排名百分位的CDF
我们在 2013 年 8 月获得的snapshot of the Facebook friendship graph运行 SybilRank。该社交图包含在本研究之前被现有对策认为是良性的所有 Facebook 用户，不包括在graph snapshot之前已经被现有对策阻止的用户。图 10 显示了 SynchroTrap 在每个 Facebook application中检测到的恶意帐户的排名百分位数的 CDF。可以看出，一定比例的恶意用户（登录时约为40%，其他application中约为15%）排在最后，这部分用户由在社交图谱上几乎没有参与度的虚假账户组成。尽管 SybilRank 对大部分已识别的恶意用户的排名较低（例如在应用安装中检测到的用户中有80%属于最低的25%排名），但不可忽略的一部分用户出现在中间甚至是排名列表的顶部区间，这表明攻击者操纵与合法用户具有不同程度社交联系的帐户。例如，在照片上传中捕获的部分帐户排名靠前，这可能是因为攻击者倾向于使用连接良好的帐户将垃圾照片传播给他们的许多朋友。如第 8.1 节所述，这些连接良好的帐户可以通过恶意软件、社会工程等获得，对社交图谱的潜在影响力以及获取此类帐户的高成本使它们对攻击者更有价值。
8.4 Operation experience
我们对 SynchroTrap 部署后的前 11 周内被 SynchroTrap 捕获的用户数量进行了纵向研究（图 11）。从一开始，Facebook 登录、应用安装和照片上传的变化就很小。相比之下在第一个月后，Facebook 页面喜欢和 Instagram 用户关注项目中检测到的用户数量会减少，然后稳定在每周 100K 左右。我们怀疑这种下降可能是由 SynchroTrap 的部署引起的。攻击者要么无法获得新的受控帐户来发起攻击，要么他们暂时停止攻击以防止其受控帐户被抓获。每个application中检测到的帐户数量稳定表明 SynchroTrap 随着时间的推移继续有效地检测恶意帐户。
图11：SynchroTrap在11周内每周检测到的用户数量
尽管大多数检测到的帐户都是第一次被 SynchroTrap 捕获，但我们观察到其中不可忽略的一部分被反复捕获。图 12 显示了这些用户（至少被抓到两次）的比例。正如我们所见，在每个application中，检测到的用户中有 5%∼15% 被 SynchroTrap 捕获两次；被抓到五次以上的用户比例不到 1%。一些帐户被反复抓获，因为他们能够清除发送给他们的挑战。当检测到恶意帐户时，Facebook 的安全系统会向其发送验证码或短信等挑战。攻击者或受感染帐户的所有者都可以clear掉我们设置的挑战，以便使用这些帐户发起新的攻击。
图 12：被SynchroTrap反复捕获的用户分布
8.5 System performance
我们在 Facebook 的 200 台机器集群上评估了 SynchroTrap 的性能。每个application中的日常活动数据为 TB 级，同时测量了不同参数设置下 SynchroTrap 管道每个阶段的执行时间。
Daily jobs。
在日常工作中，action-matching窗口 Tsim 决定了滑动比较窗口的大小。为了检验其影响，我们将 Tsim 的值从 10 分钟更改为 5 小时。图 13 显示，随着我们将 Tsim 设置为更高的值，日常作业的执行时间会增加。这是因为较高的比较窗口 Tsim 会导致比较更多的用户对。当我们使用重叠的滑动窗口对数据进行分区时，application中的每个日常作业都会在几个小时内完成。
图 13：SynchroTrap的日常作业在不同application中的执行时间，误差线代表 95% 的置信区间。
Aggregation jobs。
图14可以看出，当我们在日常作业中增加 Tsim 时，聚合作业需要更长的时间。这是因为具有较大 Tsim 值的日常作业会生成更多具有匹配操作的用户对，因此会增加聚合时间。在所有application中，每组聚合作业在约 15 小时内完成执行。
图 14：每个application中聚合作业的执行时间
Giraph上的单链接层次聚类
。SynchroTrap 的用户对过滤功能（第 4.4 节）允许不同粒度上的不同相似度阈值。我们使用一周的数据集来检查在不同相似度阈值下聚类的执行时间。为简单起见，我们为所有相似度阈值分配相同的值，并将该值分别设置为 0.2、0.4、0.6 和 0.8。图 15 显示每个application的执行时间随着我们将阈值设置为较低值而增加。这是因为较小的阈值会导致要过滤的用户对较少，从而使用户相似度图更密集。由于 Giraph非常高效，SynchroTrap的clustering job在 100 分钟内即可完成。
图 15：在每个application中查找connected components的执行时间
9. RELATED WORK
在本节中，我们将简要描述以前的 OSN 防御建议，并将它们与这项工作进行比较。我们将先前的工作分为三大类：基于社交图的方法、基于特征的帐户分类和聚合行为聚类。SynchroTrap这项工作属于聚合行为聚类的范畴。
基于社交图的方法使用社交连接来推断与合法用户的社交连接有限的虚假账户，他们可以检测到大量创建的大部分虚假账户，但可能会错过维护良好的虚假账户和被盗账户。
基于特征的账户分类使用各种账户特征来训练分类器来检测恶意账户。例如，Facebook Immune System可以管理许多 Facebook 攻击分类器，COMPA使用捕捉用户行为突然变化的统计模型来识别被盗账户。
Clickstream和CopyCatch开创了OSN用户聚合行为聚类的工作。Clickstream比较来自社交网络帐户的 http 请求的成对相似对，并将具有相似 http 请求模式的帐户聚集起来。它使用预先标记的数据将集群分类为虚假的或合法的，如果集群中预先标记的虚假账户的数量大于某个阈值，则该集群被分类为虚假，否则认为是合法的。虽然 Clickstream 在 16K 人人网络用户的数据集上取得了很好的检测结果，但我们不能直接借用这种方法，主要是因为我们的目标是在更大的OSN部署 SynchroTrap。首先，将大型社交网络中每对用户的所有点击与数亿活跃用户进行比较具有很高挑战性，其次，在大型社交网络上很难获得大量的训练数据，因为它需要昂贵的人工标注成本，许多集群因此可能不包含任何标记数据，不能作预分类。
Facebook 内部系统 CopyCatch 可以检测松散同步的虚假点赞。SynchroTrap 的设计基于类似的洞察力，即恶意账户往往会一起行动，然而，CopyCatch 假设用户只能执行一次恶意操作并将检测问题建模为一个共同聚类问题。当用户可以多次重复相同的恶意操作时，例如从同一个 IP 地址重复登录，CopyCatch 的计算复杂度会随着重复操作的次数呈指数级增长。
相比之下，SynchroTrap 假设恶意账户可以多次重复任何操作，并采用一种聚类算法，其计算复杂度随着账户执行的操作数量线性增长。此外，SynchroTrap 使用源 IP 地址和活动目标来进一步降低其计算复杂性，使其可部署在 Facebook 等大型社交网络上。
除了社交网络防御系统，SynchroTrap 还借鉴了以前关于僵尸网络检测的工作 ，因为一些攻击者使用僵尸网络来控制恶意帐户，特别是BotMiner和 BotSniffer检测以类似方式响应命令的机器人，BotGraph检测由大量垃圾邮件帐户共享的僵尸网络 IP 地址。SynchroTrap 还使用共享 IP 地址作为检测恶意帐户组的信号，但使用用户操作的时间戳来进一步提高检测准确性。
最后，我们注意到 SynchroTrap 的设计使用无监督学习，并且不会实时检测恶意行为。将来，我们可以从它检测到的恶意活动和帐户中提取攻击特征，并使用监督学习来开发可以实时检测攻击的快速分类器。
题图来源：网站Pexels
THE END
阅读原文
声明：文中观点不代表本站立场。本文传送门：https://eyangzhen.com/239563.html
