commit cdaff26f91ff6e3dceca6054157bbcf976713398 Author: George Kadianakis desnacked@riseup.net Date: Wed Mar 13 13:21:52 2019 +0200
circpad: Machines MUST have strictly increasing histogram edges.
Add a basic validation function for the histograms. It can be a building block for the future --- src/core/or/circuitpadding.c | 98 +++++++++++++++++++++++++++++++++++++----- src/core/or/circuitpadding.h | 6 ++- src/test/test_circuitpadding.c | 15 +++---- 3 files changed, 99 insertions(+), 20 deletions(-)
diff --git a/src/core/or/circuitpadding.c b/src/core/or/circuitpadding.c index 106bb4ffa..2ee233cc5 100644 --- a/src/core/or/circuitpadding.c +++ b/src/core/or/circuitpadding.c @@ -494,12 +494,13 @@ circpad_machine_sample_delay(circpad_machine_state_t *mi) * function below samples from [bin_start, bin_end) */ bin_end = circpad_histogram_bin_to_usec(mi, curr_bin+1);
- // Sample uniformly between histogram[i] to histogram[i+1]-1, - // but no need to sample if they are the same timeval (aka bin 0 or bin 1). - if (bin_end <= bin_start+1) + /* Bin edges are monotonically increasing so this is a bug. Handle it. */ + if (BUG(bin_start > bin_end)) { return bin_start; - else - return (circpad_delay_t)crypto_rand_uint64_range(bin_start, bin_end); + } + + /* Sample randomly from within the bin width */ + return (circpad_delay_t)crypto_rand_uint64_range(bin_start, bin_end); }
/** @@ -2050,16 +2051,92 @@ circpad_setup_machine_on_circ(circuit_t *on_circ, on_circ->padding_machine[machine->machine_index] = machine; }
-/* These padding machines are only used for tests pending #28634. */ #ifdef TOR_UNIT_TESTS +/** Validate a single state of a padding machine */ +static bool +padding_machine_state_is_valid(const circpad_state_t *state) +{ + int b; + uint32_t tokens_count = 0; + circpad_delay_t prev_bin_edge = 0; + + /* We only validate histograms */ + if (!state->histogram_len) { + return true; + } + + /* We need at least two bins in a histogram */ + if (state->histogram_len < 2) { + log_warn(LD_GENERAL, "You can't have a histogram with less than 2 bins"); + return false; + } + + /* For each machine state, if it's a histogram, make sure all the + * histogram edges are well defined (i.e. are strictly monotonic). */ + for (b = 0 ; b < state->histogram_len ; b++) { + /* Check that histogram edges are strictly increasing. Ignore the first + * edge since it can be zero. */ + if (prev_bin_edge >= state->histogram_edges[b] && b > 0) { + log_warn(LD_GENERAL, "Histogram edges are not increasing [%u/%u]", + prev_bin_edge, state->histogram_edges[b]); + return false; + } + + prev_bin_edge = state->histogram_edges[b]; + + /* Also count the number of tokens as we go through the histogram states */ + tokens_count += state->histogram[b]; + } + /* Verify that the total number of tokens is correct */ + if (tokens_count != state->histogram_total_tokens) { + log_warn(LD_GENERAL, "Histogram token count is wrong [%u/%u]", + tokens_count, state->histogram_total_tokens); + return false; + } + + return true; +} + +/** Basic validation of padding machine */ +static bool +padding_machine_is_valid(const circpad_machine_spec_t *machine) +{ + int i; + + /* Validate the histograms of the padding machine */ + for (i = 0 ; i < machine->num_states ; i++) { + if (!padding_machine_state_is_valid(&machine->states[i])) { + return false; + } + } + + return true; +} + +/* Validate and register <b>machine</b> into <b>machine_list</b>. If + * <b>machine_list</b> is NULL, then just validate. */ +STATIC void +register_padding_machine(circpad_machine_spec_t *machine, + smartlist_t *machine_list) +{ + if (!padding_machine_is_valid(machine)) { + log_warn(LD_GENERAL, "Machine #%u is invalid. Ignoring.", + machine->machine_num); + return; + } + + if (machine_list) { + smartlist_add(machine_list, machine); + } +} + +/* These padding machines are only used for tests pending #28634. */ static void circpad_circ_client_machine_init(void) { circpad_machine_spec_t *circ_client_machine = tor_malloc_zero(sizeof(circpad_machine_spec_t));
- // XXX: Better conditions for merge.. Or disable this machine in - // merge? circ_client_machine->conditions.min_hops = 2; circ_client_machine->conditions.state_mask = CIRCPAD_CIRC_BUILDING|CIRCPAD_CIRC_OPENED|CIRCPAD_CIRC_HAS_RELAY_EARLY; @@ -2091,7 +2168,6 @@ circpad_circ_client_machine_init(void) circ_client_machine->states[CIRCPAD_STATE_BURST].token_removal = CIRCPAD_TOKEN_REMOVAL_CLOSEST;
- // FIXME: Tune this histogram circ_client_machine->states[CIRCPAD_STATE_BURST].histogram_len = 2; circ_client_machine->states[CIRCPAD_STATE_BURST].histogram_edges[0]= 500; circ_client_machine->states[CIRCPAD_STATE_BURST].histogram_edges[1]= 1000000; @@ -2105,7 +2181,7 @@ circpad_circ_client_machine_init(void) circ_client_machine->states[CIRCPAD_STATE_BURST].histogram_total_tokens = 5;
circ_client_machine->machine_num = smartlist_len(origin_padding_machines); - smartlist_add(origin_padding_machines, circ_client_machine); + register_padding_machine(circ_client_machine, origin_padding_machines); }
static void @@ -2205,7 +2281,7 @@ circpad_circ_responder_machine_init(void) CIRCPAD_TOKEN_REMOVAL_CLOSEST_USEC;
circ_responder_machine->machine_num = smartlist_len(relay_padding_machines); - smartlist_add(relay_padding_machines, circ_responder_machine); + register_padding_machine(circ_responder_machine, relay_padding_machines); } #endif
diff --git a/src/core/or/circuitpadding.h b/src/core/or/circuitpadding.h index 2c763f46e..54039fa59 100644 --- a/src/core/or/circuitpadding.h +++ b/src/core/or/circuitpadding.h @@ -291,7 +291,7 @@ typedef struct circpad_state_t { /** The histogram itself: an array of uint16s of tokens, whose * widths are exponentially spaced, in microseconds. * - * This array must have histogram_len elements that are (non-strictly) + * This array must have histogram_len elements that are strictly * monotonically increasing. */ circpad_hist_token_t histogram[CIRCPAD_MAX_HISTOGRAM_LEN]; /* The histogram bin edges in usec. @@ -730,6 +730,10 @@ histogram_get_bin_upper_bound(const circpad_machine_state_t *mi, #ifdef TOR_UNIT_TESTS extern smartlist_t *origin_padding_machines; extern smartlist_t *relay_padding_machines; + +STATIC void +register_padding_machine(circpad_machine_spec_t *machine, + smartlist_t *machine_list); #endif
#endif diff --git a/src/test/test_circuitpadding.c b/src/test/test_circuitpadding.c index 3570b179b..a62b2b516 100644 --- a/src/test/test_circuitpadding.c +++ b/src/test/test_circuitpadding.c @@ -794,7 +794,7 @@ test_circuitpadding_closest_token_removal(void *arg) tt_int_op(client_side->padding_info[0]->current_state, OP_EQ, CIRCPAD_STATE_BURST); circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[0] = 100; - circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[1] = 100; + circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[1] = 101; circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[2] = 120; mi->padding_scheduled_at_usec = current_time - 102; mi->histogram[0] = 0; @@ -903,7 +903,7 @@ test_circuitpadding_closest_token_removal_usec(void *arg) tt_int_op(client_side->padding_info[0]->current_state, OP_EQ, CIRCPAD_STATE_BURST); circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[0] = 100; - circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[1] = 100; + circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[1] = 101; circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[2] = 120; mi->padding_scheduled_at_usec = current_time - 102; mi->histogram[0] = 0; @@ -1649,7 +1649,7 @@ helper_create_conditional_machine(void) ret->states[CIRCPAD_STATE_BURST].histogram_len = 3;
ret->states[CIRCPAD_STATE_BURST].histogram_edges[0] = 0; - ret->states[CIRCPAD_STATE_BURST].histogram_edges[1] = 0; + ret->states[CIRCPAD_STATE_BURST].histogram_edges[1] = 1; ret->states[CIRCPAD_STATE_BURST].histogram_edges[2] = 1000000;
ret->states[CIRCPAD_STATE_BURST].histogram[0] = 6; @@ -1686,8 +1686,7 @@ helper_create_conditional_machines(void) add->conditions.state_mask = CIRCPAD_CIRC_BUILDING| CIRCPAD_CIRC_NO_STREAMS|CIRCPAD_CIRC_HAS_RELAY_EARLY; add->conditions.purpose_mask = CIRCPAD_PURPOSE_ALL; - - smartlist_add(origin_padding_machines, add); + register_padding_machine(add, origin_padding_machines);
add = helper_create_conditional_machine(); add->machine_num = 3; @@ -1706,15 +1705,15 @@ helper_create_conditional_machines(void) add->conditions.state_mask = CIRCPAD_CIRC_OPENED| CIRCPAD_CIRC_STREAMS|CIRCPAD_CIRC_HAS_NO_RELAY_EARLY; add->conditions.purpose_mask = CIRCPAD_PURPOSE_ALL; - smartlist_add(origin_padding_machines, add); + register_padding_machine(add, origin_padding_machines);
add = helper_create_conditional_machine(); add->machine_num = 2; - smartlist_add(relay_padding_machines, add); + register_padding_machine(add, relay_padding_machines);
add = helper_create_conditional_machine(); add->machine_num = 3; - smartlist_add(relay_padding_machines, add); + register_padding_machine(add, relay_padding_machines); }
void