Patching the eBPF Verifier to Preserve Spilled Zeroes

The eBPF verifier first proves that a BPF program is safe before the program can run inside the kernel. It continuously tracks information such as where pointers point, which stack bytes are initialized, and which register values are constants. When this tracking is precise enough, valid programs pass. When it loses precision conservatively, programs that are safe in practice can still be rejected.

The issue discussed here was a very small precision loss. A value stored on the stack was clearly zero, but that fact disappeared after a variable-offset stack read because of how the verifier represented the stack internally. As a result, an otherwise valid program could be rejected after using the loaded byte as a pointer offset.

In one sentence:

If every byte read from the stack is actually zero, the verifier should preserve the result register as zero whether those bytes are represented as STACK_ZERO or as scalar const-zero STACK_SPILL. But if that conclusion depends on a stack spill value, the contributing stack slot must be connected as a precise dependency so that pruning remains sound.

This post records how the patch was found, why the first simple fix was not enough, and what shape eventually landed in bpf-next.

The Beginning of the Problem

The verifier tracks the BPF stack byte by byte. Some bytes are marked as STACK_ZERO when an immediate zero is stored. Other bytes are marked as STACK_SPILL when they come from spilling a register to the stack.

For example, storing an immediate zero like this can make the corresponding bytes STACK_ZERO.

*(u32 *)(r10 - 4) = 0

In contrast, if zero is first placed in a register and that register is then stored to the stack, the verifier can track it as a scalar register spill.

r0 = 0
*(u64 *)(r10 - 8) = r0

Both forms store actual zero bytes in memory. But their internal verifier representations can be different.

The problem was in the mark_reg_stack_read() path. For a variable-offset stack read, the verifier checks the whole possible read range and then marks what kind of value the destination register holds. The old code made the result a const zero only if every byte in the read range was STACK_ZERO. Simplified, it looked like this.

for (i = min_off; i < max_off; i++) {
        slot = -i - 1;
        spi = slot / BPF_REG_SIZE;
        stype = ptr_state->stack[spi].slot_type;
        if (stype[slot % BPF_REG_SIZE] != STACK_ZERO)
                break;
        zeros++;
}

if (zeros == max_off - min_off)
        __mark_reg_const_zero(env, &state->regs[dst_regno]);
else
        mark_reg_unknown(env, state->regs, dst_regno);

So even when the whole read range was actually zero, if the bytes came from a scalar const-zero spill rather than STACK_ZERO, the result became an unknown scalar.

Why This Matters in Practice

The first question was whether this was only an artificial pattern that appears in hand-written verifier selftests. For a kernel patch, saying that something is theoretically possible is usually not enough. Real BPF C code should be able to produce the bytecode pattern.

It turned out that the BPF backend in clang 22.1.6 can generate this pattern at both -O2 and -O3. The C program was a small helper-based BPF program that initializes a stack scalar to zero, treats its address as a byte pointer, and reads one byte through a bounded context-derived index.

The core BPF instruction stream can be simplified as follows.

r2 = 0
*(u64 *)(r10 - 8) = r2
w1 = *(u32 *)(r1 + 0)
if w1 > 7 goto exit
r2 = r10
r2 += -8
r2 += r1
w1 = *(u8 *)(r2 + 0)

Here, fp-8..fp-1 are all zero. Therefore, no matter which byte *(u8 *)(r2 + 0) reads, the result should be zero. But the old verifier could turn the read result into an unknown byte with var_off=(0x0; 0xff).

If that value is simply discarded, the problem is not visible. But if the loaded byte is used again as a pointer offset, it can lead to rejection.

r1 = one_byte_value_pointer
r1 += loaded_byte
*(u8 *)(r1 + 0) = loaded_byte

To a human, loaded_byte is zero. So this is a safe write to offset 0 of a one-byte object. But if the verifier sees loaded_byte as an unknown u8, it considers values up to 255 possible. Then one_byte_value_pointer + 255 is possible, so the program can be rejected for violating map value bounds or stack bounds.

In the experiment, the key log from the unpatched verifier looked like this.

R1=scalar(...,var_off=(0x0; 0xff)) ... fp-8=0
invalid access to map value, value_size=1 off=255 size=1
R6 max value is outside of the allowed memory range

The important point is that the verifier was not missing initialization. The stack range had already been checked as initialized. The problem was that the fact that the initialized value was zero did not propagate to the read result because the bytes were represented as STACK_SPILL.

The First Fix Was Not Enough

The simplest fix was to teach mark_reg_stack_read() to treat scalar const-zero STACK_SPILL bytes as zero bytes, in addition to STACK_ZERO.

In pseudo-code:

if (stype[byte] == STACK_ZERO)
        zero = true;

if (stype[byte] == STACK_SPILL && spilled_reg_is_const_zero(spi))
        zero = true;

With only this change, the positive case passes. But for the verifier, that is not sufficient. The reason is state pruning.

The verifier compares states that reach the same instruction and can avoid rechecking a path when it decides that a state has already been sufficiently verified. If a scalar value or spilled stack value is not precise, value differences can be ignored in the pruning comparison.

Therefore, once the verifier concludes that "the read result is zero because this stack slot contains a spilled zero," that stack slot value must become part of the verifier's precision dependency. Otherwise, the following risk appears.

Path A: spill 0 to fp-8. Treat the read result as 0 and accept.
Path B: spill 1 to fp-8. But this path can be wrongly pruned as equivalent to path A.

In that case, the naive implementation can accept valid programs, but it can also accept invalid programs. The experiment confirmed this: the naive implementation without precision marking accepted the positive cases, but wrongly accepted a pruning negative case using BPF_F_TEST_STATE_FREQ.

The comparison looked like this.

This experiment changed the direction of the patch. The patch could not just recognize more zero bytes. It also had to connect the source dependency behind the zero conclusion.

Final Approach: Preserve Zeroes and Mark Precision Together

The final patch lets mark_reg_stack_read() recognize scalar const-zero spills as zero bytes, but when such spills are used, it records the stack slot mask and calls mark_chain_precision_batch().

The core flow is as follows.

if (stype[slot % BPF_REG_SIZE] == STACK_ZERO) {
        zeros++;
        continue;
}

if (stype[slot % BPF_REG_SIZE] == STACK_SPILL &&
    bpf_register_is_null(&ptr_state->stack[spi].spilled_ptr)) {
        zero_spill_mask |= 1ull << spi;
        zeros++;
        continue;
}

Then, when the whole read range is determined to be zero, the destination register is marked as const zero. If that result depended on scalar zero spills, the source stack slots are marked precise.

if (zeros == max_off - min_off) {
        __mark_reg_const_zero(env, &state->regs[dst_regno]);
        if (zero_spill_mask) {
                bpf_bt_set_frame_slot_mask(&env->bt, ptr_state->frameno,
                                           zero_spill_mask);
                return mark_chain_precision_batch(env, env->cur_state);
        }
}

The meaning of this approach is straightforward.

Restricting the change to zero was also important. Generalizing this to non-zero constant scalars would require reasoning about which partial byte is read, what the endianness is, and what the access size is. That would make the patch larger and create more review surface. For this problem, "every byte is zero" was small and clear enough.

It Was Not Only a Variable-Offset Problem

The initial issue was about variable-offset stack reads. Up to v2, the patch focused on that path. During review, however, it became clear that fixed-offset stack reads had a related mixed case as well.

Fixed-offset reads already handled the case where a pure scalar-zero spill is restored as a register fill. But a read range containing both STACK_ZERO bytes and scalar const-zero STACK_SPILL bytes was different.

For example, consider an 8-byte slot with this state.

0000ssss

Here, 0000 represents STACK_ZERO, and ssss represents bytes from a scalar const-zero spill. In reality, all 8 bytes are zero. But the old fixed-offset mixed read could fail to reconstruct this as const zero and fall back to unknown.

In v3, the var-offset-only flag in mark_reg_stack_read() was removed, and both variable-offset reads and fixed-offset mixed reads were made to use the same zero reconstruction path. The existing pure register-fill behavior was kept unchanged. In other words, the patch did not disturb the path that restores the original register state; it only improved the mixed zero case that previously fell back to unknown.

This was reflected in the final implementation patch as well: bpf: Preserve scalar zero spills for stack reads.

The issue started with var-offset reads, but the final patch became a small cleanup of an inconsistency across stack read paths.

What the Selftests Lock In

Even for a small verifier patch, tests matter. The selftests did not only check that the positive cases now pass. They also locked in which values should be recognized as zero and which values must not be.

The tests added to verifier_var_off.c covered the following cases.

The tests also included log assertions. For example, success cases check not only that the result register remains zero, but also that the precision backtracking trail is present.

__msg("mark_precise: frame0: regs= stack=-8")
__msg("R3=0")

The fixed-offset mixed case was added to verifier_spill_fill.c. Its goal is to check that an 8-byte read spanning both STACK_ZERO and scalar const-zero STACK_SPILL bytes is reconstructed as const zero.

The final v3 selftest patch touched these two files.

tools/testing/selftests/bpf/progs/verifier_var_off.c
tools/testing/selftests/bpf/progs/verifier_spill_fill.c

The test code was also reviewed. Inline asm selftests should follow the style of the surrounding file, and unnecessary helpers or annotations should be avoided. Even in the final review, there was a cleanup comment that the fixed-offset mixed test could use a simpler instruction form. This was a reminder that verifier selftests are reviewed just as carefully as verifier implementation code.

Verification Results

The v3 candidate was built on top of bpf-next and tested in a QEMU guest with BPF selftests.

The main verification results were as follows.

Earlier experiments hit unrelated selftest build failures and VM shared-library issues. For the final verification, the setup was cleaned up by running the latest artifacts directly in the QEMU guest through a hostshare mount.

I also compared unrelated verifier objects with veristat in an earlier experiment. For objects such as verifier_spill_fill, verifier_live_stack, and verifier_search_pruning, stable fields such as verdict, peak states, max states per instruction, program size, JIT size, and stack depth showed no differences. This does not prove that there is no cost impact in all cases, but it did not show any signal of broad verifier state growth.

Review Flow and Final Merge

The series went through v1, v2, and v3 and was sent to bpf-next. Since I did not have a confirmed deployed-program regression, I did not add a Fixes: tag. Instead, the motivation was that clang can generate this pattern in practice, and that the same object is rejected by the unpatched verifier but accepted by the patched verifier.

The important review points were these.

The key sentence in the v3 cover letter was this.

Stack reads currently lose the known-zero fact when loaded bytes come from
a spilled scalar constant zero rather than from STACK_ZERO bytes in some
paths.

Finally, the patchwork bot reported that the series was applied to bpf/bpf-next.git.

This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <[email protected]>

This was a small verifier precision improvement, but the path from discovery to merge was not simple. In particular, any change that makes the verifier accept more valid programs must also prove that it does not accidentally accept invalid programs.

For me, this series was also my third patch merged into the kernel.

References

Summary

The core of this patch is to reduce the semantic mismatch between STACK_ZERO and scalar const-zero STACK_SPILL. If all actual bytes are zero, the stack read result should be preserved as zero. But if that conclusion depends on a spilled scalar value, the verifier's precision model must retain that dependency as well.

The lessons from this work are:

• Patches that reduce unnecessary verifier rejections need soundness validation at the same time.
• When different internal representations have the same meaning, it is worth checking whether they can be reconstructed consistently.
• A naive precision improvement can become an unsafe accept because of state pruning.
• Showing that clang can generate the pattern makes the patch motivation much stronger.
• Similar paths such as fixed-offset and variable-offset reads should be checked together, or review will expose the inconsistency.
• Selftests are more convincing when they include negative cases and verifier log assertions, not only positive cases.

In the end, this patch made the verifier preserve known-zero facts a little better. The scope is small, but these small facts matter in the eBPF verifier. If the fact that a value is zero disappears, a valid program can be rejected. If the verifier trusts that fact incorrectly, an invalid program can be accepted. The hard part of verifier work is walking that narrow line correctly.