Tor  0.4.5.0-alpha-dev
circpathbias.c
Go to the documentation of this file.
1 /* Copyright (c) 2001 Matej Pfajfar.
2  * Copyright (c) 2001-2004, Roger Dingledine.
3  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4  * Copyright (c) 2007-2020, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
6 
7 /**
8  * \file circpathbias.c
9  *
10  * \brief Code to track success/failure rates of circuits built through
11  * different tor nodes, in an attempt to detect attacks where
12  * an attacker deliberately causes circuits to fail until the client
13  * choses a path they like.
14  *
15  * This code is currently configured in a warning-only mode, though false
16  * positives appear to be rare in practice. There is also support for
17  * disabling really bad guards, but it's quite experimental and may have bad
18  * anonymity effects.
19  *
20  * The information here is associated with the entry_guard_t object for
21  * each guard, and stored persistently in the state file.
22  */
23 
24 #include "core/or/or.h"
25 #include "core/or/channel.h"
26 #include "feature/client/circpathbias.h"
27 #include "core/or/circuitbuild.h"
28 #include "core/or/circuitlist.h"
29 #include "core/or/circuituse.h"
30 #include "core/or/circuitstats.h"
32 #include "app/config/config.h"
36 #include "core/or/relay.h"
37 #include "lib/math/fp.h"
38 #include "lib/math/laplace.h"
39 
40 #include "core/or/cell_st.h"
42 #include "core/or/crypt_path_st.h"
43 #include "core/or/extend_info_st.h"
45 
47 static void pathbias_count_collapse(origin_circuit_t *circ);
49 static void pathbias_measure_use_rate(entry_guard_t *guard);
50 static void pathbias_measure_close_rate(entry_guard_t *guard);
51 static void pathbias_scale_use_rates(entry_guard_t *guard);
52 static void pathbias_scale_close_rates(entry_guard_t *guard);
53 static int entry_guard_inc_circ_attempt_count(entry_guard_t *guard);
54 
55 /** Increment the number of times we successfully extended a circuit to
56  * <b>guard</b>, first checking if the failure rate is high enough that
57  * we should eliminate the guard. Return -1 if the guard looks no good;
58  * return 0 if the guard looks fine.
59  */
60 static int
62 {
64 
66 
68 
69  if (pb->path_bias_disabled)
70  return -1;
71 
73  pb->circ_attempts++;
74 
75  log_info(LD_CIRC, "Got success count %f/%f for guard %s",
77  entry_guard_describe(guard));
78  return 0;
79 }
80 
81 /** The minimum number of circuit attempts before we start
82  * thinking about warning about path bias and dropping guards */
83 static int
85 {
86 #define DFLT_PATH_BIAS_MIN_CIRC 150
87  if (options->PathBiasCircThreshold >= 5)
88  return options->PathBiasCircThreshold;
89  else
90  return networkstatus_get_param(NULL, "pb_mincircs",
91  DFLT_PATH_BIAS_MIN_CIRC,
92  5, INT32_MAX);
93 }
94 
95 /** The circuit success rate below which we issue a notice */
96 static double
98 {
99 #define DFLT_PATH_BIAS_NOTICE_PCT 70
100  if (options->PathBiasNoticeRate >= 0.0)
101  return options->PathBiasNoticeRate;
102  else
103  return networkstatus_get_param(NULL, "pb_noticepct",
104  DFLT_PATH_BIAS_NOTICE_PCT, 0, 100)/100.0;
105 }
106 
107 /** The circuit success rate below which we issue a warn */
108 static double
110 {
111 #define DFLT_PATH_BIAS_WARN_PCT 50
112  if (options->PathBiasWarnRate >= 0.0)
113  return options->PathBiasWarnRate;
114  else
115  return networkstatus_get_param(NULL, "pb_warnpct",
116  DFLT_PATH_BIAS_WARN_PCT, 0, 100)/100.0;
117 }
118 
119 /* XXXX I'd like to have this be static again, but entrynodes.c needs it. */
120 /**
121  * The extreme rate is the rate at which we would drop the guard,
122  * if pb_dropguard is also set. Otherwise we just warn.
123  */
124 double
126 {
127 #define DFLT_PATH_BIAS_EXTREME_PCT 30
128  if (options->PathBiasExtremeRate >= 0.0)
129  return options->PathBiasExtremeRate;
130  else
131  return networkstatus_get_param(NULL, "pb_extremepct",
132  DFLT_PATH_BIAS_EXTREME_PCT, 0, 100)/100.0;
133 }
134 
135 /* XXXX I'd like to have this be static again, but entrynodes.c needs it. */
136 /**
137  * If 1, we actually disable use of guards that fall below
138  * the extreme_pct.
139  */
140 int
142 {
143 #define DFLT_PATH_BIAS_DROP_GUARDS 0
144  if (options->PathBiasDropGuards >= 0)
145  return options->PathBiasDropGuards;
146  else
147  return networkstatus_get_param(NULL, "pb_dropguards",
148  DFLT_PATH_BIAS_DROP_GUARDS, 0, 1);
149 }
150 
151 /**
152  * This is the number of circuits at which we scale our
153  * counts by mult_factor/scale_factor. Note, this count is
154  * not exact, as we only perform the scaling in the event
155  * of no integer truncation.
156  */
157 static int
159 {
160 #define DFLT_PATH_BIAS_SCALE_THRESHOLD 300
161  if (options->PathBiasScaleThreshold >= 10)
162  return options->PathBiasScaleThreshold;
163  else
164  return networkstatus_get_param(NULL, "pb_scalecircs",
165  DFLT_PATH_BIAS_SCALE_THRESHOLD, 10,
166  INT32_MAX);
167 }
168 
169 /**
170  * Compute the path bias scaling ratio from the consensus
171  * parameters pb_multfactor/pb_scalefactor.
172  *
173  * Returns a value in (0, 1.0] which we multiply our pathbias
174  * counts with to scale them down.
175  */
176 static double
178 {
179  (void) options;
180  /*
181  * The scale factor is the denominator for our scaling
182  * of circuit counts for our path bias window.
183  *
184  * Note that our use of doubles for the path bias state
185  * file means that powers of 2 work best here.
186  */
187  int denominator = networkstatus_get_param(NULL, "pb_scalefactor",
188  2, 2, INT32_MAX);
189  tor_assert(denominator > 0);
190 
191  /**
192  * The mult factor is the numerator for our scaling
193  * of circuit counts for our path bias window. It
194  * allows us to scale by fractions.
195  */
196  return networkstatus_get_param(NULL, "pb_multfactor",
197  1, 1, denominator)/((double)denominator);
198 }
199 
200 /** The minimum number of circuit usage attempts before we start
201  * thinking about warning about path use bias and dropping guards */
202 static int
204 {
205 #define DFLT_PATH_BIAS_MIN_USE 20
206  if (options->PathBiasUseThreshold >= 3)
207  return options->PathBiasUseThreshold;
208  else
209  return networkstatus_get_param(NULL, "pb_minuse",
210  DFLT_PATH_BIAS_MIN_USE,
211  3, INT32_MAX);
212 }
213 
214 /** The circuit use success rate below which we issue a notice */
215 static double
217 {
218 #define DFLT_PATH_BIAS_NOTICE_USE_PCT 80
219  if (options->PathBiasNoticeUseRate >= 0.0)
220  return options->PathBiasNoticeUseRate;
221  else
222  return networkstatus_get_param(NULL, "pb_noticeusepct",
223  DFLT_PATH_BIAS_NOTICE_USE_PCT,
224  0, 100)/100.0;
225 }
226 
227 /**
228  * The extreme use rate is the rate at which we would drop the guard,
229  * if pb_dropguard is also set. Otherwise we just warn.
230  */
231 double
233 {
234 #define DFLT_PATH_BIAS_EXTREME_USE_PCT 60
235  if (options->PathBiasExtremeUseRate >= 0.0)
236  return options->PathBiasExtremeUseRate;
237  else
238  return networkstatus_get_param(NULL, "pb_extremeusepct",
239  DFLT_PATH_BIAS_EXTREME_USE_PCT,
240  0, 100)/100.0;
241 }
242 
243 /**
244  * This is the number of circuits at which we scale our
245  * use counts by mult_factor/scale_factor. Note, this count is
246  * not exact, as we only perform the scaling in the event
247  * of no integer truncation.
248  */
249 static int
251 {
252 #define DFLT_PATH_BIAS_SCALE_USE_THRESHOLD 100
253  if (options->PathBiasScaleUseThreshold >= 10)
254  return options->PathBiasScaleUseThreshold;
255  else
256  return networkstatus_get_param(NULL, "pb_scaleuse",
257  DFLT_PATH_BIAS_SCALE_USE_THRESHOLD,
258  10, INT32_MAX);
259 }
260 
261 /**
262  * Convert a Guard's path state to string.
263  */
264 const char *
266 {
267  switch (state) {
268  case PATH_STATE_NEW_CIRC:
269  return "new";
271  return "build attempted";
273  return "build succeeded";
275  return "use attempted";
277  return "use succeeded";
279  return "use failed";
281  return "already counted";
282  }
283 
284  return "unknown";
285 }
286 
287 /**
288  * This function decides if a circuit has progressed far enough to count
289  * as a circuit "attempt". As long as end-to-end tagging is possible,
290  * we assume the adversary will use it over hop-to-hop failure. Therefore,
291  * we only need to account bias for the last hop. This should make us
292  * much more resilient to ambient circuit failure, and also make that
293  * failure easier to measure (we only need to measure Exit failure rates).
294  */
295 static int
297 {
298 #define N2N_TAGGING_IS_POSSIBLE
299 #ifdef N2N_TAGGING_IS_POSSIBLE
300  /* cpath is a circular list. We want circs with more than one hop,
301  * and the second hop must be waiting for keys still (it's just
302  * about to get them). */
303  return circ->cpath &&
304  circ->cpath->next != circ->cpath &&
305  circ->cpath->next->state == CPATH_STATE_AWAITING_KEYS;
306 #else /* !defined(N2N_TAGGING_IS_POSSIBLE) */
307  /* If tagging attacks are no longer possible, we probably want to
308  * count bias from the first hop. However, one could argue that
309  * timing-based tagging is still more useful than per-hop failure.
310  * In which case, we'd never want to use this.
311  */
312  return circ->cpath &&
313  circ->cpath->state == CPATH_STATE_AWAITING_KEYS;
314 #endif /* defined(N2N_TAGGING_IS_POSSIBLE) */
315 }
316 
317 /**
318  * Decide if the path bias code should count a circuit.
319  *
320  * @returns 1 if we should count it, 0 otherwise.
321  */
322 static int
324 {
325 #define PATHBIAS_COUNT_INTERVAL (600)
326  static ratelim_t count_limit =
327  RATELIM_INIT(PATHBIAS_COUNT_INTERVAL);
328  char *rate_msg = NULL;
329 
330  /* We can't do path bias accounting without entry guards.
331  * Testing and controller circuits also have no guards.
332  *
333  * We also don't count server-side rends, because their
334  * endpoint could be chosen maliciously.
335  * Similarly, we can't count client-side intro attempts,
336  * because clients can be manipulated into connecting to
337  * malicious intro points. */
338  if (get_options()->UseEntryGuards == 0 ||
339  circ->base_.purpose == CIRCUIT_PURPOSE_TESTING ||
340  circ->base_.purpose == CIRCUIT_PURPOSE_CONTROLLER ||
341  circ->base_.purpose == CIRCUIT_PURPOSE_S_CONNECT_REND ||
342  circ->base_.purpose == CIRCUIT_PURPOSE_S_REND_JOINED ||
343  (circ->base_.purpose >= CIRCUIT_PURPOSE_C_INTRODUCING &&
344  circ->base_.purpose <= CIRCUIT_PURPOSE_C_INTRODUCE_ACKED)) {
345 
346  /* Check to see if the shouldcount result has changed due to a
347  * unexpected purpose change that would affect our results.
348  *
349  * The reason we check the path state too here is because for the
350  * cannibalized versions of these purposes, we count them as successful
351  * before their purpose change.
352  */
353  if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_COUNTED
355  log_info(LD_BUG,
356  "Circuit %d is now being ignored despite being counted "
357  "in the past. Purpose is %s, path state is %s",
358  circ->global_identifier,
359  circuit_purpose_to_string(circ->base_.purpose),
361  }
362  circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_IGNORED;
363  return 0;
364  }
365 
366  /* Completely ignore one hop circuits */
367  if (circ->build_state->onehop_tunnel ||
368  circ->build_state->desired_path_len == 1) {
369  /* Check for inconsistency */
370  if (circ->build_state->desired_path_len != 1 ||
371  !circ->build_state->onehop_tunnel) {
372  if ((rate_msg = rate_limit_log(&count_limit, approx_time()))) {
373  log_info(LD_BUG,
374  "One-hop circuit %d has length %d. Path state is %s. "
375  "Circuit is a %s currently %s.%s",
376  circ->global_identifier,
379  circuit_purpose_to_string(circ->base_.purpose),
380  circuit_state_to_string(circ->base_.state),
381  rate_msg);
382  tor_free(rate_msg);
383  }
385  }
386 
387  /* Check to see if the shouldcount result has changed due to a
388  * unexpected change that would affect our results */
389  if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_COUNTED) {
390  log_info(LD_BUG,
391  "One-hop circuit %d is now being ignored despite being counted "
392  "in the past. Purpose is %s, path state is %s",
393  circ->global_identifier,
394  circuit_purpose_to_string(circ->base_.purpose),
396  }
397  circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_IGNORED;
398  return 0;
399  }
400 
401  /* Check to see if the shouldcount result has changed due to a
402  * unexpected purpose change that would affect our results */
403  if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_IGNORED) {
404  log_info(LD_CIRC,
405  "Circuit %d is not being counted by pathbias because it was "
406  "ignored in the past. Purpose is %s, path state is %s",
407  circ->global_identifier,
408  circuit_purpose_to_string(circ->base_.purpose),
410  return 0;
411  }
412  circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_COUNTED;
413 
414  return 1;
415 }
416 
417 /**
418  * Check our circuit state to see if this is a successful circuit attempt.
419  * If so, record it in the current guard's path bias circ_attempt count.
420  *
421  * Also check for several potential error cases for bug #6475.
422  */
423 int
425 {
426 #define CIRC_ATTEMPT_NOTICE_INTERVAL (600)
427  static ratelim_t circ_attempt_notice_limit =
428  RATELIM_INIT(CIRC_ATTEMPT_NOTICE_INTERVAL);
429  char *rate_msg = NULL;
430 
431  if (!pathbias_should_count(circ)) {
432  return 0;
433  }
434 
435  if (pathbias_is_new_circ_attempt(circ)) {
436  /* Help track down the real cause of bug #6475: */
437  if (circ->has_opened && circ->path_state != PATH_STATE_BUILD_ATTEMPTED) {
438  if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
439  approx_time()))) {
440  log_info(LD_BUG,
441  "Opened circuit %d is in strange path state %s. "
442  "Circuit is a %s currently %s.%s",
443  circ->global_identifier,
445  circuit_purpose_to_string(circ->base_.purpose),
446  circuit_state_to_string(circ->base_.state),
447  rate_msg);
448  tor_free(rate_msg);
449  }
450  }
451 
452  /* Don't re-count cannibalized circs.. */
453  if (!circ->has_opened) {
454  entry_guard_t *guard = NULL;
455 
456  if (circ->cpath && circ->cpath->extend_info) {
459  } else if (circ->base_.n_chan) {
460  guard =
462  }
463 
464  if (guard) {
465  if (circ->path_state == PATH_STATE_NEW_CIRC) {
467 
468  if (entry_guard_inc_circ_attempt_count(guard) < 0) {
469  /* Bogus guard; we already warned. */
470  return -END_CIRC_REASON_TORPROTOCOL;
471  }
472  } else {
473  if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
474  approx_time()))) {
475  log_info(LD_BUG,
476  "Unopened circuit %d has strange path state %s. "
477  "Circuit is a %s currently %s.%s",
478  circ->global_identifier,
480  circuit_purpose_to_string(circ->base_.purpose),
481  circuit_state_to_string(circ->base_.state),
482  rate_msg);
483  tor_free(rate_msg);
484  }
485  }
486  } else {
487  if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
488  approx_time()))) {
489  log_info(LD_CIRC,
490  "Unopened circuit has no known guard. "
491  "Circuit is a %s currently %s.%s",
492  circuit_purpose_to_string(circ->base_.purpose),
493  circuit_state_to_string(circ->base_.state),
494  rate_msg);
495  tor_free(rate_msg);
496  }
497  }
498  }
499  }
500 
501  return 0;
502 }
503 
504 /**
505  * Check our circuit state to see if this is a successful circuit
506  * completion. If so, record it in the current guard's path bias
507  * success count.
508  *
509  * Also check for several potential error cases for bug #6475.
510  */
511 void
513 {
514 #define SUCCESS_NOTICE_INTERVAL (600)
515  static ratelim_t success_notice_limit =
516  RATELIM_INIT(SUCCESS_NOTICE_INTERVAL);
517  char *rate_msg = NULL;
518  entry_guard_t *guard = NULL;
519 
520  if (!pathbias_should_count(circ)) {
521  return;
522  }
523 
524  /* Don't count cannibalized/reused circs for path bias
525  * "build" success, since they get counted under "use" success. */
526  if (!circ->has_opened) {
527  if (circ->cpath && circ->cpath->extend_info) {
530  }
531 
532  if (guard) {
534 
535  if (circ->path_state == PATH_STATE_BUILD_ATTEMPTED) {
537  pb->circ_successes++;
539 
540  log_info(LD_CIRC, "Got success count %f/%f for guard %s",
541  pb->circ_successes, pb->circ_attempts,
542  entry_guard_describe(guard));
543  } else {
544  if ((rate_msg = rate_limit_log(&success_notice_limit,
545  approx_time()))) {
546  log_info(LD_BUG,
547  "Succeeded circuit %d is in strange path state %s. "
548  "Circuit is a %s currently %s.%s",
549  circ->global_identifier,
551  circuit_purpose_to_string(circ->base_.purpose),
552  circuit_state_to_string(circ->base_.state),
553  rate_msg);
554  tor_free(rate_msg);
555  }
556  }
557 
558  if (pb->circ_attempts < pb->circ_successes) {
559  log_notice(LD_BUG, "Unexpectedly high successes counts (%f/%f) "
560  "for guard %s",
561  pb->circ_successes, pb->circ_attempts,
562  entry_guard_describe(guard));
563  }
564  /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
565  * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
566  * No need to log that case. */
567  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
568  if ((rate_msg = rate_limit_log(&success_notice_limit,
569  approx_time()))) {
570  log_info(LD_CIRC,
571  "Completed circuit has no known guard. "
572  "Circuit is a %s currently %s.%s",
573  circuit_purpose_to_string(circ->base_.purpose),
574  circuit_state_to_string(circ->base_.state),
575  rate_msg);
576  tor_free(rate_msg);
577  }
578  }
579  } else {
581  if ((rate_msg = rate_limit_log(&success_notice_limit,
582  approx_time()))) {
583  log_info(LD_BUG,
584  "Opened circuit %d is in strange path state %s. "
585  "Circuit is a %s currently %s.%s",
586  circ->global_identifier,
588  circuit_purpose_to_string(circ->base_.purpose),
589  circuit_state_to_string(circ->base_.state),
590  rate_msg);
591  tor_free(rate_msg);
592  }
593  }
594  }
595 }
596 
597 /**
598  * Record an attempt to use a circuit. Changes the circuit's
599  * path state and update its guard's usage counter.
600  *
601  * Used for path bias usage accounting.
602  */
603 void
605 {
606  if (!pathbias_should_count(circ)) {
607  return;
608  }
609 
611  log_notice(LD_BUG,
612  "Used circuit %d is in strange path state %s. "
613  "Circuit is a %s currently %s.",
614  circ->global_identifier,
616  circuit_purpose_to_string(circ->base_.purpose),
617  circuit_state_to_string(circ->base_.state));
618  } else if (circ->path_state < PATH_STATE_USE_ATTEMPTED) {
619  entry_guard_t *guard = entry_guard_get_by_id_digest(
621  if (guard) {
623 
626  pb->use_attempts++;
628 
629  log_debug(LD_CIRC,
630  "Marked circuit %d (%f/%f) as used for guard %s.",
631  circ->global_identifier,
632  pb->use_successes, pb->use_attempts,
633  entry_guard_describe(guard));
634  }
635 
637  } else {
638  /* Harmless but educational log message */
639  log_info(LD_CIRC,
640  "Used circuit %d is already in path state %s. "
641  "Circuit is a %s currently %s.",
642  circ->global_identifier,
644  circuit_purpose_to_string(circ->base_.purpose),
645  circuit_state_to_string(circ->base_.state));
646  }
647 
648  return;
649 }
650 
651 /**
652  * Check the circuit's path state is appropriate and mark it as
653  * successfully used. Used for path bias usage accounting.
654  *
655  * We don't actually increment the guard's counters until
656  * pathbias_check_close(), because the circuit can still transition
657  * back to PATH_STATE_USE_ATTEMPTED if a stream fails later (this
658  * is done so we can probe the circuit for liveness at close).
659  */
660 void
662 {
663  if (!pathbias_should_count(circ)) {
664  return;
665  }
666 
667  if (circ->path_state < PATH_STATE_USE_ATTEMPTED) {
668  log_notice(LD_BUG,
669  "Used circuit %d is in strange path state %s. "
670  "Circuit is a %s currently %s.",
671  circ->global_identifier,
673  circuit_purpose_to_string(circ->base_.purpose),
674  circuit_state_to_string(circ->base_.state));
675 
677  }
678 
679  /* We don't do any accounting at the guard until actual circuit close */
681 
682  return;
683 }
684 
685 /**
686  * If a stream ever detatches from a circuit in a retriable way,
687  * we need to mark this circuit as still needing either another
688  * successful stream, or in need of a probe.
689  *
690  * An adversary could let the first stream request succeed (ie the
691  * resolve), but then tag and timeout the remainder (via cell
692  * dropping), forcing them on new circuits.
693  *
694  * Rolling back the state will cause us to probe such circuits, which
695  * should lead to probe failures in the event of such tagging due to
696  * either unrecognized cells coming in while we wait for the probe,
697  * or the cipher state getting out of sync in the case of dropped cells.
698  */
699 void
701 {
702  if (circ->path_state == PATH_STATE_USE_SUCCEEDED) {
703  log_info(LD_CIRC,
704  "Rolling back pathbias use state to 'attempted' for detached "
705  "circuit %d", circ->global_identifier);
707  }
708 }
709 
710 /**
711  * Actually count a circuit success towards a guard's usage counters
712  * if the path state is appropriate.
713  */
714 static void
716 {
717  entry_guard_t *guard;
718 
719  if (!pathbias_should_count(circ)) {
720  return;
721  }
722 
723  if (circ->path_state != PATH_STATE_USE_SUCCEEDED) {
724  log_notice(LD_BUG,
725  "Successfully used circuit %d is in strange path state %s. "
726  "Circuit is a %s currently %s.",
727  circ->global_identifier,
729  circuit_purpose_to_string(circ->base_.purpose),
730  circuit_state_to_string(circ->base_.state));
731  } else {
734  if (guard) {
736 
737  pb->use_successes++;
739 
740  if (pb->use_attempts < pb->use_successes) {
741  log_notice(LD_BUG, "Unexpectedly high use successes counts (%f/%f) "
742  "for guard %s",
743  pb->use_successes, pb->use_attempts,
744  entry_guard_describe(guard));
745  }
746 
747  log_debug(LD_CIRC,
748  "Marked circuit %d (%f/%f) as used successfully for guard %s",
749  circ->global_identifier, pb->use_successes,
750  pb->use_attempts,
751  entry_guard_describe(guard));
752  }
753  }
754 
755  return;
756 }
757 
758 /**
759  * Send a probe down a circuit that the client attempted to use,
760  * but for which the stream timed out/failed. The probe is a
761  * RELAY_BEGIN cell with a 0.a.b.c destination address, which
762  * the exit will reject and reply back, echoing that address.
763  *
764  * The reason for such probes is because it is possible to bias
765  * a user's paths simply by causing timeouts, and these timeouts
766  * are not possible to differentiate from unresponsive servers.
767  *
768  * The probe is sent at the end of the circuit lifetime for two
769  * reasons: to prevent cryptographic taggers from being able to
770  * drop cells to cause timeouts, and to prevent easy recognition
771  * of probes before any real client traffic happens.
772  *
773  * Returns -1 if we couldn't probe, 0 otherwise.
774  */
775 static int
777 {
778  /* Based on connection_ap_handshake_send_begin() */
779  char payload[CELL_PAYLOAD_SIZE];
780  int payload_len;
781  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
782  crypt_path_t *cpath_layer = NULL;
783  char *probe_nonce = NULL;
784 
785  tor_assert(ocirc);
786 
787  cpath_layer = ocirc->cpath->prev;
788 
789  if (cpath_layer->state != CPATH_STATE_OPEN) {
790  /* This can happen for cannibalized circuits. Their
791  * last hop isn't yet open */
792  log_info(LD_CIRC,
793  "Got pathbias probe request for unopened circuit %d. "
794  "Opened %d, len %d", ocirc->global_identifier,
795  ocirc->has_opened, ocirc->build_state->desired_path_len);
796  return -1;
797  }
798 
799  /* We already went down this road. */
801  ocirc->pathbias_probe_id) {
802  log_info(LD_CIRC,
803  "Got pathbias probe request for circuit %d with "
804  "outstanding probe", ocirc->global_identifier);
805  return -1;
806  }
807 
808  /* Can't probe if the channel isn't open */
809  if (circ->n_chan == NULL ||
810  (!CHANNEL_IS_OPEN(circ->n_chan)
811  && !CHANNEL_IS_MAINT(circ->n_chan))) {
812  log_info(LD_CIRC,
813  "Skipping pathbias probe for circuit %d: Channel is not open.",
814  ocirc->global_identifier);
815  return -1;
816  }
817 
819 
820  /* Update timestamp for when circuit_expire_building() should kill us */
822 
823  /* Generate a random address for the nonce */
824  crypto_rand((char*)&ocirc->pathbias_probe_nonce,
825  sizeof(ocirc->pathbias_probe_nonce));
826  ocirc->pathbias_probe_nonce &= 0x00ffffff;
827  probe_nonce = tor_dup_ip(ocirc->pathbias_probe_nonce);
828 
829  if (!probe_nonce) {
830  log_err(LD_BUG, "Failed to generate nonce");
831  return -1;
832  }
833 
834  tor_snprintf(payload,RELAY_PAYLOAD_SIZE, "%s:25", probe_nonce);
835  payload_len = (int)strlen(payload)+1;
836 
837  // XXX: need this? Can we assume ipv4 will always be supported?
838  // If not, how do we tell?
839  //if (payload_len <= RELAY_PAYLOAD_SIZE - 4 && edge_conn->begincell_flags) {
840  // set_uint32(payload + payload_len, htonl(edge_conn->begincell_flags));
841  // payload_len += 4;
842  //}
843 
844  /* Generate+Store stream id, make sure it's non-zero */
846 
847  if (ocirc->pathbias_probe_id==0) {
848  log_warn(LD_CIRC,
849  "Ran out of stream IDs on circuit %u during "
850  "pathbias probe attempt.", ocirc->global_identifier);
851  tor_free(probe_nonce);
852  return -1;
853  }
854 
855  log_info(LD_CIRC,
856  "Sending pathbias testing cell to %s:25 on stream %d for circ %d.",
857  probe_nonce, ocirc->pathbias_probe_id, ocirc->global_identifier);
858  tor_free(probe_nonce);
859 
860  /* Send a test relay cell */
861  if (relay_send_command_from_edge(ocirc->pathbias_probe_id, circ,
862  RELAY_COMMAND_BEGIN, payload,
863  payload_len, cpath_layer) < 0) {
864  log_notice(LD_CIRC,
865  "Failed to send pathbias probe cell on circuit %d.",
866  ocirc->global_identifier);
867  return -1;
868  }
869 
870  /* Mark it freshly dirty so it doesn't get expired in the meantime */
871  circ->timestamp_dirty = time(NULL);
872 
873  return 0;
874 }
875 
876 /**
877  * Check the response to a pathbias probe, to ensure the
878  * cell is recognized and the nonce and other probe
879  * characteristics are as expected.
880  *
881  * If the response is valid, return 0. Otherwise return < 0.
882  */
883 int
885 {
886  /* Based on connection_edge_process_relay_cell() */
887  relay_header_t rh;
888  int reason;
889  uint32_t ipv4_host;
890  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
891 
892  tor_assert(cell);
893  tor_assert(ocirc);
895 
896  relay_header_unpack(&rh, cell->payload);
897 
898  reason = rh.length > 0 ?
899  get_uint8(cell->payload+RELAY_HEADER_SIZE) : END_STREAM_REASON_MISC;
900 
901  if (rh.command == RELAY_COMMAND_END &&
902  reason == END_STREAM_REASON_EXITPOLICY &&
903  ocirc->pathbias_probe_id == rh.stream_id) {
904 
905  /* Check length+extract host: It is in network order after the reason code.
906  * See connection_edge_end(). */
907  if (rh.length < 9) { /* reason+ipv4+dns_ttl */
908  log_notice(LD_PROTOCOL,
909  "Short path bias probe response length field (%d).", rh.length);
910  return - END_CIRC_REASON_TORPROTOCOL;
911  }
912 
913  ipv4_host = ntohl(get_uint32(cell->payload+RELAY_HEADER_SIZE+1));
914 
915  /* Check nonce */
916  if (ipv4_host == ocirc->pathbias_probe_nonce) {
918  circuit_read_valid_data(ocirc, rh.length);
919  circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED);
920  log_info(LD_CIRC,
921  "Got valid path bias probe back for circ %d, stream %d.",
922  ocirc->global_identifier, ocirc->pathbias_probe_id);
923  return 0;
924  } else {
925  log_notice(LD_CIRC,
926  "Got strange probe value 0x%x vs 0x%x back for circ %d, "
927  "stream %d.", ipv4_host, ocirc->pathbias_probe_nonce,
928  ocirc->global_identifier, ocirc->pathbias_probe_id);
929  return -1;
930  }
931  }
932  log_info(LD_CIRC,
933  "Got another cell back back on pathbias probe circuit %d: "
934  "Command: %d, Reason: %d, Stream-id: %d",
935  ocirc->global_identifier, rh.command, reason, rh.stream_id);
936  return -1;
937 }
938 
939 /**
940  * Check if a cell is counts as valid data for a circuit,
941  * and if so, count it as valid.
942  */
943 void
945 {
946  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
947  relay_header_t rh;
948 
949  relay_header_unpack(&rh, cell->payload);
950 
951  /* Check to see if this is a cell from a previous connection,
952  * or is a request to close the circuit. */
953  switch (rh.command) {
954  case RELAY_COMMAND_TRUNCATED:
955  /* Truncated cells can arrive on path bias circs. When they do,
956  * just process them. This closes the circ, but it was junk anyway.
957  * No reason to wait for the probe. */
958  circuit_read_valid_data(ocirc, rh.length);
961 
962  break;
963 
964  case RELAY_COMMAND_END:
966  rh.stream_id)) {
968  }
969  break;
970 
971  case RELAY_COMMAND_DATA:
973  rh.stream_id)) {
975  }
976  break;
977 
978  case RELAY_COMMAND_SENDME:
980  rh.stream_id)) {
982  }
983  break;
984 
985  case RELAY_COMMAND_CONNECTED:
987  rh.stream_id)) {
989  }
990  break;
991 
992  case RELAY_COMMAND_RESOLVED:
994  rh.stream_id)) {
996  }
997  break;
998  }
999 }
1000 
1001 /**
1002  * Check if a circuit was used and/or closed successfully.
1003  *
1004  * If we attempted to use the circuit to carry a stream but failed
1005  * for whatever reason, or if the circuit mysteriously died before
1006  * we could attach any streams, record these two cases.
1007  *
1008  * If we *have* successfully used the circuit, or it appears to
1009  * have been closed by us locally, count it as a success.
1010  *
1011  * Returns 0 if we're done making decisions with the circ,
1012  * or -1 if we want to probe it first.
1013  */
1014 int
1016 {
1017  circuit_t *circ = &ocirc->base_;
1018 
1019  if (!pathbias_should_count(ocirc)) {
1020  return 0;
1021  }
1022 
1023  switch (ocirc->path_state) {
1024  /* If the circuit was closed after building, but before use, we need
1025  * to ensure we were the ones who tried to close it (and not a remote
1026  * actor). */
1028  if (reason & END_CIRC_REASON_FLAG_REMOTE) {
1029  /* Remote circ close reasons on an unused circuit all could be bias */
1030  log_info(LD_CIRC,
1031  "Circuit %d remote-closed without successful use for reason %d. "
1032  "Circuit purpose %d currently %d,%s. Len %d.",
1033  ocirc->global_identifier,
1034  reason, circ->purpose, ocirc->has_opened,
1036  ocirc->build_state->desired_path_len);
1037  pathbias_count_collapse(ocirc);
1038  } else if ((reason & ~END_CIRC_REASON_FLAG_REMOTE)
1039  == END_CIRC_REASON_CHANNEL_CLOSED &&
1040  circ->n_chan &&
1041  circ->n_chan->reason_for_closing
1042  != CHANNEL_CLOSE_REQUESTED) {
1043  /* If we didn't close the channel ourselves, it could be bias */
1044  /* XXX: Only count bias if the network is live?
1045  * What about clock jumps/suspends? */
1046  log_info(LD_CIRC,
1047  "Circuit %d's channel closed without successful use for reason "
1048  "%d, channel reason %d. Circuit purpose %d currently %d,%s. Len "
1049  "%d.", ocirc->global_identifier,
1050  reason, circ->n_chan->reason_for_closing,
1051  circ->purpose, ocirc->has_opened,
1053  ocirc->build_state->desired_path_len);
1054  pathbias_count_collapse(ocirc);
1055  } else {
1057  }
1058  break;
1059 
1060  /* If we tried to use a circuit but failed, we should probe it to ensure
1061  * it has not been tampered with. */
1063  /* XXX: Only probe and/or count failure if the network is live?
1064  * What about clock jumps/suspends? */
1065  if (pathbias_send_usable_probe(circ) == 0)
1066  return -1;
1067  else
1069 
1070  /* Any circuit where there were attempted streams but no successful
1071  * streams could be bias */
1072  log_info(LD_CIRC,
1073  "Circuit %d closed without successful use for reason %d. "
1074  "Circuit purpose %d currently %d,%s. Len %d.",
1075  ocirc->global_identifier,
1076  reason, circ->purpose, ocirc->has_opened,
1078  ocirc->build_state->desired_path_len);
1079  break;
1080 
1084  break;
1085 
1086  case PATH_STATE_USE_FAILED:
1088  break;
1089 
1090  case PATH_STATE_NEW_CIRC:
1093  default:
1094  // Other states are uninteresting. No stats to count.
1095  break;
1096  }
1097 
1099 
1100  return 0;
1101 }
1102 
1103 /**
1104  * Count a successfully closed circuit.
1105  */
1106 static void
1108 {
1109  entry_guard_t *guard = NULL;
1110  if (!pathbias_should_count(circ)) {
1111  return;
1112  }
1113 
1114  if (circ->cpath && circ->cpath->extend_info) {
1117  }
1118 
1119  if (guard) {
1121 
1122  /* In the long run: circuit_success ~= successful_circuit_close +
1123  * circ_failure + stream_failure */
1126  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
1127  /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1128  * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1129  * No need to log that case. */
1130  log_info(LD_CIRC,
1131  "Successfully closed circuit has no known guard. "
1132  "Circuit is a %s currently %s",
1133  circuit_purpose_to_string(circ->base_.purpose),
1134  circuit_state_to_string(circ->base_.state));
1135  }
1136 }
1137 
1138 /**
1139  * Count a circuit that fails after it is built, but before it can
1140  * carry any traffic.
1141  *
1142  * This is needed because there are ways to destroy a
1143  * circuit after it has successfully completed. Right now, this is
1144  * used for purely informational/debugging purposes.
1145  */
1146 static void
1148 {
1149  entry_guard_t *guard = NULL;
1150 
1151  if (!pathbias_should_count(circ)) {
1152  return;
1153  }
1154 
1155  if (circ->cpath && circ->cpath->extend_info) {
1158  }
1159 
1160  if (guard) {
1162 
1163  pb->collapsed_circuits++;
1165  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
1166  /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1167  * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1168  * No need to log that case. */
1169  log_info(LD_CIRC,
1170  "Destroyed circuit has no known guard. "
1171  "Circuit is a %s currently %s",
1172  circuit_purpose_to_string(circ->base_.purpose),
1173  circuit_state_to_string(circ->base_.state));
1174  }
1175 }
1176 
1177 /**
1178  * Count a known failed circuit (because we could not probe it).
1179  *
1180  * This counter is informational.
1181  */
1182 static void
1184 {
1185  entry_guard_t *guard = NULL;
1186  if (!pathbias_should_count(circ)) {
1187  return;
1188  }
1189 
1190  if (circ->cpath && circ->cpath->extend_info) {
1193  }
1194 
1195  if (guard) {
1197 
1198  pb->unusable_circuits++;
1200  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
1201  /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1202  * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1203  * No need to log that case. */
1204  /* XXX note cut-and-paste code in this function compared to nearby
1205  * functions. Would be nice to refactor. -RD */
1206  log_info(LD_CIRC,
1207  "Stream-failing circuit has no known guard. "
1208  "Circuit is a %s currently %s",
1209  circuit_purpose_to_string(circ->base_.purpose),
1210  circuit_state_to_string(circ->base_.state));
1211  }
1212 }
1213 
1214 /**
1215  * Count timeouts for path bias log messages.
1216  *
1217  * These counts are purely informational.
1218  */
1219 void
1221 {
1222  entry_guard_t *guard = NULL;
1223 
1224  if (!pathbias_should_count(circ)) {
1225  return;
1226  }
1227 
1228  /* For hidden service circs, they can actually be used
1229  * successfully and then time out later (because
1230  * the other side declines to use them). */
1231  if (circ->path_state == PATH_STATE_USE_SUCCEEDED) {
1232  return;
1233  }
1234 
1235  if (circ->cpath && circ->cpath->extend_info) {
1238  }
1239 
1240  if (guard) {
1242 
1243  pb->timeouts++;
1245  }
1246 }
1247 
1248 /**
1249  * Helper function to count all of the currently opened circuits
1250  * for a guard that are in a given path state range. The state
1251  * range is inclusive on both ends.
1252  */
1253 static int
1254 pathbias_count_circs_in_states(entry_guard_t *guard,
1255  path_state_t from,
1256  path_state_t to)
1257 {
1258  int open_circuits = 0;
1259 
1260  /* Count currently open circuits. Give them the benefit of the doubt. */
1262  origin_circuit_t *ocirc = NULL;
1263  if (!CIRCUIT_IS_ORIGIN(circ) || /* didn't originate here */
1264  circ->marked_for_close) /* already counted */
1265  continue;
1266 
1267  ocirc = TO_ORIGIN_CIRCUIT(circ);
1268 
1269  if (!ocirc->cpath || !ocirc->cpath->extend_info)
1270  continue;
1271 
1272  if (ocirc->path_state >= from &&
1273  ocirc->path_state <= to &&
1274  pathbias_should_count(ocirc) &&
1277  DIGEST_LEN)) {
1278  log_debug(LD_CIRC, "Found opened circuit %d in path_state %s",
1279  ocirc->global_identifier,
1281  open_circuits++;
1282  }
1283  }
1284  SMARTLIST_FOREACH_END(circ);
1285 
1286  return open_circuits;
1287 }
1288 
1289 /**
1290  * Return the number of circuits counted as successfully closed for
1291  * this guard.
1292  *
1293  * Also add in the currently open circuits to give them the benefit
1294  * of the doubt.
1295  */
1296 double
1298 {
1300 
1301  return pb->successful_circuits_closed +
1305 }
1306 
1307 /**
1308  * Return the number of circuits counted as successfully used
1309  * this guard.
1310  *
1311  * Also add in the currently open circuits that we are attempting
1312  * to use to give them the benefit of the doubt.
1313  */
1314 double
1315 pathbias_get_use_success_count(entry_guard_t *guard)
1316 {
1318 
1319  return pb->use_successes +
1323 }
1324 
1325 /**
1326  * Check the path bias use rate against our consensus parameter limits.
1327  *
1328  * Emits a log message if the use success rates are too low.
1329  *
1330  * If pathbias_get_dropguards() is set, we also disable the use of
1331  * very failure prone guards.
1332  */
1333 static void
1334 pathbias_measure_use_rate(entry_guard_t *guard)
1335 {
1336  const or_options_t *options = get_options();
1338 
1339  if (pb->use_attempts > pathbias_get_min_use(options)) {
1340  /* Note: We rely on the < comparison here to allow us to set a 0
1341  * rate and disable the feature entirely. If refactoring, don't
1342  * change to <= */
1344  < pathbias_get_extreme_use_rate(options)) {
1345  /* Dropping is currently disabled by default. */
1346  if (pathbias_get_dropguards(options)) {
1347  if (!pb->path_bias_disabled) {
1348  log_warn(LD_CIRC,
1349  "Guard %s is failing to carry an extremely large "
1350  "amount of stream on its circuits. "
1351  "To avoid potential route manipulation attacks, Tor has "
1352  "disabled use of this guard. "
1353  "Use counts are %ld/%ld. Success counts are %ld/%ld. "
1354  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1355  "and %ld timed out. "
1356  "For reference, your timeout cutoff is %ld seconds.",
1357  entry_guard_describe(guard),
1359  tor_lround(pb->use_attempts),
1365  tor_lround(pb->timeouts),
1367  pb->path_bias_disabled = 1;
1368  return;
1369  }
1370  } else if (!pb->path_bias_use_extreme) {
1371  pb->path_bias_use_extreme = 1;
1372  log_warn(LD_CIRC,
1373  "Guard %s is failing to carry an extremely large "
1374  "amount of streams on its circuits. "
1375  "This could indicate a route manipulation attack, network "
1376  "overload, bad local network connectivity, or a bug. "
1377  "Use counts are %ld/%ld. Success counts are %ld/%ld. "
1378  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1379  "and %ld timed out. "
1380  "For reference, your timeout cutoff is %ld seconds.",
1381  entry_guard_describe(guard),
1383  tor_lround(pb->use_attempts),
1389  tor_lround(pb->timeouts),
1391  }
1392  } else if (pathbias_get_use_success_count(guard)/pb->use_attempts
1393  < pathbias_get_notice_use_rate(options)) {
1394  if (!pb->path_bias_use_noticed) {
1395  pb->path_bias_use_noticed = 1;
1396  log_notice(LD_CIRC,
1397  "Guard %s is failing to carry more streams on its "
1398  "circuits than usual. "
1399  "Most likely this means the Tor network is overloaded "
1400  "or your network connection is poor. "
1401  "Use counts are %ld/%ld. Success counts are %ld/%ld. "
1402  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1403  "and %ld timed out. "
1404  "For reference, your timeout cutoff is %ld seconds.",
1405  entry_guard_describe(guard),
1407  tor_lround(pb->use_attempts),
1413  tor_lround(pb->timeouts),
1415  }
1416  }
1417  }
1418 }
1419 
1420 /**
1421  * Check the path bias circuit close status rates against our consensus
1422  * parameter limits.
1423  *
1424  * Emits a log message if the use success rates are too low.
1425  *
1426  * If pathbias_get_dropguards() is set, we also disable the use of
1427  * very failure prone guards.
1428  *
1429  * XXX: This function shares similar log messages and checks to
1430  * pathbias_measure_use_rate(). It may be possible to combine them
1431  * eventually, especially if we can ever remove the need for 3
1432  * levels of closure warns (if the overall circuit failure rate
1433  * goes down with ntor). One way to do so would be to multiply
1434  * the build rate with the use rate to get an idea of the total
1435  * fraction of the total network paths the user is able to use.
1436  * See ticket #8159.
1437  */
1438 static void
1439 pathbias_measure_close_rate(entry_guard_t *guard)
1440 {
1441  const or_options_t *options = get_options();
1443 
1444  if (pb->circ_attempts > pathbias_get_min_circs(options)) {
1445  /* Note: We rely on the < comparison here to allow us to set a 0
1446  * rate and disable the feature entirely. If refactoring, don't
1447  * change to <= */
1449  < pathbias_get_extreme_rate(options)) {
1450  /* Dropping is currently disabled by default. */
1451  if (pathbias_get_dropguards(options)) {
1452  if (!pb->path_bias_disabled) {
1453  log_warn(LD_CIRC,
1454  "Guard %s is failing an extremely large "
1455  "amount of circuits. "
1456  "To avoid potential route manipulation attacks, Tor has "
1457  "disabled use of this guard. "
1458  "Success counts are %ld/%ld. Use counts are %ld/%ld. "
1459  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1460  "and %ld timed out. "
1461  "For reference, your timeout cutoff is %ld seconds.",
1462  entry_guard_describe(guard),
1466  tor_lround(pb->use_attempts),
1470  tor_lround(pb->timeouts),
1472  pb->path_bias_disabled = 1;
1473  return;
1474  }
1475  } else if (!pb->path_bias_extreme) {
1476  pb->path_bias_extreme = 1;
1477  log_warn(LD_CIRC,
1478  "Guard %s is failing an extremely large "
1479  "amount of circuits. "
1480  "This could indicate a route manipulation attack, "
1481  "extreme network overload, or a bug. "
1482  "Success counts are %ld/%ld. Use counts are %ld/%ld. "
1483  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1484  "and %ld timed out. "
1485  "For reference, your timeout cutoff is %ld seconds.",
1486  entry_guard_describe(guard),
1490  tor_lround(pb->use_attempts),
1494  tor_lround(pb->timeouts),
1496  }
1497  } else if (pathbias_get_close_success_count(guard)/pb->circ_attempts
1498  < pathbias_get_warn_rate(options)) {
1499  if (!pb->path_bias_warned) {
1500  pb->path_bias_warned = 1;
1501  log_warn(LD_CIRC,
1502  "Guard %s is failing a very large "
1503  "amount of circuits. "
1504  "Most likely this means the Tor network is "
1505  "overloaded, but it could also mean an attack against "
1506  "you or potentially the guard itself. "
1507  "Success counts are %ld/%ld. Use counts are %ld/%ld. "
1508  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1509  "and %ld timed out. "
1510  "For reference, your timeout cutoff is %ld seconds.",
1511  entry_guard_describe(guard),
1515  tor_lround(pb->use_attempts),
1519  tor_lround(pb->timeouts),
1521  }
1522  } else if (pathbias_get_close_success_count(guard)/pb->circ_attempts
1523  < pathbias_get_notice_rate(options)) {
1524  if (!pb->path_bias_noticed) {
1525  pb->path_bias_noticed = 1;
1526  log_notice(LD_CIRC,
1527  "Guard %s is failing more circuits than "
1528  "usual. "
1529  "Most likely this means the Tor network is overloaded. "
1530  "Success counts are %ld/%ld. Use counts are %ld/%ld. "
1531  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1532  "and %ld timed out. "
1533  "For reference, your timeout cutoff is %ld seconds.",
1534  entry_guard_describe(guard),
1538  tor_lround(pb->use_attempts),
1542  tor_lround(pb->timeouts),
1544  }
1545  }
1546  }
1547 }
1548 
1549 /**
1550  * This function scales the path bias use rates if we have
1551  * more data than the scaling threshold. This allows us to
1552  * be more sensitive to recent measurements.
1553  *
1554  * XXX: The attempt count transfer stuff here might be done
1555  * better by keeping separate pending counters that get
1556  * transferred at circuit close. See ticket #8160.
1557  */
1558 static void
1559 pathbias_scale_close_rates(entry_guard_t *guard)
1560 {
1561  const or_options_t *options = get_options();
1563 
1564  /* If we get a ton of circuits, just scale everything down */
1565  if (pb->circ_attempts > pathbias_get_scale_threshold(options)) {
1566  double scale_ratio = pathbias_get_scale_ratio(options);
1567  int opened_attempts = pathbias_count_circs_in_states(guard,
1569  int opened_built = pathbias_count_circs_in_states(guard,
1572  /* Verify that the counts are sane before and after scaling */
1573  int counts_are_sane = (pb->circ_attempts >= pb->circ_successes);
1574 
1575  pb->circ_attempts -= (opened_attempts+opened_built);
1576  pb->circ_successes -= opened_built;
1577 
1578  pb->circ_attempts *= scale_ratio;
1579  pb->circ_successes *= scale_ratio;
1580  pb->timeouts *= scale_ratio;
1581  pb->successful_circuits_closed *= scale_ratio;
1582  pb->collapsed_circuits *= scale_ratio;
1583  pb->unusable_circuits *= scale_ratio;
1584 
1585  pb->circ_attempts += (opened_attempts+opened_built);
1586  pb->circ_successes += opened_built;
1587 
1589 
1590  log_info(LD_CIRC,
1591  "Scaled pathbias counts to (%f,%f)/%f (%d/%d open) for guard "
1592  "%s",
1594  pb->circ_attempts, opened_built, opened_attempts,
1595  entry_guard_describe(guard));
1596 
1597  /* Have the counts just become invalid by this scaling attempt? */
1598  if (counts_are_sane && pb->circ_attempts < pb->circ_successes) {
1599  log_notice(LD_BUG,
1600  "Scaling has mangled pathbias counts to %f/%f (%d/%d open) "
1601  "for guard %s",
1602  pb->circ_successes, pb->circ_attempts, opened_built,
1603  opened_attempts,
1604  entry_guard_describe(guard));
1605  }
1606  }
1607 }
1608 
1609 /**
1610  * This function scales the path bias circuit close rates if we have
1611  * more data than the scaling threshold. This allows us to be more
1612  * sensitive to recent measurements.
1613  *
1614  * XXX: The attempt count transfer stuff here might be done
1615  * better by keeping separate pending counters that get
1616  * transferred at circuit close. See ticket #8160.
1617  */
1618 void
1619 pathbias_scale_use_rates(entry_guard_t *guard)
1620 {
1621  const or_options_t *options = get_options();
1623 
1624  /* If we get a ton of circuits, just scale everything down */
1625  if (pb->use_attempts > pathbias_get_scale_use_threshold(options)) {
1626  double scale_ratio = pathbias_get_scale_ratio(options);
1627  int opened_attempts = pathbias_count_circs_in_states(guard,
1629  /* Verify that the counts are sane before and after scaling */
1630  int counts_are_sane = (pb->use_attempts >= pb->use_successes);
1631 
1632  pb->use_attempts -= opened_attempts;
1633 
1634  pb->use_attempts *= scale_ratio;
1635  pb->use_successes *= scale_ratio;
1636 
1637  pb->use_attempts += opened_attempts;
1638 
1639  log_info(LD_CIRC,
1640  "Scaled pathbias use counts to %f/%f (%d open) for guard %s",
1641  pb->use_successes, pb->use_attempts, opened_attempts,
1642  entry_guard_describe(guard));
1643 
1644  /* Have the counts just become invalid by this scaling attempt? */
1645  if (counts_are_sane && pb->use_attempts < pb->use_successes) {
1646  log_notice(LD_BUG,
1647  "Scaling has mangled pathbias usage counts to %f/%f "
1648  "(%d open) for guard %s",
1649  pb->circ_successes, pb->circ_attempts,
1650  opened_attempts, entry_guard_describe(guard));
1651  }
1652 
1654  }
1655 }
pathbias_measure_close_rate
static void pathbias_measure_close_rate(entry_guard_t *guard)
Definition: circpathbias.c:1439
entry_guard_describe
const char * entry_guard_describe(const entry_guard_t *guard)
Definition: entrynodes.c:319
tor_free
#define tor_free(p)
Definition: malloc.h:52
PATH_STATE_BUILD_ATTEMPTED
@ PATH_STATE_BUILD_ATTEMPTED
Definition: origin_circuit_st.h:42
connection_edge.h
Header file for connection_edge.c.
origin_circuit_t::half_streams
smartlist_t * half_streams
Definition: origin_circuit_st.h:88
origin_circuit_t::pathbias_probe_id
streamid_t pathbias_probe_id
Definition: origin_circuit_st.h:187
pathbias_is_new_circ_attempt
static int pathbias_is_new_circ_attempt(origin_circuit_t *circ)
Definition: circpathbias.c:296
channel_t::identity_digest
char identity_digest[DIGEST_LEN]
Definition: channel.h:378
circuit_t::purpose
uint8_t purpose
Definition: circuit_st.h:111
circuit_t::timestamp_dirty
time_t timestamp_dirty
Definition: circuit_st.h:187
PATH_STATE_BUILD_SUCCEEDED
@ PATH_STATE_BUILD_SUCCEEDED
Definition: origin_circuit_st.h:44
guard_pathbias_t::path_bias_extreme
unsigned int path_bias_extreme
Definition: entrynodes.h:40
get_circuit_build_close_time_ms
double get_circuit_build_close_time_ms(void)
Definition: circuitstats.c:94
approx_time
time_t approx_time(void)
Definition: approx_time.c:32
pathbias_get_min_use
static int pathbias_get_min_use(const or_options_t *options)
Definition: circpathbias.c:203
guard_pathbias_t::unusable_circuits
double unusable_circuits
Definition: entrynodes.h:57
guard_pathbias_t::circ_attempts
double circ_attempts
Definition: entrynodes.h:49
circuit_get_global_list
smartlist_t * circuit_get_global_list(void)
Definition: circuitlist.c:696
relay_header_t::command
uint8_t command
Definition: or.h:639
tor_assert
#define tor_assert(expr)
Definition: util_bug.h:102
LD_BUG
#define LD_BUG
Definition: log.h:86
cpath_build_state_st.h
Circuit-build-stse structure.
CIRCUIT_PURPOSE_PATH_BIAS_TESTING
#define CIRCUIT_PURPOSE_PATH_BIAS_TESTING
Definition: circuitlist.h:122
circuituse.h
Header file for circuituse.c.
channel.h
Header file for channel.c.
guard_pathbias_t::path_bias_use_noticed
unsigned int path_bias_use_noticed
Definition: entrynodes.h:44
tor_dup_ip
char * tor_dup_ip(uint32_t addr)
Definition: address.c:2047
tor_fragile_assert
#define tor_fragile_assert()
Definition: util_bug.h:259
RELAY_PAYLOAD_SIZE
#define RELAY_PAYLOAD_SIZE
Definition: or.h:606
crypt_path_t::state
uint8_t state
Definition: crypt_path_st.h:68
or_options_t::PathBiasCircThreshold
int PathBiasCircThreshold
Definition: or_options_st.h:884
pathbias_count_use_attempt
void pathbias_count_use_attempt(origin_circuit_t *circ)
Definition: circpathbias.c:604
guard_pathbias_t::path_bias_disabled
unsigned int path_bias_disabled
Definition: entrynodes.h:42
connection_half_edge_is_valid_end
int connection_half_edge_is_valid_end(smartlist_t *half_conns, streamid_t stream_id)
Definition: connection_edge.c:775
guard_pathbias_t::collapsed_circuits
double collapsed_circuits
Definition: entrynodes.h:54
END_CIRC_REASON_FLAG_REMOTE
#define END_CIRC_REASON_FLAG_REMOTE
Definition: or.h:329
guard_pathbias_t::path_bias_noticed
unsigned int path_bias_noticed
Definition: entrynodes.h:36
guard_pathbias_t
Definition: entrynodes.h:35
circuit_t::n_chan
channel_t * n_chan
Definition: circuit_st.h:69
pathbias_check_probe_response
int pathbias_check_probe_response(circuit_t *circ, const cell_t *cell)
Definition: circpathbias.c:884
tor_snprintf
int tor_snprintf(char *str, size_t size, const char *format,...)
Definition: printf.c:27
CIRCUIT_IS_ORIGIN
#define CIRCUIT_IS_ORIGIN(c)
Definition: circuitlist.h:146
channel_t::reason_for_closing
enum channel_t::@0 reason_for_closing
crypt_path_t
Definition: crypt_path_st.h:47
CELL_PAYLOAD_SIZE
#define CELL_PAYLOAD_SIZE
Definition: or.h:577
pathbias_count_circs_in_states
static int pathbias_count_circs_in_states(entry_guard_t *guard, path_state_t from, path_state_t to)
Definition: circpathbias.c:1254
connection_half_edge_is_valid_connected
int connection_half_edge_is_valid_connected(const smartlist_t *half_conns, streamid_t stream_id)
Definition: connection_edge.c:724
networkstatus.h
Header file for networkstatus.c.
origin_circuit_t::global_identifier
uint32_t global_identifier
Definition: origin_circuit_st.h:240
guard_pathbias_t::successful_circuits_closed
double successful_circuits_closed
Definition: entrynodes.h:52
cell_t
Definition: cell_st.h:17
entry_guard_inc_circ_attempt_count
static int entry_guard_inc_circ_attempt_count(entry_guard_t *guard)
Definition: circpathbias.c:61
relay_header_t::stream_id
streamid_t stream_id
Definition: or.h:641
CIRCUIT_PURPOSE_CONTROLLER
#define CIRCUIT_PURPOSE_CONTROLLER
Definition: circuitlist.h:120
LD_CIRC
#define LD_CIRC
Definition: log.h:82
fp.h
Header for fp.c.
circuitlist.h
Header file for circuitlist.c.
crypt_path_st.h
Path structures for origin circuits.
DIGEST_LEN
#define DIGEST_LEN
Definition: digest_sizes.h:20
pathbias_get_notice_use_rate
static double pathbias_get_notice_use_rate(const or_options_t *options)
Definition: circpathbias.c:216
connection_half_edge_is_valid_sendme
int connection_half_edge_is_valid_sendme(const smartlist_t *half_conns, streamid_t stream_id)
Definition: connection_edge.c:750
rate_limit_log
char * rate_limit_log(ratelim_t *lim, time_t now)
Definition: ratelim.c:42
origin_circuit_t::path_state
path_state_bitfield_t path_state
Definition: origin_circuit_st.h:163
pathbias_scale_close_rates
static void pathbias_scale_close_rates(entry_guard_t *guard)
Definition: circpathbias.c:1559
PATH_STATE_ALREADY_COUNTED
@ PATH_STATE_ALREADY_COUNTED
Definition: origin_circuit_st.h:74
entrynodes.h
Header file for circuitbuild.c.
pathbias_get_scale_use_threshold
static int pathbias_get_scale_use_threshold(const or_options_t *options)
Definition: circpathbias.c:250
origin_circuit_t
Definition: origin_circuit_st.h:79
pathbias_send_usable_probe
static int pathbias_send_usable_probe(circuit_t *circ)
Definition: circpathbias.c:776
pathbias_scale_use_rates
static void pathbias_scale_use_rates(entry_guard_t *guard)
Definition: circpathbias.c:1619
cpath_build_state_t::onehop_tunnel
unsigned int onehop_tunnel
Definition: cpath_build_state_st.h:32
guard_pathbias_t::use_successes
double use_successes
Definition: entrynodes.h:62
origin_circuit_t::has_opened
unsigned int has_opened
Definition: origin_circuit_st.h:156
path_state_t
path_state_t
Definition: origin_circuit_st.h:36
connection_half_edge_is_valid_data
int connection_half_edge_is_valid_data(const smartlist_t *half_conns, streamid_t stream_id)
Definition: connection_edge.c:698
pathbias_count_timeout
void pathbias_count_timeout(origin_circuit_t *circ)
Definition: circpathbias.c:1220
relay_header_unpack
void relay_header_unpack(relay_header_t *dest, const uint8_t *src)
Definition: relay.c:490
pathbias_get_dropguards
int pathbias_get_dropguards(const or_options_t *options)
Definition: circpathbias.c:141
circuit_change_purpose
void circuit_change_purpose(circuit_t *circ, uint8_t new_purpose)
Definition: circuituse.c:3117
circuit_truncated
int circuit_truncated(origin_circuit_t *circ, int reason)
Definition: circuitbuild.c:1259
circuit_t::timestamp_began
struct timeval timestamp_began
Definition: circuit_st.h:165
CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
#define CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
Definition: circuitlist.h:95
circuit_t
Definition: circuit_st.h:61
guard_pathbias_t::path_bias_use_extreme
unsigned int path_bias_use_extreme
Definition: entrynodes.h:46
pathbias_count_successful_close
static void pathbias_count_successful_close(origin_circuit_t *circ)
Definition: circpathbias.c:1107
PATH_STATE_USE_SUCCEEDED
@ PATH_STATE_USE_SUCCEEDED
Definition: origin_circuit_st.h:61
laplace.h
Header for laplace.c.
connection_half_edge_is_valid_resolved
int connection_half_edge_is_valid_resolved(smartlist_t *half_conns, streamid_t stream_id)
Definition: connection_edge.c:802
or_options_t::PathBiasUseThreshold
int PathBiasUseThreshold
Definition: or_options_st.h:910
pathbias_get_min_circs
static int pathbias_get_min_circs(const or_options_t *options)
Definition: circpathbias.c:84
tor_gettimeofday
void tor_gettimeofday(struct timeval *timeval)
Definition: tor_gettimeofday.c:42
circuitstats.h
Header file for circuitstats.c.
origin_circuit_t::pathbias_shouldcount
uint8_t pathbias_shouldcount
Definition: origin_circuit_st.h:180
pathbias_state_to_string
const char * pathbias_state_to_string(path_state_t state)
Definition: circpathbias.c:265
cell_t::payload
uint8_t payload[CELL_PAYLOAD_SIZE]
Definition: cell_st.h:21
get_unique_stream_id_by_circ
streamid_t get_unique_stream_id_by_circ(origin_circuit_t *circ)
Definition: connection_edge.c:3126
entry_guards_changed
void entry_guards_changed(void)
Definition: entrynodes.c:3548
entry_guard_get_by_id_digest
entry_guard_t * entry_guard_get_by_id_digest(const char *digest)
Definition: entrynodes.c:3341
pathbias_mark_use_success
void pathbias_mark_use_success(origin_circuit_t *circ)
Definition: circpathbias.c:661
pathbias_count_collapse
static void pathbias_count_collapse(origin_circuit_t *circ)
Definition: circpathbias.c:1147
relay_header_t::length
uint16_t length
Definition: or.h:643
crypto_rand.h
Common functions for using (pseudo-)random number generators.
pathbias_get_use_success_count
double pathbias_get_use_success_count(entry_guard_t *guard)
Definition: circpathbias.c:1315
get_options
const or_options_t * get_options(void)
Definition: config.c:928
entry_guard_get_pathbias_state
guard_pathbias_t * entry_guard_get_pathbias_state(entry_guard_t *guard)
Definition: entrynodes.c:338
origin_circuit_t::build_state
cpath_build_state_t * build_state
Definition: origin_circuit_st.h:123
circuitbuild.h
Header file for circuitbuild.c.
CIRCUIT_PURPOSE_S_REND_JOINED
#define CIRCUIT_PURPOSE_S_REND_JOINED
Definition: circuitlist.h:112
get_uint32
static uint32_t get_uint32(const void *cp)
Definition: bytes.h:54
pathbias_get_notice_rate
static double pathbias_get_notice_rate(const or_options_t *options)
Definition: circpathbias.c:97
guard_pathbias_t::circ_successes
double circ_successes
Definition: entrynodes.h:50
extend_info_st.h
Extend-info structure.
CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
#define CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
Definition: circuitlist.h:81
pathbias_check_close
int pathbias_check_close(origin_circuit_t *ocirc, int reason)
Definition: circpathbias.c:1015
origin_circuit_t::cpath
crypt_path_t * cpath
Definition: origin_circuit_st.h:129
tor_lround
long tor_lround(double d)
Definition: fp.c:31
TO_ORIGIN_CIRCUIT
origin_circuit_t * TO_ORIGIN_CIRCUIT(circuit_t *x)
Definition: circuitlist.c:168
origin_circuit_t::pathbias_probe_nonce
uint32_t pathbias_probe_nonce
Definition: origin_circuit_st.h:191
pathbias_get_extreme_use_rate
double pathbias_get_extreme_use_rate(const or_options_t *options)
Definition: circpathbias.c:232
relay.h
Header file for relay.c.
relay_header_t
Definition: or.h:638
extend_info_t::identity_digest
char identity_digest[DIGEST_LEN]
Definition: extend_info_st.h:31
CIRCUIT_PURPOSE_S_CONNECT_REND
#define CIRCUIT_PURPOSE_S_CONNECT_REND
Definition: circuitlist.h:109
pathbias_count_use_failed
static void pathbias_count_use_failed(origin_circuit_t *circ)
Definition: circpathbias.c:1183
crypt_path_t::prev
struct crypt_path_t * prev
Definition: crypt_path_st.h:75
PATH_STATE_USE_FAILED
@ PATH_STATE_USE_FAILED
Definition: origin_circuit_st.h:67
pathbias_get_extreme_rate
double pathbias_get_extreme_rate(const or_options_t *options)
Definition: circpathbias.c:125
pathbias_get_close_success_count
double pathbias_get_close_success_count(entry_guard_t *guard)
Definition: circpathbias.c:1297
pathbias_count_build_attempt
int pathbias_count_build_attempt(origin_circuit_t *circ)
Definition: circpathbias.c:424
crypt_path_t::extend_info
extend_info_t * extend_info
Definition: crypt_path_st.h:61
PATH_STATE_USE_ATTEMPTED
@ PATH_STATE_USE_ATTEMPTED
Definition: origin_circuit_st.h:53
SMARTLIST_FOREACH_BEGIN
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
Definition: smartlist_foreach.h:78
CIRCUIT_PURPOSE_TESTING
#define CIRCUIT_PURPOSE_TESTING
Definition: circuitlist.h:118
circuit_read_valid_data
void circuit_read_valid_data(origin_circuit_t *circ, uint16_t relay_body_len)
Definition: circuituse.c:3208
pathbias_count_valid_cells
void pathbias_count_valid_cells(circuit_t *circ, const cell_t *cell)
Definition: circpathbias.c:944
get_uint8
static uint8_t get_uint8(const void *cp)
Definition: bytes.h:23
cell_st.h
Fixed-size cell structure.
pathbias_measure_use_rate
static void pathbias_measure_use_rate(entry_guard_t *guard)
Definition: circpathbias.c:1334
RELAY_HEADER_SIZE
#define RELAY_HEADER_SIZE
Definition: or.h:604
pathbias_count_build_success
void pathbias_count_build_success(origin_circuit_t *circ)
Definition: circpathbias.c:512
crypt_path_t::next
struct crypt_path_t * next
Definition: crypt_path_st.h:72
config.h
Header file for config.c.
entry_guard_get_rsa_id_digest
const char * entry_guard_get_rsa_id_digest(const entry_guard_t *guard)
Definition: entrynodes.c:331
cpath_build_state_t::desired_path_len
int desired_path_len
Definition: cpath_build_state_st.h:18
circuit_state_to_string
const char * circuit_state_to_string(int state)
Definition: circuitlist.c:764
guard_pathbias_t::use_attempts
double use_attempts
Definition: entrynodes.h:61
pathbias_get_warn_rate
static double pathbias_get_warn_rate(const or_options_t *options)
Definition: circpathbias.c:109
guard_pathbias_t::path_bias_warned
unsigned int path_bias_warned
Definition: entrynodes.h:38
pathbias_count_use_success
static void pathbias_count_use_success(origin_circuit_t *circ)
Definition: circpathbias.c:715
or_options_t
Definition: or_options_st.h:45
crypto_rand
void crypto_rand(char *to, size_t n)
Definition: crypto_rand.c:477
networkstatus_get_param
int32_t networkstatus_get_param(const networkstatus_t *ns, const char *param_name, int32_t default_val, int32_t min_val, int32_t max_val)
Definition: networkstatus.c:2495
guard_pathbias_t::timeouts
double timeouts
Definition: entrynodes.h:59
pathbias_get_scale_ratio
static double pathbias_get_scale_ratio(const or_options_t *options)
Definition: circpathbias.c:177
origin_circuit_st.h
Origin circuit structure.
PATH_STATE_NEW_CIRC
@ PATH_STATE_NEW_CIRC
Definition: origin_circuit_st.h:39
pathbias_mark_use_rollback
void pathbias_mark_use_rollback(origin_circuit_t *circ)
Definition: circpathbias.c:700
pathbias_get_scale_threshold
static int pathbias_get_scale_threshold(const or_options_t *options)
Definition: circpathbias.c:158
fast_memeq
#define fast_memeq(a, b, c)
Definition: di_ops.h:35
circuit_t::state
uint8_t state
Definition: circuit_st.h:110
pathbias_should_count
static int pathbias_should_count(origin_circuit_t *circ)
Definition: circpathbias.c:323
CIRCUIT_PURPOSE_C_INTRODUCING
#define CIRCUIT_PURPOSE_C_INTRODUCING
Definition: circuitlist.h:75
circuit_purpose_to_string
const char * circuit_purpose_to_string(uint8_t purpose)
Definition: circuitlist.c:905
ratelim_t
Definition: ratelim.h:42
or.h
Master header file for Tor-specific functionality.
LD_PROTOCOL
#define LD_PROTOCOL
Definition: log.h:72