💻 computer science

Chasing Elusive Memory Bugs in GPU Programs

This paper presents SCuBA, a novel compile-time analysis tool that leverages semantic relations between CPU and GPU code and a SAT solver to detect elusive input-dependent and intra-allocation memory safety bugs in GPU programs, outperforming existing runtime techniques like NVIDIA's Compute Sanitizer by identifying all previously missed bugs without false alarms.

Original authors: Anubhab Ghosh, Ajay Nayak, Dhananjay Rao Thallikar Shyam, Arkaprava Basu

Published 2026-01-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Anubhab Ghosh, Ajay Nayak, Dhananjay Rao Thallikar Shyam, Arkaprava Basu

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

Imagine you are a chef running a massive, high-speed kitchen (the GPU). You have a huge pantry (memory) where you store ingredients. The problem is that sometimes, a chef grabs a jar of spices from a shelf that doesn't exist, or they grab a jar from the wrong section of the pantry because they miscounted the shelves. In the world of computer programming, this is called an Out-of-Bounds (OOB) error. It's like reaching for a cookie jar that isn't there; it can crash the whole kitchen or let someone sneak in and steal the silverware (security vulnerabilities).

For years, the way we found these mistakes was like hiring a security guard to watch the kitchen while it was cooking. The guard would only catch a mistake if a chef actually reached for the wrong jar during a specific shift.

The Problem: The "Ghost" Mistakes

The authors of this paper discovered two major problems with this "security guard" approach:

The "Ghost" Mistakes (Input-Dependent OOBs): Imagine a recipe that only goes wrong if you use exactly 3 eggs instead of 4. If the kitchen usually uses 4 eggs, the security guard never sees the mistake. The mistake only happens on rare, specific days. Because the guard only watches what actually happens, these "ghost" mistakes slip right by. The paper found that many real-world programs have these hidden bugs that only appear under very specific, rare conditions.
The "Shared Box" Mistakes (Intra-Allocation OOBs): Imagine the kitchen has one giant, long box of ingredients. The head chef decides to divide this box into three sections: one for flour, one for sugar, and one for salt. The security guard only knows the total size of the box. If a chef grabs a cup of sugar but accidentally reaches too far and grabs salt from the next section, the guard doesn't care! The guard sees the chef is still inside the "Big Box," so they think everything is fine. But inside the box, the chef just ruined the recipe. The paper calls this an "intra-allocation" bug.

The Solution: SCuBA (The Recipe Forensic Analyst)

Instead of hiring a security guard to watch the cooking, the authors built a tool called SCuBA. Think of SCuBA as a super-smart forensic analyst who looks at the recipe book (the source code) before the kitchen even opens.

Here is how SCuBA works, using simple analogies:

Reading the Logic, Not Just Watching: SCuBA doesn't wait for the kitchen to open. It reads the recipe and asks, "If the chef uses any number of eggs (from 1 to a million), is there a scenario where they reach for a jar that doesn't exist?"
The "Math Detective" (SAT Solver): SCuBA uses a special math engine (called a SAT solver) to play out every possible version of the recipe in its head. It checks the relationship between the size of the pantry and the number of chefs working.
- Example: If the recipe says, "The pantry size depends on the number of guests," but the chefs are told to "always grab the 256th jar," SCuBA does the math: "If we only have 10 guests, the pantry is tiny. But the chefs are still trying to grab jar #256. CRASH!"
- It finds the mistake without ever needing to actually cook the meal.
Mapping the "Shared Box": SCuBA also looks closely at how the giant box is divided. It knows, "Ah, the first 10 inches are for flour, the next 10 are for sugar." If the recipe says, "Grab the 15th inch of the sugar section," SCuBA knows that's actually the salt section. It catches the "Shared Box" mistakes that the security guard missed.

The Results

The authors tested SCuBA against the industry standard tool (NVIDIA's Compute Sanitizer), which is like the best security guard currently available.

The Security Guard: Missed 45 different bugs across 20 different programs. It only found bugs when they happened to show up during its watch.
SCuBA: Found all 45 bugs. It didn't miss a single one, and it didn't raise any false alarms (it didn't accuse the chefs of mistakes when they were actually fine).

Why This Matters

The paper claims that by looking at the logic and math of the code before it runs, SCuBA can find "ghost" bugs that are invisible to current tools. It doesn't need to slow down the computer or add special hardware; it just needs to analyze the code like a detective solving a puzzle. This makes software safer and more reliable, ensuring that the "kitchen" doesn't crash just because a specific, rare ingredient was used.

Technical Summary: Chasing Elusive Memory Bugs in GPU Programs

Problem Statement
Memory safety bugs, particularly out-of-bounds (OOB) accesses, remain a critical vulnerability in GPU-accelerated software, threatening both security and reliability. While existing detection tools (e.g., NVIDIA's Compute Sanitizer, cuCatch, GMOD) utilize runtime dynamic analysis to identify OOBs, they suffer from two fundamental limitations:

Input-Dependent OOBs: These bugs manifest only under specific input conditions. Since runtime tools require the bug to actually occur during execution to detect it, they frequently miss these elusive errors if the "right" inputs are not provided during testing.
Intra-Allocation OOBs: In CUDA programs, it is common to logically partition a single memory allocation (especially dynamic shared memory or local memory) into multiple distinct data structures using pointer arithmetic. Existing tools track only the boundaries of the raw memory allocation and are agnostic to these logical partitions. Consequently, they cannot detect when a thread accesses a data structure outside its logical partition but still within the bounds of the parent allocation.

Furthermore, existing software-only tools incur significant runtime performance and memory overheads due to instrumentation, while hardware-assisted solutions require non-standard hardware modifications.

Methodology: SCuBA
The authors propose SCuBA (Static CUDA Bounds Analyzer), a novel compile-time static analysis tool designed to detect both input-dependent and intra-allocation OOBs without runtime overhead or hardware modifications.

Core Insight: The authors observe that in bug-free GPU programs, there exists a semantic relation between the variables determining memory allocation sizes (typically in host/CPU code) and the variables calculating memory access offsets (in GPU kernel code). The absence of such a binding relation indicates a potential OOB.
Static Analysis & IR: SCuBA utilizes the MLIR (Multi-Level Intermediate Representation) framework and the CGeist compiler to translate both host and kernel CUDA code into an intermediate representation. Unlike binary analysis, MLIR retains high-level semantic information, including pointer arithmetic used for logical partitioning.
Constraint Generation:
- Host Analysis: SCuBA constructs Expression Trees (ETs) to model how memory allocation sizes (e.g., cudaMalloc) and thread grid dimensions are derived from input variables.
- Kernel Analysis: It tracks how memory access offsets are calculated using thread identifiers (threadIdx, blockIdx) and analyzes pointer arithmetic to identify logical partitions within shared and local memory.
- Logical Partitioning: For dynamic shared memory, SCuBA tracks the base allocation and the offsets used to carve out sub-structures, calculating the logical size of each partition.
SAT Solving: SCuBA formulates the detection problem as a satisfiability (SAT) problem. It generates constraints representing:
1. CUDA semantics (e.g., thread IDs must be less than grid dimensions).
2. Semantic relations derived from the code (e.g., allocation size equations).
3. The condition for an OOB (offset $\ge$ allocation size).
  The SAT solver (Google OR-Tools) checks if there exists any legal input assignment that satisfies all constraints simultaneously. If a solution exists, an OOB is possible, regardless of whether it has manifested in any specific execution.
Use-After-Free (UAF): The tool also tracks memory lifecycles to detect UAFs by maintaining a set of live allocations and verifying that accesses occur only on valid, non-freed memory.

Key Contributions

Discovery of Elusive Bugs: The authors demonstrate the existence of input-dependent OOBs in widely used open-source CUDA programs and libraries that evade current runtime tools.
Identification of Intra-Allocation OOBs: They identify and define a new class of bugs arising from the logical partitioning of memory allocations, which existing tools cannot detect.
First-of-its-Kind Static Tool: SCuBA is the first tool to combine static analysis with SAT solving to detect these elusive OOBs and intra-allocation errors without runtime overhead or hardware changes.

Results
The authors evaluated SCuBA against a diverse set of 20 workloads, including popular libraries (Kaldi, llm.c), benchmark suites (Rodinia, HeCBench, Indigo), and CUDA samples.

Detection Capability: Compared to NVIDIA's Compute Sanitizer, SCuBA detected 45 OOBs that the sanitizer missed. Specifically, it found 30 previously unreported input-dependent OOBs and 19 intra-allocation OOBs (introduced for testing in programs that were otherwise safe).
Accuracy: SCuBA reported zero false positives and zero false negatives across the evaluated workloads.
Overhead: As a static analysis tool, SCuBA incurs no runtime performance or memory overhead. The analysis time is a one-time compilation cost, ranging from 8 milliseconds to 32 seconds, with the SAT solver being the primary contributor to this time.

Significance
The paper argues that the reliance on runtime dynamic analysis is a fundamental bottleneck in GPU memory safety, as it cannot proactively detect bugs that depend on specific, untested inputs or complex logical memory structures. By shifting to a static analysis approach that leverages semantic relations and SAT solving, SCuBA offers a way to guarantee the absence of these elusive memory safety bugs before deployment. The authors position SCuBA as a necessary evolution in GPU tooling to address the limitations of current industry-standard sanitizers, particularly for safety-critical applications where missing an intermittent bug is unacceptable.

The Problem: The "Ghost" Mistakes

The Solution: SCuBA (The Recipe Forensic Analyst)

The Results

Why This Matters

More like this