commit 412ae099cb656ab47fc8cbb408aa5f4cee956961 Author: Mike Perry mikeperry-git@fscked.org Date: Sat Nov 17 16:30:50 2012 -0800
Prop 209: Add path bias counts for timeouts and other mechanisms.
Turns out there's more than one way to block a tagged circuit.
This seems to successfully handle all of the normal exit circuits. Hidden services need additional tweaks, still. --- src/or/circuitbuild.c | 194 ++++++++++++++++++++++++++++++++++++++++++---- src/or/circuitbuild.h | 6 ++ src/or/circuitlist.c | 37 +++++++++ src/or/config.c | 1 + src/or/connection_edge.c | 11 +++ src/or/entrynodes.c | 36 +++++++-- src/or/entrynodes.h | 10 ++- src/or/or.h | 8 ++ 8 files changed, 277 insertions(+), 26 deletions(-)
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index 215ca14..22f7289 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -1104,6 +1104,21 @@ pathbias_get_mult_factor(const or_options_t *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 * @@ -1348,6 +1363,94 @@ pathbias_count_success(origin_circuit_t *circ) }
/** + * Count a successfully closed circuit. + */ +void +pathbias_count_successful_close(origin_circuit_t *circ) +{ + entry_guard_t *guard = NULL; + if (!pathbias_should_count(circ)) { + return; + } + + guard = entry_guard_get_by_id_digest(circ->base_.n_chan->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_BUG, + "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. + */ +void +pathbias_count_collapse(origin_circuit_t *circ) +{ + entry_guard_t *guard = NULL; + if (!pathbias_should_count(circ)) { + return; + } + + guard = entry_guard_get_by_id_digest(circ->base_.n_chan->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_BUG, + "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)); + } +} + +void +pathbias_count_unusable(origin_circuit_t *circ) +{ + entry_guard_t *guard = NULL; + if (!pathbias_should_count(circ)) { + return; + } + + guard = entry_guard_get_by_id_digest(circ->base_.n_chan->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_BUG, + "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. @@ -1367,6 +1470,44 @@ pathbias_count_timeout(origin_circuit_t *circ) } }
+// XXX: DOCDOC +int +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) { + if (!CIRCUIT_IS_ORIGIN(circ) || /* didn't originate here */ + circ->marked_for_close) /* already counted */ + continue; + + if (TO_ORIGIN_CIRCUIT(circ)->path_state == PATH_STATE_SUCCEEDED && + (memcmp(guard->identity, circ->n_chan->identity_digest, DIGEST_LEN) + == 0)) { + open_circuits++; + } + } + + return guard->successful_circuits_closed + open_circuits; +} + +/** + * This function checks the consensus parameters to decide + * if it should return guard->circuit_successes or + * guard->successful_circuits_closed. + */ +static int +pathbias_get_success_count(entry_guard_t *guard) +{ + if (pathbias_use_close_counts(get_options())) { + return pathbias_get_closed_count(guard); + } else { + return guard->circuit_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 @@ -1382,7 +1523,7 @@ entry_guard_inc_first_hop_count(entry_guard_t *guard) /* 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) + if (pathbias_get_success_count(guard)/((double)guard->first_hops) < pathbias_get_extreme_rate(options)) { /* Dropping is currently disabled by default. */ if (pathbias_get_dropguards(options)) { @@ -1390,11 +1531,14 @@ entry_guard_inc_first_hop_count(entry_guard_t *guard) 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 %d/%d, with %d timeouts. For reference, your " - "timeout cutoff is %ld seconds.", + "Tor has disabled use of this guard. " + "Success counts are %d/%d. %d circuits completed, %d " + "were unusable, %d collapsed, and %d timed out. For " + "reference, your timeout cutoff is %ld seconds.", guard->nickname, hex_str(guard->identity, DIGEST_LEN), - guard->circuit_successes, guard->first_hops, guard->timeouts, + pathbias_get_closed_count(guard), guard->first_hops, + guard->circuit_successes, guard->unusable_circuits, + guard->collapsed_circuits, guard->timeouts, (long)circ_times.close_ms/1000); guard->path_bias_disabled = 1; guard->bad_since = approx_time(); @@ -1406,13 +1550,16 @@ entry_guard_inc_first_hop_count(entry_guard_t *guard) "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 %d/%d, with %d timeouts. " - "For reference, your timeout cutoff is %ld seconds.", + "Success counts are %d/%d. %d circuits completed, %d " + "were unusable, %d collapsed, and %d timed out. For " + "reference, your timeout cutoff is %ld seconds.", guard->nickname, hex_str(guard->identity, DIGEST_LEN), - guard->circuit_successes, guard->first_hops, guard->timeouts, + pathbias_get_closed_count(guard), guard->first_hops, + guard->circuit_successes, guard->unusable_circuits, + guard->collapsed_circuits, guard->timeouts, (long)circ_times.close_ms/1000); } - } else if (guard->circuit_successes/((double)guard->first_hops) + } else if (pathbias_get_success_count(guard)/((double)guard->first_hops) < pathbias_get_warn_rate(options)) { if (!guard->path_bias_warned) { guard->path_bias_warned = 1; @@ -1420,25 +1567,31 @@ entry_guard_inc_first_hop_count(entry_guard_t *guard) "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 %d/%d, with %d timeouts. For reference, your timeout " - "cutoff is %ld seconds.", + "you or the potentially the guard itself. " + "Success counts are %d/%d. %d circuits completed, %d " + "were unusable, %d collapsed, and %d timed out. For " + "reference, your timeout cutoff is %ld seconds.", guard->nickname, hex_str(guard->identity, DIGEST_LEN), - guard->circuit_successes, guard->first_hops, guard->timeouts, + pathbias_get_closed_count(guard), guard->first_hops, + guard->circuit_successes, guard->unusable_circuits, + guard->collapsed_circuits, guard->timeouts, (long)circ_times.close_ms/1000); } - } else if (guard->circuit_successes/((double)guard->first_hops) + } else if (pathbias_get_success_count(guard)/((double)guard->first_hops) < 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 %d/%d, with %d timeouts. For " + "Success counts are %d/%d. %d circuits completed, %d " + "were unusable, %d collapsed, and %d timed out. For " "reference, your timeout cutoff is %ld seconds.", guard->nickname, hex_str(guard->identity, DIGEST_LEN), - guard->circuit_successes, guard->first_hops, - guard->timeouts, (long)circ_times.close_ms/1000); + pathbias_get_closed_count(guard), guard->first_hops, + guard->circuit_successes, guard->unusable_circuits, + guard->collapsed_circuits, guard->timeouts, + (long)circ_times.close_ms/1000); } } } @@ -1456,13 +1609,20 @@ entry_guard_inc_first_hop_count(entry_guard_t *guard) guard->circuit_successes, guard->first_hops, mult_factor, scale_factor, guard->nickname, hex_str(guard->identity, DIGEST_LEN)); + guard->first_hops *= mult_factor; guard->circuit_successes *= mult_factor; guard->timeouts *= mult_factor; + guard->successful_circuits_closed *= mult_factor; + guard->collapsed_circuits *= mult_factor; + guard->unusable_circuits *= mult_factor;
guard->first_hops /= scale_factor; guard->circuit_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++; diff --git a/src/or/circuitbuild.h b/src/or/circuitbuild.h index 3338c9e..325a583 100644 --- a/src/or/circuitbuild.h +++ b/src/or/circuitbuild.h @@ -56,6 +56,12 @@ const node_t *choose_good_entry_server(uint8_t purpose, double pathbias_get_extreme_rate(const or_options_t *options); int pathbias_get_dropguards(const or_options_t *options); void pathbias_count_timeout(origin_circuit_t *circ); +void pathbias_count_successful_close(origin_circuit_t *circ); +void pathbias_count_collapse(origin_circuit_t *circ); +void pathbias_count_unusable(origin_circuit_t *circ); + +typedef struct entry_guard_t entry_guard_t; +int pathbias_get_closed_count(entry_guard_t *gaurd);
#endif
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c index 8f06c06..66cdbe1 100644 --- a/src/or/circuitlist.c +++ b/src/or/circuitlist.c @@ -1347,7 +1347,44 @@ circuit_mark_for_close_(circuit_t *circ, int reason, int line, } reason = END_CIRC_REASON_NONE; } + if (CIRCUIT_IS_ORIGIN(circ)) { + origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ); + + if (ocirc->path_state == PATH_STATE_SUCCEEDED) { + int pathbias_is_normal_close = 1; + + /* FIXME: Is timestamp_dirty the right thing for these two checks? + * Should we use isolation_any_streams_attached instead? */ + if (!circ->timestamp_dirty) { + if (reason & END_CIRC_REASON_FLAG_REMOTE) { + /* Unused remote circ close reasons all could be bias */ + pathbias_is_normal_close = 0; + pathbias_count_collapse(ocirc); + } else if ((reason & ~END_CIRC_REASON_FLAG_REMOTE) + == END_CIRC_REASON_CHANNEL_CLOSED && + circ->n_chan->reason_for_closing + != CHANNEL_CLOSE_REQUESTED) { + /* If we didn't close the channel ourselves, it could be bias */ + /* FIXME: Only count bias if the network is live? + * What about clock jumps/suspends? */ + pathbias_is_normal_close = 0; + pathbias_count_collapse(ocirc); + } + } else if (circ->timestamp_dirty && !ocirc->any_streams_succeeded) { + /* Any circuit where there were attempted streams but no successful + * streams could be bias */ + /* FIXME: This may be better handled by limiting the number of retries + * per stream? */ + pathbias_is_normal_close = 0; + pathbias_count_unusable(ocirc); + } + + if (pathbias_is_normal_close) { + pathbias_count_successful_close(ocirc); + } + } + /* We don't send reasons when closing circuits at the origin. */ reason = END_CIRC_REASON_NONE; } diff --git a/src/or/config.c b/src/or/config.c index fb95642..79725cb 100644 --- a/src/or/config.c +++ b/src/or/config.c @@ -323,6 +323,7 @@ static config_var_t option_vars_[] = { V(PathBiasScaleFactor, INT, "-1"), V(PathBiasMultFactor, INT, "-1"), V(PathBiasDropGuards, BOOL, "0"), + V(PathBiasUseCloseCounts, BOOL, "1"),
OBSOLETE("PathlenCoinWeight"), V(PerConnBWBurst, MEMUNIT, "0"), diff --git a/src/or/connection_edge.c b/src/or/connection_edge.c index 95088c7..cb2afe1 100644 --- a/src/or/connection_edge.c +++ b/src/or/connection_edge.c @@ -2176,6 +2176,17 @@ connection_ap_handshake_socks_reply(entry_connection_t *conn, char *reply, status==SOCKS5_SUCCEEDED ? STREAM_EVENT_SUCCEEDED : STREAM_EVENT_FAILED, endreason);
+ /* Flag this stream's circuit as having completed a stream successfully + * (for path bias) */ + if (status == SOCKS5_SUCCEEDED) { + if(!conn->edge_.on_circuit || + !CIRCUIT_IS_ORIGIN(conn->edge_.on_circuit)) { + log_warn(LD_BUG, "No origin circuit for successful SOCKS stream"); + } else { + TO_ORIGIN_CIRCUIT(conn->edge_.on_circuit)->any_streams_succeeded = 1; + } + } + if (conn->socks_request->has_finished) { log_warn(LD_BUG, "(Harmless.) duplicate calls to " "connection_ap_handshake_socks_reply."); diff --git a/src/or/entrynodes.c b/src/or/entrynodes.c index 317a088..1e64aaf 100644 --- a/src/or/entrynodes.c +++ b/src/or/entrynodes.c @@ -1021,7 +1021,8 @@ entry_guards_parse_state(or_state_t *state, int set, char **msg) digestmap_set(added_by, d, tor_strdup(line->value+HEX_DIGEST_LEN+1)); } else if (!strcasecmp(line->key, "EntryGuardPathBias")) { const or_options_t *options = get_options(); - unsigned hop_cnt, success_cnt, timeouts; + unsigned hop_cnt, success_cnt, timeouts, collapsed, successful_closed, + unusable;
if (!node) { *msg = tor_strdup("Unable to parse entry nodes: " @@ -1030,19 +1031,33 @@ entry_guards_parse_state(or_state_t *state, int set, char **msg) }
/* First try 3 params, then 2. */ - if (tor_sscanf(line->value, "%u %u %u", &success_cnt, &hop_cnt, - &timeouts) != 3) { - timeouts = 0; + // XXX: We want to convert this to floating point before merge + /* In the long run: circuit_success ~= successful_circuit_close + + * collapsed_circuits + + * unusable_circuits */ + if (tor_sscanf(line->value, "%u %u %u %u %u %u", + &hop_cnt, &success_cnt, &successful_closed, + &collapsed, &unusable, &timeouts) != 6) { if (tor_sscanf(line->value, "%u %u", &success_cnt, &hop_cnt) != 2) { - log_warn(LD_GENERAL, "Unable to parse guard path bias info: " - "Misformated EntryGuardPathBias %s", escaped(line->value)); continue; } + log_info(LD_GENERAL, "Reading old-style EntryGuardPathBias %s", + escaped(line->value)); + + successful_closed = success_cnt; + timeouts = 0; + collapsed = 0; + unusable = 0; }
node->first_hops = hop_cnt; node->circuit_successes = success_cnt; + + node->successful_circuits_closed = successful_closed; node->timeouts = timeouts; + node->collapsed_circuits = collapsed; + node->unusable_circuits = unusable; + log_info(LD_GENERAL, "Read %u/%u path bias for node %s", node->circuit_successes, node->first_hops, node->nickname); /* Note: We rely on the < comparison here to allow us to set a 0 @@ -1180,8 +1195,13 @@ entry_guards_update_state(or_state_t *state) if (e->first_hops) { *next = line = tor_malloc_zero(sizeof(config_line_t)); line->key = tor_strdup("EntryGuardPathBias"); - tor_asprintf(&line->value, "%u %u %u", - e->circuit_successes, e->first_hops, e->timeouts); + /* In the long run: circuit_success ~= successful_circuit_close + + * collapsed_circuits + + * unusable_circuits */ + tor_asprintf(&line->value, "%u %u %u %u %u %u", + e->first_hops, e->circuit_successes, + pathbias_get_closed_count(e), e->collapsed_circuits, + e->unusable_circuits, e->timeouts); next = &(line->next); }
diff --git a/src/or/entrynodes.h b/src/or/entrynodes.h index f087f90..b9c8052 100644 --- a/src/or/entrynodes.h +++ b/src/or/entrynodes.h @@ -51,7 +51,15 @@ typedef struct entry_guard_t { unsigned first_hops; /**< Number of first hops this guard has completed */ unsigned circuit_successes; /**< Number of successfully built circuits using * this guard as first hop. */ - unsigned timeouts; /**< Number of 'right-censored' timeouts for this guard.*/ + unsigned successful_circuits_closed; /**< Number of circuits that carried + * streams successfully. */ + unsigned collapsed_circuits; /**< Number of fully built circuits that were + * remotely closed before any streams were + * attempted. */ + unsigned unusable_circuits; /**< Number of circuits for which streams were + * attempted, but none succeeded. */ + unsigned timeouts; /**< Number of 'right-censored' circuit timeouts for this + * guard. */ } entry_guard_t;
entry_guard_t *entry_guard_get_by_id_digest(const char *digest); diff --git a/src/or/or.h b/src/or/or.h index a5e96b2..f26fc39 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -2872,6 +2872,13 @@ typedef struct origin_circuit_t { */ unsigned int isolation_any_streams_attached : 1;
+ /** + * Did any SOCKS streams actually succeed on this circuit? + * + * XXX: We probably also need to set this for intro other hidserv circs.. + */ + unsigned int any_streams_succeeded : 1; + /** A bitfield of ISO_* flags for every isolation field such that this * circuit has had streams with more than one value for that field * attached to it. */ @@ -3790,6 +3797,7 @@ typedef struct { int PathBiasScaleThreshold; int PathBiasScaleFactor; int PathBiasMultFactor; + int PathBiasUseCloseCounts; /** @} */
int IPv6Exit; /**< Do we support exiting to IPv6 addresses? */