Opened 10 years ago

Last modified 7 years ago

#1203 closed defect (Fixed)

smartlist_choose_by_bandwidth() uses crypto_rand_uint64() wrong

Reported by: arma Owned by:
Priority: Low Milestone:
Component: Core Tor/Tor Version: 0.2.1.21
Severity: Keywords:
Cc: arma, Sebastian, nickm Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

In smartlist_choose_by_bandwidth(), we sum up all the bandwidths available
and then use crypto_rand_uint64() to pick which relay we'll use. But we
have an off-by-one error.

Imagine there are three relays, each with bandwidth 1. So total_bw is 3.
So crypto_rand_uint64() can return {0, 1, 2} with equal probability.

Suppose it returns 1.

Then we go through the first round of the for() loop, at the end of which tmp = 1.

So 1 >= 1, and we break. We return the first relay when we should have returned
the second.

Ok, so this is a really crazy case that will never happen in practice, right?
Not quite.

First, it could have been triggered in the pathological case described by kenobi
here (if we hadn't accidentally made it much less likely by moving to KB in the
consensus):
https://bugs.torproject.org/flyspray/index.php?do=details&id=1194&area=comments#3664
Second, imagine if the first relay has 0 bandwidth, and the other relays have
some bandwidth. If crypto_rand_uint64() returns 0, we'll pick the first relay even
though it has no weight.

The fix (well, hack) is to set rand_bw++ once we've chosen it. Then we count our
fenceposts correctly.

In theory, we shouldn't run into the round-off error warn at the end of the for()
clause. Heck if I know how it'll go in practice though.

Thanks to kenobi for diagnosing and coming up with the fix.

[Automatically added by flyspray2trac: Operating System: All]

Child Tickets

Change History (3)

comment:1 Changed 10 years ago by arma

Fixed in 0.2.2.7-alpha.

comment:2 Changed 10 years ago by arma

flyspray2trac: bug closed.

comment:3 Changed 7 years ago by nickm

Component: Tor ClientTor
Note: See TracTickets for help on using tickets.