safe_timer_diff is unsafe under wrapping

safe_timer_diff is meant to avoid overflow (or perhaps negative return values) but doesn't. (It was introduced to tor 0.2.8.0-alpha-dev in #3199 (moved).)

For example:

• safe_timer_diff(INT_MIN, INT_MAX) returns -1 on a system where TIME_T_IS_SIGNED. It should return a (clipped) value representing the largest integer difference possible, such as INT_MAX.

I'm sure there are equivalent issues where TIME_T_IS_UNSIGNED, but I can't think of any right now.

changed milestone to %Tor: 0.2.8.x-final

added component::core tor/tor easy milestone::Tor: 0.2.8.x-final owner::nickm parent::17983 points::small priority::high regression resolution::fixed severity::normal status::closed type::defect version::tor unspecified labels

Make this the child of the periodic events cleanup task

Trac:
Parent: N/A to #17623 (moved)

fwiw, I am about 99% sure that TIME_T_IS_UNSIGNED is never never true.

Trac:
Keywords: N/A deleted, regression added

How to do this patch:

• check that each value is within a sensible range before subtracting them (or adding them)
  • once integer overflow happens in C, it's too late to fix it afterwards
  • remember that INT_MAX - -1 and 0 - INT_MIN both overflow, as does anything larger
  • we want to support times less than zero, because the shadow simulator uses them
• write unit tests for edge cases like:
  • safe_timer_diff(INT_MIN, INT_MAX)
  • safe_timer_diff(-1, INT_MAX)
  • safe_timer_diff(0, INT_MAX)
  • safe_timer_diff(1, INT_MAX)
  • safe_timer_diff(INT_MIN, -1)
  • safe_timer_diff(INT_MIN, 0)
  • safe_timer_diff(INT_MIN, 1)

Trac:
Keywords: N/A deleted, TorCoreTeam201512, easy added

I'd look at a patch for these if we got one, but AFAIK nobody's looking at them right now, and there's no reason to expect them to get done this month.

Trac:
Keywords: TorCoreTeam201512 deleted, N/A added

Trac:
Parent: #17623 (moved) to N/A

It would be great to implement and test this once, and then use it here, and when we parse integers from strings, and perhaps in other locations that (attempt) to detect integer overflow.

I can imagine us wanting the following behaviours:

• saturate (clip to MIN/MAX) on over/underflow
• fail on over/underflow
• wrap on over/underflow (that is, a simple cast to a wide unsigned type)

The checked_add_1() function in http://blog.regehr.org/archives/1139 compiles efficiently on both clang and gcc, let's start with that as a base. (If we need to, we could implement it as a macro which expands into type-specific or outcome-specific functions.)

See also #17983 (moved), #13538 (moved) and http://c-faq.com/misc/sd26.html (which doesn't handle INT_MIN, so it's not that helpful.)

Edit: get bug number correct

Trac:
Parent: N/A to #17983 (moved)

Trac:
Priority: Medium to High

Trac:
Owner: N/A to nickm
Status: new to accepted

bug17682 in my public repository should fix this. It's not the beautiful thing that we might have had in mind, but it has the advantage of having been written.

Trac:
Status: accepted to needs_review

Code review:

+    /* There were no computers at signed TIME_MIN, and nothing that could run
+     * Tor. It's a bug if 'now' is around then. */
+    tor_assert(now > TIME_MIN + LONGEST_TIMER_PERIOD);

Doesn't shadow rely on starting Tor at the epoch? (I think I heard that once, I'm not sure how accurate it is.)

+    if (next < now - LONGEST_TIMER_PERIOD)
+      return LONGEST_TIMER_PERIOD;

Do you mean next > now - LONGEST_TIMER_PERIOD?

Given the assertion, now - LONGEST_TIMER_PERIOD never underflows, so now - LONGEST_TIMER_PERIOD > TIME_MIN. And if next > now, then it's never true that next < now - LONGEST_TIMER_PERIOD.

Trac:
Status: needs_review to needs_revision

Replying to teor:

Code review:

{{{

• /* There were no computers at signed TIME_MIN, and nothing that could run

• * Tor. It's a bug if 'now' is around then. */

• tor_assert(now > TIME_MIN + LONGEST_TIMER_PERIOD); }}} Doesn't shadow rely on starting Tor at the epoch? (I think I heard that once, I'm not sure how accurate it is.)

I believe it once did. But in any case, TIME_MIN on a 32-bit computer isn't 1970 -- it's 1902. And on a 64-bit time_t, it is 292 billion years in the past, whereas current cosmological models only put our universe at 13.8 billion years old.

(I continue to maintained that unsigned time_t doesn't actually exist. Adding a ticket to remove unsigned TIME_T support as #18184 (moved) )

{{{

• if (next < now - LONGEST_TIMER_PERIOD)

•  return LONGEST_TIMER_PERIOD;

}}} Do you mean next > now - LONGEST_TIMER_PERIOD?

Given the assertion, now - LONGEST_TIMER_PERIOD never underflows, so now - LONGEST_TIMER_PERIOD > TIME_MIN. And if next > now, then it's never true that next < now - LONGEST_TIMER_PERIOD.

D'oh. Trying again. I think the fixup in bug17682 should be right.

Looks good, just sent an email to Rob to check out how my vague memories of shadow correspond to reality. But I don't think we need to wait for his reply, we can fix that in another ticket if needed, or he can patch it on his end.

Trac:
Status: needs_revision to needs_review

Replying to nickm:

Replying to teor:

Doesn't shadow rely on starting Tor at the epoch? (I think I heard that once, I'm not sure how accurate it is.)

I believe it once did.

Shadow internally starts at time 0, and maintains a simulation clock that ticks with nanosecond granularity. Because applications like Tor rely on time() and gettimeofday() to properly function, the time that Shadow emulates to Tor indeed starts at the epoch. (I.e., at the first tick, Shadow would return 0 if Tor called time() or gettimeofday()).

The logic for what time gets returned from Shadow to Tor starts here: https://github.com/shadow/shadow/blob/master/src/host/shd-process.c#L3404

Sounds like since time_t is never unsigned, and shadow starts at 0, we'll be fine.

Also sounds like teor thought this would be okay so long as we checked that.

Squashing and merging this.

Trac:
Resolution: N/A to fixed
Status: needs_review to closed

closed

moved to tpo/core/tor#17682 (closed)