| Message ID | 20240122235208.work.748-kees@kernel.org (mailing list archive) |
|---|---|
| Headers | show |
| Series | overflow: Refactor open-coded arithmetic wrap-around | expand |
On Mon, Jan 22, 2024 at 04:26:35PM -0800, Kees Cook wrote: > 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: This all seems fine, but... Rust already has this at the type system level.... I know you're not one of the people bringing bickering into the Rust threads, so I'm wondering if perhaps your secret plan is to annoy the die hard "I want everything to be fast with razor blades everywhere" C programmers enough to finally get onboard the "let's just switch to a language with less razor wire" train.
On January 22, 2024 6:22:13 PM PST, Kent Overstreet <kent.overstreet@linux.dev> wrote: >On Mon, Jan 22, 2024 at 04:26:35PM -0800, Kees Cook wrote: >> 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. >> >This all seems fine, but... Rust already has this at the type system >level.... > >I know you're not one of the people bringing bickering into the Rust >threads, so I'm wondering if perhaps your secret plan is to annoy the >die hard "I want everything to be fast with razor blades everywhere" C >programmers enough to finally get onboard the "let's just switch to a >language with less razor wire" train. I don't want to annoy anyone, but yeah, in the process of getting rid of dangerous stuff we do end up asking people to make changes they're not used to. I hope to make it as easy as possible, though. I'm a big fan of Rust, but I know it's not going to happen over night; there is a LOT of C code in Linux. :) I look at making the kernel safer by removing as many C foot-guns as possible. As we remove the ambiguities in C that lead to vulnerabilities, we'll eventually meet halfway with the new Rust code. -Kees
On Mon, Jan 22, 2024 at 04:26:35PM -0800, Kees Cook wrote: > Hi, Hi Kees, > 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. With that in mind, I note that this patch primarily modifies addition operations, but leaves subtraction operations unchanged (even though those permit the value to go below the minimum, or above the maximum if a negative value is used as the subtrahend). Shouldn't we address both at the same time? I'll note that in many places the same logic is used for both the add and sub, and can legitimately overflow or underflow; I hope that whatever we use to suppress overflow warnings also ignores underflow. [...] Looking at the diffstat, I think you've missed a few places: > 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 +++++- This misses the include/asm-generic/{atomic,atomic64}.h implementations. This also misses the include/linux/atomic/atomic-arch-fallback.h implementations. Those are generated from the scripts/atomic/fallbacks/* templates, and you'll need to adjust at least fetch_add_unless and inc_unless_negative. As noted on other patches, my preference is to use add_wrap() in those. > 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 ++++++ This misses lib/atomic64.c. Thanks, Mark.
On Tue, Jan 23, 2024 at 09:46:35AM +0000, Mark Rutland wrote: > With that in mind, I note that this patch primarily modifies addition > operations, but leaves subtraction operations unchanged (even though those > permit the value to go below the minimum, or above the maximum if a negative > value is used as the subtrahend). Right, this was kind of a "first pass" on what I'd found so far. > Shouldn't we address both at the same time? I'll note that in many places the > same logic is used for both the add and sub, and can legitimately overflow or > underflow; I hope that whatever we use to suppress overflow warnings also > ignores underflow. > > [...] > > Looking at the diffstat, I think you've missed a few places: > > [...] > > This misses the include/asm-generic/{atomic,atomic64}.h implementations. > > This also misses the include/linux/atomic/atomic-arch-fallback.h > implementations. Those are generated from the scripts/atomic/fallbacks/* > templates, and you'll need to adjust at least fetch_add_unless and > inc_unless_negative. As noted on other patches, my preference is to use > add_wrap() in those. > [...] > This misses lib/atomic64.c. Thanks! I'll take a closer look at places we can use the helpers on the atomics. -Kees
On Tue, Jan 23, 2024 at 09:46:35AM +0000, Mark Rutland wrote: > This also misses the include/linux/atomic/atomic-arch-fallback.h > implementations. Those are generated from the scripts/atomic/fallbacks/* > templates, and you'll need to adjust at least fetch_add_unless and > inc_unless_negative. As noted on other patches, my preference is to use > add_wrap() in those. How do I regenerate the header files using the templates? I found a script, but its use eluded me, and it doesn't seem wired up to the top-level Makefile? Maybe I missed something obvious...
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