在 LLVM 中对抗 Hyrum 定律

# 在 LLVM 源码中对抗海勒姆定律 来源：https://maskray.me/blog/2026-05-10-fighting-hyrums-law-in-llvm > *对于一个 API 而言，只要用户数量足够多，你在契约中承诺什么都不重要：系统的所有可观察行为都会被某些人依赖。* — 海勒姆定律 (Hyrum's Law) 在编译器中，海勒姆定律最常见的形式是依赖*未指定行为* — 哈希桶顺序、`std::sort` 后相等元素的顺序、填充偏移。同样的框架涵盖了一些技术上是未定义行为的情况（使用失效的迭代器）或纯粹的 incidental 属性（ABI 结构体布局、ELF 段偏移）。当编译器本身存在这种依赖时，症状通常是输出随构建而变化：标准库更改后不稳定排序落在不同位置，哈希函数更改后哈希映射的迭代顺序 shifts。偶尔变化发生在单次构建内的运行之间 — 具有源自 ASLR 种子的 `DenseMap` 键在每次调用时重新排序桶。无论如何，可重现构建、二分排查和错误报告都假设相同输入 → 相同输出，而隐蔽的海勒姆依赖会破坏这一点。本文调查了一些扰动契约盲点的机制，以便依赖无法静默形成。 ## 哈希种子扰动 第一道防线是哈希函数本身。`llvm/include/llvm/ADT/Hashing.h`： ```cpp inline uint64_t get_execution_seed() { #if LLVM_ENABLE_ABI_BREAKING_CHECKS return static_cast<uint64_t>( reinterpret_cast<uintptr_t>(&install_fatal_error_handler)); #else return 0xff51afd7ed558ccdULL; #endif } ``` 异或到每个 `llvm::hash_value` 中的种子是 `install_fatal_error_handler` 的运行时地址 — 在 ASLR 下，每个进程都不同。头部注释明确说明： > *种子是每个进程非确定性的（LLVMSupport 中函数的地址），以防止用户依赖特定的哈希值。* 每次 `hash_combine`/`hash_integer_value` 调用都会获取种子，每个由使用 `hash_value` 的类型键控的 `DenseMap` 随后会在每次运行时重新排序其桶。MD5, BLAKE3, SHA1, SHA256 保持字节稳定 — 当你确实想要摘要时，这些是正确的工具。我的提交 `ce80c80dca45` (https://github.com/llvm/llvm-project/commit/ce80c80dca45) 于 2024 年引入了该种子。 ## 容器迭代顺序 代码可能会对迭代顺序产生依赖。`LLVM_ENABLE_REVERSE_ITERATION` 反向遍历哈希容器以标记违规行为。`llvm/include/llvm/Support/ReverseIteration.h`： ```cpp template <typename T> constexpr bool shouldReverseIterate() { #if LLVM_ENABLE_REVERSE_ITERATION return detail::IsPointerLike<T>::value; #else return false; #endif } ``` `DenseMap` 将其 `BucketItTy` 翻转为 `std::reverse_iterator`；`SmallPtrSet` 交换 `begin()` 和 `end()`；`StringMap` 在桶选择前对哈希进行按位非操作 — 这是唯一扰动 `StringMap` 的东西，因为其哈希绕过了 `get_execution_seed`。与哈希种子不同，反向迭代不会随断言自动开启；`-DLLVM_REVERSE_ITERATION=ON` 显式启用。2026 年已经合并了由其触发的修复：`7f703cabf728` (https://github.com/llvm/llvm-project/commit/7f703cabf728)（MLIR SSA 值完成顺序）、`0b3afd35c41d` (https://github.com/llvm/llvm-project/commit/0b3afd35c41d)（MLIR SROA alloca 顺序）和 `f5e2c5ddcec7` (https://github.com/llvm/llvm-project/commit/f5e2c5ddcec7)（一个 clang 测试）。 ## 迭代器失效 与迭代顺序正交：突变后现有迭代器会发生什么。`llvm/include/llvm/ADT/EpochTracker.h`： ```cpp class DebugEpochBase { uint64_t Epoch = 0; public: void incrementEpoch() { ++Epoch; } ~DebugEpochBase() { incrementEpoch(); } class HandleBase { bool isHandleInSync() const { return *EpochAddress == EpochAtCreation; } }; }; ``` `DenseMap` 及其友元继承自 `DebugEpochBase`。突变会增加 epoch；迭代器在构造时捕获它，并在不匹配时断言。析构函数也会增加 epoch，因此指向已销毁容器的陈旧迭代器会断言，而不是读取已释放内存。没有它，迭代期间突变“碰巧有效”，取决于桶布局 — 而桶布局正是上述哈希种子和反向迭代所扰动的。epoch 检查将潜在 bug 转变为干净的断言，无论运行落在哪个“幸运”布局上。在 `NDEBUG` 下折叠为无操作。 ## 预洗牌不稳定排序 相同的防御模式在 monorepo 中出现了两次，在不同的子项目中，相隔数年。 ### `EXPENSIVE_CHECKS` 下的 `llvm::sort` `llvm/include/llvm/ADT/STLExtras.h`： ```cpp #ifdef EXPENSIVE_CHECKS namespace detail { inline unsigned presortShuffleEntropy() { static unsigned Result(std::random_device{}()); return Result; } template <typename IteratorTy> inline void presortShuffle(IteratorTy Start, IteratorTy End) { std::mt19937 Generator(presortShuffleEntropy()); llvm::shuffle(Start, End, Generator); } } // end namespace detail #endif template <typename IteratorTy, typename Compare> inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) { #ifdef EXPENSIVE_CHECKS detail::presortShuffle(Start, End); #endif std::sort(Start, End, Comp); } ``` `std::sort` 和 `qsort` 是不稳定的；观察相等元素顺序的代码依赖于未记录的行为。预洗牌使该观察每次运行都不同。提交 `5a3d47fabcb6` (https://github.com/llvm/llvm-project/commit/5a3d47fabcb6) 于 2018 年添加了该包装器，动机是 PR35135 (https://bugs.llvm.org/show_bug.cgi?id=35135)。LLVM 还发布了自己的 `llvm::shuffle` 而不是调用 `std::shuffle`，"*以便 LLVM 在使用不同标准库时表现一致。*"一个可重现性取决于宿主 stdlib 的可重现性工具比没有工具更糟 — 而下方的链接器部分依赖于这一点。`llvm::stable_sort` 故意不预洗牌；它是确实需要相等元素排序的代码的显式启用。 ### libc++ `_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY` libc++ 有一个近乎完美的并行机制，专为下游用户设计，而非项目内部。`libcxx/include/__debug_utils/randomize_range.h`： ```cpp template <class _Iterator, class _Sentinel> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void __debug_randomize_range(_Iterator __first, _Sentinel __last) { #ifdef _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY if (!__libcpp_is_constant_evaluated()) std::__shuffle<_AlgPolicy>(__first, __last, __libcpp_debug_randomizer()); #else (void)__first; (void)__last; #endif } ``` 三个调用点： - `std::sort` — 预洗牌输入。 - `std::partial_sort` — 预洗牌输入*并*随后重新洗牌未排序的尾部。 - `std::nth_element` — 预洗牌，然后重新洗牌分区的每一侧。 种子处理与 `get_execution_seed` 类似：ASLR 或静态 `std::random_device` 用于每进程变化，并使用 `_LIBCPP_RANDOMIZE_UNSPECIFIED_STABILITY_SEED=` 作为固定种子逃生舱。默认关闭；仅限 C++11 及更高版本。`libcxx/docs/DesignDocs/UnspecifiedBehaviorRandomization.rst` 解释了动机： > *Google 测量了数千个测试依赖于排序和选择算法的稳定性。由于我们也计划更新（或至少，在标志下提供更多）排序算法，这项工作有助于逐步且可持续地进行。* 它引用了 PR20837 (https://llvm.org/PR20837) — 一个最坏情况 `O(n2)` 的 `std::sort` — 作为 libc++ 特别希望发布的升级。洗牌是 gating 工具：如果下游测试在启用它时通过，它们在算法更改后也会通过。比较两者比单独看任何一个更有趣： - `llvm::sort` 的包装器是内部卫生：LLVM 是其自己的主要用户，因此洗牌位于构建标志后的 `STLExtras.h` 中且无文档。 - libc++ 的包装器是面向用户的 — `DesignDocs/` 页面、公共宏、公共种子覆盖、显式的 "Patches welcome." 邀请。必须如此：libc++ 的用户不是 libc++，且被防御的契约是 C++ 标准本身。 - libc++ 泛化了原语：`__debug_randomize_range` 应用于三个调用点，每个都声明算法留下未指定的子范围。LLVM 的包装器仅覆盖更简单的相等元素情况。 - 哈希容器 — `std::unordered_*` 迭代顺序 — 在两者中均未指定，但 libc++ 不随机化它们。LLVM 库确实如此；在这一表面上 LLVM 领先于其自己的 stdlib。 ## 链接器输出：`--shuffle-sections` 和 `--randomize-section-padding` 两个仅 ELF 的 lld 旋钮扰动契约未覆盖的布局细节。 ### `--shuffle-sections=<pattern>=<seed>` `lld/ELF/Writer.cpp`： ```cpp for (const auto &patAndSeed : ctx.arg.shuffleSections) { ... const uint32_t seed = patAndSeed.second; if (seed == UINT32_MAX) { std::reverse(matched.begin(), matched.end()); } else { std::mt19937 g(seed ? seed : std::random_device()()); llvm::shuffle(matched.begin(), matched.end(), g); } } ``` 一个选项中的三种模式： - `seed = -1` — 确定性反向，即使出现新段也稳定。Glob `\.init_array\*` 到 `-1`，重建，运行测试套件：任何破坏的都是真正的静态初始化顺序 bug。一个标志，无需 Frankenstein 链接脚本。 - `seed > 0` — 确定性随机洗牌，跨运行和主机可重现（因为 `llvm::shuffle` 与主机无关）。在 CI 中很有用，不会破坏二分排查。 - `seed = 0` — `std::random_device()` 种子。每次链接都是新的非确定性。 历史：`423cb321dfae` (https://github.com/llvm/llvm-project/commit/423cb321dfae) 引入了 `=-1` 反向模式；`16c30c3c23ef` (https://github.com/llvm/llvm-project/commit/16c30c3c23ef) 泛化为每 glob 种子，这使得 `\.init_array*=-1` 方案成为可能；`c135a68d426f` (https://github.com/llvm/llvm-project/commit/c135a68d426f) 修复了一个 bug，该功能本身产生了无效的动态重定位顺序 — 即使海勒姆缓解措施也有正确性陷阱。 ### `--randomize-section-padding=<seed>` 姐妹选项通过在输入段之间和段起点插入填充来扰动段*偏移*（`lld/ELF/Writer.cpp`）： ```cpp static void randomizeSectionPadding(Ctx &ctx) { std::mt19937 g(*ctx.arg.randomizeSectionPadding); } ``` 调用者会对链接器从未承诺的填充导致的偏移产生依赖 — profile 引导的流水线、侧信道研究、固定到特定地址的利用工具链。种子扰动使这些依赖可见。两个选项都仅限 ELF；MachO 和 COFF 端口没有等效项。 ## ABI 破坏检测 `llvm/include/llvm/Config/abi-breaking.h.cmake`： ```cpp #if LLVM_ENABLE_ABI_BREAKING_CHECKS ABI_BREAKING_EXPORT_ABI extern int EnableABIBreakingChecks; LLVM_HIDDEN_VISIBILITY __attribute__((weak)) int *VerifyEnableABIBreakingChecks = &EnableABIBreakingChecks; #else ABI_BREAKING_EXPORT_ABI extern int DisableABIBreakingChecks; ... #endif ``` 每个包含头文件的 TU 根据其自身的构建标志对 `EnableABIBreakingChecks` 或 `DisableABIBreakingChecks` 采取弱引用。将两者与同一个 `libLLVM` 混合会在链接时产生未解析符号。MSVC 通过 `#pragma detect_mismatch` 获得相同的保证。树外用户通常针对一个树的头文件编译，并链接到不同的 `libLLVM`。没有这个门，链接碰巧选择的任何结构体布局都会静默错误编译；有了它，链接会失败。 ## LLVM *没有* 做什么 上述机制都针对稳定消费者不应关心的表面：桶顺序、相等元素排序顺序、init-array 顺序。调试器、性能分析器、sanitizer 和可重现构建基础设施消费这些输出并需要它们稳定。在某些情况下，更强的保证仅通过显式选项提供。例如，Bitcode 和文本 IR 仅在 `-preserve-bc-uselistorder`/`-preserve-ll-uselistorder` 下保留使用列表顺序。一个近亲：clang 的 `-frandomize-layout-seed`/`__attribute__((randomize_layout))`。机制上相同 — 对结构体字段进行种子 `std::shuffle` — 它确实偶然使 `offsetof` 依赖失效。但意图是漏洞利用缓解，借鉴自 GrSecurity 的 Randstruct GCC 插件：每构建一次的内核硬化，而非开发者工具。