commit 4234ca3bf2c87d01026b3d003f6e5b4d1ec5b7df Author: teor (Tim Wilson-Brown) teor2345@gmail.com Date: Wed Jun 29 13:30:28 2016 +1000

Improve overflow checks in tv_udiff and tv_mdiff

Validate that tv_usec inputs to tv_udiff and tv_mdiff are in range.

Do internal calculations in tv_udiff and tv_mdiff in 64-bit, which makes the function less prone to integer overflow, particularly on platforms where long and time_t are 32-bit, but tv_sec is 64-bit, like some BSD configurations.

Check every addition and subtraction that could overflow. --- src/common/util.c | 115 ++++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 98 insertions(+), 17 deletions(-)

diff --git a/src/common/util.c b/src/common/util.c index 44994fb..613e000 100644 --- a/src/common/util.c +++ b/src/common/util.c @@ -1386,51 +1386,132 @@ tor_escape_str_for_pt_args(const char *string, const char *chars_to_escape) * Time * ===== */

+#define TOR_USEC_PER_SEC 1000000 + +/** Return the difference between start->tv_sec and end->tv_sec. + * Returns INT64_MAX on overflow and underflow. + */ +static int64_t +tv_secdiff_impl(const struct timeval *start, const struct timeval *end) +{ + const int64_t s = (int64_t)start->tv_sec; + const int64_t e = (int64_t)end->tv_sec; + + /* This may not be the most efficient way of implemeting this check, + * but it's easy to see that it's correct and doesn't overflow */ + + if (s > 0 && e < INT64_MIN + s) { + /* s is positive: equivalent to e - s < INT64_MIN, but without any + * overflow */ + return INT64_MAX; + } else if (s < 0 && e > INT64_MAX + s) { + /* s is negative: equivalent to e - s > INT64_MAX, but without any + * overflow */ + return INT64_MAX; + } + + return e - s; +} + /** Return the number of microseconds elapsed between *start and *end. + * Returns LONG_MAX on overflow and underflow. */ long tv_udiff(const struct timeval *start, const struct timeval *end) { - long udiff; - long secdiff = end->tv_sec - start->tv_sec; + /* Sanity check tv_usec */ + if (start->tv_usec > TOR_USEC_PER_SEC || start->tv_usec < 0) { + log_warn(LD_GENERAL, "comparing times on microsecond detail with bad " + "start tv_usec: " I64_FORMAT " microseconds", + I64_PRINTF_ARG(start->tv_usec)); + return LONG_MAX; + }

- /* end->tv_usec - start->tv_usec can be up to 1 second */ - if (labs(secdiff)+1 > LONG_MAX/1000000) { + if (end->tv_usec > TOR_USEC_PER_SEC || end->tv_usec < 0) { + log_warn(LD_GENERAL, "comparing times on microsecond detail with bad " + "end tv_usec: " I64_FORMAT " microseconds", + I64_PRINTF_ARG(end->tv_usec)); + return LONG_MAX; + } + + /* Some BSDs have struct timeval.tv_sec 64-bit, but time_t (and long) 32-bit + */ + int64_t udiff; + const int64_t secdiff = tv_secdiff_impl(start, end); + + /* end->tv_usec - start->tv_usec can be up to 1 second either way */ + if (secdiff > (int64_t)(LONG_MAX/1000000 - 1) || + secdiff < (int64_t)(LONG_MIN/1000000 + 1)) { log_warn(LD_GENERAL, "comparing times on microsecond detail too far " - "apart: %ld seconds", secdiff); + "apart: " I64_FORMAT " seconds", I64_PRINTF_ARG(secdiff)); return LONG_MAX; }

- udiff = secdiff*1000000L + (end->tv_usec - start->tv_usec); - return udiff; + /* we'll never get an overflow here, because we check that both usecs are + * between 0 and TV_USEC_PER_SEC. */ + udiff = secdiff*1000000 + ((int64_t)end->tv_usec - (int64_t)start->tv_usec); + + if (udiff > (int64_t)LONG_MAX || udiff < (int64_t)LONG_MIN) { + return LONG_MAX; + } else { + return (long)udiff; + } }

/** Return the number of milliseconds elapsed between *start and *end. + * If the tv_usec difference is 500, rounds away from zero. + * Returns LONG_MAX on overflow and underflow. */ long tv_mdiff(const struct timeval *start, const struct timeval *end) { - long mdiff; - long secdiff = end->tv_sec - start->tv_sec; + /* Sanity check tv_usec */ + if (start->tv_usec > TOR_USEC_PER_SEC || start->tv_usec < 0) { + log_warn(LD_GENERAL, "comparing times on millisecond detail with bad " + "start tv_usec: " I64_FORMAT " microseconds", + I64_PRINTF_ARG(start->tv_usec)); + return LONG_MAX; + } + + if (end->tv_usec > TOR_USEC_PER_SEC || end->tv_usec < 0) { + log_warn(LD_GENERAL, "comparing times on millisecond detail with bad " + "end tv_usec: " I64_FORMAT " microseconds", + I64_PRINTF_ARG(end->tv_usec)); + return LONG_MAX; + }

- /* end->tv_usec - start->tv_usec can be up to 1 second, - * but the mdiff calculation adds another temporary second */ - if (labs(secdiff)+2 > LONG_MAX/1000) { + /* Some BSDs have struct timeval.tv_sec 64-bit, but time_t (and long) 32-bit + */ + int64_t mdiff; + const int64_t secdiff = tv_secdiff_impl(start, end); + + /* end->tv_usec - start->tv_usec can be up to 1 second either way, but the + * mdiff calculation may add another temporary second for rounding. + * Whether this actually causes overflow depends on the compiler's constant + * folding and order of operations. */ + if (secdiff > (int64_t)(LONG_MAX/1000 - 2) || + secdiff < (int64_t)(LONG_MIN/1000 + 1)) { log_warn(LD_GENERAL, "comparing times on millisecond detail too far " - "apart: %ld seconds", secdiff); + "apart: " I64_FORMAT " seconds", I64_PRINTF_ARG(secdiff)); return LONG_MAX; }

/* Subtract and round */ - mdiff = secdiff*1000L + + mdiff = secdiff*1000 + /* We add a million usec here to ensure that the result is positive, * so that the round-towards-zero behavior of the division will give * the right result for rounding to the nearest msec. Later we subtract * 1000 in order to get the correct result. - */ - ((long)end->tv_usec - (long)start->tv_usec + 500L + 1000000L) / 1000L + * We'll never get an overflow here, because we check that both usecs are + * between 0 and TV_USEC_PER_SEC. */ + ((int64_t)end->tv_usec - (int64_t)start->tv_usec + 500 + 1000000) / 1000 - 1000; - return mdiff; + + if (mdiff > (int64_t)LONG_MAX || mdiff < (int64_t)LONG_MIN) { + return LONG_MAX; + } else { + return (long)mdiff; + } }

/**