1 //! Code for estimating good values for circuit timeouts. 2 //! 3 //! We need good circuit timeouts for two reasons: first, they help 4 //! user experience. If user wait too long for their circuits, or if 5 //! they use exceptionally slow circuits, then Tor will feel really 6 //! slow. Second, these timeouts are actually a security 7 //! property. (XXXX explain why!) 8 9 use std::time::Duration; 10 11 pub(crate) mod estimator; 12 pub(crate) mod pareto; 13 pub(crate) mod readonly; 14 15 pub(crate) use estimator::Estimator; 16 17 /// An object that calculates circuit timeout thresholds from the history 18 /// of circuit build times. 19 pub(crate) trait TimeoutEstimator { 20 /// Record that a given circuit hop has completed. 21 /// 22 /// The `hop` number is a zero-indexed value for which hop just completed. 23 /// 24 /// The `delay` value is the amount of time after we first launched the 25 /// circuit. 26 /// 27 /// If this is the last hop of the circuit, then `is_last` is true. note_hop_completed(&mut self, hop: u8, delay: Duration, is_last: bool)28 fn note_hop_completed(&mut self, hop: u8, delay: Duration, is_last: bool); 29 30 /// Record that a circuit failed to complete because it took too long. 31 /// 32 /// The `hop` number is a the number of hops that were successfully 33 /// completed. 34 /// 35 /// The `delay` number is the amount of time after we first launched the 36 /// circuit. note_circ_timeout(&mut self, hop: u8, delay: Duration)37 fn note_circ_timeout(&mut self, hop: u8, delay: Duration); 38 39 /// Return the current estimation for how long we should wait for a given 40 /// [`Action`] to complete. 41 /// 42 /// This function should return a 2-tuple of `(timeout, abandon)` 43 /// durations. After `timeout` has elapsed since circuit launch, 44 /// the circuit should no longer be used, but we should still keep 45 /// building it in order see how long it takes. After `abandon` 46 /// has elapsed since circuit launch, the circuit should be 47 /// abandoned completely. timeouts(&mut self, action: &Action) -> (Duration, Duration)48 fn timeouts(&mut self, action: &Action) -> (Duration, Duration); 49 50 /// Return true if we're currently trying to learn more timeouts 51 /// by launching testing circuits. learning_timeouts(&self) -> bool52 fn learning_timeouts(&self) -> bool; 53 54 /// Replace the network parameters used by this estimator (if any) 55 /// with ones derived from `params`. update_params(&mut self, params: &tor_netdir::params::NetParameters)56 fn update_params(&mut self, params: &tor_netdir::params::NetParameters); 57 58 /// Construct a new ParetoTimeoutState to represent the current state 59 /// of this estimator, if it is possible to store the state to disk. 60 /// 61 /// TODO: change the type used for the state. build_state(&mut self) -> Option<pareto::ParetoTimeoutState>62 fn build_state(&mut self) -> Option<pareto::ParetoTimeoutState>; 63 } 64 65 /// A possible action for which we can try to estimate a timeout. 66 #[non_exhaustive] 67 #[derive(Copy, Clone, Debug, Eq, PartialEq)] 68 pub(crate) enum Action { 69 /// Build a circuit of a given length. 70 BuildCircuit { 71 /// The length of the circuit to construct. 72 /// 73 /// (A 0-hop circuit takes no time.) 74 length: usize, 75 }, 76 /// Extend a given circuit from one length to another. 77 #[allow(dead_code)] 78 ExtendCircuit { 79 /// The current length of the circuit. 80 initial_length: usize, 81 /// The new length of the circuit. 82 /// 83 /// (Must be greater than `initial_length`.) 84 final_length: usize, 85 }, 86 /// Send a message to the last hop of a circuit and receive a response 87 #[allow(dead_code)] 88 RoundTrip { 89 /// The length of the circuit. 90 length: usize, 91 }, 92 } 93 94 impl Action { 95 /// Compute a scaling factor for a given `Action` 96 /// 97 /// These values are arbitrary numbers such that if the correct 98 /// timeout for an Action `a1` is `t`, then the correct timeout 99 /// for an action `a2` is `t * a2.timeout_scale() / 100 /// a1.timeout_scale()`. 101 /// 102 /// This function can return garbage if the circuit length is larger 103 /// than actually supported on the Tor network. timeout_scale(&self) -> usize104 fn timeout_scale(&self) -> usize { 105 /// An arbitrary value to use to prevent overflow. 106 const MAX_LEN: usize = 64; 107 108 /// Return the scale value for building a `len`-hop circuit. 109 fn build_scale(len: usize) -> usize { 110 len * (len + 1) / 2 111 } 112 // This is based on an approximation from Tor's 113 // `circuit_expire_building()` code. 114 // 115 // The general principle here is that when you're waiting for 116 // a round-trip through a circuit through three relays 117 // 'a--b--c', it takes three units of time. Thus, building a 118 // three hop circuit requires you to send a message through 119 // "a", then through "a--b", then through "a--b--c", for a 120 // total of 6. 121 // 122 // XXXX This should go into the specifications. 123 match *self { 124 Action::BuildCircuit { length } => { 125 // We never down-scale our estimates for building a circuit 126 // below a 3-hop length. 127 // 128 // TODO: This is undocumented. 129 let length = length.clamp(3, MAX_LEN); 130 build_scale(length) 131 } 132 Action::ExtendCircuit { 133 initial_length, 134 final_length, 135 } => { 136 let initial_length = initial_length.clamp(0, MAX_LEN); 137 let final_length = final_length.clamp(initial_length, MAX_LEN); 138 build_scale(final_length) - build_scale(initial_length) 139 } 140 Action::RoundTrip { length } => length.clamp(0, MAX_LEN), 141 } 142 } 143 } 144 145 #[cfg(test)] 146 mod test { 147 use super::Action; 148 149 #[test] action_scale_values()150 fn action_scale_values() { 151 assert_eq!(Action::BuildCircuit { length: 1 }.timeout_scale(), 6); 152 assert_eq!(Action::BuildCircuit { length: 2 }.timeout_scale(), 6); 153 assert_eq!(Action::BuildCircuit { length: 3 }.timeout_scale(), 6); 154 assert_eq!(Action::BuildCircuit { length: 4 }.timeout_scale(), 10); 155 assert_eq!(Action::BuildCircuit { length: 5 }.timeout_scale(), 15); 156 157 assert_eq!( 158 Action::ExtendCircuit { 159 initial_length: 3, 160 final_length: 4 161 } 162 .timeout_scale(), 163 4 164 ); 165 assert_eq!( 166 Action::ExtendCircuit { 167 initial_length: 99, 168 final_length: 4 169 } 170 .timeout_scale(), 171 0 172 ); 173 174 assert_eq!(Action::RoundTrip { length: 3 }.timeout_scale(), 3); 175 } 176 } 177