sched/topology: old domain chains are queued for RCU freeing before the per-CPU pointers are updated, so a late reader can still dereference a freed sched_domain and sched_domain_shared (UAF)

[徐晗翔 <xuhx@hust.edu.cn>]

[-- Attachment #1: Type: text/plain, Size: 9679 bytes --]

cpu_attach_domain() queues the old sched_domain chain for RCU freeing
(destroy_sched_domains(), kernel/sched/topology.c:829) and only then
publishes the new chain to the per-CPU sd_llc/sd_llc_shared/
sd_asym_packing/sd_asym_cpucapacity/sd_balance_shared pointers
(update_top_cache_domain(), topology.c:831).  RCU requires a pointer to
be published before the object is removed; here the removal phase
starts first.  A reader that starts after a grace period which began
in that window is not waited for by that grace period (its CPU has
already reported a quiescent state), yet can still load the old
per-CPU pointer before the store and dereference the freed
sched_domain and sched_domain_shared.  KASAN catches the resulting
slab-use-after-free; the fix is to publish the new (or NULL) pointers
before call_rcu().

The detailed description:

* Test environment / affected version

  Linux 7.3.0 (gcc 13.3.0, GNU ld 2.42) #5 SMP PREEMPT_DYNAMIC,
  x86_64 QEMU/KVM guest, 8 vCPUs, 4 GiB, KASAN enabled.  The tested
  kernel/sched/topology.c and kernel/sched/fair.c are byte-identical
  to the v7.3 release and to linux-7.3.y.  Relevant config:
  CONFIG_SMP=y, CONFIG_SCHED_CACHE=y, CONFIG_PREEMPT_RCU=y,
  CONFIG_PREEMPTION=y, CONFIG_PREEMPT_DYNAMIC=y,
  CONFIG_NUMA_BALANCING=n, CONFIG_CPUSETS=y, CONFIG_HOTPLUG_CPU=y,
  CONFIG_NR_CPUS=64.  The same store-after-call_rcu order exists in
  v5.4, v5.15, v6.1, v6.6, v6.12 and current master; sched_domain is
  affected there, and sched_domain_shared since that object was
  introduced.

* Mechanism

  Two objects are involved.  struct sched_domain is allocated in
  sd_init() with the cpumask span embedded in the same allocation
  (topology.c:2688; sched_domain_span() at
  include/linux/sched/topology.h:175-193 returns (void *)sd +
  sizeof(*sd)).  struct sched_domain_shared (sds) is refcounted:
  free_sched_domain_shared() does kfree() when the last reference
  goes away (topology.c:626-630), and destroy_sched_domain() releases
  groups, shared and llc_counts before kfree(sd) (topology.c:632-647).

  The removal phase starts before the per-CPU pointers are touched:

    - cpu_attach_domain() stores the new chain in rq->sd
      (rcu_assign_pointer(rq->sd, sd), topology.c:827);
    - it then queues the old chain for RCU freeing
      (destroy_sched_domains(tmp), topology.c:829 ->
      call_rcu(&sd->rcu, destroy_sched_domains_rcu),
      topology.c:660-664);
    - only after that does update_top_cache_domain(cpu)
      (topology.c:831) store the per-CPU pointers: sd_llc (705),
      sd_llc_shared (707), sd_asym_packing (724),
      sd_asym_cpucapacity (737), sd_balance_shared (738).

  The practical path is partition teardown: detach_destroy_domains()
  calls cpu_attach_domain(NULL, &def_root_domain, cpu) for every CPU
  in the dying partition under rcu_read_lock() (topology.c:3325-3328).
  With sd == NULL, update_top_cache_domain() stores NULL into the
  per-CPU pointers; a reader that loads an old non-NULL pointer
  before that store keeps a pointer to a chain that is already in the
  RCU removal phase.  In the build path rq->sd is normally NULL after
  the preceding detach, so destroy_sched_domains(NULL) is a no-op;
  the detach path is the one that materially mismatches.

  Why the stale pointer is not waited for: a grace period snapshots
  the CPUs' qsmask at start (kernel/rcu/tree.c:1986) and clears a
  CPU's bit when that CPU reports a quiescent state (tree.c:2395).  A
  reader that begins its section after its CPU's QS is not represented
  in the current grace period at all.  If such a reader blocks, the
  preempt-RCU code only sets RCU_GP_BLKD (and thus gp_tasks) when the
  CPU's qsmask bit is still set (kernel/rcu/tree_plugin.h:162-254),
  and the blocked-reader test only looks at gp_tasks
  (tree_plugin.h:381-383).  So the grace period does not wait for it,
  the callbacks run, and the object is freed while the reader still
  holds the pointer.  Blocking the reader does not help; it only
  makes the window larger.

  Natural readers:

    - task_cache_work() (fair.c:2089-2145, CONFIG_SCHED_CACHE) loads
      per_cpu(sd_llc, cpu) under rcu_read_lock() and then walks
      sched_domain_span(sd) in a loop, dereferencing sd and calling
      into the runqueues; it holds the domain for the whole span.
    - nohz_balancer_kick() (fair.c:14486-14497) loads
      per_cpu(sd_asym_packing, cpu) and walks sched_domain_span(sd)
      when an SD_ASYM_PACKING domain exists.

  Shorter readers exist as well: select_idle_cpu() and
  select_idle_capacity() copy the span at entry (fair.c:8935 and the
  corresponding copy in select_idle_capacity()),
  get_llc_stats() and record_sg_llc_stats() read the sds fields,
  update_idle_cpu_scan() writes nr_idle_scan (fair.c:12882),
  set_idle_cores() writes has_idle_cores (fair.c:8802-8820) and
  set_cpu_sd_state_busy/idle() do atomic_inc/dec on
  sds->nr_busy_cpus (fair.c:14546-14586).  The last two are the reason
  this is not read-only in principle, even though the reproducer
  below only shows the read side.

  The refcount is not the problem: a published per-CPU pointer is not
  a reference.  The sds ref is held by the owning sched_domain, which
  is itself freed by the same callback chain; the refcount decides
  when sds is freed, not whether a stale pointer can reach it.

* Trigger model

  A privileged actor tears down a scheduling partition (CPU hotplug
  offline, echo 0 > /sys/devices/system/cpu/cpuN/online, or a cpuset
  partition update) while a task with an mm is running and generating
  periodic cache-aware wakeups.  For the long-holding readers the
  machine needs multiple LLCs with CONFIG_SCHED_CACHE enabled
  (/sys/kernel/debug/sched/llc_balancing/enabled, default 1), or an
  SD_ASYM_PACKING domain for the nohz reader.  KASAN is needed to
  observe the short natural window; without instrumentation the
  window is on the order of the two adjacent calls.

  Consequence: use-after-free read of struct sched_domain and its
  embedded span, and of struct sched_domain_shared; the short writers
  can also turn it into a use-after-free atomic write.  Kernel crash
  or memory corruption (DoS) is possible; no privilege escalation is
  claimed.  The trigger needs CAP_SYS_ADMIN; the reader side is
  ordinary kernel work.

* Reproducer 

  The attached patch is verification instrumentation against vanilla
  7.3; it is not a proposed fix.  It adds mdelay(100) between
  destroy_sched_domains(tmp) and update_top_cache_domain(cpu), and a
  witness kthread that stands in for task_cache_work(): it waits for
  the first detach window, sleeps past the start of the grace period
  (so its CPU has reported a QS), enters rcu_read_lock(), loads
  per_cpu(sd_llc, 0), holds the section for 1.5 s, and then reads
  sd->shared and sd->flags.  The artificial delay and hold are what
  make the race deterministic on a KASAN kernel; the code path and
  the pointer lifetime are unchanged.

    # build (from the 7.3 tree)
    patch -p1 < sds-uaf-repro.patch
    # use a KASAN-enabled x86_64 config with the keys listed above
    make O=build-kasan -jN bzImage

    # boot an initramfs that toggles cpu 7 offline/online 60 times:
    qemu-system-x86_64 -enable-kvm -cpu host -m 4G -smp 8 \
      -kernel build-kasan/arch/x86/boot/bzImage \
      -initrd initrd.cpio.gz \
      -append "console=ttyS0 rdinit=/init ignore_loglevel \
               preempt=full kasan_multi_shot=1" -nographic

  Result, first offline/online cycle (7.3, KASAN):

    [    8.746873] BUG: KASAN: slab-use-after-free in sds_witness_fn+0x9c/0x130
    [    8.746906] Read of size 8 at addr ff110001002e4968 by task sds_witness/99
    ...
    [    8.747565]  build_sched_domains+0x1f1/0x2d90
    [    8.747861]  destroy_sched_domains_rcu+0x24/0x30
    [    8.748056]  cpu_attach_domain+0x73e/0xd20
    [    8.748076]  partition_sched_domains+0x463/0x6d0
    [    8.748098]  cpuset_update_active_cpus+0x66d/0xa20
    [    8.748119]  sched_cpu_deactivate+0x1b5/0x1f0

  The object is the kmalloc-512 allocation that contains the
  sched_domain and its embedded span; the read at +360 is sd->shared.
  Timeline from the instrumented kernel:

    [    7.180976] SDS-WINDOW: cpu=0     <- call_rcu() done
    [    7.188809] SDS-LOAD: cpu=0 sd=ff110001002e4800
    [    7.281007] SDS-STORE: cpu=0      <- per-CPU pointer cleared
    [    8.746873] BUG: KASAN ...

  The reader loaded the pointer 92 ms before the store; the grace
  period had already started, so the callback ran and freed the
  object while the reader was blocked; the dereference happened
  1.5 s later.  Without the mdelay()/hold instrumentation, 100 and 60
  offline/online cycles did not reproduce (the natural window is
  only a few instructions); the ordering violation is still the same.



* Suggested direction

  Move update_top_cache_domain(cpu) before destroy_sched_domains(tmp)
  in cpu_attach_domain(), i.e. publish the new chain (and clear the
  per-CPU pointers when sd == NULL) before entering the RCU removal
  phase.  Then every per-CPU store precedes call_rcu(): a reader that
  loads an old pointer must have started its section before the store,
  hence before the grace period began, and is therefore waited for
  (including the blocked case, where RCU_GP_BLKD is set because the
  qsmask bit is still set); a reader that starts after the grace
  period began loads the new or NULL pointer.  A comment documenting
  the ordering requirement would help; the same change should go to
  stable.  Report-first, no patch attached; happy to test any
  proposal.


Please keep me in Cc; I am not subscribed to the lists.


Regards,
Hanxiang Xu
xuhx@hust.edu.cn

[-- Attachment #2: sds-uaf-repro.patch --]
[-- Type: application/octet-stream, Size: 2715 bytes --]

--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -6,6 +6,10 @@
 #include <linux/sched/isolation.h>
 #include <linux/sched/clock.h>
 #include <linux/bsearch.h>
+#include <linux/delay.h>
+#ifdef CONFIG_SCHED_CACHE
+int sds_window_cpu = -1; /* SDS-WITNESS */
+#endif
 #include "sched.h"
 
 DEFINE_MUTEX(sched_domains_mutex);
@@ -828,6 +832,16 @@
 	dirty_sched_domain_sysctl(cpu);
 	destroy_sched_domains(tmp);
 
+	/*
+	 * SDS-WITNESS: widen the window between entering the RCU removal
+	 * phase (destroy_sched_domains) and publishing the new per-CPU
+	 * pointers (update_top_cache_domain).  Verification only.
+	 */
+	WRITE_ONCE(sds_window_cpu, cpu);
+	pr_info("SDS-WINDOW: cpu=%d\n", cpu);
+	mdelay(100);
+	pr_info("SDS-STORE: cpu=%d\n", cpu);
+
 	update_top_cache_domain(cpu);
 }
 
@@ -3502,3 +3516,63 @@
 	partition_sched_domains_locked(ndoms_new, doms_new, dattr_new);
 	sched_domains_mutex_unlock();
 }
+
+/* ---------------- SDS-WITNESS: verification instrumentation ---------------- */
+/*
+ * Reacts to the first window of a detach/build pass (cpu 0), reports a
+ * quiescent state after the grace period has started, then loads the old
+ * per-CPU domain pointer, holds the RCU read-side section across the
+ * callback, and dereferences the domain.  With the mdelay(100) in
+ * cpu_attach_domain() the window is wide enough to load the old pointer
+ * after call_rcu() and before the per-CPU store.
+ */
+#ifdef CONFIG_SCHED_CACHE
+#include <linux/kthread.h>
+
+#define SDS_WITNESS_CPU		0
+#define SDS_WITNESS_HOLD_MS	1500
+
+static int sds_witness_fn(void *unused)
+{
+	struct sched_domain *sd;
+	struct sched_domain_shared *sds;
+
+	while (!kthread_should_stop()) {
+		if (READ_ONCE(sds_window_cpu) != SDS_WITNESS_CPU) {
+			msleep(1);
+			continue;
+		}
+		WRITE_ONCE(sds_window_cpu, -1);
+
+		/* QS after the GP started, before entering the section. */
+		msleep(5);
+
+		rcu_read_lock();
+		sd = rcu_dereference_all(per_cpu(sd_llc, SDS_WITNESS_CPU));
+		if (sd) {
+			pr_info("SDS-LOAD: cpu=%d sd=%px\n",
+				SDS_WITNESS_CPU, (void *)sd);
+			msleep(SDS_WITNESS_HOLD_MS);
+			sds = rcu_dereference_all(sd->shared);
+			pr_info("SDS-WITNESS: cpu=%d sd=%px flags=%x shared=%px nr_busy=%d\n",
+				SDS_WITNESS_CPU, (void *)sd,
+				(unsigned int)READ_ONCE(sd->flags), (void *)sds,
+				sds ? atomic_read(&sds->nr_busy_cpus) : -1);
+		} else {
+			pr_info("SDS-LOAD: cpu=%d NULL\n", SDS_WITNESS_CPU);
+		}
+		rcu_read_unlock();
+		msleep(10);
+	}
+
+	return 0;
+}
+
+static int __init sds_witness_init(void)
+{
+	pr_info("SDS-WITNESS: starting, target cpu %d\n", SDS_WITNESS_CPU);
+	kthread_run(sds_witness_fn, NULL, "sds_witness");
+	return 0;
+}
+late_initcall(sds_witness_init);
+#endif