Signed integer overflow in __secs_to_tm

Signed integer overflow in __secs_to_tm

[Brian Mastenbrook]

__secs_to_tm (used by gmtime_r et al) may invoke undefined behavior due to signed integer overflow in two places. At __secs_to_tm.c:58, 400*qc_cycles may overflow. At __secs_to_tm.c:63, there is a nonsensical comparison between an already overflowed value and INT_MAX or INT_MIN; the compiler will delete this test due to overflow. Here are some example values that provoke the overflow:

t = -67771633420944000

__secs_to_tm.c:58:[kernel] warning: signed overflow. assert -2147483648 ≤ 400*qc_cycles;

t = 67768037838810496

__secs_to_tm.c:63:[kernel] warning: signed overflow. assert years+100 ≤ 2147483647;

These errors were found using KLEE and clang's undefined behavior sanitizer together. (Unfortunately KLEE also produced a false report of an out-of-bounds access to the days_in_month array due to a solver bug.)

--
Brian Mastenbrook
brian@mastenbrook.net
http://brian.mastenbrook.net/

Re: Signed integer overflow in __secs_to_tm

[Jens Gustedt]

[-- Attachment #1: Type: text/plain, Size: 1521 bytes --]

Hello,

Am Dienstag, den 06.10.2015, 19:09 -0500 schrieb Brian Mastenbrook:
> __secs_to_tm (used by gmtime_r et al) may invoke undefined behavior due to signed integer overflow in two places. At __secs_to_tm.c:58, 400*qc_cycles may overflow. At __secs_to_tm.c:63, there is a nonsensical comparison between an already overflowed value and INT_MAX or INT_MIN; the compiler will delete this test due to overflow. Here are some example values that provoke the overflow:
> 
> t = -67771633420944000
> 
> __secs_to_tm.c:58:[kernel] warning: signed overflow. assert -2147483648 ≤ 400*qc_cycles;
> 
> t = 67768037838810496
> 
> __secs_to_tm.c:63:[kernel] warning: signed overflow. assert years+100 ≤ 2147483647;
> 
> These errors were found using KLEE and clang's undefined behavior sanitizer together. (Unfortunately KLEE also produced a false report of an out-of-bounds access to the days_in_month array due to a solver bug.)

There is a test in line 21 that is intended to inhibit that, I
think. The error there seems to be that it doesn't take the shift by
100 years into account.

If that test would use corrected constants, the overflow test that you
found should be superfluous.

Jens


-- 
:: INRIA Nancy Grand Est ::: Camus ::::::: ICube/ICPS :::
:: ::::::::::::::: office Strasbourg : +33 368854536   ::
:: :::::::::::::::::::::: gsm France : +33 651400183   ::
:: ::::::::::::::: gsm international : +49 15737185122 ::
:: http://icube-icps.unistra.fr/index.php/Jens_Gustedt ::




[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

Re: Signed integer overflow in __secs_to_tm

[Szabolcs Nagy]

[-- Attachment #1: Type: text/plain, Size: 1306 bytes --]

* Brian Mastenbrook <brian@mastenbrook.net> [2015-10-06 19:09:45 -0500]:
> __secs_to_tm (used by gmtime_r et al) may invoke undefined behavior due to signed integer overflow in two places. At __secs_to_tm.c:58, 400*qc_cycles may overflow. At __secs_to_tm.c:63, there is a nonsensical comparison between an already overflowed value and INT_MAX or INT_MIN; the compiler will delete this test due to overflow. Here are some example values that provoke the overflow:
> 

i think that computation was supposed to be done
with long longs and then the comparision is
sensical and both problems go away.

can you try the attached patch?

> t = -67771633420944000
> 
> __secs_to_tm.c:58:[kernel] warning: signed overflow. assert -2147483648 ??? 400*qc_cycles;
> 
> t = 67768037838810496
> 
> __secs_to_tm.c:63:[kernel] warning: signed overflow. assert years+100 ??? 2147483647;
> 
> These errors were found using KLEE and clang's undefined behavior sanitizer together. (Unfortunately KLEE also produced a false report of an out-of-bounds access to the days_in_month array due to a solver bug.)
> 

i have some questions:

have you look at other parts of musl?

can klee model libc/syscall api behaviour?

is it possible to instrument a libc.a with klee
and then use small programs to check various
libc interfaces?

[-- Attachment #2: tm.diff --]
[-- Type: text/x-diff, Size: 860 bytes --]

diff --git a/src/time/__secs_to_tm.c b/src/time/__secs_to_tm.c
index f3c1cf9..3a3123a 100644
--- a/src/time/__secs_to_tm.c
+++ b/src/time/__secs_to_tm.c
@@ -10,10 +10,10 @@
 
 int __secs_to_tm(long long t, struct tm *tm)
 {
-	long long days, secs;
+	long long days, secs, years;
 	int remdays, remsecs, remyears;
 	int qc_cycles, c_cycles, q_cycles;
-	int years, months;
+	int months;
 	int wday, yday, leap;
 	static const char days_in_month[] = {31,30,31,30,31,31,30,31,30,31,31,29};
 
@@ -55,7 +55,7 @@ int __secs_to_tm(long long t, struct tm *tm)
 	yday = remdays + 31 + 28 + leap;
 	if (yday >= 365+leap) yday -= 365+leap;
 
-	years = remyears + 4*q_cycles + 100*c_cycles + 400*qc_cycles;
+	years = remyears + 4*q_cycles + 100*c_cycles + 400LL*qc_cycles;
 
 	for (months=0; days_in_month[months] <= remdays; months++)
 		remdays -= days_in_month[months];

Re: Signed integer overflow in __secs_to_tm

[Rich Felker]

On Wed, Oct 07, 2015 at 12:22:53PM +0200, Szabolcs Nagy wrote:
> * Brian Mastenbrook <brian@mastenbrook.net> [2015-10-06 19:09:45 -0500]:
> > __secs_to_tm (used by gmtime_r et al) may invoke undefined
> > behavior due to signed integer overflow in two places. At
> > __secs_to_tm.c:58, 400*qc_cycles may overflow. At
> > __secs_to_tm.c:63, there is a nonsensical comparison between an
> > already overflowed value and INT_MAX or INT_MIN; the compiler will
> > delete this test due to overflow. Here are some example values
> > that provoke the overflow:
> > 
> 
> i think that computation was supposed to be done
> with long longs and then the comparision is
> sensical and both problems go away.
> 
> can you try the attached patch?

It looks good to me. I'm applying it. Thanks!

Rich