Tor  0.4.4.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  tor_snprintf(payload,RELAY_PAYLOAD_SIZE, "%s:25", probe_nonce);
830  payload_len = (int)strlen(payload)+1;
831 
832  // XXX: need this? Can we assume ipv4 will always be supported?
833  // If not, how do we tell?
834  //if (payload_len <= RELAY_PAYLOAD_SIZE - 4 && edge_conn->begincell_flags) {
835  // set_uint32(payload + payload_len, htonl(edge_conn->begincell_flags));
836  // payload_len += 4;
837  //}
838 
839  /* Generate+Store stream id, make sure it's non-zero */
841 
842  if (ocirc->pathbias_probe_id==0) {
843  log_warn(LD_CIRC,
844  "Ran out of stream IDs on circuit %u during "
845  "pathbias probe attempt.", ocirc->global_identifier);
846  tor_free(probe_nonce);
847  return -1;
848  }
849 
850  log_info(LD_CIRC,
851  "Sending pathbias testing cell to %s:25 on stream %d for circ %d.",
852  probe_nonce, ocirc->pathbias_probe_id, ocirc->global_identifier);
853  tor_free(probe_nonce);
854 
855  /* Send a test relay cell */
856  if (relay_send_command_from_edge(ocirc->pathbias_probe_id, circ,
857  RELAY_COMMAND_BEGIN, payload,
858  payload_len, cpath_layer) < 0) {
859  log_notice(LD_CIRC,
860  "Failed to send pathbias probe cell on circuit %d.",
861  ocirc->global_identifier);
862  return -1;
863  }
864 
865  /* Mark it freshly dirty so it doesn't get expired in the meantime */
866  circ->timestamp_dirty = time(NULL);
867 
868  return 0;
869 }
870 
871 /**
872  * Check the response to a pathbias probe, to ensure the
873  * cell is recognized and the nonce and other probe
874  * characteristics are as expected.
875  *
876  * If the response is valid, return 0. Otherwise return < 0.
877  */
878 int
880 {
881  /* Based on connection_edge_process_relay_cell() */
882  relay_header_t rh;
883  int reason;
884  uint32_t ipv4_host;
885  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
886 
887  tor_assert(cell);
888  tor_assert(ocirc);
890 
891  relay_header_unpack(&rh, cell->payload);
892 
893  reason = rh.length > 0 ?
894  get_uint8(cell->payload+RELAY_HEADER_SIZE) : END_STREAM_REASON_MISC;
895 
896  if (rh.command == RELAY_COMMAND_END &&
897  reason == END_STREAM_REASON_EXITPOLICY &&
898  ocirc->pathbias_probe_id == rh.stream_id) {
899 
900  /* Check length+extract host: It is in network order after the reason code.
901  * See connection_edge_end(). */
902  if (rh.length < 9) { /* reason+ipv4+dns_ttl */
903  log_notice(LD_PROTOCOL,
904  "Short path bias probe response length field (%d).", rh.length);
905  return - END_CIRC_REASON_TORPROTOCOL;
906  }
907 
908  ipv4_host = ntohl(get_uint32(cell->payload+RELAY_HEADER_SIZE+1));
909 
910  /* Check nonce */
911  if (ipv4_host == ocirc->pathbias_probe_nonce) {
913  circuit_read_valid_data(ocirc, rh.length);
914  circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED);
915  log_info(LD_CIRC,
916  "Got valid path bias probe back for circ %d, stream %d.",
917  ocirc->global_identifier, ocirc->pathbias_probe_id);
918  return 0;
919  } else {
920  log_notice(LD_CIRC,
921  "Got strange probe value 0x%x vs 0x%x back for circ %d, "
922  "stream %d.", ipv4_host, ocirc->pathbias_probe_nonce,
923  ocirc->global_identifier, ocirc->pathbias_probe_id);
924  return -1;
925  }
926  }
927  log_info(LD_CIRC,
928  "Got another cell back back on pathbias probe circuit %d: "
929  "Command: %d, Reason: %d, Stream-id: %d",
930  ocirc->global_identifier, rh.command, reason, rh.stream_id);
931  return -1;
932 }
933 
934 /**
935  * Check if a cell is counts as valid data for a circuit,
936  * and if so, count it as valid.
937  */
938 void
940 {
941  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
942  relay_header_t rh;
943 
944  relay_header_unpack(&rh, cell->payload);
945 
946  /* Check to see if this is a cell from a previous connection,
947  * or is a request to close the circuit. */
948  switch (rh.command) {
949  case RELAY_COMMAND_TRUNCATED:
950  /* Truncated cells can arrive on path bias circs. When they do,
951  * just process them. This closes the circ, but it was junk anyway.
952  * No reason to wait for the probe. */
953  circuit_read_valid_data(ocirc, rh.length);
956 
957  break;
958 
959  case RELAY_COMMAND_END:
961  rh.stream_id)) {
963  }
964  break;
965 
966  case RELAY_COMMAND_DATA:
968  rh.stream_id)) {
970  }
971  break;
972 
973  case RELAY_COMMAND_SENDME:
975  rh.stream_id)) {
977  }
978  break;
979 
980  case RELAY_COMMAND_CONNECTED:
982  rh.stream_id)) {
984  }
985  break;
986 
987  case RELAY_COMMAND_RESOLVED:
989  rh.stream_id)) {
991  }
992  break;
993  }
994 }
995 
996 /**
997  * Check if a circuit was used and/or closed successfully.
998  *
999  * If we attempted to use the circuit to carry a stream but failed
1000  * for whatever reason, or if the circuit mysteriously died before
1001  * we could attach any streams, record these two cases.
1002  *
1003  * If we *have* successfully used the circuit, or it appears to
1004  * have been closed by us locally, count it as a success.
1005  *
1006  * Returns 0 if we're done making decisions with the circ,
1007  * or -1 if we want to probe it first.
1008  */
1009 int
1011 {
1012  circuit_t *circ = &ocirc->base_;
1013 
1014  if (!pathbias_should_count(ocirc)) {
1015  return 0;
1016  }
1017 
1018  switch (ocirc->path_state) {
1019  /* If the circuit was closed after building, but before use, we need
1020  * to ensure we were the ones who tried to close it (and not a remote
1021  * actor). */
1023  if (reason & END_CIRC_REASON_FLAG_REMOTE) {
1024  /* Remote circ close reasons on an unused circuit all could be bias */
1025  log_info(LD_CIRC,
1026  "Circuit %d remote-closed without successful use for reason %d. "
1027  "Circuit purpose %d currently %d,%s. Len %d.",
1028  ocirc->global_identifier,
1029  reason, circ->purpose, ocirc->has_opened,
1031  ocirc->build_state->desired_path_len);
1032  pathbias_count_collapse(ocirc);
1033  } else if ((reason & ~END_CIRC_REASON_FLAG_REMOTE)
1034  == END_CIRC_REASON_CHANNEL_CLOSED &&
1035  circ->n_chan &&
1036  circ->n_chan->reason_for_closing
1037  != CHANNEL_CLOSE_REQUESTED) {
1038  /* If we didn't close the channel ourselves, it could be bias */
1039  /* XXX: Only count bias if the network is live?
1040  * What about clock jumps/suspends? */
1041  log_info(LD_CIRC,
1042  "Circuit %d's channel closed without successful use for reason "
1043  "%d, channel reason %d. Circuit purpose %d currently %d,%s. Len "
1044  "%d.", ocirc->global_identifier,
1045  reason, circ->n_chan->reason_for_closing,
1046  circ->purpose, ocirc->has_opened,
1048  ocirc->build_state->desired_path_len);
1049  pathbias_count_collapse(ocirc);
1050  } else {
1052  }
1053  break;
1054 
1055  /* If we tried to use a circuit but failed, we should probe it to ensure
1056  * it has not been tampered with. */
1058  /* XXX: Only probe and/or count failure if the network is live?
1059  * What about clock jumps/suspends? */
1060  if (pathbias_send_usable_probe(circ) == 0)
1061  return -1;
1062  else
1064 
1065  /* Any circuit where there were attempted streams but no successful
1066  * streams could be bias */
1067  log_info(LD_CIRC,
1068  "Circuit %d closed without successful use for reason %d. "
1069  "Circuit purpose %d currently %d,%s. Len %d.",
1070  ocirc->global_identifier,
1071  reason, circ->purpose, ocirc->has_opened,
1073  ocirc->build_state->desired_path_len);
1074  break;
1075 
1079  break;
1080 
1081  case PATH_STATE_USE_FAILED:
1083  break;
1084 
1085  case PATH_STATE_NEW_CIRC:
1088  default:
1089  // Other states are uninteresting. No stats to count.
1090  break;
1091  }
1092 
1094 
1095  return 0;
1096 }
1097 
1098 /**
1099  * Count a successfully closed circuit.
1100  */
1101 static void
1103 {
1104  entry_guard_t *guard = NULL;
1105  if (!pathbias_should_count(circ)) {
1106  return;
1107  }
1108 
1109  if (circ->cpath && circ->cpath->extend_info) {
1112  }
1113 
1114  if (guard) {
1116 
1117  /* In the long run: circuit_success ~= successful_circuit_close +
1118  * circ_failure + stream_failure */
1121  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
1122  /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1123  * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1124  * No need to log that case. */
1125  log_info(LD_CIRC,
1126  "Successfully closed circuit has no known guard. "
1127  "Circuit is a %s currently %s",
1128  circuit_purpose_to_string(circ->base_.purpose),
1129  circuit_state_to_string(circ->base_.state));
1130  }
1131 }
1132 
1133 /**
1134  * Count a circuit that fails after it is built, but before it can
1135  * carry any traffic.
1136  *
1137  * This is needed because there are ways to destroy a
1138  * circuit after it has successfully completed. Right now, this is
1139  * used for purely informational/debugging purposes.
1140  */
1141 static void
1143 {
1144  entry_guard_t *guard = NULL;
1145 
1146  if (!pathbias_should_count(circ)) {
1147  return;
1148  }
1149 
1150  if (circ->cpath && circ->cpath->extend_info) {
1153  }
1154 
1155  if (guard) {
1157 
1158  pb->collapsed_circuits++;
1160  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
1161  /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1162  * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1163  * No need to log that case. */
1164  log_info(LD_CIRC,
1165  "Destroyed circuit has no known guard. "
1166  "Circuit is a %s currently %s",
1167  circuit_purpose_to_string(circ->base_.purpose),
1168  circuit_state_to_string(circ->base_.state));
1169  }
1170 }
1171 
1172 /**
1173  * Count a known failed circuit (because we could not probe it).
1174  *
1175  * This counter is informational.
1176  */
1177 static void
1179 {
1180  entry_guard_t *guard = NULL;
1181  if (!pathbias_should_count(circ)) {
1182  return;
1183  }
1184 
1185  if (circ->cpath && circ->cpath->extend_info) {
1188  }
1189 
1190  if (guard) {
1192 
1193  pb->unusable_circuits++;
1195  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
1196  /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1197  * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1198  * No need to log that case. */
1199  /* XXX note cut-and-paste code in this function compared to nearby
1200  * functions. Would be nice to refactor. -RD */
1201  log_info(LD_CIRC,
1202  "Stream-failing circuit has no known guard. "
1203  "Circuit is a %s currently %s",
1204  circuit_purpose_to_string(circ->base_.purpose),
1205  circuit_state_to_string(circ->base_.state));
1206  }
1207 }
1208 
1209 /**
1210  * Count timeouts for path bias log messages.
1211  *
1212  * These counts are purely informational.
1213  */
1214 void
1216 {
1217  entry_guard_t *guard = NULL;
1218 
1219  if (!pathbias_should_count(circ)) {
1220  return;
1221  }
1222 
1223  /* For hidden service circs, they can actually be used
1224  * successfully and then time out later (because
1225  * the other side declines to use them). */
1226  if (circ->path_state == PATH_STATE_USE_SUCCEEDED) {
1227  return;
1228  }
1229 
1230  if (circ->cpath && circ->cpath->extend_info) {
1233  }
1234 
1235  if (guard) {
1237 
1238  pb->timeouts++;
1240  }
1241 }
1242 
1243 /**
1244  * Helper function to count all of the currently opened circuits
1245  * for a guard that are in a given path state range. The state
1246  * range is inclusive on both ends.
1247  */
1248 static int
1249 pathbias_count_circs_in_states(entry_guard_t *guard,
1250  path_state_t from,
1251  path_state_t to)
1252 {
1253  int open_circuits = 0;
1254 
1255  /* Count currently open circuits. Give them the benefit of the doubt. */
1257  origin_circuit_t *ocirc = NULL;
1258  if (!CIRCUIT_IS_ORIGIN(circ) || /* didn't originate here */
1259  circ->marked_for_close) /* already counted */
1260  continue;
1261 
1262  ocirc = TO_ORIGIN_CIRCUIT(circ);
1263 
1264  if (!ocirc->cpath || !ocirc->cpath->extend_info)
1265  continue;
1266 
1267  if (ocirc->path_state >= from &&
1268  ocirc->path_state <= to &&
1269  pathbias_should_count(ocirc) &&
1272  DIGEST_LEN)) {
1273  log_debug(LD_CIRC, "Found opened circuit %d in path_state %s",
1274  ocirc->global_identifier,
1276  open_circuits++;
1277  }
1278  }
1279  SMARTLIST_FOREACH_END(circ);
1280 
1281  return open_circuits;
1282 }
1283 
1284 /**
1285  * Return the number of circuits counted as successfully closed for
1286  * this guard.
1287  *
1288  * Also add in the currently open circuits to give them the benefit
1289  * of the doubt.
1290  */
1291 double
1293 {
1295 
1296  return pb->successful_circuits_closed +
1300 }
1301 
1302 /**
1303  * Return the number of circuits counted as successfully used
1304  * this guard.
1305  *
1306  * Also add in the currently open circuits that we are attempting
1307  * to use to give them the benefit of the doubt.
1308  */
1309 double
1310 pathbias_get_use_success_count(entry_guard_t *guard)
1311 {
1313 
1314  return pb->use_successes +
1318 }
1319 
1320 /**
1321  * Check the path bias use rate against our consensus parameter limits.
1322  *
1323  * Emits a log message if the use success rates are too low.
1324  *
1325  * If pathbias_get_dropguards() is set, we also disable the use of
1326  * very failure prone guards.
1327  */
1328 static void
1329 pathbias_measure_use_rate(entry_guard_t *guard)
1330 {
1331  const or_options_t *options = get_options();
1333 
1334  if (pb->use_attempts > pathbias_get_min_use(options)) {
1335  /* Note: We rely on the < comparison here to allow us to set a 0
1336  * rate and disable the feature entirely. If refactoring, don't
1337  * change to <= */
1339  < pathbias_get_extreme_use_rate(options)) {
1340  /* Dropping is currently disabled by default. */
1341  if (pathbias_get_dropguards(options)) {
1342  if (!pb->path_bias_disabled) {
1343  log_warn(LD_CIRC,
1344  "Guard %s is failing to carry an extremely large "
1345  "amount of stream on its circuits. "
1346  "To avoid potential route manipulation attacks, Tor has "
1347  "disabled use of this guard. "
1348  "Use counts are %ld/%ld. Success counts are %ld/%ld. "
1349  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1350  "and %ld timed out. "
1351  "For reference, your timeout cutoff is %ld seconds.",
1352  entry_guard_describe(guard),
1354  tor_lround(pb->use_attempts),
1360  tor_lround(pb->timeouts),
1362  pb->path_bias_disabled = 1;
1363  return;
1364  }
1365  } else if (!pb->path_bias_use_extreme) {
1366  pb->path_bias_use_extreme = 1;
1367  log_warn(LD_CIRC,
1368  "Guard %s is failing to carry an extremely large "
1369  "amount of streams on its circuits. "
1370  "This could indicate a route manipulation attack, network "
1371  "overload, bad local network connectivity, or a bug. "
1372  "Use counts are %ld/%ld. Success counts are %ld/%ld. "
1373  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1374  "and %ld timed out. "
1375  "For reference, your timeout cutoff is %ld seconds.",
1376  entry_guard_describe(guard),
1378  tor_lround(pb->use_attempts),
1384  tor_lround(pb->timeouts),
1386  }
1387  } else if (pathbias_get_use_success_count(guard)/pb->use_attempts
1388  < pathbias_get_notice_use_rate(options)) {
1389  if (!pb->path_bias_use_noticed) {
1390  pb->path_bias_use_noticed = 1;
1391  log_notice(LD_CIRC,
1392  "Guard %s is failing to carry more streams on its "
1393  "circuits than usual. "
1394  "Most likely this means the Tor network is overloaded "
1395  "or your network connection is poor. "
1396  "Use counts are %ld/%ld. Success counts are %ld/%ld. "
1397  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1398  "and %ld timed out. "
1399  "For reference, your timeout cutoff is %ld seconds.",
1400  entry_guard_describe(guard),
1402  tor_lround(pb->use_attempts),
1408  tor_lround(pb->timeouts),
1410  }
1411  }
1412  }
1413 }
1414 
1415 /**
1416  * Check the path bias circuit close status rates against our consensus
1417  * parameter limits.
1418  *
1419  * Emits a log message if the use success rates are too low.
1420  *
1421  * If pathbias_get_dropguards() is set, we also disable the use of
1422  * very failure prone guards.
1423  *
1424  * XXX: This function shares similar log messages and checks to
1425  * pathbias_measure_use_rate(). It may be possible to combine them
1426  * eventually, especially if we can ever remove the need for 3
1427  * levels of closure warns (if the overall circuit failure rate
1428  * goes down with ntor). One way to do so would be to multiply
1429  * the build rate with the use rate to get an idea of the total
1430  * fraction of the total network paths the user is able to use.
1431  * See ticket #8159.
1432  */
1433 static void
1434 pathbias_measure_close_rate(entry_guard_t *guard)
1435 {
1436  const or_options_t *options = get_options();
1438 
1439  if (pb->circ_attempts > pathbias_get_min_circs(options)) {
1440  /* Note: We rely on the < comparison here to allow us to set a 0
1441  * rate and disable the feature entirely. If refactoring, don't
1442  * change to <= */
1444  < pathbias_get_extreme_rate(options)) {
1445  /* Dropping is currently disabled by default. */
1446  if (pathbias_get_dropguards(options)) {
1447  if (!pb->path_bias_disabled) {
1448  log_warn(LD_CIRC,
1449  "Guard %s is failing an extremely large "
1450  "amount of circuits. "
1451  "To avoid potential route manipulation attacks, Tor has "
1452  "disabled use of this guard. "
1453  "Success counts are %ld/%ld. Use counts are %ld/%ld. "
1454  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1455  "and %ld timed out. "
1456  "For reference, your timeout cutoff is %ld seconds.",
1457  entry_guard_describe(guard),
1461  tor_lround(pb->use_attempts),
1465  tor_lround(pb->timeouts),
1467  pb->path_bias_disabled = 1;
1468  return;
1469  }
1470  } else if (!pb->path_bias_extreme) {
1471  pb->path_bias_extreme = 1;
1472  log_warn(LD_CIRC,
1473  "Guard %s is failing an extremely large "
1474  "amount of circuits. "
1475  "This could indicate a route manipulation attack, "
1476  "extreme network overload, or a bug. "
1477  "Success counts are %ld/%ld. Use counts are %ld/%ld. "
1478  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1479  "and %ld timed out. "
1480  "For reference, your timeout cutoff is %ld seconds.",
1481  entry_guard_describe(guard),
1485  tor_lround(pb->use_attempts),
1489  tor_lround(pb->timeouts),
1491  }
1492  } else if (pathbias_get_close_success_count(guard)/pb->circ_attempts
1493  < pathbias_get_warn_rate(options)) {
1494  if (!pb->path_bias_warned) {
1495  pb->path_bias_warned = 1;
1496  log_warn(LD_CIRC,
1497  "Guard %s is failing a very large "
1498  "amount of circuits. "
1499  "Most likely this means the Tor network is "
1500  "overloaded, but it could also mean an attack against "
1501  "you or potentially the guard itself. "
1502  "Success counts are %ld/%ld. Use counts are %ld/%ld. "
1503  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1504  "and %ld timed out. "
1505  "For reference, your timeout cutoff is %ld seconds.",
1506  entry_guard_describe(guard),
1510  tor_lround(pb->use_attempts),
1514  tor_lround(pb->timeouts),
1516  }
1517  } else if (pathbias_get_close_success_count(guard)/pb->circ_attempts
1518  < pathbias_get_notice_rate(options)) {
1519  if (!pb->path_bias_noticed) {
1520  pb->path_bias_noticed = 1;
1521  log_notice(LD_CIRC,
1522  "Guard %s is failing more circuits than "
1523  "usual. "
1524  "Most likely this means the Tor network is overloaded. "
1525  "Success counts are %ld/%ld. Use counts are %ld/%ld. "
1526  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1527  "and %ld timed out. "
1528  "For reference, your timeout cutoff is %ld seconds.",
1529  entry_guard_describe(guard),
1533  tor_lround(pb->use_attempts),
1537  tor_lround(pb->timeouts),
1539  }
1540  }
1541  }
1542 }
1543 
1544 /**
1545  * This function scales the path bias use rates if we have
1546  * more data than the scaling threshold. This allows us to
1547  * be more sensitive to recent measurements.
1548  *
1549  * XXX: The attempt count transfer stuff here might be done
1550  * better by keeping separate pending counters that get
1551  * transferred at circuit close. See ticket #8160.
1552  */
1553 static void
1554 pathbias_scale_close_rates(entry_guard_t *guard)
1555 {
1556  const or_options_t *options = get_options();
1558 
1559  /* If we get a ton of circuits, just scale everything down */
1560  if (pb->circ_attempts > pathbias_get_scale_threshold(options)) {
1561  double scale_ratio = pathbias_get_scale_ratio(options);
1562  int opened_attempts = pathbias_count_circs_in_states(guard,
1564  int opened_built = pathbias_count_circs_in_states(guard,
1567  /* Verify that the counts are sane before and after scaling */
1568  int counts_are_sane = (pb->circ_attempts >= pb->circ_successes);
1569 
1570  pb->circ_attempts -= (opened_attempts+opened_built);
1571  pb->circ_successes -= opened_built;
1572 
1573  pb->circ_attempts *= scale_ratio;
1574  pb->circ_successes *= scale_ratio;
1575  pb->timeouts *= scale_ratio;
1576  pb->successful_circuits_closed *= scale_ratio;
1577  pb->collapsed_circuits *= scale_ratio;
1578  pb->unusable_circuits *= scale_ratio;
1579 
1580  pb->circ_attempts += (opened_attempts+opened_built);
1581  pb->circ_successes += opened_built;
1582 
1584 
1585  log_info(LD_CIRC,
1586  "Scaled pathbias counts to (%f,%f)/%f (%d/%d open) for guard "
1587  "%s",
1589  pb->circ_attempts, opened_built, opened_attempts,
1590  entry_guard_describe(guard));
1591 
1592  /* Have the counts just become invalid by this scaling attempt? */
1593  if (counts_are_sane && pb->circ_attempts < pb->circ_successes) {
1594  log_notice(LD_BUG,
1595  "Scaling has mangled pathbias counts to %f/%f (%d/%d open) "
1596  "for guard %s",
1597  pb->circ_successes, pb->circ_attempts, opened_built,
1598  opened_attempts,
1599  entry_guard_describe(guard));
1600  }
1601  }
1602 }
1603 
1604 /**
1605  * This function scales the path bias circuit close rates if we have
1606  * more data than the scaling threshold. This allows us to be more
1607  * sensitive to recent measurements.
1608  *
1609  * XXX: The attempt count transfer stuff here might be done
1610  * better by keeping separate pending counters that get
1611  * transferred at circuit close. See ticket #8160.
1612  */
1613 void
1614 pathbias_scale_use_rates(entry_guard_t *guard)
1615 {
1616  const or_options_t *options = get_options();
1618 
1619  /* If we get a ton of circuits, just scale everything down */
1620  if (pb->use_attempts > pathbias_get_scale_use_threshold(options)) {
1621  double scale_ratio = pathbias_get_scale_ratio(options);
1622  int opened_attempts = pathbias_count_circs_in_states(guard,
1624  /* Verify that the counts are sane before and after scaling */
1625  int counts_are_sane = (pb->use_attempts >= pb->use_successes);
1626 
1627  pb->use_attempts -= opened_attempts;
1628 
1629  pb->use_attempts *= scale_ratio;
1630  pb->use_successes *= scale_ratio;
1631 
1632  pb->use_attempts += opened_attempts;
1633 
1634  log_info(LD_CIRC,
1635  "Scaled pathbias use counts to %f/%f (%d open) for guard %s",
1636  pb->use_successes, pb->use_attempts, opened_attempts,
1637  entry_guard_describe(guard));
1638 
1639  /* Have the counts just become invalid by this scaling attempt? */
1640  if (counts_are_sane && pb->use_attempts < pb->use_successes) {
1641  log_notice(LD_BUG,
1642  "Scaling has mangled pathbias usage counts to %f/%f "
1643  "(%d open) for guard %s",
1644  pb->circ_successes, pb->circ_attempts,
1645  opened_attempts, entry_guard_describe(guard));
1646  }
1647 
1649  }
1650 }
#define RELAY_PAYLOAD_SIZE
Definition: or.h:605
#define CIRCUIT_PURPOSE_C_INTRODUCING
Definition: circuitlist.h:75
Header file for circuitstats.c.
static int pathbias_count_circs_in_states(entry_guard_t *guard, path_state_t from, path_state_t to)
void crypto_rand(char *to, size_t n)
Definition: crypto_rand.c:477
#define CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
Definition: circuitlist.h:95
char identity_digest[DIGEST_LEN]
static int entry_guard_inc_circ_attempt_count(entry_guard_t *guard)
Definition: circpathbias.c:61
void pathbias_count_build_success(origin_circuit_t *circ)
Definition: circpathbias.c:512
channel_t * n_chan
Definition: circuit_st.h:69
static int pathbias_is_new_circ_attempt(origin_circuit_t *circ)
Definition: circpathbias.c:296
Header file for circuitbuild.c.
Common functions for using (pseudo-)random number generators.
double use_attempts
Definition: entrynodes.h:61
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
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)
extend_info_t * extend_info
Definition: crypt_path_st.h:61
uint32_t pathbias_probe_nonce
Header for laplace.c.
enum channel_t::@8 reason_for_closing
static double pathbias_get_warn_rate(const or_options_t *options)
Definition: circpathbias.c:109
void pathbias_count_timeout(origin_circuit_t *circ)
static void pathbias_count_use_success(origin_circuit_t *circ)
Definition: circpathbias.c:715
Definition: cell_st.h:17
static void pathbias_scale_close_rates(entry_guard_t *guard)
#define CIRCUIT_IS_ORIGIN(c)
Definition: circuitlist.h:146
Path structures for origin circuits.
streamid_t stream_id
Definition: or.h:640
int PathBiasUseThreshold
const char * circuit_purpose_to_string(uint8_t purpose)
Definition: circuitlist.c:900
streamid_t get_unique_stream_id_by_circ(origin_circuit_t *circ)
uint8_t state
Definition: circuit_st.h:110
uint8_t purpose
Definition: circuit_st.h:111
void relay_header_unpack(relay_header_t *dest, const uint8_t *src)
Definition: relay.c:488
double unusable_circuits
Definition: entrynodes.h:57
double circ_attempts
Definition: entrynodes.h:49
int pathbias_get_dropguards(const or_options_t *options)
Definition: circpathbias.c:141
unsigned int path_bias_extreme
Definition: entrynodes.h:40
char * rate_limit_log(ratelim_t *lim, time_t now)
Definition: ratelim.c:41
int circuit_truncated(origin_circuit_t *circ, int reason)
struct timeval timestamp_began
Definition: circuit_st.h:165
smartlist_t * half_streams
Header file for config.c.
const or_options_t * get_options(void)
Definition: config.c:926
crypt_path_t * cpath
#define tor_assert(expr)
Definition: util_bug.h:102
struct crypt_path_t * prev
Definition: crypt_path_st.h:75
path_state_t
static void pathbias_measure_close_rate(entry_guard_t *guard)
void tor_gettimeofday(struct timeval *timeval)
unsigned int path_bias_warned
Definition: entrynodes.h:38
#define tor_free(p)
Definition: malloc.h:52
static double pathbias_get_notice_rate(const or_options_t *options)
Definition: circpathbias.c:97
static int pathbias_get_min_circs(const or_options_t *options)
Definition: circpathbias.c:84
#define tor_fragile_assert()
Definition: util_bug.h:246
static int pathbias_get_scale_use_threshold(const or_options_t *options)
Definition: circpathbias.c:250
static void pathbias_scale_use_rates(entry_guard_t *guard)
double successful_circuits_closed
Definition: entrynodes.h:52
uint8_t payload[CELL_PAYLOAD_SIZE]
Definition: cell_st.h:21
unsigned int path_bias_use_noticed
Definition: entrynodes.h:44
#define END_CIRC_REASON_FLAG_REMOTE
Definition: or.h:328
static uint32_t get_uint32(const void *cp)
Definition: bytes.h:54
Circuit-build-stse structure.
int PathBiasCircThreshold
smartlist_t * circuit_get_global_list(void)
Definition: circuitlist.c:691
static uint8_t get_uint8(const void *cp)
Definition: bytes.h:23
const char * entry_guard_describe(const entry_guard_t *guard)
Definition: entrynodes.c:315
static double pathbias_get_notice_use_rate(const or_options_t *options)
Definition: circpathbias.c:216
#define CIRCUIT_PURPOSE_CONTROLLER
Definition: circuitlist.h:120
double pathbias_get_extreme_use_rate(const or_options_t *options)
Definition: circpathbias.c:232
unsigned int path_bias_noticed
Definition: entrynodes.h:36
void entry_guards_changed(void)
Definition: entrynodes.c:3430
Header file for channel.c.
streamid_t pathbias_probe_id
int connection_half_edge_is_valid_sendme(const smartlist_t *half_conns, streamid_t stream_id)
Header for fp.c.
#define LD_CIRC
Definition: log.h:82
long tor_lround(double d)
Definition: fp.c:31
#define DIGEST_LEN
Definition: digest_sizes.h:20
#define CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
Definition: circuitlist.h:81
Origin circuit structure.
#define CIRCUIT_PURPOSE_TESTING
Definition: circuitlist.h:118
Master header file for Tor-specific functionality.
Header file for circuitbuild.c.
static void pathbias_measure_use_rate(entry_guard_t *guard)
static void pathbias_count_collapse(origin_circuit_t *circ)
void pathbias_mark_use_rollback(origin_circuit_t *circ)
Definition: circpathbias.c:700
entry_guard_t * entry_guard_get_by_id_digest(const char *digest)
Definition: entrynodes.c:3223
Header file for circuituse.c.
Extend-info structure.
unsigned int path_bias_disabled
Definition: entrynodes.h:42
double pathbias_get_close_success_count(entry_guard_t *guard)
int pathbias_check_probe_response(circuit_t *circ, const cell_t *cell)
Definition: circpathbias.c:879
#define CIRCUIT_PURPOSE_S_CONNECT_REND
Definition: circuitlist.h:109
Header file for circuitlist.c.
#define CIRCUIT_PURPOSE_PATH_BIAS_TESTING
Definition: circuitlist.h:122
double pathbias_get_extreme_rate(const or_options_t *options)
Definition: circpathbias.c:125
Fixed-size cell structure.
int pathbias_check_close(origin_circuit_t *ocirc, int reason)
static double pathbias_get_scale_ratio(const or_options_t *options)
Definition: circpathbias.c:177
Header file for connection_edge.c.
static int pathbias_get_scale_threshold(const or_options_t *options)
Definition: circpathbias.c:158
static int pathbias_send_usable_probe(circuit_t *circ)
Definition: circpathbias.c:776
double circ_successes
Definition: entrynodes.h:50
origin_circuit_t * TO_ORIGIN_CIRCUIT(circuit_t *x)
Definition: circuitlist.c:165
static int pathbias_should_count(origin_circuit_t *circ)
Definition: circpathbias.c:323
const char * circuit_state_to_string(int state)
Definition: circuitlist.c:759
int tor_snprintf(char *str, size_t size, const char *format,...)
Definition: printf.c:27
#define CELL_PAYLOAD_SIZE
Definition: or.h:576
path_state_bitfield_t path_state
Header file for relay.c.
cpath_build_state_t * build_state
uint16_t length
Definition: or.h:642
int connection_half_edge_is_valid_end(smartlist_t *half_conns, streamid_t stream_id)
double get_circuit_build_close_time_ms(void)
Definition: circuitstats.c:97
time_t approx_time(void)
Definition: approx_time.c:32
time_t timestamp_dirty
Definition: circuit_st.h:187
const char * pathbias_state_to_string(path_state_t state)
Definition: circpathbias.c:265
void pathbias_count_use_attempt(origin_circuit_t *circ)
Definition: circpathbias.c:604
void circuit_change_purpose(circuit_t *circ, uint8_t new_purpose)
Definition: circuituse.c:3095
int connection_half_edge_is_valid_resolved(smartlist_t *half_conns, streamid_t stream_id)
int pathbias_count_build_attempt(origin_circuit_t *circ)
Definition: circpathbias.c:424
struct crypt_path_t * next
Definition: crypt_path_st.h:72
void circuit_read_valid_data(origin_circuit_t *circ, uint16_t relay_body_len)
Definition: circuituse.c:3184
double pathbias_get_use_success_count(entry_guard_t *guard)
static void pathbias_count_successful_close(origin_circuit_t *circ)
void pathbias_count_valid_cells(circuit_t *circ, const cell_t *cell)
Definition: circpathbias.c:939
#define CIRCUIT_PURPOSE_S_REND_JOINED
Definition: circuitlist.h:112
unsigned int path_bias_use_extreme
Definition: entrynodes.h:46
#define LD_PROTOCOL
Definition: log.h:72
static int pathbias_get_min_use(const or_options_t *options)
Definition: circpathbias.c:203
#define RELAY_HEADER_SIZE
Definition: or.h:603
void pathbias_mark_use_success(origin_circuit_t *circ)
Definition: circpathbias.c:661
uint8_t command
Definition: or.h:638
guard_pathbias_t * entry_guard_get_pathbias_state(entry_guard_t *guard)
Definition: entrynodes.c:334
Header file for networkstatus.c.
#define LD_BUG
Definition: log.h:86
static void pathbias_count_use_failed(origin_circuit_t *circ)
char identity_digest[DIGEST_LEN]
Definition: channel.h:383
uint8_t state
Definition: crypt_path_st.h:68
int connection_half_edge_is_valid_connected(const smartlist_t *half_conns, streamid_t stream_id)
int connection_half_edge_is_valid_data(const smartlist_t *half_conns, streamid_t stream_id)
unsigned int has_opened
double collapsed_circuits
Definition: entrynodes.h:54
const char * entry_guard_get_rsa_id_digest(const entry_guard_t *guard)
Definition: entrynodes.c:327
#define fast_memeq(a, b, c)
Definition: di_ops.h:35
double use_successes
Definition: entrynodes.h:62
char * tor_dup_ip(uint32_t addr)
Definition: address.c:1948