Exploiting Kernel Races through Taming Thread Interleaving

Overview: Yutan presents a systematic approach to exploiting Linux kernel race conditions by manipulating thread interleaving to overcome challenging timing constraints. While automated fuzzing and sanitizing tools have discovered numerous kernel race conditions, many are dismissed as unexploitable due to extremely narrow execution windows that cannot be won through probabilistic brute-forcing alone. The talk categorizes race conditions into single-variable and multivariable (inclusive vs. non-inclusive) types and demonstrates methods—such as heterogeneous core scheduling and kernel preemption manipulation—to reliably trigger complex kernel races.

Key Topics: - Evolution of race condition detection using tools like Razzer and Kernel Concurrency Sanitizer (KCSAN). - Taxonomy of kernel race conditions: single-variable vs. multivariable races. - Deterministic analysis of inclusive versus non-inclusive multivariable race windows. - Techniques for stretching race windows using heterogeneous CPU cores and Linux CONFIG_PREEMPT scheduling.

Technical Details: Automated tools have increasingly exposed kernel concurrency bugs, including Razzer (finding over 30 race bugs in 2019) and Google's Kernel Concurrency Sanitizer (KCSAN, finding over 300 bugs). A race condition occurs when concurrent instructions across multiple processor cores access shared memory locations in a non-deterministic order. In a single-variable race condition, all racing instruction pairs interact around a single memory location within a defined race window (e.g., instruction B on Core 2 must execute between instructions A and C on Core 1). For example, a Linux kernel vulnerability in header inclusion allows instruction B to overwrite an inclusion variable with zero between instructions A and C, resulting in an uninitialized rfb pointer being passed into memcpy. While a narrow window lowers probability, brute-force repetition can eventually hit the required execution order.

Multivariable race conditions introduce multiple memory locations and instruction pairs (e.g., instructions A and D on Core 1 accessing memory 1, and instructions B and C on Core 2 accessing memory 2), requiring B and C to execute strictly between A and D. These are sub-classified into inclusive and non-inclusive races based on whether time window X (between A and D) naturally subsumes time window Y (between B and C). In non-inclusive races, instructions A and D execute back-to-back in Core 1 (spanning as few as 18 CPU cycles), while instructions B and C in Core 2 require a larger margin (e.g., 2,250 cycles). Because D will almost invariably execute before C finishes, traditional brute-forcing cannot trigger the bug. To bridge this cycle gap, attackers can leverage heterogeneous CPU architectures (such as Qualcomm Snapdragon 845 with 2.5 GHz and 1.6 GHz cores) by assigning the thread requiring an expanded window to a slow core and the racing thread to a fast core. Alternatively, on Linux kernels compiled with CONFIG_PREEMPT, an attacker can manipulate scheduling via sched_setaffinity: a rescheduling request from Core 0 causes Core 1 to preempt its thread and context switch after instruction A, expanding window X so Core 2 completes instructions B and C.

Key Takeaways: Relying on narrow race windows as a barrier to exploitability is a flawed assumption, as kernel preemption and multi-core architectural differences allow attackers to deterministically stretch execution windows. Kernel developers cannot assume that back-to-back instructions are immune to interleaving across cores. Mitigations require strict synchronization primitives (locks, memory barriers, atomic variables) rather than timing assumptions, while kernel fuzzing must incorporate delay mechanisms to detect non-inclusive race conditions.

(AI summary — Gemini Flash)