kSTEP: Kernel Scheduler Test and Evaluation Platform

Source code for kSTEP: Characterization and Deterministic Testing of Linux CPU Scheduler Bugs. (OSDI '26).

Tingjia Cao, Shawn Wanxiang Zhong, Caeden Whitaker, Ke Han, Andrea Arpaci-Dusseau, and Remzi Arpaci-Dusseau

📄 Paper  ·  💻 Code (osdi26)  ·  🌐 Website  ·  📚 Study  ·  📊 Results

🚀 Getting Started

# 📦 Clone the repository (add `--branch osdi26` to reproduce the paper exactly)
git clone --recurse-submodules https://github.com/kstep-dev/kstep && cd kstep

# 💾 Install dependencies
./setup.sh

# 🐞 Reproduce bugs
# ./kstep.sh reproduce <name|all|extra> [--steps buggy fixed plot]
#   1. Checks out the buggy and fixed kernels
#   2. Builds and runs the bug's driver on each
#   3. Plots the two traces
./kstep.sh reproduce sync_wakeup

📊 Results

kSTEP Driver, Fix, and Output	Figure
sync_wakeup.c Official Fix: linux@aa3ee4f Our Fix: sync_wakeup.patch buggy.jsonl, fixed.jsonl
vruntime_overflow.c Fix: linux@bbce3de buggy.jsonl, fixed.jsonl
freeze.c Fix: linux@cd9626e buggy.jsonl, fixed.jsonl
extra_balance.c Fix: linux@6d7e478 buggy.jsonl, fixed.jsonl
driver_util_avg.c Fix: linux@17e3e88 buggy.jsonl, fixed.jsonl
long_balance.c Fix: linux@2feab24 buggy.jsonl, fixed.jsonl
lag_vruntime.c Fix: linux@5068d84 buggy.jsonl, fixed.jsonl
even_idle_cpu.c Fix: even_idle_cpu.patch buggy.jsonl, fixed.jsonl
local_group_imbalance.c Fix: fix_local_group_imbalanced.patch buggy.jsonl, fixed.jsonl
util_avg_jump.c Fix: fix_util_avg_jump.patch buggy.jsonl, fixed.jsonl
rt_runtime_toggle.c Fix: linux@9b58e97 buggy.jsonl, fixed.jsonl
uclamp_inversion.c Fix: linux@0213b70 buggy.jsonl, fixed.jsonl
h_nr_runnable.c Fix: linux@3429dd5 buggy.jsonl, fixed.jsonl

💻 Running Your Own Drivers

For driver development, please refer to AGENTS.md for recommended workflow and tips.

🐧 Checkout Linux source code

./kstep.sh checkout <ref> [<name>] [--git] [--patch <file>] [--keep-current]

• <ref>: Linux tag (e.g., v6.14) or commit hash (e.g., 6d7e478, 5068d84~1).
• Default: download a tarball from kernel.org / GitHub (fast, one-shot). --git: add a worktree of build/master (multi-version dev, supports git log/git diff).
• Example: ./kstep.sh checkout v6.14 foo_buggy checks out Linux v6.14 under build/foo_buggy/linux/ and points build/current at build/foo_buggy/.

🛠️ Build kSTEP

./kstep.sh build [<name>]                      # kmod + user + rootfs.cpio; builds the kernel first if needed
./kstep.sh build [<name>] --linux [--config F]  # reconfigure and rebuild the kernel; run after Linux file changes

• [<name>]: build directory under build/; defaults to whatever build/current points to. A bug's build (<bug>_buggy, <bug>_fixed) or a Linux version (v6.18) is checked out first if missing.

🏃‍♂️ Run kSTEP

./kstep.sh run [<name>] [<driver>] [--num-cpus <n>] [--mem-mb <mb>] [-o <dir>] [-i <file>]

• [<name>]: kernel build to run against (defaults to build/current). A bug's build, <bug>_buggy or <bug>_fixed, brings the bug's driver and machine from bugs.yaml.

• [<driver>]: driver to run (see *.c files in kmod/drivers/); defaults to cli, an interactive session: type commands (listed at the top of kmod/cli.c), see the machine after each. -i <file> or a pipe scripts one.

• [-o <dir>]: subdir under results/ for output; defaults to a timestamped tmp_* dir. results/latest symlinks to it.

• --debug starts the guest stopped with a gdb stub; ./kstep.sh gdb [<name>] attaches.

• Example: ./kstep.sh run sync_wakeup_buggy runs the sync_wakeup driver on its buggy kernel, checking it out and building it first if needed.

📁 Directory Structure

• kmod/: Kernel module (kmod.ko) loaded at boot

  • drivers/: bug-specific drivers (one .c per bug)
  • checkers/: rules over scheduler state and decisions, enabled by the cli's check verb
  • cli.c: interactive driver behind the website playground (text commands in and JSON replies out on the virtio console port)
  • cpu.c: topology, capacity and frequency setup, behind the cpu-topo/cpu-cap/cpu-freq cli verbs
  • driver.h: public API for drivers (task creation, ticking, cgroups, etc.)
  • internal.h and other top-level *.c: framework primitives

• user/: Minimal userspace (user.c) that mounts filesystems and loads kmod.ko

• linux/: Project-static kernel files (committed to git)

  • config.kstep*: Kconfig fragments merged into the build
  • cov.c, Kconfig.kstep, Makefile.kstep: scheduler-coverage instrumentation
  • *.patch: Fixes for specific bugs

• build/: Per-kernel build artifacts (gitignored, regenerable)

  • current: symlink to the active <name>/ (set by kstep checkout)
  • master/: kernel clone reused by kstep checkout --git
  • user: statically linked userspace binary
  • <name>/: kernel (the image QEMU boots: the bzImage on x86, the Image on arm64; plus vmlinux for gdb/addr2line) and rootfs.cpio (kmod.ko + user); linux/ source tree; kmod/ module build dir with kmod.ko and the clangd compile_commands.json (the project root symlinks to it)

• results/: Run outputs. See results/README.md. repro_<bug>/ is tracked; tmp_* are gitignored. The fuzzer's per-client runs land in fuzz_<build>_<n>/.

• crates/: the Rust tooling. core/ is what the website's wasm decoder shares with the binaries (the kmod/shm.h decoder, generated from the header, and the QEMU command line); kstep/ is the kstep command (./kstep.sh): checkout, build, run, reproduce, viz; fuzz/ is the LibAFL fuzzer (./kstep-fuzz.sh <bug>), a host-side client of the cli driver, with corpora and findings under fuzz/ (gitignored)

  • the earlier in-guest fuzzer is kept for reference in docs/archive/old_fuzzer/

• scripts/: the plot scripts (Python, self-contained: uv run --script scripts/plot_<format>.py <bug>), which kstep reproduce runs.

• bugs.yaml: one entry per bug -- how to build, run, reproduce and fuzz it; read by kstep run, kstep reproduce and the fuzzer