[Openvpn-devel,v2] Check for time_t overflow in event_timeout_trigger()

Message ID 20180102222854.29198-1-steffan@karger.me
State New
Headers show
Series
  • [Openvpn-devel,v2] Check for time_t overflow in event_timeout_trigger()
Related show

Commit Message

Steffan Karger Jan. 2, 2018, 10:28 p.m.
As reported in trac #922, the wakeup computation in
event_timeout_trigger() could overflow.  Since time_t and int are signed
types, that is officially undefined behvaiour.

On systems with a 64-bit signed time_t (most if not all 64-bit system),
the overflow was caused by the (unnecessary) cast to "int".  Removing
that, changing the time of "wakeup" to time_t, and assuming that the
system clock on our host system will never be set to the year
292471210579 or later, this can no longer overflow on systems with a
64-bit time_t.

For systems with a signed 32-bit time_t however, we need an additional
check to prevent signed overflow (and thus undefined behaviour).  Since
time_t is only specified by C99 to be "an arithmetic type capable of
representing times", and no TIME_MAX or TIME_MIN macros are available,
checking for overflow is not trivial at all.  This patch takes the
practical approach, and assumes that time_t is of type "long int" (aka
"long") or "long long int" (aka "long long").  POSIX requires time_t to
be an "integer type", and all systems I know of use a long int or long
long int.  To be sure that this assumption holds, this patch uses static
asserts.

Since I can't come up with anything useful to do if this check fails,
and the input are not based on remote input, this patch just turns the
undefined behaviour into a defined ASSERT().

And while we touch this function, make it obey the 80-char line length
limit.

So much for this "simple" overflow check.

Trac: #922
Signed-off-by: Steffan Karger <steffan@karger.me>
---
v2: Fix (#if 0'd) debug print format specifier for changed type.

 src/openvpn/integer.h  | 14 ++++++++++++++
 src/openvpn/interval.c |  9 ++++++---
 2 files changed, 20 insertions(+), 3 deletions(-)

Comments

Selva Nair Feb. 22, 2018, 10:37 p.m. | #1
Hi,

This just caught my fancy :)

On Tue, Jan 2, 2018 at 5:28 PM, Steffan Karger <steffan@karger.me> wrote:
> As reported in trac #922, the wakeup computation in
> event_timeout_trigger() could overflow.  Since time_t and int are signed
> types, that is officially undefined behvaiour.
>
> On systems with a 64-bit signed time_t (most if not all 64-bit system),
> the overflow was caused by the (unnecessary) cast to "int".  Removing
> that, changing the time of "wakeup" to time_t, and assuming that the
> system clock on our host system will never be set to the year
> 292471210579 or later, this can no longer overflow on systems with a
> 64-bit time_t.
>
> For systems with a signed 32-bit time_t however, we need an additional
> check to prevent signed overflow (and thus undefined behaviour).  Since
> time_t is only specified by C99 to be "an arithmetic type capable of
> representing times", and no TIME_MAX or TIME_MIN macros are available,
> checking for overflow is not trivial at all.  This patch takes the
> practical approach, and assumes that time_t is of type "long int" (aka
> "long") or "long long int" (aka "long long").  POSIX requires time_t to
> be an "integer type", and all systems I know of use a long int or long
> long int.  To be sure that this assumption holds, this patch uses static
> asserts.
>
> Since I can't come up with anything useful to do if this check fails,
> and the input are not based on remote input, this patch just turns the
> undefined behaviour into a defined ASSERT().
>
> And while we touch this function, make it obey the 80-char line length
> limit.
>
> So much for this "simple" overflow check.
>
> Trac: #922
> Signed-off-by: Steffan Karger <steffan@karger.me>
> ---
> v2: Fix (#if 0'd) debug print format specifier for changed type.
>
>  src/openvpn/integer.h  | 14 ++++++++++++++
>  src/openvpn/interval.c |  9 ++++++---
>  2 files changed, 20 insertions(+), 3 deletions(-)
>
> diff --git a/src/openvpn/integer.h b/src/openvpn/integer.h
> index 9bb00a38..51085450 100644
> --- a/src/openvpn/integer.h
> +++ b/src/openvpn/integer.h
> @@ -77,6 +77,20 @@ constrain_int(int x, int min, int max)
>      }
>  }
>
> +/** Return true if the addition of a and b would overflow. */
> +static inline bool
> +time_t_add_overflow(time_t a, time_t b) {
> +    static_assert(((time_t) -1) < 0, "OpenVPN assumes time_t is signed");
> +    static_assert(((time_t) .9) == 0, "OpenVPN assumes time_t is integer type");
> +    static_assert(sizeof(time_t) == sizeof(long) || sizeof(time_t) == sizeof(long long),
> +        "OpenVPN assumes that time_t is of type long int or long long int");
> +    static const time_t TIME_MAX = sizeof(time_t) == sizeof(long) ?
> +            LONG_MAX : LLONG_MAX;
> +    static const time_t TIME_MIN = sizeof(time_t) == sizeof(long) ?
> +            LONG_MIN : LLONG_MIN;
> +    return (a > 0 && b > TIME_MAX - a) || (a < 0 && b < TIME_MIN - a);

Interesting. But I think this can be simplified much. Addition of
identically sized integers a and b overflows if and only if

((a > 0 && a + b < b) || (a < 0 && a + b > b))

As overflow is possible only when both have same sign it can also be written as

((a > 0 && a + b < a) || (a < 0 && a + b > a))

So the TIME_MAX and TIME_MIN may be eliminated and that means no need
to check signed/unsigned or long/long-long.

Am I missing something?

> +}
> +
>  /*
>   * Functions used for circular buffer index arithmetic.
>   */
> diff --git a/src/openvpn/interval.c b/src/openvpn/interval.c
> index 16343865..909e3fcd 100644
> --- a/src/openvpn/interval.c
> +++ b/src/openvpn/interval.c
> @@ -51,11 +51,13 @@ event_timeout_trigger(struct event_timeout *et,
>
>      if (et->defined)
>      {
> -        int wakeup = (int) et->last + et->n - local_now;
> +        ASSERT(!time_t_add_overflow(et->last, et->n));
> +        time_t wakeup = et->last + et->n - local_now;
>          if (wakeup <= 0)
>          {
>  #if INTERVAL_DEBUG
> -            dmsg(D_INTERVAL, "EVENT event_timeout_trigger (%d) etcr=%d", et->n, et_const_retry);
> +            dmsg(D_INTERVAL, "EVENT event_timeout_trigger (%d) etcr=%d", et->n,
> +                 et_const_retry);
>  #endif
>              if (et_const_retry < 0)
>              {
> @@ -72,7 +74,8 @@ event_timeout_trigger(struct event_timeout *et,
>          if (tv && wakeup < tv->tv_sec)
>          {
>  #if INTERVAL_DEBUG
> -            dmsg(D_INTERVAL, "EVENT event_timeout_wakeup (%d/%d) etcr=%d", wakeup, et->n, et_const_retry);
> +            dmsg(D_INTERVAL, "EVENT event_timeout_wakeup (%ld/%d) etcr=%d",
> +                 (long) wakeup, et->n, et_const_retry);
>  #endif
>              tv->tv_sec = wakeup;
>              tv->tv_usec = 0;
> --

Selva

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
Selva Nair Feb. 22, 2018, 11:02 p.m. | #2
Hi,

On Thu, Feb 22, 2018 at 5:37 PM, Selva Nair <selva.nair@gmail.com> wrote:

>> +/** Return true if the addition of a and b would overflow. */
>> +static inline bool
>> +time_t_add_overflow(time_t a, time_t b) {
>> +    static_assert(((time_t) -1) < 0, "OpenVPN assumes time_t is signed");
>> +    static_assert(((time_t) .9) == 0, "OpenVPN assumes time_t is integer type");
>> +    static_assert(sizeof(time_t) == sizeof(long) || sizeof(time_t) == sizeof(long long),
>> +        "OpenVPN assumes that time_t is of type long int or long long int");
>> +    static const time_t TIME_MAX = sizeof(time_t) == sizeof(long) ?
>> +            LONG_MAX : LLONG_MAX;
>> +    static const time_t TIME_MIN = sizeof(time_t) == sizeof(long) ?
>> +            LONG_MIN : LLONG_MIN;
>> +    return (a > 0 && b > TIME_MAX - a) || (a < 0 && b < TIME_MIN - a);
>
> Interesting. But I think this can be simplified much. Addition of
> identically sized integers a and b overflows if and only if
>
> ((a > 0 && a + b < b) || (a < 0 && a + b > b))
>
> As overflow is possible only when both have same sign it can also be written as
>
> ((a > 0 && a + b < a) || (a < 0 && a + b > a))
>
> So the TIME_MAX and TIME_MIN may be eliminated and that means no need
> to check signed/unsigned or long/long-long.
>
> Am I missing something?

Hm... replying to self: I suppose the worry is related to unsigned int
arithmetic overflow being undefined behaviour in C. So potentially a
compiler can treat those statements as always true if it wishes..

Well, excuse the noise I caused then.

Selva

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
Steffan Karger Feb. 24, 2018, 2:07 p.m. | #3
Hi

On 23-02-18 00:02, Selva Nair wrote:
> On Thu, Feb 22, 2018 at 5:37 PM, Selva Nair <selva.nair@gmail.com> wrote:
>>> +/** Return true if the addition of a and b would overflow. */
>>> +static inline bool
>>> +time_t_add_overflow(time_t a, time_t b) {
>>> +    static_assert(((time_t) -1) < 0, "OpenVPN assumes time_t is signed");
>>> +    static_assert(((time_t) .9) == 0, "OpenVPN assumes time_t is integer type");
>>> +    static_assert(sizeof(time_t) == sizeof(long) || sizeof(time_t) == sizeof(long long),
>>> +        "OpenVPN assumes that time_t is of type long int or long long int");
>>> +    static const time_t TIME_MAX = sizeof(time_t) == sizeof(long) ?
>>> +            LONG_MAX : LLONG_MAX;
>>> +    static const time_t TIME_MIN = sizeof(time_t) == sizeof(long) ?
>>> +            LONG_MIN : LLONG_MIN;
>>> +    return (a > 0 && b > TIME_MAX - a) || (a < 0 && b < TIME_MIN - a);
>>
>> Interesting. But I think this can be simplified much. Addition of
>> identically sized integers a and b overflows if and only if
>>
>> ((a > 0 && a + b < b) || (a < 0 && a + b > b))
>>
>> As overflow is possible only when both have same sign it can also be written as
>>
>> ((a > 0 && a + b < a) || (a < 0 && a + b > a))
>>
>> So the TIME_MAX and TIME_MIN may be eliminated and that means no need
>> to check signed/unsigned or long/long-long.
>>
>> Am I missing something?
> 
> Hm... replying to self: I suppose the worry is related to unsigned int
> arithmetic overflow being undefined behaviour in C. So potentially a
> compiler can treat those statements as always true if it wishes..
> 
> Well, excuse the noise I caused then.

Yeah, at least, *signed* integer overflow is undefined, and time_t is
(usually) a signed type.

-Steffan

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot

Patch

diff --git a/src/openvpn/integer.h b/src/openvpn/integer.h
index 9bb00a38..51085450 100644
--- a/src/openvpn/integer.h
+++ b/src/openvpn/integer.h
@@ -77,6 +77,20 @@  constrain_int(int x, int min, int max)
     }
 }
 
+/** Return true if the addition of a and b would overflow. */
+static inline bool
+time_t_add_overflow(time_t a, time_t b) {
+    static_assert(((time_t) -1) < 0, "OpenVPN assumes time_t is signed");
+    static_assert(((time_t) .9) == 0, "OpenVPN assumes time_t is integer type");
+    static_assert(sizeof(time_t) == sizeof(long) || sizeof(time_t) == sizeof(long long),
+        "OpenVPN assumes that time_t is of type long int or long long int");
+    static const time_t TIME_MAX = sizeof(time_t) == sizeof(long) ?
+            LONG_MAX : LLONG_MAX;
+    static const time_t TIME_MIN = sizeof(time_t) == sizeof(long) ?
+            LONG_MIN : LLONG_MIN;
+    return (a > 0 && b > TIME_MAX - a) || (a < 0 && b < TIME_MIN - a);
+}
+
 /*
  * Functions used for circular buffer index arithmetic.
  */
diff --git a/src/openvpn/interval.c b/src/openvpn/interval.c
index 16343865..909e3fcd 100644
--- a/src/openvpn/interval.c
+++ b/src/openvpn/interval.c
@@ -51,11 +51,13 @@  event_timeout_trigger(struct event_timeout *et,
 
     if (et->defined)
     {
-        int wakeup = (int) et->last + et->n - local_now;
+        ASSERT(!time_t_add_overflow(et->last, et->n));
+        time_t wakeup = et->last + et->n - local_now;
         if (wakeup <= 0)
         {
 #if INTERVAL_DEBUG
-            dmsg(D_INTERVAL, "EVENT event_timeout_trigger (%d) etcr=%d", et->n, et_const_retry);
+            dmsg(D_INTERVAL, "EVENT event_timeout_trigger (%d) etcr=%d", et->n,
+                 et_const_retry);
 #endif
             if (et_const_retry < 0)
             {
@@ -72,7 +74,8 @@  event_timeout_trigger(struct event_timeout *et,
         if (tv && wakeup < tv->tv_sec)
         {
 #if INTERVAL_DEBUG
-            dmsg(D_INTERVAL, "EVENT event_timeout_wakeup (%d/%d) etcr=%d", wakeup, et->n, et_const_retry);
+            dmsg(D_INTERVAL, "EVENT event_timeout_wakeup (%ld/%d) etcr=%d",
+                 (long) wakeup, et->n, et_const_retry);
 #endif
             tv->tv_sec = wakeup;
             tv->tv_usec = 0;