circpathbias.c 55 KB

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