commit a09d5f5735abe2e1d16cf0ee9389ae096d5e7ef1 Author: teor <teor2345@gmail.com> Date: Wed Jan 31 11:13:17 2018 +1100 dos: Make sure cc_stats_refill_bucket can't overflow while calculating Debug log the elapsed time in cc_stats_refill_bucket Part of #25094. Signed-off-by: David Goulet <dgoulet@torproject.org> --- src/or/dos.c | 82 +++++++++++++++++++++++++++++++++++++---------------- src/or/dos.h | 2 +- src/test/test_dos.c | 2 +- 3 files changed, 59 insertions(+), 27 deletions(-) diff --git a/src/or/dos.c b/src/or/dos.c index a614d1231..c221e5ecd 100644 --- a/src/or/dos.c +++ b/src/or/dos.c @@ -222,7 +222,7 @@ cc_consensus_has_changed(const networkstatus_t *ns) /** Return the number of circuits we allow per second under the current * configuration. */ -STATIC uint32_t +STATIC uint64_t get_circuit_rate_per_second(void) { return dos_cc_circuit_rate; @@ -234,31 +234,40 @@ get_circuit_rate_per_second(void) STATIC void cc_stats_refill_bucket(cc_client_stats_t *stats, const tor_addr_t *addr) { - uint32_t new_circuit_bucket_count, circuit_rate = 0, num_token; - time_t now, elapsed_time_last_refill; + uint32_t new_circuit_bucket_count; + uint64_t num_token, elapsed_time_last_refill = 0, circuit_rate = 0; + time_t now; + int64_t last_refill_ts; tor_assert(stats); tor_assert(addr); now = approx_time(); + last_refill_ts = (int64_t)stats->last_circ_bucket_refill_ts; - /* We've never filled the bucket so fill it with the maximum being the burst - * and we are done. */ - if (stats->last_circ_bucket_refill_ts == 0) { - num_token = dos_cc_circuit_burst; - goto end; + /* If less than a second has elapsed, don't add any tokens. + * Note: If a relay's clock is ever 0, any new clients won't get a refill + * until the next second. But a relay that thinks it is 1970 will never + * validate the public consensus. */ + if ((int64_t)now == last_refill_ts) { + goto done; } /* At this point, we know we might need to add token to the bucket. We'll - * first compute the circuit rate that is how many circuit are we allowed to - * do per second. */ + * first get the circuit rate that is how many circuit are we allowed to do + * per second. */ circuit_rate = get_circuit_rate_per_second(); - /* How many seconds have elapsed between now and the last refill? */ - elapsed_time_last_refill = now - stats->last_circ_bucket_refill_ts; + /* We've never filled the bucket so fill it with the maximum being the burst + * and we are done. + * Note: If a relay's clock is ever 0, all clients that were last refilled + * in that zero second will get a full refill here. */ + if (last_refill_ts == 0) { + num_token = dos_cc_circuit_burst; + goto end; + } - /* If the elapsed time is below 0 it means our clock jumped backward so in - * that case, lets be safe and fill it up to the maximum. Not filling it + /* Our clock jumped backward so fill it up to the maximum. Not filling it * could trigger a detection for a valid client. Also, if the clock jumped * negative but we didn't notice until the elapsed time became positive * again, then we potentially spent many seconds not refilling the bucket @@ -266,28 +275,51 @@ cc_stats_refill_bucket(cc_client_stats_t *stats, const tor_addr_t *addr) * until now means that no circuit creation requests came in during that * time, so the client doesn't end up punished that much from this hopefully * rare situation.*/ - if (elapsed_time_last_refill < 0) { - /* Dividing the burst by the circuit rate gives us the time span that will - * give us the maximum allowed value of token. */ - elapsed_time_last_refill = (dos_cc_circuit_burst / circuit_rate); + if ((int64_t)now < last_refill_ts) { + /* Use the maximum allowed value of token. */ + num_token = dos_cc_circuit_burst; + goto end; + } + + /* How many seconds have elapsed between now and the last refill? + * This subtraction can't underflow, because now >= last_refill_ts. + * And it can't overflow, because INT64_MAX - (-INT64_MIN) == UINT64_MAX. */ + elapsed_time_last_refill = (uint64_t)now - last_refill_ts; + + /* If the elapsed time is very large, it means our clock jumped forward. + * If the multiplication would overflow, use the maximum allowed value. */ + if (elapsed_time_last_refill > UINT32_MAX) { + num_token = dos_cc_circuit_burst; + goto end; } /* Compute how many circuits we are allowed in that time frame which we'll - * add to the bucket. This can be big but it is cap to a maximum after. */ + * add to the bucket. This can't overflow, because both multiplicands + * are less than or equal to UINT32_MAX, and num_token is uint64_t. */ num_token = elapsed_time_last_refill * circuit_rate; end: - /* We cap the bucket to the burst value else this could grow to infinity - * over time. */ - new_circuit_bucket_count = MIN(stats->circuit_bucket + num_token, - dos_cc_circuit_burst); + /* If the sum would overflow, use the maximum allowed value. */ + if (num_token > UINT32_MAX - stats->circuit_bucket) { + new_circuit_bucket_count = dos_cc_circuit_burst; + } else { + /* We cap the bucket to the burst value else this could overflow uint32_t + * over time. */ + new_circuit_bucket_count = MIN(stats->circuit_bucket + (uint32_t)num_token, + dos_cc_circuit_burst); + } + /* This function is not allowed to make the bucket count smaller */ + tor_assert_nonfatal(new_circuit_bucket_count >= stats->circuit_bucket); log_debug(LD_DOS, "DoS address %s has its circuit bucket value: %" PRIu32 - ". Filling it to %" PRIu32 ". Circuit rate is %" PRIu32, + ". Filling it to %" PRIu32 ". Circuit rate is %" PRIu64 + ". Elapsed time is %" PRIi64, fmt_addr(addr), stats->circuit_bucket, new_circuit_bucket_count, - circuit_rate); + circuit_rate, (int64_t)elapsed_time_last_refill); stats->circuit_bucket = new_circuit_bucket_count; stats->last_circ_bucket_refill_ts = now; + + done: return; } diff --git a/src/or/dos.h b/src/or/dos.h index 8695512ea..5d35a2b12 100644 --- a/src/or/dos.h +++ b/src/or/dos.h @@ -125,7 +125,7 @@ STATIC uint32_t get_param_cc_circuit_burst(const networkstatus_t *ns); STATIC uint32_t get_param_cc_min_concurrent_connection( const networkstatus_t *ns); -STATIC uint32_t get_circuit_rate_per_second(void); +STATIC uint64_t get_circuit_rate_per_second(void); STATIC void cc_stats_refill_bucket(cc_client_stats_t *stats, const tor_addr_t *addr); diff --git a/src/test/test_dos.c b/src/test/test_dos.c index 80abc1937..7fe549560 100644 --- a/src/test/test_dos.c +++ b/src/test/test_dos.c @@ -176,7 +176,7 @@ test_dos_bucket_refill(void *arg) /* Initialize DoS subsystem and get relevant limits */ dos_init(); uint32_t max_circuit_count = get_param_cc_circuit_burst(NULL); - int circ_rate = get_circuit_rate_per_second(); + uint64_t circ_rate = get_circuit_rate_per_second(); /* Check that the circuit rate is a positive number and smaller than the max * circuit count */ tt_int_op(circ_rate, OP_GT, 1);