Line data Source code
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"
31 : #include "core/or/connection_edge.h"
32 : #include "app/config/config.h"
33 : #include "lib/crypt_ops/crypto_rand.h"
34 : #include "feature/client/entrynodes.h"
35 : #include "feature/nodelist/networkstatus.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"
41 : #include "core/or/cpath_build_state_st.h"
42 : #include "core/or/crypt_path_st.h"
43 : #include "core/or/extend_info_st.h"
44 : #include "core/or/origin_circuit_st.h"
45 :
46 : static void pathbias_count_successful_close(origin_circuit_t *circ);
47 : static void pathbias_count_collapse(origin_circuit_t *circ);
48 : static void pathbias_count_use_failed(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
61 0 : entry_guard_inc_circ_attempt_count(entry_guard_t *guard)
62 : {
63 0 : guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
64 :
65 0 : entry_guards_changed();
66 :
67 0 : pathbias_measure_close_rate(guard);
68 :
69 0 : if (pb->path_bias_disabled)
70 : return -1;
71 :
72 0 : pathbias_scale_close_rates(guard);
73 0 : pb->circ_attempts++;
74 :
75 0 : log_info(LD_CIRC, "Got success count %f/%f for guard %s",
76 : pb->circ_successes, pb->circ_attempts,
77 : entry_guard_describe(guard));
78 0 : 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
84 0 : pathbias_get_min_circs(const or_options_t *options)
85 : {
86 : #define DFLT_PATH_BIAS_MIN_CIRC 150
87 0 : if (options->PathBiasCircThreshold >= 5)
88 : return options->PathBiasCircThreshold;
89 : else
90 0 : 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
97 0 : pathbias_get_notice_rate(const or_options_t *options)
98 : {
99 : #define DFLT_PATH_BIAS_NOTICE_PCT 70
100 0 : if (options->PathBiasNoticeRate >= 0.0)
101 : return options->PathBiasNoticeRate;
102 : else
103 0 : return networkstatus_get_param(NULL, "pb_noticepct",
104 0 : 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
109 0 : pathbias_get_warn_rate(const or_options_t *options)
110 : {
111 : #define DFLT_PATH_BIAS_WARN_PCT 50
112 0 : if (options->PathBiasWarnRate >= 0.0)
113 : return options->PathBiasWarnRate;
114 : else
115 0 : return networkstatus_get_param(NULL, "pb_warnpct",
116 0 : 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
125 11 : pathbias_get_extreme_rate(const or_options_t *options)
126 : {
127 : #define DFLT_PATH_BIAS_EXTREME_PCT 30
128 11 : if (options->PathBiasExtremeRate >= 0.0)
129 : return options->PathBiasExtremeRate;
130 : else
131 11 : return networkstatus_get_param(NULL, "pb_extremepct",
132 11 : 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
141 0 : pathbias_get_dropguards(const or_options_t *options)
142 : {
143 : #define DFLT_PATH_BIAS_DROP_GUARDS 0
144 0 : if (options->PathBiasDropGuards >= 0)
145 : return options->PathBiasDropGuards;
146 : else
147 0 : 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
158 0 : pathbias_get_scale_threshold(const or_options_t *options)
159 : {
160 : #define DFLT_PATH_BIAS_SCALE_THRESHOLD 300
161 0 : if (options->PathBiasScaleThreshold >= 10)
162 : return options->PathBiasScaleThreshold;
163 : else
164 0 : 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
177 0 : pathbias_get_scale_ratio(const or_options_t *options)
178 : {
179 0 : (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 0 : int denominator = networkstatus_get_param(NULL, "pb_scalefactor",
188 : 2, 2, INT32_MAX);
189 0 : 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 0 : return networkstatus_get_param(NULL, "pb_multfactor",
197 0 : 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
203 0 : pathbias_get_min_use(const or_options_t *options)
204 : {
205 : #define DFLT_PATH_BIAS_MIN_USE 20
206 0 : if (options->PathBiasUseThreshold >= 3)
207 : return options->PathBiasUseThreshold;
208 : else
209 0 : 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
216 0 : pathbias_get_notice_use_rate(const or_options_t *options)
217 : {
218 : #define DFLT_PATH_BIAS_NOTICE_USE_PCT 80
219 0 : if (options->PathBiasNoticeUseRate >= 0.0)
220 : return options->PathBiasNoticeUseRate;
221 : else
222 0 : return networkstatus_get_param(NULL, "pb_noticeusepct",
223 : DFLT_PATH_BIAS_NOTICE_USE_PCT,
224 0 : 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
232 0 : pathbias_get_extreme_use_rate(const or_options_t *options)
233 : {
234 : #define DFLT_PATH_BIAS_EXTREME_USE_PCT 60
235 0 : if (options->PathBiasExtremeUseRate >= 0.0)
236 : return options->PathBiasExtremeUseRate;
237 : else
238 0 : return networkstatus_get_param(NULL, "pb_extremeusepct",
239 : DFLT_PATH_BIAS_EXTREME_USE_PCT,
240 0 : 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
250 0 : pathbias_get_scale_use_threshold(const or_options_t *options)
251 : {
252 : #define DFLT_PATH_BIAS_SCALE_USE_THRESHOLD 100
253 0 : if (options->PathBiasScaleUseThreshold >= 10)
254 : return options->PathBiasScaleUseThreshold;
255 : else
256 0 : 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 *
265 0 : pathbias_state_to_string(path_state_t state)
266 : {
267 0 : switch (state) {
268 : case PATH_STATE_NEW_CIRC:
269 : return "new";
270 0 : case PATH_STATE_BUILD_ATTEMPTED:
271 0 : return "build attempted";
272 0 : case PATH_STATE_BUILD_SUCCEEDED:
273 0 : return "build succeeded";
274 0 : case PATH_STATE_USE_ATTEMPTED:
275 0 : return "use attempted";
276 0 : case PATH_STATE_USE_SUCCEEDED:
277 0 : return "use succeeded";
278 0 : case PATH_STATE_USE_FAILED:
279 0 : return "use failed";
280 0 : case PATH_STATE_ALREADY_COUNTED:
281 0 : return "already counted";
282 : }
283 :
284 0 : 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
296 0 : pathbias_is_new_circ_attempt(origin_circuit_t *circ)
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 0 : return circ->cpath &&
304 0 : circ->cpath->next != circ->cpath &&
305 0 : 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
323 23 : pathbias_should_count(origin_circuit_t *circ)
324 : {
325 : #define PATHBIAS_COUNT_INTERVAL (600)
326 23 : static ratelim_t count_limit =
327 : RATELIM_INIT(PATHBIAS_COUNT_INTERVAL);
328 23 : 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 23 : if (get_options()->UseEntryGuards == 0 ||
339 0 : 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 23 : if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_COUNTED
354 0 : && circ->path_state != PATH_STATE_ALREADY_COUNTED) {
355 0 : 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),
360 : pathbias_state_to_string(circ->path_state));
361 : }
362 23 : circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_IGNORED;
363 23 : return 0;
364 : }
365 :
366 : /* Completely ignore one hop circuits */
367 0 : if (circ->build_state->onehop_tunnel ||
368 0 : circ->build_state->desired_path_len == 1) {
369 : /* Check for inconsistency */
370 0 : if (circ->build_state->desired_path_len != 1 ||
371 : !circ->build_state->onehop_tunnel) {
372 0 : if ((rate_msg = rate_limit_log(&count_limit, approx_time()))) {
373 0 : 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,
377 : circ->build_state->desired_path_len,
378 : pathbias_state_to_string(circ->path_state),
379 : circuit_purpose_to_string(circ->base_.purpose),
380 : circuit_state_to_string(circ->base_.state),
381 : rate_msg);
382 0 : tor_free(rate_msg);
383 : }
384 0 : tor_fragile_assert();
385 : }
386 :
387 : /* Check to see if the shouldcount result has changed due to a
388 : * unexpected change that would affect our results */
389 0 : if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_COUNTED) {
390 0 : 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),
395 : pathbias_state_to_string(circ->path_state));
396 : }
397 0 : circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_IGNORED;
398 0 : 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 0 : if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_IGNORED) {
404 0 : 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),
409 : pathbias_state_to_string(circ->path_state));
410 0 : return 0;
411 : }
412 0 : circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_COUNTED;
413 :
414 0 : 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
424 0 : pathbias_count_build_attempt(origin_circuit_t *circ)
425 : {
426 : #define CIRC_ATTEMPT_NOTICE_INTERVAL (600)
427 0 : static ratelim_t circ_attempt_notice_limit =
428 : RATELIM_INIT(CIRC_ATTEMPT_NOTICE_INTERVAL);
429 0 : char *rate_msg = NULL;
430 :
431 0 : if (!pathbias_should_count(circ)) {
432 : return 0;
433 : }
434 :
435 0 : if (pathbias_is_new_circ_attempt(circ)) {
436 : /* Help track down the real cause of bug #6475: */
437 0 : if (circ->has_opened && circ->path_state != PATH_STATE_BUILD_ATTEMPTED) {
438 0 : if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
439 : approx_time()))) {
440 0 : 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,
444 : pathbias_state_to_string(circ->path_state),
445 : circuit_purpose_to_string(circ->base_.purpose),
446 : circuit_state_to_string(circ->base_.state),
447 : rate_msg);
448 0 : tor_free(rate_msg);
449 : }
450 : }
451 :
452 : /* Don't re-count cannibalized circs.. */
453 0 : if (!circ->has_opened) {
454 0 : entry_guard_t *guard = NULL;
455 :
456 0 : if (circ->cpath && circ->cpath->extend_info) {
457 0 : guard = entry_guard_get_by_id_digest(
458 0 : circ->cpath->extend_info->identity_digest);
459 0 : } else if (circ->base_.n_chan) {
460 0 : guard =
461 0 : entry_guard_get_by_id_digest(circ->base_.n_chan->identity_digest);
462 : }
463 :
464 0 : if (guard) {
465 0 : if (circ->path_state == PATH_STATE_NEW_CIRC) {
466 0 : circ->path_state = PATH_STATE_BUILD_ATTEMPTED;
467 :
468 0 : if (entry_guard_inc_circ_attempt_count(guard) < 0) {
469 : /* Bogus guard; we already warned. */
470 0 : return -END_CIRC_REASON_TORPROTOCOL;
471 : }
472 : } else {
473 0 : if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
474 : approx_time()))) {
475 0 : 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,
479 : pathbias_state_to_string(circ->path_state),
480 : circuit_purpose_to_string(circ->base_.purpose),
481 : circuit_state_to_string(circ->base_.state),
482 : rate_msg);
483 0 : tor_free(rate_msg);
484 : }
485 : }
486 : } else {
487 0 : if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
488 : approx_time()))) {
489 0 : 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 0 : 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
512 0 : pathbias_count_build_success(origin_circuit_t *circ)
513 : {
514 : #define SUCCESS_NOTICE_INTERVAL (600)
515 0 : static ratelim_t success_notice_limit =
516 : RATELIM_INIT(SUCCESS_NOTICE_INTERVAL);
517 0 : char *rate_msg = NULL;
518 0 : entry_guard_t *guard = NULL;
519 :
520 0 : if (!pathbias_should_count(circ)) {
521 0 : return;
522 : }
523 :
524 : /* Don't count cannibalized/reused circs for path bias
525 : * "build" success, since they get counted under "use" success. */
526 0 : if (!circ->has_opened) {
527 0 : if (circ->cpath && circ->cpath->extend_info) {
528 0 : guard = entry_guard_get_by_id_digest(
529 0 : circ->cpath->extend_info->identity_digest);
530 : }
531 :
532 0 : if (guard) {
533 0 : guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
534 :
535 0 : if (circ->path_state == PATH_STATE_BUILD_ATTEMPTED) {
536 0 : circ->path_state = PATH_STATE_BUILD_SUCCEEDED;
537 0 : pb->circ_successes++;
538 0 : entry_guards_changed();
539 :
540 0 : 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 0 : if ((rate_msg = rate_limit_log(&success_notice_limit,
545 : approx_time()))) {
546 0 : 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,
550 : pathbias_state_to_string(circ->path_state),
551 : circuit_purpose_to_string(circ->base_.purpose),
552 : circuit_state_to_string(circ->base_.state),
553 : rate_msg);
554 0 : tor_free(rate_msg);
555 : }
556 : }
557 :
558 0 : if (pb->circ_attempts < pb->circ_successes) {
559 0 : 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 0 : } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
568 0 : if ((rate_msg = rate_limit_log(&success_notice_limit,
569 : approx_time()))) {
570 0 : 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 0 : tor_free(rate_msg);
577 : }
578 : }
579 : } else {
580 0 : if (circ->path_state < PATH_STATE_BUILD_SUCCEEDED) {
581 0 : if ((rate_msg = rate_limit_log(&success_notice_limit,
582 : approx_time()))) {
583 0 : 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,
587 : pathbias_state_to_string(circ->path_state),
588 : circuit_purpose_to_string(circ->base_.purpose),
589 : circuit_state_to_string(circ->base_.state),
590 : rate_msg);
591 0 : 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
604 4 : pathbias_count_use_attempt(origin_circuit_t *circ)
605 : {
606 4 : if (!pathbias_should_count(circ)) {
607 : return;
608 : }
609 :
610 0 : if (circ->path_state < PATH_STATE_BUILD_SUCCEEDED) {
611 0 : 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,
615 : pathbias_state_to_string(circ->path_state),
616 : circuit_purpose_to_string(circ->base_.purpose),
617 : circuit_state_to_string(circ->base_.state));
618 0 : } else if (circ->path_state < PATH_STATE_USE_ATTEMPTED) {
619 0 : entry_guard_t *guard = entry_guard_get_by_id_digest(
620 0 : circ->cpath->extend_info->identity_digest);
621 0 : if (guard) {
622 0 : guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
623 :
624 0 : pathbias_measure_use_rate(guard);
625 0 : pathbias_scale_use_rates(guard);
626 0 : pb->use_attempts++;
627 0 : entry_guards_changed();
628 :
629 0 : 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 :
636 0 : circ->path_state = PATH_STATE_USE_ATTEMPTED;
637 : } else {
638 : /* Harmless but educational log message */
639 0 : 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,
643 : pathbias_state_to_string(circ->path_state),
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
661 4 : pathbias_mark_use_success(origin_circuit_t *circ)
662 : {
663 4 : if (!pathbias_should_count(circ)) {
664 : return;
665 : }
666 :
667 0 : if (circ->path_state < PATH_STATE_USE_ATTEMPTED) {
668 0 : 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,
672 : pathbias_state_to_string(circ->path_state),
673 : circuit_purpose_to_string(circ->base_.purpose),
674 : circuit_state_to_string(circ->base_.state));
675 :
676 0 : pathbias_count_use_attempt(circ);
677 : }
678 :
679 : /* We don't do any accounting at the guard until actual circuit close */
680 0 : circ->path_state = PATH_STATE_USE_SUCCEEDED;
681 :
682 0 : return;
683 : }
684 :
685 : /**
686 : * If a stream ever detaches 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
700 0 : pathbias_mark_use_rollback(origin_circuit_t *circ)
701 : {
702 0 : if (circ->path_state == PATH_STATE_USE_SUCCEEDED) {
703 0 : log_info(LD_CIRC,
704 : "Rolling back pathbias use state to 'attempted' for detached "
705 : "circuit %d", circ->global_identifier);
706 0 : circ->path_state = PATH_STATE_USE_ATTEMPTED;
707 : }
708 0 : }
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
715 0 : pathbias_count_use_success(origin_circuit_t *circ)
716 : {
717 0 : entry_guard_t *guard;
718 :
719 0 : if (!pathbias_should_count(circ)) {
720 : return;
721 : }
722 :
723 0 : if (circ->path_state != PATH_STATE_USE_SUCCEEDED) {
724 0 : 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,
728 : pathbias_state_to_string(circ->path_state),
729 : circuit_purpose_to_string(circ->base_.purpose),
730 : circuit_state_to_string(circ->base_.state));
731 : } else {
732 0 : guard = entry_guard_get_by_id_digest(
733 0 : circ->cpath->extend_info->identity_digest);
734 0 : if (guard) {
735 0 : guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
736 :
737 0 : pb->use_successes++;
738 0 : entry_guards_changed();
739 :
740 0 : if (pb->use_attempts < pb->use_successes) {
741 0 : 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 0 : 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
776 0 : pathbias_send_usable_probe(circuit_t *circ)
777 : {
778 : /* Based on connection_ap_handshake_send_begin() */
779 0 : char payload[CELL_PAYLOAD_SIZE];
780 0 : int payload_len;
781 0 : origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
782 0 : crypt_path_t *cpath_layer = NULL;
783 0 : char *probe_nonce = NULL;
784 :
785 0 : tor_assert(ocirc);
786 :
787 0 : cpath_layer = ocirc->cpath->prev;
788 :
789 0 : if (cpath_layer->state != CPATH_STATE_OPEN) {
790 : /* This can happen for cannibalized circuits. Their
791 : * last hop isn't yet open */
792 0 : 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 0 : return -1;
797 : }
798 :
799 : /* We already went down this road. */
800 0 : if (circ->purpose == CIRCUIT_PURPOSE_PATH_BIAS_TESTING &&
801 0 : ocirc->pathbias_probe_id) {
802 0 : log_info(LD_CIRC,
803 : "Got pathbias probe request for circuit %d with "
804 : "outstanding probe", ocirc->global_identifier);
805 0 : return -1;
806 : }
807 :
808 : /* Can't probe if the channel isn't open */
809 0 : if (circ->n_chan == NULL ||
810 0 : (!CHANNEL_IS_OPEN(circ->n_chan)
811 0 : && !CHANNEL_IS_MAINT(circ->n_chan))) {
812 0 : log_info(LD_CIRC,
813 : "Skipping pathbias probe for circuit %d: Channel is not open.",
814 : ocirc->global_identifier);
815 0 : return -1;
816 : }
817 :
818 0 : circuit_change_purpose(circ, CIRCUIT_PURPOSE_PATH_BIAS_TESTING);
819 :
820 : /* Update timestamp for when circuit_expire_building() should kill us */
821 0 : tor_gettimeofday(&circ->timestamp_began);
822 :
823 : /* Generate a random address for the nonce */
824 0 : crypto_rand((char*)ô->pathbias_probe_nonce,
825 : sizeof(ocirc->pathbias_probe_nonce));
826 0 : ocirc->pathbias_probe_nonce &= 0x00ffffff;
827 0 : probe_nonce = tor_dup_ip(ocirc->pathbias_probe_nonce);
828 :
829 0 : if (!probe_nonce) {
830 0 : log_err(LD_BUG, "Failed to generate nonce");
831 0 : return -1;
832 : }
833 :
834 0 : tor_snprintf(payload,RELAY_PAYLOAD_SIZE, "%s:25", probe_nonce);
835 0 : payload_len = (int)strlen(payload)+1;
836 :
837 : // XXX: need this? Can we assume ipv4 will always be supported?
838 : // If not, how do we tell?
839 : //if (payload_len <= RELAY_PAYLOAD_SIZE - 4 && edge_conn->begincell_flags) {
840 : // set_uint32(payload + payload_len, htonl(edge_conn->begincell_flags));
841 : // payload_len += 4;
842 : //}
843 :
844 : /* Generate+Store stream id, make sure it's non-zero */
845 0 : ocirc->pathbias_probe_id = get_unique_stream_id_by_circ(ocirc);
846 :
847 0 : if (ocirc->pathbias_probe_id==0) {
848 0 : log_warn(LD_CIRC,
849 : "Ran out of stream IDs on circuit %u during "
850 : "pathbias probe attempt.", ocirc->global_identifier);
851 0 : tor_free(probe_nonce);
852 0 : return -1;
853 : }
854 :
855 0 : log_info(LD_CIRC,
856 : "Sending pathbias testing cell to %s:25 on stream %d for circ %d.",
857 : probe_nonce, ocirc->pathbias_probe_id, ocirc->global_identifier);
858 0 : tor_free(probe_nonce);
859 :
860 : /* Send a test relay cell */
861 0 : if (relay_send_command_from_edge(ocirc->pathbias_probe_id, circ,
862 : RELAY_COMMAND_BEGIN, payload,
863 : payload_len, cpath_layer) < 0) {
864 0 : log_notice(LD_CIRC,
865 : "Failed to send pathbias probe cell on circuit %d.",
866 : ocirc->global_identifier);
867 0 : return -1;
868 : }
869 :
870 : /* Mark it freshly dirty so it doesn't get expired in the meantime */
871 0 : circ->timestamp_dirty = time(NULL);
872 :
873 0 : return 0;
874 : }
875 :
876 : /**
877 : * Check the response to a pathbias probe, to ensure the
878 : * cell is recognized and the nonce and other probe
879 : * characteristics are as expected.
880 : *
881 : * If the response is valid, return 0. Otherwise return < 0.
882 : */
883 : int
884 0 : pathbias_check_probe_response(circuit_t *circ, const cell_t *cell)
885 : {
886 : /* Based on connection_edge_process_relay_cell() */
887 0 : relay_header_t rh;
888 0 : int reason;
889 0 : uint32_t ipv4_host;
890 0 : origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
891 :
892 0 : tor_assert(cell);
893 0 : tor_assert(ocirc);
894 0 : tor_assert(circ->purpose == CIRCUIT_PURPOSE_PATH_BIAS_TESTING);
895 :
896 0 : relay_header_unpack(&rh, cell->payload);
897 :
898 0 : reason = rh.length > 0 ?
899 0 : get_uint8(cell->payload+RELAY_HEADER_SIZE) : END_STREAM_REASON_MISC;
900 :
901 0 : if (rh.command == RELAY_COMMAND_END &&
902 0 : reason == END_STREAM_REASON_EXITPOLICY &&
903 0 : ocirc->pathbias_probe_id == rh.stream_id) {
904 :
905 : /* Check length+extract host: It is in network order after the reason code.
906 : * See connection_edge_end(). */
907 0 : if (rh.length < 9) { /* reason+ipv4+dns_ttl */
908 0 : log_notice(LD_PROTOCOL,
909 : "Short path bias probe response length field (%d).", rh.length);
910 0 : return - END_CIRC_REASON_TORPROTOCOL;
911 : }
912 :
913 0 : ipv4_host = ntohl(get_uint32(cell->payload+RELAY_HEADER_SIZE+1));
914 :
915 : /* Check nonce */
916 0 : if (ipv4_host == ocirc->pathbias_probe_nonce) {
917 0 : pathbias_mark_use_success(ocirc);
918 0 : circuit_read_valid_data(ocirc, rh.length);
919 0 : circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED);
920 0 : log_info(LD_CIRC,
921 : "Got valid path bias probe back for circ %d, stream %d.",
922 : ocirc->global_identifier, ocirc->pathbias_probe_id);
923 0 : return 0;
924 : } else {
925 0 : log_notice(LD_CIRC,
926 : "Got strange probe value 0x%x vs 0x%x back for circ %d, "
927 : "stream %d.", ipv4_host, ocirc->pathbias_probe_nonce,
928 : ocirc->global_identifier, ocirc->pathbias_probe_id);
929 0 : return -1;
930 : }
931 : }
932 0 : log_info(LD_CIRC,
933 : "Got another cell back back on pathbias probe circuit %d: "
934 : "Command: %d, Reason: %d, Stream-id: %d",
935 : ocirc->global_identifier, rh.command, reason, rh.stream_id);
936 0 : return -1;
937 : }
938 :
939 : /**
940 : * Check if a cell is counts as valid data for a circuit,
941 : * and if so, count it as valid.
942 : */
943 : void
944 526 : pathbias_count_valid_cells(circuit_t *circ, const cell_t *cell)
945 : {
946 526 : origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
947 526 : relay_header_t rh;
948 :
949 526 : relay_header_unpack(&rh, cell->payload);
950 :
951 : /* Check to see if this is a cell from a previous connection,
952 : * or is a request to close the circuit. */
953 526 : switch (rh.command) {
954 1 : case RELAY_COMMAND_TRUNCATED:
955 : /* Truncated cells can arrive on path bias circs. When they do,
956 : * just process them. This closes the circ, but it was junk anyway.
957 : * No reason to wait for the probe. */
958 1 : circuit_read_valid_data(ocirc, rh.length);
959 2 : circuit_truncated(TO_ORIGIN_CIRCUIT(circ),
960 1 : get_uint8(cell->payload + RELAY_HEADER_SIZE));
961 :
962 1 : break;
963 :
964 4 : case RELAY_COMMAND_END:
965 4 : if (connection_half_edge_is_valid_end(ocirc->half_streams,
966 4 : rh.stream_id)) {
967 2 : circuit_read_valid_data(TO_ORIGIN_CIRCUIT(circ), rh.length);
968 : }
969 : break;
970 :
971 504 : case RELAY_COMMAND_DATA:
972 504 : if (connection_half_edge_is_valid_data(ocirc->half_streams,
973 504 : rh.stream_id)) {
974 500 : circuit_read_valid_data(TO_ORIGIN_CIRCUIT(circ), rh.length);
975 : }
976 : break;
977 :
978 11 : case RELAY_COMMAND_SENDME:
979 11 : if (connection_half_edge_is_valid_sendme(ocirc->half_streams,
980 11 : rh.stream_id)) {
981 9 : circuit_read_valid_data(TO_ORIGIN_CIRCUIT(circ), rh.length);
982 : }
983 : break;
984 :
985 4 : case RELAY_COMMAND_CONNECTED:
986 4 : if (connection_half_edge_is_valid_connected(ocirc->half_streams,
987 4 : rh.stream_id)) {
988 1 : circuit_read_valid_data(TO_ORIGIN_CIRCUIT(circ), rh.length);
989 : }
990 : break;
991 :
992 2 : case RELAY_COMMAND_RESOLVED:
993 2 : if (connection_half_edge_is_valid_resolved(ocirc->half_streams,
994 2 : rh.stream_id)) {
995 1 : circuit_read_valid_data(TO_ORIGIN_CIRCUIT(circ), rh.length);
996 : }
997 : break;
998 : }
999 526 : }
1000 :
1001 : /**
1002 : * Check if a circuit was used and/or closed successfully.
1003 : *
1004 : * If we attempted to use the circuit to carry a stream but failed
1005 : * for whatever reason, or if the circuit mysteriously died before
1006 : * we could attach any streams, record these two cases.
1007 : *
1008 : * If we *have* successfully used the circuit, or it appears to
1009 : * have been closed by us locally, count it as a success.
1010 : *
1011 : * Returns 0 if we're done making decisions with the circ,
1012 : * or -1 if we want to probe it first.
1013 : */
1014 : int
1015 14 : pathbias_check_close(origin_circuit_t *ocirc, int reason)
1016 : {
1017 14 : circuit_t *circ = ô->base_;
1018 :
1019 14 : if (!pathbias_should_count(ocirc)) {
1020 : return 0;
1021 : }
1022 :
1023 0 : switch (ocirc->path_state) {
1024 : /* If the circuit was closed after building, but before use, we need
1025 : * to ensure we were the ones who tried to close it (and not a remote
1026 : * actor). */
1027 0 : case PATH_STATE_BUILD_SUCCEEDED:
1028 0 : if (reason & END_CIRC_REASON_FLAG_REMOTE) {
1029 : /* Remote circ close reasons on an unused circuit all could be bias */
1030 0 : log_info(LD_CIRC,
1031 : "Circuit %d remote-closed without successful use for reason %d. "
1032 : "Circuit purpose %d currently %d,%s. Len %d.",
1033 : ocirc->global_identifier,
1034 : reason, circ->purpose, ocirc->has_opened,
1035 : circuit_state_to_string(circ->state),
1036 : ocirc->build_state->desired_path_len);
1037 0 : pathbias_count_collapse(ocirc);
1038 0 : } else if ((reason & ~END_CIRC_REASON_FLAG_REMOTE)
1039 0 : == END_CIRC_REASON_CHANNEL_CLOSED &&
1040 0 : circ->n_chan &&
1041 0 : circ->n_chan->reason_for_closing
1042 : != CHANNEL_CLOSE_REQUESTED) {
1043 : /* If we didn't close the channel ourselves, it could be bias */
1044 : /* XXX: Only count bias if the network is live?
1045 : * What about clock jumps/suspends? */
1046 0 : log_info(LD_CIRC,
1047 : "Circuit %d's channel closed without successful use for reason "
1048 : "%d, channel reason %d. Circuit purpose %d currently %d,%s. Len "
1049 : "%d.", ocirc->global_identifier,
1050 : reason, circ->n_chan->reason_for_closing,
1051 : circ->purpose, ocirc->has_opened,
1052 : circuit_state_to_string(circ->state),
1053 : ocirc->build_state->desired_path_len);
1054 0 : pathbias_count_collapse(ocirc);
1055 : } else {
1056 0 : pathbias_count_successful_close(ocirc);
1057 : }
1058 : break;
1059 :
1060 : /* If we tried to use a circuit but failed, we should probe it to ensure
1061 : * it has not been tampered with. */
1062 0 : case PATH_STATE_USE_ATTEMPTED:
1063 : /* XXX: Only probe and/or count failure if the network is live?
1064 : * What about clock jumps/suspends? */
1065 0 : if (pathbias_send_usable_probe(circ) == 0)
1066 : return -1;
1067 : else
1068 0 : pathbias_count_use_failed(ocirc);
1069 :
1070 : /* Any circuit where there were attempted streams but no successful
1071 : * streams could be bias */
1072 0 : log_info(LD_CIRC,
1073 : "Circuit %d closed without successful use for reason %d. "
1074 : "Circuit purpose %d currently %d,%s. Len %d.",
1075 : ocirc->global_identifier,
1076 : reason, circ->purpose, ocirc->has_opened,
1077 : circuit_state_to_string(circ->state),
1078 : ocirc->build_state->desired_path_len);
1079 0 : break;
1080 :
1081 0 : case PATH_STATE_USE_SUCCEEDED:
1082 0 : pathbias_count_successful_close(ocirc);
1083 0 : pathbias_count_use_success(ocirc);
1084 0 : break;
1085 :
1086 0 : case PATH_STATE_USE_FAILED:
1087 0 : pathbias_count_use_failed(ocirc);
1088 0 : break;
1089 :
1090 : case PATH_STATE_NEW_CIRC:
1091 : case PATH_STATE_BUILD_ATTEMPTED:
1092 : case PATH_STATE_ALREADY_COUNTED:
1093 : default:
1094 : // Other states are uninteresting. No stats to count.
1095 : break;
1096 : }
1097 :
1098 0 : ocirc->path_state = PATH_STATE_ALREADY_COUNTED;
1099 :
1100 0 : return 0;
1101 : }
1102 :
1103 : /**
1104 : * Count a successfully closed circuit.
1105 : */
1106 : static void
1107 0 : pathbias_count_successful_close(origin_circuit_t *circ)
1108 : {
1109 0 : entry_guard_t *guard = NULL;
1110 0 : if (!pathbias_should_count(circ)) {
1111 : return;
1112 : }
1113 :
1114 0 : if (circ->cpath && circ->cpath->extend_info) {
1115 0 : guard = entry_guard_get_by_id_digest(
1116 0 : circ->cpath->extend_info->identity_digest);
1117 : }
1118 :
1119 0 : if (guard) {
1120 0 : guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
1121 :
1122 : /* In the long run: circuit_success ~= successful_circuit_close +
1123 : * circ_failure + stream_failure */
1124 0 : pb->successful_circuits_closed++;
1125 0 : entry_guards_changed();
1126 0 : } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
1127 : /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1128 : * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1129 : * No need to log that case. */
1130 0 : log_info(LD_CIRC,
1131 : "Successfully closed circuit has no known guard. "
1132 : "Circuit is a %s currently %s",
1133 : circuit_purpose_to_string(circ->base_.purpose),
1134 : circuit_state_to_string(circ->base_.state));
1135 : }
1136 : }
1137 :
1138 : /**
1139 : * Count a circuit that fails after it is built, but before it can
1140 : * carry any traffic.
1141 : *
1142 : * This is needed because there are ways to destroy a
1143 : * circuit after it has successfully completed. Right now, this is
1144 : * used for purely informational/debugging purposes.
1145 : */
1146 : static void
1147 0 : pathbias_count_collapse(origin_circuit_t *circ)
1148 : {
1149 0 : entry_guard_t *guard = NULL;
1150 :
1151 0 : if (!pathbias_should_count(circ)) {
1152 : return;
1153 : }
1154 :
1155 0 : if (circ->cpath && circ->cpath->extend_info) {
1156 0 : guard = entry_guard_get_by_id_digest(
1157 0 : circ->cpath->extend_info->identity_digest);
1158 : }
1159 :
1160 0 : if (guard) {
1161 0 : guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
1162 :
1163 0 : pb->collapsed_circuits++;
1164 0 : entry_guards_changed();
1165 0 : } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
1166 : /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1167 : * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1168 : * No need to log that case. */
1169 0 : log_info(LD_CIRC,
1170 : "Destroyed circuit has no known guard. "
1171 : "Circuit is a %s currently %s",
1172 : circuit_purpose_to_string(circ->base_.purpose),
1173 : circuit_state_to_string(circ->base_.state));
1174 : }
1175 : }
1176 :
1177 : /**
1178 : * Count a known failed circuit (because we could not probe it).
1179 : *
1180 : * This counter is informational.
1181 : */
1182 : static void
1183 0 : pathbias_count_use_failed(origin_circuit_t *circ)
1184 : {
1185 0 : entry_guard_t *guard = NULL;
1186 0 : if (!pathbias_should_count(circ)) {
1187 : return;
1188 : }
1189 :
1190 0 : if (circ->cpath && circ->cpath->extend_info) {
1191 0 : guard = entry_guard_get_by_id_digest(
1192 0 : circ->cpath->extend_info->identity_digest);
1193 : }
1194 :
1195 0 : if (guard) {
1196 0 : guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
1197 :
1198 0 : pb->unusable_circuits++;
1199 0 : entry_guards_changed();
1200 0 : } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
1201 : /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1202 : * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1203 : * No need to log that case. */
1204 : /* XXX note cut-and-paste code in this function compared to nearby
1205 : * functions. Would be nice to refactor. -RD */
1206 0 : log_info(LD_CIRC,
1207 : "Stream-failing circuit has no known guard. "
1208 : "Circuit is a %s currently %s",
1209 : circuit_purpose_to_string(circ->base_.purpose),
1210 : circuit_state_to_string(circ->base_.state));
1211 : }
1212 : }
1213 :
1214 : /**
1215 : * Count timeouts for path bias log messages.
1216 : *
1217 : * These counts are purely informational.
1218 : */
1219 : void
1220 1 : pathbias_count_timeout(origin_circuit_t *circ)
1221 : {
1222 1 : entry_guard_t *guard = NULL;
1223 :
1224 1 : if (!pathbias_should_count(circ)) {
1225 : return;
1226 : }
1227 :
1228 : /* For hidden service circs, they can actually be used
1229 : * successfully and then time out later (because
1230 : * the other side declines to use them). */
1231 0 : if (circ->path_state == PATH_STATE_USE_SUCCEEDED) {
1232 : return;
1233 : }
1234 :
1235 0 : if (circ->cpath && circ->cpath->extend_info) {
1236 0 : guard = entry_guard_get_by_id_digest(
1237 0 : circ->cpath->extend_info->identity_digest);
1238 : }
1239 :
1240 0 : if (guard) {
1241 0 : guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
1242 :
1243 0 : pb->timeouts++;
1244 0 : entry_guards_changed();
1245 : }
1246 : }
1247 :
1248 : /**
1249 : * Helper function to count all of the currently opened circuits
1250 : * for a guard that are in a given path state range. The state
1251 : * range is inclusive on both ends.
1252 : */
1253 : static int
1254 29 : pathbias_count_circs_in_states(entry_guard_t *guard,
1255 : path_state_t from,
1256 : path_state_t to)
1257 : {
1258 29 : int open_circuits = 0;
1259 :
1260 : /* Count currently open circuits. Give them the benefit of the doubt. */
1261 29 : SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
1262 0 : origin_circuit_t *ocirc = NULL;
1263 0 : if (!CIRCUIT_IS_ORIGIN(circ) || /* didn't originate here */
1264 0 : circ->marked_for_close) /* already counted */
1265 0 : continue;
1266 :
1267 0 : ocirc = TO_ORIGIN_CIRCUIT(circ);
1268 :
1269 0 : if (!ocirc->cpath || !ocirc->cpath->extend_info)
1270 0 : continue;
1271 :
1272 0 : if (ocirc->path_state >= from &&
1273 0 : ocirc->path_state <= to &&
1274 0 : pathbias_should_count(ocirc) &&
1275 0 : fast_memeq(entry_guard_get_rsa_id_digest(guard),
1276 : ocirc->cpath->extend_info->identity_digest,
1277 : DIGEST_LEN)) {
1278 0 : log_debug(LD_CIRC, "Found opened circuit %d in path_state %s",
1279 : ocirc->global_identifier,
1280 : pathbias_state_to_string(ocirc->path_state));
1281 0 : open_circuits++;
1282 : }
1283 : }
1284 0 : SMARTLIST_FOREACH_END(circ);
1285 :
1286 29 : return open_circuits;
1287 : }
1288 :
1289 : /**
1290 : * Return the number of circuits counted as successfully closed for
1291 : * this guard.
1292 : *
1293 : * Also add in the currently open circuits to give them the benefit
1294 : * of the doubt.
1295 : */
1296 : double
1297 20 : pathbias_get_close_success_count(entry_guard_t *guard)
1298 : {
1299 20 : guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
1300 :
1301 40 : return pb->successful_circuits_closed +
1302 20 : pathbias_count_circs_in_states(guard,
1303 : PATH_STATE_BUILD_SUCCEEDED,
1304 : PATH_STATE_USE_SUCCEEDED);
1305 : }
1306 :
1307 : /**
1308 : * Return the number of circuits counted as successfully used
1309 : * this guard.
1310 : *
1311 : * Also add in the currently open circuits that we are attempting
1312 : * to use to give them the benefit of the doubt.
1313 : */
1314 : double
1315 9 : pathbias_get_use_success_count(entry_guard_t *guard)
1316 : {
1317 9 : guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
1318 :
1319 18 : return pb->use_successes +
1320 9 : pathbias_count_circs_in_states(guard,
1321 : PATH_STATE_USE_ATTEMPTED,
1322 : PATH_STATE_USE_SUCCEEDED);
1323 : }
1324 :
1325 : /**
1326 : * Check the path bias use rate against our consensus parameter limits.
1327 : *
1328 : * Emits a log message if the use success rates are too low.
1329 : *
1330 : * If pathbias_get_dropguards() is set, we also disable the use of
1331 : * very failure prone guards.
1332 : */
1333 : static void
1334 0 : pathbias_measure_use_rate(entry_guard_t *guard)
1335 : {
1336 0 : const or_options_t *options = get_options();
1337 0 : guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
1338 :
1339 0 : if (pb->use_attempts > pathbias_get_min_use(options)) {
1340 : /* Note: We rely on the < comparison here to allow us to set a 0
1341 : * rate and disable the feature entirely. If refactoring, don't
1342 : * change to <= */
1343 0 : if (pathbias_get_use_success_count(guard)/pb->use_attempts
1344 0 : < pathbias_get_extreme_use_rate(options)) {
1345 : /* Dropping is currently disabled by default. */
1346 0 : if (pathbias_get_dropguards(options)) {
1347 0 : if (!pb->path_bias_disabled) {
1348 0 : log_warn(LD_CIRC,
1349 : "Guard %s is failing to carry an extremely large "
1350 : "amount of stream on its circuits. "
1351 : "To avoid potential route manipulation attacks, Tor has "
1352 : "disabled use of this guard. "
1353 : "Use counts are %ld/%ld. Success counts are %ld/%ld. "
1354 : "%ld circuits completed, %ld were unusable, %ld collapsed, "
1355 : "and %ld timed out. "
1356 : "For reference, your timeout cutoff is %ld seconds.",
1357 : entry_guard_describe(guard),
1358 : tor_lround(pathbias_get_use_success_count(guard)),
1359 : tor_lround(pb->use_attempts),
1360 : tor_lround(pathbias_get_close_success_count(guard)),
1361 : tor_lround(pb->circ_attempts),
1362 : tor_lround(pb->circ_successes),
1363 : tor_lround(pb->unusable_circuits),
1364 : tor_lround(pb->collapsed_circuits),
1365 : tor_lround(pb->timeouts),
1366 : tor_lround(get_circuit_build_close_time_ms()/1000));
1367 0 : pb->path_bias_disabled = 1;
1368 0 : return;
1369 : }
1370 0 : } else if (!pb->path_bias_use_extreme) {
1371 0 : pb->path_bias_use_extreme = 1;
1372 0 : log_warn(LD_CIRC,
1373 : "Guard %s is failing to carry an extremely large "
1374 : "amount of streams on its circuits. "
1375 : "This could indicate a route manipulation attack, network "
1376 : "overload, bad local network connectivity, or a bug. "
1377 : "Use counts are %ld/%ld. Success counts are %ld/%ld. "
1378 : "%ld circuits completed, %ld were unusable, %ld collapsed, "
1379 : "and %ld timed out. "
1380 : "For reference, your timeout cutoff is %ld seconds.",
1381 : entry_guard_describe(guard),
1382 : tor_lround(pathbias_get_use_success_count(guard)),
1383 : tor_lround(pb->use_attempts),
1384 : tor_lround(pathbias_get_close_success_count(guard)),
1385 : tor_lround(pb->circ_attempts),
1386 : tor_lround(pb->circ_successes),
1387 : tor_lround(pb->unusable_circuits),
1388 : tor_lround(pb->collapsed_circuits),
1389 : tor_lround(pb->timeouts),
1390 : tor_lround(get_circuit_build_close_time_ms()/1000));
1391 : }
1392 0 : } else if (pathbias_get_use_success_count(guard)/pb->use_attempts
1393 0 : < pathbias_get_notice_use_rate(options)) {
1394 0 : if (!pb->path_bias_use_noticed) {
1395 0 : pb->path_bias_use_noticed = 1;
1396 0 : log_notice(LD_CIRC,
1397 : "Guard %s is failing to carry more streams on its "
1398 : "circuits than usual. "
1399 : "Most likely this means the Tor network is overloaded "
1400 : "or your network connection is poor. "
1401 : "Use counts are %ld/%ld. Success counts are %ld/%ld. "
1402 : "%ld circuits completed, %ld were unusable, %ld collapsed, "
1403 : "and %ld timed out. "
1404 : "For reference, your timeout cutoff is %ld seconds.",
1405 : entry_guard_describe(guard),
1406 : tor_lround(pathbias_get_use_success_count(guard)),
1407 : tor_lround(pb->use_attempts),
1408 : tor_lround(pathbias_get_close_success_count(guard)),
1409 : tor_lround(pb->circ_attempts),
1410 : tor_lround(pb->circ_successes),
1411 : tor_lround(pb->unusable_circuits),
1412 : tor_lround(pb->collapsed_circuits),
1413 : tor_lround(pb->timeouts),
1414 : tor_lround(get_circuit_build_close_time_ms()/1000));
1415 : }
1416 : }
1417 : }
1418 : }
1419 :
1420 : /**
1421 : * Check the path bias circuit close status rates against our consensus
1422 : * parameter limits.
1423 : *
1424 : * Emits a log message if the use success rates are too low.
1425 : *
1426 : * If pathbias_get_dropguards() is set, we also disable the use of
1427 : * very failure prone guards.
1428 : *
1429 : * XXX: This function shares similar log messages and checks to
1430 : * pathbias_measure_use_rate(). It may be possible to combine them
1431 : * eventually, especially if we can ever remove the need for 3
1432 : * levels of closure warns (if the overall circuit failure rate
1433 : * goes down with ntor). One way to do so would be to multiply
1434 : * the build rate with the use rate to get an idea of the total
1435 : * fraction of the total network paths the user is able to use.
1436 : * See ticket #8159.
1437 : */
1438 : static void
1439 0 : pathbias_measure_close_rate(entry_guard_t *guard)
1440 : {
1441 0 : const or_options_t *options = get_options();
1442 0 : guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
1443 :
1444 0 : if (pb->circ_attempts > pathbias_get_min_circs(options)) {
1445 : /* Note: We rely on the < comparison here to allow us to set a 0
1446 : * rate and disable the feature entirely. If refactoring, don't
1447 : * change to <= */
1448 0 : if (pathbias_get_close_success_count(guard)/pb->circ_attempts
1449 0 : < pathbias_get_extreme_rate(options)) {
1450 : /* Dropping is currently disabled by default. */
1451 0 : if (pathbias_get_dropguards(options)) {
1452 0 : if (!pb->path_bias_disabled) {
1453 0 : log_warn(LD_CIRC,
1454 : "Guard %s is failing an extremely large "
1455 : "amount of circuits. "
1456 : "To avoid potential route manipulation attacks, Tor has "
1457 : "disabled use of this guard. "
1458 : "Success counts are %ld/%ld. Use counts are %ld/%ld. "
1459 : "%ld circuits completed, %ld were unusable, %ld collapsed, "
1460 : "and %ld timed out. "
1461 : "For reference, your timeout cutoff is %ld seconds.",
1462 : entry_guard_describe(guard),
1463 : tor_lround(pathbias_get_close_success_count(guard)),
1464 : tor_lround(pb->circ_attempts),
1465 : tor_lround(pathbias_get_use_success_count(guard)),
1466 : tor_lround(pb->use_attempts),
1467 : tor_lround(pb->circ_successes),
1468 : tor_lround(pb->unusable_circuits),
1469 : tor_lround(pb->collapsed_circuits),
1470 : tor_lround(pb->timeouts),
1471 : tor_lround(get_circuit_build_close_time_ms()/1000));
1472 0 : pb->path_bias_disabled = 1;
1473 0 : return;
1474 : }
1475 0 : } else if (!pb->path_bias_extreme) {
1476 0 : pb->path_bias_extreme = 1;
1477 0 : log_warn(LD_CIRC,
1478 : "Guard %s is failing an extremely large "
1479 : "amount of circuits. "
1480 : "This could indicate a route manipulation attack, "
1481 : "extreme network overload, or a bug. "
1482 : "Success counts are %ld/%ld. Use counts are %ld/%ld. "
1483 : "%ld circuits completed, %ld were unusable, %ld collapsed, "
1484 : "and %ld timed out. "
1485 : "For reference, your timeout cutoff is %ld seconds.",
1486 : entry_guard_describe(guard),
1487 : tor_lround(pathbias_get_close_success_count(guard)),
1488 : tor_lround(pb->circ_attempts),
1489 : tor_lround(pathbias_get_use_success_count(guard)),
1490 : tor_lround(pb->use_attempts),
1491 : tor_lround(pb->circ_successes),
1492 : tor_lround(pb->unusable_circuits),
1493 : tor_lround(pb->collapsed_circuits),
1494 : tor_lround(pb->timeouts),
1495 : tor_lround(get_circuit_build_close_time_ms()/1000));
1496 : }
1497 0 : } else if (pathbias_get_close_success_count(guard)/pb->circ_attempts
1498 0 : < pathbias_get_warn_rate(options)) {
1499 0 : if (!pb->path_bias_warned) {
1500 0 : pb->path_bias_warned = 1;
1501 0 : log_warn(LD_CIRC,
1502 : "Guard %s is failing a very large "
1503 : "amount of circuits. "
1504 : "Most likely this means the Tor network is "
1505 : "overloaded, but it could also mean an attack against "
1506 : "you or potentially the guard itself. "
1507 : "Success counts are %ld/%ld. Use counts are %ld/%ld. "
1508 : "%ld circuits completed, %ld were unusable, %ld collapsed, "
1509 : "and %ld timed out. "
1510 : "For reference, your timeout cutoff is %ld seconds.",
1511 : entry_guard_describe(guard),
1512 : tor_lround(pathbias_get_close_success_count(guard)),
1513 : tor_lround(pb->circ_attempts),
1514 : tor_lround(pathbias_get_use_success_count(guard)),
1515 : tor_lround(pb->use_attempts),
1516 : tor_lround(pb->circ_successes),
1517 : tor_lround(pb->unusable_circuits),
1518 : tor_lround(pb->collapsed_circuits),
1519 : tor_lround(pb->timeouts),
1520 : tor_lround(get_circuit_build_close_time_ms()/1000));
1521 : }
1522 0 : } else if (pathbias_get_close_success_count(guard)/pb->circ_attempts
1523 0 : < pathbias_get_notice_rate(options)) {
1524 0 : if (!pb->path_bias_noticed) {
1525 0 : pb->path_bias_noticed = 1;
1526 0 : log_notice(LD_CIRC,
1527 : "Guard %s is failing more circuits than "
1528 : "usual. "
1529 : "Most likely this means the Tor network is overloaded. "
1530 : "Success counts are %ld/%ld. Use counts are %ld/%ld. "
1531 : "%ld circuits completed, %ld were unusable, %ld collapsed, "
1532 : "and %ld timed out. "
1533 : "For reference, your timeout cutoff is %ld seconds.",
1534 : entry_guard_describe(guard),
1535 : tor_lround(pathbias_get_close_success_count(guard)),
1536 : tor_lround(pb->circ_attempts),
1537 : tor_lround(pathbias_get_use_success_count(guard)),
1538 : tor_lround(pb->use_attempts),
1539 : tor_lround(pb->circ_successes),
1540 : tor_lround(pb->unusable_circuits),
1541 : tor_lround(pb->collapsed_circuits),
1542 : tor_lround(pb->timeouts),
1543 : tor_lround(get_circuit_build_close_time_ms()/1000));
1544 : }
1545 : }
1546 : }
1547 : }
1548 :
1549 : /**
1550 : * This function scales the path bias use rates if we have
1551 : * more data than the scaling threshold. This allows us to
1552 : * be more sensitive to recent measurements.
1553 : *
1554 : * XXX: The attempt count transfer stuff here might be done
1555 : * better by keeping separate pending counters that get
1556 : * transferred at circuit close. See ticket #8160.
1557 : */
1558 : static void
1559 0 : pathbias_scale_close_rates(entry_guard_t *guard)
1560 : {
1561 0 : const or_options_t *options = get_options();
1562 0 : guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
1563 :
1564 : /* If we get a ton of circuits, just scale everything down */
1565 0 : if (pb->circ_attempts > pathbias_get_scale_threshold(options)) {
1566 0 : double scale_ratio = pathbias_get_scale_ratio(options);
1567 0 : int opened_attempts = pathbias_count_circs_in_states(guard,
1568 : PATH_STATE_BUILD_ATTEMPTED, PATH_STATE_BUILD_ATTEMPTED);
1569 0 : int opened_built = pathbias_count_circs_in_states(guard,
1570 : PATH_STATE_BUILD_SUCCEEDED,
1571 : PATH_STATE_USE_FAILED);
1572 : /* Verify that the counts are sane before and after scaling */
1573 0 : int counts_are_sane = (pb->circ_attempts >= pb->circ_successes);
1574 :
1575 0 : pb->circ_attempts -= (opened_attempts+opened_built);
1576 0 : pb->circ_successes -= opened_built;
1577 :
1578 0 : pb->circ_attempts *= scale_ratio;
1579 0 : pb->circ_successes *= scale_ratio;
1580 0 : pb->timeouts *= scale_ratio;
1581 0 : pb->successful_circuits_closed *= scale_ratio;
1582 0 : pb->collapsed_circuits *= scale_ratio;
1583 0 : pb->unusable_circuits *= scale_ratio;
1584 :
1585 0 : pb->circ_attempts += (opened_attempts+opened_built);
1586 0 : pb->circ_successes += opened_built;
1587 :
1588 0 : entry_guards_changed();
1589 :
1590 0 : log_info(LD_CIRC,
1591 : "Scaled pathbias counts to (%f,%f)/%f (%d/%d open) for guard "
1592 : "%s",
1593 : pb->circ_successes, pb->successful_circuits_closed,
1594 : pb->circ_attempts, opened_built, opened_attempts,
1595 : entry_guard_describe(guard));
1596 :
1597 : /* Have the counts just become invalid by this scaling attempt? */
1598 0 : if (counts_are_sane && pb->circ_attempts < pb->circ_successes) {
1599 0 : log_notice(LD_BUG,
1600 : "Scaling has mangled pathbias counts to %f/%f (%d/%d open) "
1601 : "for guard %s",
1602 : pb->circ_successes, pb->circ_attempts, opened_built,
1603 : opened_attempts,
1604 : entry_guard_describe(guard));
1605 : }
1606 : }
1607 0 : }
1608 :
1609 : /**
1610 : * This function scales the path bias circuit close rates if we have
1611 : * more data than the scaling threshold. This allows us to be more
1612 : * sensitive to recent measurements.
1613 : *
1614 : * XXX: The attempt count transfer stuff here might be done
1615 : * better by keeping separate pending counters that get
1616 : * transferred at circuit close. See ticket #8160.
1617 : */
1618 : void
1619 0 : pathbias_scale_use_rates(entry_guard_t *guard)
1620 : {
1621 0 : const or_options_t *options = get_options();
1622 0 : guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
1623 :
1624 : /* If we get a ton of circuits, just scale everything down */
1625 0 : if (pb->use_attempts > pathbias_get_scale_use_threshold(options)) {
1626 0 : double scale_ratio = pathbias_get_scale_ratio(options);
1627 0 : int opened_attempts = pathbias_count_circs_in_states(guard,
1628 : PATH_STATE_USE_ATTEMPTED, PATH_STATE_USE_SUCCEEDED);
1629 : /* Verify that the counts are sane before and after scaling */
1630 0 : int counts_are_sane = (pb->use_attempts >= pb->use_successes);
1631 :
1632 0 : pb->use_attempts -= opened_attempts;
1633 :
1634 0 : pb->use_attempts *= scale_ratio;
1635 0 : pb->use_successes *= scale_ratio;
1636 :
1637 0 : pb->use_attempts += opened_attempts;
1638 :
1639 0 : log_info(LD_CIRC,
1640 : "Scaled pathbias use counts to %f/%f (%d open) for guard %s",
1641 : pb->use_successes, pb->use_attempts, opened_attempts,
1642 : entry_guard_describe(guard));
1643 :
1644 : /* Have the counts just become invalid by this scaling attempt? */
1645 0 : if (counts_are_sane && pb->use_attempts < pb->use_successes) {
1646 0 : log_notice(LD_BUG,
1647 : "Scaling has mangled pathbias usage counts to %f/%f "
1648 : "(%d open) for guard %s",
1649 : pb->circ_successes, pb->circ_attempts,
1650 : opened_attempts, entry_guard_describe(guard));
1651 : }
1652 :
1653 0 : entry_guards_changed();
1654 : }
1655 0 : }
|
