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)

# 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

DF-3011 — VERDICT

status: reproduced (twice) | impact: panic (kernel stack overflow; silent kstack smash into adjacent kernel_map memory on production builds) | confidence: certain | fix validated: fixed

What was verified on the guest (stock INVARIANTS kernel #0)

1. The recursion is attacker-depth-controlled. Depth-4 crafted chain → console backtrace shows exactly 4 btree_remove recursion frames (btree_remove+0x26a ×3 under btree_remove+0x2fd, panic_layer2_d4.txt / run_control_d4.log — that run later tripped an environmental freemap assert during the unwind frees, see "artifact" below). Depth-64: recursion completes (panic_d64_layer2artifact.txt — again the artifact, after 64 successful levels). Depth-200: DOUBLE FAULT before any unwind (panic_d200.txt, panic_d200_run2.txt — two independent fresh-mount runs): DOUBLE FAULT rip = 0xffffffff80949d20 -> hammer_ref_buffer+0x0 (nm /boot/kernel/kernel) rsp = 0xfffff80118bb1000 -> page-aligned kstack floor (16KB LWKT stack) panic: double fault
2. The mount itself is clean. mount_hammer + ls /mnt succeed on the crafted image (original subtree intact under the grafted root R2); the original records remain reachable. Only the record deletion triggers the overflow — via hammer snaprm (HAMMERIOC_DEL_SNAPSHOT) which calls hammer_delete_at_cursor(HAMMER_DELETE_DESTROY) → hammer_btree_delete → btree_remove synchronously in the ioctl thread.
3. All forged fields are in-range. deepforge writes count=1/2, type 'I'/'L', and recomputes every node CRC32C — the DF-0776 count/type validation (evidence pack DF-0776/fix.diff, hammer_ondisk.c) passes every crafted node. The attacker-controlled quantity is the chain length (tree depth), which nothing validates anywhere in HAMMER1.

Root cause trace (path:line)

• sys/vfs/hammer/hammer_btree.c:932-935 — empty leaf → btree_remove(cursor, ndelete).
• sys/vfs/hammer/hammer_btree.c:1979 — if (parent->ondisk->count == 1): every single-element internal level recurses.
• sys/vfs/hammer/hammer_btree.c:2002-2007 — hammer_cursor_up_locked(cursor) then error = btree_remove(cursor, ndelete); — one C-stack frame per B-tree level, no depth bound.
• No depth limit exists anywhere else: btree_search pushdown (hammer_btree.c:1255 hammer_cursor_down) and the parent reload (hammer_cursor.c:490-521 hammer_load_cursor_parent) are iterative; grep -n depth sys/vfs/hammer/hammer_btree.c only finds the rebalancer's caller-bounded lcache/lock_children depths.
• Caller thread stack: 16KB — sys/sys/thread.h:472 #define LWKT_THREAD_STACK (UPAGES * PAGE_SIZE), UPAGES 4 (sys/cpu/x86_64/include/param.h:126), allocated for user LWPs at sys/kern/kern_fork.c:818 via kmem_alloc_stack(kernel_map, ...) (sys/kern/lwkt_thread.c:393-395) — kernel_map, no guard page: overflow writes into whatever is mapped below the kstack on production builds.
• Trigger reachability: hammer_ioctl.c:833 (snaprm), hammer_prune.c:201, hammer_mirror.c:754,828, hammer_object.c:2236 (nohistory unlink), hammer_pfs.c:520,525.

Why panic and not uid=0 (honest impact ceiling)

The overflowing data are the recursion's own stack frames: saved RBP/RIP and locals of btree_remove/hammer_cursor_up_locked/hammer_load_cursor_parent/ hammer_btree_get_parent/hammer_get_node. Content control is coarse (kernel pointers and small integers influenced by crafted offsets/keys, valid kernel return addresses). On the INVARIANTS guest the overflow manifests as a double fault (proof of the primitive). On a production kernel the same overflow writes below the kstack into adjacent kernel_map allocations — a memory-corruption primitive — but turning it into a controlled hijack was not attempted within this run's budget; no leak/groom work was done, and I am reporting DoS-class impact with a corruption ceiling, not claiming privesc.

Environmental artifact (NOT part of this finding)

Sub-overflow depths unwind and free the chain nodes; the first hammer_blockmap_free on these dd/newfs-created base images trips KKASSERT(layer2->zone == zone) (hammer_blockmap.c:832). The on-disk freemap of the fresh image decodes (via vol0_blockmap[4]) to layer1[0].phys = 0x5ba (garbage) — an inconsistency of the test image environment (newfs on sparse vn images) that affects any btree-node free, unrelated to the recursion bug. The attack depth (200) always overflows before the first free, so the artifact never masks the finding. (Worth a separate look by the project: the 8-byte offset between the on-disk layer1 table and the blockmap root.)

Fix validation (single-fix kernel)

• fix.diff applied to the guest's /usr/src copy only (audit tree untouched), make nativekernel KERNCONF=X86_64_GENERIC → build OK (fix_build.log).
• Rebooted into the fixed kernel (uname recorded in fix_run_d200.log).
• Re-ran the exact depth-200 PoC: no panic — snaprm returns, mount stays healthy, unmount clean (fix_run_d200.log). The capped recursion defers via the existing EDEADLK semantics (empty leaf left for the pruner).
• Regression: normal newfs/mount/write/rm/sync/umount cycle on an uncrafted image passes on the fixed kernel.

Reproduce summary

build.sh                    # deepforge
sh run.sh 200 0x4000000000000000
# console: DOUBLE FAULT, rsp = kstack floor, panic: double fault