commit a7cbaa7e58ad0d8e7fda373e3d4b88b695bb7545 Author: Karsten Loesing karsten.loesing@gmx.net Date: Fri Aug 24 12:47:11 2012 +0200
Add script to group relays by families (#6662). --- task-6662/.classpath | 6 ++ task-6662/.project | 17 ++++ task-6662/Eval.java | 215 ++++++++++++++++++++++++++++++++++++++++++++++++++ task-6662/README | 2 + 4 files changed, 240 insertions(+), 0 deletions(-)
diff --git a/task-6662/.classpath b/task-6662/.classpath new file mode 100644 index 0000000..233be1d --- /dev/null +++ b/task-6662/.classpath @@ -0,0 +1,6 @@ +<?xml version="1.0" encoding="UTF-8"?> +<classpath> + <classpathentry kind="src" path=""/> + <classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER"/> + <classpathentry kind="output" path=""/> +</classpath> diff --git a/task-6662/.project b/task-6662/.project new file mode 100644 index 0000000..36b9f76 --- /dev/null +++ b/task-6662/.project @@ -0,0 +1,17 @@ +<?xml version="1.0" encoding="UTF-8"?> +<projectDescription> + <name>family</name> + <comment></comment> + <projects> + </projects> + <buildSpec> + <buildCommand> + <name>org.eclipse.jdt.core.javabuilder</name> + <arguments> + </arguments> + </buildCommand> + </buildSpec> + <natures> + <nature>org.eclipse.jdt.core.javanature</nature> + </natures> +</projectDescription> diff --git a/task-6662/Eval.java b/task-6662/Eval.java new file mode 100644 index 0000000..5359fba --- /dev/null +++ b/task-6662/Eval.java @@ -0,0 +1,215 @@ +import java.io.*; +import java.util.*; +public class Eval { + /* curl "https://onionoo.torproject.org/details?running=true&type=relay" > details.json */ + public static void main(String[] args) throws Exception { + + /* Parse relays and their families from details.json. Also create a + * list of Named relays. */ + BufferedReader br = new BufferedReader(new FileReader( + "details.json")); + String line; + Set<String> family = new HashSet<String>(); + String nickname = null, fingerprint = null; + boolean isParsingFamily = false; + SortedMap<String, Set<String>> listedRelays = + new TreeMap<String, Set<String>>(); + Map<String, String> nicknames = new HashMap<String, String>(); + Map<String, String> namedRelays = new HashMap<String, String>(); + Set<String> unnamedRelays = new HashSet<String>(); + while ((line = br.readLine()) != null) { + if (isParsingFamily) { + if (line.startsWith(" ")) { + family.add(line.split(""")[1]); + } else { + listedRelays.put(fingerprint, family); + family = new HashSet<String>(); + isParsingFamily = false; + } + } + if (line.startsWith("{"nickname":")) { + nickname = line.split(":")[1].split(""")[1]; + } else if (line.startsWith(""fingerprint":")) { + fingerprint = "$" + line.split(":")[1].split(""")[1]; + nicknames.put(fingerprint, nickname); + } else if (line.startsWith(""flags":")) { + if (line.contains(""Named"")) { + if (namedRelays.containsKey(nickname)) { + System.err.println("Two named relays with same nickname: '" + + nickname + "'. Exiting."); + System.exit(1); + } + namedRelays.put(nickname, fingerprint); + } else { + unnamedRelays.add(nickname); + } + } else if (line.equals(""family":[")) { + isParsingFamily = true; + } + } + br.close(); + + /* Print out unconfirmed families reported by relays, possibly + * containing nicknames of unnamed relays. */ + SortedSet<String> unconfirmedFamilyStrings = new TreeSet<String>(); + System.out.println("Complete family relationships as reported by " + + "running relays, not mutually confirmed and possibly " + + "containing nicknames of unnamed relays:"); + for (Map.Entry<String, Set<String>> e : listedRelays.entrySet()) { + StringBuilder sb = new StringBuilder(); + sb.append(nicknames.get(e.getKey()) + "~" + + e.getKey().substring(1, 5) + " ->"); + for (String member : e.getValue()) { + if (member.startsWith("$")) { + sb.append(" " + (nicknames.containsKey(member) ? + nicknames.get(member) : "(not-running)") + "~" + + member.substring(1, 5)); + } else { + sb.append(" " + member + "~" + + (namedRelays.containsKey(member) ? + namedRelays.get(member).substring(1, 5) : + (unnamedRelays.contains(member) ? "(unnamed)" : + "(not-running)"))); + } + } + unconfirmedFamilyStrings.add(sb.toString()); + } + for (String s : unconfirmedFamilyStrings) { + System.out.println(s); + } + System.out.println(); + + /* Determine mutually confirmed families with two or more family + * members. */ + SortedMap<String, SortedSet<String>> confirmedRelays = + new TreeMap<String, SortedSet<String>>(); + for (Map.Entry<String, Set<String>> e : listedRelays.entrySet()) { + SortedSet<String> confirmedMembers = new TreeSet<String>(); + String ownFingerprint = e.getKey(); + String ownNickname = nicknames.get(e.getKey()); + String ownRelayString = ownNickname + "~" + + ownFingerprint.substring(1, 5); + for (String member : e.getValue()) { + String memberNickname = null, memberFingerprint = null; + if (!member.startsWith("$") && + namedRelays.containsKey(member) && + listedRelays.containsKey(namedRelays.get(member))) { + /* member is the nickname of a named relay. */ + memberNickname = member; + memberFingerprint = namedRelays.get(member); + } else if (member.startsWith("$") && + listedRelays.containsKey(member)) { + /* member is the fingerprint of a running relay. */ + memberNickname = nicknames.get(member); + memberFingerprint = member; + } + if (memberFingerprint == null) { + continue; + } + String memberRelayString = memberNickname + "~" + + memberFingerprint.substring(1, 5); + Set<String> otherMembers = listedRelays.get(memberFingerprint); + if (otherMembers != null && (otherMembers.contains(ownFingerprint) || + otherMembers.contains(ownNickname)) && + !(ownRelayString.equals(memberRelayString))) { + confirmedMembers.add(memberRelayString); + } + } + if (!confirmedMembers.isEmpty()) { + confirmedRelays.put(e.getKey(), confirmedMembers); + } + } + SortedSet<String> confirmedFamilyStrings = new TreeSet<String>(); + for (Map.Entry<String, SortedSet<String>> e : + confirmedRelays.entrySet()) { + StringBuilder sb = new StringBuilder(); + sb.append(nicknames.get(e.getKey()) + "~" + + e.getKey().substring(1, 5) + " ->"); + for (String member : e.getValue()) { + sb.append(" " + member); + } + confirmedFamilyStrings.add(sb.toString()); + } + System.out.println("Mutually confirmed families with two or more " + + "family members, without reporting relay itself"); + for (String s : confirmedFamilyStrings) { + System.out.println(s); + } + System.out.println(); + + /* Determine possibly overlapping families with two or more family + * members. */ + Set<SortedSet<String>> overlappingFamilies = + new HashSet<SortedSet<String>>(); + for (Map.Entry<String, SortedSet<String>> e : + confirmedRelays.entrySet()) { + SortedSet<String> overlappingFamily = new TreeSet<String>(); + overlappingFamily.add(nicknames.get(e.getKey()) + "~" + + e.getKey().substring(1, 5)); + overlappingFamily.addAll(e.getValue()); + overlappingFamilies.add(overlappingFamily); + } + SortedSet<String> overlappingFamilyStrings = new TreeSet<String>(); + for (SortedSet<String> overlappingFamily : overlappingFamilies) { + if (overlappingFamily.size() < 2) { + continue; + } + int written = 0; + StringBuilder sb = new StringBuilder(); + for (String member : overlappingFamily) { + sb.append((written++ > 0 ? " " : "") + member); + } + overlappingFamilyStrings.add(sb.toString()); + } + System.out.println("Possibly overlapping families with two or more " + + "family members:"); + for (String s : overlappingFamilyStrings) { + System.out.println(s); + } + System.out.println(); + + /* Merge possibly overlapping families into extended families. */ + Set<SortedSet<String>> extendedFamilies = + new HashSet<SortedSet<String>>(); + for (SortedSet<String> overlappingFamily : overlappingFamilies) { + SortedSet<String> newExtendedFamily = + new TreeSet<String>(overlappingFamily); + Set<SortedSet<String>> removeExtendedFamilies = + new HashSet<SortedSet<String>>(); + for (SortedSet<String> extendedFamily : extendedFamilies) { + for (String member : newExtendedFamily) { + if (extendedFamily.contains(member)) { + removeExtendedFamilies.add(extendedFamily); + break; + } + } + if (removeExtendedFamilies.contains(extendedFamily)) { + newExtendedFamily.addAll(extendedFamily); + } + } + for (SortedSet<String> removeExtendedFamily : + removeExtendedFamilies) { + extendedFamilies.remove(removeExtendedFamily); + } + extendedFamilies.add(newExtendedFamily); + } + SortedSet<String> extendedFamilyStrings = new TreeSet<String>(); + for (SortedSet<String> extendedFamily : extendedFamilies) { + if (extendedFamily.size() < 2) { + continue; + } + int written = 0; + StringBuilder sb = new StringBuilder(); + for (String member : extendedFamily) { + sb.append((written++ > 0 ? " " : "") + member); + } + extendedFamilyStrings.add(sb.toString()); + } + System.out.println("Extended families based on merging possibly " + + "overlapping families:"); + for (String s : extendedFamilyStrings) { + System.out.println(s); + } + } +} + diff --git a/task-6662/README b/task-6662/README new file mode 100644 index 0000000..87177f7 --- /dev/null +++ b/task-6662/README @@ -0,0 +1,2 @@ +Script to group relays by families +