💻 computer science

TENSURE: Fuzzing Sparse Tensor Compilers (Registered Report)

本文提出了 TENSURE，这是首个专为稀疏张量编译器设计的可扩展黑盒模糊测试框架，它利用爱因斯坦求和表示法作为通用输入抽象，并通过新颖的约束生成算法确保 100% 的语义有效性，从而有效暴露了现有编译器在代码生成阶段的广泛脆弱性。

原作者： Kabilan Mahathevan, Yining Zhang, Muhammad Ali Gulzar, Kirshanthan Sundararajah

发布于 2026-03-20

📖 1 分钟阅读☕ 轻松阅读

原作者： Kabilan Mahathevan, Yining Zhang, Muhammad Ali Gulzar, Kirshanthan Sundararajah

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文介绍了一个名为 TENSURE 的新工具，它就像是一个专门用来“找茬”的智能测试员，专门负责检查一种叫“稀疏张量编译器”（STC）的复杂软件是否靠谱。

为了让你更容易理解，我们可以用几个生活中的比喻来拆解这篇论文的核心内容：

1. 背景：什么是“稀疏张量编译器”？

想象一下，你有一个巨大的图书馆（数据），里面有几亿本书，但其中 99% 的书页都是空白的，只有很少几页写着字。

普通编译器（处理密集数据）：就像是一个笨拙的管理员，不管书有没有字，他都要把每一页都翻一遍，非常慢且浪费力气。
稀疏张量编译器（STC）：就像是一个超级聪明的管理员。他知道哪些书是空的，直接跳过，只去翻那些有字的页面。这样处理速度极快，非常适合现在的 AI 和大数据分析。

但是，这个“超级管理员”太聪明了，他需要自己发明一套极其复杂的规则（代码）来跳过那些空白页。因为规则太复杂、太灵活，很容易在“跳过”的过程中出乱子，导致算错数或者系统崩溃。

2. 问题：以前的测试方法为什么不管用？

以前，人们测试这些编译器就像是在玩“连连看”：

旧方法：测试员手里只有一堆固定的“标准卡片”（比如标准的矩阵乘法、卷积等），他们把这些卡片拼在一起，看看编译器能不能算对。
缺陷：这就像只测试管理员能不能处理“整齐排列”的书架。但现实中的数据是杂乱无章的（稀疏的）。旧方法无法生成那些奇怪、复杂、非标准的“乱序书架”来测试管理员的极限。
结果：很多隐藏的 Bug（比如管理员在跳过空白页时算错了位置）根本发现不了。

3. 解决方案：TENSURE 是怎么工作的？

TENSURE 就像是一个拥有“魔法生成器”的疯狂测试员。它不再依赖固定的卡片，而是直接生成任意形状的复杂任务。

A. 魔法生成器（约束生成算法）

比喻：以前的测试员乱写乱画，写出来的任务书（代码）经常语法错误，被编译器直接扔回来（就像你写了一封语法不通的信，邮局直接拒收）。
TENSURE 的做法：它使用一种智能算法，确保生成的每一个任务书在数学上都是绝对正确的。它就像是一个精通语法的作家，写出来的每一封信都符合逻辑，保证编译器能“读得懂”，从而能真正进入“干活”的环节。
效果：旧方法生成的测试中，只有 3.3% 是有效的；而 TENSURE 生成的 100% 都是有效的。

B. 变形金刚（变异算子）

一旦生成了一个正确的任务，TENSURE 会玩“变形”游戏，看看编译器会不会被绕晕：

交换顺序（代数交换律）：
- 比喻：如果你让管理员先整理 A 书架再整理 B 书架，和先整理 B 再整理 A，结果应该是一样的。TENSURE 故意打乱顺序，看管理员会不会因为顺序变了就算错数。
换装游戏（存储格式异构）：
- 比喻：同样的书，可以按“按作者名字排序”放，也可以按“按颜色排序”放。TENSURE 会突然把书的摆放规则（存储格式）从一种换成另一种，看管理员能不能适应这种变化。如果换了个放法，管理员就崩溃了，说明他太死板，有 Bug。

4. 测试结果：发现了什么？

作者用 TENSURE 测试了两个目前最先进的“超级管理员”（一个叫 TACO，一个叫 Finch）：

TACO 的表现：惨不忍睹。在生成的测试案例中，超过 60% 都导致了系统崩溃或者算错了结果（而且这种算错是静悄悄的，程序没报错，但结果不对，就像管理员偷偷把书放错了位置，你根本发现不了）。
Finch 的表现：虽然运行速度慢，但也发现了不少导致系统崩溃的 Bug。

5. 总结：这篇论文的意义

这篇论文告诉我们：现在的 AI 基础设施（稀疏张量编译器）虽然很强大，但非常脆弱，就像一座看似宏伟但内部有很多裂缝的大厦。

TENSURE 就是那个拿着探照灯，专门去敲裂缝、找隐患的专业质检员。
它证明了，用老办法（只测标准卡片）是测不出来的，必须用这种能生成“任意复杂场景”的新工具，才能确保未来的 AI 系统不会在关键时刻掉链子。

一句话总结：TENSURE 是一个能自动生成“千奇百怪”数学难题的测试机器人，它发现现在的 AI 编译器在处理复杂数据时，经常因为太聪明而把自己绕晕，导致严重的计算错误，我们需要它来给这些编译器“体检”和“排雷”。

1. 研究背景与问题 (Problem)

背景：
稀疏张量编译器（如 TACO, Finch, MLIR Sparse Dialect 等）是优化高维数据分析和机器学习工作负载的关键基础设施。它们负责将高级声明式规范（如 Einstein Summation/Einsum）转换为针对各种压缩存储格式（如 CSR, COO, CSC）优化的底层循环代码。

核心挑战：

极高的复杂性： 与稠密张量不同，稀疏张量编译器需要合成复杂的、不规则的控制流（循环嵌套），以同步访问多个稀疏操作数。这种复杂性使得编译器极易产生微妙的正确性缺陷（如迭代错误、内存安全违规）。
现有测试方法的局限性：
- 基于计算图的模糊测试（如 NNSmith, PolyJuice）： 这些方法依赖固定的算子词汇表（如 MatMul, Conv2d），无法测试编译器合成任意、非标准循环结构的能力。此外，它们缺乏对压缩存储格式表示的支持。
- 通用语法模糊测试（Grammar-based Fuzzing）： 由于 Einsum 语法的索引重用规则是**上下文敏感（Context-Sensitive）**的（例如，输出索引必须是输入索引的子集，且收缩索引必须至少出现两次），标准的上下文无关文法（CFG）模糊器无法生成有效的输入。论文指出，通用模糊器的有效生成率仅为 ~3.3%，绝大多数输入因维度不匹配被拒绝，无法触及核心的循环生成阶段。
- 缺乏专用测试工具： 目前尚无专门针对 STCs 功能正确性的测试框架，导致该生态系统的大部分处于“未测试”状态。

2. 方法论 (Methodology)

TENSURE 是一个可扩展的黑盒模糊测试框架，旨在验证 STCs 的功能正确性。其核心设计包括以下三个部分：

A. 基于约束的生成算法 (Constraint-Based Generation)

为了解决通用模糊器有效率低的问题，TENSURE 放弃了基于 CFG 的随机生成，转而将 Einsum 表达式的生成建模为约束满足问题（Constraint Satisfaction Problem）。

索引连通性： 算法首先从全局索引池中为输入张量分配索引，然后严格检查收缩索引（Contraction Indices）是否至少在两个输入张量中出现。
维度一致性： 确保输出索引是输入索引的子集，并为每个唯一索引分配具体的运行时维度大小，保证生成的张量形状兼容。
结果： 该算法保证了生成的 100% 语义有效性，确保所有生成的测试用例都能通过编译器前端并进入关键的循环降低（Loop Lowering）阶段。

B. 领域特定的变异算子 (Domain-Specific Mutation Operators)

由于 STCs 通常将每个 Einsum 表达式视为独立的宏展开目标，传统的基于控制流（如死代码注入）的变异方法不适用。TENSURE 提出了两种利用代数不变性的变异策略：

代数交换律 (Algebraic Commutativity)： 利用张量乘法在实数域上的交换律（ $A \times B = B \times A$ ），随机打乱操作数的顺序。这会迫使编译器为相同的数学运算生成不同的迭代调度，从而暴露调度逻辑中的缺陷。
存储格式异构性 (Storage Format Heterogeneity)： 利用数学定义与物理布局解耦的特性，随机为输入和输出张量分配不同的压缩存储格式（如 COO, CSR, CSC）。这会迫使编译器合成针对特定格式组合的迭代图，从而检测编译器在处理特定访问模式时的错误。

C. 语言无关的架构 (Language-Agnostic Architecture)

为了应对不同 STC 框架（如 C++ 的 TACO 和 Julia 的 Finch）的语法碎片化问题，TENSURE 设计了一个通用的 JSON 抽象层。

模糊引擎生成包含语义细节（包括存储格式配置）的 JSON 描述。
针对特定编译器的轻量级“翻译器”解析 JSON 并生成对应的 DSL 代码。
这种插件式架构使得 TENSURE 能够轻松扩展至新的编译器后端。

D. 元变测试 (Metamorphic Testing)

由于缺乏可信的参考编译器，TENSURE 采用元变测试策略：

生成一个参考程序（Reference Program）并执行，记录输出作为“真值”。
生成语义等价的变异程序（Mutants）并执行。
比较两者的输出。如果输出不一致（且排除了浮点数精度噪声），则判定为编译器存在**静默错误（Silent Miscompilation）**或崩溃。

3. 主要贡献 (Key Contributions)

首个专用模糊器： 提出了 TENSURE，这是首个专门用于验证稀疏张量编译器功能正确性的语言无关黑盒模糊测试框架。
领域特定变异算子： 定义了利用“存储格式异构性”和“代数交换律”的变异算子，能够在不依赖参考编译器的情况下生成语义等价的测试程序。
约束生成算法： 形式化并实现了一种解决上下文敏感维度约束的生成算法。与基准线（通用语法模糊器）仅 ~3.3% 的有效率相比，TENSURE 实现了 100% 的语义有效性，显著提升了测试吞吐量。

4. 评估结果 (Results)

作者在两个最先进的系统 TACO (C++) 和 Finch (Julia) 上进行了评估：

生成效率对比：
- 在生成 100 万个内核的对比实验中，TENSURE 的约束生成算法保证了 100% 的有效性。
- 基于 Grammarinator 的基准模糊器仅产生了 ~3.3% 的有效内核，其余 96% 以上因维度不匹配被拒绝。
TACO 评估：
- 在 6 小时的模糊测试中，TENSURE 在 267,000 次迭代中发现了大量缺陷。
- 在编译器接受的有效输入中，约 65.2% 的测试用例触发了缺陷。
- 其中，18.6% 被归类为静默错误（Wrong-Code Bugs），即编译器生成了错误的代码但未崩溃，这是最危险的缺陷类型。
- 论文展示了一个具体案例：TACO 在稀疏输出模式下错误地初始化了循环内的坐标跟踪器，导致计算结果错误，而 TENSURE 成功复现了该问题。
Finch 评估：
- 由于 Julia 编译器编译速度较慢（每个内核约 181 秒 vs TACO 的 64 毫秒），6 小时内仅完成了 1,619 次迭代。
- 尽管如此，TENSURE 仍成功发现了 57 个崩溃（Crash）缺陷，证明了框架在不同架构上的可扩展性。

5. 意义与影响 (Significance)

揭示基础设施脆弱性： 研究结果表明，当前的稀疏张量编译基础设施（即使是研究原型如 TACO）存在广泛的脆弱性，极易产生静默错误和崩溃。
填补测试空白： 解决了稀疏张量编译器缺乏专用测试工具的问题，填补了张量编译器生态系统中这一关键的安全与质量缺口。
方法论创新： 证明了在处理具有严格语义约束（如上下文敏感语法）的领域特定语言（DSL）时，基于约束的生成方法远优于传统的语法模糊测试。
未来方向： 该工作为构建更健壮的下一代稀疏计算基础设施提供了必要的验证工具，并指出了未来在浮点数确定性处理、转置变异算子以及集成更多现代框架（如 MLIR Sparse Dialect）方面的改进空间。

总结： TENSURE 通过结合约束满足生成和领域特定的元变测试策略，成功克服了稀疏张量编译器测试的难点，揭示了现有系统中普遍存在的严重缺陷，是该领域自动化测试的重要突破。