Hello, I'm doing research on improving Tor security via path selection. This work is with Ryan Wails, Aaron Johnson, Prateek Mittal, and Olivier Pereira. In our work, we ran into load-balancing problems that affected our experiments. We identified the problem to originate in the specification and implementation of Proposal 271, "Another algorithm for guard selection", which was implemented in tor-0.3.0.1-alpha ~2 years ago and is thus now in tor stable. In short, Prop 271 causes guards to be selected with probabilities different than their weights due to the way it samples many guards and then chooses primary guards from that sample. We are suggesting a straightforward fix to the problem, which is, roughly speaking, to choose primary guards in the order in which they were sampled. We have created a patch implementing this fix for the case affecting our experiments, which would improve the current situation. We are further suggesting that Tor apply the technique throughout the guard-selection logic. In more detail, Prop 271 chooses guards via a multi-step process: 1. It chooses 20 distinct guards (and sometimes more) by sampling without replacement with probability proportional to consensus weight. 2. It produces two subsets of the sample: (1) "filtered" guards, which are guards that satisfy various torrc constraints, and (2) "confirmed" guards, which are guards through which a circuit has been constructed. 3. The "primary" guards (i.e. the actual guards used for circuits) are chosen from the confirmed and filtered subsets. I'm ignoring the additional "usable" subsets for clarity. This description is based on Section 4.6 of the specification (https://gitweb.torproject.org/torspec.git/tree/guard-spec.txt). The primary guards are selected uniformly at random from the filtered guards when no confirmed guards exist. No confirmed guards appear to exist until some primary guards have been selected, and so when Tor is started the first time the primary guards always come only from the filtered set. The uniformly-random selection causes a bias in primary-guard selection away from consensus weights and towards a more uniform selection of guards. As just an example of the problem, if there were only 20 guards in the network, the sampled set would be all guards and primary guard selection would be entirely uniformly random, ignoring weights entirely. This bias is worse the larger the sampled set is relative to the entire set of guards, and it has a significant effect on Tor simulations, which are typically on smaller networks. We believe that this issue has only a limited effect on Tor currently due to the relatively large number of guards. However, the issue is potentially worse when there exist confirmed guards. In this case, primary guards are chosen from the intersection of confirmed and filtered guards in the order they were added to the confirmed set. That order seems to be the order in which circuits were successfully created through the guards, which would thus be both somewhat non-deterministic (because it depends on when a circuit successfully finishes) and random (because circuits are only attempted through primary guards, which are initially uniformly-random filtered guards). The non-determinism especially could yield guard selection probabilities that deviate quite a bit from the consensus weights. This design has both performance and security implications. It potentially reduces the performance of the Tor network by making the load unbalanced. It also affects the correctness of performance analyses done with Shadow simulations, and the error is likely much larger due to the smaller size of simulation networks, which commonly include 100 or fewer guards. The design also reduces Tor's security by increasing the number of clients that an adversary running small relays can observe. In addition, an adversary has to wait less time than it should after it starts a malicious guard to be chosen by a client. This weakness occurs because the malicious guard only needs to enter the sampled list to have a chance to be chosen as primary, rather than having to wait until all previously-sampled guards have already expired. We propose a solution that fits well within the existing guard-selection algorithm. Our solution is to select primary guards in the order they were sampled. This ordering should be applied after the filtering and/or confirmed guard sets are constructed as normal. That is, primary guards should be selected from the filtered guards (if no guards are both confirmed and filtered) or from the set of confirmed and filtered guards (if such guards exist) in the order they were initially sampled. This solution guarantees that each primary guard is selected (without replacement) from all guards with a probability that is proportional to its consensus weight. We include a patch that applies this ordering only when primary guards are selected from filtered guards. This fixes the problem in Shadow simulations because confirmed guards never exist when primary guards are being selected. However, to solve all issues in the real Tor network, we recommend that you apply similar logic to the case that primary guards are selected from confirmed guards. Note that the issue of sampling skewing guard selection seems to have been raised in proposal discussions, which is documented in the proposal (although the proposed solution is less practical): > [Paul Syverson in a conversation at the Wilmington Meeting 2017 says that > we should look into how we're doing this sampling. Essentially, his > concern is that, since we are sampling by bandwidth at first (when we > choose the `sampled` set), then later there is another bias—when trying to > build circuits (and hence marking guards as confirmed) we select those > which completed a usable circuit first (and hence have the lowest > latency)—that this sort of "doubly skewed" selection may "snub" some > low-consensus-weight guards and leave them unused completely. Thus the > issue is primarily that we're not allocating network resources > efficiently. Mine and Nick's guard algorithm simulation code never > checked what percentage of possible guards the algorithm reasonably > allowed clients to use; this would be an interesting thing to check in > simulation at some point. If it does turn out to be a problem, Paul's > intuition for a fix is to select uniformly at random to obtain the > `sampled` set, then weight by bandwidth when trying to build circuits and > marking guards as confirmed. —isis] Best, Florentin
Attachment:
1500cli-250rel_sampling_exp.pdf
Description: 1500cli-250rel_sampling_exp.pdf
From 5f8ca77f1b650534a38afb07a28aef8bbf9b1a34 Mon Sep 17 00:00:00 2001
From: Florentin Rochet <florentin.rochet@xxxxxxxxxxxx>
Date: Wed, 11 Sep 2019 14:39:37 +0200
Subject: [PATCH] Makes selection of filtered guards and primary guard ordered
w.r.t. to the weighted selection during the sampling, to preserve
load-balancing and security for the choice of the primary guard
---
src/feature/client/entrynodes.c | 51 +++++++++++++++++++++++++++++----
src/feature/client/entrynodes.h | 12 ++++++++
2 files changed, 57 insertions(+), 6 deletions(-)
diff --git a/src/feature/client/entrynodes.c b/src/feature/client/entrynodes.c
index e543289ce..c2d821391 100644
--- a/src/feature/client/entrynodes.c
+++ b/src/feature/client/entrynodes.c
@@ -172,6 +172,7 @@ static entry_guard_t *get_sampled_guard_by_bridge_addr(guard_selection_t *gs,
const tor_addr_port_t *addrport);
static int entry_guard_obeys_restriction(const entry_guard_t *guard,
const entry_guard_restriction_t *rst);
+static int compare_guards_by_sampled_idx(const void **a_, const void **b_);
/** Return 0 if we should apply guardfraction information found in the
* consensus. A specific consensus can be specified with the
@@ -890,6 +891,7 @@ entry_guard_add_to_sample_impl(guard_selection_t *gs,
tor_free(guard->sampled_by_version);
guard->sampled_by_version = tor_strdup(VERSION);
guard->currently_listed = 1;
+ guard->sampled_idx = gs->next_sampled_idx++;
guard->confirmed_idx = -1;
/* non-persistent fields */
@@ -1771,7 +1773,8 @@ sample_reachable_filtered_entry_guards(guard_selection_t *gs,
flags, smartlist_len(reachable_filtered_sample));
if (smartlist_len(reachable_filtered_sample)) {
- result = smartlist_choose(reachable_filtered_sample);
+ smartlist_sort(reachable_filtered_sample, compare_guards_by_sampled_idx);
+ result = smartlist_get(reachable_filtered_sample, 0);
log_info(LD_GUARD, " (Selected %s.)",
result ? entry_guard_describe(result) : "<null>");
}
@@ -1795,6 +1798,21 @@ compare_guards_by_confirmed_idx(const void **a_, const void **b_)
else
return 0;
}
+/**
+ * Helper: compare two entry_guard_t by their sampled_idx values.
+ * Used to sort the sampled list
+ */
+static int
+compare_guards_by_sampled_idx(const void **a_, const void **b_)
+{
+ const entry_guard_t *a = *a_, *b = *b_;
+ if (a->sampled_idx < b->sampled_idx)
+ return -1;
+ else if (a->sampled_idx > b->sampled_idx)
+ return 1;
+ else
+ return 0;
+}
/**
* Find the confirmed guards from among the sampled guards in <b>gs</b>,
@@ -2051,12 +2069,21 @@ select_primary_guard_for_circuit(guard_selection_t *gs,
int num_entry_guards = get_n_primary_guards_to_use(usage);
smartlist_t *usable_primary_guards = smartlist_new();
+ /** Always takes the oldest ones first -- I did not find guarantees that
+ * gs->primary_entry_guards has the same ordering after update of the list,
+ * even for the num_entry_guards same relays
+ * */
+ smartlist_sort(gs->primary_entry_guards, compare_guards_by_sampled_idx);
SMARTLIST_FOREACH_BEGIN(gs->primary_entry_guards, entry_guard_t *, guard) {
entry_guard_consider_retry(guard);
- if (! entry_guard_obeys_restriction(guard, rst))
+ if (! entry_guard_obeys_restriction(guard, rst)){
+ log_info(LD_GUARD, "Entry guard %s doesn't obey restriction, we test the next one",
+ entry_guard_describe(guard));
continue;
+ }
if (guard->is_reachable != GUARD_REACHABLE_NO) {
if (need_descriptor && !guard_has_descriptor(guard)) {
+ log_info(LD_GUARD, "Guard %s does not have a descriptor", entry_guard_describe(guard));
continue;
}
*state_out = GUARD_CIRC_STATE_USABLE_ON_COMPLETION;
@@ -2069,9 +2096,9 @@ select_primary_guard_for_circuit(guard_selection_t *gs,
if (smartlist_len(usable_primary_guards)) {
chosen_guard = smartlist_choose(usable_primary_guards);
+ log_info(LD_GUARD, "Selected primary guard %s for circuit from a list size of %d.",
+ entry_guard_describe(chosen_guard), smartlist_len(usable_primary_guards));
smartlist_free(usable_primary_guards);
- log_info(LD_GUARD, "Selected primary guard %s for circuit.",
- entry_guard_describe(chosen_guard));
}
smartlist_free(usable_primary_guards);
@@ -2799,7 +2826,8 @@ entry_guard_encode_for_state(entry_guard_t *guard)
format_iso_time_nospace(tbuf, guard->sampled_on_date);
smartlist_add_asprintf(result, "sampled_on=%s", tbuf);
-
+
+ smartlist_add_asprintf(result, "sampled_idx=%d", guard->sampled_idx);
if (guard->sampled_by_version) {
smartlist_add_asprintf(result, "sampled_by=%s",
guard->sampled_by_version);
@@ -2870,6 +2898,7 @@ entry_guard_parse_from_state(const char *s)
char *rsa_id = NULL;
char *nickname = NULL;
char *sampled_on = NULL;
+ char *sampled_idx = NULL;
char *sampled_by = NULL;
char *unlisted_since = NULL;
char *listed = NULL;
@@ -2899,6 +2928,7 @@ entry_guard_parse_from_state(const char *s)
FIELD(rsa_id);
FIELD(nickname);
FIELD(sampled_on);
+ FIELD(sampled_idx);
FIELD(sampled_by);
FIELD(unlisted_since);
FIELD(listed);
@@ -3020,7 +3050,16 @@ entry_guard_parse_from_state(const char *s)
/* Take sampled_by_version verbatim. */
guard->sampled_by_version = sampled_by;
sampled_by = NULL; /* prevent free */
-
+ if (sampled_idx) {
+ int ok = 1;
+ long idx = tor_parse_long(sampled_idx, 10, 0, INT_MAX, &ok, NULL);
+ if (!ok) {
+ log_warn(LD_GUARD, "Guard has invalid sampled_idx %s",
+ escaped(sampled_idx));
+ } else {
+ guard->sampled_idx = (int)idx;
+ }
+ }
/* Listed is a boolean */
if (listed && strcmp(listed, "0"))
guard->currently_listed = 1;
diff --git a/src/feature/client/entrynodes.h b/src/feature/client/entrynodes.h
index 4e5eb4e96..cb94abbb9 100644
--- a/src/feature/client/entrynodes.h
+++ b/src/feature/client/entrynodes.h
@@ -116,6 +116,12 @@ struct entry_guard_t {
* successfully and decide to keep it?) This field is zero if this is not a
* confirmed guard. */
time_t confirmed_on_date; /* 0 if not confirmed */
+ /**
+ * In what order was this guard sampled without replacement? Guards with lower
+ * indices appear earlier on the sampled list
+ */
+ int sampled_idx;
+
/**
* In what order was this guard confirmed? Guards with lower indices
* appear earlier on the confirmed list. If the confirmed list is compacted,
@@ -271,6 +277,12 @@ struct guard_selection_s {
* confirmed_entry_guards receive? */
int next_confirmed_idx;
+ /** What sampled_idx value should the next-added member of
+ * sampled_entry_guards receive? This should follow the size of the sampled
+ * list until sampled relays get pruned for some reason
+ */
+ int next_sampled_idx;
+
};
struct entry_guard_handle_t;
--
2.17.1
_______________________________________________ tor-dev mailing list tor-dev@xxxxxxxxxxxxxxxxxxxx https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev