CVE-2026-55266 AI-generated analysis
platform/system/libufdt, sysdeps/libufdt_sysdeps_vendor.c (vendor sysdeps, qsort)
Rewrites the partition handling of the copied BSD qsort in libufdt's vendor sysdeps so that it recurses on the smaller partition and iterates on the larger one, bounding recursion depth to O(log n) instead of O(n) on adversarial inputs.
Root cause
The qsort implementation copied into sysdeps/libufdt_sysdeps_vendor.c always recursed on the left partition (`if ((r = pb - pa) > (int)es) qsort(a, r / es, es, cmp);`) and iterated via `goto loop` only on the right partition. The side chosen for recursion did not depend on partition size. An input whose pivot selection repeatedly left a large left partition therefore drove recursion depth proportional to n, so a large or adversarially ordered input could exhaust the stack (DoS per bulletin).
How the fix works
- sysdeps/libufdt_sysdeps_vendor.c:qsort adds a new local `int l`. After the final vecswap calls it computes `l = pb - pa` (left partition byte size) and `r = pd - pc` (right partition byte size) explicitly, instead of reusing `r` for both.
- If `l < r`: recurse with `qsort(a, l / es, es, cmp)` on the left (only when `l > es`), then iterate on the right by setting `a = pn - r; n = r / es; goto loop` (only when `r > es`).
- Else: recurse with `qsort(pn - r, r / es, es, cmp)` on the right (only when `r > es`), then iterate on the left by setting `n = l / es; goto loop` (only when `l > es`). `a` is unchanged because the left partition starts at `a`.
- The recursive call is always made on the smaller of the two partitions, so each recursion level at least halves the problem and stack depth is bounded to O(log n). The stale comment `/* qsort(pn - r, r / es, es, cmp); */` is removed.
Completeness
- Covers the single recursion site in the vendor qsort. Both partitions now go through the size comparison, and the `> (int)es` guards are preserved on each branch.
- Sorting semantics are unchanged; only the order in which partitions are processed differs.
- Partition sizes `l`, `r` and `d` remain `int` values computed from pointer differences, as before the fix. The patch does not change these types or add any size validation.
- Only sysdeps/libufdt_sysdeps_vendor.c is touched; the material shows no change to any other sysdeps variant or caller.
Behavior changes
- Maximum stack depth of the vendor qsort is bounded to O(log n) frames for any input ordering.
- No change to the sorted result, API, or return behavior. The order in which sub-partitions are processed changes (the right partition may now be sorted before the left).
Per major
- Android 14: same fix: platform/system/libufdt bbc615c85bf1 in android-security-14.0.0_r29 (cherry-pick, Change-Id I260075b5280433ae59b61edef9b30cb6610bd02f). At android-security-14.0.0_r30 the new declaration `int d, l, r, swaptype, swap_cnt;` is visible, and the resolver reports 7/8 lines of the patched region present.
- Android 15: same fix: 109d68930129 in android-security-15.0.0_r17. Same diff, hunk offsets and file index (235d995..3b1e60a) as Android 14. 7/8 lines present at android-security-15.0.0_r18.
- Android 16: same fix: 8dfd47aab1f2 in android-security-16.0.0_r8. Same change with hunks two lines later (@@ -100 / @@ -161, file index fc5b186..57d334a). 7/8 lines present at android-security-16.0.0_r9.
- Android 17: same fix: 70c20864187d in android-security-17.0.0_r1. Identical to the Android 16 patch (same file index). 7/8 lines present at android-security-17.0.0_r2.
Unknowns
- Which libufdt function calls this qsort and whether its input (e.g. device tree overlay data) is attacker controlled is not shown.
- Which build configurations actually compile sysdeps/libufdt_sysdeps_vendor.c (versus a libc-backed sysdeps) is not shown.
- Stack size of the affected environment and the input size required to trigger the overflow are not shown.
- Which line of the patched region the resolver counts as missing (7/8 lines present on every major) is not shown. The partition-handling block at the latest tags is not included in the code excerpt.
- Why the Android 16/17 hunks are offset by two lines is not shown.