Check for time_t overflow in event_timeout_trigger()

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 <[email protected]...>

---
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(-)

src/openvpn/integer.h +2 -0

index 9bb00a38..51085450 100644
@@ -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

src/openvpn/integer.h +2 -0

+}
+
 /*
  * Functions used for circular buffer index arithmetic.
  */

src/openvpn/interval.c +4 -2

index 16343865..909e3fcd 100644
@@ -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)
             {

src/openvpn/integer.h constrain_int(int x, int min, int max) · line 91

Quoted 12 lines

src/openvpn/integer.h +12 -0

+/** 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?

Quoted 25 lines · Selva Nair

src/openvpn/integer.h constrain_int(int x, int min, int max) · line 91

Quoted 12 lines

src/openvpn/integer.h +12 -0

+/** 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.

Quoted 1 line

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.

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 <[email protected]...>

---
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(-)

src/openvpn/integer.h +4 -0

index 9bb00a38..51085450 100644
@@ -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");

src/openvpn/integer.h +0 -0

 /*
  * Functions used for circular buffer index arithmetic.
  */

src/openvpn/interval.c +0 -0

index 16343865..909e3fcd 100644

INT_MAX (for 32 bit time_t), not something we should worry about

         if (wakeup <= 0)
         {

#if INTERVAL_DEBUG

src/openvpn/interval.c +2 -1

-            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)
             {

We can avoid all overflow and eliminate the check and the ASSERT by writing it as

time_t wakeup = (et->last - local_now) + et->n; // parens added for clarity

For the first subtraction to overflow, last and now have to differ by

Quoted 1 line

INT_MAX (for 32 bit time_t), not something we should worry about

(can't happen in normal operation).
Further, the term in brackets is always negative (as now >= last), while et->n is positive and < INT_MAX by construction. So the final addition also cannot overflow. All assuming that 32 bit "now" and "last" are not used beyond 2037.

That would take care of this particular overflow concern.