Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Spacek, Jodi
Master of Science - MSc
University of British Columbia
Internet censorship is a form of digital authoritarianism in certain countries that restrict access to the internet. Internet freedom, to a degree, is possible even in these countries by means of proxies maintained outside of the censor's boundaries. These proxies can be compromised by censors who pose as legitimate users to discover proxies. Censors are powerful adversaries and may block access to any proxy once they know about it. We propose a novel technique to address the proxy distribution problem in this thesis. We introduce the needle algorithm that preserves proxies by limiting their distribution. We show that it is a useful mechanism for both preserving proxies and maintaining client service under a censorship threat model. We examine characteristics of the needle algorithm in a simulation. Three measures are important under the censorship threat model; the enumeration or discovery of all proxies, load balancing guarantees, and the collateral damage of innocent bystanders. We compare the results of these experiments with two well-known algorithms, uniform random and power of 2 choices, as well as Tor's bridgedb proxy assignment mechanism.
The unbalancing act: proxy preservation for censorshipresistance systemsbyJodi SpacekBachelor of Computer Science, UBC, 2014Bachelor of Music, Mount Allison University, 2000A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORALSTUDIES(Computer Science)The University of British Columbia(Vancouver)April 2019c© Jodi Spacek, 2019The following individuals certify that they have read, and recommend to the Fac-ulty of Graduate and Postdoctoral Studies for acceptance, the thesis entitled:The unbalancing act: proxy preservation for censorship resistance sys-temssubmitted by Jodi Spacek in partial fulfillment of the requirements for the degreeof Master of Science in Computer Science.Examining Committee:Ivan Beschastnikh, Computer ScienceSupervisorNorman Hutchinson, Computer ScienceSupervisory Committee MemberiiAbstractInternet censorship is a form of digital authoritarianism in certain countries thatrestrict access to the internet. Internet freedom, to a degree, is possible even inthese countries by means of proxies maintained outside of the censor’s boundaries.These proxies can be compromised by censors who pose as legitimate users todiscover proxies. Censors are powerful adversaries and may block access to anyproxy once they know about it.We propose a novel technique to address the proxy distribution problem in thisthesis. We introduce the needle algorithm that preserves proxies by limiting theirdistribution. We show that it is a useful mechanism for both preserving proxies andmaintaining client service under a censorship threat model.We examine characteristics of the needle algorithm in a simulation. Three mea-sures are important under the censorship threat model; the enumeration or discov-ery of all proxies, load balancing guarantees, and the collateral damage of innocentbystanders. We compare the results of these experiments with two well-known al-gorithms, uniform random and power of 2 choices, as well as Tor’s bridgedbproxy assignment mechanism.iiiLay SummaryInternet censorship prevents citizens of a country from accessing content on spe-cific websites. Censors are powerful figures that restrict free access to informationby limiting their citizens’ internet access when they are within the censor’s coun-try. A proxy is a single hop beyond the reach of the censor that is controlled by anorganization on the outside. A censored user connects to the proxy to hop outsideof their country to view restricted content. There are not enough proxies for eachcensored user to have their own, so they must share. A censor may pretend to behonest to learn about the proxies to block access to them. This thesis presents anapproach to proxy distribution that preserves some proxies by restricting their dis-tribution. We examine the lifetime of proxies in a simulation to see if this solutionis practical in a real-life setting.ivPrefaceThe original and unpublished work presented in this thesis was conducted by theauthor in the Networks, Systems, and Security (NSS) lab in the Department ofComputer Science at the University of British Columbia (UBC) in Vancouver. Itwas designed, documented, and written with assistance from Dr. Ivan Beschast-nikh, Dr. Norman Hutchinson, and Dr. William Aiello. Figures 1.1, 1.2, and 1.3were created by Carlo Cossette. All other figures, tables, and experiments weredesigned and conducted by the author.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixGlossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1 Censorship Threat Model . . . . . . . . . . . . . . . . . . . . . . 52.1.1 Out of Scope . . . . . . . . . . . . . . . . . . . . . . . . 62.2 Coupon Collector Problem . . . . . . . . . . . . . . . . . . . . . 62.2.1 Harmonic Number Approximation . . . . . . . . . . . . . 82.2.2 Singleton Coupons . . . . . . . . . . . . . . . . . . . . . 82.3 Load Balancing . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3.1 Maximum Load . . . . . . . . . . . . . . . . . . . . . . . 9vi2.3.2 Uniform Random Distribution . . . . . . . . . . . . . . . 92.3.3 Power of 2 Choice . . . . . . . . . . . . . . . . . . . . . 92.4 Tor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Needle Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.1 Coupon Collector Ring . . . . . . . . . . . . . . . . . . . . . . . 143.2 Enumeration Analysis . . . . . . . . . . . . . . . . . . . . . . . . 173.2.1 Algorithm Termination . . . . . . . . . . . . . . . . . . . 183.2.2 Upper Bound . . . . . . . . . . . . . . . . . . . . . . . . 183.2.3 Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . 223.3 Load Balancing Analysis . . . . . . . . . . . . . . . . . . . . . . 253.4 Bystander Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 264 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.1 Simulation Model . . . . . . . . . . . . . . . . . . . . . . . . . . 304.2 Enumeration Results . . . . . . . . . . . . . . . . . . . . . . . . 324.3 Load Balancing Results . . . . . . . . . . . . . . . . . . . . . . . 354.4 Bystander Results . . . . . . . . . . . . . . . . . . . . . . . . . . 364.5 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.1 Resource Scheduling and Allocation . . . . . . . . . . . . . . . . 415.2 Trust-based Allocation . . . . . . . . . . . . . . . . . . . . . . . 425.3 Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.4 Related Approaches . . . . . . . . . . . . . . . . . . . . . . . . . 456 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49viiList of TablesTable 3.1 Notation used in the Enumeration Analysis . . . . . . . . . . . 17Table 3.2 Notation used in the Load Balancing Analysis . . . . . . . . . 25Table 3.3 Notation used in the Bystander Analysis . . . . . . . . . . . . 27Table 4.1 Variables in the Simulation . . . . . . . . . . . . . . . . . . . 31Table 4.2 Experimental results for 100 proxies over 1000 trials . . . . . 34Table 4.3 Comparison chart of the 4 algorithms . . . . . . . . . . . . . 39viiiList of FiguresFigure 1.1 A censor observes a citizen’s network activity. . . . . . . . . . 1Figure 1.2 The citizen uses a proxy to access the internet. . . . . . . . . 2Figure 1.3 Censorship circumvention via proxy distribution. . . . . . . . 3Figure 1.4 Open Observatory of Network Interference (OONI) project’scensorship data. . . . . . . . . . . . . . . . . . . . . . . . . . 3Figure 3.1 5 giant steps around a ring of 20 proxies . . . . . . . . . . . . 14Figure 3.2 Rings of 8 proxies each with steps g=1,2,4,8 . . . . . . . . . . 16Figure 3.3 Worst case enumeration in 5 giant steps. . . . . . . . . . . . . 21Figure 3.4 Best case enumeration in 5 giant steps. . . . . . . . . . . . . . 23Figure 3.5 Upper and Lower Bounds for the Needle algorithm, where n=100, g = 1...50 . . . . . . . . . . . . . . . . . . . . . . . . . 24Figure 3.6 Proxies px1 to px4 with honest and attacker clients. . . . . . . 27Figure 4.1 M/M/c/k with uniform random distribution . . . . . . . . . . 30Figure 4.2 Giant step enumeration comparison for 100 proxies . . . . . . 33Figure 4.3 Number of assignments before enumeration for each algorithmfor n=10 to 100 proxies. . . . . . . . . . . . . . . . . . . . . 34Figure 4.4 Needle Load Balancing until all proxies are enumerated twicefor n = 60,100,200,500. . . . . . . . . . . . . . . . . . . . . 35Figure 4.5 Load balancing results for each algorithm for n=10 to 100proxies and 5000 assignments each. . . . . . . . . . . . . . . 36Figure 4.6 Comparison of Malicious Clients over 5000 assignments with50% attackers in the system. . . . . . . . . . . . . . . . . . . 37ixFigure 4.7 Total number of bystander clients in the least popular proxies. 38xGlossaryCCP Coupon Collector ProblemCCP-R Coupon Collector Problem RingCDN Content Delivery NetworksCRS Censorship Resistance SystemsDNS Domain Name SystemHTTP Hypertext Transfer ProtocolHTTPS Hypertext Transfer Protocol SecureIP Internet ProtocolISP Internet Service ProvidersOONI Open Observatory of Network InterferencexiAcknowledgementsThis research was funded by a Canada Graduate Scholarships-Master’s (CGS-M)grant from the Natural Science and Engineering Research Council of Canada (NSERC).I would like to thank my advisor, Dr. Ivan Beschastnikh for his patience andguidance through the trials of learning how to research. I would also like to thankDr. Norman Hutchinson for his insights, and Dr. William Aiello for helping me tocarve out this research topic.To my partner, Carlo, whose support through this endeavour has been unwa-vering.To my grandmother, Marjorie Sˇpacˇek, thank you for teaching me how to codeon your Commodore 64. To my grandfather, Dr. Miroslav Sˇpacˇek, for teaching meto question everything. And to my great uncle, RNDr. Ladislav (Adus) Sˇpacˇek, forinspiring me through music and math.A special thanks to all my teachers for providing answers to my questions.xiiChapter 1IntroductionInternet censorship is a significant and growing problem that threatens our free-dom of expression and access to information. A citizen within a censored countryattempts to access the internet that is hosted beyond the censor’s control boundary,shown in Figure 1.1. A censor is a strong nation state adversary that conducts masssurveillance and utilizes blacklists. One of the simplest techniques employed bycensors is to deny access to users by blocking traffic destined for blacklisted sites.Figure 1.1: A censor observes a citizen’s network activity.This effective censorship technique can be circumvented by means of proxies;single-hop servers outside of the censored country that facilitate indirect accessto censored information. In Figure 1.2, a citizen is blocked from the internet butmanages to access sites via a proxy. Censorship Resistance Systems (CRS) like1rBridge [25], meek [9], and Tor’s bridgedb [2] manage proxies and allow usersin censored countries to access blacklisted websites. These systems bypass censorsand route users through secret paths. Secret paths rely on proxies that are managedby censorship resistance systems. Proxies serve as intermediary hops between auser and a blacklisted destination site.Figure 1.2: The citizen uses a proxy to access the internet.CRS are composed of honest and dishonest (fake) users, several honest proxies,and a centralized proxy distributor that is also honest. Figure 1.3 shows a typicalcensorship circumvention system using a collection of proxies and a centralizeddistributor. CRS rely on the proxy distributor to assign clients to proxies. Honestusers anonymously request proxies and receive proxy information details from thedistributor. However, a censor may also learn proxy details by posing as an hon-est user via legitimate, anonymous methods. The censor coordinates informationcollected through a collection of fake accounts to gain knowledge of the proxies inthe circumvention system.To get an idea of the scale of censorship events around the world, Figure 1.4shows a world map where the Open Observatory of Network Interference (OONI)project’s network measurement tests, ooniprobes, are run daily by volunteers[3]. The red areas on the map outline confirmed cases of censorship. Censorship isconfirmed by the response body of a Hypertext Transfer Protocol (HTTP) requestof a blocked page from within a censored country.2Figure 1.3: Censorship circumvention via proxy distribution.Figure 1.4: OONI project’s censorship data.Proxies in censorship resistance systems that cannot distinguish between hon-est users and fake users are destined for discovery over time. Most systems man-ually reserve a set of proxies that is only distributed when all other proxies arecompromised. This manual solution is effective, but does not maximize the alloca-tion of proxies.We offer a lightweight, elegant solution to the proxy distribution problem byslowing down the progress of the censor to learn new proxies. Our goal is to3provide service to clients while preserving proxies from distribution, a goal thatis complimentary to reserving proxies. We introduce a partially random strat-egy for the proxy distribution problem to distribute proxies to honest clients whilefake clients are present. Our approach uses principles of load balancing in a non-intuitive way to preserve random proxies by unbalancing the load on proxies, mak-ing them more difficult to discover.We provide an approximation of the censor’s required effort to discover all ofthe proxies in a system based on the coupon collector problem [11]. We validatethis approach in a simulator that simulates a proxy distributor in a censorship re-sistance system.We contribute to the existing body of knowledge in the following five ways:1. We introduce a novel algorithm, needle, that restricts the distribution of prox-ies in order to slow the expected time of proxy system compromise while stillmaintaining service to a proportion of clients.2. We define a censorship threat model within which we evaluate the needlealgorithm. We define honest users, a proxy distributor, insider attackers,popularity blocking, and a colluding censor within this model.3. We analyze the needle algorithm in the context of the coupon collector prob-lem to give bounds on the average time to collect all of the proxies.4. We build a simulator to evaluate the needle proxy distribution algorithm andcompare the results with Tor’s bridgedb distribution, uniform random dis-tribution, and the power of 2 choice load balancing algorithms.5. We discuss the benefits and drawbacks of trust-based proxy distribution vs.lightweight approaches and provide ideas for future work on our approach.4Chapter 2Background2.1 Censorship Threat ModelThe first goal of our censor in this model is to discover proxies. The censor discov-ers, or enumerates, proxies by posing as a legitimate user of a CRS. The distributionof proxies to honest users and the censor posing as an honest user is a cat-and-mouse game between the censor and a CRS, referred to as the proxy distributionproblem.There are three attacks that lead to the ability of our censor to block a proxy;the Sybil attack followed by the insider attack leading to the enumeration attack.In the first stage of the insider attack, a malicious entity, such as a censor, deploysmultiple accounts through anonymous authentication. This is the Sybil attack thatcreates fake accounts to gain entry to the system. The insider attack occurs whenthe knowledge of assigned proxies gained from honest proxy assignment is given tothe censor. The enumeration attack that follows is usually the action of the censorto block all of the proxies it knows about [25].Once a censor knows about a proxy, it can decide to block that proxy. The sec-ond goal of our censor is to block the largest amount of honest users as possible.The censor may choose to block immediately when a proxy is discovered, knownas immediate blocking. The censor may instead delay blocking in order to maxi-mize the collateral damage to honest clients, or perhaps wait for a critical time ormaximum number of users to time a blocking attack.5In addition, the censor keeps track of proxies that are the most popular. Thecensor determines that a proxy is popular by the number of times a proxy is as-signed compared to other proxies that it knows about. The censor then chooses toblock proxies based on their popularity ranking.We make different kinds of blocking assumptions in the evaluation section inChapter 4. Immediate blocking makes the most sense when we evaluate enumera-tion because as soon as the censor is assigned to any proxy, it is enumerated. Weassume delayed blocking behaviour in the load balancing analysis because we wantto observe load balancing trends over time, without any blocking on the part of thecensor. The bystander evaluation assumes that the censor blocks the most popularproxies so that we can measure the number of bystanders in the remaining proxies.2.1.1 Out of ScopeThe censor is a powerful, nation-state adversary and many of its capabilities arebeyond the scope of this work. For example, network-level proxy discovery wherethe censor actively or passively scans Internet Protocol (IP) addresses is not ad-dressed. A censor may monitor all traffic in their network, store the state of thenetwork, and monitor requests and responses to known proxy addresses. This al-lows the censor to potentially mount a zig-zag attack to connect users together bytheir proxies [1]. Only proxy discovery by assignment of an attacker to a proxy isexplored in this thesis.2.2 Coupon Collector ProblemIn our model, the problem of proxy distribution is simply to distribute a collectionof n proxies to some users, where k of these users are attackers, in such a way as toprovide a degree of functionality to the honest users. From the censor’s viewpoint,it closely aligns to the Coupon Collector Problem (CCP) where the proxies arecoupons and the censor is the coupon collector.CCP is a classic occupancy problem that considers the number of coupons thatmust be collected before one has the entire collection of coupons. There are ndistinct coupons that are collected one at a time where the ith coupon arrives withprobability pi [21]. The uniform random algorithm, shown in Algorithm 1, chooses6one coupon randomly from the list of total coupons.Where probabilities pi from i = 1 to n are equal, the arrivals are uniform ran-dom. This equi-probable case, where all probabilities of coupons are equal, showsthat the probability of obtaining a new coupon i decreases with each draw. Theaverage number of draws to collect all of the coupons is nHn where Hn is the nthharmonic number [11]. We briefly show why this is the case below.The summation of probabilities of obtaining a distinct coupon, not previouslyseen, is nn +n−1n +n−2n + ...+1n . The probability of receiving a unique coupondecreases by 1 in the numerator for each selection. The probability of a new couponin the first draw is 100% for instance, because no coupon has yet appeared. Thevery last coupon is the most difficult to select with probability = 1/n. By linearityof expectations, where pi is the probability of obtaining the ith coupon, this can bewritten as:pi =n−1∑i=0n− inThis follows a geometric distribution, therefore E[Xi] = 1pi where X is the sumof the expected number of draws for the ith coupon from i to n. The expectednumber of draws for all n coupons in total is:E[X ] =n−1∑i=0nn− iBy changing the variable i to j = n− i, we obtain E[X ] = nHn, where Hn is thenth harmonic number:E[X ] = nn∑j=11j= nHnWe use two previous works in our analyses in Chapter 3; the uniform randomapproximation and singleton coupons.7Data: A list of coupons and one randomly selected coupon c. Coupons areselected uniform randomlyResult: A coupon cbeginc←− random(coupons)endAlgorithm 1: Uniform Random Coupon Collection2.2.1 Harmonic Number ApproximationRecall that the censor collects n proxies in E[X ] = nHn steps. There is no closedform expression for the harmonic number, Hn. Instead, the approximation withEuler Mascheroni Constant γ ≈ 0.5772156649 and Hn = lnn+ γ+1/2n is used inthis analysis [11].2.2.2 Singleton CouponsVariations of the CCP are explored in [22] where a single collector attempts toobtain a specific number of coupons out of n total coupons. As part of this analysis,we use the number of singleton coupons that Myers et al. provide. Singletoncoupons are coupons that have been selected exactly once after all of the othercoupons have been collected. Most coupons are duplicates and only a few appearonly once. On average, the number of singleton coupons is equal to the harmonicnumber Hn.2.3 Load BalancingFrom the perspective of the proxy distributor, the proxy distribution problem is aform of load balancing where some clients are malicious and the proxy distributorwould like to allocate as many proxies as possible to honest clients. Load balancingstrategies are used to evenly allocate resources in distributed systems and havehistorically been modelled as balls and bins [19].82.3.1 Maximum LoadThe evenness of the distribution is formalized as the maximum load. The maximumload is equal to the number of balls in the bin that has, with high probability1, themaximum number of balls over all the bins. The closer that the maximum load isto a perfect distribution of m balls over n bins, m/n, the more even the distribution,and thereby the load is more evenly balanced.2.3.2 Uniform Random DistributionThe maximum load of a uniform random placement of balls in bins where m = nis well known to be approximately logn/ log logn with high probability [12]. SeeLemma 5.1 below from the analysis in Chapter 5 of Probability and Computing[19].Lemma 1 When n balls are thrown independently and uniformly at random inton bins, the probability that the maximum load is more than 3lnn/ ln lnn is at most1/n for n sufficiently large.2.3.3 Power of 2 ChoiceThe power of 2 choice algorithm for load balancing shows that giving two randomchoices instead of a uniform random placement results in an exponential improve-ment in the maximum load [20]. Figure 2 outlines the power of 2 choices algorithmthat randomly selects two bins from the total list of bins. To determine the bin thatis selected, the algorithm checks the load of each bin. The bin with the least num-ber of client assignments is returned.The maximum load in the uniform random case is lognlog logn +O(1) where thenumber of balls is equal to the number of bins [5]. In the two-choice algorithm, thefullest bin with high probability has log lognlog2 +O(1) balls where the number of binsselected randomly is 2. Increasing the number of bins ≥ 2 yields only a constantfactor of improvement. The heavily loaded case, where the number of balls strictlyincreases over the number of bins, m>> n, was found to have a maximum load of1with high probability means at least 1−O(1/n)9Data: A list of bins bins, two randomly selected bins b1 and b2 with totalnumber balls, or loads, l1 and l2 respectivelyResult: One of {b1,b2}beginb1←− random(bins)b2←− random(bins)l1←− load(b1)l2←− load(b2)if l1 == l2 thenreturn random(b1,b2)/* break a tie */else if l1 < l2 thenreturn b1/* b1 is least loaded */return b2/* b2 is least loaded */endAlgorithm 2: Power of Two Choicesm/n+O(log logn) [6].2.4 TorOne of the most widely used distributed, anonymous networks is the Tor onion net-work. Tor is useful for avoiding traffic analysis, a form of internet surveillance, butany anonymous network on its own is insufficient for censorship circumvention.For example, Tor packets are identifiable from telltale signs in the format of trafficsent to the Tor network. Additionally, these packets are easily blacklisted by cen-sors because onion relay IP addresses in the onion network are publicly known. Torincludes various obfuscation protocols, known as pluggable transports,to hide distinguishing characteristics of packets from censors. These protocols arerun by Tor bridges; bridges are single-hop proxies into the Tor onion network.Bridges are run by volunteers in a trusted proxy environment outside of the censorboundary. Tor needs to communicate the address of a bridge to legitimate users se-curely. This is another form of the proxy distribution problem; to distribute secret10bridge addresses (proxies) only to legitimate users, not to censors.A user requests bridge addresses from Tor by emailing Tor’s bridge service.The bridge service, bridgedb, selects three bridge addresses at a time and ratelimits these requests. For example, a request from a single email address can re-quest bridges once daily. The bridgedb data structure is a hashring where anindex into the keyspace is generated by hashing unique user information into asubring that is rotated on a scheduled interval.2 This index gives the first bridgeaddress, the other two bridge addresses are the successors of the first index in thering. The censor can enumerate bridges one-by-one by posing as a legitimate user.Ling, Luo, Yu, Yang, and Fu showed in [16] that Tor bridges can be enumeratedwith bulk emails via the Hypertext Transfer Protocol Secure (HTTPS) protocol.Coming up next, in Chapter 3, we’ll analyze the expected time to collect allof the proxies using the needle algorithm in the context of the coupon collectorproblem. We’ll also refer to the maximum load in the load balancing analysis.Later on, in Chapter 4, we’ll compare the uniform random, power of 2 choices,and Tor’s distribution mechanism with the needle algorithm in our evaluation.2https://gitweb.torproject.org/bridgedb.git/tree/bridgedb/distributors/email/distributor.py11Chapter 3Needle AlgorithmWe present a new algorithm, the needle algorithm, and compare it to two well-known algorithms, uniform random and power of 2 choices, as well as Tor’s bridgedistribution scheme, in order to contrast their respective trade-offs and suitabilityunder differing system goals. The primary goal of the needle algorithm is to pre-serve some proxies from within the larger list of n proxies. Another goal is tomaintain practical load balancing for the majority of the proxies. It achieves thesegoals by breaking the list of proxies into sublists. It moves through the proxiesjumping from sublist to sublist, referred to as GIANTSTEPS or g. These steps iso-late some proxies from distribution.1 The algorithm has the following parameters:• proxies: a sorted list of proxies ordered by load• n: the total number of proxies• g: the number of steps around the proxy ring• s: the number of proxies in each g step• move: indicates a move to the next step• px1, px2: two randomly selected proxies from within the sublist of the cur-rent step g, sampled with replacement1Those readers familiar with the algorithmic composition techniques of jazz chord progressionmay draw a parallel from the restriction of proxies to the restriction of notes in a key change. Theseare reminiscent of Coltrane’s Giant Steps [15].12Data: proxies, n, s = bn/gcResult: One of {px1, px2}beginwindow←− (start,end)if move> 1 then/* a giant step around the proxy ring */start←− (start+ s) % nend←− (end+ s) % nmove←− 0move←− move+1sublist←− (proxies [start,end])px1←− random(sublist)px2←− random(sublist)l1←− load(px1)l2←− load(px2)if l1 == l2 thenreturn px1/* break a tie */else if l1 > l2 thenreturn px1/* px1 is heaviest loaded */return px2/* px2 is heaviest loaded */endAlgorithm 3: Needle AlgorithmThe algorithm selects two proxies uniform randomly in each giant step g. Us-ing reverse power of 2 choices, it then chooses the heavier loaded proxy and returnsthis proxy to the collector. (Note that the standard power of d choices algorithmchooses the lighter loaded proxy.) The step begins at the bottom of the list of prox-ies and is moved step-wise around the list, eventually wrapping around, so that allproxies have an opportunity to be selected, shown in Figure 3.1.Some number of proxies are less likely to be selected as step g moves. Forexample, the proxies in previous selections left behind are referred to as needlesbecause they are hidden from the current selection. Additionally, proxies that havea lower chance of appearing in the random selection, e.g., the last few distinctproxies to be selected, have a lower probability of appearing in any selection. As13Figure 3.1: 5 giant steps around a ring of 20 proxiesg moves, it also unbalances the load on proxies thereby increasing the number ofselections that the censor must perform because there are more duplicate selections(misses).3.1 Coupon Collector RingOne may find a parallel between the Coupon Collector Problem CCP and the prob-lem of a censor who collects, not coupons, but proxies. Consider both the couponand proxy as objects in some vast space, where all of these objects have the samechance of being selected. Each object is replaced after it is selected so that any ob-ject may be selected multiple times. It is increasingly difficult to collect a distinctobject because most objects are selected more than once. The rarest object is theone that occurs at the very end to complete the collection. The selection of thisvery last unique object ends the game, since only the selection of distinct objectscounts towards progress in this problem.14We can frame the needle algorithm as a CCP variant, we call this the CouponCollector Problem Ring (CCP-R) variant. Suppose that the coupon collector orga-nizes collections from several different neighbourhoods. Each neighbourhood dis-tributes a different set of coupons, and each of the coupons in each set is distinct.The coupon collector needs to travel through all of the neighbourhoods (these areconveniently arranged in a ring). The collector can’t magically move from place toplace and does not zigzag from neighbourhood to neighbourhood. If the collectormisses a coupon from the first neighbourhood, then he must wait until all of theother neighbourhoods are visited before returning to collect the missed coupon.The missed coupon is rarer than all of the previously collected coupons. It is alsorarer than all future coupons up until the point at which the collector returns to thespecific neighbourhood with the missed coupon.In our CCP-R variant, the reverse power of 2 choices gives the collector a deci-sion to make; he selects 2 coupons at random. If he already has more of 1 couponthan the other, he must keep the coupon that is less rare, and return the rarer couponback to the store in the current neighbourhood.There is an expected number of attempts E[X ] by the collector to collect n dis-tinct objects. This can be extended to a censor, whose problem it is to enumerate, ordiscover, all the proxies. We use E[X ] to analyze the amount of effort that it wouldtake a censor, on average, to enumerate all proxies. To simplify this analysis, wedo not consider the ratio of honest to malicious clients and, for now, assume thereis one malicious client, the censor. Honest and malicious client rates are examinedin Section 3.4, bystanders.The needle algorithm is partly randomized and partly deterministic. The uni-form random selection of 2 proxies is randomized, and the reverse power of 2choices is deterministic. In addition, the movement of the steps is also determin-istic. Because the steps move clock-wise around the ring, proxies are enumeratedrandomly within deterministic batches. Moving the steps around the ring servestwo functions; 1) by limiting the size of proxies in a step, it squeezes the numberof possible proxies that a censor can enumerate in each assignment, and 2) someproxies are left behind. This makes it more difficult for the censor to enumeratea complete collection of proxies due to these rare proxies (not unlike needles in ahaystack). Restricting the size of the sublists in a step tends towards a deterministic15enumeration of all of the proxies, so one must take care to not set too many giantsteps.In Figure 3.2, we see how different step sizes affect the enumeration of proxies.With one-step, the enumeration time is the slowest, because the needle proxiesmust be discovered within the largest pool of size n. Enumeration time starts todecrease with 2-steps, because the needle proxies are more likely to be selectedwith a smaller pool size of n/2. The enumeration time decreases with each increasein giant step g. The algorithm only functions as expected up to g= n/2 where thereare at least 2 proxies for each step. If there is only a single proxy in each step, asshown in the bottom right corner, the proxies are enumerated one after the other inn assignments, because our reverse power of 2 choices algorithm cannot functionas intended. We therefore restrict the giant step size to 1≥ g≤ n2 so that the proxiesare never enumerated in deterministic order.Figure 3.2: Rings of 8 proxies each with steps g=1,2,4,8163.2 Enumeration AnalysisRecall that the enumeration of our collection of proxies occurs when the censorlearns all of the proxies through assignment. The enumeration of proxies is mod-eled as the complete collection of coupons. The CCP-R variant is used to calculatethe average time to collect all distinct proxies.Parameter Name Descriptionn total number of proxiesg number of steps around a proxy rings size of proxies allocated in each step n/gHn harmonic numberpxi the ith proxypi probability that the ith proxy is enumeratedp sum probability that proxies 1 to n are enumeratedXi random variable of assignments to enumerate the ith proxyX random variable of sum of Xi from 1 to nE[X ] expected time on average to enumerate all proxiesTable 3.1: Notation used in the Enumeration AnalysisThere are two different, yet intertwined, flavours of probabilities in our algo-rithm; the probability of selection and the probability of choice. The probability ofselection is uniform random and is restricted by the size of the giant step g. Whena pair of proxies is selected uniform randomly from the total collection of prox-ies, this is referred to as the selection. When we refer to likelihood of selection,we are talking about the probability of selection in relation to the coupon collectorproblem. Because we sample proxies randomly with replacement, a proxy can beselected twice in a pair. The probability of choice relates to the order in which aproxy is selected as a pair. The likelihood of choice is dependent on the load of aproxy as it affects the choice in the reverse power of 2 choices algorithm. Prob-ability of choice is important in our analyses, particularly in the load balancinganalysis.173.2.1 Algorithm TerminationWe define two lemmas below that we will use to approximate upper and lowerbounds on the average enumeration time. We define the algorithm termination interms of the rarest proxy, the last distinct proxy that is selected, pxn. Proxy pxn hasthe probability of selection = 1/n making it the rarest proxy out of all of the otherproxies. Note that this proxy must have load = 0 because it was never previouslychosen out of a selected pair. Recall that the reverse power of 2 algorithm choosesthe proxy with the highest load out of a pair of proxies. The rarest proxy can onlybe chosen if it is compared against itself. The only case where this occurs (whenthe proxy appears with probability of selection 1/n) is when this proxy is selectedin a pair.Lemma 2 A pair of the rarest proxy terminates the algorithm.Assume we have the rarest proxy pxn that has probability equal to 1/n of beingselected in the reverse power of 2 choices algorithm. Suppose that this proxy isselected twice in a row and forms a pair. If the choice from this selected pair doesnot terminate the algorithm, there must be some other proxy in the collection of nproxies that has not yet been chosen. If this statement is true, then proxy pxn musthave a probability greater than 1/n and our initial assumption is false, leadingus to a contradiction. Therefore, the proxy with probability 1/n terminates thealgorithm if it is selected twice in a row, as a pair. In other words, the least likely,rarest proxy must occur as a pair for the algorithm to terminate.Lemma 3 The probability of enumerating the rarest proxy is at least 1/n2.By Lemma 2, the needle algorithm terminates after the rarest proxy is selectedin a pair. The probability that the rarest proxy is selected is 1/n. We sample withreplacement, so the probability that the rarest proxy is selected twice in a pair, bycounting argument, is p = (1n)(1n) = 1/n2.3.2.2 Upper BoundWe use the number of singletons described in Chapter 2, Hn, directly to providean upper bound on the average number of pairs selected, E[X ], before all of theproxies are enumerated. Singletons are proxies that occur only once and so have18the lowest probability of selection. These proxies need to be paired with otherproxies that have lighter loads to ensure that they are chosen by the reversed powerof 2 choice algorithm. (They also need to appear as the first item in the pair for thetie-breaking logic.) Most of the singleton proxies occur at the end of the selectionprocess, so the probability of selection for each of them is closer to 1/n than n/n.In the worst case (for the censor), all of the singleton proxies occur at the end ofthe collection. Since most of the proxies have load> 1 as n increases, there is littlechance that singleton proxies are chosen against non-singleton proxies, becausemost of these non-singleton proxies have appeared numerous times already andhave higher assignment loads.Lemma 4 The probability of collecting all of the singleton proxies isdHne∑i=1(in2)The probability of collecting all of the singleton proxies is bounded above bythe likelihood that the singleton proxies are selected in a pair with the rarest proxypxn, the worst case for a censor. The rarest proxy pxn is selected with probability1n . The probability that some ith singleton proxy is selected in a pairing with pxn ispi = ( in)(1n).If we pair all of the singleton proxies with the rarest singleton proxy, pxn, weget the probability pairs (1n)(1n)+ (2n)(1n)+ ...+(Hnn )(1n). There is no guaranteethat Hn is an integer, indeed it will not be. Fractional pairings can’t happen in ourpairings, e.g. there is no half of a proxy selected. Because we are dealing with anupper bound, we say that the number of singleton proxies is≤dHne. In addition, weneed an even number of pairings, so dHne is rounded to an even number. Generallystated, the probability of this pairing over all Hn singletons is:p≤dHne∑i=1(in)(1n)=dHne∑i=1(in2)19Now, we are ready to present the upper bound on the average number of assign-ments before all of the proxies are enumerated. Recall that Xi is a random variablerepresenting the number of assignments needed to enumerate the ith proxy, there-fore E[Xi] is the average number of assignments to collect the ith proxy. E[X ] is theaverage number of assignments needed to enumerate all of the proxies. We denotethe ith proxy as pxi where the last selected, rarest proxy is pxn with probability 1/n.The second rarest proxy is pxn−1 with probability 2/n. The first proxy selected ispx1 with probability 1.Theorem 5 Upper bound on E[X ]≤ n2HdHnegProof. We use the probability of collecting all of the Hn singleton proxies fromLemma 4 to provide an upper bound on the average number of assignments neededto enumerate all of the proxies, E[X ].Like the classic CCP, this follows a geometric distribution, so E[Xi] = 1pi .E[Xi] = 1/pi =1in2=n2iThe expected number of assignments to find all n proxies is bounded above bythe sum of E[X1] to E[Xn], where n = dHne:E[X ]≤dHne∑i=1(n2i)E[X ] = n2dHne∑i=1(1i)E[X ] =(n2)(HdHne)When giant step g is very small, the algorithm churns on a few proxies, mean-ing that a small proportion of proxies have high loads. By dividing n proxies intog > 1 giant steps, where each step has a sublist of size s, we make the algorithmmore load balanced. In other words, the distribution of proxies in each step is20smaller so the censor gets more chances to find the singletons. We rework theupper bound to incorporate the number of giant steps g.Figure 3.3: Worst case enumeration in 5 giant steps.We have g giant steps and Hn singleton proxies; g divides the enumerationtime into smaller sized sublists, making it proportionally easier for the censor toenumerate all n proxies. In the worst case (for the censor), all of the singletonproxies are located in different steps, so all of the steps wait for the other steps’singletons to be enumerated before the algorithm can terminate. Figure 3.3 showsa collection of proxies with 5 giant steps. The first enumerated sublist occurs inthe top right portion of the ring (denoted (1)). The algorithm proceeds clock-wise,moving through each sublist one by one. We divide the upper bound by the numberof steps g to obtain:E[X ]≤ n2HdHneg213.2.3 Lower BoundBefore we present the lower bound on the average number of assignments beforeall of the proxies are enumerated, we consider the probability of singleton proxiesthat are very likely to be chosen. The reverse power of 2 choices relies on the loadof the proxy in order to choose a proxy from a selected pair. Consider a singletonproxy that by definition has a lighter load because it is selected infrequently. Whenthis proxy is paired with some other proxy with a higher probability of selection,the singleton proxy has less chance to be chosen, because the proxy with the higherprobability of selection has a higher chance of having more load. In other words,this singleton proxy has both a lower probability of selection and lower probabilityof choice.We concern ourselves with a lower bound, so we would like to know the typeof scenario in which a singleton proxy has the higher probability of choice, mean-ing that the censor is able to enumerate proxies more easily. A singleton proxypaired with itself is guaranteed to be chosen and thus has the highest probability ofchoice out of any other pairing. We would like to know the probability of a pair ofsingleton proxies to appear.Lemma 6 Singleton proxies occur in a pair with probability p≥ ∑bHnci=1 ( in)2A repeated pair selection of the singleton proxies gives us the probability pairsp = (1n)(1n)+(2n)(2n)+ ...+(Hnn )(Hnn ). The probability of the ith singleton proxy tobe chosen is ( in)2. The probability of this pairing for all Hn singletons is:p≥bHnc∑i=1(in)2We use Lemma 6 in the following proof to obtain the lower bound on E[X ]. Thefastest enumeration of all of the proxies is to collect all of the singleton proxiesthe first time that they show up in a randomly selected pair, that is, their veryfirst selection. We again use Hn singleton proxies, this time to bound the averagenumber of assignments from below. We consider cases where g≥ 1 and we changethe variable n to s because we draw from g sublists of size s.Returning to the idea of a ring of proxies, if all of the sublists are enumeratedone directly after the other, none of the other steps are ”held up” by any of the22Figure 3.4: Best case enumeration in 5 giant steps.other previous steps. This means that there are no extra revolutions necessary toenumerate the steps, as shown in Figure 3.4.Theorem 7 Lower bound on E[X ]≥ (g)(s2)H(2)bHncProof. Using the probability of pairs from Lemma 6, we have a geometricdistribution, so we can write:E[Xi] =1pi=1( is)2=(si)2The expected number of assignments to find all n proxies is bounded below bythe sum of E[X1] to E[Xn], where n is the number of singleton proxies, n = bHnc:E[X ]≥bHnc∑i=1(si)2= s2bHnc∑i=11i2= s2H(2)bHnc23Figure 3.5: Upper and Lower Bounds for the Needle algorithm, where n =100, g = 1...50We have g such enumerations of sublists with size s, one per each g steps,therefore for all n proxies are bounded from below by:E[X ]≥ (g)(s2)H(2)bHncIn Figure 3.5, we show the upper and lower bounds for 100 proxies with giantsteps 1 to 50. The enumeration time drops for each giant step, particularly dramat-ically where the giant step is increased from 1 to 2. It levels out as the giant stepincreases, as these increases create an increasingly deterministic enumeration.24This concludes our discussion of bounds on the average number of assignmentsto enumerate all of the proxies in the needle algorithm. In the next section, we diveinto a load balancing analysis to tell us more about how clients are assigned toproxies.3.3 Load Balancing AnalysisWe discussed maximum load as a metric for load balancing in Chapter 2. We can-not guarantee that the number of bins (proxies) is equal to the number of balls(assignments), so the maximum load does not tell the whole picture. We need tolook at the least loaded and heaviest loaded extremes and find an average measure-ment and compare this to the optimal load. The optimal load is the load of eachproxy if the system was perfectly balanced, that is, if the number of assignmentswere divided evenly over the number of proxies.Parameter Name Descriptionn total number of proxiesm total number of assignments in a series of trialspxi the ith proxypi probability that the ith proxy is enumerated` optimal loadu maximum loadE[X ] expected time on average to enumerate all proxiesd1 distance between px1 and px n2d2 distance between px n2 and pxnTable 3.2: Notation used in the Load Balancing AnalysisLemma 8 Proxy loads increase linearly.We sort the proxies by their load, or their respective numbers of assignments,averaged over multiple trials. (Note that these are not static proxy numbers, butproxies that are numbered by their load.) We see that the loads have a linear re-lationship. This is because the probability of selection of the pxi proxy decreaseslinearly from i= 1...n. The probability of selecting the first proxy px1 is p1 = nn = 1,the probability of the second px2 is p2 = n−1n , pn−1 = 2/n, pn = 1/n, increasing25linearly. This linear relationship between the probability of proxy selection is fur-ther reinforced by the probability of choice, where the maximum loaded proxy isalways chosen over a lower load.Lemma 9 The middle proxy, pxn/2, has the optimal load `.Let the number of total assignments in a series of trials be m, and E[X ] be theaverage number of assignments before all proxies are enumerated where m >>E[X ]. The optimal load is ` = m/n. Proxy pxn/2 has the probability of selectionequal to p n2= n/2n in the reverse power of 2 choice selection. It is n/2 more likelyto be chosen from the selection than proxies px1 to px n2−1 and n/2 less likely to bechosen over proxies px n2+1. Its placement at the midway point of choice means thatit is also at the midway point of the load `.Theorem 10 The maximum load, u, of proxy px1 is twice as big as the optimalload, 2`, if all of the proxies are enumerated.We know by CCP that the minimum load is at least 1 if all of the proxies areenumerated. By Lemma 9, we see that the middle proxy px n2has the optimal load.Since the proxy load has a linear relationship by Lemma 8, the distance, d1 betweenpxn and px n2 is equivalent to the distance, d2 between px n2 and px1. px n2 has theoptimal load and the function is increasing linearly, therefore px1 has twice theoptimal load u = 2`= (2)(mn ).3.4 Bystander AnalysisWe integrate honest users into our analysis where previously we only includedthe censor’s problem of enumerating all of the proxies. We want to know thelikelihood that a proxy has been assigned to an attacker, proxy exposure, and theproportion of honest users, or bystanders, that are affected by proxy exposure. Wedraw inferences from the load of each proxy and the probability that a client is anattacker to evaluate bystanders in section 4.4.We define an exposed proxy as a proxy that has at least one insider attackerassigned at any point in time. In a single assignment of a client to a proxy, theprobability that the client is an attacker is given as pa. The total number of assign-ments in a proxy is equivalent to its historical load h.26Parameter Name Descriptionpa probability that a client is an attackerpx probability that a proxy is exposedpnx probability that a proxy is not exposedpb probability of bystander clientsh historical load on a single proxy` optimal loadu maximum loadTable 3.3: Notation used in the Bystander AnalysisLemma 11 The probability that a proxy is not exposed is (1− pa)h.The number of client assignments that a proxy received is equal to the historicalload h. The probability that all h of these assignments are attackers is an ”and”relationship. We multiply the probabilities of attackers per each assignment, htimes. Therefore, the probability that all of the assigned clients on a proxy aremalicious is (pa)h.For a proxy to not be exposed, then it must never have had any attackers as-signed to it. The probability that none of the clients assigned are attackers is(1− pa)h. Then the probability that a proxy is not exposed is the same as theprobability that none of the clients are attackers:pnx = (1− pa)hFigure 3.6: Proxies px1 to px4 with honest and attacker clients.We generalize the probability of exposure to apply to any proxy in the systemusing a bound on the maximum load. This is interesting for our bystander analysis27because we observe that the probability that a proxy is exposed more closely ap-proaches 100% as the maximum load increases, thereby creating more bystanders.Lemma 12 The probability that any proxy is exposed is px ≤ 1− (1− pa)uThe height of any proxy must be less than or equal to the maximum height, u,by definition. Without knowing the load on any individual proxy, we can say thatthe likelihood that an arbitrarily selected proxy is not exposed is less than or equalto the likelihood that the maximum loaded proxy is not exposed.pnx = (1− pa)h ≤ (1− pa)u.Conversely, the probability that any randomly selected proxy is exposed is lessthan or equal to the probability of exposure on the proxy that has the maximumload.px = 1− pnx≤ 1− (1− pa)uThe proxy that has the highest load has the highest chance of exposure. In Fig-ure 3.6, we give an example with four proxies, px1 to px4 that have attacker clientsrepresented as filled circles, and honest clients shown as empty circles. There areno bystanders in proxy px1 because it is not exposed. Proxies px2 and px3 bothhave two bystanders because they each have two honest clients and the proxies areexposed. There are three bystanders on proxy px4. We’ve shown how the max-imum load affects the probability of assigned attackers in a proxy, now we willcompare the relationship of load balancing to bystanders.Theorem 13 The probability of bystanders on a proxy ispb ≤ (u)(1− pa)(1− (1− pa)u)Proof. Honest clients occur with probability 1− pa on any proxy. For an honestclient to be considered a bystander, there must be at least one attacker assigned to28the proxy. We consider the other attackers on a proxy as wasted resources on thepart of the attacker.We know from Lemma 12 that the probability that any proxy is exposed ispx ≤ 1− (1− pa)u. If px = 0 then there are no bystanders, because the proxy is notexposed. (In order for honest clients to be defined as bystanders, the proxy mustbe exposed by at least one attacker.) Therefore, we can say that the probabilityof bystanders on any proxy is less than the probability of bystanders on the proxywith the maximum load.pb ≤ (u)(1− pa)(1− (1− pa)u)We have shown that the amount of collateral damage, expressed by the prob-ability of bystanders on a proxy, relies on the proxy load and the probability ofattackers in each assignment. There are other interesting stories to tell about theimpact of unbalancing proxy loads for proxy preservation. If we have a systemthat is perfectly balanced, with all proxy loads equal to `, intuitively we suspectthat there will be more innocent bystanders b. We may reason that with lowerproxy loads, such as those held in the needle algorithm of proxies px1 to px n2−1,result in fewer bystanders because the likelihood of a malicious client attacker isreduced. We may also reason that in higher loaded proxies, there is more chanceof proxy enumeration, but more wasted resources by the attacker. These musingsare examined in Chapter 4 through empirical data based on simulations of systemsusing the needle algorithm, uniform random distribution, power of 2 choices, andTor’s bridgedb proxy distribution strategy.29Chapter 4Evaluation4.1 Simulation ModelFigure 4.1: M/M/c/k with uniform random distributionBefore considering details of the simulation experiments, we formalize the sim-ulation model and how it applies to the needle algorithm proxy distribution strategy.The notion of static and dynamic models stems from static and dynamic routing in30networks. Mitzenmacher redefined static and dynamic models for task allocationand applied this to the balls and bins model [20]. In this context, a ball is a task anda bin is a processor. The primary distinguishing features of the static model is thatthere are a finite number of tasks that are assigned to processors and these tasks donot leave. The static system model completes its execution when all of the tasksare allocated. This model execution is generally represented in a bipartite graph.A static model applied to the proxy distribution problem assigns a finite number ofclients to proxies in one round.The dynamic model captures scenarios that are more realistic than what maybe represented in the static model. For example, tasks in the dynamic model mayenter and leave the system over time. In the open dynamic model, there may not bea fixed number of tasks. The closed dynamic model allows for tasks to enter andleave over time, but there is a fixed number of arrivals. A dynamic system does nothave a final termination time as in the static model. The advantage of a dynamicmodel is that one can observe the behaviour of a system over time.We are interested in how proxies are enumerated by a censor throughout thesystem’s lifetime, so the open dynamic model suits our scenario well. Utilizing anopen dynamic model allows us to observe trends and compare different approachestemporally. However, our clients don’t leave in the traditional sense; we assumethat once a proxy is discovered, the knowledge of a proxy cannot leave or exit.Parameter Name Descriptionλh client arrival rate intensity of client arrival rate 1/λλa attacker arrival rate intensity of attacker client arrival rate 1/λn number of proxiesTable 4.1: Variables in the SimulationIn addition to the dynamic model, the queue model is a standard that suits theproblem of proxy distribution well. Mitzenmacher models the power of two choicealgorithm as an idealized process, or a queue system of infinite size, that is laterrelated to a finite system by bounding the error between the two [20].Our simulation is best described as a feed-forward network of M/M/c/k queues.This is similar to a load balancing system with a constant number of servers. How-ever, in this scenario, the load balancer is in fact the proxy distributor that is respon-31sible for distributing clients to proxies. Figure 4.1 shows the network queue layoutwhere the proxy distributor assigns clients to proxies uniform randomly, where thearrival of clients to proxies is evenly distributed λ/n.Clients arrive with a Poisson arrival distribution with variable λ clients perminute. This means that, on average, one client appears at every 1/λ minutes andwe define this as the arrival intensity. In this model, we are additionally concernedwith honest and malicious client arrival rates. As the proportion of attackers in thesystem increases, the arrival rate, or intensity of malicious client arrivals increases.Each proxy has a service time that is exponentially distributed. This is not atraditional service rate because the system assumes short-lived client connections.The important function of the server is to keep a record of each client assignmentthat can be used by the censor to discover clients in the system. In other words,even if the client leaves the system, the censor still gains knowledge of the proxyand may impact the client’s future connections to the known proxy, effectivelymounting a potential future blocking attack on the proxy.Parameters. Parameters in the simulation control the rate of honest and mali-cious client arrival intensity, the total number of proxies, and the size of the step forthe needle algorithm. These are sweeping parameters; the simulation runs across arange of values for each parameter to produce a variety of conditions for the anal-ysis. The analysis operates on the dependent variables such as maximum load andthe expected time to overtake the system. The variable names and descriptions areoutlined in table 4.1.The simulator was written in Python using simpy, a discrete event based sim-ulator.1 The evaluation uses numpy2 and matplotlib3 for data manipulation andgraphing.4.2 Enumeration ResultsGiant step analysis. We ran the needle algorithm in the simulator, with only ma-licious attacker clients, to observe how many assignments a censor needs to enu-merate all of the proxies. In section 3.2.2, we analyzed the giant step version of1https://simpy.readthedocs.io/en/latest/2http://www.numpy.org/3https://matplotlib.org/32Figure 4.2: Giant step enumeration comparison for 100 proxiesthe needle algorithm where step size g > 1. Results are shown in Figure 4.2 for1000 trials using 100 proxies in each experiment. The experimental results areshown in the black, solid line. The upper and lower bounds, E[X ] ≤ (n2)HdHneg andE[X ]≥ (g)(s2H(2)bHnc) respectively, are shown in dashed lines.Table 4.2 shows the numerical data from these 1000 trials of varying step sizefor 100 proxies, and the calculated upper and lower bounds.Enumeration Comparison. We compare the four different algorithms in Fig-ure 4.3. The y-axis shows the average enumeration time over 1000 trials where ahigher number of assignments is favourable because it takes longer for a censorto discover all of the proxies. The x-axis shows the trials over different sizes ofn proxies. We know from the Coupon Collector Problem CCP that the uniformrandom distribution of coupons results in nHn total assignments before collection.We see that the uniform random distribution of Tor’s bridgedb follows a simi-lar enumeration. We use the regular power of 2 choices algorithm to show how amore optimal load balancing algorithm results in faster enumeration [27]. In theupcoming section, we’ll take a closer look at the load balancing properties of eachof these algorithms.33Sublist (s) Step (g) Upper Bound Experiment Lower Bound100 1 40000 20619 1250050 2 20000 10718 625033 3 13333 7763 408325 4 10000 6738 340320 5 8000 5869 272216 6 6667 4800 209112 8 5000 3850 156810 10 4000 3537 14248 14 2857 2839 12765 20 2000 1987 7124 25 1600 1683 5692 50 800 788 2851 100 400 100 100Table 4.2: Experimental results for 100 proxies over 1000 trialsFigure 4.3: Number of assignments before enumeration for each algorithmfor n=10 to 100 proxies.344.3 Load Balancing ResultsRecall that in the analysis, Lemma 9 in section 3.3 stated that pxn/2 has the optimalload. In the experiments shown in Figure 4.4, we ran the needle trials until all of theproxies were enumerated and then kept running the trials until twice the numberof enumeration time. We see that the load balancing is divided into two halvescentred around the optimal load. We also note that the maximum load for each ofthe experiments is no more than 4% of the total load.Figure 4.4: Needle Load Balancing until all proxies are enumerated twice forn = 60,100,200,500.We wish to observe and compare the load balancing tendencies of each of thefour algorithms. The x-axis in Figure 4.5 orders all of the proxies by their respec-tive loads. The y-axis shows the percentage of the total load that each proxy holds.We ran each algorithm for 5000 assignments with a total of 100 proxies.A distinguishing feature of each algorithm is their varying degree of even dis-35tribution of assignments to proxies. The power of 2 choices algorithm gives themost evenly balanced distribution. The uniform random distribution results in thenext best load balancing. Tor’s mechanism is less balanced than uniform randombut more balanced than the needle algorithm. The needle algorithm results in theworst load balancing.Figure 4.5: Load balancing results for each algorithm for n=10 to 100 proxiesand 5000 assignments each.4.4 Bystander ResultsLoad balancing and the proportion of attackers directly affect the number of by-standers. Bystanders are those honest clients that still receive service in the pres-ence of malicious clients. For the experiment in Figure 4.6, we run all of thealgorithms so they each have 5000 assignments and the probability that a client ismalicious is 50%. We sort the proxies by their loads in increasing order and plot36the numbers of malicious clients assigned to each proxy, from lowest loaded proxyto highest loaded.Figure 4.6: Comparison of Malicious Clients over 5000 assignments with50% attackers in the system.We see from the results of this experiment that the number of malicious clientsincreases with load in all of the algorithms. The power of 2 choices algorithm hasthe flattest distribution of malicious clients, meaning that proxies are enumeratedthe quickest thus creating the highest number of enumerated proxies over all of thealgorithms, as we discussed in the enumeration analysis in section 3.2.When we consider the number of bystanders, we make the assumption that thecensor chooses to block the top half of the proxies. These are the proxies that aredetermined as the most popular proxies. Figure 4.7 shows the total number ofbystanders that receive service in each algorithm, assuming that the most heavilyloaded n/2 proxies are blocked; that is, the rightmost n/2 proxies in Figure 4.6.The steep slope in the needle’s load balancing for the least heavily loaded, leftmost37n/2 unblocked proxies, allows for a small number of proxies to be preserved, whilestacking higher loads onto the remaining proxies. It also serves to distinguish therightmost proxies as more popular than the others, in a sense serving up theseproxies to be blocked as expected collateral damage.Figure 4.7: Total number of bystander clients in the least popular proxies.We’ve shown that by unbalancing the load on the proxies in the needle algo-rithm, we are still able to service as many or more bystander clients than in theuniform random, power of 2 choices, and Tor’s bridgedb mechanism.4.5 ComparisonWe consider enumeration, load balancing, and bystander analyses of the four algo-rithms in order to contrast their respective trade-offs and suitability under differingsystem goals. Table 4.3 outlines the three metrics that we consider in this the-sis. We indicate with checkmarks 3 where the algorithm is well suited, doublecheckmarks indicate that it is very well suited. A single X mark 7 shows that thealgorithm is unsuitable, a double 7 is used when we consider the algorithm to becompletely unusable for a purpose.38Enumeration Load Balancing Bystanderspower of 2 choices 77 33 33uniform random 7 3 7Tor’s bridgedb 7 3 7needle 33 77 33Table 4.3: Comparison chart of the 4 algorithmsThe power of 2 choices algorithm provided the best load balancing, and sowould be appropriate for systems where this is a concern. However, it is enumer-ated very quickly.Uniform random distribution and Tor’s bridgedb distribution perform simi-larly, and so we consider their respective trade-offs in the same vein. They providea slower enumeration time than the power of 2 choices algorithm due to their un-even load balancing. The number of bystanders is also slightly lower than the otheralgorithms.The needle algorithm gives the slowest enumeration of all the algorithms; thisattribute is beneficial to allocation of proxies in a distribution system. It is notsuitable for systems that require even load balancing. (It is unbalanced to a largedegree but not so much that it is unusable.) It services as many bystanders as thepower of 2 choices algorithm, but without the drawback of fast enumeration. In thecontext of proxy distribution under our censorship threat model, we consider this abenefit.39Chapter 5Related WorkCensorship resistance systems CRS are composed of two parts; 1) communicationestablishment, or handshake, needed to join the CRS, and 2) the conversation stagewhere the actual information is exchanged between the client and the censoredsite. In SOK: Making sense of censorship resistance systems [14], categorizationsof different types of CRS are outlined based on the system’s approach to these twofunctions.There are two main approaches to communication establishment in censorshipresistance systems; resource scheduling and allocation approach, and the trust-based approach. Resource scheduling and allocation fight a losing battle to dis-tribute proxies under a censorship threat model where proxies are continuouslyblocked. Proxies need to be birthed or placed into reserve in order to keep upwith the censor’s blocking rate. The advantage of these schemes is that they arelightweight and easy to implement.The goal of trust-based proxy distribution is to mitigate blocking by buildingtrust between honest users of the system and the proxy distributor. They achievethis by distinguishing honest clients from malicious clients. We outline systemsand techniques that fall under a similar censorship threat model as our own, wherethe censor is omnipotent and blocks proxies based on information gained by posingas an honest user.Note that other types of anonymous systems, such as Vuvuzela [24], Dissent[8], and Freenet [7], are concerned with maintaining levels of anonymity in order40to prevent an adversary from learning about messages from a sender to a receiver.The highest level of anonymity in these systems is a third axis where one cannottell that a user is communicating with any other user [23]. The adversary in theproxy distribution problem under a censorship threat model is vastly stronger thanin general anonymity systems. The goal of CRS is to obfuscate evidence that a useris in the system at all, as well as to hide the activity of the user within said system.5.1 Resource Scheduling and AllocationTor’s Bridge Distribution. Tor bridges are private relays or proxies used for cen-sorship circumvention. Tor bridge IP addresses and fingerprints are distributed outof band using registered email or through a captcha site on the Tor blog. Tor’sBridgeDB authority distributes up to 3 new bridge IPs and corresponding finger-prints to clients based on a hashring uniform distribution. Bridge requests are ratelimited by a centralized bridge distributor. Despite these efforts, censors in Chinahave discovered and blocked most of the bridges given through the public distri-bution channels. Bridge enumeration attacks are possible using bulk emails viaHTTPS [16]. Tor uses a fingerprint as a shared secret scheme to thwart active prob-ing, however this can’t prevent bridge discovery using a delayed insider attack [10].TorBricks. The TorBricks [28] design distributes proxies in groups to guar-antee a maximum number of rounds until all honest users can connect to a proxyserver after some number of retries. It relies on exponential growth in the numberof proxies in order to provide these guarantees of a logarithmic number of rounds.A caveat in this system is, if there are no unblocked proxies in the current group,then the algorithm requires that a unique bridge be allocated per each user.While this approach allows for adaptive adjustment to a proportion of attack-ers in the system, it requires a great deal of resources. For example, if a CRS hadenough proxies to give one out per each user, we would not have the problem ofproxy distribution since we could hand out private proxies. If we have private prox-ies, then no attacker could discover an honest user’s proxy because users would nothave to share.41Fighting Censorship with Algorithms. Mahdian [17] studies proxy distribu-tion as an algorithmic problem and gives bounds on the number of proxies requiredto provide service to clients, some of whom are adversaries. He includes a theo-retical analysis of bounds for the number of proxies needed to survive an insiderattack. His theorems use k-union-free families of sets, probabilistic methods, andextremal set theory to give lower and upper bounds.Mahdian’s scheme creates two sets of users, trusted and suspicious, and dis-tributes keys based on the user’s membership in one of these two sets. Users aredivided into these sets based on their association with compromised keys; they aremoved from the trusted group to the suspicious group. Fresh keys are only handedout to trusted users. This adaptive model bounds the number of keys that an ad-versary can compromise thus providing guarantees for the user with respect to theexpected total number of keys required to give every legitimate user access.In Mahdian’s model, a key represents a servlet or proxy server. His schemeassumes a known number of malicious users and there are no bounds on the numberof clients a proxy can serve. While maintenance of keys is usually relatively simplein practice, the logistics of proxy server maintenance is more involved. It is animpractical assumption that keys (representing proxies) can be distributed to anunlimited number of users without significant overhead.Mahdian’s algorithm distributes an increasing number of keys to users in orderto reduce the risk posed by a growing number of adversaries. This does not addressthe case where adversaries are controlled by the same entity, such as a censor. Forexample, it does not take into consideration the enumeration attack. This attack isfurther exacerbated by the reuse of keys, as opposed to the removal of suspect keys.5.2 Trust-based AllocationProximax. The main goal of the Proximax [18] reputation-based system is tomaximize the yield of a proxy resource, where yield is the number of user-hoursper day before a proxy is blocked, calculated as the product of usage and lifetime.Each proxy resource is advertised on multiple channels. This novel use of a channelrelies on a fast flux technique that piggybacks on Domain Name System (DNS)42infrastructure. Proximax registers multiple proxies to the same domain name andload balances them based on their current utilization and resource risk parameter.The usage and risk of a proxy resource is the sum of the risk of each of the chan-nels where it is distributed. Resource risk is calculated as a maximum likelihoodestimate of blocking - it is only an approximation because resources are advertisedon multiple channels, and the risk per channel cannot be sampled directly. In otherwords, when a proxy is blocked, there is no way to detect the specific channel thatcaused the block and so it is difficult to tease out channel from proxy risk.All proxies will eventually be discovered in proxy distribution, so Proximaxadds a trust scheme to delay censor discovery. Registered users build up theirreputation score and invite new users, handled by a registration system. The reg-istration system allocates proxies that have higher risk to lower reputation scores.They widely disseminate the location of low risk proxies in order to maximizetheir yield. This leads to the potential of rapid enumeration attacks, where the bestproxies are enumerated in quick succession.Proximax’s trust scheme is likely to be thwarted by colluding insider attackerswhere registered users build up reputation to invite other users, as it does not workwell in a delayed blocking attack. Furthermore, the risk approximation may notbe particularly useful because if there is only a single attacker assigned to a proxy,and with the reasonable assumption that all attackers are controlled by the samecensor entity, then this proxy has the same likelihood of being blocked as a proxyto which several insider attackers are assigned.rBridge. rBridge [25] is a trust-based reputation system for a Tor bridge dis-tributor that addresses insider attacks, minimizes user wait time for an availableproxy, and preserves privacy of client assignment information. The rBridge dis-tributor computes user reputation based on the uptime of bridges to which a useris assigned. A payment system allows users to buy unblocked bridges to preventrepeated blocks. They show rBridge’s user-hours served is at least one order ofmagnitude more than Proximax and that thirsty hours of users waiting for a proxyis minimized. This is mainly achieved by making sure that the overall rate of newbridges outpaces the rate of proxy blocks, and by reserving half of their bridgeresources for future invitations.43A significant contribution of rBridge’s design is their privacy preserving schemeusing anonymous credentials to build trust, invite users, and obtain signed creden-tials. Restricting proxy assignments can lead to user fingerprinting as there areunique combinations of proxies tied to a single user. Previous work in pseudony-mous credentials and oblivious transfer methods don’t work well in proxy systemsbecause an attacker can still infer client assignments based on behaviour after aproxy is blocked. rBridge hides bridge assignment from even the distributor by en-abling the proxy assignments to be written and updated by users. They take extrameasures to maintain integrity using anonymous credentials, one-time tokens andsecrets that cannot be forged owing to zero knowledge proofs and blind signatures.In addressing the delayed blocking attack, they note that invitation tickets arerandomly distributed over all users, so there is a chance that the corrupt user maynot receive a ticket. Since tickets cannot be transferred, it is no more likely thatan attacker receives a ticket than an honest user. However, they do not provideanalysis given that even just one corrupt user is more than enough to block a proxy,therefore an assignment of a proxy to a single attacker is more significant than as-signment to an honest user.5.3 RoutingRouting users through decoy paths as a mechanism to discover proxies is a vastlydifferent approach to the proxy distribution problem and handshake used in cen-sorship resistance systems. Essentially, this approach solves the issue of censorsposing as honest users and blocking proxies because censors do not want to blockthe decoy paths. This is because there would be too much collateral damage as thedecoy paths are heavily used and it is difficult to tell if users are accessing blockedsites from the decoys. The barrier to implement these solutions, however, is thatthey require a large commitment from either Content Delivery Networks (CDN) orInternet Service Providers (ISP) to build the decoy paths and to maintain the net-work that provides the anonymous handshake.Telex. This CRS uses destination obfuscation via decoy routing at Telex sta-44tions that are end-to-middle proxies located in their own network infrastructure[26]. Sessions between users and Telex have special tags to direct them throughto censored sites. These proxies are built into the network with involvement fromlocal ISP that must deploy Telex stations on paths between networks under censorcontrol and blocked destinations.Domain Fronting. An elegant way to circumvent censors is through domainfronting, where a user is routed through a legitimate intermediary, such as a CDN[9]. These intermediaries are used to rendezvous with Tor and cannot be detectedby a censor because the CDN’s network is beyond the censor boundary. Domainfronting is the most reliable way to perform the rendezvous handshake and recentlyit is the only protocol that works in China [4]. However, we see that major CDNlike Google and Amazon no longer support domain fronting. Microsoft’s Azurecloud is a temporary fix as there is no formal agreement between Microsoft andTor to support domain fronting in the future.5.4 Related ApproachesThe following works aren’t directly related to the problem of censorship circum-vention. However, their analysis of resource allocation is closely tied to the couponcollector analysis in this thesis. Their lightweight distribution under a differentthreat model also relates to and inspired our approach.Coupon Collector and Power of d Choices. The Power of d Choices wasanalyzed for the generalized form of the coupon collector problem in [27]. Thisincludes the case where a collector wants to collect m out of n total coupons. Thecollector selects d coupons out of the total collection and chooses the least heavilyloaded (or least collected) coupon in each draw. This benefits the collector becauseduplicate coupons are discarded. They show that the expected number of draws tocollect m out of a total of n coupons is (n logn)/d+(n/d)(m1) log logn+O(mn).Although this is opposite from our reverse power of 2 choice algorithm, and farmore complex in its analyses, it is a useful counterpoint to our goal of delaying45enumeration, as the goal here is to enable the coupon collector to collect couponsas quickly as possible.Proxisch. Proxisch [13] is an application of a scheduling algorithm for proxydistribution in web crawling applications. Although Proxisch is intended for dis-tributed web crawling, the proxy server selection mechanism has a similar goalshared by the proxy distribution problem; to reduce the risk of assigning high riskproxies to clients. This work estimates the reliability of proxies based on a relia-bility calculation and uses queuing theory to organize proxies by their respectivereliability factors.To model the life of a proxy, they use an exponential distribution based on thelife of an ideal lamp. They show in their simulations that the actual life span ofsome proxy servers is close to the exponential distribution. This leads to the cal-culation of an optimal update period for cycling proxies among processes. Theycompare their result to a polling scheduling solution that illustrates higher suc-cessful service rates within shorter time periods for their solution. Their resourcescheduling algorithm approach is similar to a randomized proxy selection based onattributes of proxies, such as time, reputation, or credits because it orders proxiesbased on criterion. This is a move away from more complex, monolithic designsfavouring proxies that earn standing over time within the system.It’s not possible to directly translate this solution into the problem addressed inthis thesis, since modeling the lifetime of a proxy server does not directly translateto the motivations of a powerful censor that can cut the lifetime of a proxy at anytime. However, this work does provide useful hints for how one may approach alightweight proxy distribution design.46Chapter 6Discussion6.1 Future WorkBlocking behaviour. The simulation can easily extend to model different formsof blocking behaviour by a censor. The parameters for a blocking rate processare coded in the simulation although these were not utilized in the simulation noranalyzed for the evaluation.Proxies joining and leaving. A more realistic version of the simulator is to runthe experiments with some proxies joining and leaving. This would provide moredata on how the needle algorithm preserves new proxies, rather than only dealingwith proxies that are created at the same time.Service times. The simulation was not fully utilized to analyze classic prob-lems like Quality of Service. It would be particularly interesting to examine hownon-needle proxies are able to handle the larger loads in a real system.Tor integration. The needle algorithm could be run inside of the Tor BridgeDBcodebase to validate the simplicity of the algorithm’s approach. It would requirea different method of client assignment because Tor uses hashes of IP addressesand does not store load or assignment information in the same way that the needlealgorithm requires for its operation.47Chapter 7ConclusionOur work has the same goal as many proxy distribution systems; to provide serviceto clients in a hostile environment with practically an omnipotent censor entity.Our trust-less, elegant approach to proxy distribution relies on essentially hidingneedle proxies in distribution rounds.Building trust requires storage of user behaviour over time. Within anonymoussystems, the assumption that a system itself can be trusted to store this informa-tion is an extremely complex topic, both technically and ideologically. It may beargued that any proxy system provides some measure of anonymity guaranteesbecause many users are aggregated onto single proxies. However, there exists afundamental distrust of any proxy distribution system that persists user informa-tion.Many trust-based systems are proposed yet few are adopted in practice. Sim-pler systems such as lightweight proxy distribution and decoy routing are adoptedwidely, and it may not only be a result of their implementation simplicity. Perhaps,the foundation of trust-based systems goes against the ethos of anonymity. As ourprivacy concerns grow, we look for more varieties of systems with demonstrableprivacy guarantees that align with our privacy needs. The wider the adoption ofsuch systems, the more privacy guarantees we can give. The more honest users inthe system, the less of an impact that attackers can have. It requires the effort ofeveryone to hide vulnerable parties in the crowd. If we volunteer our resources andparticipate in the privacy community, it is possible.48Bibliography[1] Research problems: Ten ways to discover Tor bridges, 2019 (accessed April9, 2019). URL https://blog.torproject.org/research-problems-ten-ways-discover-tor-bridges. →page 6[2] BridgeDB, 2019 (accessed April 9, 2019). URLhttps://bridges.torproject.org. → page 2[3] OONI Project, 2019 (accessed April 9, 2019). URLhttps://blog.torproject.org/tor-heart-ooni-project. → page 2[4] Domain Fronting Is Critical to the Open Web, 2019 (accessed April 9,2019). URL https://blog.torproject.org/domain-fronting-critical-open-web.→ page 45[5] Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal. Balanced allocations.SIAM journal on computing, 29(1):180–200, 1999. → page 9[6] P. Berenbrink, A. Czumaj, A. Steger, and B. Vocking. Balanced allocations:the heavily loaded case. In Annual ACM Symposium on Theory ofComputing: Proceedings of the thirty-second annual ACM symposium onTheory of computing, volume 21, pages 745–754, 2000. → page 10[7] I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong. Freenet: A distributedanonymous information storage and retrieval system. In Designing privacyenhancing technologies, pages 46–66. Springer, 2001. → page 40[8] H. Corrigan-Gibbs and B. Ford. Dissent: accountable anonymous groupmessaging. In Proceedings of the 17th ACM conference on Computer andcommunications security, pages 340–350. ACM, 2010. → page 40[9] D. Fifield. Threat modeling and circumvention of Internet censorship. PhDthesis, University of California, Berkeley, Dec. 2017. URLhttps://www.bamsoftware.com/papers/thesis/. → pages 2, 4549[10] D. Fifield and L. Tsai. Censors’ delay in blocking circumvention proxies.arXiv preprint arXiv:1605.08808, 2016. → page 41[11] P. Flajolet, D. Gardy, and L. Thimonier. Birthday paradox, couponcollectors, caching algorithms and self-organizing search. Discrete AppliedMathematics, 39(3):207–229, 1992. → pages 4, 7, 8[12] G. H. Gonnet. Expected length of the longest probe sequence in hash codesearching. Journal of the ACM (JACM), 28(2):289–304, 1981. → page 9[13] X. Jiang, J. Shi, Q. Tan, W. Zhang, X. Wang, and M. Chen. Proxisch: Anoptimization approach of large-scale unstable proxy servers scheduling.World Academy of Science, Engineering and Technology, InternationalJournal of Computer, Electrical, Automation, Control and InformationEngineering, 10(6):1149–1154, 2016. → page 46[14] S. Khattak, T. Elahi, L. Simon, C. M. Swanson, S. J. Murdoch, andI. Goldberg. Sok: Making sense of censorship resistance systems.Proceedings on Privacy Enhancing Technologies, 2016(4):37–61, 2016. →page 40[15] Y. A. Lateef. Repository of scales and melodic patterns. Fana Music, 1981.→ page 12[16] Z. Ling, J. Luo, W. Yu, M. Yang, and X. Fu. Tor bridge discovery: extensiveanalysis and large-scale empirical evaluation. IEEE Transactions on Paralleland Distributed Systems, 26(7):1887–1899, 2015. → pages 11, 41[17] M. Mahdian. Fighting censorship with algorithms. In InternationalConference on Fun with Algorithms, pages 296–306. Springer, 2010. →page 42[18] D. McCoy, J. A. Morales, and K. Levchenko. Proximax: A measurementbased system for proxies dissemination. Financial Cryptography and DataSecurity, 5(9):10, 2011. → page 42[19] M. Mitzenmacher and E. Upfal. Probability and computing: Randomizedalgorithms and probabilistic analysis. Cambridge university press, 2005. →pages 8, 9[20] M. D. Mitzenmacher. The power of two random choices in randomized loadbalancing. PhD thesis, PhD thesis, Graduate Division of the University ofCalifornia at Berkley, 1996. → pages 9, 3150[21] R. Motwani and P. Raghavan. Randomized algorithms. Cambridgeuniversity press, 1995. → page 6[22] A. N. Myers and H. S. Wilf. Some new aspects of the coupon collector’sproblem. SIAM review, 48(3):549–565, 2006. → page 8[23] M. K. Reiter and A. D. Rubin. Anonymous web transactions with crowds.Communications of the ACM, 42(2):32–48, 1999. → page 41[24] J. van den Hooff, D. Lazar, M. Zaharia, and N. Zeldovich. Vuvuzela:Scalable private messaging resistant to traffic analysis. In Proceedings of the25th Symposium on Operating Systems Principles, SOSP ’15, pages137–152, New York, NY, USA, 2015. ACM. ISBN 978-1-4503-3834-9.doi:10.1145/2815400.2815417. URLhttp://doi.acm.org/10.1145/2815400.2815417. → page 40[25] Q. Wang, Z. Lin, N. Borisov, and N. Hopper. rbridge: User reputation basedtor bridge distribution with privacy preservation. In NDSS, 2013. → pages2, 5, 43[26] E. Wustrow, S. Wolchok, I. Goldberg, and J. A. Halderman. Telex:Anticensorship in the network infrastructure. In USENIX SecuritySymposium, 2011. → page 45[27] W. Xu and A. K. Tang. A generalized coupon collector problem. Journal ofApplied Probability, 48(4):1081–1094, 2011. → pages 33, 45[28] M. Zamani, J. Saia, and J. Crandall. Torbricks: Blocking-resistant tor bridgedistribution. In International Symposium on Stabilization, Safety, andSecurity of Distributed Systems, pages 426–440. Springer, 2017. → page 4151
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
The unbalancing act : proxy preservation for censorship resistance systems
Text