Opened 4 months ago

Last modified 4 weeks ago

#31482 needs_revision defect

Avoid possible overflow when converting between coarse stamp to approx ms

Reported by: teor Owned by: teor
Priority: Medium Milestone: Tor: 0.4.3.x-final
Component: Core Tor/Tor Version: Tor: 0.3.4.1-alpha
Severity: Normal Keywords: 043-should, 035-backport, 040-backport, 041-backport, 042-backport
Cc: nickm, gaba Actual Points: 0.5
Parent ID: Points: 1
Reviewer: nickm Sponsor:

Description

Our coarse monotonic time conversion code can overflow on some platforms.

In particular, passing a large rate to a token bucket will overflow on iOS, and any other platform where monotime.numerator2 / monotime.denominator > 512.

I have a fix that makes sure that token bucket's rate_per_sec_to_rate_per_sec() can't cause an overflow. I can do tests and a changes file after nickm answers some of my remaining questions.

Gaba, this is a fix on a refactor for #25766, which was originally for sponsor 8. Are refactor bug fixes covered by sponsor 31 now?

Child Tickets

Change History (8)

comment:1 Changed 4 months ago by teor

Reviewer: nickm

Here's a draft fix for initial review:

Here's my TODO list:

  • changes file
  • tests for simplify_fraction32()
  • tests for monotime_coarse_stamp_units_to_approx_msec() and monotime_msec_to_approx_coarse_stamp_units(), underflow and overflow

I have some questions:

  • do I need to do any extra tests for monotime_init_internal()
  • does anyone run our unit tests on iOS?
  • how serious is this bug in rate_per_sec_to_rate_per_step()? Do we actually use token bucket rates close to 230? Is my math on that limit correct?
  • are there any other callers of monotime_coarse_stamp_units_to_approx_msec() or monotime_msec_to_approx_coarse_stamp_units() that might trigger this bug?
  • Have I missed anything?

Edit: fix typo

Last edited 7 weeks ago by teor (previous) (diff)

comment:2 Changed 4 months ago by teor

Status: assignedneeds_review

comment:3 Changed 4 months ago by teor

One more question:

  • Do we need to make a similar change to the Windows code?
    • If so, should we abstract the common parts of these functions, to avoid duplicate code? (in a new ticket?)

comment:4 Changed 4 months ago by nickm

Status: needs_reviewneeds_revision

I don't see any problems in the patch as written, but I do support doing the TODO items.

We should also base this on maint-0.3.5 if the bug is there.

To try to answer your questions:

do I need to do any extra tests for monotime_init_internal()

Maybe it would be good to extract the computation to a new STATIC function, and then test that new function. That way we can make sure that the stuff calculated by monotime_init_internal() looks the way we expect with different inputs.

does anyone run our unit tests on iOS?

I'm not sure; Guardian might?

I can easily believe that nobody has tried rate-limiting on iOS.

how serious is this bug in rate_per_sec_to_rate_per_step()? Do we actually use token bucket rates close to 230? Is my math on that limit correct?

I think that if it only affects iOS, it's not that bad, but we should backport anyway. I am not 100% sure on your math on the limit; tests there would make me more confident.

are there any other callers of monotime_coarse_stamp_units_to_approx_msec() or monotime_msec_to_approx_coarse_stamp_units() that might trigger this bug?

There's a safe call in relay.c, and that's all I can see outside of the unit tests.

Do we need to make a similar change to the Windows code?

I don't think so, though doing a GCD calculation on init wouldn't hurt.

For windows, the fraction is "nsec per tick", which is unlikely to need a very big denominator.

Edit: fix typo

Last edited 7 weeks ago by teor (previous) (diff)

comment:5 Changed 3 months ago by nickm

Keywords: 042-should added

Mark some needs_revision tickets as 042-should

comment:6 Changed 7 weeks ago by teor

Work in progress draft:

Done:

  • rebase to 0.3.5
  • tests for simplify_fraction32()

In Progress:

  • tests for monotime_coarse_stamp_units_to_approx_msec() and monotime_msec_to_approx_coarse_stamp_units()
    • more values
    • precise and approximate cases, and their boundary conditions
    • underflow and overflow (close to 230 ?)

TODO:

  • do a GCD calculation on Windows init
  • refactor and extra tests for monotime_init_internal()
  • changes file

comment:7 Changed 7 weeks ago by teor

macOS fails with:

util/monotonic_time: 
  FAIL src/test/test_util.c:6211: assert(rep_units OP_EQ units): 9534 vs 9536
  [monotonic_time FAILED]

comment:8 Changed 4 weeks ago by teor

Keywords: 043-should 042-backport added; 042-should removed
Milestone: Tor: 0.4.2.x-finalTor: 0.4.3.x-final

We're at rc stage for 0.4.2, so this ticket isn't going to make it in.

Note: See TracTickets for help on using tickets.