◐ Off-By-One · answer catalog

go-ebpf-verifier-pruning-bounded-loop-range

2 answer(s)gogo1.26gogo1.26

Environment: Go 1.26 · Language: Go · Module: ~/ebpfverifier

📦 Source in repository (JSON)

Answer 1

The workspace was empty, so I implemented the verifier from scratch as a Go module at ~/ebpfverifier and wrote the full write-up to ~/SOLUTION.md (≈80 KB, includes every source file). Here is the solution.

Simplified eBPF Verifier with State Pruning and Bounded-Loop Range Induction

Environment: Go 1.26 · Language: Go · Module: ~/ebpfverifier

1. Root-cause analysis

The verifier must decide soundly whether a small eBPF program can run without violating memory/type/initialisation rules, and the analysis itself must always terminate even when the program contains loops. Five things make a naive implementation wrong.

1.1 Naive forward exploration diverges on loops

A forward walk that records (pc, registers) never stops for a loop whose register state changes each iteration:

r6 = 0
loop:
  r6 += 1
  if r6 < 10 goto loop

The header sees r6=0, r6=1, r6=2, … With a variable bound the number of distinct states is unbounded, so this is a non-termination bug, not just a performance issue.

Fix: keep the states already recorded at each pc and prune any new state that is subsumed by a recorded one; add widening at loop headers to force a fixpoint. (The “pruning” half of the title.)

1.2 Subsumption must be real lattice implication

“Prune if a state at the same pc was already seen” is not enough. The test must be is the new state a subset of a recorded (more general) state for the register lattice {uninit, scalar[min,max], stack-ptr[offmin,offmax], map-value-ptr(provenance,offmin,offmax), ctx-ptr}:

Definitely-initialised stack bytes are a must property, so the join uses intersection (a slot is initialised only if every path initialises it).

1.3 Widening alone accepts non-terminating loops

Widening a counter to full [MIN,MAX] and letting a branch narrow it proves safety, but destroys the information needed to prove termination:

r6 = 1
loop:
  r6 += 2
  if r6 != 100 goto loop   ; always odd, never exits

r6 == 100 becomes abstractly feasible, so a pure widening verifier accepts an infinite loop. This is exactly the “bounded-loop-range” failure mode.

Fix (range induction): for every reachable backward edge, find a loop-carried scalar updated by a constant step whose exit test bounds it:

Everything else is reported as unbounded loop. The same analysis clamps affine loop-carried values (including pointer offsets) to the iteration bound so large indexed map/stack accesses stay precise.

1.4 Pointer offsets need provenance

A scalar range cannot express pointer safety. The lattice tracks stack pointers (offset window [-512,0)), map-value pointers (map id + offset window [0,map_size)), and the context pointer. Each rejection names the exact class, instruction index and offending register:

reason trigger
uninitialized register reading an uninit register, or exit with r0 uninit
invalid stack access access outside [-512,0), or read of an unwritten slot
out-of-bounds map value access access outside [0,map_size)
pointer type mismatch scalar base, pointer+pointer, ALU on a pointer, write r10/ctx
unbounded loop reachable loop with no feasible exit or no induction bound

2. Exact fix

The module layout is:

file responsibility
lattice.go RegValue lattice + valueSubsumes / join
insn.go eBPF opcodes, encoding, constructors
arith.go interval arithmetic, pointer arithmetic, branch refinement
verifier.go work-list interpreter, state pruning, widening, memory checks, errors
termination.go range-induction proof and affine clamp
asm.go textual assembler for CLI/tests
main.go stdin CLI → accept or reject: <reason> at insn N (rX): detail
verifier_test.go table-driven tests

2.1 Core algorithm

visited[pc] : list of abstract states recorded at pc
worklist    : states to process

push(s):
    if some v in visited[s.pc] subsumes s: return          # pruning
    if s.pc is a loop header and |visited[s.pc]| >= WidenAfter:
        w = join(s, all visited[s.pc])                     # widening
        if range-induction bound exists:
            w = clampAffine(w, bound, entry state)         # range induction
        else:
            widenCount++; if too many: w = saturate(w)     # convergence
        visited[s.pc].append(w); worklist.push(w)
    else:
        visited[s.pc].append(s); worklist.push(s)

run to fixpoint
for each reachable backward edge:
    require a feasible exit AND an induction proof, else -> unbounded loop

WidenAfter = 128 keeps small loops exactly explored (fully precise pointers); larger loops widen and clamp. Every pc is capped at MaxStatesPerPC = 1024, and after MaxWidenings joins a header state is saturated to the full lattice value, after which everything is subsumed — so the work-list drains in finite time.

2.2 Key code — lattice subsumption/join (lattice.go)

func valueSubsumes(a, b RegValue) bool { // a covers b
    if b.Kind == KindUninit { return true }   // empty ⊆ anything
    if a.Kind == KindUninit { return false }
    if a.Kind != b.Kind { return false }
    switch a.Kind {
    case KindScalar:      return a.Min <= b.Min && b.Max <= a.Max
    case KindStackPtr:    return a.OffMin <= b.OffMin && b.OffMax <= a.OffMax
    case KindMapValuePtr: return a.Provenance == b.Provenance &&
                                 a.OffMin <= b.OffMin && b.OffMax <= a.OffMax
    case KindCtxPtr:      return true
    }
    return false
}

func join(a, b RegValue) (RegValue, bool) {
    if a.Kind == KindUninit || b.Kind == KindUninit { return Uninit(), true }
    if a.Kind != b.Kind { return RegValue{}, false }
    switch a.Kind {
    case KindScalar:      return Scalar(min64(a.Min,b.Min), max64(a.Max,b.Max)), true
    case KindStackPtr:    return StackPtr(min64(a.OffMin,b.OffMin), max64(a.OffMax,b.OffMax)), true
    case KindMapValuePtr: /* same provenance required */ ...
    case KindCtxPtr:      return CtxPtr(), true
    }
}

State subsumption additionally requires A.Init ⊆ B.Init (fewer definitely-initialised bytes is less precise) and A.Stack[i] covers B.Stack[i].

2.3 Key code — pruning + widening (verifier.go)

func (v *verifier) push(s State, from int) *VerifyError {
    pc := s.PC
    for _, old := range v.visited[pc] {
        if subsumes(old, s) { return nil }          // state pruning
    }
    if len(v.visited[pc]) >= v.cfg.MaxStatesPerPC {
        return &VerifyError{Reason: ReasonUnboundedLoop, Insn: from, Reg: -1, Detail: "state explosion"}
    }
    if v.isHeader[pc] && len(v.visited[pc]) >= v.cfg.WidenAfter {
        w := s
        for _, old := range v.visited[pc] {
            var ok bool
            w, ok = joinState(w, old)
            if !ok { return &VerifyError{Reason: ReasonPointerTypeMismatch, Insn: from, Reg: -1} }
        }
        if cw, applied := v.clampInduction(pc, w, v.visited[pc][0]); applied {
            v.visited[pc] = append(v.visited[pc], cw)
            v.work = append(v.work, cw)
            return nil
        }
        v.widenCount[pc]++
        if v.widenCount[pc] > v.cfg.MaxWidenings { w = saturateState(w) }
        v.visited[pc] = append(v.visited[pc], w)
        v.work = append(v.work, w)
        return nil
    }
    v.visited[pc] = append(v.visited[pc], s)
    v.work = append(v.work, s)
    return nil
}

Memory checks are range-based; e.g. a map store rejects unless bp.OffMin+disp ≥ 0 and bp.OffMax+disp+size ≤ map_size (analogous [-512,0) check for r10).

2.4 Key code — range induction (termination.go)

// Returns ok only if loop [t,j] has a provably terminating induction counter.
func (v *verifier) analyzeLoop(t, j int) (induction, bool) {
    // count writes in body, remember the single constant-step update per reg
    // for each candidate counter r with step delta and an exit branch `r OP K`:
    //   continuation `r < K`  with delta > 0  -> ok
    //   continuation `r <= K` with delta > 0  -> ok
    //   continuation `r > K`  with delta < 0  -> ok
    //   continuation `r >= K` with delta < 0  -> ok
    //   continuation `r != K`: ok iff delta==±1, or K is actually hit from the
    //                          exact entry value of r
    // A branch that can jump over the counter update while staying in the loop
    // (updateIsSkippable) invalidates the candidate.
}

clampInduction then bounds every affine register v by |step_v| · iterations in the direction of its step, so r2 += 1 inside a 100000-iteration loop yields offset [0, 100000] rather than [MIN,MAX].

2.5 Build & run

cd ~/ebpfverifier
go build -o ebpfverifier .
printf 'mov64 r0, 0\nexit\n' | ./ebpfverifier
# accept

printf 'mov64 r1, 1\ncall 1\nldxdw r0, [r0+8]\nexit\n' | ./ebpfverifier -map 1:8
# reject: out-of-bounds map value access at insn 2 (r0): map 1 read [8,16) size 8

go test ./... && ./demo.sh

Program text is one instruction per line (labels end with :; comments start with ;/#). -map id:size declares a map-value size for helper 1 (bpf_map_lookup_elem); -ctx size declares the context size.

3. Verification

3.1 Unit tests

$ go test ./...
ok      ebpfverifier    0.9s

$ go test -v ./...
--- PASS: TestVerifier
    --- PASS: TestVerifier/simple_accept
    --- PASS: TestVerifier/uninitialised_destination
    --- PASS: TestVerifier/uninitialised_source
    --- PASS: TestVerifier/exit_uninitialised_r0
    --- PASS: TestVerifier/invalid_stack_read_below_frame
    --- PASS: TestVerifier/invalid_stack_write_above_frame
    --- PASS: TestVerifier/uninitialised_stack_read
    --- PASS: TestVerifier/stack_spill_and_fill
    --- PASS: TestVerifier/spill_pointer_and_reload
    --- PASS: TestVerifier/map_in_bounds
    --- PASS: TestVerifier/map_out_of_bounds
    --- PASS: TestVerifier/scalar_as_base_pointer
    --- PASS: TestVerifier/add_two_pointers
    --- PASS: TestVerifier/write_frame_pointer
    --- PASS: TestVerifier/bounded_loop_constant
    --- PASS: TestVerifier/bounded_loop_large_constant_(range_induction)
    --- PASS: TestVerifier/bounded_loop_unknown_start_(range_induction)
    --- PASS: TestVerifier/unbounded_loop_unconditional
    --- PASS: TestVerifier/unbounded_loop_no_progress
    --- PASS: TestVerifier/nested_bounded_loops
    --- PASS: TestVerifier/nested_with_inner_unbounded
    --- PASS: TestVerifier/32-bit_alu_zero_extends
    --- PASS: TestVerifier/equality_loop_sampled_at_every_value
    --- PASS: TestVerifier/equality_loop_parity_trap
    --- PASS: TestVerifier/equality_loop_hit_from_even_start
    --- PASS: TestVerifier/counter_update_skipped_by_internal_branch
--- PASS: TestAcceptanceSummary
--- PASS: TestAssemblerRoundTrip
PASS
ok      ebpfverifier    0.937s

go vet ./... is clean.

3.2 End-to-end demonstration

$ ./demo.sh
== acceptance ==
simple                                        -> accept
bounded constant loop                         -> accept
bounded huge loop (range induction)           -> accept
bounded loop, unknown start                   -> accept
indexed map access, in bounds                 -> accept
== rejection reasons ==
unbounded loop                                -> reject: unbounded loop at insn 2: loop 1..2 has no feasible exit
unbounded loop, no progress                   -> reject: unbounded loop at insn 1: loop 1..1 has no feasible exit
uninitialised register                        -> reject: uninitialized register at insn 0 (r0): read of uninitialised destination
invalid stack access                          -> reject: invalid stack access at insn 0 (r10): stack read [-520,-512) out of bounds
out-of-bounds map value access                -> reject: out-of-bounds map value access at insn 2 (r0): map 1 read [8,16) size 8
pointer type mismatch                         -> reject: pointer type mismatch at insn 1 (r1): load from non-pointer register
indexed map access, out of bounds             -> reject: out-of-bounds map value access at insn 6 (r2): map 1 write [0,5000) size 4999

3.3 What the important checks demonstrate

property program shape result
state pruning r=0; loop: r+=1; ja loop rejected unbounded loop (fixpoint reached by pruning, no exit)
bounded loop r=0; loop: r+=1; jlt r,10,loop accepted
huge bounded loop bound 1_000_000_000 accepted via widening + induction (no unrolling)
unknown-start loop r=ctx[0]; r+=1; jlt r,100000,loop accepted (monotone counter)
parity trap r=1; r+=2; jne r,100,loop rejected (progression never hits 100)
safe equality loop r=0; r+=2; jne r,100,loop accepted (progression hits 100)
affine pointer loop stb [r2]; r2+=1 for map_size iterations accepted iff map_size is sufficient, else out-of-bounds map value access

4. Deliberate simplifications

The complete, compilable source (all files plus the full SOLUTION.md) is in ~/ebpfverifier and ~/SOLUTION.md.

Evidence & signatures

# Evidence
- Problem class: go-ebpf-verifier-pruning-bounded-loop-range
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-18T04:30:36.050Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement a simplified eBPF verifier over the documented instruction subset (alu64/alu32, stack and map-value loads/stores, conditional jumps, helper calls, exit) that abstractly interprets each program with a register lattice of {uninit, scalar with 64-bit min/max range, stack pointer with offset range, map-value pointer with provenance id and offset, context pointer}. On a branch join where a new state at the same pc is subsumed by an already-visited state the state must be pruned, otherwise exploration diverges on loops. Each program must be accepted or rejected with the exact reason class (unbounded loop, invalid stack access, out-of-bounds map value access, pointer type mismatch, uninitialized register), naming the instruction index and offending register, and loop-carried scalars need range induction so provably terminating loops are accepted.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-ebpf-verifier-pruning-bounded-loop-range", "provider": "openrouter", "solved_at": "2026-09-18T04:30:36.050Z", "version": "1.26"}

Answer 2

The workspace was empty, so I implemented the verifier from scratch as a Go module at ~/ebpfverifier and wrote the full write-up to ~/SOLUTION.md (≈80 KB, includes every source file). Here is the solution.

Simplified eBPF Verifier with State Pruning and Bounded-Loop Range Induction

Environment: Go 1.26 · Language: Go · Module: ~/ebpfverifier

1. Root-cause analysis

The verifier must decide soundly whether a small eBPF program can run without violating memory/type/initialisation rules, and the analysis itself must always terminate even when the program contains loops. Five things make a naive implementation wrong.

1.1 Naive forward exploration diverges on loops

A forward walk that records (pc, registers) never stops for a loop whose register state changes each iteration:

r6 = 0
loop:
  r6 += 1
  if r6 < 10 goto loop

The header sees r6=0, r6=1, r6=2, … With a variable bound the number of distinct states is unbounded, so this is a non-termination bug, not just a performance issue.

Fix: keep the states already recorded at each pc and prune any new state that is subsumed by a recorded one; add widening at loop headers to force a fixpoint. (The “pruning” half of the title.)

1.2 Subsumption must be real lattice implication

“Prune if a state at the same pc was already seen” is not enough. The test must be is the new state a subset of a recorded (more general) state for the register lattice {uninit, scalar[min,max], stack-ptr[offmin,offmax], map-value-ptr(provenance,offmin,offmax), ctx-ptr}:

Definitely-initialised stack bytes are a must property, so the join uses intersection (a slot is initialised only if every path initialises it).

1.3 Widening alone accepts non-terminating loops

Widening a counter to full [MIN,MAX] and letting a branch narrow it proves safety, but destroys the information needed to prove termination:

r6 = 1
loop:
  r6 += 2
  if r6 != 100 goto loop   ; always odd, never exits

r6 == 100 becomes abstractly feasible, so a pure widening verifier accepts an infinite loop. This is exactly the “bounded-loop-range” failure mode.

Fix (range induction): for every reachable backward edge, find a loop-carried scalar updated by a constant step whose exit test bounds it:

Everything else is reported as unbounded loop. The same analysis clamps affine loop-carried values (including pointer offsets) to the iteration bound so large indexed map/stack accesses stay precise.

1.4 Pointer offsets need provenance

A scalar range cannot express pointer safety. The lattice tracks stack pointers (offset window [-512,0)), map-value pointers (map id + offset window [0,map_size)), and the context pointer. Each rejection names the exact class, instruction index and offending register:

reason trigger
uninitialized register reading an uninit register, or exit with r0 uninit
invalid stack access access outside [-512,0), or read of an unwritten slot
out-of-bounds map value access access outside [0,map_size)
pointer type mismatch scalar base, pointer+pointer, ALU on a pointer, write r10/ctx
unbounded loop reachable loop with no feasible exit or no induction bound

2. Exact fix

The module layout is:

file responsibility
lattice.go RegValue lattice + valueSubsumes / join
insn.go eBPF opcodes, encoding, constructors
arith.go interval arithmetic, pointer arithmetic, branch refinement
verifier.go work-list interpreter, state pruning, widening, memory checks, errors
termination.go range-induction proof and affine clamp
asm.go textual assembler for CLI/tests
main.go stdin CLI → accept or reject: <reason> at insn N (rX): detail
verifier_test.go table-driven tests

2.1 Core algorithm

visited[pc] : list of abstract states recorded at pc
worklist    : states to process

push(s):
    if some v in visited[s.pc] subsumes s: return          # pruning
    if s.pc is a loop header and |visited[s.pc]| >= WidenAfter:
        w = join(s, all visited[s.pc])                     # widening
        if range-induction bound exists:
            w = clampAffine(w, bound, entry state)         # range induction
        else:
            widenCount++; if too many: w = saturate(w)     # convergence
        visited[s.pc].append(w); worklist.push(w)
    else:
        visited[s.pc].append(s); worklist.push(s)

run to fixpoint
for each reachable backward edge:
    require a feasible exit AND an induction proof, else -> unbounded loop

WidenAfter = 128 keeps small loops exactly explored (fully precise pointers); larger loops widen and clamp. Every pc is capped at MaxStatesPerPC = 1024, and after MaxWidenings joins a header state is saturated to the full lattice value, after which everything is subsumed — so the work-list drains in finite time.

2.2 Key code — lattice subsumption/join (lattice.go)

func valueSubsumes(a, b RegValue) bool { // a covers b
    if b.Kind == KindUninit { return true }   // empty ⊆ anything
    if a.Kind == KindUninit { return false }
    if a.Kind != b.Kind { return false }
    switch a.Kind {
    case KindScalar:      return a.Min <= b.Min && b.Max <= a.Max
    case KindStackPtr:    return a.OffMin <= b.OffMin && b.OffMax <= a.OffMax
    case KindMapValuePtr: return a.Provenance == b.Provenance &&
                                 a.OffMin <= b.OffMin && b.OffMax <= a.OffMax
    case KindCtxPtr:      return true
    }
    return false
}

func join(a, b RegValue) (RegValue, bool) {
    if a.Kind == KindUninit || b.Kind == KindUninit { return Uninit(), true }
    if a.Kind != b.Kind { return RegValue{}, false }
    switch a.Kind {
    case KindScalar:      return Scalar(min64(a.Min,b.Min), max64(a.Max,b.Max)), true
    case KindStackPtr:    return StackPtr(min64(a.OffMin,b.OffMin), max64(a.OffMax,b.OffMax)), true
    case KindMapValuePtr: /* same provenance required */ ...
    case KindCtxPtr:      return CtxPtr(), true
    }
}

State subsumption additionally requires A.Init ⊆ B.Init (fewer definitely-initialised bytes is less precise) and A.Stack[i] covers B.Stack[i].

2.3 Key code — pruning + widening (verifier.go)

func (v *verifier) push(s State, from int) *VerifyError {
    pc := s.PC
    for _, old := range v.visited[pc] {
        if subsumes(old, s) { return nil }          // state pruning
    }
    if len(v.visited[pc]) >= v.cfg.MaxStatesPerPC {
        return &VerifyError{Reason: ReasonUnboundedLoop, Insn: from, Reg: -1, Detail: "state explosion"}
    }
    if v.isHeader[pc] && len(v.visited[pc]) >= v.cfg.WidenAfter {
        w := s
        for _, old := range v.visited[pc] {
            var ok bool
            w, ok = joinState(w, old)
            if !ok { return &VerifyError{Reason: ReasonPointerTypeMismatch, Insn: from, Reg: -1} }
        }
        if cw, applied := v.clampInduction(pc, w, v.visited[pc][0]); applied {
            v.visited[pc] = append(v.visited[pc], cw)
            v.work = append(v.work, cw)
            return nil
        }
        v.widenCount[pc]++
        if v.widenCount[pc] > v.cfg.MaxWidenings { w = saturateState(w) }
        v.visited[pc] = append(v.visited[pc], w)
        v.work = append(v.work, w)
        return nil
    }
    v.visited[pc] = append(v.visited[pc], s)
    v.work = append(v.work, s)
    return nil
}

Memory checks are range-based; e.g. a map store rejects unless bp.OffMin+disp ≥ 0 and bp.OffMax+disp+size ≤ map_size (analogous [-512,0) check for r10).

2.4 Key code — range induction (termination.go)

// Returns ok only if loop [t,j] has a provably terminating induction counter.
func (v *verifier) analyzeLoop(t, j int) (induction, bool) {
    // count writes in body, remember the single constant-step update per reg
    // for each candidate counter r with step delta and an exit branch `r OP K`:
    //   continuation `r < K`  with delta > 0  -> ok
    //   continuation `r <= K` with delta > 0  -> ok
    //   continuation `r > K`  with delta < 0  -> ok
    //   continuation `r >= K` with delta < 0  -> ok
    //   continuation `r != K`: ok iff delta==±1, or K is actually hit from the
    //                          exact entry value of r
    // A branch that can jump over the counter update while staying in the loop
    // (updateIsSkippable) invalidates the candidate.
}

clampInduction then bounds every affine register v by |step_v| · iterations in the direction of its step, so r2 += 1 inside a 100000-iteration loop yields offset [0, 100000] rather than [MIN,MAX].

2.5 Build & run

cd ~/ebpfverifier
go build -o ebpfverifier .
printf 'mov64 r0, 0\nexit\n' | ./ebpfverifier
# accept

printf 'mov64 r1, 1\ncall 1\nldxdw r0, [r0+8]\nexit\n' | ./ebpfverifier -map 1:8
# reject: out-of-bounds map value access at insn 2 (r0): map 1 read [8,16) size 8

go test ./... && ./demo.sh

Program text is one instruction per line (labels end with :; comments start with ;/#). -map id:size declares a map-value size for helper 1 (bpf_map_lookup_elem); -ctx size declares the context size.

3. Verification

3.1 Unit tests

$ go test ./...
ok      ebpfverifier    0.9s

$ go test -v ./...
--- PASS: TestVerifier
    --- PASS: TestVerifier/simple_accept
    --- PASS: TestVerifier/uninitialised_destination
    --- PASS: TestVerifier/uninitialised_source
    --- PASS: TestVerifier/exit_uninitialised_r0
    --- PASS: TestVerifier/invalid_stack_read_below_frame
    --- PASS: TestVerifier/invalid_stack_write_above_frame
    --- PASS: TestVerifier/uninitialised_stack_read
    --- PASS: TestVerifier/stack_spill_and_fill
    --- PASS: TestVerifier/spill_pointer_and_reload
    --- PASS: TestVerifier/map_in_bounds
    --- PASS: TestVerifier/map_out_of_bounds
    --- PASS: TestVerifier/scalar_as_base_pointer
    --- PASS: TestVerifier/add_two_pointers
    --- PASS: TestVerifier/write_frame_pointer
    --- PASS: TestVerifier/bounded_loop_constant
    --- PASS: TestVerifier/bounded_loop_large_constant_(range_induction)
    --- PASS: TestVerifier/bounded_loop_unknown_start_(range_induction)
    --- PASS: TestVerifier/unbounded_loop_unconditional
    --- PASS: TestVerifier/unbounded_loop_no_progress
    --- PASS: TestVerifier/nested_bounded_loops
    --- PASS: TestVerifier/nested_with_inner_unbounded
    --- PASS: TestVerifier/32-bit_alu_zero_extends
    --- PASS: TestVerifier/equality_loop_sampled_at_every_value
    --- PASS: TestVerifier/equality_loop_parity_trap
    --- PASS: TestVerifier/equality_loop_hit_from_even_start
    --- PASS: TestVerifier/counter_update_skipped_by_internal_branch
--- PASS: TestAcceptanceSummary
--- PASS: TestAssemblerRoundTrip
PASS
ok      ebpfverifier    0.937s

go vet ./... is clean.

3.2 End-to-end demonstration

$ ./demo.sh
== acceptance ==
simple                                        -> accept
bounded constant loop                         -> accept
bounded huge loop (range induction)           -> accept
bounded loop, unknown start                   -> accept
indexed map access, in bounds                 -> accept
== rejection reasons ==
unbounded loop                                -> reject: unbounded loop at insn 2: loop 1..2 has no feasible exit
unbounded loop, no progress                   -> reject: unbounded loop at insn 1: loop 1..1 has no feasible exit
uninitialised register                        -> reject: uninitialized register at insn 0 (r0): read of uninitialised destination
invalid stack access                          -> reject: invalid stack access at insn 0 (r10): stack read [-520,-512) out of bounds
out-of-bounds map value access                -> reject: out-of-bounds map value access at insn 2 (r0): map 1 read [8,16) size 8
pointer type mismatch                         -> reject: pointer type mismatch at insn 1 (r1): load from non-pointer register
indexed map access, out of bounds             -> reject: out-of-bounds map value access at insn 6 (r2): map 1 write [0,5000) size 4999

3.3 What the important checks demonstrate

property program shape result
state pruning r=0; loop: r+=1; ja loop rejected unbounded loop (fixpoint reached by pruning, no exit)
bounded loop r=0; loop: r+=1; jlt r,10,loop accepted
huge bounded loop bound 1_000_000_000 accepted via widening + induction (no unrolling)
unknown-start loop r=ctx[0]; r+=1; jlt r,100000,loop accepted (monotone counter)
parity trap r=1; r+=2; jne r,100,loop rejected (progression never hits 100)
safe equality loop r=0; r+=2; jne r,100,loop accepted (progression hits 100)
affine pointer loop stb [r2]; r2+=1 for map_size iterations accepted iff map_size is sufficient, else out-of-bounds map value access

4. Deliberate simplifications

The complete, compilable source (all files plus the full SOLUTION.md) is in ~/ebpfverifier and ~/SOLUTION.md.

Evidence & signatures

# Evidence
- Problem class: go-ebpf-verifier-pruning-bounded-loop-range
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-18T04:30:36.050Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement a simplified eBPF verifier over the documented instruction subset (alu64/alu32, stack and map-value loads/stores, conditional jumps, helper calls, exit) that abstractly interprets each program with a register lattice of {uninit, scalar with 64-bit min/max range, stack pointer with offset range, map-value pointer with provenance id and offset, context pointer}. On a branch join where a new state at the same pc is subsumed by an already-visited state the state must be pruned, otherwise exploration diverges on loops. Each program must be accepted or rejected with the exact reason class (unbounded loop, invalid stack access, out-of-bounds map value access, pointer type mismatch, uninitialized register), naming the instruction index and offending register, and loop-carried scalars need range induction so provably terminating loops are accepted.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-ebpf-verifier-pruning-bounded-loop-range", "provider": "openrouter", "solved_at": "2026-09-18T04:30:36.050Z", "version": "1.26"}
Generated from the verified corpus · MIT licensedBack to the catalog