commit 968def62d5872fb23279a35c2474db276ae455e7 Author: Karsten Loesing <karsten.loesing@gmx.net> Date: Sat Jan 17 17:53:03 2015 +0100 Add hidserv-stats extrapolation code (#13192). --- task-13192/.gitignore | 7 + task-13192/README.md | 24 + task-13192/src/R/plot.R | 246 ++++++++ task-13192/src/java/ExtrapolateHidServStats.java | 722 ++++++++++++++++++++++ 4 files changed, 999 insertions(+) diff --git a/task-13192/.gitignore b/task-13192/.gitignore new file mode 100644 index 0000000..7e8bf3b --- /dev/null +++ b/task-13192/.gitignore @@ -0,0 +1,7 @@ +in/ +.classpath +.project +src/bash/ +src/bin/ +out/ + diff --git a/task-13192/README.md b/task-13192/README.md new file mode 100644 index 0000000..c6ba2c8 --- /dev/null +++ b/task-13192/README.md @@ -0,0 +1,24 @@ +Extrapolating network totals from hidden-service statistics +=========================================================== + +Fetch (and inflate, but not extract) tarballs and/or fetch single files +from CollecTor and store them in the following directories: + + in/collector/archive/relay-descriptors/extra-infos/ + in/collector/archive/relay-descriptors/consensuses/ + in/collector/recent/relay-descriptors/extra-infos/ + in/collector/recent/relay-descriptors/consensuses/ + +Fetch the latest bandwidth.csv file from Metrics and put it in the +following directory: + + in/metrics/bandwidth.csv + +Add metrics-lib to the classpath and compile the classes in src/java/. + +Run Java class ExtrapolateHidServStats. + +Run the R script: + + R --slave -f src/R/plot.R + diff --git a/task-13192/src/R/plot.R b/task-13192/src/R/plot.R new file mode 100644 index 0000000..991928b --- /dev/null +++ b/task-13192/src/R/plot.R @@ -0,0 +1,246 @@ +# Load required libraries. +require(ggplot2, warn.conflicts = FALSE, quietly = TRUE) +require(scales, warn.conflicts = FALSE, quietly = TRUE) +require(reshape, warn.conflicts = FALSE, quietly = TRUE) +require(splines, warn.conflicts = FALSE, quietly = TRUE) +require(Hmisc, warn.conflicts = FALSE, quietly = TRUE) + +# Avoid scientific notation. +options(scipen = 15) + +# Read .csv file written by Java. +h <- read.csv("out/csv/hidserv-stats.csv", stringsAsFactors = FALSE) + +# Create directories for graphs. +dir.create(file.path("out", "graphs", "report"), showWarnings = FALSE, + recursive = TRUE) +dir.create(file.path("out", "graphs", "slides"), showWarnings = FALSE, + recursive = TRUE) + +# Cut off last two days, because stats might be incomplete for those. +h <- h[as.Date(h$stats_end) < max(as.Date(h$stats_end) - 1), ] + +# Graph the number of reported stats by day. +h7 <- data.frame(date = as.Date(h$stats_end), reports = 1) +ggplot(h7, aes(x = date)) + +geom_bar(colour = 'lightgray', width = .7, binwidth = 1) + +scale_x_date("") + +scale_y_continuous("") +ggsave("out/graphs/report/num-reported-stats.pdf", width = 10, height = 3, + dpi = 100) +ggsave("out/graphs/slides/hidserv-12.png", width = 8, height = 3, + dpi = 100) + +# Graph distributions of reported values by day. +h1 <- data.frame(date = as.Date(h$stats_end), + traffic = h$hidserv_rend_relayed_cells * 512 / (86400 * 1000 * 1000), + services = h$hidserv_dir_onions_seen) +h1 <- melt(h1, "date") +h1 <- data.frame(date = h1$date, + variable = ifelse(h1$variable == "traffic", "traffic in MB/s", + ".onion addresses"), value = h1$value) +ggplot(h1, aes(x = date, y = value, group = date)) + +geom_boxplot() + +facet_grid(variable ~ ., scales = "free_y") + +scale_x_date("") + +scale_y_continuous("Statistics reported by single relays\n") +ggsave("out/graphs/report/stats-by-day.pdf", width = 10, height = 5, + dpi = 100) + +# Graph distributions of calculated fractions by day. +h2 <- data.frame(date = as.Date(h$stats_end), + prob_rend_point = h$prob_rend_point, + x_frac_hsdesc = h$frac_hsdesc / 3.0) +h2 <- melt(h2, "date") +h2 <- data.frame(date = h2$date, + variable = ifelse(h2$variable == "prob_rend_point", + "selected as rendezvous point", "responsible for a descriptor"), + value = h2$value) +ggplot(h2, aes(x = date, y = value, group = date)) + +geom_boxplot() + +facet_grid(variable ~ ., scales = "free_y") + +scale_x_date("") + +scale_y_continuous("Calculated probabilities\n", labels = percent) +ggsave("out/graphs/report/probs-by-relay.pdf", width = 10, height = 5, + dpi = 100) + +# Graph ECDF of cells reported by relays with rend point probability of 0. +h8 <- h[h$prob_rend_point == 0, + "hidserv_rend_relayed_cells" ] +h8 <- sort(h8) +h8 <- data.frame(x = h8, y = (1:length(h8)) / length(h8)) +laplace_cells <- function(x) { + 0.5 + 0.5 * sign(x) * (1 - exp(abs(x) / (-2048/0.3))) +} +ggplot(h8, aes(x = x, y = y)) + +geom_line() + +stat_function(fun = laplace_cells, colour = "blue") + +scale_x_continuous("\nReported cells on rendezvous circuits") + +scale_y_continuous("Cumulative probability\n") +ggsave("out/graphs/report/zero-prob-cells.pdf", width = 5, height = 3, + dpi = 100) + +# Graph ECDF of .onions reported by relays with HSDir probability of 0. +h9 <- h[h$frac_hsdesc == 0, "hidserv_dir_onions_seen"] +h9 <- sort(h9) +h9 <- data.frame(x = h9, y = (1:length(h9)) / length(h9)) +laplace_onions <- function(x) { + 0.5 + 0.5 * sign(x) * (1 - exp(abs(x) / (-8/0.3))) +} +ggplot(h9, aes(x = x, y = y)) + +geom_line() + +stat_function(fun = laplace_onions, colour = "blue") + +scale_x_continuous("\nReported .onion addresses") + +scale_y_continuous("Cumulative probability\n") +ggsave("out/graphs/report/zero-prob-onions.pdf", width = 5, height = 3, + dpi = 100) + +# Graph correlation between reports and fractions per relay. +h3 <- rbind( + data.frame(x = h$frac_hsdesc / 3.0, + y = ifelse(h$frac_hsdesc == 0, NA, h$hidserv_dir_onions_seen), + facet = ".onion addresses"), + data.frame(x = h$prob_rend_point, + y = ifelse(h$prob_rend_point == 0, NA, + h$hidserv_rend_relayed_cells * 512 / (86400 * 1000)), + facet = "traffic in kB/s")) +ggplot(h3[h3$facet == ".onion addresses", ], aes(x = x, y = y)) + +geom_point(alpha = 0.5) + +stat_smooth(method = "lm") + +scale_x_continuous(name = "\nProbability", labels = percent) + +scale_y_continuous(name = "Reported .onion addresses\n") +ggsave("out/graphs/report/corr-probs-onions-by-relay.pdf", width = 5, + height = 3, dpi = 100) +ggplot(h3[h3$facet == "traffic in kB/s", ], aes(x = x, y = y)) + +geom_point(alpha = 0.5) + +stat_smooth(method = "lm") + +scale_x_continuous(name = "\nProbability", labels = percent) + +scale_y_continuous(name = "Reported traffic in kB/s\n") +ggsave("out/graphs/report/corr-probs-cells-by-relay.pdf", width = 5, + height = 3, dpi = 100) + +# Graph correlation between reports and fractions per day. +h5 <- rbind( + data.frame(date = as.Date(h$stats_end), + prob = ifelse(h$frac_hsdesc == 0, NA, h$frac_hsdesc / 3.0), + reported = h$hidserv_dir_onions_seen, facet = "published descriptor"), + data.frame(date = as.Date(h$stats_end), + prob = ifelse(h$prob_rend_point == 0, NA, h$prob_rend_point), + reported = h$hidserv_rend_relayed_cells * 512 / (86400 * 1000 * 1000), + facet = "traffic in MB/s")) +h5 <- na.omit(h5) +h5 <- aggregate(list(prob = h5$prob, reported = h5$reported), + by = list(date = h5$date, facet = h5$facet), FUN = sum) +ggplot(h5[h5$facet == "traffic in MB/s", ], aes(x = prob, y = reported)) + +geom_point(alpha = 0.5) + +scale_x_continuous(name = "\nTotal probability", labels = percent) + +scale_y_continuous(name = "Total traffic in MB/s\n") + +stat_smooth(method = "lm") + +geom_vline(xintercept = 0.01, linetype = 2) +ggsave("out/graphs/report/corr-probs-cells-by-day.pdf", width = 5, + height = 3, dpi = 100) +ggplot(h5[h5$facet == "published descriptor", ], + aes(x = prob, y = reported)) + +geom_point(alpha = 0.5) + +scale_x_continuous(name = "\nTotal probability", labels = percent) + +scale_y_continuous(name = "Total reported .onion addresses\n") + +stat_smooth(method = "lm") + +geom_vline(xintercept = 0.01, linetype = 2) +ggsave("out/graphs/report/corr-probs-onions-by-day.pdf", width = 5, + height = 3, dpi = 100) + +# Graph extrapolated network totals. +h6 <- data.frame(date = as.Date(h$stats_end), + traffic = ifelse(h$prob_rend_point == 0, 0, + h$hidserv_rend_relayed_cells * 512 / (86400 * 1000 * 1000)), + prob_rend_point = h$prob_rend_point, + onions = ifelse(h$frac_hsdesc == 0, 0, h$hidserv_dir_onions_seen), + prob_onion = h$frac_hsdesc * 4.0) +h6 <- aggregate(list(traffic = h6$traffic, + prob_rend_point = h6$prob_rend_point, + onions = h6$onions, + prob_onion = h6$prob_onion), by = list(date = h6$date), FUN = sum) +h6 <- data.frame(date = h6$date, + traffic = ifelse(h6$prob_rend_point < 0.01, 0, + h6$traffic / h6$prob_rend_point), + onions = ifelse(h6$prob_onion / 12.0 < 0.01, 0, + h6$onions / h6$prob_onion)) +h6 <- melt(h6, "date") +h6 <- h6[h6$value > 0, ] +h6 <- rbind(h6, data.frame(date = NA, variable = c('traffic', 'onions'), + value = 0)) +h6 <- data.frame(date = h6$date, + variable = ifelse(h6$variable == "traffic", "total traffic in MB/s", + ".onion addresses"), value = h6$value) +ggplot(h6, aes(date, value)) + +facet_grid(variable ~ ., scales = "free_y") + +geom_point() + +stat_smooth() + +scale_x_date(name = "") + +scale_y_continuous(name = "Extrapolated network totals\n") +ggsave("out/graphs/report/extrapolated-network-totals.pdf", width = 10, + height = 5, dpi = 100) + +# Graph extrapolated number of .onion addresses. +h11 <- h6[h6$variable == ".onion addresses", ] +ggplot(h11, aes(x = date, y = value)) + +geom_point() + +stat_smooth() + +scale_x_date(name = "") + +scale_y_continuous(name = "") +ggsave("out/graphs/slides/hidserv-13.png", width = 8, height = 3, + dpi = 100) + +# Graph extrapolated fraction of hidden-service traffic. +b <- read.csv("in/metrics/bandwidth.csv", stringsAsFactors = FALSE) +b <- b[b$isexit == '' & b$isguard == '' & b$date > '2014-12-20', ] +h10 <- data.frame(date = as.Date(h$stats_end), + traffic = h$hidserv_rend_relayed_cells * 512 / (86400 * 1000 * 1000), + prob_rend_point = h$prob_rend_point) +h10 <- aggregate(list(traffic = h10$traffic, + prob_rend_point = h10$prob_rend_point), by = list(date = h10$date), + FUN = sum) +h10 <- data.frame(date = h10$date, + traffic = ifelse(h10$prob_rend_point < 0.01, 0, + h10$traffic / h10$prob_rend_point)) +h10 <- melt(h10, "date") +h10 <- h10[h10$value > 0, ] +h10 <- rbind(h10, data.frame(date = as.Date(b$date), variable = "bw", + value = b$bwread + b$bwwrite)) +h10 <- cast(h10, date ~ variable, value = "value") +h10 <- na.omit(h10) +h10 <- data.frame(date = h10$date, + value = h10$traffic * 1000 * 1000 / h10$bw) +h10 <- rbind(h10, data.frame(date = NA, value = 0)) +ggplot(h10, aes(x = date, y = value)) + +geom_point() + +scale_x_date(name = "") + +scale_y_continuous(name = "", labels = percent) + +stat_smooth() +ggsave("out/graphs/slides/hidserv-14.png", width = 8, height = 3, + dpi = 100) + +# Graph simulation results for cells on rendezvous circuits. +s <- read.csv("out/csv/sim-cells.csv") +ggplot(s, aes(x = frac, y = (p500 - 1e10) / 1e10, + ymin = (p025 - 1e10) / 1e10, ymax = (p975 - 1e10) / 1e10)) + +geom_line() + +geom_ribbon(alpha = 0.2) + +scale_x_continuous("\nRendezvous points included in extrapolation", + labels = percent) + +scale_y_continuous("Deviation from network totals\n", labels = percent) +ggsave("out/graphs/report/sim-cells.pdf", width = 5, height = 3, + dpi = 100) + +# Graph simulation results for .onion addresses. +o <- read.csv("out/csv/sim-onions.csv") +ggplot(o, aes(x = frac, y = (p500 - 40000) / 40000, + ymin = (p025 - 40000) / 40000, ymax = (p975 - 40000) / 40000)) + +geom_line() + +geom_ribbon(alpha = 0.2) + +scale_x_continuous("\nDirectories included in extrapolation", + labels = percent) + +scale_y_continuous("Deviation from network totals\n", labels = percent) +ggsave("out/graphs/report/sim-onions.pdf", width = 5, height = 3, + dpi = 100) + diff --git a/task-13192/src/java/ExtrapolateHidServStats.java b/task-13192/src/java/ExtrapolateHidServStats.java new file mode 100644 index 0000000..100520d --- /dev/null +++ b/task-13192/src/java/ExtrapolateHidServStats.java @@ -0,0 +1,722 @@ +import java.io.BufferedWriter; +import java.io.ByteArrayInputStream; +import java.io.File; +import java.io.FileWriter; +import java.math.BigInteger; +import java.text.DateFormat; +import java.text.ParseException; +import java.text.SimpleDateFormat; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.Collections; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Random; +import java.util.Scanner; +import java.util.SortedMap; +import java.util.SortedSet; +import java.util.TimeZone; +import java.util.TreeMap; +import java.util.TreeSet; + +import org.torproject.descriptor.Descriptor; +import org.torproject.descriptor.DescriptorFile; +import org.torproject.descriptor.DescriptorReader; +import org.torproject.descriptor.DescriptorSourceFactory; +import org.torproject.descriptor.ExtraInfoDescriptor; +import org.torproject.descriptor.NetworkStatusEntry; +import org.torproject.descriptor.RelayNetworkStatusConsensus; + +public class ExtrapolateHidServStats { + + private static File archiveExtraInfosDirectory = + new File("in/collector/archive/relay-descriptors/extra-infos/"); + + private static File recentExtraInfosDirectory = + new File("in/collector/recent/relay-descriptors/extra-infos/"); + + private static File archiveConsensuses = + new File("in/collector/archive/relay-descriptors/consensuses/"); + + private static File recentConsensuses = + new File("in/collector/recent/relay-descriptors/consensuses/"); + + private static File hidservStatsCsvFile = + new File("out/csv/hidserv-stats.csv"); + + private static File simCellsCsvFile = + new File("out/csv/sim-cells.csv"); + + private static File simOnionsCsvFile = + new File("out/csv/sim-onions.csv"); + + public static void main(String[] args) throws Exception { + System.out.println("Extracting hidserv-* lines from extra-info " + + "descriptors..."); + SortedMap<String, SortedSet<HidServStats>> hidServStats = + extractHidServStats(); + System.out.println("Extracting fractions from consensuses..."); + SortedMap<String, SortedSet<ConsensusFraction>> consensusFractions = + extractConsensusFractions(hidServStats.keySet()); + System.out.println("Extrapolating statistics..."); + extrapolateHidServStats(hidServStats, consensusFractions); + System.out.println("Simulating extrapolation of rendezvous cells..."); + simulateCells(); + System.out.println("Simulating extrapolation of .onions..."); + simulateOnions(); + System.out.println("Terminating."); + } + + private static final DateFormat DATE_TIME_FORMAT; + + static { + DATE_TIME_FORMAT = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); + DATE_TIME_FORMAT.setLenient(false); + DATE_TIME_FORMAT.setTimeZone(TimeZone.getTimeZone("UTC")); + } + + private static class HidServStats implements Comparable<HidServStats> { + + /* Hidden-service statistics end timestamp in milliseconds. */ + private long statsEndMillis; + + /* Statistics interval length in seconds. */ + private long statsIntervalSeconds; + + /* Number of relayed cells reported by the relay and adjusted by + * rounding to the nearest right side of a bin and subtracting half of + * the bin size. */ + private long rendRelayedCells; + + /* Number of .onions reported by the relay and adjusted by rounding to + * the nearest right side of a bin and subtracting half of the bin + * size. */ + private long dirOnionsSeen; + + private HidServStats(long statsEndMillis, long statsIntervalSeconds, + long rendRelayedCells, long dirOnionsSeen) { + this.statsEndMillis = statsEndMillis; + this.statsIntervalSeconds = statsIntervalSeconds; + this.rendRelayedCells = rendRelayedCells; + this.dirOnionsSeen = dirOnionsSeen; + } + + @Override + public boolean equals(Object otherObject) { + if (!(otherObject instanceof HidServStats)) { + return false; + } + HidServStats other = (HidServStats) otherObject; + return this.statsEndMillis == other.statsEndMillis && + this.statsIntervalSeconds == other.statsIntervalSeconds && + this.rendRelayedCells == other.rendRelayedCells && + this.dirOnionsSeen == other.dirOnionsSeen; + } + + @Override + public int compareTo(HidServStats other) { + return this.statsEndMillis < other.statsEndMillis ? -1 : + this.statsEndMillis > other.statsEndMillis ? 1 : 0; + } + } + + /* Extract fingerprint and hidserv-* lines from extra-info descriptors + * located in in/{archive,recent}/relay-descriptors/extra-infos/. */ + private static SortedMap<String, SortedSet<HidServStats>> + extractHidServStats() { + SortedMap<String, SortedSet<HidServStats>> extractedHidServStats = + new TreeMap<String, SortedSet<HidServStats>>(); + DescriptorReader descriptorReader = + DescriptorSourceFactory.createDescriptorReader(); + descriptorReader.addDirectory(archiveExtraInfosDirectory); + descriptorReader.addDirectory(recentExtraInfosDirectory); + Iterator<DescriptorFile> descriptorFiles = + descriptorReader.readDescriptors(); + while (descriptorFiles.hasNext()) { + DescriptorFile descriptorFile = descriptorFiles.next(); + for (Descriptor descriptor : descriptorFile.getDescriptors()) { + if (!(descriptor instanceof ExtraInfoDescriptor)) { + continue; + } + String fingerprint = + ((ExtraInfoDescriptor) descriptor).getFingerprint(); + Scanner scanner = new Scanner(new ByteArrayInputStream( + descriptor.getRawDescriptorBytes())); + Long statsEndMillis = null, statsIntervalSeconds = null, + rendRelayedCells = null, dirOnionsSeen = null; + try { + while (scanner.hasNext()) { + String line = scanner.nextLine(); + if (line.startsWith("hidserv-")) { + String[] parts = line.split(" "); + if (parts[0].equals("hidserv-stats-end")) { + if (parts.length != 5 || !parts[3].startsWith("(") || + !parts[4].equals("s)")) { + /* Will warn below, because statsEndMillis and + * statsIntervalSeconds are still null. */ + continue; + } + statsEndMillis = DATE_TIME_FORMAT.parse( + parts[1] + " " + parts[2]).getTime(); + statsIntervalSeconds = + Long.parseLong(parts[3].substring(1)); + } else if (parts[0].equals("hidserv-rend-relayed-cells")) { + if (parts.length != 5 || + !parts[4].startsWith("bin_size=")) { + /* Will warn below, because rendRelayedCells is still + * null. */ + continue; + } + rendRelayedCells = removeNoise(Long.parseLong(parts[1]), + Long.parseLong(parts[4].substring(9))); + } else if (parts[0].equals("hidserv-dir-onions-seen")) { + if (parts.length != 5 || + !parts[4].startsWith("bin_size=")) { + /* Will warn below, because dirOnionsSeen is still + * null. */ + continue; + } + dirOnionsSeen = removeNoise(Long.parseLong(parts[1]), + Long.parseLong(parts[4].substring(9))); + } + } + } + } catch (ParseException e) { + e.printStackTrace(); + continue; + } catch (NumberFormatException e) { + e.printStackTrace(); + continue; + } + if (statsEndMillis == null && statsIntervalSeconds == null && + rendRelayedCells == null && dirOnionsSeen == null) { + continue; + } else if (statsEndMillis != null && statsIntervalSeconds != null + && rendRelayedCells != null && dirOnionsSeen != null) { + if (!extractedHidServStats.containsKey(fingerprint)) { + extractedHidServStats.put(fingerprint, + new TreeSet<HidServStats>()); + } + extractedHidServStats.get(fingerprint).add(new HidServStats( + statsEndMillis, statsIntervalSeconds, rendRelayedCells, + dirOnionsSeen)); + } else { + System.err.println("Relay " + fingerprint + " published " + + "incomplete hidserv-stats. Ignoring."); + } + } + } + return extractedHidServStats; + } + + private static long removeNoise(long reportedNumber, long binSize) { + long roundedToNearestRightSideOfTheBin = + ((reportedNumber + binSize / 2) / binSize) * binSize; + long subtractedHalfOfBinSize = + roundedToNearestRightSideOfTheBin - binSize / 2; + return subtractedHalfOfBinSize; + } + + private static class ConsensusFraction + implements Comparable<ConsensusFraction> { + + /* Valid-after timestamp of the consensus in milliseconds. */ + private long validAfterMillis; + + /* Fresh-until timestamp of the consensus in milliseconds. */ + private long freshUntilMillis; + + /* Fraction of consensus weight in [0.0, 1.0] of this relay. */ + private double fractionConsensusWeight; + + /* Probability for being selected by clients as rendezvous point. */ + private double probabilityRendezvousPoint; + + /* Fraction of descriptor identifiers in [0.0, 1.0] that this relay + * has been responsible for. This is the "distance" from the + * fingerprint of the relay three HSDir positions earlier in the ring + * to the fingerprint of this relay. Fractions of all HSDirs in a + * consensus add up to 3.0, not 1.0. */ + private double fractionResponsibleDescriptors; + + private ConsensusFraction(long validAfterMillis, + long freshUntilMillis, + double fractionConsensusWeight, + double probabilityRendezvousPoint, + double fractionResponsibleDescriptors) { + this.validAfterMillis = validAfterMillis; + this.freshUntilMillis = freshUntilMillis; + this.fractionConsensusWeight = fractionConsensusWeight; + this.probabilityRendezvousPoint = probabilityRendezvousPoint; + this.fractionResponsibleDescriptors = + fractionResponsibleDescriptors; + } + + @Override + public boolean equals(Object otherObject) { + if (!(otherObject instanceof ConsensusFraction)) { + return false; + } + ConsensusFraction other = (ConsensusFraction) otherObject; + return this.validAfterMillis == other.validAfterMillis && + this.freshUntilMillis == other.freshUntilMillis && + this.fractionResponsibleDescriptors == + other.fractionResponsibleDescriptors && + this.fractionConsensusWeight == other.fractionConsensusWeight && + this.probabilityRendezvousPoint == + other.probabilityRendezvousPoint; + } + + @Override + public int compareTo(ConsensusFraction other) { + return this.validAfterMillis < other.validAfterMillis ? -1 : + this.validAfterMillis > other.validAfterMillis ? 1 : 0; + } + } + + /* Extract fractions that relays were responsible for from consensuses + * located in in/{archive,recent}/relay-descriptors/consensuses/. */ + private static SortedMap<String, SortedSet<ConsensusFraction>> + extractConsensusFractions(Collection<String> fingerprints) { + SortedMap<String, SortedSet<ConsensusFraction>> + extractedConsensusFractions = + new TreeMap<String, SortedSet<ConsensusFraction>>(); + DescriptorReader descriptorReader = + DescriptorSourceFactory.createDescriptorReader(); + descriptorReader.addDirectory(archiveConsensuses); + descriptorReader.addDirectory(recentConsensuses); + Iterator<DescriptorFile> descriptorFiles = + descriptorReader.readDescriptors(); + while (descriptorFiles.hasNext()) { + DescriptorFile descriptorFile = descriptorFiles.next(); + for (Descriptor descriptor : descriptorFile.getDescriptors()) { + if (!(descriptor instanceof RelayNetworkStatusConsensus)) { + continue; + } + RelayNetworkStatusConsensus consensus = + (RelayNetworkStatusConsensus) descriptor; + SortedSet<String> weightKeys = new TreeSet<String>(Arrays.asList( + "Wmg,Wmm,Wme,Wmd".split(","))); + weightKeys.removeAll(consensus.getBandwidthWeights().keySet()); + if (!weightKeys.isEmpty()) { + System.err.println("Consensus with valid-after time " + + DATE_TIME_FORMAT.format(consensus.getValidAfterMillis()) + + " doesn't contain expected Wmx weights. Skipping."); + continue; + } + double wmg = ((double) consensus.getBandwidthWeights().get("Wmg")) + / 10000.0; + double wmm = ((double) consensus.getBandwidthWeights().get("Wmm")) + / 10000.0; + double wme = ((double) consensus.getBandwidthWeights().get("Wme")) + / 10000.0; + double wmd = ((double) consensus.getBandwidthWeights().get("Wmd")) + / 10000.0; + SortedSet<String> hsDirs = new TreeSet<String>( + Collections.reverseOrder()); + long totalConsensusWeight = 0L; + double totalWeightsRendezvousPoint = 0.0; + SortedMap<String, Double> weightsRendezvousPoint = + new TreeMap<String, Double>(); + for (Map.Entry<String, NetworkStatusEntry> e : + consensus.getStatusEntries().entrySet()) { + String fingerprint = e.getKey(); + NetworkStatusEntry statusEntry = e.getValue(); + SortedSet<String> flags = statusEntry.getFlags(); + if (flags.contains("HSDir")) { + hsDirs.add(statusEntry.getFingerprint()); + } + totalConsensusWeight += statusEntry.getBandwidth(); + double weightRendezvousPoint = 0.0; + if (flags.contains("Fast")) { + weightRendezvousPoint = (double) statusEntry.getBandwidth(); + if (flags.contains("Guard") && flags.contains("Exit")) { + weightRendezvousPoint *= wmd; + } else if (flags.contains("Guard")) { + weightRendezvousPoint *= wmg; + } else if (flags.contains("Exit")) { + weightRendezvousPoint *= wme; + } else { + weightRendezvousPoint *= wmm; + } + } + weightsRendezvousPoint.put(fingerprint, weightRendezvousPoint); + totalWeightsRendezvousPoint += weightRendezvousPoint; + } + /* Add all HSDir fingerprints with leading "0" and "1" to + * simplify the logic to traverse the ring start. */ + SortedSet<String> hsDirsCopy = new TreeSet<String>(hsDirs); + hsDirs.clear(); + for (String fingerprint : hsDirsCopy) { + hsDirs.add("0" + fingerprint); + hsDirs.add("1" + fingerprint); + } + final double RING_SIZE = new BigInteger( + "10000000000000000000000000000000000000000", + 16).doubleValue(); + for (String fingerprint : fingerprints) { + double probabilityRendezvousPoint = 0.0, + fractionResponsibleDescriptors = 0.0, + fractionConsensusWeight = 0.0; + NetworkStatusEntry statusEntry = + consensus.getStatusEntry(fingerprint); + if (statusEntry != null) { + if (hsDirs.contains("1" + fingerprint)) { + String startResponsible = fingerprint; + int positionsToGo = 3; + for (String hsDirFingerprint : + hsDirs.tailSet("1" + fingerprint)) { + startResponsible = hsDirFingerprint; + if (positionsToGo-- <= 0) { + break; + } + } + fractionResponsibleDescriptors = + new BigInteger("1" + fingerprint, 16).subtract( + new BigInteger(startResponsible, 16)).doubleValue() + / RING_SIZE; + } + fractionConsensusWeight = + ((double) statusEntry.getBandwidth()) + / ((double) totalConsensusWeight); + probabilityRendezvousPoint = + weightsRendezvousPoint.get(fingerprint) + / totalWeightsRendezvousPoint; + } + if (!extractedConsensusFractions.containsKey(fingerprint)) { + extractedConsensusFractions.put(fingerprint, + new TreeSet<ConsensusFraction>()); + } + extractedConsensusFractions.get(fingerprint).add( + new ConsensusFraction(consensus.getValidAfterMillis(), + consensus.getFreshUntilMillis(), fractionConsensusWeight, + probabilityRendezvousPoint, + fractionResponsibleDescriptors)); + } + } + } + return extractedConsensusFractions; + } + + private static void extrapolateHidServStats( + SortedMap<String, SortedSet<HidServStats>> hidServStats, + SortedMap<String, SortedSet<ConsensusFraction>> + consensusFractions) throws Exception { + hidservStatsCsvFile.getParentFile().mkdirs(); + BufferedWriter bw = new BufferedWriter( + new FileWriter(hidservStatsCsvFile)); + bw.write("fingerprint,stats_start,stats_end," + + "hidserv_rend_relayed_cells,hidserv_dir_onions_seen," + + "prob_rend_point,frac_hsdesc\n"); + for (Map.Entry<String, SortedSet<HidServStats>> e : + hidServStats.entrySet()) { + String fingerprint = e.getKey(); + if (!consensusFractions.containsKey(fingerprint)) { + System.err.println("We have hidserv-stats but no consensus " + + "fractions for " + fingerprint + ". Skipping."); + continue; + } + for (HidServStats stats : e.getValue()) { + long statsStartMillis = stats.statsEndMillis + - stats.statsIntervalSeconds * 1000L; + double sumProbabilityRendezvousPoint = 0.0, + sumResponsibleDescriptors = 0.0; + int statusEntries = 0; + for (ConsensusFraction frac : + consensusFractions.get(fingerprint)) { + if (statsStartMillis <= frac.validAfterMillis && + frac.validAfterMillis < stats.statsEndMillis) { + sumProbabilityRendezvousPoint += + frac.probabilityRendezvousPoint; + sumResponsibleDescriptors += + frac.fractionResponsibleDescriptors; + statusEntries++; + } + } + bw.write(String.format("%s,%s,%s,%d,%d,%.8f,%.8f%n", fingerprint, + DATE_TIME_FORMAT.format(statsStartMillis), + DATE_TIME_FORMAT.format(stats.statsEndMillis), + stats.rendRelayedCells, stats.dirOnionsSeen, + sumProbabilityRendezvousPoint / statusEntries, + sumResponsibleDescriptors / statusEntries)); + } + } + bw.close(); + } + + private static Random rnd = new Random(3); + + private static void simulateCells() throws Exception { + + /* Generate consensus weights following an exponential distribution + * with lambda = 1 for 3000 potential rendezvous points. */ + final int numberRendPoints = 3000; + double[] consensusWeights = new double[numberRendPoints]; + double totalConsensusWeight = 0.0; + for (int i = 0; i < numberRendPoints; i++) { + double consensusWeight = -Math.log(1.0 - rnd.nextDouble()); + consensusWeights[i] = consensusWeight; + totalConsensusWeight += consensusWeight; + } + + /* Compute probabilities for being selected as rendezvous point. */ + double[] probRendPoint = new double[numberRendPoints]; + for (int i = 0; i < numberRendPoints; i++) { + probRendPoint[i] = consensusWeights[i] / totalConsensusWeight; + } + + /* Generate 10,000,000,000 (roughly 60 MiB/s) cells in chunks + * following an exponential distribution with lambda = 0.00001 and + * randomly assign them to a rendezvous point to report them later. */ + long cellsLeft = 10000000000L; + final double cellsLambda = 0.00001; + long[] observedCells = new long[numberRendPoints]; + while (cellsLeft > 0) { + long cells = (long) (-Math.log(1.0 - rnd.nextDouble()) + / cellsLambda); + double selectRendPoint = rnd.nextDouble(); + for (int i = 0; i < probRendPoint.length; i++) { + selectRendPoint -= probRendPoint[i]; + if (selectRendPoint <= 0.0) { + observedCells[i] += cells; + break; + } + } + cellsLeft -= cells; + } + + /* Obfuscate reports using binning and Laplace noise, and then attempt + * to remove noise again. */ + final long binSize = 1024L; + final double b = 2048.0 / 0.3; + long[] reportedCells = new long[numberRendPoints]; + long[] removedNoiseCells = new long[numberRendPoints]; + for (int i = 0; i < numberRendPoints; i++) { + long observed = observedCells[i]; + long afterBinning = ((observed + binSize - 1L) / binSize) * binSize; + double p = rnd.nextDouble(); + double laplaceNoise = -b * (p > 0.5 ? 1.0 : -1.0) * + Math.log(1.0 - 2.0 * Math.abs(p - 0.5)); + long reported = afterBinning + (long) laplaceNoise; + reportedCells[i] = reported; + long roundedToNearestRightSideOfTheBin = + ((reported + binSize / 2) / binSize) * binSize; + long subtractedHalfOfBinSize = + roundedToNearestRightSideOfTheBin - binSize / 2; + removedNoiseCells[i] = subtractedHalfOfBinSize; + } + + /* Perform 10,000 extrapolations from random fractions of reports by + * probability to be selected as rendezvous point. */ + simCellsCsvFile.getParentFile().mkdirs(); + BufferedWriter bw = new BufferedWriter(new FileWriter( + simCellsCsvFile)); + bw.write("frac,p025,p500,p975\n"); + double[] fractions = new double[] { 0.01, 0.02, 0.03, 0.04, 0.05, 0.1, + 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.99 }; + final int numberOfExtrapolations = 10000; + for (double fraction : fractions) { + List<Long> extrapolations = new ArrayList<Long>(); + for (int i = 0; i < numberOfExtrapolations; i++) { + SortedSet<Integer> nonReportingRelays = new TreeSet<Integer>(); + for (int j = 0; j < numberRendPoints; j++) { + nonReportingRelays.add(j); + } + List<Integer> shuffledRelays = new ArrayList<Integer>( + nonReportingRelays); + Collections.shuffle(shuffledRelays); + SortedSet<Integer> reportingRelays = new TreeSet<Integer>(); + for (int j = 0; j < (int) ((double) numberRendPoints * fraction); + j++) { + reportingRelays.add(shuffledRelays.get(j)); + nonReportingRelays.remove(shuffledRelays.get(j)); + } + double reportingProbability; + long totalReports; + do { + reportingProbability = 0.0; + totalReports = 0L; + for (int reportingRelay : reportingRelays) { + reportingProbability += probRendPoint[reportingRelay]; + totalReports += removedNoiseCells[reportingRelay]; + } + if (reportingProbability < fraction - 0.001) { + int addRelay = new ArrayList<Integer>(nonReportingRelays).get( + rnd.nextInt(nonReportingRelays.size())); + nonReportingRelays.remove(addRelay); + reportingRelays.add(addRelay); + } else if (reportingProbability > fraction + 0.001) { + int removeRelay = new ArrayList<Integer>(reportingRelays).get( + rnd.nextInt(reportingRelays.size())); + reportingRelays.remove(removeRelay); + nonReportingRelays.add(removeRelay); + } + } while (reportingProbability < fraction - 0.001 || + reportingProbability > fraction + 0.001); + extrapolations.add((long) ((double) totalReports + / reportingProbability)); + } + Collections.sort(extrapolations); + long p025 = extrapolations.get((extrapolations.size() * 25) / 1000), + p500 = extrapolations.get((extrapolations.size() * 500) / 1000), + p975 = extrapolations.get((extrapolations.size() * 975) / 1000); + bw.write(String.format("%.2f,%d,%d,%d%n", fraction, p025, p500, + p975)); + } + bw.close(); + } + + private static void simulateOnions() throws Exception { + + /* Generate 3000 HSDirs with "fingerprints" between 0.0 and 1.0. */ + final int numberHsDirs = 3000; + SortedSet<Double> hsDirFingerprints = new TreeSet<Double>(); + for (int i = 0; i < numberHsDirs; i++) { + hsDirFingerprints.add(rnd.nextDouble()); + } + + /* Compute fractions of observed descriptor space. */ + SortedSet<Double> ring = + new TreeSet<Double>(Collections.reverseOrder()); + for (double fingerprint : hsDirFingerprints) { + ring.add(fingerprint); + ring.add(fingerprint - 1.0); + } + SortedMap<Double, Double> hsDirFractions = + new TreeMap<Double, Double>(); + for (double fingerprint : hsDirFingerprints) { + double start = fingerprint; + int positionsToGo = 3; + for (double prev : ring.tailSet(fingerprint)) { + start = prev; + if (positionsToGo-- <= 0) { + break; + } + } + hsDirFractions.put(fingerprint, fingerprint - start); + } + + /* Generate 40000 .onions with 4 HSDesc IDs, store them on HSDirs. */ + final int numberOnions = 40000; + final int replicas = 4; + final int storeOnDirs = 3; + SortedMap<Double, SortedSet<Integer>> storedDescs = + new TreeMap<Double, SortedSet<Integer>>(); + for (double fingerprint : hsDirFingerprints) { + storedDescs.put(fingerprint, new TreeSet<Integer>()); + } + for (int i = 0; i < numberOnions; i++) { + for (int j = 0; j < replicas; j++) { + int leftToStore = storeOnDirs; + for (double fingerprint : + hsDirFingerprints.tailSet(rnd.nextDouble())) { + storedDescs.get(fingerprint).add(i); + if (--leftToStore <= 0) { + break; + } + } + if (leftToStore > 0) { + for (double fingerprint : hsDirFingerprints) { + storedDescs.get(fingerprint).add(i); + if (--leftToStore <= 0) { + break; + } + } + } + } + } + + /* Obfuscate reports using binning and Laplace noise, and then attempt + * to remove noise again. */ + final long binSize = 8L; + final double b = 8.0 / 0.3; + SortedMap<Double, Long> reportedOnions = new TreeMap<Double, Long>(), + removedNoiseOnions = new TreeMap<Double, Long>(); + for (Map.Entry<Double, SortedSet<Integer>> e : + storedDescs.entrySet()) { + double fingerprint = e.getKey(); + long observed = (long) e.getValue().size(); + long afterBinning = ((observed + binSize - 1L) / binSize) * binSize; + double p = rnd.nextDouble(); + double laplaceNoise = -b * (p > 0.5 ? 1.0 : -1.0) * + Math.log(1.0 - 2.0 * Math.abs(p - 0.5)); + long reported = afterBinning + (long) laplaceNoise; + reportedOnions.put(fingerprint, reported); + long roundedToNearestRightSideOfTheBin = + ((reported + binSize / 2) / binSize) * binSize; + long subtractedHalfOfBinSize = + roundedToNearestRightSideOfTheBin - binSize / 2; + removedNoiseOnions.put(fingerprint, subtractedHalfOfBinSize); + } + + /* Perform 10,000 extrapolations from random fractions of reports by + * probability to be selected as rendezvous point. */ + simOnionsCsvFile.getParentFile().mkdirs(); + BufferedWriter bw = new BufferedWriter(new FileWriter( + simOnionsCsvFile)); + bw.write("frac,p025,p500,p975\n"); + double[] fractions = new double[] { 0.01, 0.02, 0.03, 0.04, 0.05, 0.1, + 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.99 }; + final int numberOfExtrapolations = 10000; + for (double fraction : fractions) { + List<Long> extrapolationsTwo = new ArrayList<Long>(); + for (int i = 0; i < numberOfExtrapolations; i++) { + SortedSet<Double> nonReportingRelays = + new TreeSet<Double>(hsDirFractions.keySet()); + List<Double> shuffledRelays = new ArrayList<Double>( + nonReportingRelays); + Collections.shuffle(shuffledRelays); + SortedSet<Double> reportingRelays = new TreeSet<Double>(); + for (int j = 0; j < (int) ((double) hsDirFractions.size() + * fraction); j++) { + reportingRelays.add(shuffledRelays.get(j)); + nonReportingRelays.remove(shuffledRelays.get(j)); + } + double reportingProbability; + long totalReports; + do { + reportingProbability = 0.0; + totalReports = 0L; + for (double reportingRelay : reportingRelays) { + reportingProbability += hsDirFractions.get(reportingRelay) + / 3.0; + totalReports += removedNoiseOnions.get(reportingRelay); + } + if (reportingProbability < fraction - 0.001) { + double addRelay = + new ArrayList<Double>(nonReportingRelays).get( + rnd.nextInt(nonReportingRelays.size())); + nonReportingRelays.remove(addRelay); + reportingRelays.add(addRelay); + } else if (reportingProbability > fraction + 0.001) { + double removeRelay = + new ArrayList<Double>(reportingRelays).get( + rnd.nextInt(reportingRelays.size())); + reportingRelays.remove(removeRelay); + nonReportingRelays.add(removeRelay); + } + } while (reportingProbability < fraction - 0.001 || + reportingProbability > fraction + 0.001); + double totalFraction = 0.0; + for (double fingerprint : reportingRelays) { + totalFraction += hsDirFractions.get(fingerprint) * 4.0; + } + extrapolationsTwo.add((long) ((double) totalReports + / totalFraction)); + } + Collections.sort(extrapolationsTwo); + long pTwo025 = extrapolationsTwo.get( + (extrapolationsTwo.size() * 25) / 1000), + pTwo500 = extrapolationsTwo.get( + (extrapolationsTwo.size() * 500) / 1000), + pTwo975 = extrapolationsTwo.get( + (extrapolationsTwo.size() * 975) / 1000); + bw.write(String.format("%.2f,%d,%d,%d%n", fraction, pTwo025, + pTwo500, pTwo975)); + } + bw.close(); + } +} +