Skip to content

RFC Improve list integrity checking

Will Deacon kernel-hardening lkml 1 version Applied

Status from this message: The following commit has been merged into the locking/kcsan branch of tip:

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 RFC Latest21 patches 35 repliesApplied

Patches in v1 Applied

#Subject and filesSizeRepliesApplied
1/21list: Remove hlist_unhashed_lockless()include/linux/list.h+10 -232 replies
2/21list: Remove hlist_nulls_unhashed_lockless()include/linux/list_nulls.h+0 -142 replies
3/21list: Annotate lockless list primitives with data_race()include/linux/list.h include/linux/list_bl.h include/linux/list_nulls.h +1 more+12 -1116 replies
4/21timers: Use hlist_unhashed() instead of open-coding in timer_pending()include/linux/timer.h kernel/time/timer.c+4 -21 reply
5/21list: Comment missing WRITE_ONCE() in __list_del()include/linux/list.h+1 -01 reply
6/21list: Remove superfluous WRITE_ONCE() from hlist_nulls implementationinclude/linux/list_nulls.h+3 -31 reply
7/21Revert "list: Use WRITE_ONCE() when adding to lists and hlists"include/linux/list.h+3 -31 reply
8/21Revert "list: Use WRITE_ONCE() when initializing list_head structures"include/linux/list.h+1 -13 replies
9/21list: Remove unnecessary WRITE_ONCE() from hlist_bl_add_before()include/linux/list_bl.h+3 -32 replies
10/21kernel-hacking: Make DEBUG_{LIST,PLIST,SG,NOTIFIERS} non-debug optionsarch/arm/configs/tegra_defconfig arch/mips/configs/bigsur_defconfig arch/powerpc/configs/ppc6xx_defconfig +23 more+51 -551 reply
11/21list: Add integrity checking to hlist implementationinclude/linux/list.h include/linux/rculist.h lib/list_debug.c+162 -380 replies
12/21list: Poison ->next pointer for non-RCU deletion of 'hlist_nulls_node'include/linux/list_nulls.h+1 -01 reply
13/21list: Add integrity checking to hlist_nulls implementationinclude/linux/list_nulls.h lib/list_debug.c+70 -00 replies
14/21plist: Use CHECK_DATA_CORRUPTION instead of explicit {BUG,WARN}_ON()lib/plist.c+40 -231 reply
15/21list_bl: Use CHECK_DATA_CORRUPTION instead of custom BUG_ON() wrapperinclude/linux/list_bl.h include/linux/rculist_bl.h+42 -300 replies
16/21list_bl: Extend integrity checking in deletion routinesinclude/linux/list_bl.h+9 -10 replies
17/21linux/bit_spinlock.h: Include linux/processor.hinclude/linux/bit_spinlock.h+1 -02 replies
18/21list_bl: Move integrity checking out of lineinclude/linux/list_bl.h include/linux/rculist_bl.h lib/list_debug.c+35 -290 replies
19/21list_bl: Extend integrity checking to cover the same cases as 'hlist'lib/list_debug.c+40 -80 replies
20/21list: Format CHECK_DATA_CORRUPTION error messages consistentlylib/list_debug.c+9 -91 reply
21/21lkdtm: Extend list corruption checksdrivers/misc/lkdtm/Makefile drivers/misc/lkdtm/bugs.c drivers/misc/lkdtm/core.c +3 more+579 -740 replies

Reviews trailers per patch

9 of 21 patches have a Reviewed-by or Acked-by.

PatchGreg Kroah-HartmanPaul E. McKenney
1/21R-b A-b
2/21R-b A-b
3/21
4/21R-b
5/21R-b
6/21
7/21
8/21
9/21R-b
10/21R-b
11/21
12/21R-b
13/21
14/21R-b
15/21
16/21
17/21
18/21
19/21
20/21R-b
21/21

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v1 thread

Cover letter [RFC PATCH 00/21] Improve list integrity checking

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 <[email protected]>
Cc Greg Kroah-Hartman <[email protected]
Cc Jann Horn <[email protected]>
Cc Kees Cook <[email protected]>
Cc Maddie Stone <[email protected]>
Cc Marco Elver <[email protected]>
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>

--->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
Signature · 1 line
2.20.1