# UNDF: UNDF-2026-000000365
# cilium-0004: CWE-407 — Quadratic predecessor deduplication in eBPF CFG construction

## Severity: MEDIUM

## Repository
github.com/cilium/cilium
Commit: (depth-1 clone, branch main)

## File
`pkg/bpf/analyze/blocks.go`

## Defective Lines
```
64:    func addPredecessors(ins *asm.Instruction, preds ...*asm.Instruction) {
65:        l := setLeader(ins)
66:        for _, pred := range preds {               // O(P) new predecessors
67:            if pred == nil {
68:                continue
69:            }
70:            if !slices.Contains(l.predecessors, pred) {  // O(E) linear scan
71:                l.predecessors = append(l.predecessors, pred)
72:            }
73:        }
74:    }
```

## Call Chain
```
buildCFG(insns) →                                      [blocks.go line ~700]
    second pass: for i.Next() {                        // O(I) instructions
        targets.resolve(i.Offset, tgt, tgtPrev) →
            for _, branch := range target.branches {   // O(B) branches per target
                setBranchTarget(branch, tgt, tgtPrev) →
                    addPredecessors(tgt, branch, prev) →
                        for _, pred := range preds {   // O(P) = 1..2
                            slices.Contains(l.predecessors, pred) // O(E) scan
```

## Complexity
O(I × B × E) where:
- I = number of eBPF instructions in the program
- B = number of branches targeting a particular instruction
- E = number of existing predecessors accumulated per instruction

`l.predecessors` grows as instructions with multiple in-edges are encountered.
For heavily-branched programs (computed gotos, loop headers), E grows and the
deduplication check becomes O(E²) per instruction.

## Impact
eBPF program analysis is performed at program load time via `NewBlocks()`. Large,
heavily-branched eBPF programs (e.g., policy enforcement programs with many
conditional checks) trigger O(E²) predecessor deduplication. Cilium's datapath
programs can reach tens of thousands of instructions with complex CFGs.

This also affects `Backtracker.previousBlock()` at line 544:
```
544:    if slices.Contains(bt.visited, pred) {   // O(V) growing visited list
547:        bt.visited = append(bt.visited, pred)
```
Each `previousBlock()` call during backtracking scans the entire visited list —
O(V²) total over a full backtrack traversal of V blocks.

## Fix
Replace `[]*Block` / `[]*asm.Instruction` slice with `map[*T]struct{}` for dedup.

```go
// Before (defective) — l.predecessors is []*asm.Instruction:
if !slices.Contains(l.predecessors, pred) {
    l.predecessors = append(l.predecessors, pred)
}

// After (fixed) — use a companion map:
type leaderMeta struct {
    predecessors    []*asm.Instruction
    predecessorSet  map[*asm.Instruction]struct{}  // add this field
}

func addPredecessors(ins *asm.Instruction, preds ...*asm.Instruction) {
    l := setLeader(ins)
    if l.predecessorSet == nil {
        l.predecessorSet = make(map[*asm.Instruction]struct{})
    }
    for _, pred := range preds {
        if pred == nil { continue }
        if _, exists := l.predecessorSet[pred]; !exists {  // O(1)
            l.predecessorSet[pred] = struct{}{}
            l.predecessors = append(l.predecessors, pred)
        }
    }
}

// Similarly for Backtracker.visited:
type Backtracker struct {
    visited    []*Block
    visitedSet map[*Block]struct{}   // add companion map
    ...
}
```

## References
- CWE-407: Inefficient Algorithmic Complexity
- `pkg/bpf/analyze/blocks.go` lines 64-74 (addPredecessors)
- `pkg/bpf/analyze/blocks.go` lines 520-555 (Backtracker.previousBlock)
- `pkg/bpf/analyze/util.go` line 88 (resolve → setBranchTarget call site)
