RB tree engine has zero INVARIANTS-mode structural validation, and scan_info_done walks the inprog list without a termination guard
| Field | Value |
|---|---|
| ID | DF-2989 |
| Status | new |
| Severity | Info |
| CVSS 3.1 | CVSS:3.1/AV:L/AC:H/PR:H/UI:N/S:U/C:N/I:N/A:L |
| CWE | CWE-691 / CWE-835 |
| File | sys/kern/subr_rbtree.c |
| Lines | engine sys/sys/tree.h:460-870 (esp. :729-740) |
| Area | kern |
| Confidence | certain |
| Discovered | 2026-09-02 |
| Pass | 2 (GLM 5.3 second pass) |
| Bucket | base:kern |
| Reported | pending |
| Known CVE | none |
| CVE match | novel |
Summary
The engine compiled by RB_GENERATE contains no assertion of any kind,
even on INVARIANTS kernels: no red/black property check, no
parent-child reciprocity check, no BST-order check on insert/remove,
and no cycle guard in RB_SCAN's successor walk. The DF-2924
quota-walk cycle (a consumer-side unsynchronization corrupting an RB
tree built on this engine) therefore manifests as an unbounded wild
pointer chase through kernel memory rather than an immediate,
diagnosable panic — a corrupted pm_pvroot or swblock_root behaves the
same way. Additionally, name##_scan_info_done walks the singly-linked
inprog list with while (*infopp != scan) and no NULL exit; any prior
corruption of RB_INPROG turns unlink into an unkillable traversal of
arbitrary memory instead of a clean panic. Not directly
attacker-triggerable: degrades detectability/containment of
consumer-side bugs. Fix: INVARIANTS/DEBUG-gated validator (parent
reciprocity, BST order, black-height, color domain) invoked from
INSERT/REMOVE, bounded-steps guard on RB_SCAN, NULL-terminated walk +
KKASSERT in scan_info_done (row diff).
Timeline
- 2026-09-02 Discovered during pass-2 audit of subr_rbtree.c (GLM 5.3).
Discussion (0)
PoC verification
Evidence pack
findings/poc/DF-2989 · 6 files| File | Type | Description | Size | |
|---|---|---|---|---|
| README.md | — | 263 B | ↓ raw | |
| fix.diff | — | 618 B | view raw | |
| manifest.json | — | 381 B | view raw | |
| run.log | — | 215 B | view raw | |
| tree2989.c | — | 2.0 KB | view raw | |
| verdict.json | — | 2.1 KB | view raw |
DF-2989 evidence pack
What
RB engine has zero INVARIANTS structural validation; scan_info_done walks without a NULL guard
Verdict
status=reproduced impact=none confidence=certain
See VERDICT.md for the full narrative and fix.diff for the verified fix.
Fix verification
fixedA/B complete (userland mirror compiled against the same macros): the hijacked-inprog demo returns cleanly on the fixed tree.h (stock SIGSEGV, exit 139); healthy-scan demo unaffected. Shipped fix uses the portable no-KKASSERT form (tree.h is also a userland header - sbin/hammer includes it).
Confirmed kernel references
Detail
Evidence (decisive lines)
VERDICT.md with path:line citations; run.log where a live demo exists; fix.diff
PoC changes
initial demo registered the scan AFTER corrupting the list (scan_info_link overwrote the corruption and the walk passed); fixed by hijacking rbh_inprog after scan registration
Verified recommended fix
NULL-terminated scan_info_done walk; do not touch a corrupted inprog list
Verdict
Reproduced with a userland program compiled against the same RB_GENERATE macros from sys/sys/tree.h (RB_SCAN_LOCK no-ops outside _KERNEL): after corrupting the tree head rbh_inprog to an unrelated chain that does not contain the live scan, name##_scan_info_done (tree.h:730-740) walks while (infopp != scan) infopp = &(infopp)->link; past the chain end and SIGSEGVs (demo2, exit 139; healthy demo1 clean). In-kernel this is an unkillable wild-pointer traversal; the engine itself (tree.h:460-870) contains no assertion of any kind even under INVARIANTS. Fix: NULL-exit walk + skip-unlink when absent (compile-validated in F40FIX; the full red/black validator is recommended upstream work). The DF-2988 rig demonstrated the motivating consumer-side engine misuse on this guest.
No comments yet.