time: signed integer overflow in ktime_add_safe

time: signed integer overflow in ktime_add_safe

[Dmitry Vyukov]

Hello,

UBSAN reports undefined behavior in ktime_add_safe:

UBSAN: Undefined behaviour in kernel/time/hrtimer.c:310:16
signed integer overflow:
9223372036854775807 + 100000000 cannot be represented in type 'long long int'
CPU: 3 PID: 26438 Comm: syzkaller_execu Tainted: G    B
4.4.0-rc3+ #141
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Bochs 01/01/2011
 0000000000000003 ffff88005a62f518 ffffffff82c65588 0000000041b58ab3
 ffffffff8769c1b6 ffffffff82c654d6 ffff88005a62f4e0 ffff88005a62f618
 0000000005f5e100 0000000000000001 ffff88005a62f520 ffffffff82d540c7
Call Trace:
 [<ffffffff82d54f69>] __ubsan_handle_add_overflow+0x2a/0x31 lib/ubsan.c:199
 [<     inline     >] ktime_add_safe kernel/time/hrtimer.c:310
 [<     inline     >] hrtimer_set_expires_range_ns include/linux/hrtimer.h:224
 [<ffffffff86820fce>] schedule_hrtimeout_range_clock+0x4ae/0x580
kernel/time/hrtimer.c:1731
 [<ffffffff868210ca>] schedule_hrtimeout_range+0x2a/0x40
kernel/time/hrtimer.c:1779
 [<ffffffff81833112>] poll_schedule_timeout+0xd2/0x180 fs/select.c:241
 [<     inline     >] do_poll fs/select.c:861
 [<ffffffff8183706b>] do_sys_poll+0xa4b/0xfc0 fs/select.c:911
 [<     inline     >] SYSC_ppoll fs/select.c:1019
 [<ffffffff81837d79>] SyS_ppoll+0x1a9/0x420 fs/select.c:991

On commit 31ade3b83e1821da5fbb2f11b5b3d4ab2ec39db8.

For:

ktime_t ktime_add_safe(const ktime_t lhs, const ktime_t rhs)
{
        ktime_t res = ktime_add(lhs, rhs);
        if (res.tv64 < 0 || res.tv64 < lhs.tv64 || res.tv64 < rhs.tv64)
                res = ktime_set(KTIME_SEC_MAX, 0);
        return res;
}

compiler is within its rights to assume that res.tv64 < rhs.tv64 is
always false (after inlining ktime_add). And compilers already do
this. For example, if you compile the following program with clang -O2
(clang version 3.8.0 (trunk 252895)), it does not print OVERFLOW:

#include <stdio.h>
#include <limits.h>
int main() {
        volatile int x = 0;
        int a = INT_MAX + x;
        int b = 1 + x;
        if (a + b < a)
                printf("OVERFLOW\n");
        return 0;
}

Proper overflow checking for signed integers is quite hairy and easy
to mess up. Do we have any helper functions for this? I've seen some
patches from Hannes, not sure what's their status.

Re: time: signed integer overflow in ktime_add_safe

[Hannes Frederic Sowa]

Hello,

On Fri, Dec 4, 2015, at 12:05, Dmitry Vyukov wrote:
> UBSAN reports undefined behavior in ktime_add_safe:
> 
> UBSAN: Undefined behaviour in kernel/time/hrtimer.c:310:16
> signed integer overflow:
> 9223372036854775807 + 100000000 cannot be represented in type 'long long
> int'
> CPU: 3 PID: 26438 Comm: syzkaller_execu Tainted: G    B
> 4.4.0-rc3+ #141
> Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Bochs
> 01/01/2011
>  0000000000000003 ffff88005a62f518 ffffffff82c65588 0000000041b58ab3
>  ffffffff8769c1b6 ffffffff82c654d6 ffff88005a62f4e0 ffff88005a62f618
>  0000000005f5e100 0000000000000001 ffff88005a62f520 ffffffff82d540c7
> Call Trace:
>  [<ffffffff82d54f69>] __ubsan_handle_add_overflow+0x2a/0x31
>  lib/ubsan.c:199
>  [<     inline     >] ktime_add_safe kernel/time/hrtimer.c:310
>  [<     inline     >] hrtimer_set_expires_range_ns
>  include/linux/hrtimer.h:224
>  [<ffffffff86820fce>] schedule_hrtimeout_range_clock+0x4ae/0x580
> kernel/time/hrtimer.c:1731
>  [<ffffffff868210ca>] schedule_hrtimeout_range+0x2a/0x40
> kernel/time/hrtimer.c:1779
>  [<ffffffff81833112>] poll_schedule_timeout+0xd2/0x180 fs/select.c:241
>  [<     inline     >] do_poll fs/select.c:861
>  [<ffffffff8183706b>] do_sys_poll+0xa4b/0xfc0 fs/select.c:911
>  [<     inline     >] SYSC_ppoll fs/select.c:1019
>  [<ffffffff81837d79>] SyS_ppoll+0x1a9/0x420 fs/select.c:991
> 
> On commit 31ade3b83e1821da5fbb2f11b5b3d4ab2ec39db8.
> 
> For:
> 
> ktime_t ktime_add_safe(const ktime_t lhs, const ktime_t rhs)
> {
>         ktime_t res = ktime_add(lhs, rhs);
>         if (res.tv64 < 0 || res.tv64 < lhs.tv64 || res.tv64 < rhs.tv64)
>                 res = ktime_set(KTIME_SEC_MAX, 0);
>         return res;
> }
> 
> compiler is within its rights to assume that res.tv64 < rhs.tv64 is
> always false (after inlining ktime_add). And compilers already do
> this. For example, if you compile the following program with clang -O2
> (clang version 3.8.0 (trunk 252895)), it does not print OVERFLOW:
> 
> #include <stdio.h>
> #include <limits.h>
> int main() {
>         volatile int x = 0;
>         int a = INT_MAX + x;
>         int b = 1 + x;
>         if (a + b < a)
>                 printf("OVERFLOW\n");
>         return 0;
> }
> 
> Proper overflow checking for signed integers is quite hairy and easy
> to mess up. Do we have any helper functions for this? I've seen some
> patches from Hannes, not sure what's their status.

If you compile this example with -O2 -fno-strict-overflow, like the
linux kernel does, it will print OVERFLOW in both clang and gcc. I think
this warning is a false positive from ubsan. I am not sure if we want to
handle it like that or not.

I actually would also used the fact that -fno-strict-overflow is set
during kernel compile to make the checks easier and faster. Is this a
good thing? What do others think?

Thanks,
Hannes

Re: time: signed integer overflow in ktime_add_safe

[Andrey Ryabinin]

On 12/04/2015 02:05 PM, Dmitry Vyukov wrote:
> Hello,
> 
> UBSAN reports undefined behavior in ktime_add_safe:
> 
> UBSAN: Undefined behaviour in kernel/time/hrtimer.c:310:16
> signed integer overflow:
> 9223372036854775807 + 100000000 cannot be represented in type 'long long int'
> CPU: 3 PID: 26438 Comm: syzkaller_execu Tainted: G    B
> 4.4.0-rc3+ #141
> Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Bochs 01/01/2011
>  0000000000000003 ffff88005a62f518 ffffffff82c65588 0000000041b58ab3
>  ffffffff8769c1b6 ffffffff82c654d6 ffff88005a62f4e0 ffff88005a62f618
>  0000000005f5e100 0000000000000001 ffff88005a62f520 ffffffff82d540c7
> Call Trace:
>  [<ffffffff82d54f69>] __ubsan_handle_add_overflow+0x2a/0x31 lib/ubsan.c:199
>  [<     inline     >] ktime_add_safe kernel/time/hrtimer.c:310
>  [<     inline     >] hrtimer_set_expires_range_ns include/linux/hrtimer.h:224
>  [<ffffffff86820fce>] schedule_hrtimeout_range_clock+0x4ae/0x580
> kernel/time/hrtimer.c:1731
>  [<ffffffff868210ca>] schedule_hrtimeout_range+0x2a/0x40
> kernel/time/hrtimer.c:1779
>  [<ffffffff81833112>] poll_schedule_timeout+0xd2/0x180 fs/select.c:241
>  [<     inline     >] do_poll fs/select.c:861
>  [<ffffffff8183706b>] do_sys_poll+0xa4b/0xfc0 fs/select.c:911
>  [<     inline     >] SYSC_ppoll fs/select.c:1019
>  [<ffffffff81837d79>] SyS_ppoll+0x1a9/0x420 fs/select.c:991
> 
> On commit 31ade3b83e1821da5fbb2f11b5b3d4ab2ec39db8.
> 
> For:
> 
> ktime_t ktime_add_safe(const ktime_t lhs, const ktime_t rhs)
> {
>         ktime_t res = ktime_add(lhs, rhs);
>         if (res.tv64 < 0 || res.tv64 < lhs.tv64 || res.tv64 < rhs.tv64)
>                 res = ktime_set(KTIME_SEC_MAX, 0);
>         return res;
> }
> 

I think we can workaround it this way:

diff --git a/include/linux/ktime.h b/include/linux/ktime.h
index 2b6a204..c768cc0 100644
--- a/include/linux/ktime.h
+++ b/include/linux/ktime.h
@@ -61,7 +61,7 @@ static inline ktime_t ktime_set(const s64 secs, const unsigned long nsecs)
 
 /* Add two ktime_t variables. res = lhs + rhs: */
 #define ktime_add(lhs, rhs) \
-               ({ (ktime_t){ .tv64 = (lhs).tv64 + (rhs).tv64 }; })
+               ({ (ktime_t){ .tv64 = (s64)((u64)(lhs).tv64 + (u64)(rhs).tv64) }; })
 
 /*
  * Add a ktime_t variable and a scalar nanosecond value.

> compiler is within its rights to assume that res.tv64 < rhs.tv64 is
> always false (after inlining ktime_add). And compilers already do
> this.

Not with -fno-strict-overflow

> For example, if you compile the following program with clang -O2
> (clang version 3.8.0 (trunk 252895)), it does not print OVERFLOW:
> 
> #include <stdio.h>
> #include <limits.h>
> int main() {
>         volatile int x = 0;
>         int a = INT_MAX + x;
>         int b = 1 + x;
>         if (a + b < a)
>                 printf("OVERFLOW\n");
>         return 0;
> }
> 
> Proper overflow checking for signed integers is quite hairy and easy
> to mess up. Do we have any helper functions for this? I've seen some
> patches from Hannes, not sure what's their status.
> 

http://thread.gmane.org/gmane.linux.kernel/2072906/focus=2073073

Re: time: signed integer overflow in ktime_add_safe

[Dmitry Vyukov]

On Fri, Dec 4, 2015 at 12:32 PM, Andrey Ryabinin <ryabinin.a.a@gmail.com> wrote:
> On 12/04/2015 02:05 PM, Dmitry Vyukov wrote:
>> Hello,
>>
>> UBSAN reports undefined behavior in ktime_add_safe:
>>
>> UBSAN: Undefined behaviour in kernel/time/hrtimer.c:310:16
>> signed integer overflow:
>> 9223372036854775807 + 100000000 cannot be represented in type 'long long int'
>> CPU: 3 PID: 26438 Comm: syzkaller_execu Tainted: G    B
>> 4.4.0-rc3+ #141
>> Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Bochs 01/01/2011
>>  0000000000000003 ffff88005a62f518 ffffffff82c65588 0000000041b58ab3
>>  ffffffff8769c1b6 ffffffff82c654d6 ffff88005a62f4e0 ffff88005a62f618
>>  0000000005f5e100 0000000000000001 ffff88005a62f520 ffffffff82d540c7
>> Call Trace:
>>  [<ffffffff82d54f69>] __ubsan_handle_add_overflow+0x2a/0x31 lib/ubsan.c:199
>>  [<     inline     >] ktime_add_safe kernel/time/hrtimer.c:310
>>  [<     inline     >] hrtimer_set_expires_range_ns include/linux/hrtimer.h:224
>>  [<ffffffff86820fce>] schedule_hrtimeout_range_clock+0x4ae/0x580
>> kernel/time/hrtimer.c:1731
>>  [<ffffffff868210ca>] schedule_hrtimeout_range+0x2a/0x40
>> kernel/time/hrtimer.c:1779
>>  [<ffffffff81833112>] poll_schedule_timeout+0xd2/0x180 fs/select.c:241
>>  [<     inline     >] do_poll fs/select.c:861
>>  [<ffffffff8183706b>] do_sys_poll+0xa4b/0xfc0 fs/select.c:911
>>  [<     inline     >] SYSC_ppoll fs/select.c:1019
>>  [<ffffffff81837d79>] SyS_ppoll+0x1a9/0x420 fs/select.c:991
>>
>> On commit 31ade3b83e1821da5fbb2f11b5b3d4ab2ec39db8.
>>
>> For:
>>
>> ktime_t ktime_add_safe(const ktime_t lhs, const ktime_t rhs)
>> {
>>         ktime_t res = ktime_add(lhs, rhs);
>>         if (res.tv64 < 0 || res.tv64 < lhs.tv64 || res.tv64 < rhs.tv64)
>>                 res = ktime_set(KTIME_SEC_MAX, 0);
>>         return res;
>> }
>>
>
> I think we can workaround it this way:
>
> diff --git a/include/linux/ktime.h b/include/linux/ktime.h
> index 2b6a204..c768cc0 100644
> --- a/include/linux/ktime.h
> +++ b/include/linux/ktime.h
> @@ -61,7 +61,7 @@ static inline ktime_t ktime_set(const s64 secs, const unsigned long nsecs)
>
>  /* Add two ktime_t variables. res = lhs + rhs: */
>  #define ktime_add(lhs, rhs) \
> -               ({ (ktime_t){ .tv64 = (lhs).tv64 + (rhs).tv64 }; })
> +               ({ (ktime_t){ .tv64 = (s64)((u64)(lhs).tv64 + (u64)(rhs).tv64) }; })
>
>  /*
>   * Add a ktime_t variable and a scalar nanosecond value.
>
>> compiler is within its rights to assume that res.tv64 < rhs.tv64 is
>> always false (after inlining ktime_add). And compilers already do
>> this.
>
> Not with -fno-strict-overflow


Then I guess we need to disable this check in kernel ubsan.


>> For example, if you compile the following program with clang -O2
>> (clang version 3.8.0 (trunk 252895)), it does not print OVERFLOW:
>>
>> #include <stdio.h>
>> #include <limits.h>
>> int main() {
>>         volatile int x = 0;
>>         int a = INT_MAX + x;
>>         int b = 1 + x;
>>         if (a + b < a)
>>                 printf("OVERFLOW\n");
>>         return 0;
>> }
>>
>> Proper overflow checking for signed integers is quite hairy and easy
>> to mess up. Do we have any helper functions for this? I've seen some
>> patches from Hannes, not sure what's their status.
>>
>
> http://thread.gmane.org/gmane.linux.kernel/2072906/focus=2073073
>

Re: time: signed integer overflow in ktime_add_safe

[Andrey Ryabinin]

On 12/04/2015 02:33 PM, Dmitry Vyukov wrote:
> On Fri, Dec 4, 2015 at 12:32 PM, Andrey Ryabinin <ryabinin.a.a@gmail.com> wrote:
>> On 12/04/2015 02:05 PM, Dmitry Vyukov wrote:
>>> Hello,
>>>
>>> UBSAN reports undefined behavior in ktime_add_safe:
>>>
>>> UBSAN: Undefined behaviour in kernel/time/hrtimer.c:310:16
>>> signed integer overflow:
>>> 9223372036854775807 + 100000000 cannot be represented in type 'long long int'
>>> CPU: 3 PID: 26438 Comm: syzkaller_execu Tainted: G    B
>>> 4.4.0-rc3+ #141
>>> Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Bochs 01/01/2011
>>>  0000000000000003 ffff88005a62f518 ffffffff82c65588 0000000041b58ab3
>>>  ffffffff8769c1b6 ffffffff82c654d6 ffff88005a62f4e0 ffff88005a62f618
>>>  0000000005f5e100 0000000000000001 ffff88005a62f520 ffffffff82d540c7
>>> Call Trace:
>>>  [<ffffffff82d54f69>] __ubsan_handle_add_overflow+0x2a/0x31 lib/ubsan.c:199
>>>  [<     inline     >] ktime_add_safe kernel/time/hrtimer.c:310
>>>  [<     inline     >] hrtimer_set_expires_range_ns include/linux/hrtimer.h:224
>>>  [<ffffffff86820fce>] schedule_hrtimeout_range_clock+0x4ae/0x580
>>> kernel/time/hrtimer.c:1731
>>>  [<ffffffff868210ca>] schedule_hrtimeout_range+0x2a/0x40
>>> kernel/time/hrtimer.c:1779
>>>  [<ffffffff81833112>] poll_schedule_timeout+0xd2/0x180 fs/select.c:241
>>>  [<     inline     >] do_poll fs/select.c:861
>>>  [<ffffffff8183706b>] do_sys_poll+0xa4b/0xfc0 fs/select.c:911
>>>  [<     inline     >] SYSC_ppoll fs/select.c:1019
>>>  [<ffffffff81837d79>] SyS_ppoll+0x1a9/0x420 fs/select.c:991
>>>
>>> On commit 31ade3b83e1821da5fbb2f11b5b3d4ab2ec39db8.
>>>
>>> For:
>>>
>>> ktime_t ktime_add_safe(const ktime_t lhs, const ktime_t rhs)
>>> {
>>>         ktime_t res = ktime_add(lhs, rhs);
>>>         if (res.tv64 < 0 || res.tv64 < lhs.tv64 || res.tv64 < rhs.tv64)
>>>                 res = ktime_set(KTIME_SEC_MAX, 0);
>>>         return res;
>>> }
>>>
>>
>> I think we can workaround it this way:
>>
>> diff --git a/include/linux/ktime.h b/include/linux/ktime.h
>> index 2b6a204..c768cc0 100644
>> --- a/include/linux/ktime.h
>> +++ b/include/linux/ktime.h
>> @@ -61,7 +61,7 @@ static inline ktime_t ktime_set(const s64 secs, const unsigned long nsecs)
>>
>>  /* Add two ktime_t variables. res = lhs + rhs: */
>>  #define ktime_add(lhs, rhs) \
>> -               ({ (ktime_t){ .tv64 = (lhs).tv64 + (rhs).tv64 }; })
>> +               ({ (ktime_t){ .tv64 = (s64)((u64)(lhs).tv64 + (u64)(rhs).tv64) }; })
>>
>>  /*
>>   * Add a ktime_t variable and a scalar nanosecond value.
>>
>>> compiler is within its rights to assume that res.tv64 < rhs.tv64 is
>>> always false (after inlining ktime_add). And compilers already do
>>> this.
>>
>> Not with -fno-strict-overflow
> 
> 
> Then I guess we need to disable this check in kernel ubsan.
> 

I'm not so sure. It finds real bugs, e.g. 32a8df4e0b33f ("sched: Fix odd values in effective_load() calculations")
was caught by UBSAN
I guess that we could fix most signed overflows simply by casting to unsigned type.

Re: time: signed integer overflow in ktime_add_safe

[Dmitry Vyukov]

On Fri, Dec 4, 2015 at 12:44 PM, Andrey Ryabinin <ryabinin.a.a@gmail.com> wrote:
>>>> Hello,
>>>>
>>>> UBSAN reports undefined behavior in ktime_add_safe:
>>>>
>>>> UBSAN: Undefined behaviour in kernel/time/hrtimer.c:310:16
>>>> signed integer overflow:
>>>> 9223372036854775807 + 100000000 cannot be represented in type 'long long int'
>>>> CPU: 3 PID: 26438 Comm: syzkaller_execu Tainted: G    B
>>>> 4.4.0-rc3+ #141
>>>> Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Bochs 01/01/2011
>>>>  0000000000000003 ffff88005a62f518 ffffffff82c65588 0000000041b58ab3
>>>>  ffffffff8769c1b6 ffffffff82c654d6 ffff88005a62f4e0 ffff88005a62f618
>>>>  0000000005f5e100 0000000000000001 ffff88005a62f520 ffffffff82d540c7
>>>> Call Trace:
>>>>  [<ffffffff82d54f69>] __ubsan_handle_add_overflow+0x2a/0x31 lib/ubsan.c:199
>>>>  [<     inline     >] ktime_add_safe kernel/time/hrtimer.c:310
>>>>  [<     inline     >] hrtimer_set_expires_range_ns include/linux/hrtimer.h:224
>>>>  [<ffffffff86820fce>] schedule_hrtimeout_range_clock+0x4ae/0x580
>>>> kernel/time/hrtimer.c:1731
>>>>  [<ffffffff868210ca>] schedule_hrtimeout_range+0x2a/0x40
>>>> kernel/time/hrtimer.c:1779
>>>>  [<ffffffff81833112>] poll_schedule_timeout+0xd2/0x180 fs/select.c:241
>>>>  [<     inline     >] do_poll fs/select.c:861
>>>>  [<ffffffff8183706b>] do_sys_poll+0xa4b/0xfc0 fs/select.c:911
>>>>  [<     inline     >] SYSC_ppoll fs/select.c:1019
>>>>  [<ffffffff81837d79>] SyS_ppoll+0x1a9/0x420 fs/select.c:991
>>>>
>>>> On commit 31ade3b83e1821da5fbb2f11b5b3d4ab2ec39db8.
>>>>
>>>> For:
>>>>
>>>> ktime_t ktime_add_safe(const ktime_t lhs, const ktime_t rhs)
>>>> {
>>>>         ktime_t res = ktime_add(lhs, rhs);
>>>>         if (res.tv64 < 0 || res.tv64 < lhs.tv64 || res.tv64 < rhs.tv64)
>>>>                 res = ktime_set(KTIME_SEC_MAX, 0);
>>>>         return res;
>>>> }
>>>>
>>>
>>> I think we can workaround it this way:
>>>
>>> diff --git a/include/linux/ktime.h b/include/linux/ktime.h
>>> index 2b6a204..c768cc0 100644
>>> --- a/include/linux/ktime.h
>>> +++ b/include/linux/ktime.h
>>> @@ -61,7 +61,7 @@ static inline ktime_t ktime_set(const s64 secs, const unsigned long nsecs)
>>>
>>>  /* Add two ktime_t variables. res = lhs + rhs: */
>>>  #define ktime_add(lhs, rhs) \
>>> -               ({ (ktime_t){ .tv64 = (lhs).tv64 + (rhs).tv64 }; })
>>> +               ({ (ktime_t){ .tv64 = (s64)((u64)(lhs).tv64 + (u64)(rhs).tv64) }; })
>>>
>>>  /*
>>>   * Add a ktime_t variable and a scalar nanosecond value.
>>>
>>>> compiler is within its rights to assume that res.tv64 < rhs.tv64 is
>>>> always false (after inlining ktime_add). And compilers already do
>>>> this.
>>>
>>> Not with -fno-strict-overflow
>>
>>
>> Then I guess we need to disable this check in kernel ubsan.
>>
>
> I'm not so sure. It finds real bugs, e.g. 32a8df4e0b33f ("sched: Fix odd values in effective_load() calculations")
> was caught by UBSAN
> I guess that we could fix most signed overflows simply by casting to unsigned type.


Yeah, overflows can be just unexpected in some places (not an intended
reliance on defined overflow). If we want to continue finding real
bugs, we need to start fixing the false positives.

Re: time: signed integer overflow in ktime_add_safe

[Sasha Levin]

On 12/04/2015 06:49 AM, Dmitry Vyukov wrote:
>> I'm not so sure. It finds real bugs, e.g. 32a8df4e0b33f ("sched: Fix odd values in effective_load() calculations")
>> > was caught by UBSAN
>> > I guess that we could fix most signed overflows simply by casting to unsigned type.
> 
> Yeah, overflows can be just unexpected in some places (not an intended
> reliance on defined overflow). If we want to continue finding real
> bugs, we need to start fixing the false positives.

Right, this check finds real bugs, but quite a few false positives because
we tell gcc specifically that this overflow is really okay, and people have
relied on that.

On the other hand, we can't "fix" the code that's triggering it since nothing
is actually broken - in ktime_add_safe() for example we'd overflow, but then
we're checking for overflow, so the code is perfectly fine.

Maybe UBSAN annotations are the way to go here?


Thanks,
Sasha