💻 computer science

TENSURE: Fuzzing Sparse Tensor Compilers (Registered Report)

This paper introduces TENSURE, the first black-box fuzzing framework for Sparse Tensor Compilers that utilizes Einstein Summation notation and a novel constraint-based generation algorithm to produce semantically valid test cases, effectively uncovering widespread correctness defects in systems like TACO and Finch that existing testing methods fail to detect.

Original authors: Kabilan Mahathevan, Yining Zhang, Muhammad Ali Gulzar, Kirshanthan Sundararajah

Published 2026-03-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kabilan Mahathevan, Yining Zhang, Muhammad Ali Gulzar, Kirshanthan Sundararajah

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Sparse" Problem

Imagine you have a massive spreadsheet representing a social network. Most people don't know each other, so 99.9% of the cells in that spreadsheet are empty (zero). If you try to process this spreadsheet like a normal one, you waste a huge amount of time and energy checking empty boxes.

To fix this, computer scientists use Sparse Tensor Compilers (STCs). Think of these compilers as super-smart chefs. Instead of cooking every single ingredient in a giant pot, they look at the recipe, realize most ingredients are missing, and create a custom, highly efficient cooking plan that only touches the ingredients that actually exist.

The Problem: These "chefs" are incredibly complex. They have to invent new ways to cook on the fly for every different type of missing data. Because they are so complex, they often make subtle mistakes. Sometimes they crash the kitchen; other times, they silently serve you a dish that looks right but tastes wrong (a "silent miscompilation").

The Missing Tool: Why We Needed TENSURE

Until now, there was no good way to test these chefs.

Old Testers: Previous testing tools were like menu checkers. They only tested standard dishes (like "Matrix Multiplication" or "Convolution") using a fixed list of ingredients. They couldn't handle the weird, custom recipes these compilers were supposed to invent.
Grammar Fuzzers: Other tools tried to throw random words at the compiler to see if it broke. But because the rules for these recipes are so strict (like a complex math puzzle), 97% of the random attempts were nonsense that the compiler immediately rejected. It was like trying to teach a dog to speak by shouting random letters; it just doesn't work.

The Solution: Introducing TENSURE

The researchers built TENSURE, a new testing robot designed specifically to break these "sparse chefs."

Here is how it works, using three main tricks:

1. The "Universal Recipe Book" (Einsum)

Instead of trying to speak every specific language the chefs use (C++, Julia, etc.), TENSURE speaks a universal math language called Einsum.

Analogy: Imagine you want to test a bunch of different car engines. Instead of trying to write a manual for every specific brand, you write a generic instruction: "Turn the key, press the gas, and see if it moves." TENSURE writes these generic math instructions, which it then translates into whatever specific language the target compiler understands.

2. The "Smart Generator" (Constraint-Based)

This is TENSURE's superpower. Instead of throwing random letters at the compiler, it uses a logic puzzle solver.

Analogy: If you ask a random person to write a sentence, they might say, "The blue apple flew." That's grammatically okay but nonsense. TENSURE is like a strict editor that ensures every sentence it writes is not just grammatically correct, but logically sound.
The Result: While old tools wasted 97% of their time making nonsense, TENSURE generates 100% valid recipes. This means it spends all its time actually testing the cooking process, not just checking if the ingredients list makes sense.

3. The "Magic Mirror" (Metamorphic Testing)

How do you know if the chef made a mistake if you don't have the "correct" answer to compare it to? TENSURE uses Metamorphic Testing.

Analogy: Imagine you order a sandwich.
1. You ask the chef to make a sandwich with ham and cheese.
2. Then, you ask the chef to make the exact same sandwich, but with the order of ingredients swapped (cheese and ham) or with the bread sliced differently.
3. The Rule: Mathematically, the sandwich should taste exactly the same.
4. The Test: If the two sandwiches taste different, the chef is lying or making a mistake.
TENSURE does this by swapping the order of math operations or changing how data is stored (e.g., from "row-by-row" to "column-by-column"). If the computer gives two different answers for the same math problem, it has found a bug.

What Did They Find?

The researchers tested TENSURE on two real-world "chefs": TACO and Finch.

The Results: It was a disaster for the compilers (in a good way for the researchers).
- TACO: The fuzzer found that 65% of the time, the compiler either crashed or gave the wrong answer. It was like finding out the chef burned the kitchen or served raw chicken in 6 out of 10 attempts.
- Finch: It also found many crashes, proving that even newer systems are fragile.

Why This Matters

This paper shows that the tools we rely on to run AI and big data are currently very fragile. They are full of hidden traps that only appear when you try to do complex, weird math.

TENSURE is the first tool that can systematically hunt for these traps. By using smart logic to generate valid tests and "magic mirror" tricks to spot errors, it helps ensure that the next generation of AI and scientific computing tools won't silently fail when we need them most.

In short: TENSURE is a specialized "bug hunter" that speaks the language of math, creates perfect test cases, and tricks compilers into revealing their mistakes before they cause real-world problems.

1. Problem Statement

Sparse Tensor Compilers (STCs) are critical infrastructure for optimizing high-dimensional data analytics and machine learning workloads by generating code directly from high-level declarative specifications (e.g., Einstein Summation or Einsum) for various compressed storage formats (e.g., CSR, COO, CSC). However, STCs face unique challenges that make them highly susceptible to subtle correctness defects:

Complex Control Flow Synthesis: Unlike dense compilers, STCs must synthesize complex, irregular loop nests to handle sparse data access patterns. These loops are generated during compilation rather than being explicit in the source code.
Inapplicability of Existing Tools:
- Computation Graph Fuzzers: Tools like NNSmith and PolyJuice rely on mutating fixed operator graphs (e.g., MatMul, Conv2d). They fail to stress-test the arbitrary loop synthesis capabilities of STCs and lack representations for compressed storage formats.
- Grammar-Based Fuzzers: Generic tools (e.g., Grammarinator) struggle because valid Einsum expressions are Context-Sensitive. They require strict constraints on index reuse and dimensional consistency across tensors, which Context-Free Grammars cannot enforce. This leads to extremely low validity rates (approx. 3.3%) and wasted fuzzing budget.
- Mutation Limitations: Traditional metamorphic testing relies on mutating imperative control structures (loops, if-blocks). Since STCs operate on declarative specifications where control flow is synthesized, these standard mutations are inapplicable.

2. Methodology: TENSURE

TENSURE is the first extensible, black-box fuzzing framework designed specifically for STCs. It employs a metamorphic testing approach, generating semantically equivalent program variants to detect discrepancies without a trusted reference compiler.

A. Constraint-Based Generation Algorithm

Instead of using random walks over a grammar, TENSURE treats kernel generation as a Constraint Satisfaction Problem (CSP).

Input: A pool of index labels, a maximum tensor rank, and a number of input tensors.
Process:
1. Index Assignment: Randomly assigns indices to input tensors while enforcing a maximum rank.
2. Contraction Validation: Ensures that any index used for contraction (reduction) appears in at least two input tensors. If an index appears only once, it is injected into another tensor to satisfy semantic rules.
3. Dimensional Consistency: Assigns concrete integer dimensions to abstract indices, propagating these sizes to ensure all tensor shapes are compatible for the specified contraction.
Outcome: This algorithm guarantees 100% semantic validity of the generated Einsum expressions, ensuring they pass the compiler frontend and reach the critical loop-lowering phases.

B. Domain-Specific Mutation Operators

To generate semantically equivalent variants for metamorphic testing, TENSURE introduces two novel operators that exploit the mathematical properties of tensor algebra:

Algebraic Commutativity: Since tensor multiplication is commutative (assuming real numbers), TENSURE permutes the order of operands in the Einsum expression (e.g., $A = B \times C$ becomes $A = C \times B$ ). This forces the compiler to generate different iteration schedules for the same mathematical operation.
Storage Format Heterogeneity: The mathematical definition of a kernel is independent of its physical storage layout. TENSURE randomly assigns different compressed formats (e.g., CSR, CSC, COO) to input and output tensors. This forces the compiler to synthesize unique iteration graphs and loop nests for every format combination. Any divergence in output indicates a bug in handling specific access patterns.

C. Language-Agnostic Architecture

To bridge the syntactic fragmentation between different STCs (e.g., C++-based TACO vs. Julia-based Finch), TENSURE uses a JSON abstraction layer.

The core fuzzer generates a JSON representation of the kernel, including tensor shapes, indices, and storage format configurations.
A lightweight, compiler-specific translator parses this JSON and emits the corresponding domain-specific code.
The fuzzer acts as an oracle: it executes a reference program, then executes mutated variants, and compares the outputs. Discrepancies trigger bug reports.

3. Key Contributions

First STC Fuzzer: TENSURE is the first language-agnostic, black-box fuzzing framework specifically designed to validate the functional correctness of Sparse Tensor Compilers.
Novel Mutation Strategies: It defines mutation operators based on Storage Format Heterogeneity and Algebraic Commutativity, enabling the generation of semantically equivalent programs without relying on imperative code rewriting.
Constraint-Based Generation: It formalizes an algorithm that solves context-sensitive dimensional constraints to synthesize Einsum expressions, achieving a 100% validity rate compared to the ~3.3% rate of baseline grammar fuzzers.

4. Results

The framework was evaluated on two state-of-the-art systems: TACO (C++ based) and Finch (Julia based).

Generation Efficiency: In a comparative study of 1 million kernels, the constraint-based generator achieved 100% validity, while the grammar-based baseline (Grammarinator) achieved only ~3.3%.
TACO Evaluation:
- Over a 6-hour campaign, TENSURE executed 267,000 iterations.
- It exposed defects in approximately 65.2% of accepted inputs.
- Crucially, 18.6% of failures were silent miscompilations (wrong code bugs) where the compiler generated incorrect code without crashing.
- Total bugs found: 5,758 (including crashes and silent errors).
Finch Evaluation:
- Due to high compilation latency (181s per kernel vs. 64ms for TACO), only 1,619 iterations were completed in the same timeframe.
- Despite the low throughput, TENSURE identified 57 crash bugs, validating its ability to stress-test the Julia-based infrastructure.
Bug Characteristics: The evaluation revealed that STCs are highly fragile, particularly in handling loop initialization and coordinate tracking for sparse iterations (e.g., a specific bug where a coordinate tracker was not reset inside a loop, leading to incorrect results).

5. Significance

Filling a Critical Gap: Prior to TENSURE, a significant portion of the sparse tensor compiler ecosystem remained untested due to the inapplicability of existing testing tools.
Revealing Latent Defects: The discovery of widespread silent miscompilations highlights that current STCs are not production-ready and rely on implicit trust from developers.
Scalability and Extensibility: The JSON-based abstraction layer allows TENSURE to be easily adapted to new compilers (e.g., MLIR Sparse Dialect, PyTorch Sparse) without rewriting the core fuzzing engine.
Methodological Shift: The paper demonstrates that for declarative, constraint-heavy domains like sparse compilation, constraint-based generation is superior to grammar-based fuzzing, and semantic-preserving mutations (commutativity/format changes) are more effective than traditional control-flow mutations.

In conclusion, TENSURE provides a robust, automated solution to verify the correctness of sparse tensor compilers, uncovering critical defects that threaten the reliability of next-generation machine learning and scientific computing infrastructure.