kqsort_r recurses without depth bound: latent stack-exhaustion DoS (sibling of DF-2245 via shared qsort.c body)
Summary
qsort_r.c is 8-line shim: #define I_AM_KQSORT_R then #include libkern/qsort.c. All effective code audited in qsort.c. kqsort_r body performs genuine (non-tail) recursive call at qsort.c:175 on left partition. Worst-case recursion depth O(n): adversary forces pivot to partition maximum left region holds ~n-1 elements at every level blows kernel stack. Tail-call-eliminated goto loop at qsort.c:179-184 only protects second (right-partition) call not this one. swap_cnt==0 insertion-sort escape does not trigger killer input still causes swaps during partitioning. Same root cause as DF-2245 (qsort.c Medium) shared body. Today ZERO in-tree callers of kqsort_r (verified grep sys/) so no current concrete attack path bug is latent. Impact if kernel subsystem or privileged KLD later calls kqsort_r on attacker-influenced data with n above few hundred to ~10^4 is kernel-stack exhaustion (8-16KiB amd64 stack ~96-160 byte frames) double fault/panic local DoS. Loadable-module callers require CAP_KLD_LOAD root. Fix: always recurse on smaller partition iterate on larger bounds depth O(log n) apply in shared qsort.c closes both DF-2245 and this finding. [VERIFIED pass2: reproduced - median-of-3 killer drives linear stack growth and n 1024 panics KERNEL STACK GUARD HIT; latent, zero in-tree callers; recurse-on-smaller fix-validated bounded at 915B for n 1024]
Discussion (0)
PoC verification
Evidence pack
findings/poc/DF-2254 Β· 4 files| File | Type | Description | Size | |
|---|---|---|---|---|
| rig/dfqsort_rig.c | trigger-source | kernel rig calling the REAL kqsort_r with killer adversary + SP telemetry | 4.0 KB | view raw |
| run_baseline_smalln.log | run-log | excursion grows linearly with n | 425 B | view raw |
| panic_baseline_kqsortr.txt | panic | DOUBLE FAULT - KERNEL STACK GUARD HIT at n=1024 | 2.0 KB | view raw |
| fix.diff | suggested-fix | recurse on smaller partition (shared qsort.c body) | 1.4 KB | view raw |
Fix verification
fixedConfirmed kernel references
Detail
Evidence (decisive lines)
panic_baseline_kqsortr.txt (guard-hit double fault); run_baseline_smalln.log (linear excursion); rig/dfqsort_rig.c (calls real kqsort_r); fix A/B logs run_fixed_*
PoC changes
Authored kernel rig dfqsort_rig.c (sysctl-driven killer adversary + comparator SP telemetry) since the finding had no PoC and kqsort_r has no callers
Verified recommended fix
recurse on the smaller partition and iterate on the larger (O(log n) bound) in the shared qsort.c body
Verdict
Stock in-kernel kqsort_r (qsort_r.c shim + shared qsort.c body) proven to recurse O(n) deep on a McIlroy killer: measured kernel-stack excursion grows linearly (211B at n=16 to 7075B at n=200) and n=1024 panics with DOUBLE FAULT - KERNEL STACK GUARD HIT. Latent: zero in-tree callers today, so no user-reachable trigger exists on a stock kernel; the rig supplies the caller. Fix (smaller-partition recursion) validated by A/B rebuild. A/B: Fixed-kernel killer excursion bounded: 739B@200, 915B@1024, 1443B@16384, 1971B@131072 versus baseline 7075B@200 and DOUBLE FAULT@1024 (O(log n) depth; 128x crashing size survives).
No comments yet.