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