diff options
Diffstat (limited to 'src/or/circuitbuild.c')
| -rw-r--r-- | src/or/circuitbuild.c | 1723 |
1 files changed, 145 insertions, 1578 deletions
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index 4603de071f..897f90fe4c 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -9,8 +9,11 @@ * \brief The actual details of building circuits. **/ +#define CIRCUITBUILD_PRIVATE + #include "or.h" #include "channel.h" +#include "circpathbias.h" #include "circuitbuild.h" #include "circuitlist.h" #include "circuitstats.h" @@ -40,19 +43,11 @@ #include "routerparse.h" #include "routerset.h" #include "crypto.h" -#include "connection_edge.h" #ifndef MIN #define MIN(a,b) ((a)<(b)?(a):(b)) #endif -/********* START VARIABLES **********/ - -/** A global list of all circuits at this hop. */ -extern circuit_t *global_circuitlist; - -/********* END VARIABLES ************/ - static channel_t * channel_connect_for_circuit(const tor_addr_t *addr, uint16_t port, const char *id_digest); @@ -64,14 +59,6 @@ static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath); static int onion_extend_cpath(origin_circuit_t *circ); static int count_acceptable_nodes(smartlist_t *routers); static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice); -static int entry_guard_inc_circ_attempt_count(entry_guard_t *guard); -static void pathbias_count_build_success(origin_circuit_t *circ); -static void pathbias_count_successful_close(origin_circuit_t *circ); -static void pathbias_count_collapse(origin_circuit_t *circ); -static void pathbias_count_use_failed(origin_circuit_t *circ); -static void pathbias_measure_use_rate(entry_guard_t *guard); -static void pathbias_measure_close_rate(entry_guard_t *guard); -static void pathbias_scale_use_rates(entry_guard_t *guard); #ifdef CURVE25519_ENABLED static int circuits_can_use_ntor(void); #endif @@ -92,18 +79,29 @@ channel_connect_for_circuit(const tor_addr_t *addr, uint16_t port, return chan; } -/** Iterate over values of circ_id, starting from conn-\>next_circ_id, - * and with the high bit specified by conn-\>circ_id_type, until we get - * a circ_id that is not in use by any other circuit on that conn. +/** Search for a value for circ_id that we can use on <b>chan</b> for an + * outbound circuit, until we get a circ_id that is not in use by any other + * circuit on that conn. * * Return it, or 0 if can't get a unique circ_id. */ -static circid_t +STATIC circid_t get_unique_circ_id_by_chan(channel_t *chan) { +/* This number is chosen somewhat arbitrarily; see comment below for more + * info. When the space is 80% full, it gives a one-in-a-million failure + * chance; when the space is 90% full, it gives a one-in-850 chance; and when + * the space is 95% full, it gives a one-in-26 failure chance. That seems + * okay, though you could make a case IMO for anything between N=32 and + * N=256. */ +#define MAX_CIRCID_ATTEMPTS 64 + int in_use; + unsigned n_with_circ = 0, n_pending_destroy = 0, n_weird_pending_destroy = 0; circid_t test_circ_id; circid_t attempts=0; - circid_t high_bit, max_range; + circid_t high_bit, max_range, mask; + int64_t pending_destroy_time_total = 0; + int64_t pending_destroy_time_max = 0; tor_assert(chan); @@ -113,32 +111,108 @@ get_unique_circ_id_by_chan(channel_t *chan) "a client with no identity."); return 0; } - max_range = (chan->wide_circ_ids) ? (1u<<31) : (1u<<15); + max_range = (chan->wide_circ_ids) ? (1u<<31) : (1u<<15); + mask = max_range - 1; high_bit = (chan->circ_id_type == CIRC_ID_TYPE_HIGHER) ? max_range : 0; do { - /* Sequentially iterate over test_circ_id=1...max_range until we find a - * circID such that (high_bit|test_circ_id) is not already used. */ - test_circ_id = chan->next_circ_id++; - if (test_circ_id == 0 || test_circ_id >= max_range) { - test_circ_id = 1; - chan->next_circ_id = 2; - } - if (++attempts > max_range) { - /* Make sure we don't loop forever if all circ_id's are used. This - * matters because it's an external DoS opportunity. + if (++attempts > MAX_CIRCID_ATTEMPTS) { + /* Make sure we don't loop forever because all circuit IDs are used. + * + * Once, we would try until we had tried every possible circuit ID. But + * that's quite expensive. Instead, we try MAX_CIRCID_ATTEMPTS random + * circuit IDs, and then give up. + * + * This potentially causes us to give up early if our circuit ID space + * is nearly full. If we have N circuit IDs in use, then we will reject + * a new circuit with probability (N / max_range) ^ MAX_CIRCID_ATTEMPTS. + * This means that in practice, a few percent of our circuit ID capacity + * will go unused. + * + * The alternative here, though, is to do a linear search over the + * whole circuit ID space every time we extend a circuit, which is + * not so great either. */ - if (! chan->warned_circ_ids_exhausted) { - chan->warned_circ_ids_exhausted = 1; - log_warn(LD_CIRC,"No unused circIDs found on channel %s wide " + int64_t queued_destroys; + char *m = rate_limit_log(&chan->last_warned_circ_ids_exhausted, + approx_time()); + if (m == NULL) + return 0; /* This message has been rate-limited away. */ + if (n_pending_destroy) + pending_destroy_time_total /= n_pending_destroy; + log_warn(LD_CIRC,"No unused circIDs found on channel %s wide " "circID support, with %u inbound and %u outbound circuits. " - "Failing a circuit.", + "Found %u circuit IDs in use by circuits, and %u with " + "pending destroy cells. (%u of those were marked bogusly.) " + "The ones with pending destroy cells " + "have been marked unusable for an average of %ld seconds " + "and a maximum of %ld seconds. This channel is %ld seconds " + "old. Failing a circuit.%s", chan->wide_circ_ids ? "with" : "without", - chan->num_p_circuits, chan->num_n_circuits); + chan->num_p_circuits, chan->num_n_circuits, + n_with_circ, n_pending_destroy, n_weird_pending_destroy, + (long)pending_destroy_time_total, + (long)pending_destroy_time_max, + (long)(approx_time() - chan->timestamp_created), + m); + tor_free(m); + + if (!chan->cmux) { + /* This warning should be impossible. */ + log_warn(LD_BUG, " This channel somehow has no cmux on it!"); + return 0; } + + /* analysis so far on 12184 suggests that we're running out of circuit + IDs because it looks like we have too many pending destroy + cells. Let's see how many we really have pending. + */ + queued_destroys = circuitmux_count_queued_destroy_cells(chan, + chan->cmux); + + log_warn(LD_CIRC, " Circuitmux on this channel has %u circuits, " + "of which %u are active. It says it has "I64_FORMAT + " destroy cells queued.", + circuitmux_num_circuits(chan->cmux), + circuitmux_num_active_circuits(chan->cmux), + I64_PRINTF_ARG(queued_destroys)); + + /* Change this into "if (1)" in order to get more information about + * possible failure modes here. You'll need to know how to use gdb with + * Tor: this will make Tor exit with an assertion failure if the cmux is + * corrupt. */ + if (0) + circuitmux_assert_okay(chan->cmux); + + channel_dump_statistics(chan, LOG_WARN); + return 0; } + + do { + crypto_rand((char*) &test_circ_id, sizeof(test_circ_id)); + test_circ_id &= mask; + } while (test_circ_id == 0); + test_circ_id |= high_bit; - } while (circuit_id_in_use_on_channel(test_circ_id, chan)); + + in_use = circuit_id_in_use_on_channel(test_circ_id, chan); + if (in_use == 1) + ++n_with_circ; + else if (in_use == 2) { + time_t since_when; + ++n_pending_destroy; + since_when = + circuit_id_when_marked_unusable_on_channel(test_circ_id, chan); + if (since_when) { + time_t waiting = approx_time() - since_when; + pending_destroy_time_total += waiting; + if (waiting > pending_destroy_time_max) + pending_destroy_time_max = waiting; + } else { + ++n_weird_pending_destroy; + } + } + } while (in_use); return test_circ_id; } @@ -299,9 +373,9 @@ circuit_rep_hist_note_result(origin_circuit_t *circ) static int circuit_cpath_supports_ntor(const origin_circuit_t *circ) { - crypt_path_t *head = circ->cpath, *cpath = circ->cpath; + crypt_path_t *head, *cpath; - cpath = head; + cpath = head = circ->cpath; do { if (cpath->extend_info && !tor_mem_is_zero( @@ -475,6 +549,7 @@ circuit_handle_first_hop(origin_circuit_t *circ) log_debug(LD_CIRC,"Conn open. Delivering first onion skin."); if ((err_reason = circuit_send_next_onion_skin(circ)) < 0) { log_info(LD_CIRC,"circuit_send_next_onion_skin failed."); + circ->base_.n_chan = NULL; return err_reason; } } @@ -583,19 +658,21 @@ circuit_deliver_create_cell(circuit_t *circ, const create_cell_t *create_cell, id = get_unique_circ_id_by_chan(circ->n_chan); if (!id) { - log_warn(LD_CIRC,"failed to get unique circID."); - return -1; + static ratelim_t circid_warning_limit = RATELIM_INIT(9600); + log_fn_ratelim(&circid_warning_limit, LOG_WARN, LD_CIRC, + "failed to get unique circID."); + goto error; } - log_debug(LD_CIRC,"Chosen circID %u.", (unsigned)id); - circuit_set_n_circid_chan(circ, id, circ->n_chan); memset(&cell, 0, sizeof(cell_t)); r = relayed ? create_cell_format_relayed(&cell, create_cell) : create_cell_format(&cell, create_cell); if (r < 0) { log_warn(LD_CIRC,"Couldn't format create cell"); - return -1; + goto error; } + log_debug(LD_CIRC,"Chosen circID %u.", (unsigned)id); + circuit_set_n_circid_chan(circ, id, circ->n_chan); cell.circ_id = circ->n_circ_id; append_cell_to_circuit_queue(circ, circ->n_chan, &cell, @@ -619,6 +696,9 @@ circuit_deliver_create_cell(circuit_t *circ, const create_cell_t *create_cell, } return 0; + error: + circ->n_chan = NULL; + return -1; } /** We've decided to start our reachability testing. If all @@ -628,27 +708,30 @@ int inform_testing_reachability(void) { char dirbuf[128]; + char *address; const routerinfo_t *me = router_get_my_routerinfo(); if (!me) return 0; + address = tor_dup_ip(me->addr); control_event_server_status(LOG_NOTICE, "CHECKING_REACHABILITY ORADDRESS=%s:%d", - me->address, me->or_port); + address, me->or_port); if (me->dir_port) { tor_snprintf(dirbuf, sizeof(dirbuf), " and DirPort %s:%d", - me->address, me->dir_port); + address, me->dir_port); control_event_server_status(LOG_NOTICE, "CHECKING_REACHABILITY DIRADDRESS=%s:%d", - me->address, me->dir_port); + address, me->dir_port); } log_notice(LD_OR, "Now checking whether ORPort %s:%d%s %s reachable... " "(this may take up to %d minutes -- look for log " "messages indicating success)", - me->address, me->or_port, + address, me->or_port, me->dir_port ? dirbuf : "", me->dir_port ? "are" : "is", TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT/60); + tor_free(address); return 1; } @@ -844,20 +927,24 @@ circuit_send_next_onion_skin(origin_circuit_t *circ) * it off at, we probably had a suspend event along this codepath, * and we should discard the value. */ - if (timediff < 0 || timediff > 2*circ_times.close_ms+1000) { + if (timediff < 0 || + timediff > 2*get_circuit_build_close_time_ms()+1000) { log_notice(LD_CIRC, "Strange value for circuit build time: %ldmsec. " "Assuming clock jump. Purpose %d (%s)", timediff, circ->base_.purpose, circuit_purpose_to_string(circ->base_.purpose)); } else if (!circuit_build_times_disabled()) { /* Only count circuit times if the network is live */ - if (circuit_build_times_network_check_live(&circ_times)) { - circuit_build_times_add_time(&circ_times, (build_time_t)timediff); - circuit_build_times_set_timeout(&circ_times); + if (circuit_build_times_network_check_live( + get_circuit_build_times())) { + circuit_build_times_add_time(get_circuit_build_times_mutable(), + (build_time_t)timediff); + circuit_build_times_set_timeout(get_circuit_build_times_mutable()); } if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) { - circuit_build_times_network_circ_success(&circ_times); + circuit_build_times_network_circ_success( + get_circuit_build_times_mutable()); } } } @@ -1152,1516 +1239,6 @@ circuit_init_cpath_crypto(crypt_path_t *cpath, const char *key_data, return 0; } -/** The minimum number of circuit attempts before we start - * thinking about warning about path bias and dropping guards */ -static int -pathbias_get_min_circs(const or_options_t *options) -{ -#define DFLT_PATH_BIAS_MIN_CIRC 150 - if (options->PathBiasCircThreshold >= 5) - return options->PathBiasCircThreshold; - else - return networkstatus_get_param(NULL, "pb_mincircs", - DFLT_PATH_BIAS_MIN_CIRC, - 5, INT32_MAX); -} - -/** The circuit success rate below which we issue a notice */ -static double -pathbias_get_notice_rate(const or_options_t *options) -{ -#define DFLT_PATH_BIAS_NOTICE_PCT 70 - if (options->PathBiasNoticeRate >= 0.0) - return options->PathBiasNoticeRate; - else - return networkstatus_get_param(NULL, "pb_noticepct", - DFLT_PATH_BIAS_NOTICE_PCT, 0, 100)/100.0; -} - -/* XXXX024 I'd like to have this be static again, but entrynodes.c needs it. */ -/** The circuit success rate below which we issue a warn */ -static double -pathbias_get_warn_rate(const or_options_t *options) -{ -#define DFLT_PATH_BIAS_WARN_PCT 50 - if (options->PathBiasWarnRate >= 0.0) - return options->PathBiasWarnRate; - else - return networkstatus_get_param(NULL, "pb_warnpct", - DFLT_PATH_BIAS_WARN_PCT, 0, 100)/100.0; -} - -/* XXXX024 I'd like to have this be static again, but entrynodes.c needs it. */ -/** - * The extreme rate is the rate at which we would drop the guard, - * if pb_dropguard is also set. Otherwise we just warn. - */ -double -pathbias_get_extreme_rate(const or_options_t *options) -{ -#define DFLT_PATH_BIAS_EXTREME_PCT 30 - if (options->PathBiasExtremeRate >= 0.0) - return options->PathBiasExtremeRate; - else - return networkstatus_get_param(NULL, "pb_extremepct", - DFLT_PATH_BIAS_EXTREME_PCT, 0, 100)/100.0; -} - -/* XXXX024 I'd like to have this be static again, but entrynodes.c needs it. */ -/** - * If 1, we actually disable use of guards that fall below - * the extreme_pct. - */ -int -pathbias_get_dropguards(const or_options_t *options) -{ -#define DFLT_PATH_BIAS_DROP_GUARDS 0 - if (options->PathBiasDropGuards >= 0) - return options->PathBiasDropGuards; - else - return networkstatus_get_param(NULL, "pb_dropguards", - DFLT_PATH_BIAS_DROP_GUARDS, 0, 1); -} - -/** - * This is the number of circuits at which we scale our - * counts by mult_factor/scale_factor. Note, this count is - * not exact, as we only perform the scaling in the event - * of no integer truncation. - */ -static int -pathbias_get_scale_threshold(const or_options_t *options) -{ -#define DFLT_PATH_BIAS_SCALE_THRESHOLD 300 - if (options->PathBiasScaleThreshold >= 10) - return options->PathBiasScaleThreshold; - else - return networkstatus_get_param(NULL, "pb_scalecircs", - DFLT_PATH_BIAS_SCALE_THRESHOLD, 10, - INT32_MAX); -} - -/** - * Compute the path bias scaling ratio from the consensus - * parameters pb_multfactor/pb_scalefactor. - * - * Returns a value in (0, 1.0] which we multiply our pathbias - * counts with to scale them down. - */ -static double -pathbias_get_scale_ratio(const or_options_t *options) -{ - /* - * The scale factor is the denominator for our scaling - * of circuit counts for our path bias window. - * - * Note that our use of doubles for the path bias state - * file means that powers of 2 work best here. - */ - int denominator = networkstatus_get_param(NULL, "pb_scalefactor", - 2, 2, INT32_MAX); - (void) options; - /** - * The mult factor is the numerator for our scaling - * of circuit counts for our path bias window. It - * allows us to scale by fractions. - */ - return networkstatus_get_param(NULL, "pb_multfactor", - 1, 1, denominator)/((double)denominator); -} - -/** The minimum number of circuit usage attempts before we start - * thinking about warning about path use bias and dropping guards */ -static int -pathbias_get_min_use(const or_options_t *options) -{ -#define DFLT_PATH_BIAS_MIN_USE 20 - if (options->PathBiasUseThreshold >= 3) - return options->PathBiasUseThreshold; - else - return networkstatus_get_param(NULL, "pb_minuse", - DFLT_PATH_BIAS_MIN_USE, - 3, INT32_MAX); -} - -/** The circuit use success rate below which we issue a notice */ -static double -pathbias_get_notice_use_rate(const or_options_t *options) -{ -#define DFLT_PATH_BIAS_NOTICE_USE_PCT 80 - if (options->PathBiasNoticeUseRate >= 0.0) - return options->PathBiasNoticeUseRate; - else - return networkstatus_get_param(NULL, "pb_noticeusepct", - DFLT_PATH_BIAS_NOTICE_USE_PCT, - 0, 100)/100.0; -} - -/** - * The extreme use rate is the rate at which we would drop the guard, - * if pb_dropguard is also set. Otherwise we just warn. - */ -double -pathbias_get_extreme_use_rate(const or_options_t *options) -{ -#define DFLT_PATH_BIAS_EXTREME_USE_PCT 60 - if (options->PathBiasExtremeUseRate >= 0.0) - return options->PathBiasExtremeUseRate; - else - return networkstatus_get_param(NULL, "pb_extremeusepct", - DFLT_PATH_BIAS_EXTREME_USE_PCT, - 0, 100)/100.0; -} - -/** - * This is the number of circuits at which we scale our - * use counts by mult_factor/scale_factor. Note, this count is - * not exact, as we only perform the scaling in the event - * of no integer truncation. - */ -static int -pathbias_get_scale_use_threshold(const or_options_t *options) -{ -#define DFLT_PATH_BIAS_SCALE_USE_THRESHOLD 100 - if (options->PathBiasScaleUseThreshold >= 10) - return options->PathBiasScaleUseThreshold; - else - return networkstatus_get_param(NULL, "pb_scaleuse", - DFLT_PATH_BIAS_SCALE_USE_THRESHOLD, - 10, INT32_MAX); -} - -/** - * Convert a Guard's path state to string. - */ -const char * -pathbias_state_to_string(path_state_t state) -{ - switch (state) { - case PATH_STATE_NEW_CIRC: - return "new"; - case PATH_STATE_BUILD_ATTEMPTED: - return "build attempted"; - case PATH_STATE_BUILD_SUCCEEDED: - return "build succeeded"; - case PATH_STATE_USE_ATTEMPTED: - return "use attempted"; - case PATH_STATE_USE_SUCCEEDED: - return "use succeeded"; - case PATH_STATE_USE_FAILED: - return "use failed"; - case PATH_STATE_ALREADY_COUNTED: - return "already counted"; - } - - return "unknown"; -} - -/** - * This function decides if a circuit has progressed far enough to count - * as a circuit "attempt". As long as end-to-end tagging is possible, - * we assume the adversary will use it over hop-to-hop failure. Therefore, - * we only need to account bias for the last hop. This should make us - * much more resilient to ambient circuit failure, and also make that - * failure easier to measure (we only need to measure Exit failure rates). - */ -static int -pathbias_is_new_circ_attempt(origin_circuit_t *circ) -{ -#define N2N_TAGGING_IS_POSSIBLE -#ifdef N2N_TAGGING_IS_POSSIBLE - /* cpath is a circular list. We want circs with more than one hop, - * and the second hop must be waiting for keys still (it's just - * about to get them). */ - return circ->cpath && - circ->cpath->next != circ->cpath && - circ->cpath->next->state == CPATH_STATE_AWAITING_KEYS; -#else - /* If tagging attacks are no longer possible, we probably want to - * count bias from the first hop. However, one could argue that - * timing-based tagging is still more useful than per-hop failure. - * In which case, we'd never want to use this. - */ - return circ->cpath && - circ->cpath->state == CPATH_STATE_AWAITING_KEYS; -#endif -} - -/** - * Decide if the path bias code should count a circuit. - * - * @returns 1 if we should count it, 0 otherwise. - */ -static int -pathbias_should_count(origin_circuit_t *circ) -{ -#define PATHBIAS_COUNT_INTERVAL (600) - static ratelim_t count_limit = - RATELIM_INIT(PATHBIAS_COUNT_INTERVAL); - char *rate_msg = NULL; - - /* We can't do path bias accounting without entry guards. - * Testing and controller circuits also have no guards. - * - * We also don't count server-side rends, because their - * endpoint could be chosen maliciously. - * Similarly, we can't count client-side intro attempts, - * because clients can be manipulated into connecting to - * malicious intro points. */ - if (get_options()->UseEntryGuards == 0 || - circ->base_.purpose == CIRCUIT_PURPOSE_TESTING || - circ->base_.purpose == CIRCUIT_PURPOSE_CONTROLLER || - circ->base_.purpose == CIRCUIT_PURPOSE_S_CONNECT_REND || - circ->base_.purpose == CIRCUIT_PURPOSE_S_REND_JOINED || - (circ->base_.purpose >= CIRCUIT_PURPOSE_C_INTRODUCING && - circ->base_.purpose <= CIRCUIT_PURPOSE_C_INTRODUCE_ACKED)) { - - /* Check to see if the shouldcount result has changed due to a - * unexpected purpose change that would affect our results. - * - * The reason we check the path state too here is because for the - * cannibalized versions of these purposes, we count them as successful - * before their purpose change. - */ - if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_COUNTED - && circ->path_state != PATH_STATE_ALREADY_COUNTED) { - log_info(LD_BUG, - "Circuit %d is now being ignored despite being counted " - "in the past. Purpose is %s, path state is %s", - circ->global_identifier, - circuit_purpose_to_string(circ->base_.purpose), - pathbias_state_to_string(circ->path_state)); - } - circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_IGNORED; - return 0; - } - - /* Completely ignore one hop circuits */ - if (circ->build_state->onehop_tunnel || - circ->build_state->desired_path_len == 1) { - /* Check for inconsistency */ - if (circ->build_state->desired_path_len != 1 || - !circ->build_state->onehop_tunnel) { - if ((rate_msg = rate_limit_log(&count_limit, approx_time()))) { - log_info(LD_BUG, - "One-hop circuit has length %d. Path state is %s. " - "Circuit is a %s currently %s.%s", - circ->build_state->desired_path_len, - pathbias_state_to_string(circ->path_state), - circuit_purpose_to_string(circ->base_.purpose), - circuit_state_to_string(circ->base_.state), - rate_msg); - tor_free(rate_msg); - } - tor_fragile_assert(); - } - - /* Check to see if the shouldcount result has changed due to a - * unexpected change that would affect our results */ - if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_COUNTED) { - log_info(LD_BUG, - "One-hop circuit %d is now being ignored despite being counted " - "in the past. Purpose is %s, path state is %s", - circ->global_identifier, - circuit_purpose_to_string(circ->base_.purpose), - pathbias_state_to_string(circ->path_state)); - } - circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_IGNORED; - return 0; - } - - /* Check to see if the shouldcount result has changed due to a - * unexpected purpose change that would affect our results */ - if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_IGNORED) { - log_info(LD_BUG, - "Circuit %d is now being counted despite being ignored " - "in the past. Purpose is %s, path state is %s", - circ->global_identifier, - circuit_purpose_to_string(circ->base_.purpose), - pathbias_state_to_string(circ->path_state)); - } - circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_COUNTED; - - return 1; -} - -/** - * Check our circuit state to see if this is a successful circuit attempt. - * If so, record it in the current guard's path bias circ_attempt count. - * - * Also check for several potential error cases for bug #6475. - */ -static int -pathbias_count_build_attempt(origin_circuit_t *circ) -{ -#define CIRC_ATTEMPT_NOTICE_INTERVAL (600) - static ratelim_t circ_attempt_notice_limit = - RATELIM_INIT(CIRC_ATTEMPT_NOTICE_INTERVAL); - char *rate_msg = NULL; - - if (!pathbias_should_count(circ)) { - return 0; - } - - if (pathbias_is_new_circ_attempt(circ)) { - /* Help track down the real cause of bug #6475: */ - if (circ->has_opened && circ->path_state != PATH_STATE_BUILD_ATTEMPTED) { - if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit, - approx_time()))) { - log_info(LD_BUG, - "Opened circuit is in strange path state %s. " - "Circuit is a %s currently %s.%s", - pathbias_state_to_string(circ->path_state), - circuit_purpose_to_string(circ->base_.purpose), - circuit_state_to_string(circ->base_.state), - rate_msg); - tor_free(rate_msg); - } - } - - /* Don't re-count cannibalized circs.. */ - if (!circ->has_opened) { - entry_guard_t *guard = NULL; - - if (circ->cpath && circ->cpath->extend_info) { - guard = entry_guard_get_by_id_digest( - circ->cpath->extend_info->identity_digest); - } else if (circ->base_.n_chan) { - guard = - entry_guard_get_by_id_digest(circ->base_.n_chan->identity_digest); - } - - if (guard) { - if (circ->path_state == PATH_STATE_NEW_CIRC) { - circ->path_state = PATH_STATE_BUILD_ATTEMPTED; - - if (entry_guard_inc_circ_attempt_count(guard) < 0) { - /* Bogus guard; we already warned. */ - return -END_CIRC_REASON_TORPROTOCOL; - } - } else { - if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit, - approx_time()))) { - log_info(LD_BUG, - "Unopened circuit has strange path state %s. " - "Circuit is a %s currently %s.%s", - pathbias_state_to_string(circ->path_state), - circuit_purpose_to_string(circ->base_.purpose), - circuit_state_to_string(circ->base_.state), - rate_msg); - tor_free(rate_msg); - } - } - } else { - if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit, - approx_time()))) { - log_info(LD_CIRC, - "Unopened circuit has no known guard. " - "Circuit is a %s currently %s.%s", - circuit_purpose_to_string(circ->base_.purpose), - circuit_state_to_string(circ->base_.state), - rate_msg); - tor_free(rate_msg); - } - } - } - } - - return 0; -} - -/** - * Check our circuit state to see if this is a successful circuit - * completion. If so, record it in the current guard's path bias - * success count. - * - * Also check for several potential error cases for bug #6475. - */ -static void -pathbias_count_build_success(origin_circuit_t *circ) -{ -#define SUCCESS_NOTICE_INTERVAL (600) - static ratelim_t success_notice_limit = - RATELIM_INIT(SUCCESS_NOTICE_INTERVAL); - char *rate_msg = NULL; - entry_guard_t *guard = NULL; - - if (!pathbias_should_count(circ)) { - return; - } - - /* Don't count cannibalized/reused circs for path bias - * "build" success, since they get counted under "use" success. */ - if (!circ->has_opened) { - if (circ->cpath && circ->cpath->extend_info) { - guard = entry_guard_get_by_id_digest( - circ->cpath->extend_info->identity_digest); - } - - if (guard) { - if (circ->path_state == PATH_STATE_BUILD_ATTEMPTED) { - circ->path_state = PATH_STATE_BUILD_SUCCEEDED; - guard->circ_successes++; - entry_guards_changed(); - - log_info(LD_CIRC, "Got success count %f/%f for guard %s ($%s)", - guard->circ_successes, guard->circ_attempts, - guard->nickname, hex_str(guard->identity, DIGEST_LEN)); - } else { - if ((rate_msg = rate_limit_log(&success_notice_limit, - approx_time()))) { - log_info(LD_BUG, - "Succeeded circuit is in strange path state %s. " - "Circuit is a %s currently %s.%s", - pathbias_state_to_string(circ->path_state), - circuit_purpose_to_string(circ->base_.purpose), - circuit_state_to_string(circ->base_.state), - rate_msg); - tor_free(rate_msg); - } - } - - if (guard->circ_attempts < guard->circ_successes) { - log_notice(LD_BUG, "Unexpectedly high successes counts (%f/%f) " - "for guard %s ($%s)", - guard->circ_successes, guard->circ_attempts, - guard->nickname, hex_str(guard->identity, DIGEST_LEN)); - } - /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to - * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here. - * No need to log that case. */ - } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) { - if ((rate_msg = rate_limit_log(&success_notice_limit, - approx_time()))) { - log_info(LD_CIRC, - "Completed circuit has no known guard. " - "Circuit is a %s currently %s.%s", - circuit_purpose_to_string(circ->base_.purpose), - circuit_state_to_string(circ->base_.state), - rate_msg); - tor_free(rate_msg); - } - } - } else { - if (circ->path_state < PATH_STATE_BUILD_SUCCEEDED) { - if ((rate_msg = rate_limit_log(&success_notice_limit, - approx_time()))) { - log_info(LD_BUG, - "Opened circuit is in strange path state %s. " - "Circuit is a %s currently %s.%s", - pathbias_state_to_string(circ->path_state), - circuit_purpose_to_string(circ->base_.purpose), - circuit_state_to_string(circ->base_.state), - rate_msg); - tor_free(rate_msg); - } - } - } -} - -/** - * Record an attempt to use a circuit. Changes the circuit's - * path state and update its guard's usage counter. - * - * Used for path bias usage accounting. - */ -void -pathbias_count_use_attempt(origin_circuit_t *circ) -{ - entry_guard_t *guard; - - if (!pathbias_should_count(circ)) { - return; - } - - if (circ->path_state < PATH_STATE_BUILD_SUCCEEDED) { - log_notice(LD_BUG, - "Used circuit is in strange path state %s. " - "Circuit is a %s currently %s.", - pathbias_state_to_string(circ->path_state), - circuit_purpose_to_string(circ->base_.purpose), - circuit_state_to_string(circ->base_.state)); - } else if (circ->path_state < PATH_STATE_USE_ATTEMPTED) { - guard = entry_guard_get_by_id_digest( - circ->cpath->extend_info->identity_digest); - if (guard) { - pathbias_measure_use_rate(guard); - pathbias_scale_use_rates(guard); - guard->use_attempts++; - entry_guards_changed(); - - log_debug(LD_CIRC, - "Marked circuit %d (%f/%f) as used for guard %s ($%s).", - circ->global_identifier, - guard->use_successes, guard->use_attempts, - guard->nickname, hex_str(guard->identity, DIGEST_LEN)); - } - - circ->path_state = PATH_STATE_USE_ATTEMPTED; - } else { - /* Harmless but educational log message */ - log_info(LD_CIRC, - "Used circuit %d is already in path state %s. " - "Circuit is a %s currently %s.", - circ->global_identifier, - pathbias_state_to_string(circ->path_state), - circuit_purpose_to_string(circ->base_.purpose), - circuit_state_to_string(circ->base_.state)); - } - - return; -} - -/** - * Check the circuit's path state is appropriate and mark it as - * successfully used. Used for path bias usage accounting. - * - * We don't actually increment the guard's counters until - * pathbias_check_close(), because the circuit can still transition - * back to PATH_STATE_USE_ATTEMPTED if a stream fails later (this - * is done so we can probe the circuit for liveness at close). - */ -void -pathbias_mark_use_success(origin_circuit_t *circ) -{ - if (!pathbias_should_count(circ)) { - return; - } - - if (circ->path_state < PATH_STATE_USE_ATTEMPTED) { - log_notice(LD_BUG, - "Used circuit %d is in strange path state %s. " - "Circuit is a %s currently %s.", - circ->global_identifier, - pathbias_state_to_string(circ->path_state), - circuit_purpose_to_string(circ->base_.purpose), - circuit_state_to_string(circ->base_.state)); - - pathbias_count_use_attempt(circ); - } - - /* We don't do any accounting at the guard until actual circuit close */ - circ->path_state = PATH_STATE_USE_SUCCEEDED; - - return; -} - -/** - * If a stream ever detatches from a circuit in a retriable way, - * we need to mark this circuit as still needing either another - * successful stream, or in need of a probe. - * - * An adversary could let the first stream request succeed (ie the - * resolve), but then tag and timeout the remainder (via cell - * dropping), forcing them on new circuits. - * - * Rolling back the state will cause us to probe such circuits, which - * should lead to probe failures in the event of such tagging due to - * either unrecognized cells coming in while we wait for the probe, - * or the cipher state getting out of sync in the case of dropped cells. - */ -void -pathbias_mark_use_rollback(origin_circuit_t *circ) -{ - if (circ->path_state == PATH_STATE_USE_SUCCEEDED) { - log_info(LD_CIRC, - "Rolling back pathbias use state to 'attempted' for detached " - "circuit %d", circ->global_identifier); - circ->path_state = PATH_STATE_USE_ATTEMPTED; - } -} - -/** - * Actually count a circuit success towards a guard's usage counters - * if the path state is appropriate. - */ -static void -pathbias_count_use_success(origin_circuit_t *circ) -{ - entry_guard_t *guard; - - if (!pathbias_should_count(circ)) { - return; - } - - if (circ->path_state != PATH_STATE_USE_SUCCEEDED) { - log_notice(LD_BUG, - "Successfully used circuit %d is in strange path state %s. " - "Circuit is a %s currently %s.", - circ->global_identifier, - pathbias_state_to_string(circ->path_state), - circuit_purpose_to_string(circ->base_.purpose), - circuit_state_to_string(circ->base_.state)); - } else { - guard = entry_guard_get_by_id_digest( - circ->cpath->extend_info->identity_digest); - if (guard) { - guard->use_successes++; - entry_guards_changed(); - - if (guard->use_attempts < guard->use_successes) { - log_notice(LD_BUG, "Unexpectedly high use successes counts (%f/%f) " - "for guard %s=%s", - guard->use_successes, guard->use_attempts, - guard->nickname, hex_str(guard->identity, DIGEST_LEN)); - } - - log_debug(LD_CIRC, - "Marked circuit %d (%f/%f) as used successfully for guard " - "%s ($%s).", - circ->global_identifier, guard->use_successes, - guard->use_attempts, guard->nickname, - hex_str(guard->identity, DIGEST_LEN)); - } - } - - return; -} - -/** - * Send a probe down a circuit that the client attempted to use, - * but for which the stream timed out/failed. The probe is a - * RELAY_BEGIN cell with a 0.a.b.c destination address, which - * the exit will reject and reply back, echoing that address. - * - * The reason for such probes is because it is possible to bias - * a user's paths simply by causing timeouts, and these timeouts - * are not possible to differentiate from unresponsive servers. - * - * The probe is sent at the end of the circuit lifetime for two - * reasons: to prevent cryptographic taggers from being able to - * drop cells to cause timeouts, and to prevent easy recognition - * of probes before any real client traffic happens. - * - * Returns -1 if we couldn't probe, 0 otherwise. - */ -static int -pathbias_send_usable_probe(circuit_t *circ) -{ - /* Based on connection_ap_handshake_send_begin() */ - char payload[CELL_PAYLOAD_SIZE]; - int payload_len; - origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ); - crypt_path_t *cpath_layer = NULL; - char *probe_nonce = NULL; - - tor_assert(ocirc); - - cpath_layer = ocirc->cpath->prev; - - if (cpath_layer->state != CPATH_STATE_OPEN) { - /* This can happen for cannibalized circuits. Their - * last hop isn't yet open */ - log_info(LD_CIRC, - "Got pathbias probe request for unopened circuit %d. " - "Opened %d, len %d", ocirc->global_identifier, - ocirc->has_opened, ocirc->build_state->desired_path_len); - return -1; - } - - /* We already went down this road. */ - if (circ->purpose == CIRCUIT_PURPOSE_PATH_BIAS_TESTING && - ocirc->pathbias_probe_id) { - log_info(LD_CIRC, - "Got pathbias probe request for circuit %d with " - "outstanding probe", ocirc->global_identifier); - return -1; - } - - /* Can't probe if the channel isn't open */ - if (circ->n_chan == NULL || - (circ->n_chan->state != CHANNEL_STATE_OPEN - && circ->n_chan->state != CHANNEL_STATE_MAINT)) { - log_info(LD_CIRC, - "Skipping pathbias probe for circuit %d: Channel is not open.", - ocirc->global_identifier); - return -1; - } - - circuit_change_purpose(circ, CIRCUIT_PURPOSE_PATH_BIAS_TESTING); - - /* Update timestamp for when circuit_expire_building() should kill us */ - tor_gettimeofday(&circ->timestamp_began); - - /* Generate a random address for the nonce */ - crypto_rand((char*)ô->pathbias_probe_nonce, - sizeof(ocirc->pathbias_probe_nonce)); - ocirc->pathbias_probe_nonce &= 0x00ffffff; - probe_nonce = tor_dup_ip(ocirc->pathbias_probe_nonce); - - tor_snprintf(payload,RELAY_PAYLOAD_SIZE, "%s:25", probe_nonce); - payload_len = (int)strlen(payload)+1; - - // XXX: need this? Can we assume ipv4 will always be supported? - // If not, how do we tell? - //if (payload_len <= RELAY_PAYLOAD_SIZE - 4 && edge_conn->begincell_flags) { - // set_uint32(payload + payload_len, htonl(edge_conn->begincell_flags)); - // payload_len += 4; - //} - - /* Generate+Store stream id, make sure it's non-zero */ - ocirc->pathbias_probe_id = get_unique_stream_id_by_circ(ocirc); - - if (ocirc->pathbias_probe_id==0) { - log_warn(LD_CIRC, - "Ran out of stream IDs on circuit %u during " - "pathbias probe attempt.", ocirc->global_identifier); - tor_free(probe_nonce); - return -1; - } - - log_info(LD_CIRC, - "Sending pathbias testing cell to %s:25 on stream %d for circ %d.", - probe_nonce, ocirc->pathbias_probe_id, ocirc->global_identifier); - tor_free(probe_nonce); - - /* Send a test relay cell */ - if (relay_send_command_from_edge(ocirc->pathbias_probe_id, circ, - RELAY_COMMAND_BEGIN, payload, - payload_len, cpath_layer) < 0) { - log_notice(LD_CIRC, - "Failed to send pathbias probe cell on circuit %d.", - ocirc->global_identifier); - return -1; - } - - /* Mark it freshly dirty so it doesn't get expired in the meantime */ - circ->timestamp_dirty = time(NULL); - - return 0; -} - -/** - * Check the response to a pathbias probe, to ensure the - * cell is recognized and the nonce and other probe - * characteristics are as expected. - * - * If the response is valid, return 0. Otherwise return < 0. - */ -int -pathbias_check_probe_response(circuit_t *circ, const cell_t *cell) -{ - /* Based on connection_edge_process_relay_cell() */ - relay_header_t rh; - int reason; - uint32_t ipv4_host; - origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ); - - tor_assert(cell); - tor_assert(ocirc); - tor_assert(circ->purpose == CIRCUIT_PURPOSE_PATH_BIAS_TESTING); - - relay_header_unpack(&rh, cell->payload); - - reason = rh.length > 0 ? - get_uint8(cell->payload+RELAY_HEADER_SIZE) : END_STREAM_REASON_MISC; - - if (rh.command == RELAY_COMMAND_END && - reason == END_STREAM_REASON_EXITPOLICY && - ocirc->pathbias_probe_id == rh.stream_id) { - - /* Check length+extract host: It is in network order after the reason code. - * See connection_edge_end(). */ - if (rh.length < 9) { /* reason+ipv4+dns_ttl */ - log_notice(LD_PROTOCOL, - "Short path bias probe response length field (%d).", rh.length); - return - END_CIRC_REASON_TORPROTOCOL; - } - - ipv4_host = ntohl(get_uint32(cell->payload+RELAY_HEADER_SIZE+1)); - - /* Check nonce */ - if (ipv4_host == ocirc->pathbias_probe_nonce) { - pathbias_mark_use_success(ocirc); - circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED); - log_info(LD_CIRC, - "Got valid path bias probe back for circ %d, stream %d.", - ocirc->global_identifier, ocirc->pathbias_probe_id); - return 0; - } else { - log_notice(LD_CIRC, - "Got strange probe value 0x%x vs 0x%x back for circ %d, " - "stream %d.", ipv4_host, ocirc->pathbias_probe_nonce, - ocirc->global_identifier, ocirc->pathbias_probe_id); - return -1; - } - } - log_info(LD_CIRC, - "Got another cell back back on pathbias probe circuit %d: " - "Command: %d, Reason: %d, Stream-id: %d", - ocirc->global_identifier, rh.command, reason, rh.stream_id); - return -1; -} - -/** - * Check if a circuit was used and/or closed successfully. - * - * If we attempted to use the circuit to carry a stream but failed - * for whatever reason, or if the circuit mysteriously died before - * we could attach any streams, record these two cases. - * - * If we *have* successfully used the circuit, or it appears to - * have been closed by us locally, count it as a success. - * - * Returns 0 if we're done making decisions with the circ, - * or -1 if we want to probe it first. - */ -int -pathbias_check_close(origin_circuit_t *ocirc, int reason) -{ - circuit_t *circ = ô->base_; - - if (!pathbias_should_count(ocirc)) { - return 0; - } - - switch (ocirc->path_state) { - /* If the circuit was closed after building, but before use, we need - * to ensure we were the ones who tried to close it (and not a remote - * actor). */ - case PATH_STATE_BUILD_SUCCEEDED: - if (reason & END_CIRC_REASON_FLAG_REMOTE) { - /* Remote circ close reasons on an unused circuit all could be bias */ - log_info(LD_CIRC, - "Circuit %d remote-closed without successful use for reason %d. " - "Circuit purpose %d currently %d,%s. Len %d.", - ocirc->global_identifier, - reason, circ->purpose, ocirc->has_opened, - circuit_state_to_string(circ->state), - ocirc->build_state->desired_path_len); - pathbias_count_collapse(ocirc); - } else if ((reason & ~END_CIRC_REASON_FLAG_REMOTE) - == END_CIRC_REASON_CHANNEL_CLOSED && - circ->n_chan && - circ->n_chan->reason_for_closing - != CHANNEL_CLOSE_REQUESTED) { - /* If we didn't close the channel ourselves, it could be bias */ - /* XXX: Only count bias if the network is live? - * What about clock jumps/suspends? */ - log_info(LD_CIRC, - "Circuit %d's channel closed without successful use for reason " - "%d, channel reason %d. Circuit purpose %d currently %d,%s. Len " - "%d.", ocirc->global_identifier, - reason, circ->n_chan->reason_for_closing, - circ->purpose, ocirc->has_opened, - circuit_state_to_string(circ->state), - ocirc->build_state->desired_path_len); - pathbias_count_collapse(ocirc); - } else { - pathbias_count_successful_close(ocirc); - } - break; - - /* If we tried to use a circuit but failed, we should probe it to ensure - * it has not been tampered with. */ - case PATH_STATE_USE_ATTEMPTED: - /* XXX: Only probe and/or count failure if the network is live? - * What about clock jumps/suspends? */ - if (pathbias_send_usable_probe(circ) == 0) - return -1; - else - pathbias_count_use_failed(ocirc); - - /* Any circuit where there were attempted streams but no successful - * streams could be bias */ - log_info(LD_CIRC, - "Circuit %d closed without successful use for reason %d. " - "Circuit purpose %d currently %d,%s. Len %d.", - ocirc->global_identifier, - reason, circ->purpose, ocirc->has_opened, - circuit_state_to_string(circ->state), - ocirc->build_state->desired_path_len); - break; - - case PATH_STATE_USE_SUCCEEDED: - pathbias_count_successful_close(ocirc); - pathbias_count_use_success(ocirc); - break; - - case PATH_STATE_USE_FAILED: - pathbias_count_use_failed(ocirc); - break; - - case PATH_STATE_NEW_CIRC: - case PATH_STATE_BUILD_ATTEMPTED: - case PATH_STATE_ALREADY_COUNTED: - default: - // Other states are uninteresting. No stats to count. - break; - } - - ocirc->path_state = PATH_STATE_ALREADY_COUNTED; - - return 0; -} - -/** - * Count a successfully closed circuit. - */ -static void -pathbias_count_successful_close(origin_circuit_t *circ) -{ - entry_guard_t *guard = NULL; - if (!pathbias_should_count(circ)) { - return; - } - - if (circ->cpath && circ->cpath->extend_info) { - guard = entry_guard_get_by_id_digest( - circ->cpath->extend_info->identity_digest); - } - - if (guard) { - /* In the long run: circuit_success ~= successful_circuit_close + - * circ_failure + stream_failure */ - guard->successful_circuits_closed++; - entry_guards_changed(); - } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) { - /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to - * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here. - * No need to log that case. */ - log_info(LD_CIRC, - "Successfully closed circuit has no known guard. " - "Circuit is a %s currently %s", - circuit_purpose_to_string(circ->base_.purpose), - circuit_state_to_string(circ->base_.state)); - } -} - -/** - * Count a circuit that fails after it is built, but before it can - * carry any traffic. - * - * This is needed because there are ways to destroy a - * circuit after it has successfully completed. Right now, this is - * used for purely informational/debugging purposes. - */ -static void -pathbias_count_collapse(origin_circuit_t *circ) -{ - entry_guard_t *guard = NULL; - - if (!pathbias_should_count(circ)) { - return; - } - - if (circ->cpath && circ->cpath->extend_info) { - guard = entry_guard_get_by_id_digest( - circ->cpath->extend_info->identity_digest); - } - - if (guard) { - guard->collapsed_circuits++; - entry_guards_changed(); - } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) { - /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to - * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here. - * No need to log that case. */ - log_info(LD_CIRC, - "Destroyed circuit has no known guard. " - "Circuit is a %s currently %s", - circuit_purpose_to_string(circ->base_.purpose), - circuit_state_to_string(circ->base_.state)); - } -} - -/** - * Count a known failed circuit (because we could not probe it). - * - * This counter is informational. - */ -static void -pathbias_count_use_failed(origin_circuit_t *circ) -{ - entry_guard_t *guard = NULL; - if (!pathbias_should_count(circ)) { - return; - } - - if (circ->cpath && circ->cpath->extend_info) { - guard = entry_guard_get_by_id_digest( - circ->cpath->extend_info->identity_digest); - } - - if (guard) { - guard->unusable_circuits++; - entry_guards_changed(); - } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) { - /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to - * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here. - * No need to log that case. */ - /* XXX note cut-and-paste code in this function compared to nearby - * functions. Would be nice to refactor. -RD */ - log_info(LD_CIRC, - "Stream-failing circuit has no known guard. " - "Circuit is a %s currently %s", - circuit_purpose_to_string(circ->base_.purpose), - circuit_state_to_string(circ->base_.state)); - } -} - -/** - * Count timeouts for path bias log messages. - * - * These counts are purely informational. - */ -void -pathbias_count_timeout(origin_circuit_t *circ) -{ - entry_guard_t *guard = NULL; - - if (!pathbias_should_count(circ)) { - return; - } - - /* For hidden service circs, they can actually be used - * successfully and then time out later (because - * the other side declines to use them). */ - if (circ->path_state == PATH_STATE_USE_SUCCEEDED) { - return; - } - - if (circ->cpath && circ->cpath->extend_info) { - guard = entry_guard_get_by_id_digest( - circ->cpath->extend_info->identity_digest); - } - - if (guard) { - guard->timeouts++; - entry_guards_changed(); - } -} - -/** - * Helper function to count all of the currently opened circuits - * for a guard that are in a given path state range. The state - * range is inclusive on both ends. - */ -static int -pathbias_count_circs_in_states(entry_guard_t *guard, - path_state_t from, - path_state_t to) -{ - circuit_t *circ; - int open_circuits = 0; - - /* Count currently open circuits. Give them the benefit of the doubt. */ - for (circ = global_circuitlist; circ; circ = circ->next) { - origin_circuit_t *ocirc = NULL; - if (!CIRCUIT_IS_ORIGIN(circ) || /* didn't originate here */ - circ->marked_for_close) /* already counted */ - continue; - - ocirc = TO_ORIGIN_CIRCUIT(circ); - - if (!ocirc->cpath || !ocirc->cpath->extend_info) - continue; - - if (ocirc->path_state >= from && - ocirc->path_state <= to && - pathbias_should_count(ocirc) && - fast_memeq(guard->identity, - ocirc->cpath->extend_info->identity_digest, - DIGEST_LEN)) { - log_debug(LD_CIRC, "Found opened circuit %d in path_state %s", - ocirc->global_identifier, - pathbias_state_to_string(ocirc->path_state)); - open_circuits++; - } - } - - return open_circuits; -} - -/** - * Return the number of circuits counted as successfully closed for - * this guard. - * - * Also add in the currently open circuits to give them the benefit - * of the doubt. - */ -double -pathbias_get_close_success_count(entry_guard_t *guard) -{ - return guard->successful_circuits_closed + - pathbias_count_circs_in_states(guard, - PATH_STATE_BUILD_SUCCEEDED, - PATH_STATE_USE_SUCCEEDED); -} - -/** - * Return the number of circuits counted as successfully used - * this guard. - * - * Also add in the currently open circuits that we are attempting - * to use to give them the benefit of the doubt. - */ -double -pathbias_get_use_success_count(entry_guard_t *guard) -{ - return guard->use_successes + - pathbias_count_circs_in_states(guard, - PATH_STATE_USE_ATTEMPTED, - PATH_STATE_USE_SUCCEEDED); -} - -/** - * Check the path bias use rate against our consensus parameter limits. - * - * Emits a log message if the use success rates are too low. - * - * If pathbias_get_dropguards() is set, we also disable the use of - * very failure prone guards. - */ -static void -pathbias_measure_use_rate(entry_guard_t *guard) -{ - const or_options_t *options = get_options(); - - if (guard->use_attempts > pathbias_get_min_use(options)) { - /* Note: We rely on the < comparison here to allow us to set a 0 - * rate and disable the feature entirely. If refactoring, don't - * change to <= */ - if (pathbias_get_use_success_count(guard)/guard->use_attempts - < pathbias_get_extreme_use_rate(options)) { - /* Dropping is currently disabled by default. */ - if (pathbias_get_dropguards(options)) { - if (!guard->path_bias_disabled) { - log_warn(LD_CIRC, - "Your Guard %s ($%s) is failing to carry an extremely large " - "amount of stream on its circuits. " - "To avoid potential route manipulation attacks, Tor has " - "disabled use of this guard. " - "Use counts are %ld/%ld. Success counts are %ld/%ld. " - "%ld circuits completed, %ld were unusable, %ld collapsed, " - "and %ld timed out. " - "For reference, your timeout cutoff is %ld seconds.", - guard->nickname, hex_str(guard->identity, DIGEST_LEN), - tor_lround(pathbias_get_use_success_count(guard)), - tor_lround(guard->use_attempts), - tor_lround(pathbias_get_close_success_count(guard)), - tor_lround(guard->circ_attempts), - tor_lround(guard->circ_successes), - tor_lround(guard->unusable_circuits), - tor_lround(guard->collapsed_circuits), - tor_lround(guard->timeouts), - tor_lround(circ_times.close_ms/1000)); - guard->path_bias_disabled = 1; - guard->bad_since = approx_time(); - entry_guards_changed(); - return; - } - } else if (!guard->path_bias_use_extreme) { - guard->path_bias_use_extreme = 1; - log_warn(LD_CIRC, - "Your Guard %s ($%s) is failing to carry an extremely large " - "amount of streams on its circuits. " - "This could indicate a route manipulation attack, network " - "overload, bad local network connectivity, or a bug. " - "Use counts are %ld/%ld. Success counts are %ld/%ld. " - "%ld circuits completed, %ld were unusable, %ld collapsed, " - "and %ld timed out. " - "For reference, your timeout cutoff is %ld seconds.", - guard->nickname, hex_str(guard->identity, DIGEST_LEN), - tor_lround(pathbias_get_use_success_count(guard)), - tor_lround(guard->use_attempts), - tor_lround(pathbias_get_close_success_count(guard)), - tor_lround(guard->circ_attempts), - tor_lround(guard->circ_successes), - tor_lround(guard->unusable_circuits), - tor_lround(guard->collapsed_circuits), - tor_lround(guard->timeouts), - tor_lround(circ_times.close_ms/1000)); - } - } else if (pathbias_get_use_success_count(guard)/guard->use_attempts - < pathbias_get_notice_use_rate(options)) { - if (!guard->path_bias_use_noticed) { - guard->path_bias_use_noticed = 1; - log_notice(LD_CIRC, - "Your Guard %s ($%s) is failing to carry more streams on its " - "circuits than usual. " - "Most likely this means the Tor network is overloaded " - "or your network connection is poor. " - "Use counts are %ld/%ld. Success counts are %ld/%ld. " - "%ld circuits completed, %ld were unusable, %ld collapsed, " - "and %ld timed out. " - "For reference, your timeout cutoff is %ld seconds.", - guard->nickname, hex_str(guard->identity, DIGEST_LEN), - tor_lround(pathbias_get_use_success_count(guard)), - tor_lround(guard->use_attempts), - tor_lround(pathbias_get_close_success_count(guard)), - tor_lround(guard->circ_attempts), - tor_lround(guard->circ_successes), - tor_lround(guard->unusable_circuits), - tor_lround(guard->collapsed_circuits), - tor_lround(guard->timeouts), - tor_lround(circ_times.close_ms/1000)); - } - } - } -} - -/** - * Check the path bias circuit close status rates against our consensus - * parameter limits. - * - * Emits a log message if the use success rates are too low. - * - * If pathbias_get_dropguards() is set, we also disable the use of - * very failure prone guards. - * - * XXX: This function shares similar log messages and checks to - * pathbias_measure_use_rate(). It may be possible to combine them - * eventually, especially if we can ever remove the need for 3 - * levels of closure warns (if the overall circuit failure rate - * goes down with ntor). One way to do so would be to multiply - * the build rate with the use rate to get an idea of the total - * fraction of the total network paths the user is able to use. - * See ticket #8159. - */ -static void -pathbias_measure_close_rate(entry_guard_t *guard) -{ - const or_options_t *options = get_options(); - - if (guard->circ_attempts > pathbias_get_min_circs(options)) { - /* Note: We rely on the < comparison here to allow us to set a 0 - * rate and disable the feature entirely. If refactoring, don't - * change to <= */ - if (pathbias_get_close_success_count(guard)/guard->circ_attempts - < pathbias_get_extreme_rate(options)) { - /* Dropping is currently disabled by default. */ - if (pathbias_get_dropguards(options)) { - if (!guard->path_bias_disabled) { - log_warn(LD_CIRC, - "Your Guard %s ($%s) is failing an extremely large " - "amount of circuits. " - "To avoid potential route manipulation attacks, Tor has " - "disabled use of this guard. " - "Success counts are %ld/%ld. Use counts are %ld/%ld. " - "%ld circuits completed, %ld were unusable, %ld collapsed, " - "and %ld timed out. " - "For reference, your timeout cutoff is %ld seconds.", - guard->nickname, hex_str(guard->identity, DIGEST_LEN), - tor_lround(pathbias_get_close_success_count(guard)), - tor_lround(guard->circ_attempts), - tor_lround(pathbias_get_use_success_count(guard)), - tor_lround(guard->use_attempts), - tor_lround(guard->circ_successes), - tor_lround(guard->unusable_circuits), - tor_lround(guard->collapsed_circuits), - tor_lround(guard->timeouts), - tor_lround(circ_times.close_ms/1000)); - guard->path_bias_disabled = 1; - guard->bad_since = approx_time(); - entry_guards_changed(); - return; - } - } else if (!guard->path_bias_extreme) { - guard->path_bias_extreme = 1; - log_warn(LD_CIRC, - "Your Guard %s ($%s) is failing an extremely large " - "amount of circuits. " - "This could indicate a route manipulation attack, " - "extreme network overload, or a bug. " - "Success counts are %ld/%ld. Use counts are %ld/%ld. " - "%ld circuits completed, %ld were unusable, %ld collapsed, " - "and %ld timed out. " - "For reference, your timeout cutoff is %ld seconds.", - guard->nickname, hex_str(guard->identity, DIGEST_LEN), - tor_lround(pathbias_get_close_success_count(guard)), - tor_lround(guard->circ_attempts), - tor_lround(pathbias_get_use_success_count(guard)), - tor_lround(guard->use_attempts), - tor_lround(guard->circ_successes), - tor_lround(guard->unusable_circuits), - tor_lround(guard->collapsed_circuits), - tor_lround(guard->timeouts), - tor_lround(circ_times.close_ms/1000)); - } - } else if (pathbias_get_close_success_count(guard)/guard->circ_attempts - < pathbias_get_warn_rate(options)) { - if (!guard->path_bias_warned) { - guard->path_bias_warned = 1; - log_warn(LD_CIRC, - "Your Guard %s ($%s) is failing a very large " - "amount of circuits. " - "Most likely this means the Tor network is " - "overloaded, but it could also mean an attack against " - "you or potentially the guard itself. " - "Success counts are %ld/%ld. Use counts are %ld/%ld. " - "%ld circuits completed, %ld were unusable, %ld collapsed, " - "and %ld timed out. " - "For reference, your timeout cutoff is %ld seconds.", - guard->nickname, hex_str(guard->identity, DIGEST_LEN), - tor_lround(pathbias_get_close_success_count(guard)), - tor_lround(guard->circ_attempts), - tor_lround(pathbias_get_use_success_count(guard)), - tor_lround(guard->use_attempts), - tor_lround(guard->circ_successes), - tor_lround(guard->unusable_circuits), - tor_lround(guard->collapsed_circuits), - tor_lround(guard->timeouts), - tor_lround(circ_times.close_ms/1000)); - } - } else if (pathbias_get_close_success_count(guard)/guard->circ_attempts - < pathbias_get_notice_rate(options)) { - if (!guard->path_bias_noticed) { - guard->path_bias_noticed = 1; - log_notice(LD_CIRC, - "Your Guard %s ($%s) is failing more circuits than " - "usual. " - "Most likely this means the Tor network is overloaded. " - "Success counts are %ld/%ld. Use counts are %ld/%ld. " - "%ld circuits completed, %ld were unusable, %ld collapsed, " - "and %ld timed out. " - "For reference, your timeout cutoff is %ld seconds.", - guard->nickname, hex_str(guard->identity, DIGEST_LEN), - tor_lround(pathbias_get_close_success_count(guard)), - tor_lround(guard->circ_attempts), - tor_lround(pathbias_get_use_success_count(guard)), - tor_lround(guard->use_attempts), - tor_lround(guard->circ_successes), - tor_lround(guard->unusable_circuits), - tor_lround(guard->collapsed_circuits), - tor_lround(guard->timeouts), - tor_lround(circ_times.close_ms/1000)); - } - } - } -} - -/** - * This function scales the path bias use rates if we have - * more data than the scaling threshold. This allows us to - * be more sensitive to recent measurements. - * - * XXX: The attempt count transfer stuff here might be done - * better by keeping separate pending counters that get - * transfered at circuit close. See ticket #8160. - */ -static void -pathbias_scale_close_rates(entry_guard_t *guard) -{ - const or_options_t *options = get_options(); - - /* If we get a ton of circuits, just scale everything down */ - if (guard->circ_attempts > pathbias_get_scale_threshold(options)) { - double scale_ratio = pathbias_get_scale_ratio(options); - int opened_attempts = pathbias_count_circs_in_states(guard, - PATH_STATE_BUILD_ATTEMPTED, PATH_STATE_BUILD_ATTEMPTED); - int opened_built = pathbias_count_circs_in_states(guard, - PATH_STATE_BUILD_SUCCEEDED, - PATH_STATE_USE_FAILED); - /* Verify that the counts are sane before and after scaling */ - int counts_are_sane = (guard->circ_attempts >= guard->circ_successes); - - guard->circ_attempts -= (opened_attempts+opened_built); - guard->circ_successes -= opened_built; - - guard->circ_attempts *= scale_ratio; - guard->circ_successes *= scale_ratio; - guard->timeouts *= scale_ratio; - guard->successful_circuits_closed *= scale_ratio; - guard->collapsed_circuits *= scale_ratio; - guard->unusable_circuits *= scale_ratio; - - guard->circ_attempts += (opened_attempts+opened_built); - guard->circ_successes += opened_built; - - entry_guards_changed(); - - log_info(LD_CIRC, - "Scaled pathbias counts to (%f,%f)/%f (%d/%d open) for guard " - "%s ($%s)", - guard->circ_successes, guard->successful_circuits_closed, - guard->circ_attempts, opened_built, opened_attempts, - guard->nickname, hex_str(guard->identity, DIGEST_LEN)); - - /* Have the counts just become invalid by this scaling attempt? */ - if (counts_are_sane && guard->circ_attempts < guard->circ_successes) { - log_notice(LD_BUG, - "Scaling has mangled pathbias counts to %f/%f (%d/%d open) " - "for guard %s ($%s)", - guard->circ_successes, guard->circ_attempts, opened_built, - opened_attempts, guard->nickname, - hex_str(guard->identity, DIGEST_LEN)); - } - } -} - -/** - * This function scales the path bias circuit close rates if we have - * more data than the scaling threshold. This allows us to be more - * sensitive to recent measurements. - * - * XXX: The attempt count transfer stuff here might be done - * better by keeping separate pending counters that get - * transfered at circuit close. See ticket #8160. - */ -void -pathbias_scale_use_rates(entry_guard_t *guard) -{ - const or_options_t *options = get_options(); - - /* If we get a ton of circuits, just scale everything down */ - if (guard->use_attempts > pathbias_get_scale_use_threshold(options)) { - double scale_ratio = pathbias_get_scale_ratio(options); - int opened_attempts = pathbias_count_circs_in_states(guard, - PATH_STATE_USE_ATTEMPTED, PATH_STATE_USE_SUCCEEDED); - /* Verify that the counts are sane before and after scaling */ - int counts_are_sane = (guard->use_attempts >= guard->use_successes); - - guard->use_attempts -= opened_attempts; - - guard->use_attempts *= scale_ratio; - guard->use_successes *= scale_ratio; - - guard->use_attempts += opened_attempts; - - log_info(LD_CIRC, - "Scaled pathbias use counts to %f/%f (%d open) for guard %s ($%s)", - guard->use_successes, guard->use_attempts, opened_attempts, - guard->nickname, hex_str(guard->identity, DIGEST_LEN)); - - /* Have the counts just become invalid by this scaling attempt? */ - if (counts_are_sane && guard->use_attempts < guard->use_successes) { - log_notice(LD_BUG, - "Scaling has mangled pathbias usage counts to %f/%f " - "(%d open) for guard %s ($%s)", - guard->circ_successes, guard->circ_attempts, - opened_attempts, guard->nickname, - hex_str(guard->identity, DIGEST_LEN)); - } - - entry_guards_changed(); - } -} - -/** Increment the number of times we successfully extended a circuit to - * <b>guard</b>, first checking if the failure rate is high enough that - * we should eliminate the guard. Return -1 if the guard looks no good; - * return 0 if the guard looks fine. - */ -static int -entry_guard_inc_circ_attempt_count(entry_guard_t *guard) -{ - entry_guards_changed(); - - pathbias_measure_close_rate(guard); - - if (guard->path_bias_disabled) - return -1; - - pathbias_scale_close_rates(guard); - guard->circ_attempts++; - - log_info(LD_CIRC, "Got success count %f/%f for guard %s ($%s)", - guard->circ_successes, guard->circ_attempts, guard->nickname, - hex_str(guard->identity, DIGEST_LEN)); - return 0; -} - /** A "created" cell <b>reply</b> came back to us on circuit <b>circ</b>. * (The body of <b>reply</b> varies depending on what sort of handshake * this is.) @@ -2830,11 +1407,7 @@ onionskin_answer(or_circuit_t *circ, * number of endpoints that would give something away about our destination. * * If the routerlist <b>nodes</b> doesn't have enough routers - * to handle the desired path length, return as large a path length as - * is feasible, except if it's less than 2, in which case return -1. - * XXX ^^ I think this behavior is a hold-over from back when we had only a - * few relays in the network, and certainly back before guards existed. - * We should very likely get rid of it. -RD + * to handle the desired path length, return -1. */ static int new_route_len(uint8_t purpose, extend_info_t *exit, smartlist_t *nodes) @@ -2855,19 +1428,13 @@ new_route_len(uint8_t purpose, extend_info_t *exit, smartlist_t *nodes) log_debug(LD_CIRC,"Chosen route length %d (%d/%d routers suitable).", routelen, num_acceptable_routers, smartlist_len(nodes)); - if (num_acceptable_routers < 2) { + if (num_acceptable_routers < routelen) { log_info(LD_CIRC, - "Not enough acceptable routers (%d). Discarding this circuit.", - num_acceptable_routers); + "Not enough acceptable routers (%d/%d). Discarding this circuit.", + num_acceptable_routers, routelen); return -1; } - if (num_acceptable_routers < routelen) { - log_info(LD_CIRC,"Not enough routers: cutting routelen from %d to %d.", - routelen, num_acceptable_routers); - routelen = num_acceptable_routers; - } - return routelen; } |