tor  0.4.1.0-alpha-dev
Macros | Functions
circpathbias.c File Reference
#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"

Go to the source code of this file.

Macros

#define DFLT_PATH_BIAS_MIN_CIRC   150
 
#define DFLT_PATH_BIAS_NOTICE_PCT   70
 
#define DFLT_PATH_BIAS_WARN_PCT   50
 
#define DFLT_PATH_BIAS_EXTREME_PCT   30
 
#define DFLT_PATH_BIAS_DROP_GUARDS   0
 
#define DFLT_PATH_BIAS_SCALE_THRESHOLD   300
 
#define DFLT_PATH_BIAS_MIN_USE   20
 
#define DFLT_PATH_BIAS_NOTICE_USE_PCT   80
 
#define DFLT_PATH_BIAS_EXTREME_USE_PCT   60
 
#define DFLT_PATH_BIAS_SCALE_USE_THRESHOLD   100
 
#define N2N_TAGGING_IS_POSSIBLE
 
#define PATHBIAS_COUNT_INTERVAL   (600)
 
#define CIRC_ATTEMPT_NOTICE_INTERVAL   (600)
 
#define SUCCESS_NOTICE_INTERVAL   (600)
 

Functions

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)
 
static int pathbias_get_min_circs (const or_options_t *options)
 
static double pathbias_get_notice_rate (const or_options_t *options)
 
static double pathbias_get_warn_rate (const or_options_t *options)
 
double pathbias_get_extreme_rate (const or_options_t *options)
 
int pathbias_get_dropguards (const or_options_t *options)
 
static int pathbias_get_scale_threshold (const or_options_t *options)
 
static double pathbias_get_scale_ratio (const or_options_t *options)
 
static int pathbias_get_min_use (const or_options_t *options)
 
static double pathbias_get_notice_use_rate (const or_options_t *options)
 
double pathbias_get_extreme_use_rate (const or_options_t *options)
 
static int pathbias_get_scale_use_threshold (const or_options_t *options)
 
const char * pathbias_state_to_string (path_state_t state)
 
static int pathbias_is_new_circ_attempt (origin_circuit_t *circ)
 
static int pathbias_should_count (origin_circuit_t *circ)
 
int pathbias_count_build_attempt (origin_circuit_t *circ)
 
void pathbias_count_build_success (origin_circuit_t *circ)
 
void pathbias_count_use_attempt (origin_circuit_t *circ)
 
void pathbias_mark_use_success (origin_circuit_t *circ)
 
void pathbias_mark_use_rollback (origin_circuit_t *circ)
 
static void pathbias_count_use_success (origin_circuit_t *circ)
 
static int pathbias_send_usable_probe (circuit_t *circ)
 
int pathbias_check_probe_response (circuit_t *circ, const cell_t *cell)
 
void pathbias_count_valid_cells (circuit_t *circ, const cell_t *cell)
 
int pathbias_check_close (origin_circuit_t *ocirc, int reason)
 
void pathbias_count_timeout (origin_circuit_t *circ)
 
static int pathbias_count_circs_in_states (entry_guard_t *guard, path_state_t from, path_state_t to)
 
double pathbias_get_close_success_count (entry_guard_t *guard)
 
double pathbias_get_use_success_count (entry_guard_t *guard)
 

Detailed Description

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.

Definition in file circpathbias.c.

Function Documentation

◆ entry_guard_inc_circ_attempt_count()

static int entry_guard_inc_circ_attempt_count ( entry_guard_t *  guard)
static

Increment the number of times we successfully extended a circuit to guard, first checking if the failure rate is high enough that we should eliminate the guard. Return -1 if the guard looks no good; return 0 if the guard looks fine.

Definition at line 61 of file circpathbias.c.

References guard_pathbias_t::circ_attempts, entry_guard_get_pathbias_state(), entry_guards_changed(), guard_pathbias_t::path_bias_disabled, pathbias_measure_close_rate(), and pathbias_scale_close_rates().

◆ pathbias_check_close()

int pathbias_check_close ( origin_circuit_t ocirc,
int  reason 
)

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.

Definition at line 1001 of file circpathbias.c.

References END_CIRC_REASON_FLAG_REMOTE, origin_circuit_t::path_state, and pathbias_should_count().

◆ pathbias_check_probe_response()

int pathbias_check_probe_response ( circuit_t circ,
const cell_t cell 
)

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.

Definition at line 870 of file circpathbias.c.

References CIRCUIT_PURPOSE_PATH_BIAS_TESTING, relay_header_t::length, cell_t::payload, circuit_t::purpose, relay_header_unpack(), TO_ORIGIN_CIRCUIT(), and tor_assert().

◆ pathbias_count_build_attempt()

int pathbias_count_build_attempt ( origin_circuit_t circ)

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.

Definition at line 420 of file circpathbias.c.

◆ pathbias_count_build_success()

void pathbias_count_build_success ( origin_circuit_t circ)

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.

Definition at line 506 of file circpathbias.c.

◆ pathbias_count_circs_in_states()

static int pathbias_count_circs_in_states ( entry_guard_t *  guard,
path_state_t  from,
path_state_t  to 
)
static

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.

Definition at line 1240 of file circpathbias.c.

References CIRCUIT_IS_ORIGIN, origin_circuit_t::cpath, crypt_path_t::extend_info, origin_circuit_t::path_state, pathbias_should_count(), SMARTLIST_FOREACH_BEGIN, and TO_ORIGIN_CIRCUIT().

Referenced by pathbias_get_close_success_count(), pathbias_get_use_success_count(), pathbias_scale_close_rates(), and pathbias_scale_use_rates().

◆ pathbias_count_collapse()

static void pathbias_count_collapse ( origin_circuit_t circ)
static

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.

Definition at line 1133 of file circpathbias.c.

References CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT, guard_pathbias_t::collapsed_circuits, origin_circuit_t::cpath, entry_guard_get_by_id_digest(), entry_guard_get_pathbias_state(), entry_guards_changed(), crypt_path_t::extend_info, extend_info_t::identity_digest, pathbias_should_count(), and circuit_t::purpose.

◆ pathbias_count_successful_close()

static void pathbias_count_successful_close ( origin_circuit_t circ)
static

◆ pathbias_count_timeout()

void pathbias_count_timeout ( origin_circuit_t circ)

◆ pathbias_count_use_attempt()

void pathbias_count_use_attempt ( origin_circuit_t circ)

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.

Definition at line 596 of file circpathbias.c.

References origin_circuit_t::path_state, and pathbias_should_count().

Referenced by connection_ap_handshake_attach_chosen_circuit().

◆ pathbias_count_use_failed()

static void pathbias_count_use_failed ( origin_circuit_t circ)
static

◆ pathbias_count_use_success()

static void pathbias_count_use_success ( origin_circuit_t circ)
static

Actually count a circuit success towards a guard's usage counters if the path state is appropriate.

Definition at line 706 of file circpathbias.c.

References origin_circuit_t::path_state, and pathbias_should_count().

◆ pathbias_count_valid_cells()

void pathbias_count_valid_cells ( circuit_t circ,
const cell_t cell 
)

Check if a cell is counts as valid data for a circuit, and if so, count it as valid.

Definition at line 930 of file circpathbias.c.

References relay_header_t::command, cell_t::payload, relay_header_unpack(), and TO_ORIGIN_CIRCUIT().

◆ pathbias_get_close_success_count()

double pathbias_get_close_success_count ( entry_guard_t *  guard)

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.

Definition at line 1283 of file circpathbias.c.

References entry_guard_get_pathbias_state(), pathbias_count_circs_in_states(), and guard_pathbias_t::successful_circuits_closed.

Referenced by pathbias_check_close_success_count(), and pathbias_measure_close_rate().

◆ pathbias_get_dropguards()

int pathbias_get_dropguards ( const or_options_t options)

If 1, we actually disable use of guards that fall below the extreme_pct.

Definition at line 141 of file circpathbias.c.

Referenced by pathbias_check_close_success_count(), pathbias_check_use_success_count(), pathbias_measure_close_rate(), and pathbias_measure_use_rate().

◆ pathbias_get_extreme_rate()

double pathbias_get_extreme_rate ( const or_options_t options)

The extreme rate is the rate at which we would drop the guard, if pb_dropguard is also set. Otherwise we just warn.

Definition at line 125 of file circpathbias.c.

Referenced by pathbias_check_close_success_count(), and pathbias_measure_close_rate().

◆ pathbias_get_extreme_use_rate()

double pathbias_get_extreme_use_rate ( const or_options_t options)

The extreme use rate is the rate at which we would drop the guard, if pb_dropguard is also set. Otherwise we just warn.

Definition at line 230 of file circpathbias.c.

Referenced by pathbias_check_use_success_count(), and pathbias_measure_use_rate().

◆ pathbias_get_min_circs()

static int pathbias_get_min_circs ( const or_options_t options)
static

The minimum number of circuit attempts before we start thinking about warning about path bias and dropping guards

Definition at line 84 of file circpathbias.c.

References or_options_t::PathBiasCircThreshold.

Referenced by pathbias_measure_close_rate().

◆ pathbias_get_min_use()

static int pathbias_get_min_use ( const or_options_t options)
static

The minimum number of circuit usage attempts before we start thinking about warning about path use bias and dropping guards

Definition at line 201 of file circpathbias.c.

References or_options_t::PathBiasUseThreshold.

Referenced by pathbias_measure_use_rate().

◆ pathbias_get_notice_rate()

static double pathbias_get_notice_rate ( const or_options_t options)
static

The circuit success rate below which we issue a notice

Definition at line 97 of file circpathbias.c.

◆ pathbias_get_notice_use_rate()

static double pathbias_get_notice_use_rate ( const or_options_t options)
static

The circuit use success rate below which we issue a notice

Definition at line 214 of file circpathbias.c.

◆ pathbias_get_scale_ratio()

static double pathbias_get_scale_ratio ( const or_options_t options)
static

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.

The mult factor is the numerator for our scaling of circuit counts for our path bias window. It allows us to scale by fractions.

Definition at line 177 of file circpathbias.c.

Referenced by pathbias_scale_close_rates(), and pathbias_scale_use_rates().

◆ pathbias_get_scale_threshold()

static int pathbias_get_scale_threshold ( const or_options_t options)
static

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.

Definition at line 158 of file circpathbias.c.

Referenced by pathbias_scale_close_rates().

◆ pathbias_get_scale_use_threshold()

static int pathbias_get_scale_use_threshold ( const or_options_t options)
static

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.

Definition at line 248 of file circpathbias.c.

Referenced by pathbias_scale_use_rates().

◆ pathbias_get_use_success_count()

double pathbias_get_use_success_count ( entry_guard_t *  guard)

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.

Definition at line 1301 of file circpathbias.c.

References entry_guard_get_pathbias_state(), pathbias_count_circs_in_states(), and guard_pathbias_t::use_successes.

Referenced by pathbias_check_use_success_count(), and pathbias_measure_use_rate().

◆ pathbias_get_warn_rate()

static double pathbias_get_warn_rate ( const or_options_t options)
static

The circuit success rate below which we issue a warn

Definition at line 109 of file circpathbias.c.

◆ pathbias_is_new_circ_attempt()

static int pathbias_is_new_circ_attempt ( origin_circuit_t circ)
static

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).

Definition at line 294 of file circpathbias.c.

References origin_circuit_t::cpath, crypt_path_t::next, and crypt_path_t::state.

◆ pathbias_mark_use_rollback()

void pathbias_mark_use_rollback ( origin_circuit_t circ)

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.

Definition at line 691 of file circpathbias.c.

References origin_circuit_t::path_state.

◆ pathbias_mark_use_success()

void pathbias_mark_use_success ( origin_circuit_t circ)

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).

Definition at line 652 of file circpathbias.c.

References origin_circuit_t::path_state, and pathbias_should_count().

◆ pathbias_measure_close_rate()

static void pathbias_measure_close_rate ( entry_guard_t *  guard)
static

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.

Definition at line 1425 of file circpathbias.c.

References guard_pathbias_t::circ_attempts, entry_guard_get_pathbias_state(), guard_pathbias_t::path_bias_disabled, pathbias_get_close_success_count(), pathbias_get_dropguards(), pathbias_get_extreme_rate(), and pathbias_get_min_circs().

Referenced by entry_guard_inc_circ_attempt_count().

◆ pathbias_measure_use_rate()

static void pathbias_measure_use_rate ( entry_guard_t *  guard)
static

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.

Definition at line 1320 of file circpathbias.c.

References entry_guard_get_pathbias_state(), guard_pathbias_t::path_bias_disabled, pathbias_get_dropguards(), pathbias_get_extreme_use_rate(), pathbias_get_min_use(), pathbias_get_use_success_count(), and guard_pathbias_t::use_attempts.

◆ pathbias_scale_close_rates()

static void pathbias_scale_close_rates ( entry_guard_t *  guard)
static

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.

Definition at line 1545 of file circpathbias.c.

References guard_pathbias_t::circ_attempts, guard_pathbias_t::circ_successes, guard_pathbias_t::collapsed_circuits, entry_guard_get_pathbias_state(), entry_guards_changed(), pathbias_count_circs_in_states(), pathbias_get_scale_ratio(), pathbias_get_scale_threshold(), guard_pathbias_t::successful_circuits_closed, guard_pathbias_t::timeouts, and guard_pathbias_t::unusable_circuits.

Referenced by entry_guard_inc_circ_attempt_count().

◆ pathbias_scale_use_rates()

void pathbias_scale_use_rates ( entry_guard_t *  guard)
static

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.

Definition at line 1605 of file circpathbias.c.

References entry_guard_get_pathbias_state(), pathbias_count_circs_in_states(), pathbias_get_scale_ratio(), pathbias_get_scale_use_threshold(), guard_pathbias_t::use_attempts, and guard_pathbias_t::use_successes.

◆ pathbias_send_usable_probe()

static int pathbias_send_usable_probe ( circuit_t circ)
static

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.

Definition at line 767 of file circpathbias.c.

References CELL_PAYLOAD_SIZE, origin_circuit_t::cpath, crypt_path_t::prev, crypt_path_t::state, TO_ORIGIN_CIRCUIT(), and tor_assert().

◆ pathbias_should_count()

static int pathbias_should_count ( origin_circuit_t circ)
static

◆ pathbias_state_to_string()

const char* pathbias_state_to_string ( path_state_t  state)

Convert a Guard's path state to string.

Definition at line 263 of file circpathbias.c.