eBPF Verifier Bounds Divergence: When 32-Bit Scalar Truncation Corrupts Kernel Memory Under Heavy I/O Tracing

The central contract of the Linux eBPF subsystem is safety through static verification. Before a single instruction hits the JIT compiler, kernel/bpf/verifier.c performs abstract interpretation across every execution branch to prove termination, memory safety, and type isolation. When this verifier issues an approval, the kernel assumes the bytecode cannot dereference an unmapped page or step outside its allocated scratchpad. Yet in 2020, security researcher Manfred Paul demonstrated at Pwn2Own that this mathematical guarantee harbored a critical flaw. Documented in the Zero Day Initiative analysis of CVE-2020-8835, a subtle logical bug in the verifier's 32-bit scalar bounds calculation allowed arbitrary read and write access to arbitrary kernel memory, shattering the abstraction boundary between tracing probes and the kernel core. To understand how an abstract analyzer fails, you have to look at how it models hardware registers. The kernel does not execute bytecode during verification; it tracks constraints. For every virtual register, the verifier maintains a bpf_reg_state structure containing unsigned bounds (umin_value, umax_value), signed bounds (smin_value, smax_value), their 32-bit sub-register equivalents (u32_min_value, etc.), and a tristate number (tnum) that tracks known bit states (which bits are definitively 0, definitively 1, or unknown). When an eBPF program executes an ALU instruction, the verifier invokes adjust_scalar_min_max_vals() to calculate the new possible range of the destination register based on the operation and the operand's bounds.

/* Conceptual representation of reg state divergence */
struct bpf_reg_state {
    enum bpf_reg_type type;   /* SCALAR_VALUE, PTR_TO_MAP_VALUE */
    u64 umin_value, umax_value;
    s64 smin_value, smax_value;
    struct tnum var_off;      /* bitwise known/unknown tracking */
    u32 u32_min_value, u32_max_value;
};

The ALU32 Truncation Trap

The vulnerability surfaced because modern x86_64 hardware and modern BPF instructions operate across two worlds: full 64-bit registers and 32-bit sub-registers. When a 32-bit arithmetic operation executes on x86_64, the processor automatically zeroes out the upper 32 bits of the destination register. In eBPF, this happens via BPF_ALU32 opcodes. Inside kernel/bpf/verifier.c, tracking these transformations requires constant synchronization between the 32-bit sub-register bounds and the full 64-bit bounds via helper functions like __reg_bound_offset32() and __update_reg_bounds(). In the flawed kernel logic, the verifier's bounds propagation rules for 32-bit operations made incorrect assumptions about how bitwise operations and shifts affected the enclosing 64-bit state. When executing specific sequences of right-shifts or bitwise operations on 32-bit sub-registers, the verifier incorrectly deduced that a register's bounds had narrowed to a single constant (for example, umin_value == 0 and umax_value == 0). Meanwhile, at runtime, the silicon executed instructions that produced non-zero values—such as 0x1000. This divergence meant the verifier believed a register was guaranteed to be 0, while the hardware register contained an arbitrary, user-controlled scalar.

BASH

# An innocent-looking ALU sequence causing bounds divergence:
BPF_MOV64_REG(BPF_REG_2, BPF_REG_1)        # R2 = runtime input [0, 1]
BPF_ALU64_IMM(BPF_RSH, BPF_REG_2, 1)        # Verifier: R2 in [0, 0]
BPF_ALU32_IMM(BPF_AND, BPF_REG_2, 0xFFFF)   # Bounds calculation diverges

From Scalar Divergence to Memory Corruption

A scalar register with desynchronized bounds is not inherently destructive until it interacts with memory pointers. In tracing workflows—such as instrumenting block I/O request queues, NVMe submission queues, or virtual file system operations—engineers frequently write eBPF programs that use dynamic indices to accumulate histograms inside a BPF_MAP_TYPE_ARRAY. When a program adds a scalar register to a map value pointer (PTR_TO_MAP_VALUE), the verifier checks whether the pointer offset can exceed the allocated size of the map element. The verifier calculates: pointer_offset + reg->umax_value ≤ map->value_size. Because the verifier believed reg->umax_value was 0, it marked the pointer arithmetic as completely safe and approved the program. At runtime, however, the CPU added the actual non-zero scalar value to the base address of the map memory. By carefully choosing the scalar value, an unprivileged user could offset the map pointer far beyond the bounds of the BPF map value, into adjacent kernel slab objects (kmalloc-512 or kmalloc-1024). Subsequent load or store operations (BPF_LDX_MEM, BPF_STX_MEM) no longer targeted map memory—they read and wrote raw kernel structures, such as struct bpf_map function tables, security credentials, or thread memory, achieving arbitrary read/write and immediate root escalation.

Structural Hardening and Infrastructure Defense

Fixing bounds tracking bugs requires more than simple patches; it requires defense-in-depth across the kernel surface. The upstream kernel resolved CVE-2020-8835 by overhauling bounds propagation in kernel/bpf/verifier.c and later adopting formally verified algorithms for range analysis. For infrastructure teams running production nodes, several structural mitigations must be maintained: First, restrict unprivileged access immediately. The single most effective mitigation against verifier flaws is ensuring unprivileged users cannot load BPF bytecode:

BASH

sysctl -w kernel.unprivileged_bpf_disabled=1

Setting this parameter to 1 (or 2 to permanently lock it until reboot) stops standard users from interacting with sys_bpf entirely, neutralizing local privilege escalation vectors. Second, implement defensive bitwise masking in tracing bytecode. Even when the verifier approves an offset, production BPF probes should explicitly mask scalar offsets immediately before memory indexing (e.g., index &= (TABLE_SIZE - 1)). This ensures that even if a future verifier bug miscalculates register bounds, the silicon itself forces the pointer arithmetic to remain within safe boundaries. Third, ensure continuous monitoring of JIT compilation and tracing probes. Use audit rules and eBPF observability tools to monitor BPF_PROG_LOAD syscall invocations across fleet clusters, isolating tracing programs strictly to privileged, signed binaries managed through CI/CD pipelines.