commit f0365f4feb85ef66a55c308d3b46baea32e241b5
Author: Mike Perry <mikeperry-git(a)fscked.org>
Date: Sat Jun 16 15:06:51 2012 -0700
Analyze a multidimensional surface? No problem! I rollerskate on that shit.
This commit provides analysis to guide parameter choices for the path bias
defense. It contains a standalone attack and defense simulation script, a
results.txt with example output, and an observations.txt with comments to
help work towards an answer for #6135.
---
CircuitAnalysis/PathBias/observations.txt | 40 ++
CircuitAnalysis/PathBias/path_bias.py | 554 +++++++++++++++++++++++++++++
CircuitAnalysis/PathBias/results.txt | 152 ++++++++
3 files changed, 746 insertions(+), 0 deletions(-)
diff --git a/CircuitAnalysis/PathBias/observations.txt b/CircuitAnalysis/PathBias/observations.txt
new file mode 100644
index 0000000..c283bbd
--- /dev/null
+++ b/CircuitAnalysis/PathBias/observations.txt
@@ -0,0 +1,40 @@
+Analysis summary:
+
+1. Simulation confirms the raccoon's proof: Under a path bias attack with a
+ 100% accurate correlator, P(compromise) = c/n, where c is the amount of
+ capacity the path bias adversary *actually* carries. (This may be difficult
+ to achieve in practice, since you're actively rejecting capacity during the
+ attack, but PID feedback with the bw auths would fix that for you).
+
+3. With or without the defense, simply trying to fail less than PATH_BIAS_PCT
+ of your circuits is not substantially different than failing everything you
+ want. With the defense, your overall network-wide rate of compromise
+ doesn't change. The only thing that changes is the likelihood of getting
+ caught, and the number of circuits you get to observe per client.
+
+4. Against the defense, an adversary with full knowledge of the client's
+ current path bias parameter values can expect to evade detection, yet
+ still achieve:
+ P(compromise) <= (c/n)^2 * (100/PATH_BIAS_PCT)
+ circs_per_client <= circuit_attempts*(c/n)
+
+5. An adversary conducting a probabilistic attack of failing less than
+ PATH_BIAS_PCT of circuits in the long run can achieve similar, but
+ slightly lower bounds.
+
+
+Optimization problem:
+Tradeoff a large spread between PATH_BIAS_PCT and the ambient success rate vs
+a large MIN_CIRCS rate. Need to measure ambient success rate to do this.
+
+Other Questions:
+Can the adversary really track a client's current count values? Can we
+prevent this with randomization?
+
+Action items/Conclusions:
+Parameter choice seems to be blocked on getting a good measure of the ambient
+success rate, however the following immediate conclusions seem clear:
+
+1. We should transform SCALE_FACTOR into a percent, and make it high. Like 95.
+2. We might want to use a separate, lower PATH_BIAS_PCT before SCALE_THRESHOLD.
+3. After SCALE_THRESHOLD, PATH_BIAS_PCT can be pretty high for notice and warn
diff --git a/CircuitAnalysis/PathBias/path_bias.py b/CircuitAnalysis/PathBias/path_bias.py
new file mode 100755
index 0000000..621e2c1
--- /dev/null
+++ b/CircuitAnalysis/PathBias/path_bias.py
@@ -0,0 +1,554 @@
+#!/usr/bin/python
+
+import random
+
+# TODO:
+# Q: What quantity of middle bandwidth do you need to kill guards?
+# A: Intuitively, you need the disable rate % of bandwidth, but you
+# might have some edge cases to exploit with min_circs.
+
+PATH_BIAS_PCT = 70
+
+# XXX: Min_circs only actives the "notice" level logs
+PATH_BIAS_MIN_CIRCS = 20
+
+# XXX: An int divisor was wrong here. Fix that in Tor. We might
+# even want a weighted moving average, but that will be trickier
+# to analyze.
+PATH_BIAS_SCALE_FACTOR = 95
+PATH_BIAS_SCALE_THRESHOLD = 250
+
+# XXX: We should only emit warnings if we are above the scaling threshhold..
+PATH_BIAS_WARN_CIRCS = PATH_BIAS_SCALE_THRESHOLD*(PATH_BIAS_SCALE_FACTOR/100.0)
+
+#############################################################
+
+# FIXME: haxxx. Who cares, though?
+def reset_globals():
+ global PATH_BIAS_PCT
+ global PATH_BIAS_MIN_CIRCS
+ global PATH_BIAS_SCALE_FACTOR
+ global PATH_BIAS_SCALE_THRESHOLD
+ global PATH_BIAS_WARN_CIRCS
+
+ PATH_BIAS_PCT = 70
+ PATH_BIAS_MIN_CIRCS = 20
+ PATH_BIAS_SCALE_FACTOR = 95
+ PATH_BIAS_SCALE_THRESHOLD = 250
+ PATH_BIAS_WARN_CIRCS = PATH_BIAS_SCALE_THRESHOLD*(PATH_BIAS_SCALE_FACTOR/100.0)
+
+
+####################### Guard Types #########################
+
+# Normal Guard experiences the average circuit failure rate
+# of the network as a whole
+class Guard:
+ def __init__(self, succeed_rate):
+ self.first_hops_total = 0
+ self.success_total = 0
+
+ self._first_hops = 0
+ self._success = 0
+ self.succeed_rate = succeed_rate
+ self.rejected_count = 0
+
+ def reset(self):
+ self._success = 0
+ self._first_hops = 0
+
+ def reject_if_bad(self):
+ if self.is_bad():
+ self.reset()
+ self.rejected_count += 1
+
+ def reject_rate(self):
+ return self.rejected_count/float(self.first_hops_total)
+
+ def _get_rate(self):
+ return self._success/float(self._first_hops)
+
+ def is_bad(self):
+ return self._first_hops >= PATH_BIAS_MIN_CIRCS and \
+ (self._get_rate() < (PATH_BIAS_PCT/100.0))
+
+ def build_circuit(self):
+ self._inc_first_hop()
+ if random.random() < self.succeed_rate:
+ self._inc_success()
+
+ # Client may give up on us after this circuit
+ self.reject_if_bad()
+
+ def circ_fail_count(self):
+ return self._first_hops - self._success
+
+ def _inc_first_hop(self):
+ self._first_hops += 1
+ self.first_hops_total += 1
+ if self._first_hops > PATH_BIAS_SCALE_THRESHOLD:
+ self._first_hops *= PATH_BIAS_SCALE_FACTOR/100.0
+ self._success *= PATH_BIAS_SCALE_FACTOR/100.0
+
+ def _inc_success(self):
+ self._success += 1
+ self.success_total += 1
+
+# EvilGuard collects statistics on how evil he is, but doesn't
+# actually implement any evilness
+class EvilGuard(Guard):
+ def __init__(self, succeed_rate, adversary_capacity):
+ Guard.__init__(self, succeed_rate)
+ self.adversary_capacity = adversary_capacity # c/n probability of malicious exit
+ self.capture_count = 0
+
+ def pwnt_per_client(self):
+ return self.capture_count/float(self.rejected_count+1)
+
+ def capture_rate(self):
+ return self.capture_count/float(self.first_hops_total)
+
+ def compromise_rate(self):
+ return self.capture_count/float(self.success_total)
+
+# PassiveEvilGuard uses a non-destructive long-term timing-based
+# tagging attack to fully correlate circuits end-to-end with 100%
+# accuracy. PassiveEvilGuard does not kill any circuits.
+class PassiveEvilGuard(EvilGuard):
+ def __init__(self, succeed_rate, adversary_capacity):
+ EvilGuard.__init__(self, succeed_rate, adversary_capacity)
+
+ def build_circuit(self):
+ self._inc_first_hop()
+
+ # The presence of a malicious exit is a prior probability governed by the
+ # client. Decide it now.
+ got_malicious_exit = False
+ if random.random() < self.adversary_capacity:
+ got_malicious_exit = True
+
+ if random.random() < self.succeed_rate:
+ if got_malicious_exit: # via timing-based tagging attack
+ self._inc_success()
+ self.capture_count += 1
+ else:
+ self._inc_success() # "Better luck next time :/"
+
+ # Client may give up on us after this circuit
+ self.reject_if_bad()
+
+# UnrepentantEvilGuard uses a destructive tagging attack to
+# fully correlate circuits end-to-end with 100%
+# accuracy, as well as to kill uncorrelated circuits.
+#
+# UnrepentantEvilGuard doesn't care if there is a defense or
+# not.
+class UnrepentantEvilGuard(EvilGuard):
+ def __init__(self, succeed_rate, adversary_capacity):
+ EvilGuard.__init__(self, succeed_rate, adversary_capacity)
+
+ def build_circuit(self):
+ self._inc_first_hop()
+
+ # The presence of a malicious exit is a prior probability governed by the
+ # client. Decide it now.
+ got_malicious_exit = False
+ if random.random() < self.adversary_capacity:
+ got_malicious_exit = True
+
+ if random.random() < self.succeed_rate:
+ if got_malicious_exit: # via tagging attack
+ self._inc_success()
+ self.capture_count += 1
+ else:
+ pass # "We can't deanon it? Who cares then?"
+
+ # Client may give up on us after this circuit
+ self.reject_if_bad()
+
+# OmniscientEvilGuard is the worst-case adversary against
+# the path bias counters implemented in Tor 0.2.3.17.
+#
+# OmniscientEvilGuard knows client path counts, when they are about to
+# think it's bad, and when they scale, and tries to use all of these
+# to fail what it can to bias client paths without appearing bad to
+# them.
+#
+# Further in favor of the adversary, we assume that their circuit
+# failure rate is actually less than the network average by
+# the fraction of the network that they control (because the rest
+# of the network experiences this circuit failure as part of the
+# average failure).
+#
+# Further still, OmnscientEvilGuard is *so* omnsicient, it even knows
+# when circuits will fail due to ambient noise, so it never gets
+# killed by chance. (It is debatable how much this helps.. a
+# smart adversary could play the stats close enough to the line
+# to approach this omniscience asymptotically).
+#
+# Note: These omniscience assumptions all favor the attacker,
+# but they also simplify analysis to get worst-case bounds easily.
+#
+# XXX: Introducing some fuzz into our scaling count and/or rate might
+# help remove this exact omniscience in practice?
+class OmniscientEvilGuard(EvilGuard):
+ def __init__(self, succeed_rate, adversary_capacity):
+ EvilGuard.__init__(self, succeed_rate, adversary_capacity)
+
+ def look_ahead(self, n):
+ self.prev_first_hops = self._first_hops
+ self.prev_success = self._success
+ self.prev_first_hops_total = self.first_hops_total
+ self.prev_success_total = self.success_total
+ for i in xrange(n):
+ self._inc_first_hop()
+
+ def stop_looking(self):
+ self._first_hops = self.prev_first_hops
+ self._success = self.prev_success
+ self.first_hops_total = self.prev_first_hops_total
+ self.success_total = self.prev_success_total
+
+ # This guard should never get caught
+ def reject_if_bad(self):
+ assert not self.is_bad()
+
+ def build_circuit(self):
+ self._inc_first_hop()
+
+ # The presence of a malicious exit is a prior probability governed by the
+ # client. Decide it now.
+ got_malicious_exit = False
+ if random.random() < self.adversary_capacity:
+ got_malicious_exit = True
+
+ # In reality, OmniscientEvilGuard sees less failure because some
+ # of the failure in the network is due to other colluding nodes.
+ #if random.random() < self.succeed_rate + self.adversary_capacity:
+ #
+ # Note: We cut this out, because it favors the attacker to do so.
+ # It removes the risk of elimination by chance (which they could mitigate
+ # for an unknown but possibly small cost).
+ if True:
+ if got_malicious_exit: # via tagging attack
+ self.capture_count += 1
+ self._inc_success() # "We built a circuit! Yay!"
+ else:
+ # Look-ahead only needs to be non-zero to mitigate risk of random rejection
+ self.look_ahead(0)
+ if (self._get_rate() <= (PATH_BIAS_PCT/100.0)):
+ self.stop_looking()
+ self._inc_success() # "I better be good! don't want to get caught.."
+ else:
+ pass # Fail the circuit by doing nothing. It's not useful
+
+ # Client may give up on us after this circuit
+ self.reject_if_bad()
+
+# ProbabalisticEvilGuard only fails untagged circuits pct_below_path_bias
+# below the warning rate
+class ProbabalisticEvilGuard(EvilGuard):
+ def __init__(self, succeed_rate, adversary_capacity, pct_below_path_bias):
+ EvilGuard.__init__(self, succeed_rate, adversary_capacity)
+ # FIXME: There may be an optimal point where pct_below_path_bias
+ # is the lowest possible value that the adversary expects to control?
+ # Doesn't seem to be worth probing, though
+ self.path_bias_rate = (PATH_BIAS_PCT - pct_below_path_bias)/100.0
+ assert self.path_bias_rate <= 1.0
+
+ def build_circuit(self):
+ self._inc_first_hop()
+
+ # The presence of a malicious exit is a prior probability governed by the
+ # client. Decide it now.
+ got_malicious_exit = False
+ if random.random() < self.adversary_capacity:
+ got_malicious_exit = True
+
+ # ProbabalisticGamingGuard sees less failure because some
+ # of the failure in the network is due to other colluding nodes.
+ if random.random() < self.succeed_rate + self.adversary_capacity:
+ if got_malicious_exit: # via tagging attack
+ self._inc_success()
+ self.capture_count += 1
+ elif not self.success_total or \
+ self.success_total/float(self.first_hops_total) <= self.path_bias_rate:
+ # "Uh oh, we're failing too much, better let some through"
+ self._inc_success()
+ else:
+ pass # Fail the circuit by doing nothing. It's not useful
+
+ # Client may give up on us after this circuit
+ self.reject_if_bad()
+
+####################### Testing and Simulation #########################
+
+def simulate_circs_until(g, circ_count, say_when):
+ for i in xrange(circ_count):
+ g.build_circuit()
+ if say_when(g):
+ return True
+
+ return say_when(g)
+
+# Variables:
+# success_rate
+# PATH_BIAS_MIN_CIRCS = 20
+# PATH_BIAS_PCT = 70
+def notice_false_positive_test(trials, success_rate, min_circs, path_bias_pct):
+ # FIXME: Look it's just easier this way, ok? Get off my back already
+ global PATH_BIAS_MIN_CIRCS
+ global PATH_BIAS_PCT
+ PATH_BIAS_MIN_CIRCS = min_circs
+ PATH_BIAS_PCT = path_bias_pct
+
+ g = Guard(success_rate)
+
+ for i in xrange(1+trials/min_circs):
+ simulate_circs_until(g, PATH_BIAS_SCALE_THRESHOLD, lambda g: False)
+ g.reset()
+
+ #print g._get_rate()
+
+ return g.reject_rate()
+
+def reject_false_positive_test(trials, success_rate, scale_circs, path_bias_pct):
+ # FIXME: Look it's just easier this way, ok? Get off my back already
+ global PATH_BIAS_MIN_CIRCS
+ global PATH_BIAS_SCALE_THRESHOLD
+ global PATH_BIAS_PCT
+ PATH_BIAS_SCALE_THRESHOLD = scale_circs
+ PATH_BIAS_PCT = path_bias_pct
+
+ g = Guard(success_rate)
+
+ # Ignore startup. We don't reject then.
+ simulate_circs_until(g, PATH_BIAS_SCALE_THRESHOLD, lambda g: False)
+ g.rejected_count = 0
+
+ simulate_circs_until(g, trials, lambda g: False)
+
+ #print g._get_rate()
+
+ return g.reject_rate()
+
+def generic_rate_test(g, trials, success_rate, adversary_capacity, path_bias_pct, rate_fcn):
+ # FIXME: Look it's just easier this way, ok? Get off my back already
+ global PATH_BIAS_PCT
+ PATH_BIAS_PCT = path_bias_pct
+
+ simulate_circs_until(g, trials, lambda g: False)
+
+ if not isinstance(g, UnrepentantEvilGuard):
+ assert not g.is_bad()
+
+ return rate_fcn(g)
+
+################ Multi-Dementianal Analysis #####################
+
+# If brute force doesn't work, you're not using enough
+def brute_force(cmptr, functor, ranges, increment):
+ testpoint = map(lambda p: p[0], ranges)
+ maxpoint = testpoint
+ maxval = functor(*testpoint)
+
+ print "New extrema at "+str(maxpoint)+": "+str(maxval)
+
+ for dementia in xrange(len(ranges)):
+ if increment[dementia] > 0:
+ cmpr = lambda x, y: x<y
+ else:
+ cmpr = lambda x, y: x>y
+
+ value = ranges[dementia][0]
+ while cmpr(value, ranges[dementia][1]):
+ value += increment[dementia]
+ testpoint[dementia] = value
+ val = functor(*testpoint)
+ if cmptr(val, maxval):
+ maxval = val
+ maxpoint = testpoint
+ print "New extrema at "+str(maxpoint)+": "+str(maxval)
+
+ # FIXME: Haxx
+ reset_globals()
+
+ return maxpoint
+
+
+def surface_plot(functor, startpoint, ranges, increment):
+ pass
+
+def gradient_descent(functor, startpoint, ranges, increment):
+ # Warning, mentat: If brute force doesn't work, you're not using enough
+ # It might be wise to try to get a 3d color plot/heatmap/some other
+ # visualization before attempting this?
+ pass
+
+def main():
+ #random.seed(23)
+
+ if True:
+ print "==================== P(Compromise|Guard) =========================="
+
+ print "\nPassiveEvilGuard compromise rate at [success_rate, adversary_capacity, path_bias_pct]:"
+ print "(As expected, P(CompromisedExit|PassiveEvilGuard) ~= c/n)"
+ print brute_force(lambda x,y: x>y,
+ lambda t, a,b,c:
+ generic_rate_test(PassiveEvilGuard(a,b), t, a,b,c,
+ lambda g:
+ g.compromise_rate()),
+ #generic_rate_test(trials, success_rate, adversary_capacity, path_bias_pct):
+ [(10000,10000), (0.75,0.75), (0.05,0.85), (70, 70)],
+ [0, 0, 0.2, 5])
+
+
+ print "\nUnrepentantEvilGuard compromise rate at [success_rate, adversary_capacity, path_bias_pct]:"
+ print "(As expected, P(CompromisedExit|UnrepentantEvilGuard) = 1.0)"
+ print brute_force(lambda x,y: x>y,
+ lambda t,a,b,c:
+ generic_rate_test(UnrepentantEvilGuard(a,b), t,a,b,c,
+ lambda g:
+ g.compromise_rate()),
+ #generic_rate_test(trials, success_rate, adversary_capacity, path_bias_pct):
+ [(10000,10000), (0.75,0.75), (0.05,0.85), (70, 70)],
+ [0, 0, 0.2, 5])
+
+ print "\nProbabalisticEvilGuard compromise rate at [success_rate, adversary_capacity, path_bias_pct]:"
+ print "P(CompromisedExit|ProbabalisticEvilGuard) <= (c/n)*(100/PATH_BIAS_PCT)"
+ print brute_force(lambda x,y: x>y,
+ lambda t,a,b,c:
+ generic_rate_test(ProbabalisticEvilGuard(a,b,5),
+ t,a,b,c,
+ lambda g:
+ g.compromise_rate()),
+ #generic_rate_test(trials, success_rate, adversary_capacity, path_bias_pct):
+ [(10000,10000), (0.75,0.75), (0.05,0.85), (70, 70)],
+ [0, 0, 0.2, 5])
+
+ print "\nOmniscientEvilGuard compromise rate at [success_rate, adversary_capacity, path_bias_pct]:"
+ print "P(CompromisedExit|OmniscientEvilGuard) <= (c/n)*(100/PATH_BIAS_PCT)"
+ print brute_force(lambda x,y: x>y,
+ lambda t,a,b,c:
+ generic_rate_test(OmniscientEvilGuard(a,b), t,a,b,c,
+ lambda g:
+ g.compromise_rate()),
+ #generic_rate_test(trials, success_rate, adversary_capacity, path_bias_pct):
+ [(10000,10000), (0.75,0.75), (0.05,0.85), (70, 70)],
+ [0, 0, 0.2, 5])
+
+ print "\nOmniscientEvilGuard compromise at [success_rate, adversary_capacity, path_bias_pct]:"
+ print "P(CompromisedExit|OmniscientEvilGuard) <= (c/n)*(100/PATH_BIAS_PCT)"
+ print brute_force(lambda x,y: x<y,
+ lambda t,a,b,c:
+ generic_rate_test(OmniscientEvilGuard(a,b), t,a,b,c,
+ lambda g:
+ g.compromise_rate()),
+ #generic_rate_test(trials, success_rate, adversary_capacity, path_bias_pct):
+ [(10000,10000), (0.75,0.75), (0.20,0.20), (20, 80)],
+ [0, 0, 0.05, 20])
+
+ if True:
+ print "\n\n==================== Circuits pwnt per client ========================="
+
+ print "\nUnrepentantEvilGuard compromised circs at [success_rate, adversary_capacity, path_bias_pct]:"
+ print "circs_per_client ~= success_rate*c/n*MIN_CIRCS for c/n < PATH_BIAS_PCT || c/n < success_rate"
+ print " ~= success_rate*circ_attempts*c/n for c/n > PATH_BIAS_PCT && c/n > success_rate"
+ print brute_force(lambda x,y: x>y,
+ lambda t,a,b,c:
+ generic_rate_test(UnrepentantEvilGuard(a,b), t,a,b,c,
+ lambda g:
+ g.pwnt_per_client()),
+ #generic_rate_test(trials, success_rate, adversary_capacity, path_bias_pct):
+ [(100000,100000), (0.75,0.75), (0.05,0.85), (50, 50)],
+ [0, 0, 0.2, 5])
+
+ print "\nPassiveEvilGuard compromised circs at [success_rate, adversary_capacity, path_bias_pct]:"
+ print "circs_per_client ~= success_rate * circ_attempts * c/n"
+ print brute_force(lambda x,y: x>y,
+ lambda t,a,b,c:
+ generic_rate_test(PassiveEvilGuard(a,b),
+ t,a,b,c,
+ lambda g:
+ g.pwnt_per_client()),
+ #generic_rate_test(trials, success_rate, adversary_capacity, path_bias_pct):
+ [(100000,100000), (0.75,0.75), (0.05,0.85), (50, 50)],
+ [0, 0, 0.2, 5])
+
+ print "\nProbabalisticEvilGuard compromised circs at [success_rate, adversary_capacity, path_bias_pct]:"
+ print "circs_per_client ~= success_rate * circ_attempts * c/n"
+ print brute_force(lambda x,y: x>y,
+ lambda t,a,b,c:
+ generic_rate_test(ProbabalisticEvilGuard(a,b,5),
+ t,a,b,c,
+ lambda g:
+ g.pwnt_per_client()),
+ #generic_rate_test(trials, success_rate, adversary_capacity, path_bias_pct):
+ [(100000,100000), (0.75,0.75), (0.05,0.85), (50, 50)],
+ [0, 0, 0.2, 5])
+
+ print "\nOmniscientEvilGuard compromised circs at [success_rate, adversary_capacity, path_bias_pct]:"
+ print "circs_per_client ~= circ_attempts * c/n"
+ print brute_force(lambda x,y: x>y,
+ lambda t,a,b,c:
+ generic_rate_test(OmniscientEvilGuard(a,b), t,a,b,c,
+ lambda g:
+ g.pwnt_per_client()),
+ #generic_rate_test(trials, success_rate, adversary_capacity, path_bias_pct):
+ [(100000,100000), (0.75,0.75), (0.05,0.85), (50, 50)],
+ [0, 0, 0.2, 5])
+
+
+ if True:
+ print "\n\n===================== FALSE POSITIVES ============================"
+
+ print "\nNotice false positive rates at [trials, success_rate, min_circs, path_bias_pct]:"
+ print "(Results are some function of success_rate - path_bias_pct vs min_circs)"
+ print brute_force(lambda x,y: x<y,
+ notice_false_positive_test,
+ #false_positive_test(trials, success_rate, min_circs, path_bias_pct):
+ [(100000,100000), (0.65, 0.65), (50,250), (70, 70)],
+ [0, -0.1, 50, 5])
+
+ print "\nNotice false positive rates at [trials, success_rate, min_circs, path_bias_pct]:"
+ print "(Results are some function of success_rate - path_bias_pct vs min_circs)"
+ print brute_force(lambda x,y: x<y,
+ notice_false_positive_test,
+ #false_positive_test(trials, success_rate, min_circs, path_bias_pct):
+ [(100000,100000), (0.70, 0.70), (50,500), (70, 70)],
+ [0, -0.1, 50, 5])
+
+ print "\nNotice false positives at [trials, success_rate, min_circs, path_bias_pct]:"
+ print "(Results are some function of success_rate - path_bias_pct vs min_circs)"
+ print brute_force(lambda x,y: x<y,
+ notice_false_positive_test,
+ #false_positive_test(trials, success_rate, min_circs, path_bias_pct):
+ [(100000,100000), (0.75, 0.75), (20,400), (70, 70)],
+ [0, -0.1, 20, 5])
+
+ print "\nReject false positive rates at [trials, success_rate, scale_circs, path_bias_pct]:"
+ print "(Results are some function of success_rate - path_bias_pct vs scale_circs)"
+ print brute_force(lambda x,y: x<y,
+ reject_false_positive_test,
+ #false_positive_test(trials, success_rate, scale_circs, path_bias_pct):
+ [(1000000,1000000), (0.65, 0.65), (50,250), (70, 70)],
+ [0, -0.1, 50, 5])
+
+ print "\nReject false positive rates at [trials, success_rate, scale_circs, path_bias_pct]:"
+ print "(Results are some function of success_rate - path_bias_pct vs scale_circs)"
+ print brute_force(lambda x,y: x<y,
+ reject_false_positive_test,
+ #false_positive_test(trials, success_rate, scale_circs, path_bias_pct):
+ [(1000000,1000000), (0.70, 0.70), (50,500), (70, 70)],
+ [0, -0.1, 50, 5])
+
+ print "\nReject false positive rates at [trials, success_rate, scale_circs, path_bias_pct]:"
+ print "(Results are some function of success_rate - path_bias_pct vs scale_circs)"
+ print brute_force(lambda x,y: x<y,
+ reject_false_positive_test,
+ #false_positive_test(trials, success_rate, scale_circs, path_bias_pct):
+ [(1000000,1000000), (0.75, 0.75), (50,500), (70, 70)],
+ [0, -0.1, 50, 5])
+
+
+if __name__ == "__main__":
+ main() #sys.argv)
diff --git a/CircuitAnalysis/PathBias/results.txt b/CircuitAnalysis/PathBias/results.txt
new file mode 100644
index 0000000..4293851
--- /dev/null
+++ b/CircuitAnalysis/PathBias/results.txt
@@ -0,0 +1,152 @@
+==================== P(Compromise|Guard) ==========================
+
+PassiveEvilGuard compromise rate at [success_rate, adversary_capacity, path_bias_pct]:
+(As expected, P(CompromisedExit|PassiveEvilGuard) ~= c/n)
+New extrema at [10000, 0.75, 0.05, 70]: 0.052610548748
+New extrema at [10000, 0.75, 0.25, 70]: 0.250574712644
+New extrema at [10000, 0.75, 0.45, 70]: 0.455518836748
+New extrema at [10000, 0.75, 0.65, 70]: 0.64692513369
+New extrema at [10000, 0.75, 0.8500000000000001, 70]: 0.851249664069
+[10000, 0.75, 0.8500000000000001, 70]
+
+UnrepentantEvilGuard compromise rate at [success_rate, adversary_capacity, path_bias_pct]:
+(As expected, P(CompromisedExit|UnrepentantEvilGuard) = 1.0)
+New extrema at [10000, 0.75, 0.05, 70]: 1.0
+[10000, 0.75, 0.8500000000000001, 70]
+
+ProbabalisticEvilGuard compromise rate at [success_rate, adversary_capacity, path_bias_pct]:
+P(CompromisedExit|ProbabalisticEvilGuard) <= (c/n)*(100/PATH_BIAS_PCT)
+New extrema at [10000, 0.75, 0.05, 70]: 0.0615289955391
+New extrema at [10000, 0.75, 0.25, 70]: 0.381941239809
+New extrema at [10000, 0.75, 0.45, 70]: 0.686913732124
+New extrema at [10000, 0.75, 0.65, 70]: 0.993549377976
+New extrema at [10000, 0.75, 0.8500000000000001, 70]: 1.0
+[10000, 0.75, 0.8500000000000001, 70]
+
+OmniscientEvilGuard compromise rate at [success_rate, adversary_capacity, path_bias_pct]:
+P(CompromisedExit|OmniscientEvilGuard) <= (c/n)*(100/PATH_BIAS_PCT)
+New extrema at [10000, 0.75, 0.05, 70]: 0.0680291553523
+New extrema at [10000, 0.75, 0.25, 70]: 0.356724310419
+New extrema at [10000, 0.75, 0.45, 70]: 0.646151649293
+New extrema at [10000, 0.75, 0.65, 70]: 0.917728688757
+New extrema at [10000, 0.75, 0.8500000000000001, 70]: 1.0
+[10000, 0.75, 0.8500000000000001, 70]
+
+OmniscientEvilGuard compromise at [success_rate, adversary_capacity, path_bias_pct]:
+P(CompromisedExit|OmniscientEvilGuard) <= (c/n)*(100/PATH_BIAS_PCT)
+New extrema at [10000, 0.75, 0.2, 20]: 0.927127409497
+New extrema at [10000, 0.75, 0.2, 40]: 0.497260956175
+New extrema at [10000, 0.75, 0.2, 60]: 0.328728362184
+New extrema at [10000, 0.75, 0.2, 80]: 0.257664872982
+[10000, 0.75, 0.2, 80]
+
+
+==================== Circuits pwnt per client =========================
+
+UnrepentantEvilGuard compromised circs at [success_rate, adversary_capacity, path_bias_pct]:
+circs_per_client ~= success_rate*c/n*MIN_CIRCS for c/n < PATH_BIAS_PCT || c/n < success_rate
+ ~= success_rate*circ_attempts*c/n for c/n > PATH_BIAS_PCT && c/n > success_rate
+New extrema at [100000, 0.75, 0.05, 50]: 0.742451509698
+New extrema at [100000, 0.75, 0.25, 50]: 3.73414682937
+New extrema at [100000, 0.75, 0.45, 50]: 6.91443298969
+New extrema at [100000, 0.75, 0.65, 50]: 30.9604339502
+New extrema at [100000, 0.75, 0.8500000000000001, 50]: 63741.0
+[100000, 0.75, 0.8500000000000001, 50]
+
+PassiveEvilGuard compromised circs at [success_rate, adversary_capacity, path_bias_pct]:
+circs_per_client ~= success_rate * circ_attempts * c/n
+New extrema at [100000, 0.75, 0.05, 50]: 3657.0
+New extrema at [100000, 0.75, 0.25, 50]: 18619.0
+New extrema at [100000, 0.75, 0.45, 50]: 33849.0
+New extrema at [100000, 0.75, 0.65, 50]: 49115.0
+New extrema at [100000, 0.75, 0.8500000000000001, 50]: 63625.0
+[100000, 0.75, 0.8500000000000001, 50]
+
+ProbabalisticEvilGuard compromised circs at [success_rate, adversary_capacity, path_bias_pct]:
+circs_per_client ~= success_rate * circ_attempts * c/n
+New extrema at [100000, 0.75, 0.05, 50]: 4036.0
+New extrema at [100000, 0.75, 0.65, 50]: 65053.0
+New extrema at [100000, 0.75, 0.8500000000000001, 50]: 85187.0
+[100000, 0.75, 0.8500000000000001, 50]
+
+OmniscientEvilGuard compromised circs at [success_rate, adversary_capacity, path_bias_pct]:
+circs_per_client ~= circ_attempts * c/n
+New extrema at [100000, 0.75, 0.05, 50]: 4936.0
+New extrema at [100000, 0.75, 0.25, 50]: 25097.0
+New extrema at [100000, 0.75, 0.45, 50]: 44944.0
+New extrema at [100000, 0.75, 0.65, 50]: 65078.0
+New extrema at [100000, 0.75, 0.8500000000000001, 50]: 84984.0
+[100000, 0.75, 0.8500000000000001, 50]
+
+
+===================== FALSE POSITIVES ============================
+
+Notice false positive rates at [trials, success_rate, min_circs, path_bias_pct]:
+(Results are some function of success_rate - path_bias_pct vs min_circs)
+New extrema at [100000, 0.65, 50, 70]: 0.0151544227886
+New extrema at [100000, 0.65, 100, 70]: 0.00748851148851
+New extrema at [100000, 0.65, 150, 70]: 0.00394002998501
+New extrema at [100000, 0.65, 250, 70]: 0.00385037406484
+[100000, 0.65, 250, 70]
+
+Notice false positive rates at [trials, success_rate, min_circs, path_bias_pct]:
+(Results are some function of success_rate - path_bias_pct vs min_circs)
+New extrema at [100000, 0.7, 50, 70]: 0.0087836081959
+New extrema at [100000, 0.7, 100, 70]: 0.00484715284715
+New extrema at [100000, 0.7, 150, 70]: 0.00275262368816
+New extrema at [100000, 0.7, 200, 70]: 0.00241916167665
+New extrema at [100000, 0.7, 250, 70]: 0.00180548628429
+New extrema at [100000, 0.7, 300, 70]: 0.0
+[100000, 0.7, 500, 70]
+
+Notice false positives at [trials, success_rate, min_circs, path_bias_pct]:
+(Results are some function of success_rate - path_bias_pct vs min_circs)
+New extrema at [100000, 0.75, 20, 70]: 0.00484143171366
+New extrema at [100000, 0.75, 40, 70]: 0.00279088364654
+New extrema at [100000, 0.75, 60, 70]: 0.00188602279544
+New extrema at [100000, 0.75, 80, 70]: 0.00137170263789
+New extrema at [100000, 0.75, 100, 70]: 0.000995004995005
+New extrema at [100000, 0.75, 120, 70]: 0.000834532374101
+New extrema at [100000, 0.75, 140, 70]: 0.000581818181818
+New extrema at [100000, 0.75, 160, 70]: 0.000472843450479
+New extrema at [100000, 0.75, 200, 70]: 0.000287425149701
+New extrema at [100000, 0.75, 240, 70]: 0.000143884892086
+New extrema at [100000, 0.75, 260, 70]: 0.0
+[100000, 0.75, 400, 70]
+
+Reject false positive rates at [trials, success_rate, scale_circs, path_bias_pct]:
+(Results are some function of success_rate - path_bias_pct vs scale_circs)
+New extrema at [1000000, 0.65, 50, 70]: 0.0346242687866
+New extrema at [1000000, 0.65, 100, 70]: 0.0328767123288
+New extrema at [1000000, 0.65, 150, 70]: 0.0322721591761
+New extrema at [1000000, 0.65, 200, 70]: 0.0318086382723
+New extrema at [1000000, 0.65, 250, 70]: 0.0317770557361
+[1000000, 0.65, 250, 70]
+
+Reject false positive rates at [trials, success_rate, scale_circs, path_bias_pct]:
+(Results are some function of success_rate - path_bias_pct vs scale_circs)
+New extrema at [1000000, 0.7, 50, 70]: 0.019617019149
+New extrema at [1000000, 0.7, 100, 70]: 0.014500549945
+New extrema at [1000000, 0.7, 150, 70]: 0.0125621156826
+New extrema at [1000000, 0.7, 200, 70]: 0.0109148170366
+New extrema at [1000000, 0.7, 250, 70]: 0.00958460384904
+New extrema at [1000000, 0.7, 300, 70]: 0.00869939018295
+New extrema at [1000000, 0.7, 350, 70]: 0.00858299595142
+New extrema at [1000000, 0.7, 400, 70]: 0.00795681727309
+New extrema at [1000000, 0.7, 450, 70]: 0.00731071018042
+New extrema at [1000000, 0.7, 500, 70]: 0.00690254872564
+[1000000, 0.7, 500, 70]
+
+Reject false positive rates at [trials, success_rate, scale_circs, path_bias_pct]:
+(Results are some function of success_rate - path_bias_pct vs scale_circs)
+New extrema at [1000000, 0.75, 50, 70]: 0.00594470276486
+New extrema at [1000000, 0.75, 100, 70]: 0.00212178782122
+New extrema at [1000000, 0.75, 150, 70]: 0.000978853172024
+New extrema at [1000000, 0.75, 200, 70]: 0.000467906418716
+New extrema at [1000000, 0.75, 250, 70]: 0.000266933266683
+New extrema at [1000000, 0.75, 300, 70]: 0.000119964010797
+New extrema at [1000000, 0.75, 350, 70]: 7.99720097966e-05
+New extrema at [1000000, 0.75, 400, 70]: 3.59856057577e-05
+New extrema at [1000000, 0.75, 450, 70]: 1.99910040482e-05
+New extrema at [1000000, 0.75, 500, 70]: 2.99850074963e-06
+[1000000, 0.75, 500, 70]
