commit 3c90c181a13dcc12c69e8e8fa013948b1a6405e2
Author: Karsten Loesing <karsten.loesing(a)gmx.net>
Date: Mon Feb 9 18:25:38 2015 +0100
Update hidserv-stats extrapolation code (#13192).
---
task-13192/.gitignore | 1 +
task-13192/src/R/blog.R | 47 ++
task-13192/src/R/plot.R | 214 +++----
task-13192/src/java/Aggregate.java | 129 ++++
task-13192/src/java/Extrapolate.java | 424 +++++++++++++
task-13192/src/java/ExtrapolateHidServStats.java | 722 ----------------------
task-13192/src/java/Simulate.java | 357 +++++++++++
7 files changed, 1066 insertions(+), 828 deletions(-)
diff --git a/task-13192/.gitignore b/task-13192/.gitignore
index 7e8bf3b..89d161b 100644
--- a/task-13192/.gitignore
+++ b/task-13192/.gitignore
@@ -4,4 +4,5 @@ in/
src/bash/
src/bin/
out/
+Rplots.pdf
diff --git a/task-13192/src/R/blog.R b/task-13192/src/R/blog.R
new file mode 100644
index 0000000..82a07e9
--- /dev/null
+++ b/task-13192/src/R/blog.R
@@ -0,0 +1,47 @@
+# 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)
+
+# Read .csv files written by Java.
+h <- read.csv("out/csv/hidserv-stats.csv", stringsAsFactors = FALSE)
+
+# Create directories for graphs.
+dir.create(file.path("out", "graphs", "blog"), 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/blog/num-reported-stats.png", width = 10, height = 3,
+ dpi = 100)
+
+e <- read.csv("out/csv/hidserv-stats-extrapolated.csv",
+ stringsAsFactors = FALSE)
+e <- melt(e, by = c("date", "type"))
+e <- e[e$variable == "wiqm", ]
+e <- rbind(e, data.frame(date = NA, type = c("onions", "cells"),
+ variable = NA, value = 0))
+
+ggplot(e[e$type == "cells", ], aes(x = as.Date(date), y = value)) +
+geom_line() +
+scale_x_date(name = "") +
+scale_y_continuous(name = "")
+ggsave("out/graphs/blog/extrapolated-cells.png", width = 10,
+ height = 3, dpi = 100)
+
+ggplot(e[e$type != "cells", ], aes(x = as.Date(date), y = value)) +
+geom_line() +
+scale_x_date(name = "") +
+scale_y_continuous(name = "")
+ggsave("out/graphs/blog/extrapolated-onions.png", width = 10,
+ height = 3, dpi = 100)
+
diff --git a/task-13192/src/R/plot.R b/task-13192/src/R/plot.R
index 991928b..552b810 100644
--- a/task-13192/src/R/plot.R
+++ b/task-13192/src/R/plot.R
@@ -5,17 +5,12 @@ 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), ]
@@ -28,17 +23,15 @@ 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),
+ traffic = h$hidserv_rend_relayed_cells * 512 * 8 / (86400 * 1e6),
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)
+ variable = ifelse(h1$variable == "traffic", "traffic in Mbit/s",
+ "unique .onion addresses"), value = h1$value)
ggplot(h1, aes(x = date, y = value, group = date)) +
geom_boxplot() +
facet_grid(variable ~ ., scales = "free_y") +
@@ -49,23 +42,22 @@ ggsave("out/graphs/report/stats-by-day.pdf", width = 10, height = 5,
# 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)
+ frac_rend_relayed_cells = h$frac_rend_relayed_cells, x_frac_dir_onions_seen = h$frac_dir_onions_seen)
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"),
+ variable = ifelse(h2$variable == "frac_rend_relayed_cells",
+ "cells on rendezvous circuits", "hidden-service descriptors"),
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)
+scale_y_continuous("Calculated network fractions\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,
+h8 <- h[h$frac_rend_relayed_cells == 0,
"hidserv_rend_relayed_cells" ]
h8 <- sort(h8)
h8 <- data.frame(x = h8, y = (1:length(h8)) / length(h8))
@@ -75,13 +67,14 @@ laplace_cells <- function(x) {
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")
+scale_x_continuous("\nReported cells on rendezvous circuits",
+ limits = c(max(h8[h8$y < 0.01, "x"]), min(h8[h8$y > 0.99, "x"]))) +
+scale_y_continuous("Cumulative probability\n", labels = percent)
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 <- h[h$frac_dir_onions_seen == 0, "hidserv_dir_onions_seen"]
h9 <- sort(h9)
h9 <- data.frame(x = h9, y = (1:length(h9)) / length(h9))
laplace_onions <- function(x) {
@@ -90,51 +83,54 @@ laplace_onions <- function(x) {
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")
+scale_x_continuous("\nReported .onion addresses",
+ limits = c(max(h9[h9$y < 0.01, "x"]), min(h9[h9$y > 0.99, "x"]))) +
+scale_y_continuous("Cumulative probability\n", labels = percent)
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),
+ data.frame(x = h$frac_dir_onions_seen,
+ y = ifelse(h$frac_dir_onions_seen == 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"))
+ data.frame(x = h$frac_rend_relayed_cells,
+ y = ifelse(h$frac_rend_relayed_cells == 0, NA,
+ h$hidserv_rend_relayed_cells * 512 * 8 / (86400 * 1e6)),
+ facet = "traffic in Mbit/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_x_continuous(name = "\nFraction", 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)) +
+ggplot(h3[h3$facet == "traffic in Mbit/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")
+scale_x_continuous(name = "\nFraction", labels = percent) +
+scale_y_continuous(name = "Reported traffic in Mbit/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),
+ prob = ifelse(h$frac_dir_onions_seen == 0, NA, h$frac_dir_onions_seen),
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"))
+ prob = ifelse(h$frac_rend_relayed_cells == 0, NA,
+ h$frac_rend_relayed_cells),
+ reported = h$hidserv_rend_relayed_cells * 512 * 8 / (86400 * 1e6),
+ facet = "traffic in Mbit/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)) +
+ggplot(h5[h5$facet == "traffic in Mbit/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") +
+scale_y_continuous(name = "Total traffic in Mbit/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,
@@ -149,98 +145,104 @@ geom_vline(xintercept = 0.01, linetype = 2)
ggsave("out/graphs/report/corr-probs-onions-by-day.pdf", width = 5,
height = 3, dpi = 100)
+# Graph ECDF of extrapolated cells.
+h20 <- h[h$frac_rend_relayed_cells > 0, ]
+h20 <- h20$hidserv_rend_relayed_cells *
+ 512 * 8 / (86400 * 1e6 * h20$frac_rend_relayed_cells)
+h20 <- sort(h20)
+h20 <- data.frame(x = h20, y = (1:length(h20)) / length(h20))
+ggplot(h20, aes(x = x, y = y)) +
+geom_line() +
+scale_x_continuous("\nExtrapolated total traffic in Mbit/s",
+ limits = c(max(h20[h20$y < 0.01, "x"]), min(h20[h20$y > 0.99, "x"]))) +
+scale_y_continuous("Cumulative probability\n", labels = percent)
+ggsave("out/graphs/report/extrapolated-cells.pdf", width = 5, height = 3,
+ dpi = 100)
+
+# Graph ECDF of extrapolated .onions.
+h21 <- h[h$frac_dir_onions_seen > 0, ]
+h21 <- h21$hidserv_dir_onions_seen / (12 * h21$frac_dir_onions_seen)
+h21 <- sort(h21)
+h21 <- data.frame(x = h21, y = (1:length(h21)) / length(h21))
+ggplot(h21, aes(x = x, y = y)) +
+geom_line() +
+scale_x_continuous("\nExtrapolated total .onion addresses",
+ limits = c(max(h21[h21$y < 0.01, "x"]), min(h21[h21$y > 0.99, "x"]))) +
+scale_y_continuous("Cumulative probability\n", labels = percent)
+ggsave("out/graphs/report/extrapolated-onions.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() +
+e <- read.csv("out/csv/hidserv-stats-extrapolated.csv",
+ stringsAsFactors = FALSE)
+e <- melt(e, by = c("date", "type"))
+e <- e[e$variable == "wiqm", ]
+e <- rbind(e, data.frame(date = NA, type = c("onions", "cells"),
+ variable = NA, value = 0))
+e <- data.frame(e, label = ifelse(e$type == "cells", "traffic in Mbit/s",
+ "unique .onion addresses"))
+ggplot(e, aes(x = as.Date(date), y = value)) +
+geom_line() +
+facet_grid(label ~ ., scales = "free_y") +
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,
+# Graph distributions of calculated fractions by day.
+h71 <- data.frame(date = as.Date(h$stats_end),
+ frac_rend_relayed_cells = h$frac_rend_relayed_cells,
+ frac_dir_onions_seen = h$frac_dir_onions_seen)
+summary(h71)
+h71 <- aggregate(list(
+ frac_rend_relayed_cells = h71$frac_rend_relayed_cells,
+ frac_dir_onions_seen = h71$frac_dir_onions_seen),
+ by = list(date = h71$date), FUN = sum)
+summary(h71)
+h71 <- melt(h71, "date")
+summary(h71)
+h71 <- data.frame(date = h71$date,
+ variable = ifelse(h71$variable == "frac_rend_relayed_cells",
+ "cells on rendezvous circuits", "hidden-service descriptors"),
+ value = h71$value)
+ggplot(h71, aes(x = date, y = value)) +
+geom_line() +
+facet_grid(variable ~ ., scales = "free_y") +
+geom_hline(yintercept = 0.01, linetype = 2) +
+scale_x_date("") +
+scale_y_continuous("Total calculated network fractions per day\n",
+ labels = percent)
+ggsave("out/graphs/report/probs-by-day.pdf", width = 10, height = 5,
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)) +
+s <- do.call(data.frame, aggregate(list(X = s$wiqm),
+ by = list(frac = s$frac), FUN = quantile, probs = c(0.025, 0.5, 0.975)))
+ggplot(s, aes(x = frac, y = (X.50. - 1e10) / 1e10,
+ ymin = (X.2.5. - 1e10) / 1e10, ymax = (X.97.5. - 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)
+scale_y_continuous("Deviation from actual\nhidden-service traffic\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)) +
+o <- do.call(data.frame, aggregate(list(X = o$wiqm),
+ by = list(frac = o$frac), FUN = quantile, probs = c(0.025, 0.5, 0.975)))
+ggplot(o, aes(x = frac, y = (X.50. / 12 - 40000) / 40000,
+ ymin = (X.2.5. / 12 - 40000) / 40000,
+ ymax = (X.97.5. / 12 - 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)
+scale_y_continuous("Deviation from actual\nnumber of .onions\n",
+ labels = percent)
ggsave("out/graphs/report/sim-onions.pdf", width = 5, height = 3,
dpi = 100)
diff --git a/task-13192/src/java/Aggregate.java b/task-13192/src/java/Aggregate.java
new file mode 100644
index 0000000..56bac2c
--- /dev/null
+++ b/task-13192/src/java/Aggregate.java
@@ -0,0 +1,129 @@
+import java.io.BufferedReader;
+import java.io.BufferedWriter;
+import java.io.File;
+import java.io.FileReader;
+import java.io.FileWriter;
+import java.text.DateFormat;
+import java.text.SimpleDateFormat;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+import java.util.Map;
+import java.util.SortedMap;
+import java.util.TimeZone;
+import java.util.TreeMap;
+
+public class Aggregate {
+
+ private static File hidservStatsCsvFile =
+ new File("out/csv/hidserv-stats.csv");
+
+ private static File hidservStatsExtrapolatedCsvFile =
+ new File("out/csv/hidserv-stats-extrapolated.csv");
+
+ public static void main(String[] args) throws Exception {
+ aggregate();
+ }
+
+ private static final DateFormat DATE_TIME_FORMAT, DATE_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"));
+ DATE_FORMAT = new SimpleDateFormat("yyyy-MM-dd");
+ DATE_FORMAT.setLenient(false);
+ DATE_FORMAT.setTimeZone(TimeZone.getTimeZone("UTC"));
+ }
+
+ private static void aggregate() throws Exception {
+ if (!hidservStatsCsvFile.exists() ||
+ hidservStatsCsvFile.isDirectory()) {
+ System.err.println("Unable to read "
+ + hidservStatsCsvFile.getAbsolutePath() + ". Exiting.");
+ System.exit(1);
+ }
+ SortedMap<String, List<double[]>>
+ extrapolatedCells = new TreeMap<String, List<double[]>>(),
+ extrapolatedOnions = new TreeMap<String, List<double[]>>();
+ BufferedReader br = new BufferedReader(new FileReader(
+ hidservStatsCsvFile));
+ String line = br.readLine();
+ while ((line = br.readLine()) != null) {
+ String[] parts = line.split(",");
+ String date = DATE_FORMAT.format(DATE_TIME_FORMAT.parse(parts[2]));
+ double hidservRendRelayedCells = Double.parseDouble(parts[3]),
+ hidservDirOnionsSeen = Double.parseDouble(parts[4]),
+ fracRendRelayedCells = Double.parseDouble(parts[5]),
+ fracDirOnionsSeen = Double.parseDouble(parts[6]);
+
+ if (fracRendRelayedCells > 0.0) {
+ if (!extrapolatedCells.containsKey(date)) {
+ extrapolatedCells.put(date, new ArrayList<double[]>());
+ }
+ extrapolatedCells.get(date).add(new double[] {
+ hidservRendRelayedCells * 512.0 * 8.0
+ / (86400.0 * 1000000.0 * fracRendRelayedCells),
+ fracRendRelayedCells });
+ }
+ if (fracDirOnionsSeen > 0.0) {
+ if (!extrapolatedOnions.containsKey(date)) {
+ extrapolatedOnions.put(date, new ArrayList<double[]>());
+ }
+ extrapolatedOnions.get(date).add(new double[] {
+ hidservDirOnionsSeen / (12.0 * fracDirOnionsSeen),
+ fracDirOnionsSeen });
+ }
+ }
+ br.close();
+ hidservStatsExtrapolatedCsvFile.getParentFile().mkdirs();
+ BufferedWriter bw = new BufferedWriter(new FileWriter(
+ hidservStatsExtrapolatedCsvFile));
+ bw.write("date,type,wmean,wmedian,wiqm\n");
+ for (int i = 0; i < 2; i++) {
+ String type = i == 0 ? "cells" : "onions";
+ SortedMap<String, List<double[]>> extrapolated = i == 0
+ ? extrapolatedCells : extrapolatedOnions;
+ for (Map.Entry<String, List<double[]>> e :
+ extrapolated.entrySet()) {
+ String date = e.getKey();
+ List<double[]> weightedValues = e.getValue();
+ double totalFrac = 0.0;
+ for (double[] d : weightedValues) {
+ totalFrac += d[1];
+ }
+ if (totalFrac < 0.01) {
+ continue;
+ }
+ Collections.sort(weightedValues,
+ new Comparator<double[]>() {
+ public int compare(double[] o1, double[] o2) {
+ return o1[0] < o2[0] ? -1 : o1[0] > o2[0] ? 1 : 0;
+ }
+ });
+ double totalWeighted = 0.0, totalProbability = 0.0;
+ double totalInterquartileFrac = 0.0,
+ totalWeightedInterquartile = 0.0;
+ Double weightedMedian = null;
+ for (double[] d : weightedValues) {
+ totalWeighted += d[0] * d[1];
+ totalProbability += d[1];
+ if (weightedMedian == null &&
+ totalProbability > totalFrac * 0.5) {
+ weightedMedian = d[0];
+ }
+ if (totalProbability >= totalFrac * 0.25 &&
+ totalProbability - d[1] <= totalFrac * 0.75) {
+ totalWeightedInterquartile += d[0] * d[1];
+ totalInterquartileFrac += d[1];
+ }
+ }
+ bw.write(String.format("%s,%s,%.0f,%.0f,%.0f%n", date, type,
+ totalWeighted / totalProbability, weightedMedian,
+ totalWeightedInterquartile / totalInterquartileFrac));
+ }
+ }
+ bw.close();
+ }
+}
diff --git a/task-13192/src/java/Extrapolate.java b/task-13192/src/java/Extrapolate.java
new file mode 100644
index 0000000..29ff518
--- /dev/null
+++ b/task-13192/src/java/Extrapolate.java
@@ -0,0 +1,424 @@
+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.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Date;
+import java.util.Iterator;
+import java.util.Map;
+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 Extrapolate {
+
+ 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");
+
+ 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(new Date() + " 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;
+
+ /* Probability for being selected by clients as rendezvous point. */
+ private double probabilityRendezvousPoint;
+
+ /* Probability for being selected as directory. This is the fraction
+ * of descriptors identifiers that this relay has been responsible
+ * for, divided by 3. */
+ private double fractionResponsibleDescriptors;
+
+ private ConsensusFraction(long validAfterMillis,
+ long freshUntilMillis,
+ double probabilityRendezvousPoint,
+ double fractionResponsibleDescriptors) {
+ this.validAfterMillis = validAfterMillis;
+ this.freshUntilMillis = freshUntilMillis;
+ 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.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());
+ 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());
+ }
+ 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,
+ fractionDescriptors = 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;
+ }
+ }
+ fractionDescriptors =
+ new BigInteger("1" + fingerprint, 16).subtract(
+ new BigInteger(startResponsible, 16)).doubleValue()
+ / RING_SIZE;
+ fractionDescriptors /= 3.0;
+ }
+ 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(), probabilityRendezvousPoint,
+ fractionDescriptors));
+ }
+ }
+ }
+ 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,"
+ + "frac_rend_relayed_cells,frac_dir_onions_seen\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++;
+ }
+ }
+ double fracCells = sumProbabilityRendezvousPoint / statusEntries,
+ fracDescs = sumResponsibleDescriptors / 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, fracCells,
+ fracDescs));
+ }
+ }
+ bw.close();
+ }
+}
+
diff --git a/task-13192/src/java/ExtrapolateHidServStats.java b/task-13192/src/java/ExtrapolateHidServStats.java
deleted file mode 100644
index 100520d..0000000
--- a/task-13192/src/java/ExtrapolateHidServStats.java
+++ /dev/null
@@ -1,722 +0,0 @@
-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();
- }
-}
-
diff --git a/task-13192/src/java/Simulate.java b/task-13192/src/java/Simulate.java
new file mode 100644
index 0000000..e41e02c
--- /dev/null
+++ b/task-13192/src/java/Simulate.java
@@ -0,0 +1,357 @@
+import java.io.BufferedWriter;
+import java.io.File;
+import java.io.FileWriter;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+import java.util.Map;
+import java.util.Random;
+import java.util.SortedMap;
+import java.util.SortedSet;
+import java.util.TreeMap;
+import java.util.TreeSet;
+
+
+public class Simulate {
+ 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.print("Simulating extrapolation of rendezvous cells");
+ simulateManyCells();
+ System.out.print("\nSimulating extrapolation of .onions");
+ simulateManyOnions();
+ System.out.println("\nTerminating.");
+ }
+
+ private static Random rnd = new Random();
+
+ private static void simulateManyCells() throws Exception {
+ simCellsCsvFile.getParentFile().mkdirs();
+ BufferedWriter bw = new BufferedWriter(new FileWriter(
+ simCellsCsvFile));
+ bw.write("run,frac,wmean,wmedian,wiqm\n");
+ final int numberOfExtrapolations = 1000;
+ for (int i = 0; i < numberOfExtrapolations; i++) {
+ bw.write(simulateCells(i));
+ System.out.print(".");
+ }
+ bw.close();
+ }
+
+ private static void simulateManyOnions() throws Exception {
+ simOnionsCsvFile.getParentFile().mkdirs();
+ BufferedWriter bw = new BufferedWriter(new FileWriter(
+ simOnionsCsvFile));
+ bw.write("run,frac,wmean,wmedian,wiqm\n");
+ final int numberOfExtrapolations = 1000;
+ for (int i = 0; i < numberOfExtrapolations; i++) {
+ bw.write(simulateOnions(i));
+ System.out.print(".");
+ }
+ bw.close();
+ }
+
+ private static String simulateCells(int run) {
+
+ /* 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 cells (474 Mbit/s) in chunks following an
+ * exponential distribution with lambda = 0.0001, so on average
+ * 10,000 cells per chunk, and randomly assign them to a rendezvous
+ * point to report them later. */
+ long cellsLeft = 10000000000L;
+ final double cellsLambda = 0.0001;
+ long[] observedCells = new long[numberRendPoints];
+ while (cellsLeft > 0) {
+ long cells = Math.min(cellsLeft,
+ (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 extrapolations from random fractions of reports by
+ * probability to be selected as rendezvous point. */
+ StringBuilder sb = new StringBuilder();
+ 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 };
+ for (double fraction : fractions) {
+ 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));
+ }
+ List<double[]> singleRelayExtrapolations;
+ double totalReportingProbability;
+ do {
+ singleRelayExtrapolations = new ArrayList<double[]>();
+ totalReportingProbability = 0.0;
+ for (int reportingRelay : reportingRelays) {
+ double probability = probRendPoint[reportingRelay];
+ if (probability > 0.0) {
+ singleRelayExtrapolations.add(
+ new double[] {
+ removedNoiseCells[reportingRelay] / probability,
+ removedNoiseCells[reportingRelay],
+ probability });
+ }
+ totalReportingProbability += probability;
+ }
+ if (totalReportingProbability < fraction - 0.001) {
+ int addRelay = new ArrayList<Integer>(nonReportingRelays).get(
+ rnd.nextInt(nonReportingRelays.size()));
+ nonReportingRelays.remove(addRelay);
+ reportingRelays.add(addRelay);
+ } else if (totalReportingProbability > fraction + 0.001) {
+ int removeRelay = new ArrayList<Integer>(reportingRelays).get(
+ rnd.nextInt(reportingRelays.size()));
+ reportingRelays.remove(removeRelay);
+ nonReportingRelays.add(removeRelay);
+ }
+ } while (totalReportingProbability < fraction - 0.001 ||
+ totalReportingProbability > fraction + 0.001);
+ Collections.sort(singleRelayExtrapolations,
+ new Comparator<double[]>() {
+ public int compare(double[] o1, double[] o2) {
+ return o1[0] < o2[0] ? -1 : o1[0] > o2[0] ? 1 : 0;
+ }
+ });
+ double totalProbability = 0.0, totalValues = 0.0;
+ double totalInterquartileProbability = 0.0,
+ totalInterquartileValues = 0.0;
+ Double weightedMedian = null;
+ for (double[] extrapolation : singleRelayExtrapolations) {
+ totalValues += extrapolation[1];
+ totalProbability += extrapolation[2];
+ if (weightedMedian == null &&
+ totalProbability > totalReportingProbability * 0.5) {
+ weightedMedian = extrapolation[0];
+ }
+ if (totalProbability > totalReportingProbability * 0.25 &&
+ totalProbability < totalReportingProbability * 0.75) {
+ totalInterquartileValues += extrapolation[1];
+ totalInterquartileProbability += extrapolation[2];
+ }
+ }
+ sb.append(String.format("%d,%.2f,%.0f,%.0f,%.0f%n", run, fraction,
+ totalValues / totalProbability, weightedMedian,
+ totalInterquartileValues / totalInterquartileProbability));
+ }
+ return sb.toString();
+ }
+
+ private static String simulateOnions(final int run) {
+
+ /* 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 extrapolations from random fractions of reports by
+ * probability to be selected as rendezvous point. */
+ StringBuilder sb = new StringBuilder();
+ 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 };
+ for (double fraction : fractions) {
+ 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));
+ }
+ List<double[]> singleRelayExtrapolations;
+ double totalReportingProbability;
+ do {
+ singleRelayExtrapolations = new ArrayList<double[]>();
+ totalReportingProbability = 0.0;
+ for (double reportingRelay : reportingRelays) {
+ double probability = hsDirFractions.get(reportingRelay) / 3.0;
+ if (probability > 0.0) {
+ singleRelayExtrapolations.add(
+ new double[] { removedNoiseOnions.get(reportingRelay)
+ / probability, removedNoiseOnions.get(reportingRelay),
+ probability });
+ }
+ totalReportingProbability += probability;
+ }
+ if (totalReportingProbability < fraction - 0.001) {
+ double addRelay =
+ new ArrayList<Double>(nonReportingRelays).get(
+ rnd.nextInt(nonReportingRelays.size()));
+ nonReportingRelays.remove(addRelay);
+ reportingRelays.add(addRelay);
+ } else if (totalReportingProbability > fraction + 0.001) {
+ double removeRelay =
+ new ArrayList<Double>(reportingRelays).get(
+ rnd.nextInt(reportingRelays.size()));
+ reportingRelays.remove(removeRelay);
+ nonReportingRelays.add(removeRelay);
+ }
+ } while (totalReportingProbability < fraction - 0.001 ||
+ totalReportingProbability > fraction + 0.001);
+ Collections.sort(singleRelayExtrapolations,
+ new Comparator<double[]>() {
+ public int compare(double[] o1, double[] o2) {
+ return o1[0] < o2[0] ? -1 : o1[0] > o2[0] ? 1 : 0;
+ }
+ });
+ double totalProbability = 0.0, totalValues = 0.0;
+ double totalInterquartileProbability = 0.0,
+ totalInterquartileValues = 0.0;
+ Double weightedMedian = null;
+ for (double[] extrapolation : singleRelayExtrapolations) {
+ totalValues += extrapolation[1];
+ totalProbability += extrapolation[2];
+ if (weightedMedian == null &&
+ totalProbability > totalReportingProbability * 0.5) {
+ weightedMedian = extrapolation[0];
+ }
+ if (totalProbability > totalReportingProbability * 0.25 &&
+ totalProbability < totalReportingProbability * 0.75) {
+ totalInterquartileValues += extrapolation[1];
+ totalInterquartileProbability += extrapolation[2];
+ }
+ }
+ sb.append(String.format("%d,%.2f,%.0f,%.0f,%.0f%n", run, fraction,
+ totalValues / totalProbability, weightedMedian,
+ totalInterquartileValues / totalInterquartileProbability));
+ }
+ return sb.toString();
+ }
+}
