Opened 3 years ago

Closed 3 years ago

#17682 closed defect (fixed)

safe_timer_diff is unsafe under wrapping

Reported by: teor Owned by: nickm
Priority: High Milestone: Tor: 0.2.8.x-final
Component: Core Tor/Tor Version: Tor: unspecified
Severity: Normal Keywords: regression, easy
Cc: Actual Points:
Parent ID: #17983 Points: small
Reviewer: Sponsor:

Description

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

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.

Child Tickets

Change History (16)

comment:1 Changed 3 years ago by teor

Parent ID: #17623

Make this the child of the periodic events cleanup task

comment:2 Changed 3 years ago by nickm

Keywords: regression added

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

comment:3 Changed 3 years ago by teor

Keywords: easy TorCoreTeam201512 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)

comment:4 Changed 3 years ago by nickm

Keywords: TorCoreTeam201512 removed

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.

comment:5 Changed 3 years ago by teor

Parent ID: #17623

comment:6 Changed 3 years ago by teor

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

comment:7 Changed 3 years ago by teor

See also #17983, #13538 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

Last edited 3 years ago by teor (previous) (diff)

comment:8 Changed 3 years ago by teor

Parent ID: #17983

comment:9 Changed 3 years ago by nickm

Priority: MediumHigh

comment:10 Changed 3 years ago by nickm

Owner: set to nickm
Status: newaccepted

comment:11 Changed 3 years ago by nickm

Status: acceptedneeds_review

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.

comment:12 Changed 3 years ago by teor

Status: needs_reviewneeds_revision

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.

comment:13 in reply to:  12 ; Changed 3 years ago by nickm

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 )

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

comment:14 Changed 3 years ago by teor

Status: needs_revisionneeds_review

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.

comment:15 in reply to:  13 Changed 3 years ago by robgjansen

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

comment:16 Changed 3 years ago by nickm

Resolution: fixed
Status: needs_reviewclosed

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.

Note: See TracTickets for help on using tickets.