circpathbias.c 55 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572
  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. entry_guard_mark_bad(guard);
  1153. return;
  1154. }
  1155. } else if (!pb->path_bias_use_extreme) {
  1156. pb->path_bias_use_extreme = 1;
  1157. log_warn(LD_CIRC,
  1158. "Your Guard %s is failing to carry an extremely large "
  1159. "amount of streams on its circuits. "
  1160. "This could indicate a route manipulation attack, network "
  1161. "overload, bad local network connectivity, or a bug. "
  1162. "Use counts are %ld/%ld. Success counts are %ld/%ld. "
  1163. "%ld circuits completed, %ld were unusable, %ld collapsed, "
  1164. "and %ld timed out. "
  1165. "For reference, your timeout cutoff is %ld seconds.",
  1166. entry_guard_describe(guard),
  1167. tor_lround(pathbias_get_use_success_count(guard)),
  1168. tor_lround(pb->use_attempts),
  1169. tor_lround(pathbias_get_close_success_count(guard)),
  1170. tor_lround(pb->circ_attempts),
  1171. tor_lround(pb->circ_successes),
  1172. tor_lround(pb->unusable_circuits),
  1173. tor_lround(pb->collapsed_circuits),
  1174. tor_lround(pb->timeouts),
  1175. tor_lround(get_circuit_build_close_time_ms()/1000));
  1176. }
  1177. } else if (pathbias_get_use_success_count(guard)/pb->use_attempts
  1178. < pathbias_get_notice_use_rate(options)) {
  1179. if (!pb->path_bias_use_noticed) {
  1180. pb->path_bias_use_noticed = 1;
  1181. log_notice(LD_CIRC,
  1182. "Your Guard %s is failing to carry more streams on its "
  1183. "circuits than usual. "
  1184. "Most likely this means the Tor network is overloaded "
  1185. "or your network connection is poor. "
  1186. "Use counts are %ld/%ld. Success counts are %ld/%ld. "
  1187. "%ld circuits completed, %ld were unusable, %ld collapsed, "
  1188. "and %ld timed out. "
  1189. "For reference, your timeout cutoff is %ld seconds.",
  1190. entry_guard_describe(guard),
  1191. tor_lround(pathbias_get_use_success_count(guard)),
  1192. tor_lround(pb->use_attempts),
  1193. tor_lround(pathbias_get_close_success_count(guard)),
  1194. tor_lround(pb->circ_attempts),
  1195. tor_lround(pb->circ_successes),
  1196. tor_lround(pb->unusable_circuits),
  1197. tor_lround(pb->collapsed_circuits),
  1198. tor_lround(pb->timeouts),
  1199. tor_lround(get_circuit_build_close_time_ms()/1000));
  1200. }
  1201. }
  1202. }
  1203. }
  1204. /**
  1205. * Check the path bias circuit close status rates against our consensus
  1206. * parameter limits.
  1207. *
  1208. * Emits a log message if the use success rates are too low.
  1209. *
  1210. * If pathbias_get_dropguards() is set, we also disable the use of
  1211. * very failure prone guards.
  1212. *
  1213. * XXX: This function shares similar log messages and checks to
  1214. * pathbias_measure_use_rate(). It may be possible to combine them
  1215. * eventually, especially if we can ever remove the need for 3
  1216. * levels of closure warns (if the overall circuit failure rate
  1217. * goes down with ntor). One way to do so would be to multiply
  1218. * the build rate with the use rate to get an idea of the total
  1219. * fraction of the total network paths the user is able to use.
  1220. * See ticket #8159.
  1221. */
  1222. static void
  1223. pathbias_measure_close_rate(entry_guard_t *guard)
  1224. {
  1225. const or_options_t *options = get_options();
  1226. guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
  1227. if (pb->circ_attempts > pathbias_get_min_circs(options)) {
  1228. /* Note: We rely on the < comparison here to allow us to set a 0
  1229. * rate and disable the feature entirely. If refactoring, don't
  1230. * change to <= */
  1231. if (pathbias_get_close_success_count(guard)/pb->circ_attempts
  1232. < pathbias_get_extreme_rate(options)) {
  1233. /* Dropping is currently disabled by default. */
  1234. if (pathbias_get_dropguards(options)) {
  1235. if (!pb->path_bias_disabled) {
  1236. log_warn(LD_CIRC,
  1237. "Your Guard %s is failing an extremely large "
  1238. "amount of circuits. "
  1239. "To avoid potential route manipulation attacks, Tor has "
  1240. "disabled use of this guard. "
  1241. "Success counts are %ld/%ld. Use counts are %ld/%ld. "
  1242. "%ld circuits completed, %ld were unusable, %ld collapsed, "
  1243. "and %ld timed out. "
  1244. "For reference, your timeout cutoff is %ld seconds.",
  1245. entry_guard_describe(guard),
  1246. tor_lround(pathbias_get_close_success_count(guard)),
  1247. tor_lround(pb->circ_attempts),
  1248. tor_lround(pathbias_get_use_success_count(guard)),
  1249. tor_lround(pb->use_attempts),
  1250. tor_lround(pb->circ_successes),
  1251. tor_lround(pb->unusable_circuits),
  1252. tor_lround(pb->collapsed_circuits),
  1253. tor_lround(pb->timeouts),
  1254. tor_lround(get_circuit_build_close_time_ms()/1000));
  1255. pb->path_bias_disabled = 1;
  1256. entry_guard_mark_bad(guard);
  1257. return;
  1258. }
  1259. } else if (!pb->path_bias_extreme) {
  1260. pb->path_bias_extreme = 1;
  1261. log_warn(LD_CIRC,
  1262. "Your Guard %s is failing an extremely large "
  1263. "amount of circuits. "
  1264. "This could indicate a route manipulation attack, "
  1265. "extreme network overload, or a bug. "
  1266. "Success counts are %ld/%ld. Use counts are %ld/%ld. "
  1267. "%ld circuits completed, %ld were unusable, %ld collapsed, "
  1268. "and %ld timed out. "
  1269. "For reference, your timeout cutoff is %ld seconds.",
  1270. entry_guard_describe(guard),
  1271. tor_lround(pathbias_get_close_success_count(guard)),
  1272. tor_lround(pb->circ_attempts),
  1273. tor_lround(pathbias_get_use_success_count(guard)),
  1274. tor_lround(pb->use_attempts),
  1275. tor_lround(pb->circ_successes),
  1276. tor_lround(pb->unusable_circuits),
  1277. tor_lround(pb->collapsed_circuits),
  1278. tor_lround(pb->timeouts),
  1279. tor_lround(get_circuit_build_close_time_ms()/1000));
  1280. }
  1281. } else if (pathbias_get_close_success_count(guard)/pb->circ_attempts
  1282. < pathbias_get_warn_rate(options)) {
  1283. if (!pb->path_bias_warned) {
  1284. pb->path_bias_warned = 1;
  1285. log_warn(LD_CIRC,
  1286. "Your Guard %s is failing a very large "
  1287. "amount of circuits. "
  1288. "Most likely this means the Tor network is "
  1289. "overloaded, but it could also mean an attack against "
  1290. "you or potentially the guard itself. "
  1291. "Success counts are %ld/%ld. Use counts are %ld/%ld. "
  1292. "%ld circuits completed, %ld were unusable, %ld collapsed, "
  1293. "and %ld timed out. "
  1294. "For reference, your timeout cutoff is %ld seconds.",
  1295. entry_guard_describe(guard),
  1296. tor_lround(pathbias_get_close_success_count(guard)),
  1297. tor_lround(pb->circ_attempts),
  1298. tor_lround(pathbias_get_use_success_count(guard)),
  1299. tor_lround(pb->use_attempts),
  1300. tor_lround(pb->circ_successes),
  1301. tor_lround(pb->unusable_circuits),
  1302. tor_lround(pb->collapsed_circuits),
  1303. tor_lround(pb->timeouts),
  1304. tor_lround(get_circuit_build_close_time_ms()/1000));
  1305. }
  1306. } else if (pathbias_get_close_success_count(guard)/pb->circ_attempts
  1307. < pathbias_get_notice_rate(options)) {
  1308. if (!pb->path_bias_noticed) {
  1309. pb->path_bias_noticed = 1;
  1310. log_notice(LD_CIRC,
  1311. "Your Guard %s is failing more circuits than "
  1312. "usual. "
  1313. "Most likely this means the Tor network is overloaded. "
  1314. "Success counts are %ld/%ld. Use counts are %ld/%ld. "
  1315. "%ld circuits completed, %ld were unusable, %ld collapsed, "
  1316. "and %ld timed out. "
  1317. "For reference, your timeout cutoff is %ld seconds.",
  1318. entry_guard_describe(guard),
  1319. tor_lround(pathbias_get_close_success_count(guard)),
  1320. tor_lround(pb->circ_attempts),
  1321. tor_lround(pathbias_get_use_success_count(guard)),
  1322. tor_lround(pb->use_attempts),
  1323. tor_lround(pb->circ_successes),
  1324. tor_lround(pb->unusable_circuits),
  1325. tor_lround(pb->collapsed_circuits),
  1326. tor_lround(pb->timeouts),
  1327. tor_lround(get_circuit_build_close_time_ms()/1000));
  1328. }
  1329. }
  1330. }
  1331. }
  1332. /**
  1333. * This function scales the path bias use rates if we have
  1334. * more data than the scaling threshold. This allows us to
  1335. * be more sensitive to recent measurements.
  1336. *
  1337. * XXX: The attempt count transfer stuff here might be done
  1338. * better by keeping separate pending counters that get
  1339. * transfered at circuit close. See ticket #8160.
  1340. */
  1341. static void
  1342. pathbias_scale_close_rates(entry_guard_t *guard)
  1343. {
  1344. const or_options_t *options = get_options();
  1345. guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
  1346. /* If we get a ton of circuits, just scale everything down */
  1347. if (pb->circ_attempts > pathbias_get_scale_threshold(options)) {
  1348. double scale_ratio = pathbias_get_scale_ratio(options);
  1349. int opened_attempts = pathbias_count_circs_in_states(guard,
  1350. PATH_STATE_BUILD_ATTEMPTED, PATH_STATE_BUILD_ATTEMPTED);
  1351. int opened_built = pathbias_count_circs_in_states(guard,
  1352. PATH_STATE_BUILD_SUCCEEDED,
  1353. PATH_STATE_USE_FAILED);
  1354. /* Verify that the counts are sane before and after scaling */
  1355. int counts_are_sane = (pb->circ_attempts >= pb->circ_successes);
  1356. pb->circ_attempts -= (opened_attempts+opened_built);
  1357. pb->circ_successes -= opened_built;
  1358. pb->circ_attempts *= scale_ratio;
  1359. pb->circ_successes *= scale_ratio;
  1360. pb->timeouts *= scale_ratio;
  1361. pb->successful_circuits_closed *= scale_ratio;
  1362. pb->collapsed_circuits *= scale_ratio;
  1363. pb->unusable_circuits *= scale_ratio;
  1364. pb->circ_attempts += (opened_attempts+opened_built);
  1365. pb->circ_successes += opened_built;
  1366. entry_guards_changed();
  1367. log_info(LD_CIRC,
  1368. "Scaled pathbias counts to (%f,%f)/%f (%d/%d open) for guard "
  1369. "%s",
  1370. pb->circ_successes, pb->successful_circuits_closed,
  1371. pb->circ_attempts, opened_built, opened_attempts,
  1372. entry_guard_describe(guard));
  1373. /* Have the counts just become invalid by this scaling attempt? */
  1374. if (counts_are_sane && pb->circ_attempts < pb->circ_successes) {
  1375. log_notice(LD_BUG,
  1376. "Scaling has mangled pathbias counts to %f/%f (%d/%d open) "
  1377. "for guard %s",
  1378. pb->circ_successes, pb->circ_attempts, opened_built,
  1379. opened_attempts,
  1380. entry_guard_describe(guard));
  1381. }
  1382. }
  1383. }
  1384. /**
  1385. * This function scales the path bias circuit close rates if we have
  1386. * more data than the scaling threshold. This allows us to be more
  1387. * sensitive to recent measurements.
  1388. *
  1389. * XXX: The attempt count transfer stuff here might be done
  1390. * better by keeping separate pending counters that get
  1391. * transfered at circuit close. See ticket #8160.
  1392. */
  1393. void
  1394. pathbias_scale_use_rates(entry_guard_t *guard)
  1395. {
  1396. const or_options_t *options = get_options();
  1397. guard_pathbias_t *pb = entry_guard_get_pathbias_state(guard);
  1398. /* If we get a ton of circuits, just scale everything down */
  1399. if (pb->use_attempts > pathbias_get_scale_use_threshold(options)) {
  1400. double scale_ratio = pathbias_get_scale_ratio(options);
  1401. int opened_attempts = pathbias_count_circs_in_states(guard,
  1402. PATH_STATE_USE_ATTEMPTED, PATH_STATE_USE_SUCCEEDED);
  1403. /* Verify that the counts are sane before and after scaling */
  1404. int counts_are_sane = (pb->use_attempts >= pb->use_successes);
  1405. pb->use_attempts -= opened_attempts;
  1406. pb->use_attempts *= scale_ratio;
  1407. pb->use_successes *= scale_ratio;
  1408. pb->use_attempts += opened_attempts;
  1409. log_info(LD_CIRC,
  1410. "Scaled pathbias use counts to %f/%f (%d open) for guard %s",
  1411. pb->use_successes, pb->use_attempts, opened_attempts,
  1412. entry_guard_describe(guard));
  1413. /* Have the counts just become invalid by this scaling attempt? */
  1414. if (counts_are_sane && pb->use_attempts < pb->use_successes) {
  1415. log_notice(LD_BUG,
  1416. "Scaling has mangled pathbias usage counts to %f/%f "
  1417. "(%d open) for guard %s",
  1418. pb->circ_successes, pb->circ_attempts,
  1419. opened_attempts, entry_guard_describe(guard));
  1420. }
  1421. entry_guards_changed();
  1422. }
  1423. }