Tor  0.4.8.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-2021, 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  /* Ignore circuits where the controller helped choose the path. When
367  * this happens, we can't be sure whether the path was chosen randomly
368  * or not. */
369  if (circ->any_hop_from_controller) {
370  /* (In this case, we _don't_ check to see if shouldcount is changing,
371  * since it's possible that an already-created circuit later gets extended
372  * by the controller. */
373  circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_IGNORED;
374  return 0;
375  }
376 
377  /* Completely ignore one hop circuits */
378  if (circ->build_state->onehop_tunnel ||
379  circ->build_state->desired_path_len == 1) {
380  /* Check for inconsistency */
381  if (circ->build_state->desired_path_len != 1 ||
382  !circ->build_state->onehop_tunnel) {
383  if ((rate_msg = rate_limit_log(&count_limit, approx_time()))) {
384  log_info(LD_BUG,
385  "One-hop circuit %d has length %d. Path state is %s. "
386  "Circuit is a %s currently %s.%s",
387  circ->global_identifier,
390  circuit_purpose_to_string(circ->base_.purpose),
391  circuit_state_to_string(circ->base_.state),
392  rate_msg);
393  tor_free(rate_msg);
394  }
396  }
397 
398  /* Check to see if the shouldcount result has changed due to a
399  * unexpected change that would affect our results */
400  if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_COUNTED) {
401  log_info(LD_BUG,
402  "One-hop circuit %d is now being ignored despite being counted "
403  "in the past. Purpose is %s, path state is %s",
404  circ->global_identifier,
405  circuit_purpose_to_string(circ->base_.purpose),
407  }
408  circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_IGNORED;
409  return 0;
410  }
411 
412  /* Check to see if the shouldcount result has changed due to a
413  * unexpected purpose change that would affect our results */
414  if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_IGNORED) {
415  log_info(LD_CIRC,
416  "Circuit %d is not being counted by pathbias because it was "
417  "ignored in the past. Purpose is %s, path state is %s",
418  circ->global_identifier,
419  circuit_purpose_to_string(circ->base_.purpose),
421  return 0;
422  }
423  circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_COUNTED;
424 
425  return 1;
426 }
427 
428 /**
429  * Check our circuit state to see if this is a successful circuit attempt.
430  * If so, record it in the current guard's path bias circ_attempt count.
431  *
432  * Also check for several potential error cases for bug #6475.
433  */
434 int
436 {
437 #define CIRC_ATTEMPT_NOTICE_INTERVAL (600)
438  static ratelim_t circ_attempt_notice_limit =
439  RATELIM_INIT(CIRC_ATTEMPT_NOTICE_INTERVAL);
440  char *rate_msg = NULL;
441 
442  if (!pathbias_should_count(circ)) {
443  return 0;
444  }
445 
446  if (pathbias_is_new_circ_attempt(circ)) {
447  /* Help track down the real cause of bug #6475: */
448  if (circ->has_opened && circ->path_state != PATH_STATE_BUILD_ATTEMPTED) {
449  if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
450  approx_time()))) {
451  log_info(LD_BUG,
452  "Opened circuit %d is in strange path state %s. "
453  "Circuit is a %s currently %s.%s",
454  circ->global_identifier,
456  circuit_purpose_to_string(circ->base_.purpose),
457  circuit_state_to_string(circ->base_.state),
458  rate_msg);
459  tor_free(rate_msg);
460  }
461  }
462 
463  /* Don't re-count cannibalized circs.. */
464  if (!circ->has_opened) {
465  entry_guard_t *guard = NULL;
466 
467  if (circ->cpath && circ->cpath->extend_info) {
470  } else if (circ->base_.n_chan) {
471  guard =
473  }
474 
475  if (guard) {
476  if (circ->path_state == PATH_STATE_NEW_CIRC) {
478 
479  if (entry_guard_inc_circ_attempt_count(guard) < 0) {
480  /* Bogus guard; we already warned. */
481  return -END_CIRC_REASON_TORPROTOCOL;
482  }
483  } else {
484  if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
485  approx_time()))) {
486  log_info(LD_BUG,
487  "Unopened circuit %d has strange path state %s. "
488  "Circuit is a %s currently %s.%s",
489  circ->global_identifier,
491  circuit_purpose_to_string(circ->base_.purpose),
492  circuit_state_to_string(circ->base_.state),
493  rate_msg);
494  tor_free(rate_msg);
495  }
496  }
497  } else {
498  if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
499  approx_time()))) {
500  log_info(LD_CIRC,
501  "Unopened circuit has no known guard. "
502  "Circuit is a %s currently %s.%s",
503  circuit_purpose_to_string(circ->base_.purpose),
504  circuit_state_to_string(circ->base_.state),
505  rate_msg);
506  tor_free(rate_msg);
507  }
508  }
509  }
510  }
511 
512  return 0;
513 }
514 
515 /**
516  * Check our circuit state to see if this is a successful circuit
517  * completion. If so, record it in the current guard's path bias
518  * success count.
519  *
520  * Also check for several potential error cases for bug #6475.
521  */
522 void
524 {
525 #define SUCCESS_NOTICE_INTERVAL (600)
526  static ratelim_t success_notice_limit =
527  RATELIM_INIT(SUCCESS_NOTICE_INTERVAL);
528  char *rate_msg = NULL;
529  entry_guard_t *guard = NULL;
530 
531  if (!pathbias_should_count(circ)) {
532  return;
533  }
534 
535  /* Don't count cannibalized/reused circs for path bias
536  * "build" success, since they get counted under "use" success. */
537  if (!circ->has_opened) {
538  if (circ->cpath && circ->cpath->extend_info) {
541  }
542 
543  if (guard) {
545 
546  if (circ->path_state == PATH_STATE_BUILD_ATTEMPTED) {
548  pb->circ_successes++;
550 
551  log_info(LD_CIRC, "Got success count %f/%f for guard %s",
552  pb->circ_successes, pb->circ_attempts,
553  entry_guard_describe(guard));
554  } else {
555  if ((rate_msg = rate_limit_log(&success_notice_limit,
556  approx_time()))) {
557  log_info(LD_BUG,
558  "Succeeded circuit %d is in strange path state %s. "
559  "Circuit is a %s currently %s.%s",
560  circ->global_identifier,
562  circuit_purpose_to_string(circ->base_.purpose),
563  circuit_state_to_string(circ->base_.state),
564  rate_msg);
565  tor_free(rate_msg);
566  }
567  }
568 
569  if (pb->circ_attempts < pb->circ_successes) {
570  log_notice(LD_BUG, "Unexpectedly high successes counts (%f/%f) "
571  "for guard %s",
572  pb->circ_successes, pb->circ_attempts,
573  entry_guard_describe(guard));
574  }
575  /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
576  * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
577  * No need to log that case. */
578  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
579  if ((rate_msg = rate_limit_log(&success_notice_limit,
580  approx_time()))) {
581  log_info(LD_CIRC,
582  "Completed circuit has no known guard. "
583  "Circuit is a %s currently %s.%s",
584  circuit_purpose_to_string(circ->base_.purpose),
585  circuit_state_to_string(circ->base_.state),
586  rate_msg);
587  tor_free(rate_msg);
588  }
589  }
590  } else {
592  if ((rate_msg = rate_limit_log(&success_notice_limit,
593  approx_time()))) {
594  log_info(LD_BUG,
595  "Opened circuit %d is in strange path state %s. "
596  "Circuit is a %s currently %s.%s",
597  circ->global_identifier,
599  circuit_purpose_to_string(circ->base_.purpose),
600  circuit_state_to_string(circ->base_.state),
601  rate_msg);
602  tor_free(rate_msg);
603  }
604  }
605  }
606 }
607 
608 /**
609  * Record an attempt to use a circuit. Changes the circuit's
610  * path state and update its guard's usage counter.
611  *
612  * Used for path bias usage accounting.
613  */
614 void
616 {
617  if (!pathbias_should_count(circ)) {
618  return;
619  }
620 
622  log_notice(LD_BUG,
623  "Used circuit %d is in strange path state %s. "
624  "Circuit is a %s currently %s.",
625  circ->global_identifier,
627  circuit_purpose_to_string(circ->base_.purpose),
628  circuit_state_to_string(circ->base_.state));
629  } else if (circ->path_state < PATH_STATE_USE_ATTEMPTED) {
630  entry_guard_t *guard = entry_guard_get_by_id_digest(
632  if (guard) {
634 
637  pb->use_attempts++;
639 
640  log_debug(LD_CIRC,
641  "Marked circuit %d (%f/%f) as used for guard %s.",
642  circ->global_identifier,
643  pb->use_successes, pb->use_attempts,
644  entry_guard_describe(guard));
645  }
646 
648  } else {
649  /* Harmless but educational log message */
650  log_info(LD_CIRC,
651  "Used circuit %d is already in path state %s. "
652  "Circuit is a %s currently %s.",
653  circ->global_identifier,
655  circuit_purpose_to_string(circ->base_.purpose),
656  circuit_state_to_string(circ->base_.state));
657  }
658 
659  return;
660 }
661 
662 /**
663  * Check the circuit's path state is appropriate and mark it as
664  * successfully used. Used for path bias usage accounting.
665  *
666  * We don't actually increment the guard's counters until
667  * pathbias_check_close(), because the circuit can still transition
668  * back to PATH_STATE_USE_ATTEMPTED if a stream fails later (this
669  * is done so we can probe the circuit for liveness at close).
670  */
671 void
673 {
674  if (!pathbias_should_count(circ)) {
675  return;
676  }
677 
678  if (circ->path_state < PATH_STATE_USE_ATTEMPTED) {
679  log_notice(LD_BUG,
680  "Used circuit %d is in strange path state %s. "
681  "Circuit is a %s currently %s.",
682  circ->global_identifier,
684  circuit_purpose_to_string(circ->base_.purpose),
685  circuit_state_to_string(circ->base_.state));
686 
688  }
689 
690  /* We don't do any accounting at the guard until actual circuit close */
692 
693  return;
694 }
695 
696 /**
697  * If a stream ever detaches from a circuit in a retriable way,
698  * we need to mark this circuit as still needing either another
699  * successful stream, or in need of a probe.
700  *
701  * An adversary could let the first stream request succeed (ie the
702  * resolve), but then tag and timeout the remainder (via cell
703  * dropping), forcing them on new circuits.
704  *
705  * Rolling back the state will cause us to probe such circuits, which
706  * should lead to probe failures in the event of such tagging due to
707  * either unrecognized cells coming in while we wait for the probe,
708  * or the cipher state getting out of sync in the case of dropped cells.
709  */
710 void
712 {
713  if (circ->path_state == PATH_STATE_USE_SUCCEEDED) {
714  log_info(LD_CIRC,
715  "Rolling back pathbias use state to 'attempted' for detached "
716  "circuit %d", circ->global_identifier);
718  }
719 }
720 
721 /**
722  * Actually count a circuit success towards a guard's usage counters
723  * if the path state is appropriate.
724  */
725 static void
727 {
728  entry_guard_t *guard;
729 
730  if (!pathbias_should_count(circ)) {
731  return;
732  }
733 
734  if (circ->path_state != PATH_STATE_USE_SUCCEEDED) {
735  log_notice(LD_BUG,
736  "Successfully used circuit %d is in strange path state %s. "
737  "Circuit is a %s currently %s.",
738  circ->global_identifier,
740  circuit_purpose_to_string(circ->base_.purpose),
741  circuit_state_to_string(circ->base_.state));
742  } else {
745  if (guard) {
747 
748  pb->use_successes++;
750 
751  if (pb->use_attempts < pb->use_successes) {
752  log_notice(LD_BUG, "Unexpectedly high use successes counts (%f/%f) "
753  "for guard %s",
754  pb->use_successes, pb->use_attempts,
755  entry_guard_describe(guard));
756  }
757 
758  log_debug(LD_CIRC,
759  "Marked circuit %d (%f/%f) as used successfully for guard %s",
760  circ->global_identifier, pb->use_successes,
761  pb->use_attempts,
762  entry_guard_describe(guard));
763  }
764  }
765 
766  return;
767 }
768 
769 /**
770  * Send a probe down a circuit that the client attempted to use,
771  * but for which the stream timed out/failed. The probe is a
772  * RELAY_BEGIN cell with a 0.a.b.c destination address, which
773  * the exit will reject and reply back, echoing that address.
774  *
775  * The reason for such probes is because it is possible to bias
776  * a user's paths simply by causing timeouts, and these timeouts
777  * are not possible to differentiate from unresponsive servers.
778  *
779  * The probe is sent at the end of the circuit lifetime for two
780  * reasons: to prevent cryptographic taggers from being able to
781  * drop cells to cause timeouts, and to prevent easy recognition
782  * of probes before any real client traffic happens.
783  *
784  * Returns -1 if we couldn't probe, 0 otherwise.
785  */
786 static int
788 {
789  /* Based on connection_ap_handshake_send_begin() */
790  char payload[CELL_PAYLOAD_SIZE];
791  int payload_len;
792  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
793  crypt_path_t *cpath_layer = NULL;
794  char *probe_nonce = NULL;
795 
796  tor_assert(ocirc);
797 
798  cpath_layer = ocirc->cpath->prev;
799 
800  if (cpath_layer->state != CPATH_STATE_OPEN) {
801  /* This can happen for cannibalized circuits. Their
802  * last hop isn't yet open */
803  log_info(LD_CIRC,
804  "Got pathbias probe request for unopened circuit %d. "
805  "Opened %d, len %d", ocirc->global_identifier,
806  ocirc->has_opened, ocirc->build_state->desired_path_len);
807  return -1;
808  }
809 
810  /* We already went down this road. */
812  ocirc->pathbias_probe_id) {
813  log_info(LD_CIRC,
814  "Got pathbias probe request for circuit %d with "
815  "outstanding probe", ocirc->global_identifier);
816  return -1;
817  }
818 
819  /* Can't probe if the channel isn't open */
820  if (circ->n_chan == NULL ||
821  (!CHANNEL_IS_OPEN(circ->n_chan)
822  && !CHANNEL_IS_MAINT(circ->n_chan))) {
823  log_info(LD_CIRC,
824  "Skipping pathbias probe for circuit %d: Channel is not open.",
825  ocirc->global_identifier);
826  return -1;
827  }
828 
830 
831  /* Update timestamp for when circuit_expire_building() should kill us */
833 
834  /* Generate a random address for the nonce */
835  crypto_rand((char*)&ocirc->pathbias_probe_nonce,
836  sizeof(ocirc->pathbias_probe_nonce));
837  ocirc->pathbias_probe_nonce &= 0x00ffffff;
838  probe_nonce = tor_dup_ip(ocirc->pathbias_probe_nonce);
839 
840  if (!probe_nonce) {
841  log_err(LD_BUG, "Failed to generate nonce");
842  return -1;
843  }
844 
845  tor_snprintf(payload,RELAY_PAYLOAD_SIZE, "%s:25", probe_nonce);
846  payload_len = (int)strlen(payload)+1;
847 
848  // XXX: need this? Can we assume ipv4 will always be supported?
849  // If not, how do we tell?
850  //if (payload_len <= RELAY_PAYLOAD_SIZE - 4 && edge_conn->begincell_flags) {
851  // set_uint32(payload + payload_len, htonl(edge_conn->begincell_flags));
852  // payload_len += 4;
853  //}
854 
855  /* Generate+Store stream id, make sure it's non-zero */
857 
858  if (ocirc->pathbias_probe_id==0) {
859  log_warn(LD_CIRC,
860  "Ran out of stream IDs on circuit %u during "
861  "pathbias probe attempt.", ocirc->global_identifier);
862  tor_free(probe_nonce);
863  return -1;
864  }
865 
866  log_info(LD_CIRC,
867  "Sending pathbias testing cell to %s:25 on stream %d for circ %d.",
868  probe_nonce, ocirc->pathbias_probe_id, ocirc->global_identifier);
869  tor_free(probe_nonce);
870 
871  /* Send a test relay cell */
872  if (relay_send_command_from_edge(ocirc->pathbias_probe_id, circ,
873  RELAY_COMMAND_BEGIN, payload,
874  payload_len, cpath_layer) < 0) {
875  log_notice(LD_CIRC,
876  "Failed to send pathbias probe cell on circuit %d.",
877  ocirc->global_identifier);
878  return -1;
879  }
880 
881  /* Mark it freshly dirty so it doesn't get expired in the meantime */
882  circ->timestamp_dirty = time(NULL);
883 
884  return 0;
885 }
886 
887 /**
888  * Check the response to a pathbias probe, to ensure the
889  * cell is recognized and the nonce and other probe
890  * characteristics are as expected.
891  *
892  * If the response is valid, return 0. Otherwise return < 0.
893  */
894 int
896 {
897  /* Based on connection_edge_process_relay_cell() */
898  relay_header_t rh;
899  int reason;
900  uint32_t ipv4_host;
901  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
902 
903  tor_assert(cell);
904  tor_assert(ocirc);
906 
907  relay_header_unpack(&rh, cell->payload);
908 
909  reason = rh.length > 0 ?
910  get_uint8(cell->payload+RELAY_HEADER_SIZE) : END_STREAM_REASON_MISC;
911 
912  if (rh.command == RELAY_COMMAND_END &&
913  reason == END_STREAM_REASON_EXITPOLICY &&
914  ocirc->pathbias_probe_id == rh.stream_id) {
915 
916  /* Check length+extract host: It is in network order after the reason code.
917  * See connection_edge_end(). */
918  if (rh.length < 9) { /* reason+ipv4+dns_ttl */
919  log_notice(LD_PROTOCOL,
920  "Short path bias probe response length field (%d).", rh.length);
921  return - END_CIRC_REASON_TORPROTOCOL;
922  }
923 
924  ipv4_host = ntohl(get_uint32(cell->payload+RELAY_HEADER_SIZE+1));
925 
926  /* Check nonce */
927  if (ipv4_host == ocirc->pathbias_probe_nonce) {
929  circuit_read_valid_data(ocirc, rh.length);
930  circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED);
931  log_info(LD_CIRC,
932  "Got valid path bias probe back for circ %d, stream %d.",
933  ocirc->global_identifier, ocirc->pathbias_probe_id);
934  return 0;
935  } else {
936  log_notice(LD_CIRC,
937  "Got strange probe value 0x%x vs 0x%x back for circ %d, "
938  "stream %d.", ipv4_host, ocirc->pathbias_probe_nonce,
939  ocirc->global_identifier, ocirc->pathbias_probe_id);
940  return -1;
941  }
942  }
943  log_info(LD_CIRC,
944  "Got another cell back back on pathbias probe circuit %d: "
945  "Command: %d, Reason: %d, Stream-id: %d",
946  ocirc->global_identifier, rh.command, reason, rh.stream_id);
947  return -1;
948 }
949 
950 /**
951  * Check if a cell is counts as valid data for a circuit,
952  * and if so, count it as valid.
953  */
954 void
956 {
957  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
958  relay_header_t rh;
959 
960  relay_header_unpack(&rh, cell->payload);
961 
962  /* Check to see if this is a cell from a previous connection,
963  * or is a request to close the circuit. */
964  switch (rh.command) {
965  case RELAY_COMMAND_TRUNCATED:
966  /* Truncated cells can arrive on path bias circs. When they do,
967  * just process them. This closes the circ, but it was junk anyway.
968  * No reason to wait for the probe. */
969  circuit_read_valid_data(ocirc, rh.length);
972 
973  break;
974 
975  case RELAY_COMMAND_END:
977  rh.stream_id)) {
979  }
980  break;
981 
982  case RELAY_COMMAND_DATA:
984  rh.stream_id)) {
986  }
987  break;
988 
989  case RELAY_COMMAND_SENDME:
991  rh.stream_id)) {
993  }
994  break;
995 
996  case RELAY_COMMAND_CONNECTED:
998  rh.stream_id)) {
1000  }
1001  break;
1002 
1003  case RELAY_COMMAND_RESOLVED:
1005  rh.stream_id)) {
1007  }
1008  break;
1009  }
1010 }
1011 
1012 /**
1013  * Check if a circuit was used and/or closed successfully.
1014  *
1015  * If we attempted to use the circuit to carry a stream but failed
1016  * for whatever reason, or if the circuit mysteriously died before
1017  * we could attach any streams, record these two cases.
1018  *
1019  * If we *have* successfully used the circuit, or it appears to
1020  * have been closed by us locally, count it as a success.
1021  *
1022  * Returns 0 if we're done making decisions with the circ,
1023  * or -1 if we want to probe it first.
1024  */
1025 int
1027 {
1028  circuit_t *circ = &ocirc->base_;
1029 
1030  if (!pathbias_should_count(ocirc)) {
1031  return 0;
1032  }
1033 
1034  switch (ocirc->path_state) {
1035  /* If the circuit was closed after building, but before use, we need
1036  * to ensure we were the ones who tried to close it (and not a remote
1037  * actor). */
1039  if (reason & END_CIRC_REASON_FLAG_REMOTE) {
1040  /* Remote circ close reasons on an unused circuit all could be bias */
1041  log_info(LD_CIRC,
1042  "Circuit %d remote-closed without successful use for reason %d. "
1043  "Circuit purpose %d currently %d,%s. Len %d.",
1044  ocirc->global_identifier,
1045  reason, circ->purpose, ocirc->has_opened,
1047  ocirc->build_state->desired_path_len);
1048  pathbias_count_collapse(ocirc);
1049  } else if ((reason & ~END_CIRC_REASON_FLAG_REMOTE)
1050  == END_CIRC_REASON_CHANNEL_CLOSED &&
1051  circ->n_chan &&
1052  circ->n_chan->reason_for_closing
1053  != CHANNEL_CLOSE_REQUESTED) {
1054  /* If we didn't close the channel ourselves, it could be bias */
1055  /* XXX: Only count bias if the network is live?
1056  * What about clock jumps/suspends? */
1057  log_info(LD_CIRC,
1058  "Circuit %d's channel closed without successful use for reason "
1059  "%d, channel reason %d. Circuit purpose %d currently %d,%s. Len "
1060  "%d.", ocirc->global_identifier,
1061  reason, circ->n_chan->reason_for_closing,
1062  circ->purpose, ocirc->has_opened,
1064  ocirc->build_state->desired_path_len);
1065  pathbias_count_collapse(ocirc);
1066  } else {
1068  }
1069  break;
1070 
1071  /* If we tried to use a circuit but failed, we should probe it to ensure
1072  * it has not been tampered with. */
1074  /* XXX: Only probe and/or count failure if the network is live?
1075  * What about clock jumps/suspends? */
1076  if (pathbias_send_usable_probe(circ) == 0)
1077  return -1;
1078  else
1080 
1081  /* Any circuit where there were attempted streams but no successful
1082  * streams could be bias */
1083  log_info(LD_CIRC,
1084  "Circuit %d closed without successful use for reason %d. "
1085  "Circuit purpose %d currently %d,%s. Len %d.",
1086  ocirc->global_identifier,
1087  reason, circ->purpose, ocirc->has_opened,
1089  ocirc->build_state->desired_path_len);
1090  break;
1091 
1095  break;
1096 
1097  case PATH_STATE_USE_FAILED:
1099  break;
1100 
1101  case PATH_STATE_NEW_CIRC:
1104  default:
1105  // Other states are uninteresting. No stats to count.
1106  break;
1107  }
1108 
1110 
1111  return 0;
1112 }
1113 
1114 /**
1115  * Count a successfully closed circuit.
1116  */
1117 static void
1119 {
1120  entry_guard_t *guard = NULL;
1121  if (!pathbias_should_count(circ)) {
1122  return;
1123  }
1124 
1125  if (circ->cpath && circ->cpath->extend_info) {
1128  }
1129 
1130  if (guard) {
1132 
1133  /* In the long run: circuit_success ~= successful_circuit_close +
1134  * circ_failure + stream_failure */
1137  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
1138  /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1139  * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1140  * No need to log that case. */
1141  log_info(LD_CIRC,
1142  "Successfully closed circuit has no known guard. "
1143  "Circuit is a %s currently %s",
1144  circuit_purpose_to_string(circ->base_.purpose),
1145  circuit_state_to_string(circ->base_.state));
1146  }
1147 }
1148 
1149 /**
1150  * Count a circuit that fails after it is built, but before it can
1151  * carry any traffic.
1152  *
1153  * This is needed because there are ways to destroy a
1154  * circuit after it has successfully completed. Right now, this is
1155  * used for purely informational/debugging purposes.
1156  */
1157 static void
1159 {
1160  entry_guard_t *guard = NULL;
1161 
1162  if (!pathbias_should_count(circ)) {
1163  return;
1164  }
1165 
1166  if (circ->cpath && circ->cpath->extend_info) {
1169  }
1170 
1171  if (guard) {
1173 
1174  pb->collapsed_circuits++;
1176  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
1177  /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1178  * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1179  * No need to log that case. */
1180  log_info(LD_CIRC,
1181  "Destroyed circuit has no known guard. "
1182  "Circuit is a %s currently %s",
1183  circuit_purpose_to_string(circ->base_.purpose),
1184  circuit_state_to_string(circ->base_.state));
1185  }
1186 }
1187 
1188 /**
1189  * Count a known failed circuit (because we could not probe it).
1190  *
1191  * This counter is informational.
1192  */
1193 static void
1195 {
1196  entry_guard_t *guard = NULL;
1197  if (!pathbias_should_count(circ)) {
1198  return;
1199  }
1200 
1201  if (circ->cpath && circ->cpath->extend_info) {
1204  }
1205 
1206  if (guard) {
1208 
1209  pb->unusable_circuits++;
1211  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
1212  /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1213  * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1214  * No need to log that case. */
1215  /* XXX note cut-and-paste code in this function compared to nearby
1216  * functions. Would be nice to refactor. -RD */
1217  log_info(LD_CIRC,
1218  "Stream-failing circuit has no known guard. "
1219  "Circuit is a %s currently %s",
1220  circuit_purpose_to_string(circ->base_.purpose),
1221  circuit_state_to_string(circ->base_.state));
1222  }
1223 }
1224 
1225 /**
1226  * Count timeouts for path bias log messages.
1227  *
1228  * These counts are purely informational.
1229  */
1230 void
1232 {
1233  entry_guard_t *guard = NULL;
1234 
1235  if (!pathbias_should_count(circ)) {
1236  return;
1237  }
1238 
1239  /* For hidden service circs, they can actually be used
1240  * successfully and then time out later (because
1241  * the other side declines to use them). */
1242  if (circ->path_state == PATH_STATE_USE_SUCCEEDED) {
1243  return;
1244  }
1245 
1246  if (circ->cpath && circ->cpath->extend_info) {
1249  }
1250 
1251  if (guard) {
1253 
1254  pb->timeouts++;
1256  }
1257 }
1258 
1259 /**
1260  * Helper function to count all of the currently opened circuits
1261  * for a guard that are in a given path state range. The state
1262  * range is inclusive on both ends.
1263  */
1264 static int
1265 pathbias_count_circs_in_states(entry_guard_t *guard,
1266  path_state_t from,
1267  path_state_t to)
1268 {
1269  int open_circuits = 0;
1270 
1271  /* Count currently open circuits. Give them the benefit of the doubt. */
1273  origin_circuit_t *ocirc = NULL;
1274  if (!CIRCUIT_IS_ORIGIN(circ) || /* didn't originate here */
1275  circ->marked_for_close) /* already counted */
1276  continue;
1277 
1278  ocirc = TO_ORIGIN_CIRCUIT(circ);
1279 
1280  if (!ocirc->cpath || !ocirc->cpath->extend_info)
1281  continue;
1282 
1283  if (ocirc->path_state >= from &&
1284  ocirc->path_state <= to &&
1285  pathbias_should_count(ocirc) &&
1288  DIGEST_LEN)) {
1289  log_debug(LD_CIRC, "Found opened circuit %d in path_state %s",
1290  ocirc->global_identifier,
1292  open_circuits++;
1293  }
1294  }
1295  SMARTLIST_FOREACH_END(circ);
1296 
1297  return open_circuits;
1298 }
1299 
1300 /**
1301  * Return the number of circuits counted as successfully closed for
1302  * this guard.
1303  *
1304  * Also add in the currently open circuits to give them the benefit
1305  * of the doubt.
1306  */
1307 double
1309 {
1311 
1312  return pb->successful_circuits_closed +
1316 }
1317 
1318 /**
1319  * Return the number of circuits counted as successfully used
1320  * this guard.
1321  *
1322  * Also add in the currently open circuits that we are attempting
1323  * to use to give them the benefit of the doubt.
1324  */
1325 double
1326 pathbias_get_use_success_count(entry_guard_t *guard)
1327 {
1329 
1330  return pb->use_successes +
1334 }
1335 
1336 /**
1337  * Check the path bias use rate against our consensus parameter limits.
1338  *
1339  * Emits a log message if the use success rates are too low.
1340  *
1341  * If pathbias_get_dropguards() is set, we also disable the use of
1342  * very failure prone guards.
1343  */
1344 static void
1345 pathbias_measure_use_rate(entry_guard_t *guard)
1346 {
1347  const or_options_t *options = get_options();
1349 
1350  if (pb->use_attempts > pathbias_get_min_use(options)) {
1351  /* Note: We rely on the < comparison here to allow us to set a 0
1352  * rate and disable the feature entirely. If refactoring, don't
1353  * change to <= */
1355  < pathbias_get_extreme_use_rate(options)) {
1356  /* Dropping is currently disabled by default. */
1357  if (pathbias_get_dropguards(options)) {
1358  if (!pb->path_bias_disabled) {
1359  log_warn(LD_CIRC,
1360  "Guard %s is failing to carry an extremely large "
1361  "amount of stream on its circuits. "
1362  "To avoid potential route manipulation attacks, Tor has "
1363  "disabled use of this guard. "
1364  "Use counts are %ld/%ld. Success counts are %ld/%ld. "
1365  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1366  "and %ld timed out. "
1367  "For reference, your timeout cutoff is %ld seconds.",
1368  entry_guard_describe(guard),
1370  tor_lround(pb->use_attempts),
1376  tor_lround(pb->timeouts),
1378  pb->path_bias_disabled = 1;
1379  return;
1380  }
1381  } else if (!pb->path_bias_use_extreme) {
1382  pb->path_bias_use_extreme = 1;
1383  log_warn(LD_CIRC,
1384  "Guard %s is failing to carry an extremely large "
1385  "amount of streams on its circuits. "
1386  "This could indicate a route manipulation attack, network "
1387  "overload, bad local network connectivity, or a bug. "
1388  "Use counts are %ld/%ld. Success counts are %ld/%ld. "
1389  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1390  "and %ld timed out. "
1391  "For reference, your timeout cutoff is %ld seconds.",
1392  entry_guard_describe(guard),
1394  tor_lround(pb->use_attempts),
1400  tor_lround(pb->timeouts),
1402  }
1403  } else if (pathbias_get_use_success_count(guard)/pb->use_attempts
1404  < pathbias_get_notice_use_rate(options)) {
1405  if (!pb->path_bias_use_noticed) {
1406  pb->path_bias_use_noticed = 1;
1407  log_notice(LD_CIRC,
1408  "Guard %s is failing to carry more streams on its "
1409  "circuits than usual. "
1410  "Most likely this means the Tor network is overloaded "
1411  "or your network connection is poor. "
1412  "Use counts are %ld/%ld. Success counts are %ld/%ld. "
1413  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1414  "and %ld timed out. "
1415  "For reference, your timeout cutoff is %ld seconds.",
1416  entry_guard_describe(guard),
1418  tor_lround(pb->use_attempts),
1424  tor_lround(pb->timeouts),
1426  }
1427  }
1428  }
1429 }
1430 
1431 /**
1432  * Check the path bias circuit close status rates against our consensus
1433  * parameter limits.
1434  *
1435  * Emits a log message if the use success rates are too low.
1436  *
1437  * If pathbias_get_dropguards() is set, we also disable the use of
1438  * very failure prone guards.
1439  *
1440  * XXX: This function shares similar log messages and checks to
1441  * pathbias_measure_use_rate(). It may be possible to combine them
1442  * eventually, especially if we can ever remove the need for 3
1443  * levels of closure warns (if the overall circuit failure rate
1444  * goes down with ntor). One way to do so would be to multiply
1445  * the build rate with the use rate to get an idea of the total
1446  * fraction of the total network paths the user is able to use.
1447  * See ticket #8159.
1448  */
1449 static void
1450 pathbias_measure_close_rate(entry_guard_t *guard)
1451 {
1452  const or_options_t *options = get_options();
1454 
1455  if (pb->circ_attempts > pathbias_get_min_circs(options)) {
1456  /* Note: We rely on the < comparison here to allow us to set a 0
1457  * rate and disable the feature entirely. If refactoring, don't
1458  * change to <= */
1460  < pathbias_get_extreme_rate(options)) {
1461  /* Dropping is currently disabled by default. */
1462  if (pathbias_get_dropguards(options)) {
1463  if (!pb->path_bias_disabled) {
1464  log_warn(LD_CIRC,
1465  "Guard %s is failing an extremely large "
1466  "amount of circuits. "
1467  "To avoid potential route manipulation attacks, Tor has "
1468  "disabled use of this guard. "
1469  "Success counts are %ld/%ld. Use counts are %ld/%ld. "
1470  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1471  "and %ld timed out. "
1472  "For reference, your timeout cutoff is %ld seconds.",
1473  entry_guard_describe(guard),
1477  tor_lround(pb->use_attempts),
1481  tor_lround(pb->timeouts),
1483  pb->path_bias_disabled = 1;
1484  return;
1485  }
1486  } else if (!pb->path_bias_extreme) {
1487  pb->path_bias_extreme = 1;
1488  log_warn(LD_CIRC,
1489  "Guard %s is failing an extremely large "
1490  "amount of circuits. "
1491  "This could indicate a route manipulation attack, "
1492  "extreme network overload, or a bug. "
1493  "Success counts are %ld/%ld. Use counts are %ld/%ld. "
1494  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1495  "and %ld timed out. "
1496  "For reference, your timeout cutoff is %ld seconds.",
1497  entry_guard_describe(guard),
1501  tor_lround(pb->use_attempts),
1505  tor_lround(pb->timeouts),
1507  }
1508  } else if (pathbias_get_close_success_count(guard)/pb->circ_attempts
1509  < pathbias_get_warn_rate(options)) {
1510  if (!pb->path_bias_warned) {
1511  pb->path_bias_warned = 1;
1512  log_warn(LD_CIRC,
1513  "Guard %s is failing a very large "
1514  "amount of circuits. "
1515  "Most likely this means the Tor network is "
1516  "overloaded, but it could also mean an attack against "
1517  "you or potentially the guard itself. "
1518  "Success counts are %ld/%ld. Use counts are %ld/%ld. "
1519  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1520  "and %ld timed out. "
1521  "For reference, your timeout cutoff is %ld seconds.",
1522  entry_guard_describe(guard),
1526  tor_lround(pb->use_attempts),
1530  tor_lround(pb->timeouts),
1532  }
1533  } else if (pathbias_get_close_success_count(guard)/pb->circ_attempts
1534  < pathbias_get_notice_rate(options)) {
1535  if (!pb->path_bias_noticed) {
1536  pb->path_bias_noticed = 1;
1537  log_notice(LD_CIRC,
1538  "Guard %s is failing more circuits than "
1539  "usual. "
1540  "Most likely this means the Tor network is overloaded. "
1541  "Success counts are %ld/%ld. Use counts are %ld/%ld. "
1542  "%ld circuits completed, %ld were unusable, %ld collapsed, "
1543  "and %ld timed out. "
1544  "For reference, your timeout cutoff is %ld seconds.",
1545  entry_guard_describe(guard),
1549  tor_lround(pb->use_attempts),
1553  tor_lround(pb->timeouts),
1555  }
1556  }
1557  }
1558 }
1559 
1560 /**
1561  * This function scales the path bias use rates if we have
1562  * more data than the scaling threshold. This allows us to
1563  * be more sensitive to recent measurements.
1564  *
1565  * XXX: The attempt count transfer stuff here might be done
1566  * better by keeping separate pending counters that get
1567  * transferred at circuit close. See ticket #8160.
1568  */
1569 static void
1570 pathbias_scale_close_rates(entry_guard_t *guard)
1571 {
1572  const or_options_t *options = get_options();
1574 
1575  /* If we get a ton of circuits, just scale everything down */
1576  if (pb->circ_attempts > pathbias_get_scale_threshold(options)) {
1577  double scale_ratio = pathbias_get_scale_ratio(options);
1578  int opened_attempts = pathbias_count_circs_in_states(guard,
1580  int opened_built = pathbias_count_circs_in_states(guard,
1583  /* Verify that the counts are sane before and after scaling */
1584  int counts_are_sane = (pb->circ_attempts >= pb->circ_successes);
1585 
1586  pb->circ_attempts -= (opened_attempts+opened_built);
1587  pb->circ_successes -= opened_built;
1588 
1589  pb->circ_attempts *= scale_ratio;
1590  pb->circ_successes *= scale_ratio;
1591  pb->timeouts *= scale_ratio;
1592  pb->successful_circuits_closed *= scale_ratio;
1593  pb->collapsed_circuits *= scale_ratio;
1594  pb->unusable_circuits *= scale_ratio;
1595 
1596  pb->circ_attempts += (opened_attempts+opened_built);
1597  pb->circ_successes += opened_built;
1598 
1600 
1601  log_info(LD_CIRC,
1602  "Scaled pathbias counts to (%f,%f)/%f (%d/%d open) for guard "
1603  "%s",
1605  pb->circ_attempts, opened_built, opened_attempts,
1606  entry_guard_describe(guard));
1607 
1608  /* Have the counts just become invalid by this scaling attempt? */
1609  if (counts_are_sane && pb->circ_attempts < pb->circ_successes) {
1610  log_notice(LD_BUG,
1611  "Scaling has mangled pathbias counts to %f/%f (%d/%d open) "
1612  "for guard %s",
1613  pb->circ_successes, pb->circ_attempts, opened_built,
1614  opened_attempts,
1615  entry_guard_describe(guard));
1616  }
1617  }
1618 }
1619 
1620 /**
1621  * This function scales the path bias circuit close rates if we have
1622  * more data than the scaling threshold. This allows us to be more
1623  * sensitive to recent measurements.
1624  *
1625  * XXX: The attempt count transfer stuff here might be done
1626  * better by keeping separate pending counters that get
1627  * transferred at circuit close. See ticket #8160.
1628  */
1629 void
1630 pathbias_scale_use_rates(entry_guard_t *guard)
1631 {
1632  const or_options_t *options = get_options();
1634 
1635  /* If we get a ton of circuits, just scale everything down */
1636  if (pb->use_attempts > pathbias_get_scale_use_threshold(options)) {
1637  double scale_ratio = pathbias_get_scale_ratio(options);
1638  int opened_attempts = pathbias_count_circs_in_states(guard,
1640  /* Verify that the counts are sane before and after scaling */
1641  int counts_are_sane = (pb->use_attempts >= pb->use_successes);
1642 
1643  pb->use_attempts -= opened_attempts;
1644 
1645  pb->use_attempts *= scale_ratio;
1646  pb->use_successes *= scale_ratio;
1647 
1648  pb->use_attempts += opened_attempts;
1649 
1650  log_info(LD_CIRC,
1651  "Scaled pathbias use counts to %f/%f (%d open) for guard %s",
1652  pb->use_successes, pb->use_attempts, opened_attempts,
1653  entry_guard_describe(guard));
1654 
1655  /* Have the counts just become invalid by this scaling attempt? */
1656  if (counts_are_sane && pb->use_attempts < pb->use_successes) {
1657  log_notice(LD_BUG,
1658  "Scaling has mangled pathbias usage counts to %f/%f "
1659  "(%d open) for guard %s",
1660  pb->circ_successes, pb->circ_attempts,
1661  opened_attempts, entry_guard_describe(guard));
1662  }
1663 
1665  }
1666 }
char * tor_dup_ip(uint32_t addr)
Definition: address.c:2047
time_t approx_time(void)
Definition: approx_time.c:32
static uint8_t get_uint8(const void *cp)
Definition: bytes.h:23
static uint32_t get_uint32(const void *cp)
Definition: bytes.h:54
Fixed-size cell structure.
Header file for channel.c.
int pathbias_count_build_attempt(origin_circuit_t *circ)
Definition: circpathbias.c:435
double pathbias_get_extreme_use_rate(const or_options_t *options)
Definition: circpathbias.c:232
void pathbias_count_use_attempt(origin_circuit_t *circ)
Definition: circpathbias.c:615
static void pathbias_count_use_success(origin_circuit_t *circ)
Definition: circpathbias.c:726
static int pathbias_get_min_circs(const or_options_t *options)
Definition: circpathbias.c:84
static int pathbias_should_count(origin_circuit_t *circ)
Definition: circpathbias.c:323
void pathbias_count_valid_cells(circuit_t *circ, const cell_t *cell)
Definition: circpathbias.c:955
static int pathbias_get_min_use(const or_options_t *options)
Definition: circpathbias.c:203
int pathbias_check_close(origin_circuit_t *ocirc, int reason)
static double pathbias_get_warn_rate(const or_options_t *options)
Definition: circpathbias.c:109
static void pathbias_scale_use_rates(entry_guard_t *guard)
static void pathbias_count_collapse(origin_circuit_t *circ)
static double pathbias_get_notice_use_rate(const or_options_t *options)
Definition: circpathbias.c:216
static void pathbias_count_use_failed(origin_circuit_t *circ)
void pathbias_count_timeout(origin_circuit_t *circ)
static void pathbias_count_successful_close(origin_circuit_t *circ)
static int pathbias_is_new_circ_attempt(origin_circuit_t *circ)
Definition: circpathbias.c:296
double pathbias_get_extreme_rate(const or_options_t *options)
Definition: circpathbias.c:125
static int pathbias_send_usable_probe(circuit_t *circ)
Definition: circpathbias.c:787
void pathbias_mark_use_rollback(origin_circuit_t *circ)
Definition: circpathbias.c:711
double pathbias_get_use_success_count(entry_guard_t *guard)
static int pathbias_get_scale_use_threshold(const or_options_t *options)
Definition: circpathbias.c:250
static void pathbias_measure_use_rate(entry_guard_t *guard)
static double pathbias_get_notice_rate(const or_options_t *options)
Definition: circpathbias.c:97
static int entry_guard_inc_circ_attempt_count(entry_guard_t *guard)
Definition: circpathbias.c:61
static void pathbias_measure_close_rate(entry_guard_t *guard)
static int pathbias_count_circs_in_states(entry_guard_t *guard, path_state_t from, path_state_t to)
static double pathbias_get_scale_ratio(const or_options_t *options)
Definition: circpathbias.c:177
int pathbias_check_probe_response(circuit_t *circ, const cell_t *cell)
Definition: circpathbias.c:895
static int pathbias_get_scale_threshold(const or_options_t *options)
Definition: circpathbias.c:158
int pathbias_get_dropguards(const or_options_t *options)
Definition: circpathbias.c:141
static void pathbias_scale_close_rates(entry_guard_t *guard)
void pathbias_mark_use_success(origin_circuit_t *circ)
Definition: circpathbias.c:672
void pathbias_count_build_success(origin_circuit_t *circ)
Definition: circpathbias.c:523
const char * pathbias_state_to_string(path_state_t state)
Definition: circpathbias.c:265
double pathbias_get_close_success_count(entry_guard_t *guard)
int circuit_truncated(origin_circuit_t *circ, int reason)
Header file for circuitbuild.c.
const char * circuit_purpose_to_string(uint8_t purpose)
Definition: circuitlist.c:914
smartlist_t * circuit_get_global_list(void)
Definition: circuitlist.c:705
origin_circuit_t * TO_ORIGIN_CIRCUIT(circuit_t *x)
Definition: circuitlist.c:177
const char * circuit_state_to_string(int state)
Definition: circuitlist.c:773
Header file for circuitlist.c.
#define CIRCUIT_PURPOSE_S_CONNECT_REND
Definition: circuitlist.h:107
#define CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
Definition: circuitlist.h:93
#define CIRCUIT_PURPOSE_PATH_BIAS_TESTING
Definition: circuitlist.h:123
#define CIRCUIT_PURPOSE_CONTROLLER
Definition: circuitlist.h:121
#define CIRCUIT_IS_ORIGIN(c)
Definition: circuitlist.h:147
#define CIRCUIT_PURPOSE_TESTING
Definition: circuitlist.h:118
#define CIRCUIT_PURPOSE_S_REND_JOINED
Definition: circuitlist.h:110
#define CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
Definition: circuitlist.h:79
#define CIRCUIT_PURPOSE_C_INTRODUCING
Definition: circuitlist.h:73
double get_circuit_build_close_time_ms(void)
Definition: circuitstats.c:93
Header file for circuitstats.c.
void circuit_read_valid_data(origin_circuit_t *circ, uint16_t relay_body_len)
Definition: circuituse.c:3119
void circuit_change_purpose(circuit_t *circ, uint8_t new_purpose)
Definition: circuituse.c:3028
Header file for circuituse.c.
const or_options_t * get_options(void)
Definition: config.c:926
Header file for config.c.
int connection_half_edge_is_valid_data(const smartlist_t *half_conns, streamid_t stream_id)
int connection_half_edge_is_valid_end(smartlist_t *half_conns, streamid_t stream_id)
int connection_half_edge_is_valid_connected(const smartlist_t *half_conns, streamid_t stream_id)
int connection_half_edge_is_valid_resolved(smartlist_t *half_conns, streamid_t stream_id)
int connection_half_edge_is_valid_sendme(const smartlist_t *half_conns, streamid_t stream_id)
streamid_t get_unique_stream_id_by_circ(origin_circuit_t *circ)
Header file for connection_edge.c.
Circuit-build-stse structure.
Path structures for origin circuits.
void crypto_rand(char *to, size_t n)
Definition: crypto_rand.c:479
Common functions for using (pseudo-)random number generators.
#define fast_memeq(a, b, c)
Definition: di_ops.h:35
#define DIGEST_LEN
Definition: digest_sizes.h:20
entry_guard_t * entry_guard_get_by_id_digest(const char *digest)
Definition: entrynodes.c:3375
void entry_guards_changed(void)
Definition: entrynodes.c:3587
guard_pathbias_t * entry_guard_get_pathbias_state(entry_guard_t *guard)
Definition: entrynodes.c:339
const char * entry_guard_describe(const entry_guard_t *guard)
Definition: entrynodes.c:320
const char * entry_guard_get_rsa_id_digest(const entry_guard_t *guard)
Definition: entrynodes.c:332
Header file for circuitbuild.c.
Extend-info structure.
long tor_lround(double d)
Definition: fp.c:31
Header for fp.c.
Header for laplace.c.
#define LD_PROTOCOL
Definition: log.h:72
#define LD_BUG
Definition: log.h:86
#define LD_CIRC
Definition: log.h:82
#define tor_free(p)
Definition: malloc.h:56
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)
Header file for networkstatus.c.
Master header file for Tor-specific functionality.
#define CELL_PAYLOAD_SIZE
Definition: or.h:456
#define RELAY_PAYLOAD_SIZE
Definition: or.h:485
#define END_CIRC_REASON_FLAG_REMOTE
Definition: or.h:332
#define RELAY_HEADER_SIZE
Definition: or.h:483
Origin circuit structure.
path_state_t
@ PATH_STATE_ALREADY_COUNTED
@ PATH_STATE_USE_FAILED
@ PATH_STATE_BUILD_ATTEMPTED
@ PATH_STATE_BUILD_SUCCEEDED
@ PATH_STATE_USE_SUCCEEDED
@ PATH_STATE_NEW_CIRC
@ PATH_STATE_USE_ATTEMPTED
int tor_snprintf(char *str, size_t size, const char *format,...)
Definition: printf.c:27
char * rate_limit_log(ratelim_t *lim, time_t now)
Definition: ratelim.c:42
void relay_header_unpack(relay_header_t *dest, const uint8_t *src)
Definition: relay.c:496
Header file for relay.c.
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
Definition: cell_st.h:17
uint8_t payload[CELL_PAYLOAD_SIZE]
Definition: cell_st.h:21
char identity_digest[DIGEST_LEN]
Definition: channel.h:378
enum channel_t::@8 reason_for_closing
uint8_t state
Definition: circuit_st.h:111
time_t timestamp_dirty
Definition: circuit_st.h:188
uint8_t purpose
Definition: circuit_st.h:112
struct timeval timestamp_began
Definition: circuit_st.h:166
channel_t * n_chan
Definition: circuit_st.h:70
struct crypt_path_t * prev
Definition: crypt_path_st.h:80
uint8_t state
Definition: crypt_path_st.h:73
struct crypt_path_t * next
Definition: crypt_path_st.h:77
extend_info_t * extend_info
Definition: crypt_path_st.h:66
char identity_digest[DIGEST_LEN]
unsigned int path_bias_use_noticed
Definition: entrynodes.h:44
unsigned int path_bias_use_extreme
Definition: entrynodes.h:46
double use_successes
Definition: entrynodes.h:62
unsigned int path_bias_warned
Definition: entrynodes.h:38
unsigned int path_bias_extreme
Definition: entrynodes.h:40
double circ_attempts
Definition: entrynodes.h:49
double collapsed_circuits
Definition: entrynodes.h:54
double circ_successes
Definition: entrynodes.h:50
unsigned int path_bias_disabled
Definition: entrynodes.h:42
double unusable_circuits
Definition: entrynodes.h:57
double successful_circuits_closed
Definition: entrynodes.h:52
double use_attempts
Definition: entrynodes.h:61
unsigned int path_bias_noticed
Definition: entrynodes.h:36
int PathBiasCircThreshold
int PathBiasUseThreshold
unsigned int has_opened
path_state_bitfield_t path_state
uint32_t pathbias_probe_nonce
unsigned int any_hop_from_controller
crypt_path_t * cpath
streamid_t pathbias_probe_id
cpath_build_state_t * build_state
smartlist_t * half_streams
uint16_t length
Definition: or.h:522
uint8_t command
Definition: or.h:518
streamid_t stream_id
Definition: or.h:520
void tor_gettimeofday(struct timeval *timeval)
#define tor_assert(expr)
Definition: util_bug.h:102
#define tor_fragile_assert()
Definition: util_bug.h:270