[PATCH 00/82] overflow: Refactor open-coded arithmetic wrap-around
From: Kees Cook
Date: Mon Jan 22 2024 - 20:16:13 EST
Hi,
In our continuing effort to eliminate root causes of flaws in the kernel,
this series is the start to providing a way to have sensible coverage
for catching unexpected arithmetic wrap-around.
A quick word on language: while discussing[1] the finer details of
the C standard's view on arithmetic, I was disabused of using the term
"overflow" when what I really mean is "wrap-around". When describing
security vulnerabilities, "overflow" is the common term and often used
interchangeably with "wrap-around". Strictly speaking, though, "overflow"
applies only to signed[2] and pointer[3] types, and "wrap-around" is for
unsigned[4]. An arithmetic "overflow" is considered undefined behavior,
which has caused our builds pain in the past, since "impossible"
conditions might get elided by the compiler. As a result, we build
with -fno-strict-overflow which coverts all "overflow" conditions into
"wrap-around" (i.e. 2s complement), regardless of type.
All this is to say I am discussing arithmetic wrap-around, which is
the condition where the value exceeds a type's maximum value (or goes
below its minimum value) and wraps around. I'm not interested in the
narrow definition of "undefined behavior" -- we need to stamp out the
_unexpected_ behavior, where the kernel operates on a pathological value
that wrapped around without the code author's intent.
As always, this is about being able disambiguate the intent of arithmetic
in the kernel. We intentionally use wrapping arithmetic in all kinds of
places, but we need to be able to annotate it as such going forward so
the compiler can distinguish when it needs to perform instrumentation
(when such instrumentation is enabled).
Getting back to my earlier mention of -fno-strict-overflow, the bulk of
the series is refactoring for a common code pattern in the kernel where
to test for potentially overflowing addition, the addition is performed,
and wrap-around is tested for. This is what originally[5] caused us to
enable -fno-strict-overflow:
var + offset < var
For these cases we can use either check_add_overflow() or
add_would_overflow(). These helpers will not trip the wrap-around
instrumentation, and do not depend on the whims of the compiler options.
(Note that I have no intention of removing -fno-strict-overflow any
time soon, if ever. As with all these kinds of changes, we need to
evolve our support for it, and we can't introduce undefined behavior
into the kernel.)
This series is mainly 3 parts:
- documentation, a coccinelle script, and new/improved helpers
- (re)introduction of the overflow sanitizers
- refactoring the "please wrap around to see if I wrapped around" tests
While this work is underway in the kernel, there will be complementary
work happening in GCC and Clang to expand the existing sanitizers
to behave correctly with -fno-strict-overflow. In the meantime, the
sanitizers are excluded from CONFIG_COMPILE_TEST.
-Kees
[1] https://gcc.gnu.org/pipermail/gcc-patches/2023-September/630578.html
[2] https://github.com/KSPP/linux/issues/26
[3] https://github.com/KSPP/linux/issues/344
[4] https://github.com/KSPP/linux/issues/27
[5] https://bugzilla.kernel.org/show_bug.cgi?id=12597
Kees Cook (82):
overflow: Expand check_add_overflow() for pointer addition
overflow: Introduce add_would_overflow()
overflow: Introduce add_wrap()
docs: deprecated.rst: deprecate open-coded arithmetic wrap-around
cocci: Refactor open-coded arithmetic wrap-around
overflow: Reintroduce signed and unsigned overflow sanitizers
overflow: Introduce CONFIG_UBSAN_POINTER_WRAP
iov_iter: Avoid wrap-around instrumentation in
copy_compat_iovec_from_user
select: Avoid wrap-around instrumentation in do_sys_poll()
locking/atomic/x86: Silence intentional wrapping addition
arm64: atomics: lse: Silence intentional wrapping addition
ipv4: Silence intentional wrapping addition
btrfs: Refactor intentional wrap-around calculation
smb: client: Refactor intentional wrap-around calculation
dma-buf: Refactor intentional wrap-around calculation
drm/nouveau/mmu: Refactor intentional wrap-around calculation
drm/vc4: Refactor intentional wrap-around calculation
ext4: Refactor intentional wrap-around calculation
fs: Refactor intentional wrap-around calculation
fpga: dfl: Refactor intentional wrap-around calculation
drivers/fsi: Refactor intentional wrap-around calculation
x86/sgx: Refactor intentional wrap-around calculation
KVM: Refactor intentional wrap-around calculation
KVM: arm64: vgic: Refactor intentional wrap-around calculation
KVM: SVM: Refactor intentional wrap-around calculation
buildid: Refactor intentional wrap-around calculation
m68k: Refactor intentional wrap-around calculation
niu: Refactor intentional wrap-around calculation
rds: Refactor intentional wrap-around calculation
s390/kexec_file: Refactor intentional wrap-around calculation
ARC: dw2 unwind: Refactor intentional wrap-around calculation
vringh: Refactor intentional wrap-around calculation
mm/vmalloc: Refactor intentional wrap-around calculation
ipc: Refactor intentional wrap-around calculation
ACPI: custom_method: Refactor intentional wrap-around test
agp: Refactor intentional wrap-around test
aio: Refactor intentional wrap-around test
arm: 3117/1: Refactor intentional wrap-around test
crypto: Refactor intentional wrap-around test
arm64: stacktrace: Refactor intentional wrap-around test
wil6210: Refactor intentional wrap-around test
bcachefs: Refactor intentional wrap-around test
bpf: Refactor intentional wrap-around test
btrfs: Refactor intentional wrap-around test
cifs: Refactor intentional wrap-around test
crypto: Refactor intentional wrap-around test
dm verity: Refactor intentional wrap-around test
drm/nouveau/mmu: Refactor intentional wrap-around test
drm/i915: Refactor intentional wrap-around test
drm/vc4: Refactor intentional wrap-around test
ext4: Refactor intentional wrap-around test
f2fs: Refactor intentional wrap-around test
fs: Refactor intentional wrap-around test
hpfs: Refactor intentional wrap-around test
kasan: Refactor intentional wrap-around test
usercopy: Refactor intentional wrap-around test
KVM: arm64: vgic-v3: Refactor intentional wrap-around test
s390/mm: Refactor intentional wrap-around test
lib/scatterlist: Refactor intentional wrap-around test
powerpc: Refactor intentional wrap-around test
scsi: mpt3sas: Refactor intentional wrap-around test
mwifiex: pcie: Refactor intentional wrap-around test
mm: Refactor intentional wrap-around test
netfilter: Refactor intentional wrap-around test
nios2: Refactor intentional wrap-around test
fs/ntfs3: Refactor intentional wrap-around test
ocfs2: Refactor intentional wrap-around test
PCI: Refactor intentional wrap-around test
perf tools: Refactor intentional wrap-around test
remoteproc: Refactor intentional wrap-around test
s390/mm: Refactor intentional wrap-around test
scsi: sd_zbc: Refactor intentional wrap-around test
sh: Refactor intentional wrap-around test
ARC: dw2 unwind: Refactor intentional wrap-around test
timekeeping: Refactor intentional wrap-around test
udf: Refactor intentional wrap-around test
virtio: Refactor intentional wrap-around test
mm/vmalloc: Refactor intentional wrap-around test
staging: vme_user: Refactor intentional wrap-around test
xen-netback: Refactor intentional wrap-around test
lib: zstd: Refactor intentional wrap-around test
mqueue: Refactor intentional wrap-around test
Documentation/process/deprecated.rst | 36 ++++++++
arch/arc/kernel/unwind.c | 7 +-
arch/arm/nwfpe/softfloat.c | 2 +-
arch/arm64/include/asm/atomic_lse.h | 8 +-
arch/arm64/include/asm/stacktrace/common.h | 2 +-
arch/arm64/kvm/vgic/vgic-kvm-device.c | 6 +-
arch/arm64/kvm/vgic/vgic-mmio-v3.c | 2 +-
arch/arm64/kvm/vgic/vgic-v2.c | 10 ++-
arch/m68k/kernel/sys_m68k.c | 5 +-
arch/nios2/kernel/sys_nios2.c | 2 +-
arch/powerpc/platforms/powernv/opal-prd.c | 2 +-
arch/powerpc/xmon/xmon.c | 2 +-
arch/s390/include/asm/stacktrace.h | 6 +-
arch/s390/kernel/machine_kexec_file.c | 5 +-
arch/s390/mm/gmap.c | 4 +-
arch/s390/mm/vmem.c | 2 +-
arch/sh/kernel/sys_sh.c | 2 +-
arch/x86/include/asm/atomic.h | 2 +-
arch/x86/kernel/cpu/sgx/ioctl.c | 6 +-
arch/x86/kvm/svm/sev.c | 5 +-
crypto/adiantum.c | 2 +-
drivers/acpi/custom_method.c | 2 +-
drivers/char/agp/generic.c | 2 +-
drivers/crypto/amcc/crypto4xx_alg.c | 2 +-
drivers/crypto/axis/artpec6_crypto.c | 2 +-
drivers/dma-buf/dma-buf.c | 7 +-
drivers/fpga/dfl.c | 5 +-
drivers/fsi/fsi-core.c | 6 +-
drivers/gpu/drm/i915/i915_vma.c | 2 +-
drivers/gpu/drm/nouveau/nvkm/subdev/mmu/vmm.c | 8 +-
drivers/gpu/drm/vc4/vc4_validate.c | 7 +-
drivers/md/dm-switch.c | 2 +-
drivers/md/dm-verity-target.c | 2 +-
drivers/md/dm-writecache.c | 2 +-
drivers/net/ethernet/sun/niu.c | 5 +-
drivers/net/wireless/ath/wil6210/wmi.c | 2 +-
drivers/net/wireless/marvell/mwifiex/pcie.c | 6 +-
drivers/net/xen-netback/hash.c | 2 +-
drivers/pci/pci.c | 2 +-
drivers/remoteproc/pru_rproc.c | 2 +-
drivers/remoteproc/remoteproc_elf_loader.c | 2 +-
drivers/remoteproc/remoteproc_virtio.c | 4 +-
drivers/scsi/mpt3sas/mpt3sas_ctl.c | 2 +-
drivers/scsi/sd_zbc.c | 2 +-
drivers/staging/vme_user/vme.c | 2 +-
drivers/vhost/vringh.c | 8 +-
drivers/virtio/virtio_pci_modern_dev.c | 4 +-
fs/aio.c | 2 +-
fs/bcachefs/bkey.c | 4 +-
fs/bcachefs/fs.c | 2 +-
fs/bcachefs/quota.c | 2 +-
fs/bcachefs/util.c | 2 +-
fs/btrfs/extent_map.c | 6 +-
fs/btrfs/extent_map.h | 6 +-
fs/btrfs/ordered-data.c | 2 +-
fs/ext4/block_validity.c | 2 +-
fs/ext4/extents.c | 5 +-
fs/ext4/resize.c | 2 +-
fs/f2fs/file.c | 2 +-
fs/f2fs/verity.c | 2 +-
fs/hpfs/alloc.c | 2 +-
fs/ntfs3/record.c | 4 +-
fs/ocfs2/resize.c | 2 +-
fs/read_write.c | 8 +-
fs/remap_range.c | 2 +-
fs/select.c | 13 +--
fs/smb/client/readdir.c | 5 +-
fs/smb/client/smb2pdu.c | 4 +-
fs/udf/balloc.c | 4 +-
include/linux/compiler_types.h | 29 +++++-
include/linux/overflow.h | 76 +++++++++++++++-
ipc/mqueue.c | 2 +-
ipc/shm.c | 6 +-
kernel/bpf/verifier.c | 12 +--
kernel/time/timekeeping.c | 2 +-
lib/Kconfig.ubsan | 27 ++++++
lib/buildid.c | 6 +-
lib/iov_iter.c | 5 +-
lib/overflow_kunit.c | 77 ++++++++++++++--
lib/scatterlist.c | 2 +-
lib/test_ubsan.c | 82 +++++++++++++++++
lib/ubsan.c | 89 +++++++++++++++++++
lib/ubsan.h | 5 ++
lib/zstd/decompress/zstd_decompress.c | 4 +-
mm/kasan/generic.c | 2 +-
mm/kasan/sw_tags.c | 2 +-
mm/memory.c | 4 +-
mm/mmap.c | 2 +-
mm/mremap.c | 2 +-
mm/nommu.c | 4 +-
mm/usercopy.c | 2 +-
mm/util.c | 2 +-
mm/vmalloc.c | 7 +-
net/ipv4/route.c | 8 +-
net/netfilter/xt_u32.c | 4 +-
net/rds/info.c | 6 +-
scripts/Makefile.ubsan | 3 +
.../coccinelle/misc/add_would_overflow.cocci | 70 +++++++++++++++
tools/perf/util/dso.c | 2 +-
tools/perf/util/unwind-libdw.c | 2 +-
tools/perf/util/unwind-libunwind-local.c | 2 +-
virt/kvm/coalesced_mmio.c | 6 +-
102 files changed, 680 insertions(+), 167 deletions(-)
create mode 100644 scripts/coccinelle/misc/add_would_overflow.cocci
--
2.34.1