commit 15fdfc2993777497883df8945c1c9138bea2b33a Author: Mike Perry mikeperry-git@fscked.org Date: Wed Dec 12 11:53:18 2012 -0800

Bug 7691: Send a probe cell down certain types of circs.

In general, if we tried to use a circ for a stream, but then decided to place that stream on a different circuit, we need to probe the original circuit before deciding it was a "success".

We also need to do the same for cannibalized circuits that go unused. --- src/or/circuitbuild.c | 160 +++++++++++++++++++++++++++++++++++++++++++++- src/or/circuitbuild.h | 3 +- src/or/circuitlist.c | 8 ++- src/or/circuituse.c | 31 ++++++---- src/or/connection_edge.c | 2 +- src/or/connection_edge.h | 1 + src/or/or.h | 12 +++- src/or/relay.c | 22 ++++++- 8 files changed, 218 insertions(+), 21 deletions(-)

diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index 7d94b2b..73bd3d4 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -39,6 +39,7 @@ #include "routerparse.h" #include "routerset.h" #include "crypto.h" +#include "connection_edge.h"

#ifndef MIN #define MIN(a,b) ((a)<(b)?(a):(b)) @@ -1504,6 +1505,149 @@ pathbias_count_build_success(origin_circuit_t *circ) }

/** + * Send a probe down a circuit that wasn't usable. + * + * 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; + // XXX: Generate a random 0.a.b.c adddress + const char *probe_nonce = "0.1.2.3"; + + 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; + } + + circuit_change_purpose(circ, CIRCUIT_PURPOSE_PATH_BIAS_TESTING); + + /* Update timestamp for circuit_expire_building to kill us */ + tor_gettimeofday(&circ->timestamp_began); + + tor_snprintf(payload,RELAY_PAYLOAD_SIZE, "%s:25", probe_nonce); + tor_addr_parse(&ocirc->pathbias_probe_nonce, 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); + 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); + + /* 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. + * + * If the response is valid, return 0. Otherwise return < 0. + */ +int +pathbias_check_probe_response(circuit_t *circ, cell_t *cell) +{ + /* Based on connection_edge_process_relay_cell() */ + relay_header_t rh; + int reason; + uint32_t ipv4_host; + tor_addr_t 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_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL, + "Path bias probe response length field is insane (%d).", + rh.length); + return - END_CIRC_REASON_TORPROTOCOL; + } + + ipv4_host = get_uint32(cell->payload+RELAY_HEADER_SIZE+1); + tor_addr_from_ipv4n(&host, ipv4_host); + + /* Check nonce */ + if (memcmp(&host, &ocirc->pathbias_probe_nonce, sizeof(tor_addr_t)) == 0) { + ocirc->path_state = PATH_STATE_USE_SUCCEEDED; + 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; + } + } + 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 @@ -1512,18 +1656,26 @@ pathbias_count_build_success(origin_circuit_t *circ) * * 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. */ -void +int pathbias_check_close(origin_circuit_t *ocirc, int reason) { circuit_t *circ = &ocirc->base_;

if (!pathbias_should_count(ocirc)) { - return; + return 0; }

if (ocirc->path_state == PATH_STATE_BUILD_SUCCEEDED) { if (circ->timestamp_dirty) { + if (pathbias_send_usable_probe(circ) == 0) + return -1; + else + pathbias_count_unusable(ocirc); + /* Any circuit where there were attempted streams but no successful * streams could be bias */ log_info(LD_CIRC, @@ -1533,7 +1685,7 @@ pathbias_check_close(origin_circuit_t *ocirc, int reason) 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 */ @@ -1569,6 +1721,8 @@ pathbias_check_close(origin_circuit_t *ocirc, int reason) } else if (ocirc->path_state == PATH_STATE_USE_SUCCEEDED) { pathbias_count_successful_close(ocirc); } + + return 0; }

/** diff --git a/src/or/circuitbuild.h b/src/or/circuitbuild.h index 029bdaa..b1cedec 100644 --- a/src/or/circuitbuild.h +++ b/src/or/circuitbuild.h @@ -60,7 +60,8 @@ 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_check_close(origin_circuit_t *circ, int reason); +int pathbias_check_close(origin_circuit_t *circ, int reason); +int pathbias_check_probe_response(circuit_t *circ, cell_t *cell);

#endif

diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c index 1a73062..90719d2 100644 --- a/src/or/circuitlist.c +++ b/src/or/circuitlist.c @@ -414,6 +414,8 @@ circuit_purpose_to_controller_string(uint8_t purpose) return "MEASURE_TIMEOUT"; case CIRCUIT_PURPOSE_CONTROLLER: return "CONTROLLER"; + case CIRCUIT_PURPOSE_PATH_BIAS_TESTING: + return "PATH_BIAS_TESTING";

default: tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose); @@ -441,6 +443,7 @@ circuit_purpose_to_controller_hs_state_string(uint8_t purpose) case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT: case CIRCUIT_PURPOSE_TESTING: case CIRCUIT_PURPOSE_CONTROLLER: + case CIRCUIT_PURPOSE_PATH_BIAS_TESTING: return NULL;

case CIRCUIT_PURPOSE_INTRO_POINT: @@ -1356,7 +1359,10 @@ circuit_mark_for_close_(circuit_t *circ, int reason, int line, }

if (CIRCUIT_IS_ORIGIN(circ)) { - pathbias_check_close(TO_ORIGIN_CIRCUIT(circ), reason); + if (pathbias_check_close(TO_ORIGIN_CIRCUIT(circ), reason) == -1) { + /* Don't close it yet, we need to test it first */ + return; + }

/* We don't send reasons when closing circuits at the origin. */ reason = END_CIRC_REASON_NONE; diff --git a/src/or/circuituse.c b/src/or/circuituse.c index ffcebfd..de62100 100644 --- a/src/or/circuituse.c +++ b/src/or/circuituse.c @@ -493,6 +493,8 @@ circuit_expire_building(void) cutoff = s_intro_cutoff; else if (victim->purpose == CIRCUIT_PURPOSE_C_ESTABLISH_REND) cutoff = stream_cutoff; + else if (victim->purpose == CIRCUIT_PURPOSE_PATH_BIAS_TESTING) + cutoff = close_cutoff; else if (TO_ORIGIN_CIRCUIT(victim)->has_opened && victim->state != CIRCUIT_STATE_OPEN) cutoff = cannibalized_cutoff; @@ -581,6 +583,11 @@ circuit_expire_building(void) victim->timestamp_dirty > cutoff.tv_sec) continue; break; + case CIRCUIT_PURPOSE_PATH_BIAS_TESTING: + /* Open path bias testing circuits are given a long + * time to complete the test, but not forever */ + TO_ORIGIN_CIRCUIT(victim)->path_state = PATH_STATE_USE_FAILED; + break; case CIRCUIT_PURPOSE_C_INTRODUCING: /* We keep old introducing circuits around for * a while in parallel, and they can end up "opened". @@ -652,6 +659,18 @@ circuit_expire_building(void) circuit_build_times_set_timeout(&circ_times); } } + + if (TO_ORIGIN_CIRCUIT(victim)->has_opened && + victim->purpose != CIRCUIT_PURPOSE_PATH_BIAS_TESTING) { + /* For path bias: we want to let these guys live for a while + * so we get a chance to test them. */ + log_info(LD_CIRC, + "Allowing cannibalized circuit %d time to finish building as a " + "pathbias testing circ.", + TO_ORIGIN_CIRCUIT(victim)->global_identifier); + circuit_change_purpose(victim, CIRCUIT_PURPOSE_PATH_BIAS_TESTING); + continue; /* It now should have a longer timeout next time */ + } }

/* If this is a hidden service client circuit which is far enough @@ -1232,18 +1251,6 @@ circuit_has_opened(origin_circuit_t *circ) { control_event_circuit_status(circ, CIRC_EVENT_BUILT, 0);

- /* Cannibalized circuits count as used for path bias. - * (PURPOSE_GENERAL circs especially, since they are - * marked dirty and often go unused after preemptive - * building). */ - // XXX: Cannibalized now use RELAY_EARLY, which is visible - // to taggers end-to-end! We really need to probe these instead. - // Don't forget to remove this check once that's done! - if (circ->has_opened && - circ->build_state->desired_path_len > DEFAULT_ROUTE_LEN) { - circ->path_state = PATH_STATE_USE_SUCCEEDED; - } - /* Remember that this circuit has finished building. Now if we start * it building again later (e.g. by extending it), we will know not * to consider its build time. */ diff --git a/src/or/connection_edge.c b/src/or/connection_edge.c index a0ebfd1..272955f 100644 --- a/src/or/connection_edge.c +++ b/src/or/connection_edge.c @@ -1661,7 +1661,7 @@ connection_ap_process_natd(entry_connection_t *conn) /** Iterate over the two bytes of stream_id until we get one that is not * already in use; return it. Return 0 if can't get a unique stream_id. */ -static streamid_t +streamid_t get_unique_stream_id_by_circ(origin_circuit_t *circ) { edge_connection_t *tmpconn; diff --git a/src/or/connection_edge.h b/src/or/connection_edge.h index 9f38951..82cd95b 100644 --- a/src/or/connection_edge.h +++ b/src/or/connection_edge.h @@ -90,6 +90,7 @@ int connection_edge_update_circuit_isolation(const entry_connection_t *conn, origin_circuit_t *circ, int dry_run); void circuit_clear_isolation(origin_circuit_t *circ); +streamid_t get_unique_stream_id_by_circ(origin_circuit_t *circ);

/** @name Begin-cell flags * diff --git a/src/or/or.h b/src/or/or.h index 7b8ff70..4b4806c 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -522,7 +522,9 @@ typedef enum { #define CIRCUIT_PURPOSE_TESTING 18 /** A controller made this circuit and Tor should not use it. */ #define CIRCUIT_PURPOSE_CONTROLLER 19 -#define CIRCUIT_PURPOSE_MAX_ 19 +/** This circuit is used for path bias probing only */ +#define CIRCUIT_PURPOSE_PATH_BIAS_TESTING 20 +#define CIRCUIT_PURPOSE_MAX_ 20 /** A catch-all for unrecognized purposes. Currently we don't expect * to make or see any circuits with this purpose. */ #define CIRCUIT_PURPOSE_UNKNOWN 255 @@ -2887,6 +2889,14 @@ typedef struct origin_circuit_t { * debug why we are not seeing first hops in some cases. */ path_state_t path_state : 3;

+ /** For path probing. Store the temporary probe stream ID + * for response comparison */ + streamid_t pathbias_probe_id; + + /** For path probing. Store the temporary probe address nonce + * for response comparison. */ + tor_addr_t pathbias_probe_nonce; + /** Set iff this is a hidden-service circuit which has timed out * according to our current circuit-build timeout, but which has * been kept around because it might still succeed in connecting to diff --git a/src/or/relay.c b/src/or/relay.c index f58c5c9..a942e44 100644 --- a/src/or/relay.c +++ b/src/or/relay.c @@ -186,7 +186,17 @@ circuit_receive_relay_cell(cell_t *cell, circuit_t *circ, }

if (recognized) { - edge_connection_t *conn = relay_lookup_conn(circ, cell, cell_direction, + edge_connection_t *conn = NULL; + + if (circ->purpose == CIRCUIT_PURPOSE_PATH_BIAS_TESTING) { + pathbias_check_probe_response(circ, cell); + + /* We need to drop this cell no matter what to avoid code that expects + * a certain purpose (such as the hidserv code). */ + return 0; + } + + conn = relay_lookup_conn(circ, cell, cell_direction, layer_hint); if (cell_direction == CELL_DIRECTION_OUT) { ++stats_n_relay_cells_delivered; @@ -222,7 +232,15 @@ circuit_receive_relay_cell(cell_t *cell, circuit_t *circ, } else { log_fn(LOG_PROTOCOL_WARN, LD_OR, "Dropping unrecognized inbound cell on origin circuit."); - return 0; + /* If we see unrecognized cells on path bias testing circs, + * it's bad mojo. Those circuits need to die. + * XXX: Shouldn't they always die? */ + if (circ->purpose == CIRCUIT_PURPOSE_PATH_BIAS_TESTING) { + TO_ORIGIN_CIRCUIT(circ)->path_state = PATH_STATE_USE_FAILED; + return -END_CIRC_REASON_TORPROTOCOL; + } else { + return 0; + } }

if (!chan) {