r13979@catbus: nickm | 2007-07-29 01:20:20 -0400

 Implement proposal 109:  As an authority, never call more than 3 servers per IP Running and Valid.  Prefer Running servers to non-running ones; then prefer high-bandwidth to low-bandwidth.  Needs testing.


svn:r10968

6 files changed, 103 insertions, 8 deletions

diff --git a/ChangeLog b/ChangeLog
index 7246908b8e..411fa17d41 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -13,6 +13,9 @@ Changes in version 0.2.0.3-alpha - 2007-07-29
       at least 100KB/s, and consider their bandwidth adequate to be a
       Guard if it is at least 250KB/s, no matter the medians. This fix
       complements proposal 107. [Bugfix on 0.1.2.x]
+    - Directory authorities now never mark more than 3 servers per IP as
+      Valid and Running.  (Implements proposal 109, by Kevin Bauer and
+      Damon McCoy.)
 
   o Major bugfixes (directory):
     - Rewrite directory tokenization code to never run off the end of
diff --git a/doc/TODO b/doc/TODO
index 9d98ad9d4d..ceff559f1d 100644
--- a/doc/TODO
+++ b/doc/TODO
@@ -140,7 +140,7 @@ Things we'd like to do in 0.2.0.x:
       - Drop bandwidth history from router-descriptors
     - 105: Version negotiation for the Tor protocol
     - 108: Base "Stable" Flag on Mean Time Between Failures
-    - 109: No more than one server per IP address
+    o 109: No more than one server per IP address
     o 103: Splitting identity key from regularly used signing key
       o Merge with 101 into a new dir-spec.txt
     - 113: Simplifying directory authority administration
diff --git a/doc/spec/dir-spec-v2.txt b/doc/spec/dir-spec-v2.txt
index 712be9e7fc..553e565cc5 100644
--- a/doc/spec/dir-spec-v2.txt
+++ b/doc/spec/dir-spec-v2.txt
@@ -482,6 +482,12 @@ $Id$
    Directory server administrators may label some servers or IPs as
    blacklisted, and elect not to include them in their network-status lists.
 
+   Authorities SHOULD 'disable' any servers in excess of 3 on any single
+   IP.  When there are more than 3 to choose from, authorities should first
+   prefer Running to non-Running, and then prefer high-bandwidth to
+   low-bandwidth.  To 'disable' a server, the authority *should* advertise
+   it without the Running or Valid flag.
+
    Thus, the network-status list includes all non-blacklisted,
    non-expired, non-superseded descriptors.
 
diff --git a/doc/spec/dir-spec.txt b/doc/spec/dir-spec.txt
index 4da1e97712..1900fe3716 100644
--- a/doc/spec/dir-spec.txt
+++ b/doc/spec/dir-spec.txt
@@ -968,7 +968,13 @@ $Id$
    Directory server administrators may label some servers or IPs as
    blacklisted, and elect not to include them in their network-status lists.
 
-   Thus, the network-status list includes all non-blacklisted,
+   Authorities SHOULD 'disable' any servers in excess of 3 on any single
+   IP.  When there are more than 3 to choose from, authorities should first
+   prefer Running to non-Running, and then prefer high-bandwidth to
+   low-bandwidth.  To 'disable' a server, the authority *should* advertise
+   it without the Running or Valid flag.
+
+   Thus, the network-status vote includes all non-blacklisted,
    non-expired, non-superseded descriptors.
 
 3.4. Computing a consensus from a set of votes
diff --git a/doc/spec/proposals/109-no-sharing-ips.txt b/doc/spec/proposals/109-no-sharing-ips.txt
index 4a5f1a80b7..483b8b53fc 100644
--- a/doc/spec/proposals/109-no-sharing-ips.txt
+++ b/doc/spec/proposals/109-no-sharing-ips.txt
@@ -4,7 +4,7 @@ Version: $Revision$
 Last-Modified: $Date$
 Author: Kevin Bauer & Damon McCoy
 Created: 9-March-2007
-Status: Accepted
+Status: Closed
 
 Overview:
   This document describes a solution to a Sybil attack vulnerability in the
@@ -34,14 +34,19 @@ Specification:
   For each IP address, each directory authority tracks the number of routers
   using that IP address, along with their total observed bandwidth.  If there
   are more than MAX_SERVERS_PER_IP servers at some IP, the authority should
-  "disable" all but MAX_SERVERS_PER_IP servers.  If the total observed
+  "disable" all but MAX_SERVERS_PER_IP servers.  When choosing which servers
+  to disable, the authority should first disable non-Running servers in
+  increasing order of observed bandwidth, and then should disable Running
+  servers in increasing order of bandwidth.
+
+  [[  We don't actually do this part here. -NM
+
+  If the total observed
   bandwidth of the remaining non-"disabled" servers exceeds MAX_BW_PER_IP,
   the authority should "disable" some of the remaining servers until only one
   server remains, or until the remaining observed bandwidth of non-"disabled"
-  servers is under MAX_BW_PER_IP.  When choosing which servers to disable,
-  the authority should first disable non-Running servers in increasing order
-  of observed bandwidth, and then should disable Running servers in
-  increasing order of bandwidth.
+  servers is under MAX_BW_PER_IP.
+  ]]
 
   Servers that are "disabled" MUST be marked as non-Valid and non-Running.
 
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index e371ff7cbb..0a7a5f01af 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -1719,6 +1719,61 @@ _compare_routerinfo_by_id_digest(const void **a, const void **b)
                 DIGEST_LEN);
 }
 
+/** DOCDOC
+ *
+ * sort first by addr, and then by descending order of usefulness.
+ **/
+static int
+_compare_routerinfo_by_ip_and_bw(const void **a, const void **b)
+{
+  routerinfo_t *first = *(routerinfo_t **)a, *second = *(routerinfo_t **)b;
+  /* we return -1 if first should appear before second... that is,
+   * if first is a better router. */
+  if (first->addr < second->addr)
+    return -1;
+  else if (first->addr > second->addr)
+    return 1;
+  else if (first->is_running && !second->is_running)
+    return -1;
+  else if (!first->is_running && second->is_running)
+    return 1;
+  else if (first->bandwidthrate > second->bandwidthrate)
+    return -1;
+  else if (first->bandwidthrate < second->bandwidthrate)
+    return 1;
+  else
+    return 0;
+}
+
+/** DOCDOC takes list of routerinfo */
+static digestmap_t *
+get_possible_sybil_list(const smartlist_t *routers)
+{
+  digestmap_t *omit_as_sybil;
+  smartlist_t *routers_by_ip = smartlist_create();
+  uint32_t last_addr;
+  int addr_count;
+  smartlist_add_all(routers_by_ip, routers);
+  smartlist_sort(routers_by_ip, _compare_routerinfo_by_ip_and_bw);
+  omit_as_sybil = digestmap_new();
+
+#define MAX_WITH_SAME_ADDR 3
+  last_addr = 0;
+  addr_count = 0;
+  SMARTLIST_FOREACH(routers_by_ip, routerinfo_t *, ri,
+    {
+      if (last_addr != ri->addr) {
+        last_addr = ri->addr;
+        addr_count = 1;
+      } else if (++addr_count > MAX_WITH_SAME_ADDR) {
+        digestmap_set(omit_as_sybil, ri->cache_info.identity_digest, ri);
+      }
+    });
+
+  smartlist_free(routers_by_ip);
+  return omit_as_sybil;
+}
+
 /** DOCDOC */
 static void
 set_routerstatus_from_routerinfo(routerstatus_t *rs,
@@ -1795,6 +1850,7 @@ generate_networkstatus_vote_obj(crypto_pk_env_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;
 
   /* check that everything is deallocated XXXX020 */
 
@@ -1838,6 +1894,7 @@ generate_networkstatus_vote_obj(crypto_pk_env_t *private_key,
   routers = smartlist_create();
   smartlist_add_all(routers, rl->routers);
   smartlist_sort(routers, _compare_routerinfo_by_id_digest);
+  omit_as_sybil = get_possible_sybil_list(routers);
 
   routerstatuses = smartlist_create();
 
@@ -1852,11 +1909,18 @@ generate_networkstatus_vote_obj(crypto_pk_env_t *private_key,
                                        naming, exits_can_be_guards,
                                        listbadexits);
 
+      if (digestmap_get(omit_as_sybil, ri->cache_info.identity_digest)) {
+        rs->is_authority = rs->is_exit = rs->is_stable = rs->is_fast =
+          rs->is_running = rs->is_named = rs->is_valid = rs->is_v2_dir =
+          rs->is_possible_guard = 0;
+      }
+
       vrs->version = version_from_platform(ri->platform);
       smartlist_add(routerstatuses, vrs);
     }
   });
   smartlist_free(routers);
+  digestmap_free(omit_as_sybil, NULL);
 
   tor_assert(v3_out);
   memset(v3_out, 0, sizeof(networkstatus_vote_t));
@@ -2161,6 +2225,7 @@ generate_networkstatus_opinion(int v2)
   const char *contact;
   char *version_lines = NULL;
   smartlist_t *routers = NULL;
+  digestmap_t *omit_as_sybil = NULL;
 
   if (!v2)
     return generate_v3_networkstatus();
@@ -2246,6 +2311,8 @@ generate_networkstatus_opinion(int v2)
   smartlist_add_all(routers, rl->routers);
   smartlist_sort(routers, _compare_routerinfo_by_id_digest);
 
+  omit_as_sybil = get_possible_sybil_list(routers);
+
   SMARTLIST_FOREACH(routers, routerinfo_t *, ri, {
     if (ri->cache_info.published_on >= cutoff) {
       routerstatus_t rs;
@@ -2255,6 +2322,12 @@ generate_networkstatus_opinion(int v2)
                                        naming, exits_can_be_guards,
                                        listbadexits);
 
+      if (digestmap_get(omit_as_sybil, ri->cache_info.identity_digest)) {
+        rs.is_authority = rs.is_exit = rs.is_stable = rs.is_fast =
+          rs.is_running = rs.is_named = rs.is_valid = rs.is_v2_dir =
+          rs.is_possible_guard = 0;
+      }
+
       if (routerstatus_format_entry(outp, endp-outp, &rs, version, 0)) {
         log_warn(LD_BUG, "Unable to print router status.");
         tor_free(version);
@@ -2311,6 +2384,8 @@ generate_networkstatus_opinion(int v2)
   tor_free(identity_pkey);
   if (routers)
     smartlist_free(routers);
+  if (omit_as_sybil)
+    digestmap_free(omit_as_sybil, NULL);
   return r;
 }