We've used to detect integer overflows by causing an overflow and testing the
result. For example, to test for addition overflow we would:
if (a + b < a)
/* Overflow detected */
While it works, this is actually an undefined behaviour and we're not
guaranteed to have integers overflowing this way. GCC5 has introduced
built in macros (which existed in Clang/LLVM for a while) to test for
addition, subtraction and multiplication overflows.
Rather than keep relying on the current behaviour of GCC, let's take
it's olive branch and test for overflows by using the builtin
functions.
Changing existing code is simple and can be done using Coccinelle:
@@ expression X; expression Y; expression Z; constant C; @@
(
- X + Y < Y
+ check_add_overflow(X, Y)
|
- X - Y > X
+ check_sub_overflow(X, Y)
|
- X != 0 && Y > C / X
+ check_mul_overflow(X, Y, C)
)
Which also makes the code much more clearer, for example:
- if (addr + len < addr)
+ if (check_add_overflow(addr, len))
return -EFAULT;
Signed-off-by: Sasha Levin <[email protected]>
---
The patch following this one is an example of how changes to existing
code will look like. It's just one patch out of about 40 which are very
simiar - so to avoid lots of useless mails I'll avoid sending them until
this patch looks ok.
include/linux/compiler-gcc5.h | 8 ++++++++
include/linux/compiler.h | 11 +++++++++++
2 files changed, 19 insertions(+)
diff --git a/include/linux/compiler-gcc5.h b/include/linux/compiler-gcc5.h
index c8c5659..9d39f66 100644
--- a/include/linux/compiler-gcc5.h
+++ b/include/linux/compiler-gcc5.h
@@ -63,3 +63,11 @@
#define __HAVE_BUILTIN_BSWAP64__
#define __HAVE_BUILTIN_BSWAP16__
#endif /* CONFIG_ARCH_USE_BUILTIN_BSWAP */
+
+__maybe_unused static unsigned int gcc_overflow_dummy;
+#define check_add_overflow(A, B) \
+ __builtin_add_overflow((A), (B), &gcc_overflow_dummy)
+#define check_sub_overflow(A, B) \
+ __builtin_sub_overflow((A), (B), &gcc_overflow_dummy)
+#define check_mul_overflow(A, B, C) \
+ __builtin_mul_overflow((A), (B), &gcc_overflow_dummy)
diff --git a/include/linux/compiler.h b/include/linux/compiler.h
index 934a834..7f15a18 100644
--- a/include/linux/compiler.h
+++ b/include/linux/compiler.h
@@ -388,4 +388,15 @@ void ftrace_likely_update(struct ftrace_branch_data *f, int val, int expect);
# define __kprobes
# define nokprobe_inline inline
#endif
+
+#ifndef check_add_overflow
+#define check_add_overflow(A, B) (((A) + (B)) < (A))
+#endif
+#ifndef check_sub_overflow
+#define check_sub_overflow(A, B) (((A) - (B)) > (A))
+#endif
+#ifndef check_mul_overflow
+#define check_mul_overflow(A, B, C) ((A) != 0 && (B) > (C) / (A))
+#endif
+
#endif /* __LINUX_COMPILER_H */
--
1.7.10.4
Detect integer overflows using safe operations rather than relying on
undefined behaviour.
Signed-off-by: Sasha Levin <[email protected]>
---
virt/kvm/eventfd.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/virt/kvm/eventfd.c b/virt/kvm/eventfd.c
index 148b239..2eb044f 100644
--- a/virt/kvm/eventfd.c
+++ b/virt/kvm/eventfd.c
@@ -790,7 +790,7 @@ kvm_assign_ioeventfd(struct kvm *kvm, struct kvm_ioeventfd *args)
}
/* check for range overflow */
- if (args->addr + args->len < args->addr)
+ if (check_add_overflow(args->len, args->addr))
return -EINVAL;
/* check for extra flags that we don't understand */
--
1.7.10.4
2014-11-26 17:00 GMT+03:00 Sasha Levin <[email protected]>:
> We've used to detect integer overflows by causing an overflow and testing the
> result. For example, to test for addition overflow we would:
>
> if (a + b < a)
> /* Overflow detected */
>
> While it works, this is actually an undefined behaviour and we're not
There is a case when such check doesn't work. If a == INT_MIN then (a + b < a)
always will be false.
> guaranteed to have integers overflowing this way. GCC5 has introduced
> built in macros (which existed in Clang/LLVM for a while) to test for
> addition, subtraction and multiplication overflows.
>
> Rather than keep relying on the current behaviour of GCC, let's take
> it's olive branch and test for overflows by using the builtin
> functions.
>
> Changing existing code is simple and can be done using Coccinelle:
>
> @@ expression X; expression Y; expression Z; constant C; @@
> (
> - X + Y < Y
> + check_add_overflow(X, Y)
> |
> - X - Y > X
> + check_sub_overflow(X, Y)
> |
> - X != 0 && Y > C / X
> + check_mul_overflow(X, Y, C)
> )
>
> Which also makes the code much more clearer, for example:
>
> - if (addr + len < addr)
> + if (check_add_overflow(addr, len))
> return -EFAULT;
>
> Signed-off-by: Sasha Levin <[email protected]>
> ---
>
> The patch following this one is an example of how changes to existing
> code will look like. It's just one patch out of about 40 which are very
> simiar - so to avoid lots of useless mails I'll avoid sending them until
> this patch looks ok.
>
> include/linux/compiler-gcc5.h | 8 ++++++++
> include/linux/compiler.h | 11 +++++++++++
> 2 files changed, 19 insertions(+)
>
> diff --git a/include/linux/compiler-gcc5.h b/include/linux/compiler-gcc5.h
> index c8c5659..9d39f66 100644
> --- a/include/linux/compiler-gcc5.h
> +++ b/include/linux/compiler-gcc5.h
> @@ -63,3 +63,11 @@
> #define __HAVE_BUILTIN_BSWAP64__
> #define __HAVE_BUILTIN_BSWAP16__
> #endif /* CONFIG_ARCH_USE_BUILTIN_BSWAP */
> +
> +__maybe_unused static unsigned int gcc_overflow_dummy;
To make you macro bellow work correctly, type of gcc_overflow_dummy
variable has to be typeof(A + B)
E.g. currently you macros will return true for 0xffffffffULL + 1ULL.
> +#define check_add_overflow(A, B) \
> + __builtin_add_overflow((A), (B), &gcc_overflow_dummy)
> +#define check_sub_overflow(A, B) \
> + __builtin_sub_overflow((A), (B), &gcc_overflow_dummy)
> +#define check_mul_overflow(A, B, C) \
> + __builtin_mul_overflow((A), (B), &gcc_overflow_dummy)
> diff --git a/include/linux/compiler.h b/include/linux/compiler.h
> index 934a834..7f15a18 100644
> --- a/include/linux/compiler.h
> +++ b/include/linux/compiler.h
> @@ -388,4 +388,15 @@ void ftrace_likely_update(struct ftrace_branch_data *f, int val, int expect);
> # define __kprobes
> # define nokprobe_inline inline
> #endif
> +
> +#ifndef check_add_overflow
> +#define check_add_overflow(A, B) (((A) + (B)) < (A))
> +#endif
> +#ifndef check_sub_overflow
> +#define check_sub_overflow(A, B) (((A) - (B)) > (A))
> +#endif
> +#ifndef check_mul_overflow
> +#define check_mul_overflow(A, B, C) ((A) != 0 && (B) > (C) / (A))
> +#endif
> +
> #endif /* __LINUX_COMPILER_H */
> --
> 1.7.10.4
>
2014-11-26 17:00 GMT+03:00 Sasha Levin <[email protected]>:
> Detect integer overflows using safe operations rather than relying on
> undefined behaviour.
>
Unsigned overflow is defined.
args->addr and args->len both unsigned, so there is no UB here.
> Signed-off-by: Sasha Levin <[email protected]>
> ---
> virt/kvm/eventfd.c | 2 +-
> 1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/virt/kvm/eventfd.c b/virt/kvm/eventfd.c
> index 148b239..2eb044f 100644
> --- a/virt/kvm/eventfd.c
> +++ b/virt/kvm/eventfd.c
> @@ -790,7 +790,7 @@ kvm_assign_ioeventfd(struct kvm *kvm, struct kvm_ioeventfd *args)
> }
>
> /* check for range overflow */
> - if (args->addr + args->len < args->addr)
> + if (check_add_overflow(args->len, args->addr))
> return -EINVAL;
>
> /* check for extra flags that we don't understand */
> --
> 1.7.10.4
>
On 11/26/2014 12:50 PM, Andrey Ryabinin wrote:
> 2014-11-26 17:00 GMT+03:00 Sasha Levin <[email protected]>:
>> > Detect integer overflows using safe operations rather than relying on
>> > undefined behaviour.
>> >
> Unsigned overflow is defined.
> args->addr and args->len both unsigned, so there is no UB here.
>
Good point. Do you think there's an advantage in using GCC's overflow
checker in this case?
Thanks,
Sasha
On Wed, Nov 26, 2014 at 9:55 AM, Sasha Levin <[email protected]> wrote:
>
> Good point. Do you think there's an advantage in using GCC's overflow
> checker in this case?
No. However, if your coccinelle script can be changed to verify that
the type of the expression is unsigned, _that_ would be useful.
And the "multiplication overflow" may actually be a way to generate
better code. Possibly. I'm not entirely sure exactly what gcc actually
does. How many multiplication overflow tests do we actually have,
though?
For plain unsigned additions, "a + b < a" is already optimal (ie gcc
realizes it's an overflow check and generates a test against the carry
flag, at least when it doesn't screw up)
Linus
On 11/26/2014 12:55 PM, Linus Torvalds wrote:
> On Nov 26, 2014 6:00 AM, "Sasha Levin" <[email protected] <mailto:[email protected]>> wrote:
>>
>> We've used to detect integer overflows by causing an overflow and testing the
>> result. For example, to test for addition overflow we would:
>>
>> if (a + b < a)
>> /* Overflow detected */
>>
>> While it works, this is actually an undefined behaviour and we're not
>> guaranteed to have integers overflowing this way.
>
> Bullshit.
>
> Integer overflow is completely well defined in unsigned types.
>
> Don't make up things like this.
Yes, I messed up and picked case where both types are unsigned in my example
patch. Apologies.
The kernel still has it's share of *signed* integer overflows. Example? fadvise64_64():
loff_t offset, len;
[...]
loff_t endbyte;
[...]
/* Careful about overflows. Len == 0 means "as much as possible" */
endbyte = offset + len;
if (!len || endbyte < len)
endbyte = -1;
else
endbyte--; /* inclusive */
In essence, it's checking (offset + len < len), all of which are signed.
Thanks,
Sasha
On Wed, Nov 26, 2014 at 10:50 AM, Sasha Levin <[email protected]> wrote:
>
> The kernel still has it's share of *signed* integer overflows. Example? fadvise64_64():
Yes, those would definitely be worth fixing.
[ Although quite frankly, since I know gcc already knows about the
whole "check for overflow" pattern, from a QoI standpoint it is sad
that it then might optimize it away. Kind of like how it would trust
the type-based strict alias analysis more than the obvious *static*
alias analysis. Oh well ]
I don't think coccinelle can do signedness checks, though, especially
of the kind that are hidden deep behind some typedef like "loff_t".
Maybe I'm wrong. Maybe smatch can? Adding Dan Carpenter to the cc..
Linus
On 11/26/2014 01:23 PM, Linus Torvalds wrote:
> On Wed, Nov 26, 2014 at 9:55 AM, Sasha Levin <[email protected]> wrote:
>> >
>> > Good point. Do you think there's an advantage in using GCC's overflow
>> > checker in this case?
> No. However, if your coccinelle script can be changed to verify that
> the type of the expression is unsigned, _that_ would be useful.
I'm pretty sure that this is something GCC will warn you about in the
compilation stage.
> And the "multiplication overflow" may actually be a way to generate
> better code. Possibly. I'm not entirely sure exactly what gcc actually
> does. How many multiplication overflow tests do we actually have,
> though?
Well, there are two straightforward checks in the kcalloc() family. They're
not the issue though. The problem is the *unchecked* *signed* integer overflows
lurking around.
kernel/time/ntp.c:process_adjtimex_modes():
if (txc->modes & ADJ_FREQUENCY) {
time_freq = txc->freq * PPM_SCALE; <=== Undefined overflow
time_freq = min(time_freq, MAXFREQ_SCALED);
time_freq = max(time_freq, -MAXFREQ_SCALED);
/* update pps_freq */
pps_set_freq(time_freq);
}
The multiplication is between signed integers, and it overflows (user triggerable).
Thanks,
Sasha
On Wed, Nov 26, 2014 at 11:06 AM, Sasha Levin <[email protected]> wrote:
>
> I'm pretty sure that this is something GCC will warn you about in the
> compilation stage.
It does? I've never seen it, but maybe it's a new thing.
The gcc signedness warnings have historically been so wretched that
it's just sad, and they have to be turned off.
> kernel/time/ntp.c:process_adjtimex_modes():
>
> if (txc->modes & ADJ_FREQUENCY) {
> time_freq = txc->freq * PPM_SCALE; <=== Undefined overflow
> time_freq = min(time_freq, MAXFREQ_SCALED);
> time_freq = max(time_freq, -MAXFREQ_SCALED);
> /* update pps_freq */
> pps_set_freq(time_freq);
> }
>
> The multiplication is between signed integers, and it overflows (user triggerable).
Well, we check that the end result - overflowed or not - is in a sane
range. So this might fall under the heading of "user gets what he asks
for".
Linus
On 11/26/2014 02:12 PM, Linus Torvalds wrote:
>> kernel/time/ntp.c:process_adjtimex_modes():
>> >
>> > if (txc->modes & ADJ_FREQUENCY) {
>> > time_freq = txc->freq * PPM_SCALE; <=== Undefined overflow
>> > time_freq = min(time_freq, MAXFREQ_SCALED);
>> > time_freq = max(time_freq, -MAXFREQ_SCALED);
>> > /* update pps_freq */
>> > pps_set_freq(time_freq);
>> > }
>> >
>> > The multiplication is between signed integers, and it overflows (user triggerable).
> Well, we check that the end result - overflowed or not - is in a sane
> range. So this might fall under the heading of "user gets what he asks
> for".
I guess, though it wouldn't be clear to the user why it's broken since he passed a
seemingly valid looking value for txc->freq.
Thanks,
Sasha
On Wed, Nov 26, 2014 at 10:58:43AM -0800, Linus Torvalds wrote:
> I don't think coccinelle can do signedness checks, though, especially
> of the kind that are hidden deep behind some typedef like "loff_t".
> Maybe I'm wrong. Maybe smatch can? Adding Dan Carpenter to the cc..
>
Smatch knows about datatypes and signedness.
I've written a bunch of integer overflow checks and found some bugs but
the tests have always had too many false positives to publish. I'll
take a closer look at this next week.
regards,
dan carpenter
Hi Sasha,
Is this what you are looking for? This list is made with next-20141204.
It's mostly code which does:
x = foo + bar;
if (x < foo)
We compile the kernel with -fnostrict-overflow so GCC won't optimize
these checks away. I don't think they cause a problem?
There are some false positives which do:
if ((u16)(u16_foo + u16_bar) < u16_foo) {
regards,
dan carpenter
kernel/events/core.c:4534 perf_sample_ustack_size() warn: signed overflow undefined. 'header_size + stack_size < header_size'
kernel/delayacct.c:112 __delayacct_add_tsk() warn: signed overflow undefined. 'd->cpu_delay_total + t2 < d->cpu_delay_total'
kernel/delayacct.c:116 __delayacct_add_tsk() warn: signed overflow undefined. 'd->cpu_run_virtual_total + t3 < d->cpu_run_virtual_total'
mm/fadvise.c:71 SYSC_fadvise64_64() warn: signed overflow undefined. 'offset + len < len'
fs/ntfs/runlist.c:778 ntfs_mapping_pairs_decompress() warn: signed overflow undefined. 'attr + () < attr'
fs/ntfs/index.c:293 ntfs_index_lookup() warn: signed overflow undefined. 'kaddr + ((vcn << idx_ni->itype.index.vcn_size_bits) & ~(~(((1) << 12) - 1))) < kaddr'
fs/ntfs/index.c:351 ntfs_index_lookup() warn: signed overflow undefined. '&ia->index + () < ia'
fs/ntfs/inode.c:507 ntfs_is_extended_system_file() warn: signed overflow undefined. 'attr + () < attr'
fs/ntfs/dir.c:336 ntfs_lookup_inode_by_name() warn: signed overflow undefined. 'kaddr + ((vcn << dir_ni->itype.index.vcn_size_bits) & ~(~(((1) << 12) - 1))) < kaddr'
fs/ntfs/dir.c:394 ntfs_lookup_inode_by_name() warn: signed overflow undefined. '&ia->index + () < ia'
fs/ntfs/dir.c:1199 ntfs_readdir() warn: signed overflow undefined. '&ir->index + () < ir'
fs/ntfs/dir.c:1313 ntfs_readdir() warn: signed overflow undefined. 'kaddr + (ia_pos & ~(~(((1) << 12) - 1)) & ~(ndir->itype.index.block_size - 1)) < kaddr'
fs/ntfs/dir.c:1381 ntfs_readdir() warn: signed overflow undefined. '&ia->index + () < ia'
fs/ntfs/super.c:1890 load_system_files() warn: signed overflow undefined. 'ctx->attr + () < ctx->attr'
fs/cifs/smb2pdu.c:1124 SMB2_open() warn: signed overflow undefined. 'uni_path_len / 8 * 8 < uni_path_len'
fs/ext4/extents.c:4794 ext4_zero_range() warn: signed overflow undefined. '(((offset) - 1) | (((1 << blkbits) - 1))) + 1 < offset'
fs/sync.c:288 SYSC_sync_file_range() warn: signed overflow undefined. 'offset + nbytes < offset'
drivers/hid/hid-tmff.c:76 tmff_scale_s8() warn: signed overflow undefined. '(((in + 128) * (maximum - minimum)) / 255) + minimum < minimum'
drivers/hid/hid-tmff.c:63 tmff_scale_u16() warn: signed overflow undefined. '(in * (maximum - minimum) / 65535) + minimum < minimum'
drivers/staging/lustre/lustre/obdclass/lprocfs_status.c:212 lprocfs_write_frac_helper() warn: signed overflow undefined. 'end + 1 < end'
drivers/staging/speakup/kobjects.c:800 message_store_helper() warn: signed overflow undefined. 'firstmessage + index < firstmessage'
drivers/scsi/mpt2sas/mpt2sas_ctl.c:1986 _ctl_diag_read_buffer() warn: signed overflow undefined. 'diag_data + karg.bytes_to_read < diag_data'
drivers/scsi/mpt3sas/mpt3sas_ctl.c:2018 _ctl_diag_read_buffer() warn: signed overflow undefined. 'diag_data + karg.bytes_to_read < diag_data'
drivers/block/floppy.c:2450 copy_buffer() warn: signed overflow undefined. 'floppy_track_buffer + ((fsector_t - buffer_min) << 9) < floppy_track_buffer'
drivers/block/floppy.c:2760 make_raw_rw_request() warn: signed overflow undefined. 'floppy_track_buffer + ((aligned_sector_t - buffer_min) << 9) < floppy_track_buffer'
drivers/infiniband/core/cma.c:2716 cma_resolve_ib_udp() warn: signed overflow undefined. 'offset + conn_param->private_data_len < conn_param->private_data_len'
drivers/infiniband/core/cma.c:2773 cma_connect_ib() warn: signed overflow undefined. 'offset + conn_param->private_data_len < conn_param->private_data_len'
drivers/video/fbdev/riva/riva_hw.c:1016 nv10CalcArbitration() warn: signed overflow undefined. '(clwm / 8) * 8 < clwm'
drivers/video/fbdev/nvidia/nv_hw.c:569 nv10CalcArbitration() warn: signed overflow undefined. '(clwm / 8) * 8 < clwm'
lib/vsprintf.c:1756 vsnprintf() warn: signed overflow undefined. 'buf + size < buf'
lib/vsprintf.c:2192 bstr_printf() warn: signed overflow undefined. 'buf + size < buf'
net/netfilter/ipset/ip_set_core.c:901 ip_set_create() warn: signed overflow undefined. 'inst->ip_set_max + 64 < inst->ip_set_max'
net/irda/irlap.c:660 irlap_generate_rand_time_slot() warn: signed overflow undefined. 's + rand % (S - s) < S'
net/sunrpc/auth_gss/gss_krb5_mech.c:193 simple_get_bytes() warn: signed overflow undefined. 'p + len < p'
net/sunrpc/auth_gss/gss_krb5_mech.c:209 simple_get_netobj() warn: signed overflow undefined. 'p + len < p'
net/sunrpc/auth_gss/gss_krb5_mech.c:296 gss_import_v1_context() warn: signed overflow undefined. 'p + 20 < p'
net/sunrpc/auth_gss/auth_gss.c:154 simple_get_bytes() warn: signed overflow undefined. 'p + len < p'
net/sunrpc/auth_gss/auth_gss.c:257 gss_fill_context() warn: signed overflow undefined. 'p + seclen < p'
net/sunrpc/auth_gss/auth_gss.c:170 simple_get_netobj() warn: signed overflow undefined. 'p + len < p'
net/sunrpc/xdr.c:572 xdr_reserve_space() warn: signed overflow undefined. 'p + (nbytes >> 2) < p'
net/sunrpc/xdr.c:832 __xdr_inline_decode() warn: signed overflow undefined. 'p + nwords < p'
security/keys/keyctl.c:856 keyctl_chown_key() warn: signed overflow undefined. 'newowner->qnbytes + key->quotalen < newowner->qnbytes'
security/keys/key.c:380 key_payload_reserve() warn: signed overflow undefined. 'key->user->qnbytes + delta < key->user->qnbytes'
On Fri, Dec 5, 2014 at 1:54 AM, Dan Carpenter <[email protected]> wrote:
>
> There are some false positives which do:
>
> if ((u16)(u16_foo + u16_bar) < u16_foo) {
Actually, the worse false positive is the ones that are pointer comparisons.
A compiler that does those as signed is just broken. It's happened,
but it's *still* completely broken.
Linus
On Fri, Dec 05, 2014 at 10:50:19AM -0800, Linus Torvalds wrote:
> On Fri, Dec 5, 2014 at 1:54 AM, Dan Carpenter <[email protected]> wrote:
> >
> > There are some false positives which do:
> >
> > if ((u16)(u16_foo + u16_bar) < u16_foo) {
>
> Actually, the worse false positive is the ones that are pointer comparisons.
>
> A compiler that does those as signed is just broken. It's happened,
> but it's *still* completely broken.
>
Oh. Wow... That's embarrassing. I thought they were signed for some
reason, and I thought it was weird, but I didn't think about it hard
enough...
I'll redo this.
regards,
dan carpenter