circpathbias.c 55 KB

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