Why Validity Is a Throughput Feature
The key design question for FuzzGPU is not how to produce more GPU instructions; it is how to produce longer executions that still obey the target's SIMT rules. This chapter follows the framework's generator as it separates global coordination from per-warp control flow, then adds planned synchronization and tracked memory uncertainty. The payoff is a useful way to judge a test: validity matters because every stalled or abandoned instruction is part of the fuzzing budget that never reaches the hardware behavior under study.
A generator with two levels
A flat random generator sees a large instruction space. FuzzGPU instead starts by deciding what kind of parallel program it wants to build. Its top-level loop plans the overall structure—multiple cooperative thread arrays, multiple warps, synchronization points, and opportunities for memory interference. Its lower-level loop then emits the instruction stream for each warp. This division mirrors the target: one part manages relationships among work units, while another constructs the control flow of a single warp.
The distinction is more than a software-organization choice. A top-level planner can decide which warps must interact before any one warp emits instructions. A per-warp generator can then focus on making a particular stream executable under its own thread masks and reconvergence rules. If one flat loop made both decisions at once, a local branch choice could silently invalidate a global barrier, or a global synchronization goal could force a per-warp stream into an unreachable path.
The per-warp stream is assembled from basic blocks. A basic block is a straight-line sequence with one entry and one exit, ending at a control-flow transfer. FuzzGPU allocates separate regions for blocks and connects them into a control-flow graph. Within each block it samples instructions and operands according to the target instruction set, while respecting data-flow and control-flow constraints. Memory operations receive addresses from a randomized allocator so that reads are initialized and stores do not overwrite code or read-only regions.
This structure provides a boundary between variety and validity. The generator can randomize arithmetic, loads, stores, and other operations inside a block, but it does not randomize the existence of the block's entry, exit, or data dependencies without constraint. An instruction can be surprising while the path that reaches it remains well-defined. That is exactly the kind of complexity a hardware fuzzer needs: enough variation to activate different logic, but not so much structural noise that the test ends before the variation matters.
Following divergence without losing the path
A warp has one generation program counter while its threads are converged. A branch can create several feasible program counters once different threads take different paths. Emitting both directions naively causes two problems. It can spend the instruction budget on code that no active thread will ever reach, and it can create an expanding collection of paths as branch depth grows. Emitting only one direction is the opposite mistake: some threads may never reconverge, so the test loses part of the warp permanently.
FuzzGPU's generation stack adapts the machine's SIMT idea to program construction. When the generator samples a branch, it uses an instruction-set simulator, or ISS, to predict the next mask for each thread. If both paths have active threads, it stores the branch metadata—including the current program counter, active mask, deferred path, and reconvergence state—on the stack. It then generates one path, typically depth-first. When that path reaches its reconvergence instruction, the generator returns to the deferred path and later closes the stack entry when the threads have fully joined.
The stack does not execute the program; the ISS supplies the runtime context needed to make generation decisions. That separation matters. The ISS can answer which threads would be active after a candidate branch, while the generator decides how much code to emit and where to place the reconvergence. The resulting linearized order is a construction order in which each emitted instruction will eventually be encountered under a defined thread mask. It is not a claim that all physical hardware events will occur in that same order.
A small example makes the benefit concrete. Suppose a warp reaches branch A with all threads active. One path is favored because it contains more active threads, but the other path is saved on the stack. The generator follows the first path until join point G. If a nested branch splits that path, the same process pushes another entry. When the inner paths reconverge, the generator resumes the pending outer path. Once both outer paths reach G, it pops the first entry and continues after the join. This recursive bookkeeping lets the generator explore divergent behavior while retaining a finite, interpretable order for the emitted stream.
The paper identifies three benefits. First, using the ISS during generation supplies branch outcomes and lets the procedure bootstrap from runtime context. Second, maintaining one linearized generation counter avoids a separate program counter for every feasible path, which would magnify path explosion. Third, the order contains no unreachable dead code in the relevant thread-mask sense. That last property is especially important for later synchronization and memory analysis: a barrier or a memory access can be reasoned about as part of a path that active threads will actually encounter.
The diagram also shows why the top-level and per-warp loops cannot be collapsed without losing meaning. The per-warp generator owns the active masks and generation stack. The top-level loop owns when another warp should be considered and which global synchronization or memory relationship is being constructed. The taint state crosses the boundary only to record uncertainty that may affect later instructions. Each part has a different trigger for pausing and resuming.
Planning barriers and memory uncertainty
Control-flow validity alone does not make a multi-warp test executable. FuzzGPU's top-level loop also plans barriers before the individual warps reach them. The planner creates a global sequence of barrier records. Each record has a matching identifier and a participant scope. During per-warp generation, a warp consumes the next record that includes it and emits the barrier only when the planned sequence allows it. Once all participants have emitted that record, it is removed and the next one becomes available.
This ordered skeleton prevents a particular class of circular wait. If warp 0 independently chooses barrier B1 while warp 1 chooses B2, and each barrier expects the other warp, both can stop forever. With a common sequence, participating warps encounter barrier IDs in a consistent order. The paper formalizes this with program order within each warp and a group-barrier happens-before relation across the participants. It proves the planner deadlock-free under that model because moving across a group barrier advances a rank, while ordinary program-order edges do not reverse it.
The guarantee is deliberately bounded. Vortex supports global and CTA barrier scopes in the study, while OpenGPGPU supports CTA scope; the planner chooses only scopes that the target provides. The proof concerns deadlocks caused by the generated barrier ordering. It does not prove that every possible instruction sequence is free of hardware hangs, nor does it eliminate bugs in a target's instruction cache or writeback logic. A safe generator can still expose a later microarchitectural defect, which is part of the method's purpose.
The planner's role is therefore different from the generation stack's role. The stack makes a single warp's divergent control flow reach its joins. The planner makes the participating warps see synchronization in a compatible order. One is a local path discipline; the other is a global liveness discipline. Treating them as separate mechanisms lets the evaluation ask what each contributes instead of attributing every improvement to an undifferentiated notion of structure.
Creating useful memory interactions
FuzzGPU does not avoid shared-memory interaction just because it is difficult to compare. Cross-thread loads and stores are precisely where a GPU's relaxed behavior can reveal bugs. The generator interleaves the construction of different warps. When the current warp reaches a memory instruction, it records the effective address and operands and pauses so another warp can contribute its own operation. Once the relevant generations have paused, the framework can identify addresses that another thread has written or will write.
To increase the chance of such conflicts, it keeps a short history of recent memory addresses and reuses one when constructing a new address. The current base register and an immediate offset are chosen so that the new operation collides with a previously observed address when the candidate remains legal. This is targeted stress, not an arbitrary aliasing fault. The generator is trying to create the shared locations where ordering rules matter while retaining valid alignment and address constraints.
A conflict creates uncertainty that can propagate. Under relaxed memory consistency, a load may legally observe different writes depending on when those writes become visible. If the generator treated the resulting value as an ordinary deterministic result, it could cause every dependent instruction to look wrong. FuzzGPU instead maintains taint metadata alongside the generated program. A register with a tainted source becomes tainted when an instruction depends on it; a store with tainted data or an address taints the affected memory location; and a load from a tainted address taints its destination.
The metadata is maintained by the generator as software state; the paper says it requires no change to the GPU RTL. That is an important engineering boundary. The target is not being modified to explain its own behavior. The generator is recording where the later comparison needs to be less literal. A tainted value can still influence branches, addresses, or further arithmetic, so the generator also resamples operands when needed to keep addresses legal and control flow synchronized enough to continue.
Taint can serve two purposes at once. During construction, it identifies uncertainty and helps avoid combinations that would make the rest of the test uninterpretable. During differential checking, it marks loads whose values should not be forced into a single ISA-level answer. The paper also describes using taint constraints around known mismatching registers, addresses, or opcodes after root-cause analysis, so that a known defect does not repeatedly prevent exploration of other behavior. This is not a claim that taint repairs the hardware; it keeps one known or ambiguous result from dominating the campaign.
The phrase “validity is a throughput feature” now has a specific meaning. A valid instruction encoding is only an entry ticket. Useful throughput is the amount of generated behavior that executes through the intended control-flow paths, reaches coordinated barriers, and produces observations that the oracle can classify. The generation stack raises that amount by preserving divergent paths. The barrier planner raises it by preventing generated circular waits. Interleaving and taint raise it by creating memory stress without allowing legal uncertainty to collapse the rest of the test.
There is a trade-off. A generator that favors high completion will spend less time on deliberately malformed instructions, illegal control and status registers, unaligned addresses, or other fault-handling paths. FuzzGPU's authors identify those cases as an area for future work. The current design is therefore not “valid programs solve verification.” It is “valid, intricate programs buy enough execution depth to make one important class of verification possible.” The invalid paths still need a complementary strategy.
This boundary also explains why the next problem cannot be solved by the generator alone. Once a structured test reaches a barrier, a shared address, or an out-of-order execution path, the hardware may produce several observations that are consistent with its contract. FuzzGPU has made the behavior reachable and has marked where the result is uncertain. It still needs a checker that can tell a legal difference from a defect without undoing the value of the test.