diff options
Diffstat (limited to 'src/or/circuitbuild.c')
| -rw-r--r-- | src/or/circuitbuild.c | 720 |
1 files changed, 578 insertions, 142 deletions
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index 73018740c2..804782df33 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -59,8 +59,11 @@ 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_first_hop_count(entry_guard_t *guard); -static void pathbias_count_success(origin_circuit_t *circ); +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_unusable(origin_circuit_t *circ); /** This function tries to get a channel to the specified endpoint, * and then calls command_setup_channel() to give it the right @@ -731,13 +734,17 @@ circuit_send_next_onion_skin(origin_circuit_t *circ) } } - pathbias_count_success(circ); + pathbias_count_build_success(circ); circuit_rep_hist_note_result(circ); circuit_has_opened(circ); /* do other actions as necessary */ /* We're done with measurement circuits here. Just close them */ - if (circ->base_.purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) + if (circ->base_.purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) { + /* If a measurement circ ever gets back to us, consider it + * succeeded for path bias */ + circ->path_state = PATH_STATE_USE_SUCCEEDED; circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_FINISHED); + } return 0; } @@ -980,12 +987,12 @@ circuit_init_cpath_crypto(crypt_path_t *cpath, const char *key_data, return 0; } -/** The minimum number of first hop completions before we start +/** 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 20 +#define DFLT_PATH_BIAS_MIN_CIRC 150 if (options->PathBiasCircThreshold >= 5) return options->PathBiasCircThreshold; else @@ -994,10 +1001,11 @@ pathbias_get_min_circs(const or_options_t *options) 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 40 +#define DFLT_PATH_BIAS_NOTICE_PCT 70 if (options->PathBiasNoticeRate >= 0.0) return options->PathBiasNoticeRate; else @@ -1006,23 +1014,61 @@ pathbias_get_notice_rate(const or_options_t *options) } /* 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_disable_rate(const or_options_t *options) +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) { -// XXX: This needs tuning based on use + experimentation before we set it -#define DFLT_PATH_BIAS_DISABLE_PCT 0 - if (options->PathBiasDisableRate >= 0.0) - return options->PathBiasDisableRate; +#define DFLT_PATH_BIAS_DROP_GUARDS 0 + if (options->PathBiasDropGuards >= 0) + return options->PathBiasDropGuards; else - return networkstatus_get_param(NULL, "pb_disablepct", - DFLT_PATH_BIAS_DISABLE_PCT, 0, 100)/100.0; + 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 200 - if (options->PathBiasScaleThreshold >= 2) +#define DFLT_PATH_BIAS_SCALE_THRESHOLD 300 + if (options->PathBiasScaleThreshold >= 10) return options->PathBiasScaleThreshold; else return networkstatus_get_param(NULL, "pb_scalecircs", @@ -1030,6 +1076,13 @@ pathbias_get_scale_threshold(const or_options_t *options) INT32_MAX); } +/** + * 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. + */ static int pathbias_get_scale_factor(const or_options_t *options) { @@ -1041,40 +1094,116 @@ pathbias_get_scale_factor(const or_options_t *options) DFLT_PATH_BIAS_SCALE_FACTOR, 1, INT32_MAX); } +/** + * The mult factor is the numerator for our scaling + * of circuit counts for our path bias window. It + * allows us to scale by fractions. + */ +static int +pathbias_get_mult_factor(const or_options_t *options) +{ +#define DFLT_PATH_BIAS_MULT_FACTOR 1 + if (options->PathBiasMultFactor >= 1) + return options->PathBiasMultFactor; + else + return networkstatus_get_param(NULL, "pb_multfactor", + DFLT_PATH_BIAS_MULT_FACTOR, 1, + pathbias_get_scale_factor(options)); +} + +/** + * If this parameter is set to a true value (default), we use the + * successful_circuits_closed. Otherwise, we use the success_count. + */ +static int +pathbias_use_close_counts(const or_options_t *options) +{ +#define DFLT_PATH_BIAS_USE_CLOSE_COUNTS 1 + if (options->PathBiasUseCloseCounts >= 0) + return options->PathBiasUseCloseCounts; + else + return networkstatus_get_param(NULL, "pb_useclosecounts", + DFLT_PATH_BIAS_USE_CLOSE_COUNTS, 0, 1); +} + +/** + * Convert a Guard's path state to string. + */ static const char * pathbias_state_to_string(path_state_t state) { switch (state) { case PATH_STATE_NEW_CIRC: return "new"; - case PATH_STATE_DID_FIRST_HOP: - return "first hop"; - case PATH_STATE_SUCCEEDED: - return "succeeded"; + case PATH_STATE_BUILD_ATTEMPTED: + return "build attempted"; + case PATH_STATE_BUILD_SUCCEEDED: + return "build succeeded"; + case PATH_STATE_USE_SUCCEEDED: + return "use succeeded"; + case PATH_STATE_USE_FAILED: + return "use failed"; } return "unknown"; } /** - * Check our circuit state to see if this is a successful first hop. - * If so, record it in the current guard's path bias first_hop count. + * 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->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->state == CPATH_STATE_AWAITING_KEYS; +#endif +} + +/** + * Decide if the path bias code should count a circuit. * - * Also check for several potential error cases for bug #6475. + * @returns 1 if we should count it, 0 otherwise. */ static int -pathbias_count_first_hop(origin_circuit_t *circ) +pathbias_should_count(origin_circuit_t *circ) { -#define FIRST_HOP_NOTICE_INTERVAL (600) - static ratelim_t first_hop_notice_limit = - RATELIM_INIT(FIRST_HOP_NOTICE_INTERVAL); +#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. */ + * 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_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)) { return 0; } @@ -1084,8 +1213,7 @@ pathbias_count_first_hop(origin_circuit_t *circ) /* Check for inconsistency */ if (circ->build_state->desired_path_len != 1 || !circ->build_state->onehop_tunnel) { - if ((rate_msg = rate_limit_log(&first_hop_notice_limit, - approx_time()))) { + if ((rate_msg = rate_limit_log(&count_limit, approx_time()))) { log_notice(LD_BUG, "One-hop circuit has length %d. Path state is %s. " "Circuit is a %s currently %s.%s", @@ -1101,10 +1229,31 @@ pathbias_count_first_hop(origin_circuit_t *circ) return 0; } - if (circ->cpath->state == CPATH_STATE_AWAITING_KEYS) { + 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_circ_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_DID_FIRST_HOP) { - if ((rate_msg = rate_limit_log(&first_hop_notice_limit, + 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. " @@ -1117,22 +1266,28 @@ pathbias_count_first_hop(origin_circuit_t *circ) } } - /* Don't count cannibalized circs for path bias */ + /* Don't re-count cannibalized circs.. */ if (!circ->has_opened) { - entry_guard_t *guard; + 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); + } - 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_DID_FIRST_HOP; + circ->path_state = PATH_STATE_BUILD_ATTEMPTED; - if (entry_guard_inc_first_hop_count(guard) < 0) { + 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(&first_hop_notice_limit, + if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit, approx_time()))) { log_info(LD_BUG, "Unopened circuit has strange path state %s. " @@ -1145,9 +1300,9 @@ pathbias_count_first_hop(origin_circuit_t *circ) } } } else { - if ((rate_msg = rate_limit_log(&first_hop_notice_limit, + if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit, approx_time()))) { - log_info(LD_BUG, + log_info(LD_CIRC, "Unopened circuit has no known guard. " "Circuit is a %s currently %s.%s", circuit_purpose_to_string(circ->base_.purpose), @@ -1157,22 +1312,6 @@ pathbias_count_first_hop(origin_circuit_t *circ) } } } - } else { - /* Help track down the real cause of bug #6475: */ - if (circ->path_state == PATH_STATE_NEW_CIRC) { - if ((rate_msg = rate_limit_log(&first_hop_notice_limit, - approx_time()))) { - log_info(LD_BUG, - "A %s circuit is in cpath state %d (opened: %d). " - "Circuit is a %s currently %s.%s", - pathbias_state_to_string(circ->path_state), - circ->cpath->state, circ->has_opened, - circuit_purpose_to_string(circ->base_.purpose), - circuit_state_to_string(circ->base_.state), - rate_msg); - tor_free(rate_msg); - } - } } return 0; @@ -1186,7 +1325,7 @@ pathbias_count_first_hop(origin_circuit_t *circ) * Also check for several potential error cases for bug #6475. */ static void -pathbias_count_success(origin_circuit_t *circ) +pathbias_count_build_success(origin_circuit_t *circ) { #define SUCCESS_NOTICE_INTERVAL (600) static ratelim_t success_notice_limit = @@ -1194,49 +1333,25 @@ pathbias_count_success(origin_circuit_t *circ) char *rate_msg = NULL; entry_guard_t *guard = NULL; - /* We can't do path bias accounting without entry guards. - * Testing and controller circuits also have no guards. */ - if (get_options()->UseEntryGuards == 0 || - circ->base_.purpose == CIRCUIT_PURPOSE_TESTING || - circ->base_.purpose == CIRCUIT_PURPOSE_CONTROLLER) { - return; - } - - /* Ignore one hop circuits */ - if (circ->build_state->onehop_tunnel || - circ->build_state->desired_path_len == 1) { - /* Check for consistency */ - if (circ->build_state->desired_path_len != 1 || - !circ->build_state->onehop_tunnel) { - if ((rate_msg = rate_limit_log(&success_notice_limit, - approx_time()))) { - log_notice(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(); - } + if (!pathbias_should_count(circ)) { return; } - /* Don't count cannibalized/reused circs for path bias */ + /* Don't count cannibalized/reused circs for path bias + * build success.. They get counted under use success */ if (!circ->has_opened) { - guard = - entry_guard_get_by_id_digest(circ->base_.n_chan->identity_digest); + 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_DID_FIRST_HOP) { - circ->path_state = PATH_STATE_SUCCEEDED; - guard->circuit_successes++; + if (circ->path_state == PATH_STATE_BUILD_ATTEMPTED) { + circ->path_state = PATH_STATE_BUILD_SUCCEEDED; + guard->circ_successes++; - log_info(LD_PROTOCOL, "Got success count %u/%u for guard %s=%s", - guard->circuit_successes, guard->first_hops, + 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, @@ -1252,10 +1367,10 @@ pathbias_count_success(origin_circuit_t *circ) } } - if (guard->first_hops < guard->circuit_successes) { - log_notice(LD_BUG, "Unexpectedly high circuit_successes (%u/%u) " + if (guard->circ_attempts < guard->circ_successes) { + log_notice(LD_BUG, "Unexpectedly high successes counts (%f/%f) " "for guard %s=%s", - guard->circuit_successes, guard->first_hops, + guard->circ_successes, guard->circ_attempts, guard->nickname, hex_str(guard->identity, DIGEST_LEN)); } /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to @@ -1264,7 +1379,7 @@ pathbias_count_success(origin_circuit_t *circ) } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) { if ((rate_msg = rate_limit_log(&success_notice_limit, approx_time()))) { - log_info(LD_BUG, + log_info(LD_CIRC, "Completed circuit has no known guard. " "Circuit is a %s currently %s.%s", circuit_purpose_to_string(circ->base_.purpose), @@ -1274,7 +1389,7 @@ pathbias_count_success(origin_circuit_t *circ) } } } else { - if (circ->path_state != PATH_STATE_SUCCEEDED) { + if (circ->path_state < PATH_STATE_BUILD_SUCCEEDED) { if ((rate_msg = rate_limit_log(&success_notice_limit, approx_time()))) { log_info(LD_BUG, @@ -1290,65 +1405,381 @@ pathbias_count_success(origin_circuit_t *circ) } } +/** + * 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. + */ +void +pathbias_check_close(origin_circuit_t *ocirc, int reason) +{ + circuit_t *circ = ô->base_; + + if (!pathbias_should_count(ocirc)) { + return; + } + + if (ocirc->path_state == PATH_STATE_BUILD_SUCCEEDED) { + if (circ->timestamp_dirty) { + /* 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); + pathbias_count_unusable(ocirc); + } else { + if (reason & END_CIRC_REASON_FLAG_REMOTE) { + /* Unused remote circ close reasons 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); + } + } + } else if (ocirc->path_state == PATH_STATE_USE_SUCCEEDED) { + pathbias_count_successful_close(ocirc); + } +} + +/** + * 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)); + } +} + +static void +pathbias_count_unusable(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. */ + 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(); + } +} + +/** + * 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_closed_count(entry_guard_t *guard) +{ + circuit_t *circ = global_circuitlist; + int open_circuits = 0; + + /* Count currently open circuits. Give them the benefit of the doubt */ + for ( ; 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 >= PATH_STATE_BUILD_SUCCEEDED && + fast_memeq(guard->identity, + ocirc->cpath->extend_info->identity_digest, + DIGEST_LEN)) { + open_circuits++; + } + } + + return guard->successful_circuits_closed + open_circuits; +} + +/** + * This function checks the consensus parameters to decide + * if it should return guard->circ_successes or + * guard->successful_circuits_closed. + */ +double +pathbias_get_success_count(entry_guard_t *guard) +{ + if (pathbias_use_close_counts(get_options())) { + return pathbias_get_closed_count(guard); + } else { + return guard->circ_successes; + } +} + /** Increment the number of times we successfully extended a circuit to * 'guard', 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_first_hop_count(entry_guard_t *guard) +entry_guard_inc_circ_attempt_count(entry_guard_t *guard) { const or_options_t *options = get_options(); entry_guards_changed(); - if (guard->first_hops > (unsigned)pathbias_get_min_circs(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 (guard->circuit_successes/((double)guard->first_hops) - < pathbias_get_disable_rate(options)) { - - /* This message is currently disabled by default. */ - log_warn(LD_PROTOCOL, - "Extremely low circuit success rate %u/%u for guard %s=%s. " - "This indicates either an overloaded guard, an attack, or " - "a bug.", - guard->circuit_successes, guard->first_hops, guard->nickname, - hex_str(guard->identity, DIGEST_LEN)); - - guard->path_bias_disabled = 1; - guard->bad_since = approx_time(); - return -1; - } else if (guard->circuit_successes/((double)guard->first_hops) - < pathbias_get_notice_rate(options) - && !guard->path_bias_notice) { - guard->path_bias_notice = 1; - log_notice(LD_PROTOCOL, - "Low circuit success rate %u/%u for guard %s=%s.", - guard->circuit_successes, guard->first_hops, guard->nickname, - hex_str(guard->identity, DIGEST_LEN)); + if (pathbias_get_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 manipluation attacks, " + "Tor has disabled use of this guard. " + "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_closed_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(); + return -1; + } + } 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. %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_closed_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_success_count(guard)/((double)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 the potentially the guard itself. " + "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_closed_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_success_count(guard)/((double)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. %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_closed_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)); + } } } /* If we get a ton of circuits, just scale everything down */ - if (guard->first_hops > (unsigned)pathbias_get_scale_threshold(options)) { + if (guard->circ_attempts > pathbias_get_scale_threshold(options)) { const int scale_factor = pathbias_get_scale_factor(options); - /* For now, only scale if there will be no rounding error... - * XXX024: We want to switch to a real moving average for 0.2.4. */ - if ((guard->first_hops % scale_factor) == 0 && - (guard->circuit_successes % scale_factor) == 0) { - log_info(LD_PROTOCOL, - "Scaling pathbias counts to (%u/%u)/%d for guard %s=%s", - guard->circuit_successes, guard->first_hops, - scale_factor, guard->nickname, hex_str(guard->identity, - DIGEST_LEN)); - guard->first_hops /= scale_factor; - guard->circuit_successes /= scale_factor; - } + const int mult_factor = pathbias_get_mult_factor(options); + log_info(LD_CIRC, + "Scaling pathbias counts to (%f/%f)*(%d/%d) for guard %s=%s", + guard->circ_successes, guard->circ_attempts, + mult_factor, scale_factor, guard->nickname, + hex_str(guard->identity, DIGEST_LEN)); + + guard->circ_attempts *= mult_factor; + guard->circ_successes *= mult_factor; + guard->timeouts *= mult_factor; + guard->successful_circuits_closed *= mult_factor; + guard->collapsed_circuits *= mult_factor; + guard->unusable_circuits *= mult_factor; + + guard->circ_attempts /= scale_factor; + guard->circ_successes /= scale_factor; + guard->timeouts /= scale_factor; + guard->successful_circuits_closed /= scale_factor; + guard->collapsed_circuits /= scale_factor; + guard->unusable_circuits /= scale_factor; } - guard->first_hops++; - log_info(LD_PROTOCOL, "Got success count %u/%u for guard %s=%s", - guard->circuit_successes, guard->first_hops, guard->nickname, + 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; } @@ -1371,7 +1802,7 @@ circuit_finish_handshake(origin_circuit_t *circ, uint8_t reply_type, crypt_path_t *hop; int rv; - if ((rv = pathbias_count_first_hop(circ)) < 0) + if ((rv = pathbias_count_circ_attempt(circ)) < 0) return rv; if (circ->cpath->state == CPATH_STATE_AWAITING_KEYS) { @@ -2062,6 +2493,11 @@ circuit_extend_to_new_exit(origin_circuit_t *circ, extend_info_t *exit) circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason); return -1; } + + /* Set timestamp_dirty, so we can check it for path use bias */ + if (!circ->base_.timestamp_dirty) + circ->base_.timestamp_dirty = time(NULL); + return 0; } |