Hi all,
Linked lists appear extensively across the kernel tree in some form or
another because they are simple to use and offer efficient addition and
removal routines. Unfortunately, they are also an attractive target for
people exploiting memory corruption bugs since not only are linked lists
susceptible to use-after-free (UAF) issues when used with non-counted
references to objects [1], but the APIs can also be abused as powerful
stepping stones towards obtaining arbitrary read/write of kernel memory.
A concrete example with an excellent write-up is the exploitation of
CVE-2019-2215 ("Bad Binder"):
https://googleprojectzero.blogspot.com/2019/11/bad-binder-android-in-wild-exploit.html
Some other examples are CVE-2015-3636 ("pingpongroot") and a variant of
CVE-2019-2025 ("waterdrop").
Before you go and throw away all your computers: fear not! It is common for
distributions to enable CONFIG_DEBUG_LIST, which prevents many of these
attacks with very little runtime overhead by sanity checking node pointers
during add() and del() operations.
Anyway, that's some background. Initially, I just set out to rename
CONFIG_DEBUG_LIST to something less "debuggy", a bit like we did for
CONFIG_DEBUG_{RODATA,MODULE_RONX} in 0f5bf6d0afe4. However, I quickly ran
into some other issues:
1. The KCSAN work has led to some unusual WRITE_ONCE() additions to
the list code. These make it difficult to reason about which list
functions can run concurrently with one another, which in turn makes
it difficult to write sanity checks without locks.
Patches 1-9 try to sort this out.
2. 'hlist' is missing checks, despite being the structure targetted
by the "pingpongroot" attack mentioned earlier on. The same goes
for 'hlist_nulls'.
Patches 11-13 add these checks.
3. 'list_bl' performs some partial inline checking.
Patches 16, 18 and 19 extend this checking and move it out-of-line
to be consistent with the other list checking operations.
4. The LKDTM list tests are fairly limited.
Patch 21 adds tests for all of the new checks.
The other patches do the rename and generally tidy things up to keep the
different list implementations consistent with each other. Due to issue (1),
this series is based on tip/locking/kcsan [2]
Jann previously made a comment that renaming the CONFIG options could have
unexpected results for people using an old config. In fact, building the
'oldconfig' target will prompt you about the new options, so I don't think
this is a huge concern. I did try to find a way to leave the old options as
dummy symbols, but it just cluttered the Kconfig (a bit like the approach
taken by NETFILTER_XT_MATCH_CONNMARK).
Cheers,
Will
[1] https://lore.kernel.org/lkml/?q=%28%22KASAN%3A+use-after-free+in+__list_add_valid%22+OR+%22KASAN%3A+use-after-free+in+__list_del_entry_valid%22%29+-s%3A%22Re%3A%22+-s%3A%22%5BPATCH%22
[2] https://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git/log/?h=locking/kcsan
Cc: Eric Dumazet <edumazet@xxxxxxxxxx>
Cc: Greg Kroah-Hartman <gregkh@xxxxxxxxxxxxxxxxxxx
Cc: Jann Horn <jannh@xxxxxxxxxx>
Cc: Kees Cook <keescook@xxxxxxxxxxxx>
Cc: Maddie Stone <maddiestone@xxxxxxxxxx>
Cc: Marco Elver <elver@xxxxxxxxxx>
Cc: Paul E. McKenney <paulmck@xxxxxxxxxx>
Cc: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
Cc: Thomas Gleixner <tglx@xxxxxxxxxxxxx>
Cc: kernel-team@xxxxxxxxxxx
Cc: kernel-hardening@xxxxxxxxxxxxxxxxxx
--->8
Will Deacon (21):
list: Remove hlist_unhashed_lockless()
list: Remove hlist_nulls_unhashed_lockless()
list: Annotate lockless list primitives with data_race()
timers: Use hlist_unhashed() instead of open-coding in timer_pending()
list: Comment missing WRITE_ONCE() in __list_del()
list: Remove superfluous WRITE_ONCE() from hlist_nulls implementation
Revert "list: Use WRITE_ONCE() when adding to lists and hlists"
Revert "list: Use WRITE_ONCE() when initializing list_head structures"
list: Remove unnecessary WRITE_ONCE() from hlist_bl_add_before()
kernel-hacking: Make DEBUG_{LIST,PLIST,SG,NOTIFIERS} non-debug options
list: Add integrity checking to hlist implementation
list: Poison ->next pointer for non-RCU deletion of 'hlist_nulls_node'
list: Add integrity checking to hlist_nulls implementation
plist: Use CHECK_DATA_CORRUPTION instead of explicit {BUG,WARN}_ON()
list_bl: Use CHECK_DATA_CORRUPTION instead of custom BUG_ON() wrapper
list_bl: Extend integrity checking in deletion routines
linux/bit_spinlock.h: Include linux/processor.h
list_bl: Move integrity checking out of line
list_bl: Extend integrity checking to cover the same cases as 'hlist'
list: Format CHECK_DATA_CORRUPTION error messages consistently
lkdtm: Extend list corruption checks
arch/arm/configs/tegra_defconfig | 2 +-
arch/mips/configs/bigsur_defconfig | 2 +-
arch/powerpc/configs/ppc6xx_defconfig | 4 +-
arch/powerpc/configs/ps3_defconfig | 2 +-
arch/powerpc/configs/skiroot_defconfig | 4 +-
arch/riscv/configs/defconfig | 6 +-
arch/riscv/configs/rv32_defconfig | 6 +-
arch/s390/configs/debug_defconfig | 4 +-
arch/sh/configs/polaris_defconfig | 2 +-
arch/sh/configs/rsk7203_defconfig | 4 +-
arch/sh/configs/se7206_defconfig | 2 +-
drivers/gpu/drm/radeon/mkregtable.c | 2 +-
drivers/misc/lkdtm/Makefile | 1 +
drivers/misc/lkdtm/bugs.c | 68 ---
drivers/misc/lkdtm/core.c | 31 +-
drivers/misc/lkdtm/list.c | 489 ++++++++++++++++++
drivers/misc/lkdtm/lkdtm.h | 33 +-
drivers/staging/wfx/fwio.c | 2 +-
drivers/staging/wfx/hwio.c | 2 +-
include/linux/bit_spinlock.h | 1 +
include/linux/list.h | 95 ++--
include/linux/list_bl.h | 52 +-
include/linux/list_nulls.h | 50 +-
include/linux/llist.h | 2 +-
include/linux/plist.h | 4 +-
include/linux/rculist.h | 80 +--
include/linux/rculist_bl.h | 17 +-
include/linux/scatterlist.h | 6 +-
include/linux/timer.h | 5 +-
kernel/notifier.c | 2 +-
kernel/time/timer.c | 1 +
lib/Kconfig.debug | 24 +-
lib/Makefile | 2 +-
lib/list_debug.c | 200 ++++++-
lib/plist.c | 67 ++-
tools/include/linux/list.h | 4 +-
tools/testing/selftests/lkdtm/tests.txt | 31 +-
.../selftests/wireguard/qemu/debug.config | 6 +-
tools/virtio/linux/scatterlist.h | 4 +-
39 files changed, 1034 insertions(+), 285 deletions(-)
create mode 100644 drivers/misc/lkdtm/list.c
--
2.20.1
