commit dd6def5daf5b0b579a61c9e83cfa905b333f99a1 Author: Nick Mathewson nickm@torproject.org Date: Mon Nov 14 15:46:09 2016 -0500
Initial code to parse/encode/sample prop271 guards
The encoding code is very straightforward. The decoding code is a bit tricky, but clean-ish. The sampling code is untested and probably needs more work. --- src/or/entrynodes.c | 310 ++++++++++++++++++++++++++++++++++++++++++++- src/or/entrynodes.h | 14 +- src/test/test_entrynodes.c | 243 +++++++++++++++++++++++++++++++++++ 3 files changed, 564 insertions(+), 3 deletions(-)
diff --git a/src/or/entrynodes.c b/src/or/entrynodes.c index c96ff09..9af7140 100644 --- a/src/or/entrynodes.c +++ b/src/or/entrynodes.c @@ -77,6 +77,11 @@ struct guard_selection_s { int dirty;
/** + * A list of the sampled entry guards, as entry_guard_t structures. + * Not in any particular order. */ + smartlist_t *sampled_entry_guards; + + /** * A list of our chosen entry guards, as entry_guard_t structures; this * preserves the pre-Prop271 behavior. */ @@ -87,6 +92,8 @@ struct guard_selection_s { * config's EntryNodes first? This was formerly a global. */ int should_add_entry_nodes; + + int filtered_up_to_date; };
static smartlist_t *guard_contexts = NULL; @@ -118,6 +125,7 @@ guard_selection_new(void)
gs = tor_malloc_zero(sizeof(*gs)); gs->chosen_entry_guards = smartlist_new(); + gs->sampled_entry_guards = smartlist_new();
return gs; } @@ -191,6 +199,293 @@ entry_guard_get_pathbias_state(entry_guard_t *guard) return &guard->pb; }
+/** Return an interval betweeen 'now' and 'max_backdate' seconds in the past, + * chosen uniformly at random. */ +STATIC time_t +randomize_time(time_t now, time_t max_backdate) +{ + tor_assert(max_backdate > 0); + + time_t earliest = now - max_backdate; + time_t latest = now; + if (earliest <= 0) + earliest = 1; + if (latest <= earliest) + latest = earliest + 1; + + return crypto_rand_time_range(earliest, latest); +} + +/** + * DOCDOC + */ +STATIC void +entry_guard_add_to_sample(guard_selection_t *gs, + node_t *node) +{ + (void) entry_guard_add_to_sample; // XXXX prop271 remove -- unused + const int GUARD_LIFETIME = 90 * 86400; // xxxx prop271 + tor_assert(gs); + tor_assert(node); + + // XXXX prop271 take ed25519 identity here too. + + /* make sure that the guard is not already sampled. */ + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, + entry_guard_t *, sampled) { + if (BUG(tor_memeq(node->identity, sampled->identity, DIGEST_LEN))) { + return; + } + } SMARTLIST_FOREACH_END(sampled); + + entry_guard_t *guard = tor_malloc_zero(sizeof(entry_guard_t)); + + /* persistent fields */ + memcpy(guard->identity, node->identity, DIGEST_LEN); + strlcpy(guard->nickname, node_get_nickname(node), sizeof(guard->nickname)); + guard->sampled_on_date = randomize_time(approx_time(), GUARD_LIFETIME/10); + tor_free(guard->sampled_by_version); + guard->sampled_by_version = tor_strdup(VERSION); + guard->confirmed_idx = -1; + + /* non-persistent fields */ + guard->is_reachable = GUARD_REACHABLE_MAYBE; + + smartlist_add(gs->sampled_entry_guards, guard); + gs->filtered_up_to_date = 0; + + entry_guards_changed_for_guard_selection(gs); +} + +/** + * Return a newly allocated string for encoding the persistent parts of + * <b>guard</b> to the state file. + */ +STATIC char * +entry_guard_encode_for_state(entry_guard_t *guard) +{ + /* + * The meta-format we use is K=V K=V K=V... where K can be any + * characters excepts space and =, and V can be any characters except + * space. The order of entries is not allowed to matter. + * Unrecognized K=V entries are persisted; recognized but erroneous + * entries are corrected. + */ + + smartlist_t *result = smartlist_new(); + char tbuf[ISO_TIME_LEN+1]; + + tor_assert(guard); + + smartlist_add_asprintf(result, "rsa_id=%s", + hex_str(guard->identity, DIGEST_LEN)); + if (strlen(guard->nickname)) { + smartlist_add_asprintf(result, "nickname=%s", guard->nickname); + } + + format_iso_time_nospace(tbuf, guard->sampled_on_date); + smartlist_add_asprintf(result, "sampled_on=%s", tbuf); + + if (guard->sampled_by_version) { + smartlist_add_asprintf(result, "sampled_by=%s", + guard->sampled_by_version); + } + + if (guard->unlisted_since_date > 0) { + format_iso_time_nospace(tbuf, guard->unlisted_since_date); + smartlist_add_asprintf(result, "unlisted_since=%s", tbuf); + } + + smartlist_add_asprintf(result, "listed=%d", + (int)guard->currently_listed); + + if (guard->confirmed_idx >= 0) { + format_iso_time_nospace(tbuf, guard->confirmed_on_date); + smartlist_add_asprintf(result, "confirmed_on=%s", tbuf); + + smartlist_add_asprintf(result, "confirmed_idx=%d", guard->confirmed_idx); + } + + if (guard->extra_state_fields) + smartlist_add_strdup(result, guard->extra_state_fields); + + char *joined = smartlist_join_strings(result, " ", 0, NULL); + SMARTLIST_FOREACH(result, char *, cp, tor_free(cp)); + smartlist_free(result); + + return joined; +} + +/** + * Given a string generated by entry_guard_encode_for_state(), parse it + * (if possible) and return an entry_guard_t object for it. Return NULL + * on complete failure. + */ +STATIC entry_guard_t * +entry_guard_parse_from_state(const char *s) +{ + /* Unrecognized entries get put in here. */ + smartlist_t *extra = smartlist_new(); + + /* These fields get parsed from the string. */ + char *rsa_id = NULL; + char *nickname = NULL; + char *sampled_on = NULL; + char *sampled_by = NULL; + char *unlisted_since = NULL; + char *listed = NULL; + char *confirmed_on = NULL; + char *confirmed_idx = NULL; + + /* Split up the entries. Put the ones we know about in strings and the + * rest in "extra". */ + { + smartlist_t *entries = smartlist_new(); + + strmap_t *vals = strmap_new(); // Maps keyword to location + strmap_set(vals, "rsa_id", &rsa_id); + strmap_set(vals, "nickname", &nickname); + strmap_set(vals, "sampled_on", &sampled_on); + strmap_set(vals, "sampled_by", &sampled_by); + strmap_set(vals, "unlisted_since", &unlisted_since); + strmap_set(vals, "listed", &listed); + strmap_set(vals, "confirmed_on", &confirmed_on); + strmap_set(vals, "confirmed_idx", &confirmed_idx); + + smartlist_split_string(entries, s, " ", + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + + SMARTLIST_FOREACH_BEGIN(entries, char *, entry) { + const char *eq = strchr(entry, '='); + if (!eq) { + smartlist_add(extra, entry); + continue; + } + char *key = tor_strndup(entry, eq-entry); + char **target = strmap_get(vals, key); + if (target == NULL || *target != NULL) { + /* unrecognized or already set */ + smartlist_add(extra, entry); + tor_free(key); + continue; + } + + *target = tor_strdup(eq+1); + tor_free(key); + tor_free(entry); + } SMARTLIST_FOREACH_END(entry); + + smartlist_free(entries); + strmap_free(vals, NULL); + } + + entry_guard_t *guard = tor_malloc_zero(sizeof(entry_guard_t)); + + if (rsa_id == NULL) { + log_warn(LD_CIRC, "Guard missing RSA ID field"); + goto err; + } + + /* Process the identity and nickname. */ + if (base16_decode(guard->identity, sizeof(guard->identity), + rsa_id, strlen(rsa_id)) != DIGEST_LEN) { + log_warn(LD_CIRC, "Unable to decode guard identity %s", escaped(rsa_id)); + goto err; + } + + if (nickname) { + strlcpy(guard->nickname, nickname, sizeof(guard->nickname)); + } else { + guard->nickname[0]='$'; + base16_encode(guard->nickname+1, sizeof(guard->nickname)-1, + guard->identity, DIGEST_LEN); + } + + /* Process the various time fields. */ + +#define HANDLE_TIME(field) do { \ + if (field) { \ + int r = parse_iso_time_nospace(field, &field ## _time); \ + if (r < 0) { \ + log_warn(LD_CIRC, "Unable to parse %s %s from guard", \ + #field, escaped(field)); \ + field##_time = -1; \ + } \ + } \ + } while (0) + + time_t sampled_on_time = 0; + time_t unlisted_since_time = 0; + time_t confirmed_on_time = 0; + + HANDLE_TIME(sampled_on); + HANDLE_TIME(unlisted_since); + HANDLE_TIME(confirmed_on); + + if (sampled_on_time <= 0) + sampled_on_time = approx_time(); + if (unlisted_since_time < 0) + unlisted_since_time = 0; + if (confirmed_on_time < 0) + confirmed_on_time = 0; + + #undef HANDLE_TIME + + guard->sampled_on_date = sampled_on_time; + guard->unlisted_since_date = unlisted_since_time; + guard->confirmed_on_date = confirmed_on_time; + + /* Take sampled_by_version verbatim. */ + guard->sampled_by_version = sampled_by; + sampled_by = NULL; /* prevent free */ + + /* Listed is a boolean */ + if (listed && strcmp(listed, "0")) + guard->currently_listed = 1; + + /* The index is a nonnegative integer. */ + guard->confirmed_idx = -1; + if (confirmed_idx) { + int ok=1; + long idx = tor_parse_long(confirmed_idx, 10, 0, INT_MAX, &ok, NULL); + if (! ok) { + log_warn(LD_CIRC, "Guard has invalid confirmed_idx %s", + escaped(confirmed_idx)); + } else { + guard->confirmed_idx = (int)idx; + } + } + + /* Anything we didn't recognize gets crammed together */ + if (smartlist_len(extra) > 0) { + guard->extra_state_fields = smartlist_join_strings(extra, " ", 0, NULL); + } + + /* initialize non-persistent fields */ + guard->is_reachable = GUARD_REACHABLE_MAYBE; + + goto done; + + err: + // only consider it an error if the guard state was totally unparseable. + entry_guard_free(guard); + guard = NULL; + + done: + tor_free(rsa_id); + tor_free(nickname); + tor_free(sampled_on); + tor_free(sampled_by); + tor_free(unlisted_since); + tor_free(listed); + tor_free(confirmed_on); + tor_free(confirmed_idx); + SMARTLIST_FOREACH(extra, char *, cp, tor_free(cp)); + smartlist_free(extra); + + return guard; +} + /** Check whether the entry guard <b>e</b> is usable, given the directory * authorities' opinion about the router (stored in <b>ri</b>) and the user's * configuration (in <b>options</b>). Set <b>e</b>->bad_since @@ -677,13 +972,14 @@ pick_entry_guards(guard_selection_t *gs, #define ENTRY_GUARD_REMOVE_AFTER (30*24*60*60)
/** Release all storage held by <b>e</b>. */ -static void +STATIC void entry_guard_free(entry_guard_t *e) { if (!e) return; tor_free(e->chosen_by_version); tor_free(e->sampled_by_version); + tor_free(e->extra_state_fields); tor_free(e); }
@@ -1452,6 +1748,9 @@ entry_guards_parse_state_for_guard_selection( const char *state_version = state->TorVersion; digestmap_t *added_by = digestmap_new();
+ if (0) entry_guard_parse_from_state(NULL); // XXXX prop271 remove -- unused + if (0) entry_guard_add_to_sample(NULL, NULL); // XXXX prop271 remove + tor_assert(gs != NULL);
*msg = NULL; @@ -1777,6 +2076,8 @@ entry_guards_update_state(or_state_t *state) config_line_t **next, *line; guard_selection_t *gs = get_guard_selection_info();
+ if (0) entry_guard_encode_for_state(NULL); // XXXX prop271 remove -- unused + tor_assert(gs != NULL); tor_assert(gs->chosen_entry_guards != NULL);
@@ -2837,6 +3138,13 @@ guard_selection_free(guard_selection_t *gs) gs->chosen_entry_guards = NULL; }
+ if (gs->sampled_entry_guards) { + SMARTLIST_FOREACH(gs->sampled_entry_guards, entry_guard_t *, e, + entry_guard_free(e)); + smartlist_free(gs->sampled_entry_guards); + gs->sampled_entry_guards = NULL; + } + tor_free(gs); }
diff --git a/src/or/entrynodes.h b/src/or/entrynodes.h index 4f39a09..5c0857b 100644 --- a/src/or/entrynodes.h +++ b/src/or/entrynodes.h @@ -63,7 +63,7 @@ typedef struct guard_pathbias_t { * use a node_t, since we want to remember these even when we * don't have any directory info. */ struct entry_guard_t { - char nickname[MAX_NICKNAME_LEN+1]; + char nickname[MAX_HEX_NICKNAME_LEN+1]; char identity[DIGEST_LEN]; ed25519_public_key_t ed_id;
@@ -71,7 +71,7 @@ struct entry_guard_t {
/* Persistent fields, present for all sampled guards. */ time_t sampled_on_date; - time_t unlisted_since_date; + time_t unlisted_since_date; // can be zero char *sampled_by_version; unsigned currently_listed : 1;
@@ -93,6 +93,9 @@ struct entry_guard_t { unsigned is_filtered_guard : 1; unsigned is_usable_filtered_guard : 1;
+ /** This string holds any fields that we are maintaining because + * we saw them in the state, even if we don't understand them. */ + char *extra_state_fields; /** * @name legacy guard selection algorithm fields * @@ -152,6 +155,13 @@ const char *entry_guard_describe(const entry_guard_t *guard); guard_pathbias_t *entry_guard_get_pathbias_state(entry_guard_t *guard);
#ifdef ENTRYNODES_PRIVATE +STATIC time_t randomize_time(time_t now, time_t max_backdate); +STATIC void entry_guard_add_to_sample(guard_selection_t *gs, + node_t *node); +STATIC char *entry_guard_encode_for_state(entry_guard_t *guard); +STATIC entry_guard_t *entry_guard_parse_from_state(const char *s); +STATIC void entry_guard_free(entry_guard_t *e); + STATIC const node_t *add_an_entry_guard(guard_selection_t *gs, const node_t *chosen, int reset_status, int prepend, diff --git a/src/test/test_entrynodes.c b/src/test/test_entrynodes.c index aa1b455..45b730c 100644 --- a/src/test/test_entrynodes.c +++ b/src/test/test_entrynodes.c @@ -859,6 +859,236 @@ test_entry_guard_describe(void *arg) ; }
+static void +test_entry_guard_randomize_time(void *arg) +{ + const time_t now = 1479153573; + const int delay = 86400; + const int N = 1000; + (void)arg; + + time_t t; + int i; + for (i = 0; i < N; ++i) { + t = randomize_time(now, delay); + tt_int_op(t, OP_LE, now); + tt_int_op(t, OP_GE, now-delay); + } + + /* now try the corner cases */ + for (i = 0; i < N; ++i) { + t = randomize_time(100, delay); + tt_int_op(t, OP_GE, 1); + tt_int_op(t, OP_LE, 100); + + t = randomize_time(0, delay); + tt_int_op(t, OP_EQ, 1); + } + + done: + ; +} + +static void +test_entry_guard_encode_for_state_minimal(void *arg) +{ + (void) arg; + entry_guard_t *eg = tor_malloc_zero(sizeof(entry_guard_t)); + + memcpy(eg->identity, "plurpyflurpyslurpydo", DIGEST_LEN); + eg->sampled_on_date = 1479081600; + eg->confirmed_idx = -1; + + char *s = NULL; + s = entry_guard_encode_for_state(eg); + + tt_str_op(s, OP_EQ, + "rsa_id=706C75727079666C75727079736C75727079646F " + "sampled_on=2016-11-14T00:00:00 " + "listed=0"); + + done: + entry_guard_free(eg); + tor_free(s); +} + +static void +test_entry_guard_encode_for_state_maximal(void *arg) +{ + (void) arg; + entry_guard_t *eg = tor_malloc_zero(sizeof(entry_guard_t)); + + strlcpy(eg->nickname, "Fred", sizeof(eg->nickname)); + memcpy(eg->identity, "plurpyflurpyslurpydo", DIGEST_LEN); + eg->sampled_on_date = 1479081600; + eg->sampled_by_version = tor_strdup("1.2.3"); + eg->unlisted_since_date = 1479081645; + eg->currently_listed = 1; + eg->confirmed_on_date = 1479081690; + eg->confirmed_idx = 333; + eg->extra_state_fields = tor_strdup("and the green grass grew all around"); + + char *s = NULL; + s = entry_guard_encode_for_state(eg); + + tt_str_op(s, OP_EQ, + "rsa_id=706C75727079666C75727079736C75727079646F " + "nickname=Fred " + "sampled_on=2016-11-14T00:00:00 " + "sampled_by=1.2.3 " + "unlisted_since=2016-11-14T00:00:45 " + "listed=1 " + "confirmed_on=2016-11-14T00:01:30 " + "confirmed_idx=333 " + "and the green grass grew all around"); + + done: + entry_guard_free(eg); + tor_free(s); +} + +static void +test_entry_guard_parse_from_state_minimal(void *arg) +{ + (void)arg; + char *mem_op_hex_tmp = NULL; + entry_guard_t *eg = NULL; + time_t t = approx_time(); + + eg = entry_guard_parse_from_state( + "rsa_id=596f75206d6179206e656564206120686f626279"); + tt_assert(eg); + + test_mem_op_hex(eg->identity, OP_EQ, + "596f75206d6179206e656564206120686f626279"); + tt_str_op(eg->nickname, OP_EQ, "$596F75206D6179206E656564206120686F626279"); + tt_i64_op(eg->sampled_on_date, OP_GE, t); + tt_i64_op(eg->sampled_on_date, OP_LE, t+86400); + tt_i64_op(eg->unlisted_since_date, OP_EQ, 0); + tt_ptr_op(eg->sampled_by_version, OP_EQ, NULL); + tt_int_op(eg->currently_listed, OP_EQ, 0); + tt_i64_op(eg->confirmed_on_date, OP_EQ, 0); + tt_int_op(eg->confirmed_idx, OP_EQ, -1); + + tt_int_op(eg->last_tried_to_connect, OP_EQ, 0); + tt_int_op(eg->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE); + + done: + entry_guard_free(eg); + tor_free(mem_op_hex_tmp); +} + +static void +test_entry_guard_parse_from_state_maximal(void *arg) +{ + (void)arg; + char *mem_op_hex_tmp = NULL; + entry_guard_t *eg = NULL; + + eg = entry_guard_parse_from_state( + "rsa_id=706C75727079666C75727079736C75727079646F " + "nickname=Fred " + "sampled_on=2016-11-14T00:00:00 " + "sampled_by=1.2.3 " + "unlisted_since=2016-11-14T00:00:45 " + "listed=1 " + "confirmed_on=2016-11-14T00:01:30 " + "confirmed_idx=333 " + "and the green grass grew all around " + "rsa_id=all,around"); + tt_assert(eg); + + test_mem_op_hex(eg->identity, OP_EQ, + "706C75727079666C75727079736C75727079646F"); + tt_str_op(eg->nickname, OP_EQ, "Fred"); + tt_i64_op(eg->sampled_on_date, OP_EQ, 1479081600); + tt_i64_op(eg->unlisted_since_date, OP_EQ, 1479081645); + tt_str_op(eg->sampled_by_version, OP_EQ, "1.2.3"); + tt_int_op(eg->currently_listed, OP_EQ, 1); + tt_i64_op(eg->confirmed_on_date, OP_EQ, 1479081690); + tt_int_op(eg->confirmed_idx, OP_EQ, 333); + tt_str_op(eg->extra_state_fields, OP_EQ, + "and the green grass grew all around rsa_id=all,around"); + + tt_int_op(eg->last_tried_to_connect, OP_EQ, 0); + tt_int_op(eg->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE); + + done: + entry_guard_free(eg); + tor_free(mem_op_hex_tmp); +} + +static void +test_entry_guard_parse_from_state_failure(void *arg) +{ + (void)arg; + entry_guard_t *eg = NULL; + + /* no RSA ID. */ + eg = entry_guard_parse_from_state("nickname=Fred"); + tt_assert(! eg); + + /* Bad RSA ID: bad character. */ + eg = entry_guard_parse_from_state( + "rsa_id=596f75206d6179206e656564206120686f62627q"); + tt_assert(! eg); + + /* Bad RSA ID: too long.*/ + eg = entry_guard_parse_from_state( + "rsa_id=596f75206d6179206e656564206120686f6262703"); + tt_assert(! eg); + + /* Bad RSA ID: too short.*/ + eg = entry_guard_parse_from_state( + "rsa_id=596f75206d6179206e65656420612"); + tt_assert(! eg); + + done: + entry_guard_free(eg); +} + +static void +test_entry_guard_parse_from_state_partial_failure(void *arg) +{ + (void)arg; + char *mem_op_hex_tmp = NULL; + entry_guard_t *eg = NULL; + time_t t = approx_time(); + + eg = entry_guard_parse_from_state( + "rsa_id=706C75727079666C75727079736C75727079646F " + "nickname=FredIsANodeWithAStrangeNicknameThatIsTooLong " + "sampled_on=2016-11-14T00:00:99 " + "sampled_by=1.2.3 stuff in the middle " + "unlisted_since=2016-xx-14T00:00:45 " + "listed=0 " + "confirmed_on=2016-11-14T00:01:30zz " + "confirmed_idx=idx " + "and the green grass grew all around " + "rsa_id=all,around"); + tt_assert(eg); + + test_mem_op_hex(eg->identity, OP_EQ, + "706C75727079666C75727079736C75727079646F"); + tt_str_op(eg->nickname, OP_EQ, "FredIsANodeWithAStrangeNicknameThatIsTooL"); + tt_i64_op(eg->sampled_on_date, OP_EQ, t); + tt_i64_op(eg->unlisted_since_date, OP_EQ, 0); + tt_str_op(eg->sampled_by_version, OP_EQ, "1.2.3"); + tt_int_op(eg->currently_listed, OP_EQ, 0); + tt_i64_op(eg->confirmed_on_date, OP_EQ, 0); + tt_int_op(eg->confirmed_idx, OP_EQ, -1); + tt_str_op(eg->extra_state_fields, OP_EQ, + "stuff in the middle and the green grass grew all around " + "rsa_id=all,around"); + + tt_int_op(eg->last_tried_to_connect, OP_EQ, 0); + tt_int_op(eg->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE); + + done: + entry_guard_free(eg); + tor_free(mem_op_hex_tmp); +} + static const struct testcase_setup_t fake_network = { fake_network_setup, fake_network_cleanup }; @@ -893,6 +1123,19 @@ struct testcase_t entrynodes_tests[] = { test_node_preferred_orport, 0, NULL, NULL }, { "entry_guard_describe", test_entry_guard_describe, 0, NULL, NULL }, + { "randomize_time", test_entry_guard_randomize_time, 0, NULL, NULL }, + { "encode_for_state_minimal", + test_entry_guard_encode_for_state_minimal, 0, NULL, NULL }, + { "encode_for_state_maximal", + test_entry_guard_encode_for_state_maximal, 0, NULL, NULL }, + { "parse_from_state_minimal", + test_entry_guard_parse_from_state_minimal, 0, NULL, NULL }, + { "parse_from_state_maximal", + test_entry_guard_parse_from_state_maximal, 0, NULL, NULL }, + { "parse_from_state_failure", + test_entry_guard_parse_from_state_failure, 0, NULL, NULL }, + { "parse_from_state_partial_failure", + test_entry_guard_parse_from_state_partial_failure, 0, NULL, NULL }, END_OF_TESTCASES };