path: root/src/feature/client/circpathbias.c

/* Copyright (c) 2001 Matej Pfajfar.
 * Copyright (c) 2001-2004, Roger Dingledine.
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
 * Copyright (c) 2007-2020, The Tor Project, Inc. */
/* See LICENSE for licensing information */

/**
 * \file circpathbias.c
 *
 * \brief Code to track success/failure rates of circuits built through
 * different tor nodes, in an attempt to detect attacks where
 * an attacker deliberately causes circuits to fail until the client
 * choses a path they like.
 *
 * This code is currently configured in a warning-only mode, though false
 * positives appear to be rare in practice.  There is also support for
 * disabling really bad guards, but it's quite experimental and may have bad
 * anonymity effects.
 *
 * The information here is associated with the entry_guard_t object for
 * each guard, and stored persistently in the state file.
 */

#include "core/or/or.h"
#include "core/or/channel.h"
#include "feature/client/circpathbias.h"
#include "core/or/circuitbuild.h"
#include "core/or/circuitlist.h"
#include "core/or/circuituse.h"
#include "core/or/circuitstats.h"
#include "core/or/connection_edge.h"
#include "app/config/config.h"
#include "lib/crypt_ops/crypto_rand.h"
#include "feature/client/entrynodes.h"
#include "feature/nodelist/networkstatus.h"
#include "core/or/relay.h"
#include "lib/math/fp.h"
#include "lib/math/laplace.h"

#include "core/or/cell_st.h"
#include "core/or/cpath_build_state_st.h"
#include "core/or/crypt_path_st.h"
#include "core/or/extend_info_st.h"
#include "core/or/origin_circuit_st.h"

static void pathbias_count_successful_close(origin_circuit_t *circ);
static void pathbias_count_collapse(origin_circuit_t *circ);
static void pathbias_count_use_failed(origin_circuit_t *circ);
static void pathbias_measure_use_rate(entry_guard_t *guard);
static void pathbias_measure_close_rate(entry_guard_t *guard);
static void pathbias_scale_use_rates(entry_guard_t *guard);
static void pathbias_scale_close_rates(entry_guard_t *guard);
static int entry_guard_inc_circ_attempt_count(entry_guard_t *guard);

/** Increment the number of times we successfully extended a circuit to
 * <b>guard</b>, first checking if the failure rate is high enough that
 * we should eliminate the guard. Return -1 if the guard looks no good;
 * return 0 if the guard looks fine.
 */
static int
entry_guard_inc_circ_attempt_count(entry_guard_t *guard)
{
  guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);

  entry_guards_changed();

  pathbias_measure_close_rate(guard);

  if (pb->path_bias_disabled)
    return -1;

  pathbias_scale_close_rates(guard);
  pb->circ_attempts++;

  log_info(LD_CIRC, "Got success count %f/%f for guard %s",
           pb->circ_successes, pb->circ_attempts,
           entry_guard_describe(guard));
  return 0;
}

/** The minimum number of circuit attempts before we start
  * thinking about warning about path bias and dropping guards */
static int
pathbias_get_min_circs(const or_options_t *options)
{
#define DFLT_PATH_BIAS_MIN_CIRC 150
  if (options->PathBiasCircThreshold >= 5)
    return options->PathBiasCircThreshold;
  else
    return networkstatus_get_param(NULL, "pb_mincircs",
                                   DFLT_PATH_BIAS_MIN_CIRC,
                                   5, INT32_MAX);
}

/** The circuit success rate below which we issue a notice */
static double
pathbias_get_notice_rate(const or_options_t *options)
{
#define DFLT_PATH_BIAS_NOTICE_PCT 70
  if (options->PathBiasNoticeRate >= 0.0)
    return options->PathBiasNoticeRate;
  else
    return networkstatus_get_param(NULL, "pb_noticepct",
                                   DFLT_PATH_BIAS_NOTICE_PCT, 0, 100)/100.0;
}

/** 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;
}

/* XXXX I'd like to have this be static again, but entrynodes.c needs it. */
/**
 * The extreme rate is the rate at which we would drop the guard,
 * if pb_dropguard is also set. Otherwise we just warn.
 */
double
pathbias_get_extreme_rate(const or_options_t *options)
{
#define DFLT_PATH_BIAS_EXTREME_PCT 30
  if (options->PathBiasExtremeRate >= 0.0)
    return options->PathBiasExtremeRate;
  else
    return networkstatus_get_param(NULL, "pb_extremepct",
                                   DFLT_PATH_BIAS_EXTREME_PCT, 0, 100)/100.0;
}

/* XXXX I'd like to have this be static again, but entrynodes.c needs it. */
/**
 * If 1, we actually disable use of guards that fall below
 * the extreme_pct.
 */
int
pathbias_get_dropguards(const or_options_t *options)
{
#define DFLT_PATH_BIAS_DROP_GUARDS 0
  if (options->PathBiasDropGuards >= 0)
    return options->PathBiasDropGuards;
  else
    return networkstatus_get_param(NULL, "pb_dropguards",
                                   DFLT_PATH_BIAS_DROP_GUARDS, 0, 1);
}

/**
 * This is the number of circuits at which we scale our
 * counts by mult_factor/scale_factor. Note, this count is
 * not exact, as we only perform the scaling in the event
 * of no integer truncation.
 */
static int
pathbias_get_scale_threshold(const or_options_t *options)
{
#define DFLT_PATH_BIAS_SCALE_THRESHOLD 300
  if (options->PathBiasScaleThreshold >= 10)
    return options->PathBiasScaleThreshold;
  else
    return networkstatus_get_param(NULL, "pb_scalecircs",
                                   DFLT_PATH_BIAS_SCALE_THRESHOLD, 10,
                                   INT32_MAX);
}

/**
 * Compute the path bias scaling ratio from the consensus
 * parameters pb_multfactor/pb_scalefactor.
 *
 * Returns a value in (0, 1.0] which we multiply our pathbias
 * counts with to scale them down.
 */
static double
pathbias_get_scale_ratio(const or_options_t *options)
{
  (void) options;
  /*
   * The scale factor is the denominator for our scaling
   * of circuit counts for our path bias window.
   *
   * Note that our use of doubles for the path bias state
   * file means that powers of 2 work best here.
   */
  int denominator = networkstatus_get_param(NULL, "pb_scalefactor",
                              2, 2, INT32_MAX);
  tor_assert(denominator > 0);

  /**
   * The mult factor is the numerator for our scaling
   * of circuit counts for our path bias window. It
   * allows us to scale by fractions.
   */
  return networkstatus_get_param(NULL, "pb_multfactor",
                              1, 1, denominator)/((double)denominator);
}

/** The minimum number of circuit usage attempts before we start
  * thinking about warning about path use bias and dropping guards */
static int
pathbias_get_min_use(const or_options_t *options)
{
#define DFLT_PATH_BIAS_MIN_USE 20
  if (options->PathBiasUseThreshold >= 3)
    return options->PathBiasUseThreshold;
  else
    return networkstatus_get_param(NULL, "pb_minuse",
                                   DFLT_PATH_BIAS_MIN_USE,
                                   3, INT32_MAX);
}

/** The circuit use success rate below which we issue a notice */
static double
pathbias_get_notice_use_rate(const or_options_t *options)
{
#define DFLT_PATH_BIAS_NOTICE_USE_PCT 80
  if (options->PathBiasNoticeUseRate >= 0.0)
    return options->PathBiasNoticeUseRate;
  else
    return networkstatus_get_param(NULL, "pb_noticeusepct",
                                   DFLT_PATH_BIAS_NOTICE_USE_PCT,
                                   0, 100)/100.0;
}

/**
 * The extreme use rate is the rate at which we would drop the guard,
 * if pb_dropguard is also set. Otherwise we just warn.
 */
double
pathbias_get_extreme_use_rate(const or_options_t *options)
{
#define DFLT_PATH_BIAS_EXTREME_USE_PCT 60
  if (options->PathBiasExtremeUseRate >= 0.0)
    return options->PathBiasExtremeUseRate;
  else
    return networkstatus_get_param(NULL, "pb_extremeusepct",
                                   DFLT_PATH_BIAS_EXTREME_USE_PCT,
                                   0, 100)/100.0;
}

/**
 * This is the number of circuits at which we scale our
 * use counts by mult_factor/scale_factor. Note, this count is
 * not exact, as we only perform the scaling in the event
 * of no integer truncation.
 */
static int
pathbias_get_scale_use_threshold(const or_options_t *options)
{
#define DFLT_PATH_BIAS_SCALE_USE_THRESHOLD 100
  if (options->PathBiasScaleUseThreshold >= 10)
    return options->PathBiasScaleUseThreshold;
  else
    return networkstatus_get_param(NULL, "pb_scaleuse",
                                   DFLT_PATH_BIAS_SCALE_USE_THRESHOLD,
                                   10, INT32_MAX);
}

/**
 * Convert a Guard's path state to string.
 */
const char *
pathbias_state_to_string(path_state_t state)
{
  switch (state) {
    case PATH_STATE_NEW_CIRC:
      return "new";
    case PATH_STATE_BUILD_ATTEMPTED:
      return "build attempted";
    case PATH_STATE_BUILD_SUCCEEDED:
      return "build succeeded";
    case PATH_STATE_USE_ATTEMPTED:
      return "use attempted";
    case PATH_STATE_USE_SUCCEEDED:
      return "use succeeded";
    case PATH_STATE_USE_FAILED:
      return "use failed";
    case PATH_STATE_ALREADY_COUNTED:
      return "already counted";
  }

  return "unknown";
}

/**
 * This function decides if a circuit has progressed far enough to count
 * as a circuit "attempt". As long as end-to-end tagging is possible,
 * we assume the adversary will use it over hop-to-hop failure. Therefore,
 * we only need to account bias for the last hop. This should make us
 * much more resilient to ambient circuit failure, and also make that
 * failure easier to measure (we only need to measure Exit failure rates).
 */
static int
pathbias_is_new_circ_attempt(origin_circuit_t *circ)
{
#define N2N_TAGGING_IS_POSSIBLE
#ifdef N2N_TAGGING_IS_POSSIBLE
  /* cpath is a circular list. We want circs with more than one hop,
   * and the second hop must be waiting for keys still (it's just
   * about to get them). */
  return circ->cpath &&
         circ->cpath->next != circ->cpath &&
         circ->cpath->next->state == CPATH_STATE_AWAITING_KEYS;
#else /* !defined(N2N_TAGGING_IS_POSSIBLE) */
  /* If tagging attacks are no longer possible, we probably want to
   * count bias from the first hop. However, one could argue that
   * timing-based tagging is still more useful than per-hop failure.
   * In which case, we'd never want to use this.
   */
  return circ->cpath &&
         circ->cpath->state == CPATH_STATE_AWAITING_KEYS;
#endif /* defined(N2N_TAGGING_IS_POSSIBLE) */
}

/**
 * Decide if the path bias code should count a circuit.
 *
 * @returns 1 if we should count it, 0 otherwise.
 */
static int
pathbias_should_count(origin_circuit_t *circ)
{
#define PATHBIAS_COUNT_INTERVAL (600)
  static ratelim_t count_limit =
    RATELIM_INIT(PATHBIAS_COUNT_INTERVAL);
  char *rate_msg = NULL;

  /* We can't do path bias accounting without entry guards.
   * Testing and controller circuits also have no guards.
   *
   * We also don't count server-side rends, because their
   * endpoint could be chosen maliciously.
   * Similarly, we can't count client-side intro attempts,
   * because clients can be manipulated into connecting to
   * malicious intro points. */
  if (get_options()->UseEntryGuards == 0 ||
          circ->base_.purpose == CIRCUIT_PURPOSE_TESTING ||
          circ->base_.purpose == CIRCUIT_PURPOSE_CONTROLLER ||
          circ->base_.purpose == CIRCUIT_PURPOSE_S_CONNECT_REND ||
          circ->base_.purpose == CIRCUIT_PURPOSE_S_REND_JOINED ||
          (circ->base_.purpose >= CIRCUIT_PURPOSE_C_INTRODUCING &&
           circ->base_.purpose <= CIRCUIT_PURPOSE_C_INTRODUCE_ACKED)) {

    /* Check to see if the shouldcount result has changed due to a
     * unexpected purpose change that would affect our results.
     *
     * The reason we check the path state too here is because for the
     * cannibalized versions of these purposes, we count them as successful
     * before their purpose change.
     */
    if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_COUNTED
            && circ->path_state != PATH_STATE_ALREADY_COUNTED) {
      log_info(LD_BUG,
               "Circuit %d is now being ignored despite being counted "
               "in the past. Purpose is %s, path state is %s",
               circ->global_identifier,
               circuit_purpose_to_string(circ->base_.purpose),
               pathbias_state_to_string(circ->path_state));
    }
    circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_IGNORED;
    return 0;
  }

  /* Completely ignore one hop circuits */
  if (circ->build_state->onehop_tunnel ||
      circ->build_state->desired_path_len == 1) {
    /* Check for inconsistency */
    if (circ->build_state->desired_path_len != 1 ||
        !circ->build_state->onehop_tunnel) {
      if ((rate_msg = rate_limit_log(&count_limit, approx_time()))) {
        log_info(LD_BUG,
               "One-hop circuit %d has length %d. Path state is %s. "
               "Circuit is a %s currently %s.%s",
               circ->global_identifier,
               circ->build_state->desired_path_len,
               pathbias_state_to_string(circ->path_state),
               circuit_purpose_to_string(circ->base_.purpose),
               circuit_state_to_string(circ->base_.state),
               rate_msg);
        tor_free(rate_msg);
      }
      tor_fragile_assert();
    }

    /* Check to see if the shouldcount result has changed due to a
     * unexpected change that would affect our results */
    if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_COUNTED) {
      log_info(LD_BUG,
               "One-hop circuit %d is now being ignored despite being counted "
               "in the past. Purpose is %s, path state is %s",
               circ->global_identifier,
               circuit_purpose_to_string(circ->base_.purpose),
               pathbias_state_to_string(circ->path_state));
    }
    circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_IGNORED;
    return 0;
  }

  /* Check to see if the shouldcount result has changed due to a
   * unexpected purpose change that would affect our results */
  if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_IGNORED) {
    log_info(LD_CIRC,
            "Circuit %d is not being counted by pathbias because it was "
            "ignored in the past. Purpose is %s, path state is %s",
            circ->global_identifier,
            circuit_purpose_to_string(circ->base_.purpose),
            pathbias_state_to_string(circ->path_state));
    return 0;
  }
  circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_COUNTED;

  return 1;
}

/**
 * Check our circuit state to see if this is a successful circuit attempt.
 * If so, record it in the current guard's path bias circ_attempt count.
 *
 * Also check for several potential error cases for bug #6475.
 */
int
pathbias_count_build_attempt(origin_circuit_t *circ)
{
#define CIRC_ATTEMPT_NOTICE_INTERVAL (600)
  static ratelim_t circ_attempt_notice_limit =
    RATELIM_INIT(CIRC_ATTEMPT_NOTICE_INTERVAL);
  char *rate_msg = NULL;

  if (!pathbias_should_count(circ)) {
    return 0;
  }

  if (pathbias_is_new_circ_attempt(circ)) {
    /* Help track down the real cause of bug #6475: */
    if (circ->has_opened && circ->path_state != PATH_STATE_BUILD_ATTEMPTED) {
      if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
                                     approx_time()))) {
        log_info(LD_BUG,
                "Opened circuit %d is in strange path state %s. "
                "Circuit is a %s currently %s.%s",
                circ->global_identifier,
                pathbias_state_to_string(circ->path_state),
                circuit_purpose_to_string(circ->base_.purpose),
                circuit_state_to_string(circ->base_.state),
                rate_msg);
        tor_free(rate_msg);
      }
    }

    /* Don't re-count cannibalized circs.. */
    if (!circ->has_opened) {
      entry_guard_t *guard = NULL;

      if (circ->cpath && circ->cpath->extend_info) {
        guard = entry_guard_get_by_id_digest(
                  circ->cpath->extend_info->identity_digest);
      } else if (circ->base_.n_chan) {
        guard =
          entry_guard_get_by_id_digest(circ->base_.n_chan->identity_digest);
      }

      if (guard) {
        if (circ->path_state == PATH_STATE_NEW_CIRC) {
          circ->path_state = PATH_STATE_BUILD_ATTEMPTED;

          if (entry_guard_inc_circ_attempt_count(guard) < 0) {
            /* Bogus guard; we already warned. */
            return -END_CIRC_REASON_TORPROTOCOL;
          }
        } else {
          if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
                  approx_time()))) {
            log_info(LD_BUG,
                   "Unopened circuit %d has strange path state %s. "
                   "Circuit is a %s currently %s.%s",
                   circ->global_identifier,
                   pathbias_state_to_string(circ->path_state),
                   circuit_purpose_to_string(circ->base_.purpose),
                   circuit_state_to_string(circ->base_.state),
                   rate_msg);
            tor_free(rate_msg);
          }
        }
      } else {
        if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
                approx_time()))) {
          log_info(LD_CIRC,
              "Unopened circuit has no known guard. "
              "Circuit is a %s currently %s.%s",
              circuit_purpose_to_string(circ->base_.purpose),
              circuit_state_to_string(circ->base_.state),
              rate_msg);
          tor_free(rate_msg);
        }
      }
    }
  }

  return 0;
}

/**
 * Check our circuit state to see if this is a successful circuit
 * completion. If so, record it in the current guard's path bias
 * success count.
 *
 * Also check for several potential error cases for bug #6475.
 */
void
pathbias_count_build_success(origin_circuit_t *circ)
{
#define SUCCESS_NOTICE_INTERVAL (600)
  static ratelim_t success_notice_limit =
    RATELIM_INIT(SUCCESS_NOTICE_INTERVAL);
  char *rate_msg = NULL;
  entry_guard_t *guard = NULL;

  if (!pathbias_should_count(circ)) {
    return;
  }

  /* Don't count cannibalized/reused circs for path bias
   * "build" success, since they get counted under "use" success. */
  if (!circ->has_opened) {
    if (circ->cpath && circ->cpath->extend_info) {
      guard = entry_guard_get_by_id_digest(
                circ->cpath->extend_info->identity_digest);
    }

    if (guard) {
      guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);

      if (circ->path_state == PATH_STATE_BUILD_ATTEMPTED) {
        circ->path_state = PATH_STATE_BUILD_SUCCEEDED;
        pb->circ_successes++;
        entry_guards_changed();

        log_info(LD_CIRC, "Got success count %f/%f for guard %s",
                 pb->circ_successes, pb->circ_attempts,
                 entry_guard_describe(guard));
      } else {
        if ((rate_msg = rate_limit_log(&success_notice_limit,
                approx_time()))) {
          log_info(LD_BUG,
              "Succeeded circuit %d is in strange path state %s. "
              "Circuit is a %s currently %s.%s",
              circ->global_identifier,
              pathbias_state_to_string(circ->path_state),
              circuit_purpose_to_string(circ->base_.purpose),
              circuit_state_to_string(circ->base_.state),
              rate_msg);
          tor_free(rate_msg);
        }
      }

      if (pb->circ_attempts < pb->circ_successes) {
        log_notice(LD_BUG, "Unexpectedly high successes counts (%f/%f) "
                 "for guard %s",
                 pb->circ_successes, pb->circ_attempts,
                 entry_guard_describe(guard));
      }
    /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
     * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
     * No need to log that case. */
    } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
      if ((rate_msg = rate_limit_log(&success_notice_limit,
              approx_time()))) {
        log_info(LD_CIRC,
            "Completed circuit has no known guard. "
            "Circuit is a %s currently %s.%s",
            circuit_purpose_to_string(circ->base_.purpose),
            circuit_state_to_string(circ->base_.state),
            rate_msg);
        tor_free(rate_msg);
      }
    }
  } else {
    if (circ->path_state < PATH_STATE_BUILD_SUCCEEDED) {
      if ((rate_msg = rate_limit_log(&success_notice_limit,
              approx_time()))) {
        log_info(LD_BUG,
            "Opened circuit %d is in strange path state %s. "
            "Circuit is a %s currently %s.%s",
            circ->global_identifier,
            pathbias_state_to_string(circ->path_state),
            circuit_purpose_to_string(circ->base_.purpose),
            circuit_state_to_string(circ->base_.state),
            rate_msg);
        tor_free(rate_msg);
      }
    }
  }
}

/**
 * Record an attempt to use a circuit. Changes the circuit's
 * path state and update its guard's usage counter.
 *
 * Used for path bias usage accounting.
 */
void
pathbias_count_use_attempt(origin_circuit_t *circ)
{
  if (!pathbias_should_count(circ)) {
    return;
  }

  if (circ->path_state < PATH_STATE_BUILD_SUCCEEDED) {
    log_notice(LD_BUG,
        "Used circuit %d is in strange path state %s. "
        "Circuit is a %s currently %s.",
        circ->global_identifier,
        pathbias_state_to_string(circ->path_state),
        circuit_purpose_to_string(circ->base_.purpose),
        circuit_state_to_string(circ->base_.state));
  } else if (circ->path_state < PATH_STATE_USE_ATTEMPTED) {
    entry_guard_t *guard = entry_guard_get_by_id_digest(
                circ->cpath->extend_info->identity_digest);
    if (guard) {
      guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);

      pathbias_measure_use_rate(guard);
      pathbias_scale_use_rates(guard);
      pb->use_attempts++;
      entry_guards_changed();

      log_debug(LD_CIRC,
               "Marked circuit %d (%f/%f) as used for guard %s.",
               circ->global_identifier,
               pb->use_successes, pb->use_attempts,
               entry_guard_describe(guard));
    }

    circ->path_state = PATH_STATE_USE_ATTEMPTED;
  } else {
    /* Harmless but educational log message */
    log_info(LD_CIRC,
        "Used circuit %d is already in path state %s. "
        "Circuit is a %s currently %s.",
        circ->global_identifier,
        pathbias_state_to_string(circ->path_state),
        circuit_purpose_to_string(circ->base_.purpose),
        circuit_state_to_string(circ->base_.state));
  }

  return;
}

/**
 * Check the circuit's path state is appropriate and mark it as
 * successfully used. Used for path bias usage accounting.
 *
 * We don't actually increment the guard's counters until
 * pathbias_check_close(), because the circuit can still transition
 * back to PATH_STATE_USE_ATTEMPTED if a stream fails later (this
 * is done so we can probe the circuit for liveness at close).
 */
void
pathbias_mark_use_success(origin_circuit_t *circ)
{
  if (!pathbias_should_count(circ)) {
    return;
  }

  if (circ->path_state < PATH_STATE_USE_ATTEMPTED) {
    log_notice(LD_BUG,
        "Used circuit %d is in strange path state %s. "
        "Circuit is a %s currently %s.",
        circ->global_identifier,
        pathbias_state_to_string(circ->path_state),
        circuit_purpose_to_string(circ->base_.purpose),
        circuit_state_to_string(circ->base_.state));

    pathbias_count_use_attempt(circ);
  }

  /* We don't do any accounting at the guard until actual circuit close */
  circ->path_state = PATH_STATE_USE_SUCCEEDED;

  return;
}

/**
 * If a stream ever detatches from a circuit in a retriable way,
 * we need to mark this circuit as still needing either another
 * successful stream, or in need of a probe.
 *
 * An adversary could let the first stream request succeed (ie the
 * resolve), but then tag and timeout the remainder (via cell
 * dropping), forcing them on new circuits.
 *
 * Rolling back the state will cause us to probe such circuits, which
 * should lead to probe failures in the event of such tagging due to
 * either unrecognized cells coming in while we wait for the probe,
 * or the cipher state getting out of sync in the case of dropped cells.
 */
void
pathbias_mark_use_rollback(origin_circuit_t *circ)
{
  if (circ->path_state == PATH_STATE_USE_SUCCEEDED) {
    log_info(LD_CIRC,
             "Rolling back pathbias use state to 'attempted' for detached "
             "circuit %d", circ->global_identifier);
    circ->path_state = PATH_STATE_USE_ATTEMPTED;
  }
}

/**
 * Actually count a circuit success towards a guard's usage counters
 * if the path state is appropriate.
 */
static void
pathbias_count_use_success(origin_circuit_t *circ)
{
  entry_guard_t *guard;

  if (!pathbias_should_count(circ)) {
    return;
  }

  if (circ->path_state != PATH_STATE_USE_SUCCEEDED) {
    log_notice(LD_BUG,
        "Successfully used circuit %d is in strange path state %s. "
        "Circuit is a %s currently %s.",
        circ->global_identifier,
        pathbias_state_to_string(circ->path_state),
        circuit_purpose_to_string(circ->base_.purpose),
        circuit_state_to_string(circ->base_.state));
  } else {
    guard = entry_guard_get_by_id_digest(
                circ->cpath->extend_info->identity_digest);
    if (guard) {
      guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);

      pb->use_successes++;
      entry_guards_changed();

      if (pb->use_attempts < pb->use_successes) {
        log_notice(LD_BUG, "Unexpectedly high use successes counts (%f/%f) "
                 "for guard %s",
                 pb->use_successes, pb->use_attempts,
                 entry_guard_describe(guard));
      }

      log_debug(LD_CIRC,
                "Marked circuit %d (%f/%f) as used successfully for guard %s",
                circ->global_identifier, pb->use_successes,
                pb->use_attempts,
                entry_guard_describe(guard));
    }
  }

  return;
}

/**
 * Send a probe down a circuit that the client attempted to use,
 * but for which the stream timed out/failed. The probe is a
 * RELAY_BEGIN cell with a 0.a.b.c destination address, which
 * the exit will reject and reply back, echoing that address.
 *
 * The reason for such probes is because it is possible to bias
 * a user's paths simply by causing timeouts, and these timeouts
 * are not possible to differentiate from unresponsive servers.
 *
 * The probe is sent at the end of the circuit lifetime for two
 * reasons: to prevent cryptographic taggers from being able to
 * drop cells to cause timeouts, and to prevent easy recognition
 * of probes before any real client traffic happens.
 *
 * Returns -1 if we couldn't probe, 0 otherwise.
 */
static int
pathbias_send_usable_probe(circuit_t *circ)
{
  /* Based on connection_ap_handshake_send_begin() */
  char payload[CELL_PAYLOAD_SIZE];
  int payload_len;
  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
  crypt_path_t *cpath_layer = NULL;
  char *probe_nonce = NULL;

  tor_assert(ocirc);

  cpath_layer = ocirc->cpath->prev;

  if (cpath_layer->state != CPATH_STATE_OPEN) {
    /* This can happen for cannibalized circuits. Their
     * last hop isn't yet open */
    log_info(LD_CIRC,
             "Got pathbias probe request for unopened circuit %d. "
             "Opened %d, len %d", ocirc->global_identifier,
             ocirc->has_opened, ocirc->build_state->desired_path_len);
    return -1;
  }

  /* We already went down this road. */
  if (circ->purpose == CIRCUIT_PURPOSE_PATH_BIAS_TESTING &&
      ocirc->pathbias_probe_id) {
    log_info(LD_CIRC,
             "Got pathbias probe request for circuit %d with "
             "outstanding probe", ocirc->global_identifier);
    return -1;
  }

  /* Can't probe if the channel isn't open */
  if (circ->n_chan == NULL ||
      (!CHANNEL_IS_OPEN(circ->n_chan)
       && !CHANNEL_IS_MAINT(circ->n_chan))) {
    log_info(LD_CIRC,
             "Skipping pathbias probe for circuit %d: Channel is not open.",
             ocirc->global_identifier);
    return -1;
  }

  circuit_change_purpose(circ, CIRCUIT_PURPOSE_PATH_BIAS_TESTING);

  /* Update timestamp for when circuit_expire_building() should kill us */
  tor_gettimeofday(&circ->timestamp_began);

  /* Generate a random address for the nonce */
  crypto_rand((char*)&ocirc->pathbias_probe_nonce,
              sizeof(ocirc->pathbias_probe_nonce));
  ocirc->pathbias_probe_nonce &= 0x00ffffff;
  probe_nonce = tor_dup_ip(ocirc->pathbias_probe_nonce);

  if (!probe_nonce) {
    log_err(LD_BUG, "Failed to generate nonce");
    return -1;
  }

  tor_snprintf(payload,RELAY_PAYLOAD_SIZE, "%s:25", probe_nonce);
  payload_len = (int)strlen(payload)+1;

  // XXX: need this? Can we assume ipv4 will always be supported?
  // If not, how do we tell?
  //if (payload_len <= RELAY_PAYLOAD_SIZE - 4 && edge_conn->begincell_flags) {
  //  set_uint32(payload + payload_len, htonl(edge_conn->begincell_flags));
  //  payload_len += 4;
  //}

  /* Generate+Store stream id, make sure it's non-zero */
  ocirc->pathbias_probe_id = get_unique_stream_id_by_circ(ocirc);

  if (ocirc->pathbias_probe_id==0) {
    log_warn(LD_CIRC,
             "Ran out of stream IDs on circuit %u during "
             "pathbias probe attempt.", ocirc->global_identifier);
    tor_free(probe_nonce);
    return -1;
  }

  log_info(LD_CIRC,
           "Sending pathbias testing cell to %s:25 on stream %d for circ %d.",
           probe_nonce, ocirc->pathbias_probe_id, ocirc->global_identifier);
  tor_free(probe_nonce);

  /* Send a test relay cell */
  if (relay_send_command_from_edge(ocirc->pathbias_probe_id, circ,
                               RELAY_COMMAND_BEGIN, payload,
                               payload_len, cpath_layer) < 0) {
    log_notice(LD_CIRC,
               "Failed to send pathbias probe cell on circuit %d.",
               ocirc->global_identifier);
    return -1;
  }

  /* Mark it freshly dirty so it doesn't get expired in the meantime */
  circ->timestamp_dirty = time(NULL);

  return 0;
}

/**
 * Check the response to a pathbias probe, to ensure the
 * cell is recognized and the nonce and other probe
 * characteristics are as expected.
 *
 * If the response is valid, return 0. Otherwise return < 0.
 */
int
pathbias_check_probe_response(circuit_t *circ, const cell_t *cell)
{
  /* Based on connection_edge_process_relay_cell() */
  relay_header_t rh;
  int reason;
  uint32_t ipv4_host;
  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);

  tor_assert(cell);
  tor_assert(ocirc);
  tor_assert(circ->purpose == CIRCUIT_PURPOSE_PATH_BIAS_TESTING);

  relay_header_unpack(&rh, cell->payload);

  reason = rh.length > 0 ?
        get_uint8(cell->payload+RELAY_HEADER_SIZE) : END_STREAM_REASON_MISC;

  if (rh.command == RELAY_COMMAND_END &&
      reason == END_STREAM_REASON_EXITPOLICY &&
      ocirc->pathbias_probe_id == rh.stream_id) {

    /* Check length+extract host: It is in network order after the reason code.
     * See connection_edge_end(). */
    if (rh.length < 9) { /* reason+ipv4+dns_ttl */
      log_notice(LD_PROTOCOL,
             "Short path bias probe response length field (%d).", rh.length);
      return - END_CIRC_REASON_TORPROTOCOL;
    }

    ipv4_host = ntohl(get_uint32(cell->payload+RELAY_HEADER_SIZE+1));

    /* Check nonce */
    if (ipv4_host == ocirc->pathbias_probe_nonce) {
      pathbias_mark_use_success(ocirc);
      circuit_read_valid_data(ocirc, rh.length);
      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 cell is counts as valid data for a circuit,
 * and if so, count it as valid.
 */
void
pathbias_count_valid_cells(circuit_t *circ, const cell_t *cell)
{
  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
  relay_header_t rh;

  relay_header_unpack(&rh, cell->payload);

  /* Check to see if this is a cell from a previous connection,
   * or is a request to close the circuit. */
  switch (rh.command) {
    case RELAY_COMMAND_TRUNCATED:
      /* Truncated cells can arrive on path bias circs. When they do,
       * just process them. This closes the circ, but it was junk anyway.
       * No reason to wait for the probe. */
      circuit_read_valid_data(ocirc, rh.length);
      circuit_truncated(TO_ORIGIN_CIRCUIT(circ),
                        get_uint8(cell->payload + RELAY_HEADER_SIZE));

      break;

    case RELAY_COMMAND_END:
      if (connection_half_edge_is_valid_end(ocirc->half_streams,
                                             rh.stream_id)) {
        circuit_read_valid_data(TO_ORIGIN_CIRCUIT(circ), rh.length);
      }
      break;

    case RELAY_COMMAND_DATA:
      if (connection_half_edge_is_valid_data(ocirc->half_streams,
                                             rh.stream_id)) {
        circuit_read_valid_data(TO_ORIGIN_CIRCUIT(circ), rh.length);
      }
      break;

    case RELAY_COMMAND_SENDME:
      if (connection_half_edge_is_valid_sendme(ocirc->half_streams,
                                             rh.stream_id)) {
        circuit_read_valid_data(TO_ORIGIN_CIRCUIT(circ), rh.length);
      }
      break;

    case RELAY_COMMAND_CONNECTED:
      if (connection_half_edge_is_valid_connected(ocirc->half_streams,
                                                  rh.stream_id)) {
        circuit_read_valid_data(TO_ORIGIN_CIRCUIT(circ), rh.length);
      }
      break;

    case RELAY_COMMAND_RESOLVED:
      if (connection_half_edge_is_valid_resolved(ocirc->half_streams,
                                                 rh.stream_id)) {
        circuit_read_valid_data(TO_ORIGIN_CIRCUIT(circ), rh.length);
      }
      break;
  }
}

/**
 * Check if a circuit was used and/or closed successfully.
 *
 * If we attempted to use the circuit to carry a stream but failed
 * for whatever reason, or if the circuit mysteriously died before
 * we could attach any streams, record these two cases.
 *
 * If we *have* successfully used the circuit, or it appears to
 * have been closed by us locally, count it as a success.
 *
 * Returns 0 if we're done making decisions with the circ,
 * or -1 if we want to probe it first.
 */
int
pathbias_check_close(origin_circuit_t *ocirc, int reason)
{
  circuit_t *circ = &ocirc->base_;

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

  switch (ocirc->path_state) {
    /* If the circuit was closed after building, but before use, we need
     * to ensure we were the ones who tried to close it (and not a remote
     * actor). */
    case PATH_STATE_BUILD_SUCCEEDED:
      if (reason & END_CIRC_REASON_FLAG_REMOTE) {
        /* Remote circ close reasons on an unused circuit all could be bias */
        log_info(LD_CIRC,
            "Circuit %d remote-closed without successful use for reason %d. "
            "Circuit purpose %d currently %d,%s. Len %d.",
            ocirc->global_identifier,
            reason, circ->purpose, ocirc->has_opened,
            circuit_state_to_string(circ->state),
            ocirc->build_state->desired_path_len);
        pathbias_count_collapse(ocirc);
      } else if ((reason & ~END_CIRC_REASON_FLAG_REMOTE)
                  == END_CIRC_REASON_CHANNEL_CLOSED &&
                 circ->n_chan &&
                 circ->n_chan->reason_for_closing
                  != CHANNEL_CLOSE_REQUESTED) {
        /* If we didn't close the channel ourselves, it could be bias */
        /* XXX: Only count bias if the network is live?
         * What about clock jumps/suspends? */
        log_info(LD_CIRC,
            "Circuit %d's channel closed without successful use for reason "
            "%d, channel reason %d. Circuit purpose %d currently %d,%s. Len "
            "%d.", ocirc->global_identifier,
            reason, circ->n_chan->reason_for_closing,
            circ->purpose, ocirc->has_opened,
            circuit_state_to_string(circ->state),
            ocirc->build_state->desired_path_len);
        pathbias_count_collapse(ocirc);
      } else {
        pathbias_count_successful_close(ocirc);
      }
      break;

    /* If we tried to use a circuit but failed, we should probe it to ensure
     * it has not been tampered with. */
    case PATH_STATE_USE_ATTEMPTED:
      /* XXX: Only probe and/or count failure if the network is live?
       * What about clock jumps/suspends? */
      if (pathbias_send_usable_probe(circ) == 0)
        return -1;
      else
        pathbias_count_use_failed(ocirc);

      /* Any circuit where there were attempted streams but no successful
       * streams could be bias */
      log_info(LD_CIRC,
            "Circuit %d closed without successful use for reason %d. "
            "Circuit purpose %d currently %d,%s. Len %d.",
            ocirc->global_identifier,
            reason, circ->purpose, ocirc->has_opened,
            circuit_state_to_string(circ->state),
            ocirc->build_state->desired_path_len);
      break;

    case PATH_STATE_USE_SUCCEEDED:
      pathbias_count_successful_close(ocirc);
      pathbias_count_use_success(ocirc);
      break;

    case PATH_STATE_USE_FAILED:
      pathbias_count_use_failed(ocirc);
      break;

    case PATH_STATE_NEW_CIRC:
    case PATH_STATE_BUILD_ATTEMPTED:
    case PATH_STATE_ALREADY_COUNTED:
    default:
      // Other states are uninteresting. No stats to count.
      break;
  }

  ocirc->path_state = PATH_STATE_ALREADY_COUNTED;

  return 0;
}

/**
 * Count a successfully closed circuit.
 */
static void
pathbias_count_successful_close(origin_circuit_t *circ)
{
  entry_guard_t *guard = NULL;
  if (!pathbias_should_count(circ)) {
    return;
  }

  if (circ->cpath && circ->cpath->extend_info) {
    guard = entry_guard_get_by_id_digest(
              circ->cpath->extend_info->identity_digest);
  }

  if (guard) {
    guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);

    /* In the long run: circuit_success ~= successful_circuit_close +
     *                                     circ_failure + stream_failure */
    pb->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_pathbias_t *pb = entry_guard_get_pathbias_state(guard);

    pb->collapsed_circuits++;
    entry_guards_changed();
  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
   /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
    * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
    * No need to log that case. */
    log_info(LD_CIRC,
        "Destroyed circuit has no known guard. "
        "Circuit is a %s currently %s",
        circuit_purpose_to_string(circ->base_.purpose),
        circuit_state_to_string(circ->base_.state));
  }
}

/**
 * Count a known failed circuit (because we could not probe it).
 *
 * This counter is informational.
 */
static void
pathbias_count_use_failed(origin_circuit_t *circ)
{
  entry_guard_t *guard = NULL;
  if (!pathbias_should_count(circ)) {
    return;
  }

  if (circ->cpath && circ->cpath->extend_info) {
    guard = entry_guard_get_by_id_digest(
              circ->cpath->extend_info->identity_digest);
  }

  if (guard) {
    guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);

    pb->unusable_circuits++;
    entry_guards_changed();
  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
   /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
    * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
    * No need to log that case. */
    /* XXX note cut-and-paste code in this function compared to nearby
     * functions. Would be nice to refactor. -RD */
    log_info(LD_CIRC,
        "Stream-failing circuit has no known guard. "
        "Circuit is a %s currently %s",
        circuit_purpose_to_string(circ->base_.purpose),
        circuit_state_to_string(circ->base_.state));
  }
}

/**
 * Count timeouts for path bias log messages.
 *
 * These counts are purely informational.
 */
void
pathbias_count_timeout(origin_circuit_t *circ)
{
  entry_guard_t *guard = NULL;

  if (!pathbias_should_count(circ)) {
    return;
  }

  /* For hidden service circs, they can actually be used
   * successfully and then time out later (because
   * the other side declines to use them). */
  if (circ->path_state == PATH_STATE_USE_SUCCEEDED) {
    return;
  }

  if (circ->cpath && circ->cpath->extend_info) {
    guard = entry_guard_get_by_id_digest(
              circ->cpath->extend_info->identity_digest);
  }

  if (guard) {
    guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);

    pb->timeouts++;
    entry_guards_changed();
  }
}

/**
 * Helper function to count all of the currently opened circuits
 * for a guard that are in a given path state range. The state
 * range is inclusive on both ends.
 */
static int
pathbias_count_circs_in_states(entry_guard_t *guard,
                              path_state_t from,
                              path_state_t to)
{
  int open_circuits = 0;

  /* Count currently open circuits. Give them the benefit of the doubt. */
  SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
    origin_circuit_t *ocirc = NULL;
    if (!CIRCUIT_IS_ORIGIN(circ) || /* didn't originate here */
        circ->marked_for_close) /* already counted */
      continue;

    ocirc = TO_ORIGIN_CIRCUIT(circ);

    if (!ocirc->cpath || !ocirc->cpath->extend_info)
      continue;

    if (ocirc->path_state >= from &&
        ocirc->path_state <= to &&
        pathbias_should_count(ocirc) &&
        fast_memeq(entry_guard_get_rsa_id_digest(guard),
                   ocirc->cpath->extend_info->identity_digest,
                   DIGEST_LEN)) {
      log_debug(LD_CIRC, "Found opened circuit %d in path_state %s",
                ocirc->global_identifier,
                pathbias_state_to_string(ocirc->path_state));
      open_circuits++;
    }
  }
  SMARTLIST_FOREACH_END(circ);

  return open_circuits;
}

/**
 * Return the number of circuits counted as successfully closed for
 * this guard.
 *
 * Also add in the currently open circuits to give them the benefit
 * of the doubt.
 */
double
pathbias_get_close_success_count(entry_guard_t *guard)
{
  guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);

  return pb->successful_circuits_closed +
         pathbias_count_circs_in_states(guard,
                       PATH_STATE_BUILD_SUCCEEDED,
                       PATH_STATE_USE_SUCCEEDED);
}

/**
 * Return the number of circuits counted as successfully used
 * this guard.
 *
 * Also add in the currently open circuits that we are attempting
 * to use to give them the benefit of the doubt.
 */
double
pathbias_get_use_success_count(entry_guard_t *guard)
{
  guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);

  return pb->use_successes +
         pathbias_count_circs_in_states(guard,
                       PATH_STATE_USE_ATTEMPTED,
                       PATH_STATE_USE_SUCCEEDED);
}

/**
 * Check the path bias use rate against our consensus parameter limits.
 *
 * Emits a log message if the use success rates are too low.
 *
 * If pathbias_get_dropguards() is set, we also disable the use of
 * very failure prone guards.
 */
static void
pathbias_measure_use_rate(entry_guard_t *guard)
{
  const or_options_t *options = get_options();
  guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);

  if (pb->use_attempts > pathbias_get_min_use(options)) {
    /* Note: We rely on the < comparison here to allow us to set a 0
     * rate and disable the feature entirely. If refactoring, don't
     * change to <= */
    if (pathbias_get_use_success_count(guard)/pb->use_attempts
        < pathbias_get_extreme_use_rate(options)) {
      /* Dropping is currently disabled by default. */
      if (pathbias_get_dropguards(options)) {
        if (!pb->path_bias_disabled) {
          log_warn(LD_CIRC,
                 "Guard %s is failing to carry an extremely large "
                 "amount of stream on its circuits. "
                 "To avoid potential route manipulation attacks, Tor has "
                 "disabled use of this guard. "
                 "Use counts are %ld/%ld. Success counts are %ld/%ld. "
                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
                 "and %ld timed out. "
                 "For reference, your timeout cutoff is %ld seconds.",
                 entry_guard_describe(guard),
                 tor_lround(pathbias_get_use_success_count(guard)),
                 tor_lround(pb->use_attempts),
                 tor_lround(pathbias_get_close_success_count(guard)),
                 tor_lround(pb->circ_attempts),
                 tor_lround(pb->circ_successes),
                 tor_lround(pb->unusable_circuits),
                 tor_lround(pb->collapsed_circuits),
                 tor_lround(pb->timeouts),
                 tor_lround(get_circuit_build_close_time_ms()/1000));
          pb->path_bias_disabled = 1;
          return;
        }
      } else if (!pb->path_bias_use_extreme) {
        pb->path_bias_use_extreme = 1;
        log_warn(LD_CIRC,
                 "Guard %s is failing to carry an extremely large "
                 "amount of streams on its circuits. "
                 "This could indicate a route manipulation attack, network "
                 "overload, bad local network connectivity, or a bug. "
                 "Use counts are %ld/%ld. Success counts are %ld/%ld. "
                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
                 "and %ld timed out. "
                 "For reference, your timeout cutoff is %ld seconds.",
                 entry_guard_describe(guard),
                 tor_lround(pathbias_get_use_success_count(guard)),
                 tor_lround(pb->use_attempts),
                 tor_lround(pathbias_get_close_success_count(guard)),
                 tor_lround(pb->circ_attempts),
                 tor_lround(pb->circ_successes),
                 tor_lround(pb->unusable_circuits),
                 tor_lround(pb->collapsed_circuits),
                 tor_lround(pb->timeouts),
                 tor_lround(get_circuit_build_close_time_ms()/1000));
      }
    } else if (pathbias_get_use_success_count(guard)/pb->use_attempts
               < pathbias_get_notice_use_rate(options)) {
      if (!pb->path_bias_use_noticed) {
        pb->path_bias_use_noticed = 1;
        log_notice(LD_CIRC,
                 "Guard %s is failing to carry more streams on its "
                 "circuits than usual. "
                 "Most likely this means the Tor network is overloaded "
                 "or your network connection is poor. "
                 "Use counts are %ld/%ld. Success counts are %ld/%ld. "
                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
                 "and %ld timed out. "
                 "For reference, your timeout cutoff is %ld seconds.",
                 entry_guard_describe(guard),
                 tor_lround(pathbias_get_use_success_count(guard)),
                 tor_lround(pb->use_attempts),
                 tor_lround(pathbias_get_close_success_count(guard)),
                 tor_lround(pb->circ_attempts),
                 tor_lround(pb->circ_successes),
                 tor_lround(pb->unusable_circuits),
                 tor_lround(pb->collapsed_circuits),
                 tor_lround(pb->timeouts),
                 tor_lround(get_circuit_build_close_time_ms()/1000));
      }
    }
  }
}

/**
 * Check the path bias circuit close status rates against our consensus
 * parameter limits.
 *
 * Emits a log message if the use success rates are too low.
 *
 * If pathbias_get_dropguards() is set, we also disable the use of
 * very failure prone guards.
 *
 * XXX: This function shares similar log messages and checks to
 * pathbias_measure_use_rate(). It may be possible to combine them
 * eventually, especially if we can ever remove the need for 3
 * levels of closure warns (if the overall circuit failure rate
 * goes down with ntor). One way to do so would be to multiply
 * the build rate with the use rate to get an idea of the total
 * fraction of the total network paths the user is able to use.
 * See ticket #8159.
 */
static void
pathbias_measure_close_rate(entry_guard_t *guard)
{
  const or_options_t *options = get_options();
  guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);

  if (pb->circ_attempts > pathbias_get_min_circs(options)) {
    /* Note: We rely on the < comparison here to allow us to set a 0
     * rate and disable the feature entirely. If refactoring, don't
     * change to <= */
    if (pathbias_get_close_success_count(guard)/pb->circ_attempts
        < pathbias_get_extreme_rate(options)) {
      /* Dropping is currently disabled by default. */
      if (pathbias_get_dropguards(options)) {
        if (!pb->path_bias_disabled) {
          log_warn(LD_CIRC,
                 "Guard %s is failing an extremely large "
                 "amount of circuits. "
                 "To avoid potential route manipulation attacks, Tor has "
                 "disabled use of this guard. "
                 "Success counts are %ld/%ld. Use counts are %ld/%ld. "
                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
                 "and %ld timed out. "
                 "For reference, your timeout cutoff is %ld seconds.",
                 entry_guard_describe(guard),
                 tor_lround(pathbias_get_close_success_count(guard)),
                 tor_lround(pb->circ_attempts),
                 tor_lround(pathbias_get_use_success_count(guard)),
                 tor_lround(pb->use_attempts),
                 tor_lround(pb->circ_successes),
                 tor_lround(pb->unusable_circuits),
                 tor_lround(pb->collapsed_circuits),
                 tor_lround(pb->timeouts),
                 tor_lround(get_circuit_build_close_time_ms()/1000));
          pb->path_bias_disabled = 1;
          return;
        }
      } else if (!pb->path_bias_extreme) {
        pb->path_bias_extreme = 1;
        log_warn(LD_CIRC,
                 "Guard %s is failing an extremely large "
                 "amount of circuits. "
                 "This could indicate a route manipulation attack, "
                 "extreme network overload, or a bug. "
                 "Success counts are %ld/%ld. Use counts are %ld/%ld. "
                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
                 "and %ld timed out. "
                 "For reference, your timeout cutoff is %ld seconds.",
                 entry_guard_describe(guard),
                 tor_lround(pathbias_get_close_success_count(guard)),
                 tor_lround(pb->circ_attempts),
                 tor_lround(pathbias_get_use_success_count(guard)),
                 tor_lround(pb->use_attempts),
                 tor_lround(pb->circ_successes),
                 tor_lround(pb->unusable_circuits),
                 tor_lround(pb->collapsed_circuits),
                 tor_lround(pb->timeouts),
                 tor_lround(get_circuit_build_close_time_ms()/1000));
      }
    } else if (pathbias_get_close_success_count(guard)/pb->circ_attempts
                < pathbias_get_warn_rate(options)) {
      if (!pb->path_bias_warned) {
        pb->path_bias_warned = 1;
        log_warn(LD_CIRC,
                 "Guard %s is failing a very large "
                 "amount of circuits. "
                 "Most likely this means the Tor network is "
                 "overloaded, but it could also mean an attack against "
                 "you or potentially the guard itself. "
                 "Success counts are %ld/%ld. Use counts are %ld/%ld. "
                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
                 "and %ld timed out. "
                 "For reference, your timeout cutoff is %ld seconds.",
                 entry_guard_describe(guard),
                 tor_lround(pathbias_get_close_success_count(guard)),
                 tor_lround(pb->circ_attempts),
                 tor_lround(pathbias_get_use_success_count(guard)),
                 tor_lround(pb->use_attempts),
                 tor_lround(pb->circ_successes),
                 tor_lround(pb->unusable_circuits),
                 tor_lround(pb->collapsed_circuits),
                 tor_lround(pb->timeouts),
                 tor_lround(get_circuit_build_close_time_ms()/1000));
      }
    } else if (pathbias_get_close_success_count(guard)/pb->circ_attempts
               < pathbias_get_notice_rate(options)) {
      if (!pb->path_bias_noticed) {
        pb->path_bias_noticed = 1;
        log_notice(LD_CIRC,
                 "Guard %s is failing more circuits than "
                 "usual. "
                 "Most likely this means the Tor network is overloaded. "
                 "Success counts are %ld/%ld. Use counts are %ld/%ld. "
                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
                 "and %ld timed out. "
                 "For reference, your timeout cutoff is %ld seconds.",
                 entry_guard_describe(guard),
                 tor_lround(pathbias_get_close_success_count(guard)),
                 tor_lround(pb->circ_attempts),
                 tor_lround(pathbias_get_use_success_count(guard)),
                 tor_lround(pb->use_attempts),
                 tor_lround(pb->circ_successes),
                 tor_lround(pb->unusable_circuits),
                 tor_lround(pb->collapsed_circuits),
                 tor_lround(pb->timeouts),
                 tor_lround(get_circuit_build_close_time_ms()/1000));
      }
    }
  }
}

/**
 * This function scales the path bias use rates if we have
 * more data than the scaling threshold. This allows us to
 * be more sensitive to recent measurements.
 *
 * XXX: The attempt count transfer stuff here might be done
 * better by keeping separate pending counters that get
 * transferred at circuit close. See ticket #8160.
 */
static void
pathbias_scale_close_rates(entry_guard_t *guard)
{
  const or_options_t *options = get_options();
  guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);

  /* If we get a ton of circuits, just scale everything down */
  if (pb->circ_attempts > pathbias_get_scale_threshold(options)) {
    double scale_ratio = pathbias_get_scale_ratio(options);
    int opened_attempts = pathbias_count_circs_in_states(guard,
            PATH_STATE_BUILD_ATTEMPTED, PATH_STATE_BUILD_ATTEMPTED);
    int opened_built = pathbias_count_circs_in_states(guard,
                        PATH_STATE_BUILD_SUCCEEDED,
                        PATH_STATE_USE_FAILED);
    /* Verify that the counts are sane before and after scaling */
    int counts_are_sane = (pb->circ_attempts >= pb->circ_successes);

    pb->circ_attempts -= (opened_attempts+opened_built);
    pb->circ_successes -= opened_built;

    pb->circ_attempts *= scale_ratio;
    pb->circ_successes *= scale_ratio;
    pb->timeouts *= scale_ratio;
    pb->successful_circuits_closed *= scale_ratio;
    pb->collapsed_circuits *= scale_ratio;
    pb->unusable_circuits *= scale_ratio;

    pb->circ_attempts += (opened_attempts+opened_built);
    pb->circ_successes += opened_built;

    entry_guards_changed();

    log_info(LD_CIRC,
             "Scaled pathbias counts to (%f,%f)/%f (%d/%d open) for guard "
             "%s",
             pb->circ_successes, pb->successful_circuits_closed,
             pb->circ_attempts, opened_built, opened_attempts,
             entry_guard_describe(guard));

    /* Have the counts just become invalid by this scaling attempt? */
    if (counts_are_sane && pb->circ_attempts < pb->circ_successes) {
      log_notice(LD_BUG,
               "Scaling has mangled pathbias counts to %f/%f (%d/%d open) "
               "for guard %s",
               pb->circ_successes, pb->circ_attempts, opened_built,
               opened_attempts,
               entry_guard_describe(guard));
    }
  }
}

/**
 * This function scales the path bias circuit close rates if we have
 * more data than the scaling threshold. This allows us to be more
 * sensitive to recent measurements.
 *
 * XXX: The attempt count transfer stuff here might be done
 * better by keeping separate pending counters that get
 * transferred at circuit close. See ticket #8160.
 */
void
pathbias_scale_use_rates(entry_guard_t *guard)
{
  const or_options_t *options = get_options();
  guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);

  /* If we get a ton of circuits, just scale everything down */
  if (pb->use_attempts > pathbias_get_scale_use_threshold(options)) {
    double scale_ratio = pathbias_get_scale_ratio(options);
    int opened_attempts = pathbias_count_circs_in_states(guard,
            PATH_STATE_USE_ATTEMPTED, PATH_STATE_USE_SUCCEEDED);
    /* Verify that the counts are sane before and after scaling */
    int counts_are_sane = (pb->use_attempts >= pb->use_successes);

    pb->use_attempts -= opened_attempts;

    pb->use_attempts *= scale_ratio;
    pb->use_successes *= scale_ratio;

    pb->use_attempts += opened_attempts;

    log_info(LD_CIRC,
           "Scaled pathbias use counts to %f/%f (%d open) for guard %s",
           pb->use_successes, pb->use_attempts, opened_attempts,
           entry_guard_describe(guard));

    /* Have the counts just become invalid by this scaling attempt? */
    if (counts_are_sane && pb->use_attempts < pb->use_successes) {
      log_notice(LD_BUG,
               "Scaling has mangled pathbias usage counts to %f/%f "
               "(%d open) for guard %s",
               pb->circ_successes, pb->circ_attempts,
               opened_attempts, entry_guard_describe(guard));
    }

    entry_guards_changed();
  }
}