Deep Dive into eBPF Program Verification in the Linux Kernel

TL;DR — The eBPF verifier is the unsung hero that makes it safe to run arbitrary bytecode inside the Linux kernel. By constructing a control-flow graph, enforcing a strict type system, and proving termination and memory safety, it allows eBPF programs to power production networking, security, and observability workloads without risking kernel stability.

Introduction

Since its inception as a bare-bones packet filtering mechanism in 2014, eBPF has evolved into one of the most powerful extensibility mechanisms in the Linux kernel. Today, it underpins Cilium’s networking stack, Falco’s runtime security monitoring, and Facebook’s Katran load balancer. But what makes it possible to hand untrusted, user-space-compiled bytecode to the kernel without fear of panics, memory corruption, or infinite loops?

The answer is the eBPF program verifier — a static analysis engine baked into the kernel that every eBPF program must pass before it is ever executed. Understanding the verifier is essential for anyone building serious eBPF-based systems, because its decisions directly determine what your programs can and cannot do.

What Is the eBPF Verifier?

The eBPF verifier is a function inside the kernel — historically found in kernel/bpf/verifier.c — that performs a multi-pass static analysis on a loaded eBPF program. Its job is to answer one deceptively simple question: Is this program safe to run?

“Safe” means three things:

No out-of-bounds memory access. The program cannot read or write arbitrary kernel memory.
No infinite loops. Every execution path must terminate.
No undefined behavior. Every register and memory reference must have a known, valid type at every instruction.

The verifier operates on the eBPF instruction stream, which consists of a fixed-width 8-byte instruction format. Each instruction specifies an operation, destination register, source register, and immediate offset. The verifier walks these instructions and maintains a state for every possible program counter (PC).

Architecture of the Verifier

The Control-Flow Graph Pass

The verifier’s first major task is to construct a control-flow graph (CFG) of the program. eBPF supports conditional branches (JMP instructions with various conditions), calls to helper functions, and returns — all of which create branching paths.

The verifier starts at instruction 0 and explores every reachable path. At each JMP instruction, it splits the state: one branch assumes the condition is true, the other assumes false. This is conceptually similar to symbolic execution, though the verifier does not perform full symbolic analysis.

Example: A simple bounds check in eBPF

   r2 = *(u32 *)(r1 + 0)    // load packet length from context
   if r2 > 1400 goto +8    // if length > 1400, jump past the load
   r3 = *(u8 *)(r1 + r2)   // safe: we know r2 <= 1400

In this snippet, the verifier learns that on the fall-through path, r2 is bounded by 1400. This is a classic example of how the verifier tracks range information on registers, which is crucial for proving memory safety.

The Type System

The eBPF verifier enforces a rigorous type system. Every register has an associated type, and every memory access must be justified by that type. The key types include:

NOT_INIT — the register has not been written yet. Any use is rejected.
CONST_IMM — the register holds a known constant integer.
REG — the register holds a generic value (e.g., a pointer or integer).
PTR_TO_CTX — a pointer to the eBPF execution context (e.g., struct __sk_buff).
PTR_TO_MAP_VALUE — a pointer to a value stored in an eBPF map.
PTR_TO_PACKET — a pointer into packet data, with known bounds.
PTR_TO_SOCKET — a pointer to a socket structure.

When the verifier encounters a memory load or store, it checks the pointer type, the offset, and the size of the access. For example, a PTR_TO_PACKET pointer with a known end bound of 1400 bytes will reject any access at offset 2000.

// Kernel-side type check (simplified)
if (type == PTR_TO_PACKET && offset + size > pkt_end) {
    return -EACCES; // verifier rejects this access
}

This type system is what prevents the most common class of eBPF bugs: accessing memory you don’t own.

Helper Function Validation

eBPF programs cannot call arbitrary kernel functions. Instead, they call a whitelist of helper functions exposed by the kernel. The verifier checks every helper call against the function’s expected argument types and return type.

For example, bpf_map_lookup_elem expects a map pointer and a key pointer, and returns a pointer to the map value. After the call, the verifier knows the destination register holds PTR_TO_MAP_VALUE (or PTR_TO_NULL), and subsequent code must handle the null case before dereferencing.

Recent kernel versions have expanded the helper API significantly. Functions like bpf_redirect_neighbor, bpf_sk_assign, and bpf_loop each carry their own verifier constraints, and the verifier must track all of them precisely.

Termination Analysis

Infinite loops in eBPF would hang the entire kernel, so the verifier must prove that every loop terminates. The original verifier (pre-4.x) was conservative and rejected most loops outright. Starting with the introduction of loop validation in Linux 5.3 (via the LOOP instruction), the verifier gained a more sophisticated approach.

The modern loop validator uses backedge conditioning: it tracks how loop variables change across iterations and verifies that the loop counter moves monotonically toward a bound. If the verifier can prove that the loop index is bounded and strictly increasing (or decreasing), the loop is accepted.

// Valid loop example
   r1 = 0
loop:
   if r1 >= 10 goto end
   r2 += r1
   r1 += 1
   goto loop
end:
   // r2 is known to be 45 at this point

The verifier accumulates range information across iterations, so by the time it reaches end, it knows r1 ∈ [0, 10) and r2 = 45. This is powerful: downstream code can rely on these invariants.

Program Classes and Their Constraints

Not all eBPF programs are created equal. The kernel defines program types that constrain what helpers a program can call, what contexts it can access, and what the verifier allows.

Program Type	Typical Use	Key Context
`BPF_PROG_TYPE_KPROBE`	Kernel tracing	Kernel function arguments
`BPF_PROG_TYPE_XDP`	Early packet filtering	`struct xdp_md`
`BPF_PROG_TYPE_SOCKET_FILTER`	Socket-level filtering	`struct sk_buff`
`BPF_PROG_TYPE_CGROUP_SKB`	Network policy enforcement	`struct sk_buff`
`BPF_PROG_TYPE_TRACEPOINT`	Tracepoint instrumentation	Tracepoint arguments

Each program type has its own verifier whitelist. An XDP program, for instance, cannot call socket-related helpers, because the early-drop stage has no socket context. This constraint is enforced at load time by the verifier, preventing misuse before the program ever runs.

Common Verification Failures

Even experienced eBPF developers encounter verifier rejections. Here are the most common failure modes:

Unreachable instructions. The verifier marks some instructions as dead code if no execution path reaches them. While not always fatal, it can indicate a logic error.
Type mismatch on helper arguments. Passing a CONST_IMM where a PTR_TO_MAP is expected. The fix is usually to store the map pointer in a register first.
Unbounded memory access. Reading from a packet buffer without first checking the length. The verifier requires an explicit bounds check before any packet data access.
Dereferencing a potentially null pointer. After bpf_map_lookup_elem, the return value must be checked for null before use.
Loop not proven to terminate. A loop whose bounds cannot be statically determined will be rejected. Workarounds include using bpf_loop (introduced in kernel 5.18) or restructuring the logic.

Verifier error example (from libbpf):

> 
 >  (20) (0x00b)  r2 = *(u32 *)(r1 +0)
 R2 offset=0 size=4 id=1 off=0 r=0
 >  (21) (0x05b)  if r2 > 0x57c goto +8
 R2 id=1 off=0 r=0
 >  (22) (0x073)  r3 = *(u8 *)(r1 +r2)
 R3 offset=0 r=2
 
 error: R3 offset=0 is not within the bound of the packet

This error means the verifier could not prove that r2 (loaded from the packet length) was bounded before using it as an offset. The fix is to add an explicit comparison against the packet end pointer.

Patterns in Production

Cilium’s Approach

Cilium is perhaps the most prominent production user of eBPF. Their datapath compiles complex networking policies into eBPF programs that must pass the verifier under strict constraints. Cilium’s cilium-agent performs extensive pre-verification — running the verifier in a userspace sandbox before deploying programs to nodes. This catches rejection errors without impacting production traffic.

Facebook’s Katran

Facebook’s Katran load balancer uses XDP programs running at line rate on NICs. The verifier’s strict type system is a feature here: it guarantees that packet processing cannot corrupt kernel state, even under adversarial traffic patterns. Facebook has contributed significantly to the verifier’s robustness, including improvements to how it handles large indirect jump tables.

Observability with BCC and libbpf

Tools like BCC and libbpf abstract away much of the verifier complexity, but understanding its constraints is still essential. BCC’s BPF class will print verifier log output when a program fails to load, and libbpf exposes the verifier log buffer for programmatic inspection.

# BCC example: loading a program and capturing verifier errors
from bcc import BPF
try:
    b = BPF(src_file="my_program.c")
except Exception as e:
    print(f"Verifier rejected: {e}")

Recent Developments

The eBPF verifier is not static. Several recent developments have expanded its capabilities:

bpf_loop helper (kernel 5.18): Allows bounded loops with a configurable iteration count, giving the verifier a simpler loop model than the backedge validator.
Extended map types: New map types like BPF_MAP_TYPE_RINGBUF and BPF_MAP_TYPE_PERCPU_HASH come with their own verifier constraints, particularly around memory allocation limits.
Speculative execution hardening: Post-Spectre, the verifier has been enhanced to prevent eBPF programs from leaking kernel data through side channels, including stricter bounds checking on packet accesses.
JIT compiler integration: The verifier’s output feeds directly into the Just-In-Time compiler (kernel/bpf/jit/), which translates verified eBPF bytecode into native host instructions. The verifier must prove safety before the JIT ever sees the code.

Key Takeaways

The eBPF verifier is a static analysis engine that proves memory safety, type correctness, and termination before any eBPF program executes.
It constructs a control-flow graph and maintains a per-PC state, tracking register types and value ranges across branches.
The type system is the primary safety mechanism: every memory access must be justified by a known pointer type with verified bounds.
Program types constrain the helper whitelist and context access, and these constraints are enforced at load time.
Common verification failures include unbounded packet access, null pointer dereference, and unproven loop termination.
Production systems like Cilium and Katran rely on the verifier’s guarantees to run high-performance eBPF programs safely in the kernel.

Introduction#

What Is the eBPF Verifier?#

Architecture of the Verifier#

The Control-Flow Graph Pass#

The Type System#

Helper Function Validation#

Termination Analysis#

Program Classes and Their Constraints#

Common Verification Failures#

Patterns in Production#

Cilium’s Approach#

Facebook’s Katran#

Observability with BCC and libbpf#

Recent Developments#

Key Takeaways#

Further Reading#