Skip to content

RB-tree red-black tree transformation LPE (CVE-2025-38001)

Reentrant bir HFSC enqueue, aynı class'ı scheduler'ın red-black "eligible tree"sine iki kez ekler ve rbtree'yi corrupt eder; öyle ki sonraki bir rotation/erase bir page pointer'ını bir victim node'a kopyalar — double-insertion'ı bir page use-after-free ve root'a çevirir.

Mechanism

Note

Neden çalışır: HFSC (Hierarchical Fair Service Curve) qdisc'i, bir red-black tree olan eligible tree (eltree) içinde class başına bir el_node node'u tutar. Enqueue path'i insertion'ı if (first && !cl->cl_nactive) ile korur. Ama cl_nactive yalnızca init_vf() (fair-service-curve path'i) tarafından artırılır, oysa init_ed() (realtime service-curve / HFSC_RSC path'i) cl_nactive'e dokunmadan eltree'ye ekler. Bir leaf NETEM qdisc'i bir paketi duplicate ettiğinde, aynı class için root qdisc'in enqueue'una yeniden girer. HFSC_RSC set'liyken guard her iki seferde de geçer, dolayısıyla aynı rb_node eltree'ye iki kez linklenir; invariant'larına (tek parent, asiklik, color balance) rebalancing kodunun körce güvendiği bir yapıda bir cycle/duplicate-parent oluşturur.

Red-black tree "dönüştürücü"dür: insert, update ve erase'in hepsi, balance'ı yeniden kurmak için child/parent pointer'ları kopyalayıp üzerine yazan rotation'lar yapar. İki tree node'u aynı object'i alias ettiğinde (ya da tree başka bir şekilde tutarsız olduğunda), o pointer kopyaları saldırgan etkisindeki bir adresi alakasız bir node'a yazmak üzere yönlendirilebilir — tamamen meşru rbtree rebalancing'inden inşa edilmiş güçlü bir data-only primitive.

Walkthrough

Class object'i struct hfsc_class'tır (~752 byte, kmalloc-1k), offset 0x50 yakınında bir Qdisc *qsched/leaf pointer'ı ve offset 0xa0 yakınında bir struct rb_node el_node ile.

Bir realtime (rsc) class'lı bir HFSC root'u, duplication'lı bir NETEM leaf'i ve dequeue throttle edilsin diye üstte bir TBF kur (infinite loop'un heap groom edilmeden ateşlenmesini önler):

# HFSC root with a realtime-curve class (HFSC_RSC)
tc qdisc add dev lo root handle 1: hfsc default 1
tc class add dev lo parent 1: classid 1:1 hfsc rt m1 0 d 0 m2 100Mbit

# NETEM leaf that DUPLICATES packets -> reentrant enqueue of the same class
tc qdisc add dev lo parent 1:1 handle 2: netem duplicate 100%

Reentrant call stack: NETEM'in duplicate path'i, ilk enqueue geri sarılmadan önce aynı class için root hfsc_enqueue()'u yeniden çağırır, dolayısıyla bu iki kez ateşlenir:

/* net/sched/sch_hfsc.c, vulnerable guard */
if (first && !cl->cl_nactive)   /* cl_nactive untouched on the RSC path */
    init_ed(cl, len);           /* inserts cl->el_node into the eltree */

init_ed() (RSC) cl_nactive'i hiç artırmadığı için, ikinci geçiş init_ed()'i yeniden koşturur ve el_node'u eltree'ye ikinci kez linkler.

Warning

Throttle olmadan, corrupt edilmiş tree eltree_get_mindl() / hfsc_dequeue()'un sonsuza dek döngüsel bir rb_left zincirini kovalamasına yol açar (CWE-835, CVE'nin infinite loop yarısı). TBF-on-top numarası dequeue'u bastırır, böylece exploit takılmak yerine groom edebilir.

kernelCTF exploit'i (D3vil / FizzBuzz101 = William Liu, Savino Dicanosa ile), corrupt edilmiş tree'yi tc class change / paket gönderimleriyle sürülen üç fazda bir rbtree pointer-copy primitive'ine çevirir:

Üç fazlı rbtree pointer-copy -> page-UAF
  1. Insert — class'a paketler gönder, böylece adresi corrupt edilmiş eltree'ye linklenir ve user kontrolündeki spray page'lerine (AF_PACKET pgv page vector'leri) sızar.
  2. Update — tc class change, bir hedef pgv page-vector girişinden ~0x10 byte önceye işaret eden forge edilmiş bir "grandparent" node'u içeri sokan bir rebalance/rotation tetikler.
  3. Remove — class'ı silmek, erase-rebalance'ın corrupt edilmiş class'tan hedef page vector'üne bir page pointer kopyalamasına yol açar. Artık aynı struct page iki pgv yapısı tarafından referans alınır ama yalnızca bir refcount taşır — klasik bir page-UAF kurulumu.

Oradan: user mapping'lerini unmap et ve packet socket'leri kapatarak fazla sayılan page'in refcount'unu sıfıra düşür (diğer pgv tarafından hâlâ alias edilen bir page'i free ederek), onu bir filp/signalfd allocation ile reclaim et ve free edilmiş page'i düzenlemek için signalfd write'larını kullan — root kazanmak için cred alanlarının üzerine yaz. Ekip 3.6 s'lik bir LTS çözümü raporladı.

Writeup'ta hedeflenen build'ler: Linux LTS 6.6.x, COS 105/109, Debian 12.

Detection

  • Bir NETEM duplicate leaf'inin altına yığılmış realtime curve'lü HFSC class'larının (tc ... hfsc rt) unprivileged oluşturulması güçlü bir sinyaldir; çoğu workload bunları asla birleştirmez.
  • hfsc_dequeue/eltree_get_mindl içinde dmesg infinite-loop / soft-lockup ya da net/sched/sch_hfsc.c içinde KASAN use-after-free.
  • Yüzeye ulaşmak için CONFIG_NET_SCH_HFSC + CONFIG_NET_SCH_NETEM ve unprivileged bir user net namespace (tc'nin bir userns içinde) gerektirir.

Mitigation

2f2190ce4ca9 / ac9fe7dd8e73 "net_sched: hfsc: Address reentrant enqueue adding class to eltree twice" commit'iyle (Pedro Tammela) düzeltildi. Düzeltme, yalnızca-cl_nactive check'ini, eltree membership'ini de doğrudan test eden bir helper ile değiştirir:

static bool cl_in_el_or_vttree(struct hfsc_class *cl)
{
    return ((cl->cl_flags & HFSC_FSC) && cl->cl_nactive) ||
           ((cl->cl_flags & HFSC_RSC) && !RB_EMPTY_NODE(&cl->el_node));
}
/* enqueue: */
if (first && !cl_in_el_or_vttree(cl))
    ...

Artık HFSC_RSC path'i RB_EMPTY_NODE(&cl->el_node)'u kontrol eder, dolayısıyla zaten eltree'de olan bir class asla iki kez insert edilmez. Defense-in-depth: qdisc yüzeyine unprivileged tc erişimini kaldırmak için unprivileged user namespace'leri devre dışı bırakın (kernel.unprivileged_userns_clone=0).

References