# DF-3011 — `btree_remove()` unbounded recursion: kernel stack overflow from crafted deep (valid-count) HAMMER1 B-trees

Kernel: DragonFly 6.5-DEVELOPMENT #0 (X86_64_GENERIC, INVARIANTS), sys/vfs/hammer
File under audit: `sys/vfs/hammer/hammer_btree.c` (pass 2)

## Verdict (short)

**REPRODUCED (twice, fresh mounts): kernel stack overflow → DOUBLE FAULT → panic.**
A crafted HAMMER1 image whose B-tree contains a chain of 200 internal nodes, each
with `count == 1`, `type == 'I'` and a **valid CRC32C** (every field passes the
DF-0776 count/type validation — the crafted values are all in-range), mounted with
`vnconfig`+`mount_hammer`, and one record deleted via `hammer snaprm`
(HAMMERIOC_DEL_SNAPSHOT → `hammer_delete_at_cursor(HAMMER_DELETE_DESTROY)` →
`hammer_btree_delete` → `btree_remove`), recurses once per chain level on the
ioctl thread's 16KB kernel stack and runs off the bottom of it:

```
DOUBLE FAULT
rip = 0xffffffff80949d20      (hammer_ref_buffer+0x0 — inside hammer_get_node
                               in the recursion's per-level node walk)
rsp = 0xfffff80118bb1000      (exactly the page-aligned kstack floor)
panic: double fault
```

Measured bracket: depth 64 completes the recursion (no overflow), depth 200
double-faults → per-level cost ≈ 80–250 bytes on a 16KB stack
(`LWKT_THREAD_STACK = UPAGES*PAGE_SIZE = 4*4096`, kern_fork.c:818). Chain length
is attacker-chosen (one 4KB node per level, all CRCs recomputed by the forger —
CRC32C is not a security barrier), so *any* stack size is overflowable; the
image just needs to be large enough (200 levels ≈ 800KB of nodes inside one 8MB
big-block at the B-tree zone append point).

## Root cause

* `btree_remove()` (`hammer_btree.c:1938`) recurses once per single-element
  internal level: `if (parent->ondisk->count == 1) { hammer_cursor_up_locked();
  error = btree_remove(cursor, ndelete); }` (`hammer_btree.c:1979-2007`).
* Nothing anywhere bounds HAMMER1 B-tree depth: the pushdown in `btree_search`
  (`hammer_cursor_down`) is iterative; the parent walk
  (`hammer_load_cursor_parent`/`hammer_btree_get_parent`) holds one parent at a
  time; there is no depth check at mount, in the cursor protocol, or in
  `btree_remove` itself. grep `depth` in hammer_btree.c shows only the
  rebalancer's `lcache`/`lock_children` depths (caller-bounded).
* Deletion of the last record of a leaf empties it
  (`hammer_btree_delete` → `ondisk->count == 0` → `btree_remove`), and every
  `count==1` ancestor recurses (hammer_btree.c:932-935, 1979-2007).
* The delete is reachable from: unlink/rmdir on nohistory fs's
  (hammer_object.c:2236 `hammer_nohistory(ip)`), `hammer prune`
  (hammer_prune.c:201), `hammer snaprm` (hammer_ioctl.c:833), mirroring
  (hammer_mirror.c:754,828), and PFS downgrade (hammer_pfs.c:520).

The PoC uses `hammer snaprm` because it is fully deterministic: it looks up the
crafted SNAPSHOT record by exact key and destroys it synchronously in the ioctl
thread (hammer_ioc_del_snapshot, hammer_ioctl.c:791-843).

## Threat model

Crafted HAMMER image (attacker-supplied media / `vfs.usermount` setups) — same
class as DF-0776/DF-3002/DF-3003. Unlike DF-0776, **all forged fields are
in-range** (count=1 or 2, type 'I'/'L', CRCs valid), so the DF-0776 hardening
(count/type validation at node load) does not and cannot block it; the
attacker-controlled quantity is the *depth* of the tree.

Impact: local kernel stack overflow (CWE-674). On the INVARIANTS guest: double
fault / panic (DoS). On production (INVARIANTS-OFF) kernels the same recursion
has *smaller* frames (higher threshold) but the same unbounded growth: the
overflow writes stack frames below the kstack into adjacent kernel_map
allocations (user LWP kstacks are `kmem_alloc_stack(kernel_map, ...)` with **no
guard page**) — silent corruption of neighboring kernel objects, plausibly
exploitable (the written data are kernel stack frames: saved registers holding
node pointers/offsets the attacker influences, plus valid kernel return
addresses; control is coarse, not demonstrated to privesc here).

## Reproduce (on the dfbsd QEMU guest, as root)

```sh
# one-time: base image + tools
dd if=/dev/zero of=/root/base.img bs=1m count=0 seek=12288
vnconfig -c vn0 /root/base.img && newfs_hammer -f -L p0 /dev/vn0
mount_hammer /dev/vn0 /mnt && echo hello > /mnt/f && mkdir /mnt/d \
  && echo world > /mnt/d/g && sync && umount /mnt && vnconfig -u vn0
sh build.sh                      # cc deepforge (needs /usr/src/sys headers)

sh run.sh 4   0x4000000000000000   # control: depth 4 — recurses 4 levels, unwinds
sh run.sh 200 0x4000000000000000   # attack: DOUBLE FAULT panic (see panic_d200.txt)
```

Expected: `MOUNT_OK`, `ls` works (original tree intact), then during
`hammer snaprm` the console shows the double fault above and ssh dies
(guest wedged in DDB). run.sh output + console captured in the logs.

### Forger output (run_d200.log)
```
version=7 ... orig_root=8000000021000000 (raw 554205184)
orig root: type=L count=11
btree blockmap next_offset=8000000021001000 (raw 554209280)   <- append point
FORGED depth=200 tid=4000000000000000 r2=8000000021001000 leaf=8000000021006900
MOUNT_OK depth=200 / d / f
[hammer snaprm → panic: double fault]
```

### What the forger builds (deepforge.c)
A new root R2 (internal, count=2): elms[0] = original left bound + subtree =
original B-tree (mount + root-inode lookups keep working); elms[1] = separator
(loc=1, obj=1, rec=SNAPSHOT, key=MIN_KEY, ctid=1) + subtree = crafted chain
C1..CN (each internal, count=1, bounds [S,RB), valid CRC); elms[2] = right
boundary (root_btree_end values, hammer_vfsops.c:429-437). Leaf holds one
SNAPSHOT record (obj_id=ROOT, key=tid, create_tid=2, delete_tid=0,
data_offset=0, data_len=0). `vol0_btree_root` repointed at R2, original root's
parent patched, all volume/node CRCs recomputed. Nodes are placed at the B-tree
zone blockmap append point (zone-8-owned layer2 big-block).

## Fix (validated — see VERDICT.md)

Cap the upward recursion in `btree_remove()` at `BTREE_REMOVE_DEPTH_MAX 32` and
return EDEADLK past the cap — semantics identical to the existing
deadlock-defer path (empty leaf stays attached, pruner cleans up later; nothing
has been modified at the level that bails). With the fix, depth-200 snaprm
returns cleanly (no panic); normal fs ops unaffected.

## Files

* `deepforge.c` / `icrc32.c` / `build.sh` — image forger
* `run.sh` — mount + snaprm trigger (`run.sh <depth> [tid]`)
* `run_d200.log`, `run_d200_run2.log` — the two attack runs
* `panic_d200.txt`, `panic_d200_run2.txt` — console double-fault captures
* `run_d64.log`, `panic_d64_layer2artifact.txt` — depth-64 bracketing run
  (recursion completes 64 deep; the later `layer2->zone == zone` assert during
  the unwind-frees is an *environmental* artifact of the dd/newfs-created base
  image's freemap — it fires on any node free on this image, is unrelated to
  DF-3011, and is preempted entirely by the overflow at attack depths)
* `run_control_d4.log`, `panic_layer2_d4.txt` — depth-4 control (trace shows
  exactly 4 `btree_remove` recursion frames — proves depth is attacker-chosen)
* `fix.diff` — git-apply-able depth cap (never applied to the audit tree)
* `fix_build.log`, `fix_run_d200.log` — single-fix kernel build + re-run