Merge remote-tracking branch 'mikeperry/bug7691-rebased'

9 files changed, 377 insertions, 60 deletions

diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index 12d6ea357f..b304aebde5 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,171 @@ pathbias_count_build_success(origin_circuit_t *circ)
 }
 
 /**
+ * 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 cyptographic 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;
+  }
+
+  circuit_change_purpose(circ, CIRCUIT_PURPOSE_PATH_BIAS_TESTING);
+
+  /* Update timestamp for circuit_expire_building to kill us */
+  tor_gettimeofday(&circ->timestamp_began);
+
+  /* Generate a random address for the nonce */
+  crypto_rand((char*)&ocirc->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) {
+      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;
+    } 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
@@ -1512,18 +1678,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 +1707,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 +1743,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;
 }
 
 /**
@@ -2567,6 +2743,9 @@ circuit_extend_to_new_exit(origin_circuit_t *circ, extend_info_t *exit)
 {
   int err_reason = 0;
   warn_if_last_router_excluded(circ, exit);
+
+  tor_gettimeofday(&circ->base_.timestamp_began);
+
   circuit_append_new_exit(circ, exit);
   circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
   if ((err_reason = circuit_send_next_onion_skin(circ))<0) {
diff --git a/src/or/circuitbuild.h b/src/or/circuitbuild.h
index 029bdaa47d..8d2b986b79 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, const cell_t *cell);
 
 #endif
 
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index 1a7306292f..90719d2b63 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 e414df1026..bdaf7d8119 100644
--- a/src/or/circuituse.c
+++ b/src/or/circuituse.c
@@ -280,17 +280,19 @@ circuit_get_best(const entry_connection_t *conn,
     if (!CIRCUIT_IS_ORIGIN(circ))
       continue;
     origin_circ = TO_ORIGIN_CIRCUIT(circ);
-    if (!circuit_is_acceptable(origin_circ,conn,must_be_open,purpose,
-                               need_uptime,need_internal,now.tv_sec))
-      continue;
 
+    /* Log an info message if we're going to launch a new intro circ in
+     * parallel */
     if (purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT &&
-        !must_be_open && circ->state != CIRCUIT_STATE_OPEN &&
-        tv_mdiff(&now, &circ->timestamp_began) > circ_times.timeout_ms) {
-      intro_going_on_but_too_old = 1;
-      continue;
+        !must_be_open && origin_circ->hs_circ_has_timed_out) {
+        intro_going_on_but_too_old = 1;
+        continue;
     }
 
+    if (!circuit_is_acceptable(origin_circ,conn,must_be_open,purpose,
+                               need_uptime,need_internal,now.tv_sec))
+      continue;
+
     /* now this is an acceptable circ to hand back. but that doesn't
      * mean it's the *best* circ to hand back. try to decide.
      */
@@ -367,8 +369,8 @@ circuit_expire_building(void)
    * circuit_build_times_get_initial_timeout() if we haven't computed
    * custom timeouts yet */
   struct timeval general_cutoff, begindir_cutoff, fourhop_cutoff,
-    cannibalize_cutoff, close_cutoff, extremely_old_cutoff,
-    hs_extremely_old_cutoff;
+    close_cutoff, extremely_old_cutoff, hs_extremely_old_cutoff,
+    cannibalized_cutoff, c_intro_cutoff, s_intro_cutoff, stream_cutoff;
   const or_options_t *options = get_options();
   struct timeval now;
   cpath_build_state_t *build_state;
@@ -407,10 +409,60 @@ circuit_expire_building(void)
     timersub(&now, &diff, &target);                         \
   } while (0)
 
+  /**
+   * Because circuit build timeout is calculated only based on 3 hop
+   * general purpose circuit construction, we need to scale the timeout
+   * to make it properly apply to longer circuits, and circuits of
+   * certain usage types. The following diagram illustrates how we
+   * derive the scaling below. In short, we calculate the number
+   * of times our telescoping-based circuit construction causes cells
+   * to traverse each link for the circuit purpose types in question,
+   * and then assume each link is equivalent.
+   *
+   * OP --a--> A --b--> B --c--> C
+   * OP --a--> A --b--> B --c--> C --d--> D
+   *
+   * Let h = a = b = c = d
+   *
+   * Three hops (general_cutoff)
+   *   RTTs = 3a + 2b + c
+   *   RTTs = 6h
+   * Cannibalized:
+   *   RTTs = a+b+c+d
+   *   RTTs = 4h
+   * Four hops:
+   *   RTTs = 4a + 3b + 2c + d
+   *   RTTs = 10h
+   * Client INTRODUCE1+ACK: // XXX: correct?
+   *   RTTs = 5a + 4b + 3c + 2d
+   *   RTTs = 14h
+   * Server intro:
+   *   RTTs = 4a + 3b + 2c
+   *   RTTs = 9h
+   */
   SET_CUTOFF(general_cutoff, circ_times.timeout_ms);
   SET_CUTOFF(begindir_cutoff, circ_times.timeout_ms);
-  SET_CUTOFF(fourhop_cutoff, circ_times.timeout_ms * (4/3.0));
-  SET_CUTOFF(cannibalize_cutoff, circ_times.timeout_ms / 2.0);
+
+  /* > 3hop circs seem to have a 1.0 second delay on their cannibalized
+   * 4th hop. */
+  SET_CUTOFF(fourhop_cutoff, circ_times.timeout_ms * (10/6.0) + 1000);
+
+  /* CIRCUIT_PURPOSE_C_ESTABLISH_REND behaves more like a RELAY cell.
+   * Use the stream cutoff (more or less). */
+  SET_CUTOFF(stream_cutoff, MAX(options->CircuitStreamTimeout,15)*1000 + 1000);
+
+  /* Be lenient with cannibalized circs. They already survived the official
+   * CBT, and they're usually not perf-critical. */
+  SET_CUTOFF(cannibalized_cutoff,
+             MAX(circ_times.close_ms*(4/6.0),
+                 options->CircuitStreamTimeout * 1000) + 1000);
+
+  // Intro circs have an extra round trip (and are also 4 hops long)
+  SET_CUTOFF(c_intro_cutoff, circ_times.timeout_ms * (14/6.0) + 1000);
+
+  // Server intro circs have an extra round trip
+  SET_CUTOFF(s_intro_cutoff, circ_times.timeout_ms * (9/6.0) + 1000);
+
   SET_CUTOFF(close_cutoff, circ_times.close_ms);
   SET_CUTOFF(extremely_old_cutoff, circ_times.close_ms*2 + 1000);
 
@@ -441,13 +493,22 @@ circuit_expire_building(void)
     build_state = TO_ORIGIN_CIRCUIT(victim)->build_state;
     if (build_state && build_state->onehop_tunnel)
       cutoff = begindir_cutoff;
-    else if (build_state && build_state->desired_path_len == 4
-             && !TO_ORIGIN_CIRCUIT(victim)->has_opened)
-      cutoff = fourhop_cutoff;
-    else if (TO_ORIGIN_CIRCUIT(victim)->has_opened)
-      cutoff = cannibalize_cutoff;
     else if (victim->purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT)
       cutoff = close_cutoff;
+    else if (victim->purpose == CIRCUIT_PURPOSE_C_INTRODUCING ||
+             victim->purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT)
+      cutoff = c_intro_cutoff;
+    else if (victim->purpose == CIRCUIT_PURPOSE_S_ESTABLISH_INTRO)
+      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;
+    else if (build_state && build_state->desired_path_len >= 4)
+      cutoff = fourhop_cutoff;
     else
       cutoff = general_cutoff;
 
@@ -520,8 +581,6 @@ circuit_expire_building(void)
         default: /* most open circuits can be left alone. */
           continue; /* yes, continue inside a switch refers to the nearest
                      * enclosing loop. C is smart. */
-        case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
-        case CIRCUIT_PURPOSE_C_INTRODUCING:
         case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
           break; /* too old, need to die */
         case CIRCUIT_PURPOSE_C_REND_READY:
@@ -533,6 +592,19 @@ 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".
+           * We decide below if we're going to mark them timed
+           * out and eventually close them.
+           */
+          break;
+        case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
         case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
         case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
           /* rend and intro circs become dirty each time they
@@ -596,6 +668,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
@@ -621,6 +705,9 @@ circuit_expire_building(void)
         if (TO_ORIGIN_CIRCUIT(victim)->build_state->pending_final_cpath ==
             NULL)
           break;
+        /* fallthrough! */
+      case CIRCUIT_PURPOSE_C_INTRODUCING:
+        /* connection_ap_handshake_attach_circuit() will relaunch for us */
       case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
       case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
         /* If we have reached this line, we want to spare the circ for now. */
@@ -653,15 +740,23 @@ circuit_expire_building(void)
     }
 
     if (victim->n_chan)
-      log_info(LD_CIRC,"Abandoning circ %s:%d (state %d:%s, purpose %d)",
+      log_info(LD_CIRC,
+               "Abandoning circ %u %s:%d (state %d,%d:%s, purpose %d, "
+               "len %d)", TO_ORIGIN_CIRCUIT(victim)->global_identifier,
                channel_get_canonical_remote_descr(victim->n_chan),
                victim->n_circ_id,
+               TO_ORIGIN_CIRCUIT(victim)->has_opened,
                victim->state, circuit_state_to_string(victim->state),
-               victim->purpose);
+               victim->purpose,
+               TO_ORIGIN_CIRCUIT(victim)->build_state->desired_path_len);
     else
-      log_info(LD_CIRC,"Abandoning circ %d (state %d:%s, purpose %d)",
-               victim->n_circ_id, victim->state,
-               circuit_state_to_string(victim->state), victim->purpose);
+      log_info(LD_CIRC,
+               "Abandoning circ %u %d (state %d,%d:%s, purpose %d, len %d)",
+               TO_ORIGIN_CIRCUIT(victim)->global_identifier,
+               victim->n_circ_id, TO_ORIGIN_CIRCUIT(victim)->has_opened,
+               victim->state,
+               circuit_state_to_string(victim->state), victim->purpose,
+               TO_ORIGIN_CIRCUIT(victim)->build_state->desired_path_len);
 
     circuit_log_path(LOG_INFO,LD_CIRC,TO_ORIGIN_CIRCUIT(victim));
     if (victim->purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT)
@@ -1165,18 +1260,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. */
@@ -2101,28 +2184,12 @@ connection_ap_handshake_attach_circuit(entry_connection_t *conn)
 
     if (retval > 0) {
       /* one has already sent the intro. keep waiting. */
-      circuit_t *c = NULL;
       tor_assert(introcirc);
       log_info(LD_REND, "Intro circ %d present and awaiting ack (rend %d). "
                "Stalling. (stream %d sec old)",
                introcirc->base_.n_circ_id,
                rendcirc ? rendcirc->base_.n_circ_id : 0,
                conn_age);
-      /* abort parallel intro circs, if any */
-      for (c = global_circuitlist; c; c = c->next) {
-        if (c->purpose == CIRCUIT_PURPOSE_C_INTRODUCING &&
-            !c->marked_for_close && CIRCUIT_IS_ORIGIN(c)) {
-          origin_circuit_t *oc = TO_ORIGIN_CIRCUIT(c);
-          if (oc->rend_data &&
-              !rend_cmp_service_ids(
-                            ENTRY_TO_EDGE_CONN(conn)->rend_data->onion_address,
-                            oc->rend_data->onion_address)) {
-            log_info(LD_REND|LD_CIRC, "Closing introduction circuit that we "
-                     "built in parallel.");
-            circuit_mark_for_close(c, END_CIRC_REASON_TIMEOUT);
-          }
-        }
-      }
       return 0;
     }
 
diff --git a/src/or/connection_edge.c b/src/or/connection_edge.c
index a0ebfd1397..272955f165 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 9f38951f40..82cd95bedf 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 7b8ff705a4..eb0dc81b11 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
+   * (in host byte order) for response comparison. */
+  uint32_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 f58c5c9c55..a942e44651 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) {
diff --git a/src/or/rendclient.c b/src/or/rendclient.c
index 0bed615b60..2219fe8a1b 100644
--- a/src/or/rendclient.c
+++ b/src/or/rendclient.c
@@ -66,6 +66,11 @@ rend_client_send_establish_rendezvous(origin_circuit_t *circ)
     circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_INTERNAL);
     return -1;
   }
+
+  /* Set timestamp_dirty, because circuit_expire_building expects it,
+   * and the rend cookie also means we've used the circ. */
+  circ->base_.timestamp_dirty = time(NULL);
+
   if (relay_send_command_from_edge(0, TO_CIRCUIT(circ),
                                    RELAY_COMMAND_ESTABLISH_RENDEZVOUS,
                                    circ->rend_data->rend_cookie,
@@ -100,6 +105,7 @@ rend_client_reextend_intro_circuit(origin_circuit_t *circ)
     circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_INTERNAL);
     return -1;
   }
+  // XXX: should we not re-extend if hs_circ_has_timed_out?
   if (circ->remaining_relay_early_cells) {
     log_info(LD_REND,
              "Re-extending circ %d, this time to %s.",
@@ -338,6 +344,32 @@ rend_client_rendcirc_has_opened(origin_circuit_t *circ)
   }
 }
 
+/**
+ * Called to close other intro circuits we launched in parallel
+ * due to timeout.
+ */
+static void
+rend_client_close_other_intros(const char *onion_address)
+{
+  circuit_t *c;
+  /* abort parallel intro circs, if any */
+  for (c = circuit_get_global_list_(); c; c = c->next) {
+    if ((c->purpose == CIRCUIT_PURPOSE_C_INTRODUCING ||
+        c->purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT) &&
+        !c->marked_for_close && CIRCUIT_IS_ORIGIN(c)) {
+      origin_circuit_t *oc = TO_ORIGIN_CIRCUIT(c);
+      if (oc->rend_data &&
+          !rend_cmp_service_ids(onion_address,
+                                oc->rend_data->onion_address)) {
+        log_info(LD_REND|LD_CIRC, "Closing introduction circuit %d that we "
+                 "built in parallel (Purpose %d).", oc->global_identifier,
+                 c->purpose);
+        circuit_mark_for_close(c, END_CIRC_REASON_TIMEOUT);
+      }
+    }
+  }
+}
+
 /** Called when get an ACK or a NAK for a REND_INTRODUCE1 cell.
  */
 int
@@ -389,6 +421,9 @@ rend_client_introduction_acked(origin_circuit_t *circ,
     circuit_change_purpose(TO_CIRCUIT(circ),
                            CIRCUIT_PURPOSE_C_INTRODUCE_ACKED);
     circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_FINISHED);
+
+    /* close any other intros launched in parallel */
+    rend_client_close_other_intros(circ->rend_data->onion_address);
   } else {
     /* It's a NAK; the introduction point didn't relay our request. */
     circuit_change_purpose(TO_CIRCUIT(circ), CIRCUIT_PURPOSE_C_INTRODUCING);