task-6662/Eval.java

   1 import java.io.*;
   2 import java.util.*;
   3 public class Eval {
   4   /* curl "https://onionoo.torproject.org/details?type=relay" > details.json */
   5   public static void main(String[] args) throws Exception {
   6
   7     /* Parse relays and their families from details.json.  Also create a
   8      * list of Named relays. */
   9     BufferedReader br = new BufferedReader(new FileReader(
  10         "details.json"));
  11     String line;
  12     Set<String> family = new HashSet<String>();
  13     String nickname = null, fingerprint = null;
  14     boolean isParsingFamily = false;
  15     SortedMap<String, Set<String>> listedRelays =
  16         new TreeMap<String, Set<String>>();
  17     Map<String, String> nicknames = new HashMap<String, String>();
  18     Map<String, String> namedRelays = new HashMap<String, String>();
  19     Set<String> runningRelays = new HashSet<String>(),
  20         unnamedRelays = new HashSet<String>();
  21     while ((line = br.readLine()) != null) {
  22       if (isParsingFamily) {
  23         if (line.startsWith("  ")) {
  24           family.add(line.split("\"")[1]);
  25         } else {
  26           listedRelays.put(fingerprint, family);
  27           family = new HashSet<String>();
  28           isParsingFamily = false;
  29         }
  30       }
  31       if (line.startsWith("{\"nickname\":")) {
  32         nickname = line.split(":")[1].split("\"")[1];
  33       } else if (line.startsWith("\"fingerprint\":")) {
  34         fingerprint = "$" + line.split(":")[1].split("\"")[1];
  35         nicknames.put(fingerprint, nickname);
  36       } else if (line.startsWith("\"running\":")) {
  37         if (line.endsWith("true,")) {
  38           runningRelays.add(nickname + "~" + fingerprint.substring(1, 5));
  39         }
  40       } else if (line.startsWith("\"flags\":")) {
  41         if (line.contains("\"Named\"")) {
  42           if (namedRelays.containsKey(nickname)) {
  43             System.err.println("Two named relays with same nickname: '"
  44                 + nickname + "'.  Exiting.");
  45             System.exit(1);
  46           }
  47           namedRelays.put(nickname, fingerprint);
  48         } else {
  49           unnamedRelays.add(nickname);
  50         }
  51       } else if (line.equals("\"family\":[")) {
  52         isParsingFamily = true;
  53       }
  54     }
  55     br.close();
  56
  57     /* Print out unconfirmed families reported by relays, possibly
  58      * containing nicknames of unnamed relays. */
  59     SortedSet<String> unconfirmedFamilyStrings = new TreeSet<String>();
  60     System.out.println("Complete family relationships as reported by "
  61         + "running relays, not mutually confirmed and possibly "
  62         + "containing nicknames of unnamed relays, including non-running "
  63         + "relays:");
  64     for (Map.Entry<String, Set<String>> e : listedRelays.entrySet()) {
  65       StringBuilder sb = new StringBuilder();
  66       sb.append(nicknames.get(e.getKey()) + "~"
  67           + e.getKey().substring(1, 5) + " ->");
  68       for (String member : e.getValue()) {
  69         if (member.startsWith("$")) {
  70           sb.append(" " + (nicknames.containsKey(member) ?
  71               nicknames.get(member) : "(not-running)") + "~"
  72               + member.substring(1, 5));
  73         } else {
  74           sb.append(" " + member + "~"
  75               + (namedRelays.containsKey(member) ?
  76               namedRelays.get(member).substring(1, 5) :
  77               (unnamedRelays.contains(member) ? "(unnamed)" :
  78               "(not-running)")));
  79         }
  80       }
  81       unconfirmedFamilyStrings.add(sb.toString());
  82     }
  83     for (String s : unconfirmedFamilyStrings) {
  84       System.out.println(s);
  85     }
  86     System.out.println();
  87
  88     /* Determine mutually confirmed families with two or more family
  89      * members. */
  90     SortedMap<String, SortedSet<String>> confirmedRelays =
  91         new TreeMap<String, SortedSet<String>>();
  92     for (Map.Entry<String, Set<String>> e : listedRelays.entrySet()) {
  93       SortedSet<String> confirmedMembers = new TreeSet<String>();
  94       String ownFingerprint = e.getKey();
  95       String ownNickname = nicknames.get(e.getKey());
  96       String ownRelayString = ownNickname + "~"
  97           + ownFingerprint.substring(1, 5);
  98       for (String member : e.getValue()) {
  99         String memberNickname = null, memberFingerprint = null;
 100         if (!member.startsWith("$") &&
 101             namedRelays.containsKey(member) &&
 102             listedRelays.containsKey(namedRelays.get(member))) {
 103           /* member is the nickname of a named relay. */
 104           memberNickname = member;
 105           memberFingerprint = namedRelays.get(member);
 106         } else if (member.startsWith("$") &&
 107             listedRelays.containsKey(member)) {
 108           /* member is the fingerprint of a running relay. */
 109           memberNickname = nicknames.get(member);
 110           memberFingerprint = member;
 111         }
 112         if (memberFingerprint == null) {
 113           continue;
 114         }
 115         String memberRelayString = memberNickname + "~"
 116             + memberFingerprint.substring(1, 5);
 117         Set<String> otherMembers = listedRelays.get(memberFingerprint);
 118         if (otherMembers != null && (otherMembers.contains(ownFingerprint) ||
 119             otherMembers.contains(ownNickname)) &&
 120             !(ownRelayString.equals(memberRelayString))) {
 121           confirmedMembers.add(memberRelayString);
 122         }
 123       }
 124       if (!confirmedMembers.isEmpty()) {
 125         confirmedRelays.put(e.getKey(), confirmedMembers);
 126       }
 127     }
 128     SortedSet<String> confirmedFamilyStrings = new TreeSet<String>();
 129     for (Map.Entry<String, SortedSet<String>> e :
 130         confirmedRelays.entrySet()) {
 131       StringBuilder sb = new StringBuilder();
 132       sb.append(nicknames.get(e.getKey()) + "~"
 133           + e.getKey().substring(1, 5) + " ->");
 134       for (String member : e.getValue()) {
 135         sb.append(" " + member);
 136       }
 137       confirmedFamilyStrings.add(sb.toString());
 138     }
 139     System.out.println("Mutually confirmed families with two or more "
 140         + "family members, without reporting relay itself, including "
 141         + "non-running relays");
 142     for (String s : confirmedFamilyStrings) {
 143       System.out.println(s);
 144     }
 145     System.out.println();
 146
 147     /* Determine possibly overlapping families with two or more family
 148      * members. */
 149     Set<SortedSet<String>> overlappingFamilies =
 150         new HashSet<SortedSet<String>>();
 151     for (Map.Entry<String, SortedSet<String>> e :
 152         confirmedRelays.entrySet()) {
 153       SortedSet<String> overlappingFamily = new TreeSet<String>();
 154       overlappingFamily.add(nicknames.get(e.getKey()) + "~"
 155           + e.getKey().substring(1, 5));
 156       overlappingFamily.addAll(e.getValue());
 157       overlappingFamilies.add(overlappingFamily);
 158     }
 159     SortedSet<String> overlappingFamilyStrings = new TreeSet<String>();
 160     for (SortedSet<String> overlappingFamily : overlappingFamilies) {
 161       if (overlappingFamily.size() < 2) {
 162         continue;
 163       }
 164       int written = 0;
 165       StringBuilder sb = new StringBuilder();
 166       for (String member : overlappingFamily) {
 167         sb.append((written++ > 0 ? " " : "") + member);
 168       }
 169       overlappingFamilyStrings.add(sb.toString());
 170     }
 171     System.out.println("Possibly overlapping families with two or more "
 172         + "family members, including non-running relays:");
 173     for (String s : overlappingFamilyStrings) {
 174       System.out.println(s);
 175     }
 176     System.out.println();
 177
 178     /* Merge possibly overlapping families into extended families. */
 179     Set<SortedSet<String>> extendedFamilies =
 180         new HashSet<SortedSet<String>>();
 181     for (SortedSet<String> overlappingFamily : overlappingFamilies) {
 182       SortedSet<String> newExtendedFamily =
 183           new TreeSet<String>(overlappingFamily);
 184       Set<SortedSet<String>> removeExtendedFamilies =
 185           new HashSet<SortedSet<String>>();
 186       for (SortedSet<String> extendedFamily : extendedFamilies) {
 187         for (String member : newExtendedFamily) {
 188           if (extendedFamily.contains(member)) {
 189             removeExtendedFamilies.add(extendedFamily);
 190             break;
 191           }
 192         }
 193         if (removeExtendedFamilies.contains(extendedFamily)) {
 194           newExtendedFamily.addAll(extendedFamily);
 195         }
 196       }
 197       for (SortedSet<String> removeExtendedFamily :
 198           removeExtendedFamilies) {
 199         extendedFamilies.remove(removeExtendedFamily);
 200       }
 201       extendedFamilies.add(newExtendedFamily);
 202     }
 203     SortedSet<String> extendedFamilyStrings = new TreeSet<String>();
 204     for (SortedSet<String> extendedFamily : extendedFamilies) {
 205       if (extendedFamily.size() < 2) {
 206         continue;
 207       }
 208       int written = 0;
 209       StringBuilder sb = new StringBuilder();
 210       for (String member : extendedFamily) {
 211         sb.append((written++ > 0 ? " " : "") + member);
 212       }
 213       extendedFamilyStrings.add(sb.toString());
 214     }
 215     System.out.println("Extended families based on merging possibly "
 216         + "overlapping families, including non-running relays:");
 217     for (String s : extendedFamilyStrings) {
 218       System.out.println(s);
 219     }
 220     System.out.println();
 221
 222     /* Filter non-running relays from extended families. */
 223     SortedSet<String> extendedFamilyRunningRelaysStrings =
 224         new TreeSet<String>();
 225     for (SortedSet<String> extendedFamily : extendedFamilies) {
 226       StringBuilder sb = new StringBuilder();
 227       int written = 0;
 228       for (String relay : extendedFamily) {
 229         if (runningRelays.contains(relay)) {
 230           sb.append((written++ > 0 ? " " : "") + relay);
 231         }
 232       }
 233       if (written > 1) {
 234         extendedFamilyRunningRelaysStrings.add(sb.toString());
 235       }
 236     }
 237     System.out.println("Extended families, excluding non-running relays "
 238         + "that may previously have helped merge overlapping families:");
 239     for (String s : extendedFamilyRunningRelaysStrings) {
 240       System.out.println(s);
 241     }
 242   }
 243 }
 244