MarkUs GC 与 HWASAN/MTE 内存标签组合方案：让 C/C++ 堆 use-after-free 失去可利用性

本文解读 sanitizers 仓库中 MarkUs-GC.md 记录的核心研究思路：如何借助类似垃圾回收（GC）的 quarantine 机制，在不改变 C/C++ 语言语义的前提下，把堆 use-after-free（UAF）漏洞从"可利用"降级为"不可利用"，并进一步论证它与硬件内存标签（Memory Tagging，如 HWASAN、Arm MTE、SPARC ADI）组合后如何大幅降低 GC 扫描频率与性能开销。读完本文，你将理解 MarkUs 的完整工作流程、其已知弱点与开销模型，以及"标签代际复用 + quarantine"这一组合方案为何能把扫描频率降低一个数量级以上，并掌握仓库中可用于观测标签与 shadow 内存的实验工具。

为什么需要 MarkUs：UAF 防御的两条技术路线

传统上，C/C++ 堆 UAF 防御主要走"检测"路线——例如 AddressSanitizer 在内存访问时检查影子内存（shadow memory），一旦命中已释放区域立即报错。但检测路线需要侵入性编译插桩与较大的运行时开销，且只能发现、不能阻止攻击者利用。

MarkUs-GC.md 记录的是另一条路线：让 UAF 不可利用（unexploitable）。MarkUs 论文（MarkUs: Drop-in use-after-free prevention for low-level languages，发表于 IEEE S&P 2020）提出，用类似 GC 的机制保证：一旦 UAF 发生，被访问的一定是 quarantine（隔离区）中的内存，从而让攻击者无法稳定地通过 UAF 读取/改写已释放并重新分配的对象。其核心优势在于：

• 不改变 C/C++ 语义：malloc/free 的行为对用户透明，程序若没有 UAF，加不加 MarkUs 行为完全一致；
• 可"即插即用"（drop-in）部署：对既有代码库改动极小；
• 定位不同：MarkUs 不检测 UAF，它的目标是消除 UAF 的可利用性（exploitability）。

MarkUs GC 工作机制拆解

原文档给出了 MarkUs 的完整流程，其核心是 quarantine（隔离区）+ 类似 GC 的指针可达性扫描：

1. free() 入隔离区：内存块被释放后并不归还给 malloc 的空闲链表，而是先放入 quarantine；
2. 语义不变：从用户视角看，malloc/free 照常工作。没有 UAF 的程序行为与无 MarkUs 时完全相同；一旦真的发生 UAF，访问到的也必然是 quarantine 中的内存；
3. 阈值触发扫描：当 quarantine 大小达到某个阈值时，触发一次类似 GC 的扫描——从存活（live）内存出发标记所有可达指针；
4. 驱逐与回收：将所有未被标记（即不再被任何存活指针引用）的块从 quarantine 中驱逐出去，允许它们被重新分配；仍被标记的块继续留在 quarantine。

这套机制本质上就是"延迟释放 + 保守指针追踪"：quarantine 拉长了释放与可复用之间的时间窗，只有确认没有存活指针引用时，块才真正回到分配器。这与追溯式 GC 的"标记-清除"思想同源，只是作用对象是 C/C++ 堆分配。

MarkUs 的已知弱点

原文档明确指出（并声明该清单远未完整）：在 C/C++ 语境下，MarkUs 存在以下需要单独处理的弱点，但这些弱点并不妨碍它作为"使 UAF 不可利用"这一方向的有趣尝试。

空间错误（Spatial bugs）

MarkUs 完全忽略 C/C++ 中的空间类错误。一个缓冲区溢出（buffer overflow）依然可能越过边界访问到已释放的内存，从而绕开 quarantine 的隔离效果，削弱整个方案的保障强度。

指向末端的指针（Pointers to end）

C++ 允许指针指向分配块"末尾之后"（past-the-end），这类合法指针会让 MarkUs 的效率与有效性下降。原文档给出了完整的攻击示例：

int *p = new int [8];
int *end = p + 8;  // valid C++, points past the end.
somewhere = end;
delete p;
<GC scan kicks in>
last = *(somewhere - 1); // UAF

问题在于：如果堆分配器是**无头（header-less）**的，end 恰好指向另一个堆块（heap chunk）的开头，GC 扫描在遍历存活内存时会把 end 判定为"指向下一个 chunk 的合法指针"，从而误认为 p 仍然可达，于是 p 不会被驱逐出 quarantine——UAF 就此绕过隔离。原文档给出的出路只有两条：要么分配器在各 chunk 之间加 header/redzone（成本较高，但可调），要么接受这类 UAF 会造成 bypass。

指针隐藏（Pointer hiding）

将指针以非标准形式隐藏存储（如编码、异或、拆分存放）会使 GC 扫描无法识别其指向，原文档指出该问题在论文中有充分论述，这里不再展开。

开销模型：GC 扫描的代价与权衡

原文档明确承认 MarkUs 的不利消息：CPU 与 RAM 开销都可能相当可观，并且存在可感知的 GC 停顿（pause）。以下是文档基于实验给出的"手算级"（hand-waving）模型：

• 单次扫描时间与内存足迹成正比：扫描基本可以按"访问 RAM 的速度"完成。一个单线程程序若内存足迹为 1GB，一次 GC 扫描可能造成约 0.1 秒级别的停顿；
• 扫描频率与堆分配速率成正比：程序每秒 malloc 多少字节，直接决定多久需要扫一次。例如每秒堆分配 100MB、quarantine 上限容忍 100MB，则大约每 1 秒就要触发一次 GC 扫描；
• 并行性：GC 一般可以较好地并行化，但通常不是线性加速。

综合起来，原文档给出 MarkUs 的 CPU 开销量级估计：

O(MemoryFootprint * HeapAllocationSpeed / NumberOfThreads)

• RAM 开销由 quarantine 大小决定，用户可将其设置为任意值；
• quarantine 越小，GC 扫描越频繁——也就是 可以用 RAM 换 CPU；
• 若把 quarantine 设为整体内存足迹的固定百分比（而非固定 MB 数），则 CPU 开销可简化为 O(HeapAllocationSpeed / NumberOfThreads)。

这一模型的价值在于：它把 MarkUs 的代价拆成了"停顿长度"与"停顿频率"两个可独立调节的维度，为后文用内存标签压低频率提供了量化基础。

可能的优化方向

原文档列出了三个明确的优化方向：

1. 静态已知安全的分配绕过 quarantine：当某次分配在编译期可判定绝对安全时，不进入隔离区；
2. 用其他机制提供 UAF 安全：例如对超大堆分配，可以改用"保护部分虚拟地址空间"的方式代替 quarantine；
3. 不扫描已知不含指针的分配：例如为 std::string 等对象做的分配，扫描时直接跳过，减少扫描内存量。

MarkUs 与 Memory Tagging 的组合：从"昂贵"到"有竞争力"

这是原文档的核心论点：MarkUs 单独使用通常很昂贵，但与 Memory Tagging 组合后会变得极其有趣且便宜得多。论文作者的原话被完整保留：

... MarkUs composes well with such techniques [memory tagging]. Not only does MarkUs provide the security that tagged memory lacks, and tagged memory the debug that MarkUs does not aim to provide, but tagged memory can also make MarkUs more efficient, by allowing reuse of memory multiple times, based on incrementing the ID tag of each successive allocation, before address space must be quarantined to ensure old IDs have been eliminated and can be reallocated.

即：MarkUs 提供标签内存缺乏的安全性，标签内存提供 MarkUs 不做调试（debug）；而标签还能让 MarkUs 更高效——通过每次分配递增 ID 标签，让同一块地址空间在被 quarantine 之前复用多次。

组合方案：标签代际递增

原文档给出的组合方案适用于大多数内存标签实现（HWASAN、Arm MTE、SPARC ADI），流程如下：

• 每个堆区域首次分配时赋予 tag=0；
• 释放时标签递增：若递增后未溢出，则该块直接返回 malloc 空闲链表，可立即复用；
• 若标签溢出，该块才进入 MarkUs quarantine，等待 GC 扫描确认无存活引用后再被回收。

为什么这样能防 UAF？

原文档给出了代数化的论证：

• 第一次分配（tag=0）：该地址区域从未被使用过，不存在任何 dangling 指针，UAF 不可能发生；
• 第二次分配（tag=1）：可能存在指向同一区域、携带 tag=0 的悬垂指针，但当前分配使用 tag=1，通过旧指针访问会触发内存标签陷阱（memory tagging trap）；
• 第 MaxTag 次分配：此时可能存在 tag 为 0, 1, ..., MaxTag-1 的悬垂指针，但尚不存在 MaxTag 的指针，因此仍然安全；
• 关键点：一旦第 MaxTag 次分配被释放，该指针的全部"代际"（generation）都可能悬垂，此时无法再假设 UAF 安全——这块区域必须进入 quarantine；
• 当 quarantine 达到阈值后运行 GC 扫描，只驱逐那些"所有版本都未在存活内存中被找到"的分配。

也就是说，标签把"每释放一次就要 quarantine 一次"变成了"每释放 MaxTag 次才 quarantine 一次"，quarantine 的需求频率被压缩了整数倍。

量化收益：Arm MTE 使扫描减少 16 倍

Arm MTE 使用 4 位标签（tag 值 0–15），SPARC ADI 同样为 4 位；HWASAN 在 64 位系统上使用指针高 8 位（255 个非零 tag 值）。因此：

• 对 Arm MTE / SPARC ADI：约在第 15 次分配后进入 quarantine，即 MarkUs 只需约 1/16 的扫描次数——原文档明确结论："with e.g. Arm MTE, MarkUs will need 16x fewer scans, which makes MarkUs's performance compelling"；
• 对 HWASAN：约在第 255 次分配后进入 quarantine，扫描频率可相应再降一个数量级以上（可类比推出约 255 倍的减少）。

这让 MarkUs 原本"每秒一次甚至更频繁"的 GC 停顿，变成"每十几秒甚至更久才一次"，性能从不可接受到具有竞争力。

确定性标签分配的副作用：随机化

原文档同时指出了该方案的副作用：这种确定性的标签分配方式，可能削弱内存标签对堆缓冲区溢出的防御效果——因为攻击者可以预测相邻/后续分配的标签。解决方案是：在标签生成过程中引入额外的随机性（即保留代际递增的结构，同时混入随机成分），这也是实际内存标签系统设计时需要权衡的要点。

仓库中的配套实验与工程证据

sanitizers 仓库（该仓库现已归档，核心代码位于 LLVM 中）的 hwaddress-sanitizer 目录下保留了与本主题直接相关的一手实验材料，可用于验证标签机制的实际行为：

观测 MTE 标签：dumptags.cc

dumptags.cc 演示了如何从用户态观测 Arm MTE 实际写入每个内存页的标签：它遍历 /proc 下所有进程，通过 ptrace(PTRACE_PEEKMTETAGS, ...)（见 dumptags.cc 中该命令号的定义）读取每个映射页的 4 位分配标签并落盘。这说明标签确实存在、可被系统调用级读取——这正是"标签代际复用"方案能够成立并接受审计的底层事实。

观测 HWASAN shadow：scan.cc

scan.cc 展示了 HWASAN 影子内存（<a href="https://link.gitcode.com/i/f59454948df24d272c3cca33df4c5e74" target="_blank">anon:low shadow] / [anon:high shadow] 映射，见 [scan.cc）的实际占用测量：通过解析 /proc/<pid>/smaps 与 /proc/<pid>/pagemap，把驻留的 shadow 页映射回用户页并统计各映射的"shadow RSS"。这套工具与 MarkUs 开销模型中的"扫描内存量决定停顿长度"直接相关——shadow 规模即扫描/内存代价的近似度量。

x86 生态：check_registers 与 LAM 的 QEMU 实验环境

标签化不限于 ARM：check_registers 是一套用于检测 x86 各条指令（mov/movaps/call/jmp/ret 等）在带标签指针下行为的汇编测试套件，面向 Intel LAM 与 AMD UAI 的指针标签能力；配套的 run_in_qemu_with_lam.sh 与 create_qemu_image.sh 则演示了如何在完整系统模式的 QEMU 中启用 LAM（-cpu qemu64,+la57,+lam）并运行被测二进制——说明标签技术的验证需要在真实硬件/内核支持下进行。仓库还保留了一组相关演讲稿 PDF 可供深入阅读，例如 MTE-iSecCon-2018.pdf、"Memory tagging in LLVM and Android - LLVM DevMtg 2020.pdf" 与 "Top-byte-ignore and memory tagging: Why would RISC-V care.pdf"。

MTE 的内存成本：动态 tag 存储

部署标签必然有内存代价：mte-dynamic-carveout/spec.md 给出了一个 MTE tag 存储的量化模型——一个 Tag Block 由 32 个数据页加 1 个对应 tag 存储页组成（总开销约 1/33 ≈ 3%），并设计了操作系统在运行时于"带标签/不带标签"freelist 之间动态切换的机制。这与 MarkUs"quarantine 大小可调、用 RAM 换 CPU"的权衡模型互为补充：标签本身的内存开销与 quarantine 的内存开销需要一并纳入工程预算。

结论

MarkUs 的价值在于用"quarantine + GC 式可达性扫描"把 C/C++ 堆 UAF 从"可利用"变为"不可利用"，且不改变语言语义、可低成本部署；它的代价是扫描停顿与 CPU/RAM 开销。而与 HWASAN / Arm MTE / SPARC ADI 等内存标签技术组合后，通过"每次释放递增标签、溢出才进 quarantine"的代际复用方案，Arm MTE 场景下 GC 扫描频率可降低 16 倍、HWASAN 场景下可再降一个数量级以上——这正是原文档"MarkUs sounds interesting, although often costly; combined with Memory Tagging it becomes super interesting and much less costly"这一结论的完整推导过程。仓库中的 dumptags.cc、scan.cc 等实验代码与 MTE-iSecCon-2018.pdf 等资料，为读者自行验证与深入研究提供了可直接复用的起点。