Anpoliros
#paper

url redirection chain clustering

developer

Clustering URL addresses based on redirection vector

Disclaimer:
All papers referenced here remain the copyright of their respective authors and publishers. These notes are for personal learning and non-commercial use only. If there is any infringement, please contact me for immediate removal.

4.1 数据收集

数据集基本信息：

  • 来源于一家防病毒公司的标注数据集
  • 总共包含3亿多个URL（300,245,190个）
  • 收集时间：2024年4月21日至5月21日
  • 内容：全球范围内的URL和IP地址，这些地址当前或曾经托管过被公司产品拦截的攻击相关的网页内容
  • 标注：每个最终URL/IP都被公司内部检测系统标记为Clean（干净）或Malicious（恶意）
  • 数据来源于安全事件发生时收集的威胁遥测数据

重定向链生成： 从原始数据集中，生成了45,245,288条URL链（redirection chain），并根据4.3节描述的算法创建了重定向向量。

统计分布：

  • 恶意链：5,623,895条
  • 干净链：39,621,393条
  • 虽然数据看起来不平衡（恶意链只占约12%），但作者强调这反映了真实世界的情况——恶意活动本来就只占网络流量的一小部分

链长度处理：

  • URL链是通过浏览器缓存中的referrer关系重建的
  • 图2展示了不同长度链的频率分布
  • 作者指出链条开头可能包含很通用的网页（如广告平台），这些页面对最终页面的判断意义不大
  • 关键决策：设定最大链长度为7个URL。如果原始链条更长，就删除前面的部分，只保留最后7个节点（因为假设越接近最终页面的跳转越不通用，越有判断价值）

4.2 构建URL重定向图

基本思路： 作者要把URL链条（chains）合并成图（graphs）。如果两条链包含相同或相关的URL，就把它们连接起来形成重定向图。

核心挑战：如何判断两个URL"相等"？

URL可以分解为多个部分：

  • 协议（HTTP/HTTPS）
  • 域名/子域名
  • URL路径
  • URL查询参数及其值

作者发现查询参数的熵值很高（变化很大），会对图的构建产生不利影响，所以决定忽略所有查询参数。

去掉参数后，剩下的部分可以分为：协议、子域名、URL路径。

三种URL等价性定义方案：

  1. 只考虑：协议 + 二级域名 + 顶级域名（最宽松）
  2. 考虑：所有级别域名 + URL路径（中等）
  3. 考虑：协议 + 所有级别域名（包括子域名） + URL路径（最严格、最敏感）

作者的选择：采用第3种方案

  • 理由：同一主机的不同子域名可能托管完全不同的内容
  • URL路径也很重要，因为同一地址下可能有多个网页
  • 攻击者可能利用漏洞在不同路径或子域创建恶意内容或跳转

URL重定向图的结构

两种节点类型：

  1. URL节点：代表一个具体网址
    • 通过有向的HTTP边连接到前后的URL节点
    • 例外：第一个节点没有前驱，最后一个节点没有后继
  2. 文件节点：通过SHA256哈希值标识
    • 代表该URL地址上的网站内容或下载的文件
    • 连接到对应的URL节点

作者还提到，某些URL节点可能涉及浏览器之外的交互（如远程网络连接或API调用），这些信息可用于识别C&C（命令与控制）通信模式。

三种边（关系）类型：

  1. HTTP边：连接两个URL节点，表示重定向链中的路由连接
  2. Download边：连接URL节点和文件节点，表示文件来源
    • 意味着文件存储在该URL或从该URL下载
  3. Remote边：表示与其他网页/URL的交互，但不涉及重定向
    • 情况1：某URL上的JavaScript代码调用另一服务器的API
    • 情况2：JavaScript代码从另一服务器获取视频流

图的构建过程：

  1. 数据集中每条记录转换为重定向链（方法见4.3节）
  2. 将重定向链插入URL重定向图，保持原始重定向关系
  3. 链中的每个项目转换为对应节点类型（URL节点或文件节点）
  4. 根据数据集中的相互重定向关系连接节点

重要说明： 由于数据性质，不能保证所有URL重定向图都合并成一个单一的大图。最终结果可能是多个不相交的URL图，这些独立的图之间不共享任何节点。

4.3 创建重定向向量

构建过程：

第一步：提取节点的边信息

  • 从URL重定向图中提取每个URL节点及其元数据
  • 为每个URL节点获取四种类型的边：
    1. 输入HTTP(s)边的数量
    2. 输入REMOTE边的数量
    3. 输出HTTP(s)边的数量
    4. 输出Download边的数量

这四个数字按固定顺序构成该节点的子向量（subvector）。

边数量的上限设定：

  • 作者将所有边类型的计数上限设为3
  • 理由：提高聚类算法的泛化能力
  • 逻辑：只需要知道节点是否"分发内容"即可区分节点类型（如搜索引擎会有很多HTTP输出边），具体是10条还是100条边的差异不重要

第二步：构建完整的重定向向量

以图1中的URL链为例：

  • 链条：从"Source page 1"到"Landing page 1"，共6个节点
  • 基础向量：6个节点 × 4种边类型 = 24个数字

第三步：添加全局特征 在24个数字后，再添加2个从整条链计算出的数字：

  1. 链中唯一域名的数量
  2. 链中IP地址的数量

最终结果：

  • 总共26个数字（24 + 2）

  • 示例（假设有3个唯一域名和2个IP）：

0010 1010 3110 1230 1110 1100 32
  • 前24个数字：每4个数字代表一个节点的子向量
  • 最后2个数字：3（域名数）和2（IP数）

图3展示了从URL重定向图构建重定向向量的整个过程。

用途： 每条重定向链都会生成一个对应的重定向向量，这些向量将作为聚类方法的输入。聚类的具体描述在第5章讨论。

4.4 节点类型

引入节点类型的原因： 某些网站（如搜索引擎、带广告的网站）会产生大量重定向或URL，导致URL重定向图变得非常复杂难以理解。因此引入节点类型概念，根据节点的输入/输出特征和在图中的位置来定义其行为。

基础节点类型（沿用Zhen[15]的定义）

这些节点仅基于在图中的位置定义，代表每条链的主要高层结构：

  1. Source节点：始终在URL链的开头，没有输入边
  2. Final节点：URL链的最后一个节点，没有输出HTTP(s)边
  3. Redirection节点：位于Source和Final之间，用于重定向到链中的下一个网页

扩展节点类型（本文新定义）

作者扩展了基础类型，以更好地表示威胁行为者使用的URL重定向基础设施和行为。这有助于根据节点行为区分不同场景。例如，只分发单个payload的endpoint节点与分发大量文件的云存储节点有不同的属性。

五种扩展类型：

  1. Gateway节点（网关）
    • 3个或更多HTTP(s)输入边 + 仅1-2个HTTP(s)输出边
    • 场景：不同网站包含各种广告URL，但都重定向到同一两个处理流量的网页
  2. Rotator节点（旋转器/分发器）
    • 1-2个输入HTTP(s)边 + 3个或更多输出HTTP(s)边
    • 例子：搜索引擎或社交网络
    • 特点：人们直接访问（输入边少），但页面包含各种重定向链接（输出边多）
  3. Download节点
    • 包含在页面加载时自动下载的文件
  4. Next content节点
    • 代表数据流（如流媒体视频）或提供API的Web服务
    • 通常托管在不同域名
    • 通过输入Remote边识别
  5. Distributor节点（分发器）
    • 包含多个在页面加载时自动下载的文件
    • 例如：每次加载该URL可能生成唯一的payload下载
    • 当多条涉及该网页的重定向链合并到单个URL图时，会显示出分发多个文件的行为

复合节点类型

单个节点可能表现出不同类型的行为，因此可以通过合并现有节点类型构建复合节点：

  • 例如：

    "download-redirection"节点

    • 行为：先开始下载文件，下载完成后自动重定向流量到下一个网页

  • 其他组合：Gateway-Rotator、Distributor-Gateway-Rotator等

作者提到，使用节点进一步分析TDS（流量分发系统）超出了本文范围，将在未来研究中解决。

图4：数据集中的Top 10节点类型

展示了clean和malicious URL链中最常见的基础和扩展节点类型组合：

Clean链常见类型：

  • Redirector: Download-Gateway-Rotator
  • Final: Download
  • Source: Download等

Malicious链常见类型：

  • Redirector: Gateway-Rotator
  • Final: Next Content
  • Redirector: Rotator
  • Source: Rotator等

可以看出恶意链和干净链在节点类型分布上有明显差异。

4.5 聚类重定向向量

重定向向量的特征：

  • 由整数值组成的向量
  • 大部分值的范围是0到3
  • 例外：最后两位数字（表示链中唯一域名数和IP地址数）可以更大
  • 向量长度可变，取决于URL重定向链的长度
  • 如果需要，可以通过在向量前端或末端填充中性值来对齐到所需长度

整数向量的优势是可以很容易地集成到成熟的聚类方法中。

聚类过程概述

图5展示了聚类架构的高层描述。完整的算法描述将在5.1节提供。

聚类步骤：

  1. 构建URL重定向图
    • 如前所述，构建映射URL之间重定向关系的图
  2. 转换为重定向向量
    • 将每条URL链转换为重定向向量
    • 向量捕获重定向序列及其相关的主要属性
  3. 选择聚类方法
    • 这是关键步骤
    • 选择取决于数据特征和期望结果
    • 使用的聚类算法包括：K-means、层次聚类、DBSCAN等

流程图（图5）：

URL重定向图 → URL链 → 将重定向链插入图 → 从图中获取重定向向量 → 聚类算法 → 创建包含URL的聚类

评估： 每种聚类方法都会产生一组聚类簇。然后根据这些聚类与Gen Digital Inc.（就是提供数据集的那家防病毒公司）提供的信息的一致性来评估聚类效果。

4.6 评估指标

评估标准： 聚类结果可以根据多个标准评估，如聚类数量、聚类中不同URL的数量等。

本研究重点关注与聚类分类相关的指标，主要使用：

  • Silhouette score（轮廓系数）
  • Homogeneity（同质性）
  • 以及两个新定义的指标

聚类的分类定义：

根据URL标签，聚类可以分为三类：

  1. Clean clusters（干净聚类）：只包含干净URL
  2. Malware clusters（恶意聚类）：只包含恶意URL
  3. Mixed clusters（混合聚类）：同时包含两种类型的URL

共享分类的聚类：指只包含一种类型URL的聚类（纯Clean或纯Malware）

为什么不用F1 score？ F1分数更适合分类问题而非聚类评估，因此不使用。

新定义的两个指标：

1. Cluster Accuracy（聚类准确率）

  • 基于聚类的决定性分类（clean或malware）进行评估
  • 当聚类中所有URL共享相同标签时，该聚类被认为是"决定性标记"的
  • 理想的聚类算法应主要生成决定性标记的聚类（全Clean或全Malware）
  • 但要注意：如果算法给每个URL分配独立的聚类，虽然准确率高，但没有实际意义
  • 因此需要结合其他指标综合评估

2. Chain Accuracy（链准确率）

  • 表示URL在不同聚类类别中的分布
  • 与Cluster Accuracy类似，但关注的是聚类中URL的数量，而非聚类的数量
  • 允许基于聚类大小评估聚类影响
  • 聚类的标签会传播到该聚类中的每个URL

Chain Accuracy vs Cluster Accuracy的区别：

  • 如果少数错误分类的聚类包含大量URL，Chain accuracy会比Cluster accuracy低
  • 这说明错误分类对评估的URL有很大影响

例子： 如果聚类结果产生少量聚类，但大部分被分类为Mixed（混合），说明该算法不适合基于重定向向量对URL进行聚类。

Chain Accuracy vs Homogeneity的区别：

  • Chain Accuracy：考虑错误分类聚类的大小，对包含大量错误分类的大聚类更敏感
  • Homogeneity：独立于聚类大小测量标签纯度

具体例子： 考虑一个混合聚类，包含9个恶意URL和1个干净URL：

  • Chain accuracy：认为该聚类中所有10个URL都被错误分类
  • Homogeneity：只认为1个URL被错误分类

Silhouette Coefficient： 实验中将其值从⟨-1, 1⟩映射到0%到100%的百分比范围。