Skip to content

KernelSnitch data-structure side-channel

Variable-length kernel container'ları (hash-table bucket chain'leri, red-black tree'ler) yürüyen syscall'ların süresini ölç; access latency'si occupancy'yi açığa çıkarır ve bir covert channel, kernel heap pointer'ları ve cross-process aktivitesini leak eder — hepsi de unprivileged, hardware-agnostic bir attacker'dan.

Mechanism

Kernel container data structure'ları boyut olarak değişkendir. Bir hash table per-bucket linked-list (chain) yürüyüşlerine bozulur; bir tree'nin lookup derinliği eleman sayısıyla büyür. Dolayısıyla böyle bir yapıya insert, içinde lookup ya da ondan remove süresi, ilgili bucket/subtree'yi şu an kaç elemanın işgal ettiğine — occupancy'ye — bağlıdır. O occupancy, kısmen unprivileged bir user tarafından sıradan syscall'lar yoluyla kontrol edilir ve gözlemlenebilir.

Note

KernelSnitch'in (Maar, Juffinger, Steinbauer, Gruss, Mangard — NDSS 2025) exploit ettiği invariant tamamen algoritmiktir, microarchitectural değil: daha uzun bir bucket chain ya da daha derin bir tree basitçe daha fazla instruction çalıştırır. Bu onu hardware-agnostic yapar — belirli bir CPU bug'ına, cache attack'ine ya da shared memory'ye ihtiyaç duymaz. İki nesne yerleşimi, aynı bucket'a hash ettiklerinde (bir collision chain'i uzatır) farklı bucket'lara hash etmelerine kıyasla ayırt edilebilir. Kernel, bu hash table'ların bazılarını bir kernel heap pointer kullanarak indexlediği için (örn. futex table kısmen backing mm_struct/inode adresine göre key'lenir), bir değerin düştüğü index gizli pointer bit'lerinin bir fonksiyonudur. Hangi user-chosen key'lerin bir target ile collide ettiğini gözlemlemek dolayısıyla o pointer bit'lerini yeniden inşa eder — hash function üzerinde bir timing oracle.

Somut olarak paper şunlara saldırır: futex hash table (sys_futex wait/wake), POSIX timer hash table'ı, IPC ipc_ids.key_ht hash table'ı, IPC radix tree'si ve hrtimer red-black tree'si.

Walkthrough

Referans artifact'lar (isec-tugraz/KernelSnitch) Ubuntu 22.04, kernel v5.15 ve v6.8 üzerinde değerlendirildi. Futex covert channel'ı ve pointer leak'i öne çıkan PoC'lerdir.

  1. Occupancy'yi amplify et. Tek bir futex bucket'ına çok sayıda waiter ekle, böylece chain zamanlanacak kadar uzun olsun. Paper, tek bir bucket'a 64+ queue itmenin, yüklü bucket'ı dolaşan bir probe ile dolaşmayan biri arasında ölçülebilir ~8.2 µs'lik bir fark verdiğini bildiriyor:
// pin many FUTEX_WAIT waiters onto addresses that hash to the SAME bucket
for (int i = 0; i < 64; i++)
    // each thread blocks in sys_futex(FUTEX_WAIT) -> one queue appended to the bucket
    spawn_waiter(addr_in_target_bucket[i]);
  1. Bir probe syscall'unu zamanla. Bir FUTEX_WAKE (ya da chain'i yürüyen bir wait), bucket yüklüyken daha uzun sürer. İnce bir clock ile ölç:
unsigned long t0 = rdtscp();
syscall(SYS_futex, probe_addr, FUTEX_WAKE, 1, NULL, NULL, 0);
unsigned long dt = rdtscp() - t0;        // long chain -> dt is ~8.2us higher
  1. Bir heap pointer leak et (iki aşama).
  2. Collision detection: target ile aynı bucket'a hash eden user-chosen futex key'lerini bul — sadece ikisi de mevcutken oluşan timing artışıyla tespit edilir.
  3. Address enumeration: bucket index'i gizli kernel adresinden hesaplanır; aday kernel adreslerini enumerate et, her birinin hangi bucket'a index edeceğini tahmin et ve tahmin edilen collision'ları gözlemlenenlere uyanı tut. Bu, indexleme pointer'ını < 65 sn'de byte-accurate kurtarır.
Bildirilen case-study sonuçları (NDSS 2025)
  • Covert channel: futex hash table üzerinde 580 kbit/s; ipc_ids.key_ht üzerinde 528 kbit/s; hrtimer red-black tree üzerinde ~35 kbit/s; adaptive thresholding ile error rate'leri < %2.8.
  • Kernel heap pointer leak: byte-accurate, < 65 sn.
  • Website fingerprinting: Firefox page load'ları sırasında futex-table occupancy'sini izleyerek, ~300-boyutlu timing vector'ları üzerindeki bir CNN, Ahrefs Top 100'de F1 > %89'a (≈%89.5, %93.2 precision) ulaştı.

Warning

Sinyal, tüm syscall runtime'ına göre çok küçüktür, dolayısıyla naif single-shot timing başarısız olur. Saldırı amplification'a dayanır — ya structure-based (target bucket/subtree'yi ekstra elemanlarla şişir, böylece per-walk maliyeti baskın olsun) ya da cache-based (chain'i LLC'den evict et, böylece her node yürüyüşü bir miss ödesin; delta'yı önemli ölçüde büyüttüğü bildirildi). Amplification olmadan per-element delta sub-microsecond'dur ve syscall noise içinde kaybolur.

Detection

  • Anormal occupancy: uzun chain'ler kışkırtmak için onlarca-yüzlerce futex waiter / POSIX timer / IPC key ekleyen bir process istatistiksel olarak alışılmadıktır ve kernel accounting üzerinden gözlemlenebilir.
  • Sıkı timing (rdtscp) ile eşleşen yüksek frekanslı futex/timer_create syscall döngüleri davranışsal bir imzadır.

Mitigation

Yazarlar şunları öneriyor ve eksik olduklarını belirtiyor:

  • Watermark-based execution padding — chain length'ten bağımsız olarak syscall execution'ı sabit bir maliyete pad'le, occupancy sinyalini kaldır (bir performans maliyetiyle).
  • Structure partitioning / namespace isolation — hash table'ları namespace/user başına partition'la, böylece bir attacker bir victim ile bucket paylaşamaz ve collision oracle'ı kırılır.

Paper açıkça belirtiyor ki bunların hiçbiri leakage'ı tamamen ortadan kaldırmaz; bu, patch'lenebilir bir bug değil, variable-size container'ların algoritmik bir özelliğidir.

References