commit 43672f9fcaf78cbb49abe4b258b95648a609b4cf Author: vnepveu victor.nepveu@imt-atlantique.net Date: Wed Sep 23 11:30:15 2020 -0400
Implement IPv6 sybil protection.
[This is a squashed patch for ticket 7193, based on taking a "git diff" for the original branch, then applying it with "git apply -3". I earlier attempted to squash the branch with "git rebase", but there were too many conflicts. --nickm] --- changes/ticket7193 | 2 + scripts/maint/practracker/exceptions.txt | 2 +- src/feature/dirauth/dirvote.c | 189 +++++++--- src/feature/dirauth/dirvote.h | 18 + src/feature/nodelist/dirlist.c | 4 +- src/feature/nodelist/dirlist.h | 5 +- src/test/include.am | 1 + src/test/test.c | 1 + src/test/test.h | 1 + src/test/test_dirvote.c | 626 +++++++++++++++++++++++++++++++ 10 files changed, 795 insertions(+), 54 deletions(-)
diff --git a/changes/ticket7193 b/changes/ticket7193 new file mode 100644 index 0000000000..18c4915dd5 --- /dev/null +++ b/changes/ticket7193 @@ -0,0 +1,2 @@ + o Minor features (dirvote): + - Add IPv6 support in protection against Sybil attacks. Closes ticket7193 diff --git a/scripts/maint/practracker/exceptions.txt b/scripts/maint/practracker/exceptions.txt index 6eb315d0eb..eeef0bd668 100644 --- a/scripts/maint/practracker/exceptions.txt +++ b/scripts/maint/practracker/exceptions.txt @@ -201,7 +201,7 @@ problem function-size /src/feature/control/control_getinfo.c:getinfo_helper_misc problem function-size /src/feature/control/control_getinfo.c:getinfo_helper_dir() 297 problem function-size /src/feature/control/control_getinfo.c:getinfo_helper_events() 237 problem function-size /src/feature/dirauth/bwauth.c:dirserv_read_measured_bandwidths() 121 -problem file-size /src/feature/dirauth/dirvote.c 4734 +problem file-size /src/feature/dirauth/dirvote.c 4900 problem include-count /src/feature/dirauth/dirvote.c 55 problem function-size /src/feature/dirauth/dirvote.c:format_networkstatus_vote() 230 problem function-size /src/feature/dirauth/dirvote.c:networkstatus_compute_bw_weights_v10() 233 diff --git a/src/feature/dirauth/dirvote.c b/src/feature/dirauth/dirvote.c index 8676df76ab..c1ffa25672 100644 --- a/src/feature/dirauth/dirvote.c +++ b/src/feature/dirauth/dirvote.c @@ -4,6 +4,7 @@ /* See LICENSE for licensing information */
#define DIRVOTE_PRIVATE + #include "core/or/or.h" #include "app/config/config.h" #include "app/config/resolve_addr.h" @@ -4177,8 +4178,8 @@ dirvote_dirreq_get_status_vote(const char *url, smartlist_t *items,
/** Get the best estimate of a router's bandwidth for dirauth purposes, * preferring measured to advertised values if available. */ -static uint32_t -dirserv_get_bandwidth_for_router_kb(const routerinfo_t *ri) +MOCK_IMPL(uint32_t,dirserv_get_bandwidth_for_router_kb, + (const routerinfo_t *ri)) { uint32_t bw_kb = 0; /* @@ -4207,33 +4208,65 @@ dirserv_get_bandwidth_for_router_kb(const routerinfo_t *ri) return bw_kb; }
-/** Helper for sorting: compares two routerinfos first by address, and then by - * descending order of "usefulness". (An authority is more useful than a - * non-authority; a running router is more useful than a non-running router; - * and a router with more bandwidth is more useful than one with less.) +/** Helper for sorting: compares two ipv4 routerinfos first by ipv4 address, + * and then by descending order of "usefulness" + * (see compare_routerinfo_usefulness) **/ -static int -compare_routerinfo_by_ip_and_bw_(const void **a, const void **b) +STATIC int +compare_routerinfo_by_ipv4(const void **a, const void **b) +{ + const routerinfo_t *first = *(routerinfo_t **)a; + const routerinfo_t *second = *(routerinfo_t **)b; + // If addresses are equal, use other comparison criterions + int addr_comparison = tor_addr_compare(&(first->ipv4_addr), + &(second->ipv4_addr), CMP_EXACT); + if (addr_comparison == 0) { + return compare_routerinfo_usefulness(first, second); + } else { + // Otherwise, compare the addresses + if (addr_comparison < 0 ) + return -1; + else + return 1; + } +} + +/** Helper for sorting: compares two ipv6 routerinfos first by ipv6 address, + * and then by descending order of "usefulness" + * (see compare_routerinfo_usefulness) + **/ +STATIC int +compare_routerinfo_by_ipv6(const void **a, const void **b) +{ + const routerinfo_t *first = *(routerinfo_t **)a; + const routerinfo_t *second = *(routerinfo_t **)b; + const tor_addr_t *first_ipv6 = &(first->ipv6_addr); + const tor_addr_t *second_ipv6 = &(second->ipv6_addr); + int comparison = tor_addr_compare(first_ipv6, second_ipv6, CMP_EXACT); + // If addresses are equal, use other comparison criterions + if (comparison == 0) + return compare_routerinfo_usefulness(first, second); + else + return comparison; +} + +/** +* Compare routerinfos by descending order of "usefulness" : +* An authority is more useful than a non-authority; a running router is +* more useful than a non-running router; and a router with more bandwidth +* is more useful than one with less. +**/ +STATIC int +compare_routerinfo_usefulness(const routerinfo_t *first, + const routerinfo_t *second) { - routerinfo_t *first = *(routerinfo_t **)a, *second = *(routerinfo_t **)b; int first_is_auth, second_is_auth; - uint32_t bw_kb_first, bw_kb_second; const node_t *node_first, *node_second; int first_is_running, second_is_running; - uint32_t first_ipv4h = tor_addr_to_ipv4h(&first->ipv4_addr); - uint32_t second_ipv4h = tor_addr_to_ipv4h(&second->ipv4_addr); - - /* we return -1 if first should appear before second... that is, - * if first is a better router. */ - if (first_ipv4h < second_ipv4h) - return -1; - else if (first_ipv4h > second_ipv4h) - return 1; - + uint32_t bw_kb_first, bw_kb_second; /* Potentially, this next bit could cause k n lg n memeq calls. But in * reality, we will almost never get here, since addresses will usually be * different. */ - first_is_auth = router_digest_is_trusted_dir(first->cache_info.identity_digest); second_is_auth = @@ -4248,7 +4281,6 @@ compare_routerinfo_by_ip_and_bw_(const void **a, const void **b) node_second = node_get_by_id(second->cache_info.identity_digest); first_is_running = node_first && node_first->is_running; second_is_running = node_second && node_second->is_running; - if (first_is_running && !second_is_running) return -1; else if (!first_is_running && second_is_running) @@ -4269,40 +4301,102 @@ compare_routerinfo_by_ip_and_bw_(const void **a, const void **b) DIGEST_LEN); }
-/** Given a list of routerinfo_t in <b>routers</b>, return a new digestmap_t - * whose keys are the identity digests of those routers that we're going to - * exclude for Sybil-like appearance. */ -static digestmap_t * -get_possible_sybil_list(const smartlist_t *routers) +/** Given a list of routerinfo_t in <b>routers</b> that all use the same + * IP version, specified in <b>family</b>, return a new digestmap_t whose keys + * are the identity digests of those routers that we're going to exclude for + * Sybil-like appearance. + */ +STATIC digestmap_t * +get_sybil_list_by_ip_version(const smartlist_t *routers, sa_family_t family) { const dirauth_options_t *options = dirauth_get_options(); - digestmap_t *omit_as_sybil; + digestmap_t *omit_as_sybil = digestmap_new(); smartlist_t *routers_by_ip = smartlist_new(); - tor_addr_t last_addr = TOR_ADDR_NULL; - int addr_count; + int ipv4_addr_count = 0; + int ipv6_addr_count = 0; + tor_addr_t last_ipv6_addr, last_ipv4_addr; + int addr_comparison = 0; /* Allow at most this number of Tor servers on a single IP address, ... */ int max_with_same_addr = options->AuthDirMaxServersPerAddr; if (max_with_same_addr <= 0) max_with_same_addr = INT_MAX;
smartlist_add_all(routers_by_ip, routers); - smartlist_sort(routers_by_ip, compare_routerinfo_by_ip_and_bw_); - omit_as_sybil = digestmap_new(); + if (family == AF_INET6) + smartlist_sort(routers_by_ip, compare_routerinfo_by_ipv6); + else + smartlist_sort(routers_by_ip, compare_routerinfo_by_ipv4);
- addr_count = 0; SMARTLIST_FOREACH_BEGIN(routers_by_ip, routerinfo_t *, ri) { - if (!tor_addr_eq(&last_addr, &ri->ipv4_addr)) { - tor_addr_copy(&last_addr, &ri->ipv4_addr); - addr_count = 1; - } else if (++addr_count > max_with_same_addr) { - digestmap_set(omit_as_sybil, ri->cache_info.identity_digest, ri); + if (family == AF_INET6) { + addr_comparison = tor_addr_compare(&last_ipv6_addr, &(ri->ipv6_addr), + CMP_EXACT); + if (addr_comparison != 0) { + tor_addr_copy(&last_ipv6_addr, &(ri->ipv6_addr)); + ipv6_addr_count = 1; + } else if (++ipv6_addr_count > max_with_same_addr) { + digestmap_set(omit_as_sybil, ri->cache_info.identity_digest, ri); + } + } else { + addr_comparison = tor_addr_compare(&last_ipv4_addr, &(ri->ipv4_addr), + CMP_EXACT); + if (addr_comparison != 0) { + tor_addr_copy(&last_ipv4_addr, &(ri->ipv4_addr)); + ipv4_addr_count = 1; + } else if (++ipv4_addr_count > max_with_same_addr) { + digestmap_set(omit_as_sybil, ri->cache_info.identity_digest, ri); + } } } SMARTLIST_FOREACH_END(ri); - smartlist_free(routers_by_ip); return omit_as_sybil; }
+/** Given a list of routerinfo_t in <b>routers</b>, return a new digestmap_t + * whose keys are the identity digests of those routers that we're going to + * exclude for Sybil-like appearance. */ +STATIC digestmap_t * +get_all_possible_sybil(const smartlist_t *routers) +{ + smartlist_t *routers_ipv6, *routers_ipv4; + routers_ipv6 = smartlist_new(); + routers_ipv4 = smartlist_new(); + digestmap_t *omit_as_sybil_ipv4 = digestmap_new(); + digestmap_t *omit_as_sybil_ipv6 = digestmap_new(); + digestmap_t *omit_as_sybil = digestmap_new(); + // Sort the routers in two lists depending on their IP version + SMARTLIST_FOREACH(routers, routerinfo_t *, ri, { + // If the router is IPv6 + if (tor_addr_family(&(ri->ipv6_addr)) == AF_INET6){ + smartlist_add(routers_ipv6, ri); + } + // If the router is IPv4 + if (tor_addr_family(&(ri->ipv4_addr)) == AF_INET){ + smartlist_add(routers_ipv4, ri); + } + }); + routers_sort_by_identity(routers_ipv4); + routers_sort_by_identity(routers_ipv6); + omit_as_sybil_ipv4 = get_sybil_list_by_ip_version(routers_ipv4, AF_INET); + omit_as_sybil_ipv6 = get_sybil_list_by_ip_version(routers_ipv6, AF_INET6); + + // Add all possible sybils to the common digestmap + DIGESTMAP_FOREACH (omit_as_sybil_ipv4, sybil_id, routerinfo_t *, ri) { + digestmap_set(omit_as_sybil, ri->cache_info.identity_digest, ri); + } + DIGESTMAP_FOREACH_END + DIGESTMAP_FOREACH (omit_as_sybil_ipv6, sybil_id, routerinfo_t *, ri) { + digestmap_set(omit_as_sybil, ri->cache_info.identity_digest, ri); + } + DIGESTMAP_FOREACH_END + // Clean the temp variables + smartlist_free(routers_ipv4); + smartlist_free(routers_ipv6); + digestmap_free(omit_as_sybil_ipv4, NULL); + digestmap_free(omit_as_sybil_ipv6, NULL); + // Return the digestmap : it now contains all the possible sybils + return omit_as_sybil; +} /** Given a platform string as in a routerinfo_t (possibly null), return a * newly allocated version string for a networkstatus document, or NULL if the * platform doesn't give a Tor version. */ @@ -4477,7 +4571,7 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key, time_t cutoff = now - ROUTER_MAX_AGE_TO_PUBLISH; networkstatus_voter_info_t *voter = NULL; vote_timing_t timing; - digestmap_t *omit_as_sybil = NULL; + digestmap_t *omit_as_sybil = digestmap_new(); const int vote_on_reachability = running_long_enough_to_decide_unreachable(); smartlist_t *microdescriptors = NULL; smartlist_t *bw_file_headers = NULL; @@ -4547,19 +4641,17 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key, routers_make_ed_keys_unique(routers); /* After this point, don't use rl->routers; use 'routers' instead. */ routers_sort_by_identity(routers); - omit_as_sybil = get_possible_sybil_list(routers); - - DIGESTMAP_FOREACH(omit_as_sybil, sybil_id, void *, ignore) { - (void) ignore; + /* Get a digestmap of possible sybil routers, IPv4 or IPv6 */ + omit_as_sybil = get_all_possible_sybil(routers); + DIGESTMAP_FOREACH (omit_as_sybil, sybil_id, void *, ignore) { + (void)ignore; rep_hist_make_router_pessimal(sybil_id, now); - } DIGESTMAP_FOREACH_END; - + } + DIGESTMAP_FOREACH_END /* Count how many have measured bandwidths so we know how to assign flags; * this must come before dirserv_compute_performance_thresholds() */ dirserv_count_measured_bws(routers); - dirserv_compute_performance_thresholds(omit_as_sybil); - routerstatuses = smartlist_new(); microdescriptors = smartlist_new();
@@ -4587,7 +4679,6 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key, ri->cache_info.signing_key_cert->signing_key.pubkey, ED25519_PUBKEY_LEN); } - if (digestmap_get(omit_as_sybil, ri->cache_info.identity_digest)) clear_status_flags_on_sybil(rs);
diff --git a/src/feature/dirauth/dirvote.h b/src/feature/dirauth/dirvote.h index 9cc87489b4..a4f1b8bfe9 100644 --- a/src/feature/dirauth/dirvote.h +++ b/src/feature/dirauth/dirvote.h @@ -183,6 +183,8 @@ dirvote_add_signatures(const char *detached_signatures_body, /* Item access */ MOCK_DECL(const char*, dirvote_get_pending_consensus, (consensus_flavor_t flav)); +MOCK_DECL(uint32_t,dirserv_get_bandwidth_for_router_kb, + (const routerinfo_t *ri)); MOCK_DECL(const char*, dirvote_get_pending_detached_signatures, (void)); const cached_dir_t *dirvote_get_vote(const char *fp, int flags);
@@ -234,6 +236,22 @@ int networkstatus_add_detached_signatures(networkstatus_t *target, const char *source, int severity, const char **msg_out); +STATIC int +compare_routerinfo_usefulness(const routerinfo_t *first, + const routerinfo_t *second); +STATIC +int compare_routerinfo_by_ipv4(const void **a, const void **b); + +STATIC +int compare_routerinfo_by_ipv6(const void **a, const void **b); + +STATIC +digestmap_t * get_sybil_list_by_ip_version( + const smartlist_t *routers, sa_family_t family); + +STATIC +digestmap_t * get_all_possible_sybil(const smartlist_t *routers); + STATIC char *networkstatus_get_detached_signatures(smartlist_t *consensuses); STATIC microdesc_t *dirvote_create_microdescriptor(const routerinfo_t *ri, diff --git a/src/feature/nodelist/dirlist.c b/src/feature/nodelist/dirlist.c index cd2921e653..f6e4662a0f 100644 --- a/src/feature/nodelist/dirlist.c +++ b/src/feature/nodelist/dirlist.c @@ -236,8 +236,8 @@ mark_all_dirservers_up(smartlist_t *server_list) /** Return true iff <b>digest</b> is the digest of the identity key of a * trusted directory matching at least one bit of <b>type</b>. If <b>type</b> * is zero (NO_DIRINFO), or ALL_DIRINFO, any authority is okay. */ -int -router_digest_is_trusted_dir_type(const char *digest, dirinfo_type_t type) +MOCK_IMPL(int, router_digest_is_trusted_dir_type, + (const char *digest, dirinfo_type_t type)) { if (!trusted_dir_servers) return 0; diff --git a/src/feature/nodelist/dirlist.h b/src/feature/nodelist/dirlist.h index c9310ff357..ae3debf4e5 100644 --- a/src/feature/nodelist/dirlist.h +++ b/src/feature/nodelist/dirlist.h @@ -25,13 +25,14 @@ int router_digest_is_fallback_dir(const char *digest); MOCK_DECL(dir_server_t *, trusteddirserver_get_by_v3_auth_digest, (const char *d));
+MOCK_DECL(int, router_digest_is_trusted_dir_type, + (const char *digest, dirinfo_type_t type)); + bool router_addr_is_trusted_dir_type(const tor_addr_t *addr, dirinfo_type_t type); #define router_addr_is_trusted_dir(d) \ router_addr_is_trusted_dir_type((d), NO_DIRINFO)
-int router_digest_is_trusted_dir_type(const char *digest, - dirinfo_type_t type); #define router_digest_is_trusted_dir(d) \ router_digest_is_trusted_dir_type((d), NO_DIRINFO)
diff --git a/src/test/include.am b/src/test/include.am index 816eba894e..215e423834 100644 --- a/src/test/include.am +++ b/src/test/include.am @@ -171,6 +171,7 @@ src_test_test_SOURCES += \ src/test/test_crypto_rng.c \ src/test/test_data.c \ src/test/test_dir.c \ + src/test/test_dirvote.c \ src/test/test_dir_common.c \ src/test/test_dir_handle_get.c \ src/test/test_dispatch.c \ diff --git a/src/test/test.c b/src/test/test.c index 2961669c46..38c8206eea 100644 --- a/src/test/test.c +++ b/src/test/test.c @@ -709,6 +709,7 @@ struct testgroup_t testgroups[] = { { "dir/", dir_tests }, { "dir/auth/process_descs/", process_descs_tests }, { "dir/md/", microdesc_tests }, + { "dirauth/dirvote/", dirvote_tests}, { "dir/voting/flags/", voting_flags_tests }, { "dir/voting/schedule/", voting_schedule_tests }, { "dir_handle_get/", dir_handle_get_tests }, diff --git a/src/test/test.h b/src/test/test.h index 18987719d0..71066db48e 100644 --- a/src/test/test.h +++ b/src/test/test.h @@ -122,6 +122,7 @@ extern struct testcase_t crypto_rng_tests[]; extern struct testcase_t crypto_tests[]; extern struct testcase_t dir_handle_get_tests[]; extern struct testcase_t dir_tests[]; +extern struct testcase_t dirvote_tests[]; extern struct testcase_t dispatch_tests[]; extern struct testcase_t dns_tests[]; extern struct testcase_t dos_tests[]; diff --git a/src/test/test_dirvote.c b/src/test/test_dirvote.c new file mode 100644 index 0000000000..def494959d --- /dev/null +++ b/src/test/test_dirvote.c @@ -0,0 +1,626 @@ +/* Copyright (c) 2020, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file test_dirvote.c + * \brief Unit tests for dirvote related functions + */ +#define DIRVOTE_PRIVATE + +#include "core/or/or.h" +#include "feature/dirauth/dirvote.h" +#include "feature/nodelist/dirlist.h" +#include "feature/nodelist/node_st.h" +#include "feature/nodelist/nodelist.h" +#include "feature/nodelist/routerinfo_st.h" +#include "feature/nodelist/signed_descriptor_st.h" + +#include "test/test.h" + +/** + * This struct holds the various informations that are needed for router + * comparison. Each router in the test function has one, and they are all + * put in a global digestmap, router_properties + */ +typedef struct router_values { + int is_running; + int is_auth; + int bw_kb; + char digest[DIGEST_LEN]; +} router_values; +/** + * This typedef makes declaring digests easier and less verbose + */ +typedef char tor_digest[DIGEST_LEN]; + +// Use of global variable is justified because the functions that have to be +// mocked take as arguments objects we have no control over +static digestmap_t *router_properties = NULL; +// Use of global variable is justified by its use in nodelist.c +// and is necessary to avoid memory leaks when mocking the +// function node_get_by_id +static node_t *running_node; +static node_t *non_running_node; + +/* Allocate memory to the global variables that represent a running + * and non-running node + */ +#define ALLOCATE_MOCK_NODES() \ + running_node = tor_malloc(sizeof(node_t)); \ + running_node->is_running = 1; \ + non_running_node = tor_malloc(sizeof(node_t)); \ + non_running_node->is_running = 0; + +/* Free the memory allocated to the mock nodes */ +#define FREE_MOCK_NODES() \ + tor_free(running_node); \ + tor_free(non_running_node); + +int mock_router_digest_is_trusted(const char *digest, dirinfo_type_t type); +int +mock_router_digest_is_trusted(const char *digest, dirinfo_type_t type) +{ + (void)type; + router_values *mock_status; + mock_status = digestmap_get(router_properties, digest); + if (!mock_status) { + return -1; + } + return mock_status->is_auth; +} + +const node_t *mock_node_get_by_id(const char *identity_digest); +const node_t * +mock_node_get_by_id(const char *identity_digest) +{ + router_values *status; + status = digestmap_get(router_properties, identity_digest); + if (!status) { + return NULL; + } + if (status->is_running) + return running_node; + else + return non_running_node; +} + +uint32_t mock_dirserv_get_bw(const routerinfo_t *ri); +uint32_t +mock_dirserv_get_bw(const routerinfo_t *ri) +{ + const char *digest = ri->cache_info.identity_digest; + router_values *status; + status = digestmap_get(router_properties, digest); + if (!status) { + return -1; + } + return status->bw_kb; +} + +router_values *router_values_new(int running, int auth, int bw, char *digest); +/** Generate a pointer to a router_values struct with the arguments as + * field values, and return it + * The returned pointer has to be freed by the caller. + */ +router_values * +router_values_new(int running, int auth, int bw, char *digest) +{ + router_values *status = tor_malloc(sizeof(router_values)); + memcpy(status->digest, digest, sizeof(status->digest)); + status->is_running = running; + status->bw_kb = bw; + status->is_auth = auth; + return status; +} + +routerinfo_t *routerinfo_new(router_values *status, int family, int addr); +/** Given a router_values struct, generate a pointer to a routerinfo struct. + * In the cache_info member, put the identity digest, and depending on + * the family argument, fill the IPv4 or IPv6 address. Return the pointer. + * The returned pointer has to be freed by the caller. + */ +routerinfo_t * +routerinfo_new(router_values *status, int family, int addr) +{ + routerinfo_t *ri = tor_malloc(sizeof(routerinfo_t)); + signed_descriptor_t cache_info; + memcpy(cache_info.identity_digest, status->digest, + sizeof(cache_info.identity_digest)); + ri->cache_info = cache_info; + tor_addr_t ipv6, ipv4; + ipv6.family = family; + ipv4.family = family; + // Set the address of the other IP version to 0 + if (family == AF_INET) { + ipv4.addr.in_addr.s_addr = addr; + for (size_t i = 0; i < 16; i++) { + ipv6.addr.in6_addr.s6_addr[i] = 0; + } + } else { + for (size_t i = 0; i < 16; i++) { + ipv6.addr.in6_addr.s6_addr[i] = addr; + } + ipv4.addr.in_addr.s_addr = 0; + } + ri->ipv6_addr = ipv6; + ri->ipv4_addr = ipv4; + return ri; +} + +static void +test_dirvote_compare_routerinfo_usefulness(void *arg) +{ + (void)arg; + MOCK(router_digest_is_trusted_dir_type, mock_router_digest_is_trusted); + MOCK(node_get_by_id, mock_node_get_by_id); + MOCK(dirserv_get_bandwidth_for_router_kb, mock_dirserv_get_bw); + ALLOCATE_MOCK_NODES(); + router_properties = digestmap_new(); + + // The router one is the "least useful" router, every router is compared to + // it + tor_digest digest_one = "aaaa"; + router_values *status_one = router_values_new(0, 0, 0, digest_one); + digestmap_set(router_properties, status_one->digest, status_one); + tor_digest digest_two = "bbbb"; + router_values *status_two = router_values_new(0, 1, 0, digest_two); + digestmap_set(router_properties, status_two->digest, status_two); + tor_digest digest_three = "cccc"; + router_values *status_three = router_values_new(1, 0, 0, digest_three); + digestmap_set(router_properties, status_three->digest, status_three); + tor_digest digest_four = "dddd"; + router_values *status_four = router_values_new(0, 0, 128, digest_four); + digestmap_set(router_properties, status_four->digest, status_four); + tor_digest digest_five = "9999"; + router_values *status_five = router_values_new(0, 0, 0, digest_five); + digestmap_set(router_properties, status_five->digest, status_five); + + // A router that has auth status is more useful than a non-auth one + routerinfo_t *first = routerinfo_new(status_one, AF_INET, 0xf); + routerinfo_t *second = routerinfo_new(status_two, AF_INET, 0xf); + int a = compare_routerinfo_usefulness(first, second); + tt_assert(a == 1); + tor_free(second); + + // A running router is more useful than a non running one + routerinfo_t *third = routerinfo_new(status_three, AF_INET, 0xf); + a = compare_routerinfo_usefulness(first, third); + tt_assert(a == 1); + tor_free(third); + + // A higher bandwidth is more useful + routerinfo_t *fourth = routerinfo_new(status_four, AF_INET, 0xf); + a = compare_routerinfo_usefulness(first, fourth); + tt_assert(a == 1); + tor_free(fourth); + + // In case of tie, the digests are compared + routerinfo_t *fifth = routerinfo_new(status_five, AF_INET, 0xf); + a = compare_routerinfo_usefulness(first, fifth); + tt_assert(a > 0); + tor_free(fifth); + +done: + UNMOCK(router_digest_is_trusted_dir_type); + UNMOCK(node_get_by_id); + UNMOCK(dirserv_get_bandwidth_for_router_kb); + FREE_MOCK_NODES(); + digestmap_free(router_properties, NULL); + tor_free(status_one); + tor_free(status_two); + tor_free(status_three); + tor_free(status_four); + tor_free(status_five); + tor_free(first); +} + +static void +test_dirvote_compare_routerinfo_by_ipv4(void *arg) +{ + (void)arg; + MOCK(router_digest_is_trusted_dir_type, mock_router_digest_is_trusted); + MOCK(node_get_by_id, mock_node_get_by_id); + MOCK(dirserv_get_bandwidth_for_router_kb, mock_dirserv_get_bw); + + ALLOCATE_MOCK_NODES(); + router_properties = digestmap_new(); + tor_digest digest_one = "aaaa"; + router_values *status_one = router_values_new(0, 0, 0, digest_one); + digestmap_set(router_properties, status_one->digest, status_one); + tor_digest digest_two = "bbbb"; + router_values *status_two = router_values_new(0, 1, 0, digest_two); + digestmap_set(router_properties, status_two->digest, status_two); + + // Both routers have an IPv4 address + routerinfo_t *first = routerinfo_new(status_one, AF_INET, 1); + routerinfo_t *second = routerinfo_new(status_two, AF_INET, 0xf); + + // The first argument's address precedes the seconds' one + int a = compare_routerinfo_by_ipv4((const void **)&first, + (const void **)&second); + tt_assert(a < 0); + // The second argument's address precedes the first' one + a = compare_routerinfo_by_ipv4((const void **)&second, + (const void **)&first); + tt_assert(a > 0); + tor_addr_copy(&(second->ipv4_addr), &(first->ipv6_addr)); + // The addresses are equal, they are compared by usefulness, + // and first is less useful than second + a = compare_routerinfo_by_ipv4((const void **)&first, + (const void **)&second); + tt_assert(a == 1); +done: + UNMOCK(router_digest_is_trusted_dir_type); + UNMOCK(node_get_by_id); + UNMOCK(dirserv_get_bandwidth_for_router_kb); + FREE_MOCK_NODES(); + digestmap_free(router_properties, NULL); + tor_free(status_one); + tor_free(status_two); + tor_free(first); + tor_free(second); +} + +static void +test_dirvote_compare_routerinfo_by_ipv6(void *arg) +{ + (void)arg; + MOCK(router_digest_is_trusted_dir_type, mock_router_digest_is_trusted); + MOCK(node_get_by_id, mock_node_get_by_id); + MOCK(dirserv_get_bandwidth_for_router_kb, mock_dirserv_get_bw); + + ALLOCATE_MOCK_NODES(); + router_properties = digestmap_new(); + char digest_one[DIGEST_LEN] = "aaaa"; + router_values *status_one = router_values_new(0, 0, 0, digest_one); + digestmap_set(router_properties, status_one->digest, status_one); + char digest_two[DIGEST_LEN] = "bbbb"; + router_values *status_two = router_values_new(0, 1, 0, digest_two); + digestmap_set(router_properties, status_two->digest, status_two); + + // Both routers have an IPv6 address + routerinfo_t *first = routerinfo_new(status_one, AF_INET6, 1); + routerinfo_t *second = routerinfo_new(status_two, AF_INET6, 0xf); + + // The first argument's address precedes the seconds' one + int a = compare_routerinfo_by_ipv6((const void **)&first, + (const void **)&second); + tt_assert(a < 0); + // The second argument's address precedes the first' one + a = compare_routerinfo_by_ipv6((const void **)&second, + (const void **)&first); + tt_assert(a > 0); + tor_addr_copy(&(first->ipv6_addr), &(second->ipv6_addr)); + // The addresses are equal, they are compared by usefulness, + // and first is less useful than second + a = compare_routerinfo_by_ipv6((const void **)&first, + (const void **)&second); + tt_assert(a == 1); +done: + UNMOCK(router_digest_is_trusted_dir_type); + UNMOCK(node_get_by_id); + UNMOCK(dirserv_get_bandwidth_for_router_kb); + FREE_MOCK_NODES(); + digestmap_free(router_properties, NULL); + tor_free(status_one); + tor_free(status_two); + tor_free(first); + tor_free(second); +} + +/** Create routers values and routerinfos that always have the same + * characteristics, and add them to the global digestmap. This macro is here to + * avoid duplicated code fragments. + * The created name##_val pointer should be freed by the caller (and cannot + * be freed in the macro as it causes a heap-after-free error) + */ +#define CREATE_ROUTER(digest, name, addr, ip_version) \ + tor_digest name##_digest = digest; \ + router_values *name##_val = router_values_new(1, 1, 1, name##_digest); \ + digestmap_set(router_properties, name##_digest, name##_val); \ + routerinfo_t *name##_ri = routerinfo_new(name##_val, ip_version, addr); + +#define ROUTER_FREE(name) \ + tor_free(name##_val); \ + tor_free(name##_ri); + +/** Test to see if the returned routers are exactly the ones that should be + * flagged as sybils : we test for inclusion then for number of elements + */ +#define TEST_SYBIL(true_sybil, possible_sybil) \ + DIGESTMAP_FOREACH (true_sybil, sybil_id, void *, ignore) { \ + (void)ignore; \ + tt_assert(digestmap_get(possible_sybil, sybil_id)); \ + } \ + DIGESTMAP_FOREACH_END; \ + tt_assert(digestmap_size(true_sybil) == digestmap_size(possible_sybil)); + +static void +test_dirvote_get_sybil_by_ip_version_ipv4(void *arg) +{ + // It is assumed that global_dirauth_options.AuthDirMaxServersPerAddr == 2 + (void)arg; + MOCK(router_digest_is_trusted_dir_type, mock_router_digest_is_trusted); + MOCK(node_get_by_id, mock_node_get_by_id); + MOCK(dirserv_get_bandwidth_for_router_kb, mock_dirserv_get_bw); + ALLOCATE_MOCK_NODES(); + router_properties = digestmap_new(); + smartlist_t *routers_ipv4; + routers_ipv4 = smartlist_new(); + digestmap_t *true_sybil_routers = NULL; + true_sybil_routers = digestmap_new(); + digestmap_t *omit_as_sybil; + + CREATE_ROUTER("aaaa", aaaa, 123, AF_INET); + smartlist_add(routers_ipv4, aaaa_ri); + CREATE_ROUTER("bbbb", bbbb, 123, AF_INET); + smartlist_add(routers_ipv4, bbbb_ri); + omit_as_sybil = get_sybil_list_by_ip_version(routers_ipv4, AF_INET); + tt_assert(digestmap_isempty(omit_as_sybil) == 1); + + CREATE_ROUTER("cccc", cccc, 123, AF_INET); + smartlist_add(routers_ipv4, cccc_ri); + digestmap_set(true_sybil_routers, cccc_digest, cccc_digest); + omit_as_sybil = get_sybil_list_by_ip_version(routers_ipv4, AF_INET); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("dddd", dddd, 123, AF_INET); + smartlist_add(routers_ipv4, dddd_ri); + digestmap_set(true_sybil_routers, dddd_digest, dddd_digest); + omit_as_sybil = get_sybil_list_by_ip_version(routers_ipv4, AF_INET); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("eeee", eeee, 456, AF_INET); + smartlist_add(routers_ipv4, eeee_ri); + omit_as_sybil = get_sybil_list_by_ip_version(routers_ipv4, AF_INET); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("ffff", ffff, 456, AF_INET); + smartlist_add(routers_ipv4, ffff_ri); + omit_as_sybil = get_sybil_list_by_ip_version(routers_ipv4, AF_INET); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("gggg", gggg, 456, AF_INET); + smartlist_add(routers_ipv4, gggg_ri); + digestmap_set(true_sybil_routers, gggg_digest, gggg_digest); + omit_as_sybil = get_sybil_list_by_ip_version(routers_ipv4, AF_INET); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("hhhh", hhhh, 456, AF_INET); + smartlist_add(routers_ipv4, hhhh_ri); + digestmap_set(true_sybil_routers, hhhh_digest, hhhh_digest); + omit_as_sybil = get_sybil_list_by_ip_version(routers_ipv4, AF_INET); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + +done: + UNMOCK(router_digest_is_trusted_dir_type); + UNMOCK(node_get_by_id); + UNMOCK(dirserv_get_bandwidth_for_router_kb); + FREE_MOCK_NODES(); + digestmap_free(router_properties, NULL); + smartlist_free(routers_ipv4); + digestmap_free(omit_as_sybil, NULL); + digestmap_free(true_sybil_routers, NULL); + ROUTER_FREE(aaaa); + ROUTER_FREE(bbbb); + ROUTER_FREE(cccc); + ROUTER_FREE(dddd); + ROUTER_FREE(eeee); + ROUTER_FREE(ffff); + ROUTER_FREE(gggg); + ROUTER_FREE(hhhh); +} + +static void +test_dirvote_get_sybil_by_ip_version_ipv6(void *arg) +{ + // It is assumed that global_dirauth_options.AuthDirMaxServersPerAddr == 2 + (void)arg; + MOCK(router_digest_is_trusted_dir_type, mock_router_digest_is_trusted); + MOCK(node_get_by_id, mock_node_get_by_id); + MOCK(dirserv_get_bandwidth_for_router_kb, mock_dirserv_get_bw); + ALLOCATE_MOCK_NODES(); + router_properties = digestmap_new(); + smartlist_t *routers_ipv6; + routers_ipv6 = smartlist_new(); + digestmap_t *true_sybil_routers = NULL; + true_sybil_routers = digestmap_new(); + digestmap_t *omit_as_sybil; + + CREATE_ROUTER("aaaa", aaaa, 123, AF_INET6); + smartlist_add(routers_ipv6, aaaa_ri); + CREATE_ROUTER("bbbb", bbbb, 123, AF_INET6); + smartlist_add(routers_ipv6, bbbb_ri); + omit_as_sybil = get_sybil_list_by_ip_version(routers_ipv6, AF_INET6); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("cccc", cccc, 123, AF_INET6); + smartlist_add(routers_ipv6, cccc_ri); + digestmap_set(true_sybil_routers, cccc_digest, cccc_digest); + omit_as_sybil = get_sybil_list_by_ip_version(routers_ipv6, AF_INET6); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("dddd", dddd, 123, AF_INET6); + smartlist_add(routers_ipv6, dddd_ri); + digestmap_set(true_sybil_routers, dddd_digest, dddd_digest); + omit_as_sybil = get_sybil_list_by_ip_version(routers_ipv6, AF_INET6); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("eeee", eeee, 456, AF_INET6); + smartlist_add(routers_ipv6, eeee_ri); + omit_as_sybil = get_sybil_list_by_ip_version(routers_ipv6, AF_INET6); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("ffff", ffff, 456, AF_INET6); + smartlist_add(routers_ipv6, ffff_ri); + omit_as_sybil = get_sybil_list_by_ip_version(routers_ipv6, AF_INET6); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("gggg", gggg, 456, AF_INET6); + smartlist_add(routers_ipv6, gggg_ri); + digestmap_set(true_sybil_routers, gggg_digest, gggg_digest); + omit_as_sybil = get_sybil_list_by_ip_version(routers_ipv6, AF_INET6); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("hhhh", hhhh, 456, AF_INET6); + smartlist_add(routers_ipv6, hhhh_ri); + digestmap_set(true_sybil_routers, hhhh_digest, hhhh_digest); + omit_as_sybil = get_sybil_list_by_ip_version(routers_ipv6, AF_INET6); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); +done: + UNMOCK(router_digest_is_trusted_dir_type); + UNMOCK(node_get_by_id); + UNMOCK(dirserv_get_bandwidth_for_router_kb); + FREE_MOCK_NODES(); + digestmap_free(router_properties, NULL); + digestmap_free(true_sybil_routers, NULL); + smartlist_free(routers_ipv6); + digestmap_free(omit_as_sybil, NULL); + ROUTER_FREE(aaaa); + ROUTER_FREE(bbbb); + ROUTER_FREE(cccc); + ROUTER_FREE(dddd); + ROUTER_FREE(eeee); + ROUTER_FREE(ffff); + ROUTER_FREE(gggg); + ROUTER_FREE(hhhh); +} + +static void +test_dirvote_get_all_possible_sybil(void *arg) +{ + // It is assumed that global_dirauth_options.AuthDirMaxServersPerAddr == 2 + (void)arg; + MOCK(router_digest_is_trusted_dir_type, mock_router_digest_is_trusted); + MOCK(node_get_by_id, mock_node_get_by_id); + MOCK(dirserv_get_bandwidth_for_router_kb, mock_dirserv_get_bw); + ALLOCATE_MOCK_NODES(); + router_properties = digestmap_new(); + smartlist_t *routers; + routers = smartlist_new(); + digestmap_t *true_sybil_routers = NULL; + true_sybil_routers = digestmap_new(); + digestmap_t *omit_as_sybil; + + CREATE_ROUTER("aaaa", aaaa, 123, AF_INET); + smartlist_add(routers, aaaa_ri); + CREATE_ROUTER("bbbb", bbbb, 123, AF_INET); + smartlist_add(routers, bbbb_ri); + omit_as_sybil = get_all_possible_sybil(routers); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("cccc", cccc, 123, AF_INET); + smartlist_add(routers, cccc_ri); + digestmap_set(true_sybil_routers, cccc_digest, cccc_digest); + omit_as_sybil = get_all_possible_sybil(routers); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("dddd", dddd, 123, AF_INET); + smartlist_add(routers, dddd_ri); + digestmap_set(true_sybil_routers, dddd_digest, dddd_digest); + omit_as_sybil = get_all_possible_sybil(routers); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("eeee", eeee, 456, AF_INET); + smartlist_add(routers, eeee_ri); + omit_as_sybil = get_all_possible_sybil(routers); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("ffff", ffff, 456, AF_INET); + smartlist_add(routers, ffff_ri); + omit_as_sybil = get_all_possible_sybil(routers); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("gggg", gggg, 456, AF_INET); + smartlist_add(routers, gggg_ri); + digestmap_set(true_sybil_routers, gggg_digest, gggg_digest); + omit_as_sybil = get_all_possible_sybil(routers); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("hhhh", hhhh, 456, AF_INET); + smartlist_add(routers, hhhh_ri); + digestmap_set(true_sybil_routers, hhhh_digest, hhhh_digest); + omit_as_sybil = get_all_possible_sybil(routers); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("iiii", iiii, 123, AF_INET6); + smartlist_add(routers, iiii_ri); + CREATE_ROUTER("jjjj", jjjj, 123, AF_INET6); + smartlist_add(routers, jjjj_ri); + omit_as_sybil = get_all_possible_sybil(routers); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("kkkk", kkkk, 123, AF_INET6); + smartlist_add(routers, kkkk_ri); + digestmap_set(true_sybil_routers, kkkk_digest, kkkk_digest); + omit_as_sybil = get_all_possible_sybil(routers); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("llll", llll, 123, AF_INET6); + smartlist_add(routers, llll_ri); + digestmap_set(true_sybil_routers, llll_digest, llll_digest); + omit_as_sybil = get_all_possible_sybil(routers); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("mmmm", mmmm, 456, AF_INET6); + smartlist_add(routers, mmmm_ri); + omit_as_sybil = get_all_possible_sybil(routers); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("nnnn", nnnn, 456, AF_INET6); + smartlist_add(routers, nnnn_ri); + omit_as_sybil = get_all_possible_sybil(routers); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("oooo", oooo, 456, AF_INET6); + smartlist_add(routers, oooo_ri); + digestmap_set(true_sybil_routers, oooo_digest, oooo_digest); + omit_as_sybil = get_all_possible_sybil(routers); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + + CREATE_ROUTER("pppp", pppp, 456, AF_INET6); + smartlist_add(routers, pppp_ri); + digestmap_set(true_sybil_routers, pppp_digest, pppp_digest); + omit_as_sybil = get_all_possible_sybil(routers); + TEST_SYBIL(true_sybil_routers, omit_as_sybil); + +done: + UNMOCK(router_digest_is_trusted_dir_type); + UNMOCK(node_get_by_id); + UNMOCK(dirserv_get_bandwidth_for_router_kb); + FREE_MOCK_NODES(); + digestmap_free(router_properties, NULL); + smartlist_free(routers); + digestmap_free(omit_as_sybil, NULL); + digestmap_free(true_sybil_routers, NULL); + ROUTER_FREE(aaaa); + ROUTER_FREE(bbbb); + ROUTER_FREE(cccc); + ROUTER_FREE(dddd); + ROUTER_FREE(eeee); + ROUTER_FREE(ffff); + ROUTER_FREE(gggg); + ROUTER_FREE(hhhh); + ROUTER_FREE(iiii); + ROUTER_FREE(jjjj); + ROUTER_FREE(kkkk); + ROUTER_FREE(llll); + ROUTER_FREE(mmmm); + ROUTER_FREE(nnnn); + ROUTER_FREE(oooo); + ROUTER_FREE(pppp); +} + +#define NODE(name, flags) \ + { \ + #name, test_dirvote_##name, (flags), NULL, NULL \ + } + +struct testcase_t dirvote_tests[] = { + NODE(compare_routerinfo_usefulness, TT_FORK), + NODE(compare_routerinfo_by_ipv6, TT_FORK), + NODE(compare_routerinfo_by_ipv4, TT_FORK), + NODE(get_sybil_by_ip_version_ipv4, TT_FORK), + NODE(get_sybil_by_ip_version_ipv6, TT_FORK), + NODE(get_all_possible_sybil, TT_FORK), + END_OF_TESTCASES};