[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

[tor-dev] Proposal 271 - improvements



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