{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T21:09:05Z","timestamp":1773522545941,"version":"3.50.1"},"reference-count":34,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"1","license":[{"start":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T00:00:00Z","timestamp":1637366400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Tor has millions of daily users seeking privacy while browsing the Internet. It has thousands of relays to route users\u2019 packets while anonymizing their sources and destinations. Users choose relays to forward their traffic according to probability distributions published by the <jats:italic>Tor authorities<\/jats:italic>. The authorities generate these probability distributions based on estimates of the capacities of the relays. They compute these estimates based on the bandwidths of probes sent to the relays. These estimates are necessary for better load balancing. Unfortunately, current methods fall short of providing accurate estimates leaving the network underutilized and its capacities unfairly distributed between the users\u2019 paths. We present <jats:italic>MLEFlow<\/jats:italic>, a maximum likelihood approach for estimating relay capacities for optimal load balancing in Tor. We show that <jats:italic>MLEFlow<\/jats:italic> generalizes a version of Tor capacity estimation, <jats:italic>TorFlow<\/jats:italic>-<jats:italic>P<\/jats:italic>, by making better use of measurement history. We prove that the mean of our estimate converges to a small interval around the actual capacities, while the variance converges to zero. We present two versions of <jats:italic>MLEFlow<\/jats:italic>: <jats:italic>MLEFlow<\/jats:italic>-<jats:italic>CF<\/jats:italic>, a closed-form approximation of the MLE and <jats:italic>MLEFlow<\/jats:italic>-<jats:italic>Q<\/jats:italic>, a discretization and iterative approximation of the MLE which can account for noisy observations. We demonstrate the practical benefits of <jats:italic>MLEFlow<\/jats:italic> by simulating it using a flow-based Python simulator of a full Tor network and packet-based Shadow simulation of a scaled down version. In our simulations <jats:italic>MLEFlow<\/jats:italic> provides significantly more accurate estimates, which result in improved user performance, with median download speeds increasing by 30%.<\/jats:p>","DOI":"10.2478\/popets-2022-0005","type":"journal-article","created":{"date-parts":[[2021,11,21]],"date-time":"2021-11-21T02:43:19Z","timestamp":1637462599000},"page":"75-104","source":"Crossref","is-referenced-by-count":3,"title":["MLEFlow: Learning from History to Improve Load Balancing in Tor"],"prefix":"10.56553","volume":"2022","author":[{"given":"Hussein","family":"Darir","sequence":"first","affiliation":[{"name":"All authors with the University of Illinois at Urbana-Champaign"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hussein","family":"Sibai","sequence":"additional","affiliation":[{"name":"All authors with the University of Illinois at Urbana-Champaign"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chin-Yu","family":"Cheng","sequence":"additional","affiliation":[{"name":"All authors with the University of Illinois at Urbana-Champaign"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikita","family":"Borisov","sequence":"additional","affiliation":[{"name":"All authors with the University of Illinois at Urbana-Champaign"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Geir","family":"Dullerud","sequence":"additional","affiliation":[{"name":"All authors with the University of Illinois at Urbana-Champaign"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sayan","family":"Mitra","sequence":"additional","affiliation":[{"name":"All authors with the University of Illinois at Urbana-Champaign"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"35752","published-online":{"date-parts":[[2021,11,20]]},"reference":[{"key":"2022062314365133570_j_popets-2022-0005_ref_001","doi-asserted-by":"crossref","unstructured":"[1] M. AlSabah and I. Goldberg, \u201cPerformance and security improvements for Tor: A survey,\u201d ACM Computing Surveys (CSUR), vol. 49, no. 2, p. 32, 2016.10.1145\/2946802","DOI":"10.1145\/2946802"},{"key":"2022062314365133570_j_popets-2022-0005_ref_002","doi-asserted-by":"crossref","unstructured":"[2] R. Annessi and M. Schmiedecker, \u201cNavigator: Finding faster paths to anonymity,\u201d in 2016 IEEE European Symposium on Security and Privacy (EuroS P), 2016, pp. 214\u2013226.10.1109\/EuroSP.2016.26","DOI":"10.1109\/EuroSP.2016.26"},{"key":"2022062314365133570_j_popets-2022-0005_ref_003","doi-asserted-by":"crossref","unstructured":"[3] K. Bauer, D. McCoy, D. Grunwald, T. Kohno, and D. Sicker, \u201cLow-resource routing attacks against Tor,\u201d in Proceedings of the 2007 ACM Workshop on Privacy in Electronic Society (WPES), 2007, pp. 11\u201320.10.1145\/1314333.1314336","DOI":"10.1145\/1314333.1314336"},{"key":"2022062314365133570_j_popets-2022-0005_ref_004","unstructured":"[4] H. Darir, \u201cmleflow,\u201d 2021. [Online]. Available: https:\/\/github.com\/hdarir2\/mleflow"},{"key":"2022062314365133570_j_popets-2022-0005_ref_005","doi-asserted-by":"crossref","unstructured":"[5] H. Darir, H. Sibai, N. Borisov, G. Dullerud, and S. Mitra, \u201cTightrope: Towards optimal load-balancing of paths in anonymous networks,\u201d in Proceedings of the 2018 Workshop on Privacy in the Electronic Society, 2018, pp. 76\u201385.10.1145\/3267323.3268953","DOI":"10.1145\/3267323.3268953"},{"key":"2022062314365133570_j_popets-2022-0005_ref_006","unstructured":"[6] R. Dingledine, \u201cThe lifecycle of a new relay,\u201d The Tor Project Blog, https:\/\/blog.torproject.org\/lifecycle-new-relay, Sep. 2013."},{"key":"2022062314365133570_j_popets-2022-0005_ref_007","unstructured":"[7] \u2014\u2014, \u201cTor security advisory: \u201crelay early\u201d traffic confirmation attack,\u201d https:\/\/blog.torproject.org\/tor-security-advisory-relay-early-traffic-confirmation-attack, Jul. 2014, tor Blog."},{"key":"2022062314365133570_j_popets-2022-0005_ref_008","unstructured":"[8] R. Dingledine and N. Mathewson, \u201cAnonymity loves company: Usability and the network effect.\u201d in WEIS, 2006."},{"key":"2022062314365133570_j_popets-2022-0005_ref_009","doi-asserted-by":"crossref","unstructured":"[9] R. Dingledine, N. Mathewson, and P. F. Syverson, \u201cTor: The second-generation onion router,\u201d in USENIX Security Symposium. USENIX, 2004, pp. 303\u2013320.10.21236\/ADA465464","DOI":"10.21236\/ADA465464"},{"key":"2022062314365133570_j_popets-2022-0005_ref_010","doi-asserted-by":"crossref","unstructured":"[10] M. Edman and P. Syverson, \u201cAs-awareness in tor path selection,\u201d in Proceedings of the 16th ACM conference on Computer and communications security, 2009, pp. 380\u2013389.10.1145\/1653662.1653708","DOI":"10.1145\/1653662.1653708"},{"key":"2022062314365133570_j_popets-2022-0005_ref_011","unstructured":"[11] D. Goulet and M. Perry, \u201cMake relays report when they are overloaded,\u201d Tor Proposal 328, https:\/\/gitlab.torproject.org\/tpo\/core\/torspec\/-\/blob\/master\/proposals\/328-relay-overload-report.md, Nov. 2020."},{"key":"2022062314365133570_j_popets-2022-0005_ref_012","unstructured":"[12] A. Greubel, A. Dmitrienko, and S. Kounev, \u201cSmartor: Smarter tor with smart contracts: Improving resilience of topology distribution in the tor network,\u201d in Proceedings of the 34th Annual Computer Security Applications Conference, ACSAC 2018, San Juan, PR, USA, December 03-07, 2018. ACM, 2018, pp. 677\u2013691. [Online]. Available: https:\/\/doi.org\/10.1145\/3274694.327472210.1145\/3274694.3274722"},{"key":"2022062314365133570_j_popets-2022-0005_ref_013","doi-asserted-by":"crossref","unstructured":"[13] S. Herbert, S. J. Murdoch, and E. Punskaya, \u201cOptimising node selection probabilities in multi-hop m\/d\/1 queuing networks to reduce latency of tor,\u201d Electronics letters, vol. 50, no. 17, pp. 1205\u20131207, 2014.","DOI":"10.1049\/el.2014.2136"},{"key":"2022062314365133570_j_popets-2022-0005_ref_014","unstructured":"[14] R. Jansen, K. Bauer, N. Hopper, and R. Dingledine, \u201cMethodically modeling the tor network,\u201d in 5th Workshop on Cyber Security Experimentation and Test (CSET\u201912). Bellevue, WA: USENIX Association, Aug. 2012. [Online]. Available: https:\/\/www.usenix.org\/conference\/cset12\/workshop-program\/presentation\/Jansen"},{"key":"2022062314365133570_j_popets-2022-0005_ref_015","doi-asserted-by":"crossref","unstructured":"[15] R. Jansen and N. Hopper, \u201cShadow: Running Tor in a box for accurate and efficient experimentation,\u201d in Proceedings of the 19th Symposium on Network and Distributed System Security (NDSS), 2012.10.21236\/ADA559181","DOI":"10.21236\/ADA559181"},{"key":"2022062314365133570_j_popets-2022-0005_ref_016","doi-asserted-by":"crossref","unstructured":"[16] R. Jansen and A. Johnson, \u201cOn the accuracy of Tor bandwidth estimation,\u201d in Passive and Active Measurement Conference (PAM), 2021.10.1007\/978-3-030-72582-2_28","DOI":"10.1007\/978-3-030-72582-2_28"},{"key":"2022062314365133570_j_popets-2022-0005_ref_017","unstructured":"[17] R. Jansen, T. Vaidya, and M. Sherr, \u201cPoint break: a study of bandwidth denial-of-service attacks against Tor,\u201d in 28th USENIX Security Symposium, 2019, pp. 1823\u20131840."},{"key":"2022062314365133570_j_popets-2022-0005_ref_018","doi-asserted-by":"crossref","unstructured":"[18] A. Johnson, R. Jansen, N. Hopper, A. Segal, and P. Syverson, \u201cPeerFlow: Secure load balancing in Tor,\u201d Proceedings on Privacy Enhancing Technologies, vol. 2017, no. 2, pp. 74\u201394, 2017.","DOI":"10.1515\/popets-2017-0017"},{"key":"2022062314365133570_j_popets-2022-0005_ref_019","unstructured":"[19] juga, \u201cHow bandwidth scanners monitor the Tor network,\u201d Tor Project Blog, https:\/\/blog.torproject.org\/aggregation-feed-types\/sbws, Apr. 2019."},{"key":"2022062314365133570_j_popets-2022-0005_ref_020","unstructured":"[20] M. G. Kendall, A. Stuart, and J. K. Ord, Kendall\u2019s Advanced Theory of Statistics. USA: Oxford University Press, Inc., 1987."},{"key":"2022062314365133570_j_popets-2022-0005_ref_021","unstructured":"[21] K. Loesing, M. Perry, and A. Gibson, \u201cBandwidth scanner specification,\u201d https:\/\/gitweb.torproject.org\/torflow.git\/tree\/NetworkScanners\/BwAuthority\/README.spec.txt, 2011."},{"key":"2022062314365133570_j_popets-2022-0005_ref_022","unstructured":"[22] M. Perry, \u201cTorFlow: Tor network analysis,\u201d in Proceedings of the 2nd Workshop on Hot Topics in Privacy Enhancing Technologies (HotPETs), 2009, pp. 1\u201314."},{"key":"2022062314365133570_j_popets-2022-0005_ref_023","unstructured":"[23] R. Snader and N. Borisov, \u201cEigenSpeed: Secure peer-to-peer bandwidth evaluation,\u201d in 8th International Workshop on Peer-To-Peer Systems, R. Rodrigues and K. Ross, Eds. Berkeley, CA, USA: USENIX Association, Apr. 2009."},{"key":"2022062314365133570_j_popets-2022-0005_ref_024","doi-asserted-by":"crossref","unstructured":"[24] \u2014\u2014, \u201cImproving security and performance in the Tor network through tunable path selection,\u201d IEEE Transactions on Dependable and Secure Computing, vol. 8, no. 5, pp. 728\u2013741, 2011.10.1109\/TDSC.2010.40","DOI":"10.1109\/TDSC.2010.40"},{"key":"2022062314365133570_j_popets-2022-0005_ref_025","unstructured":"[25] The Tor Project, \u201cDeploying the simple bandwidth scanner,\u201d https:\/\/sbws.readthedocs.io\/en\/latest\/DEPLOY.html, 2018."},{"key":"2022062314365133570_j_popets-2022-0005_ref_026","unstructured":"[26] \u2014\u2014, \u201cDifferences between Torflow and sbws,\u201d https:\/\/tpo.pages.torproject.net\/network-health\/sbws\/differences.html, 2020."},{"key":"2022062314365133570_j_popets-2022-0005_ref_027","unstructured":"[27] \u2014\u2014, \u201cTor directory protocol, version 3,\u201d https:\/\/gitweb.torproject.org\/torspec.git\/tree\/dir-spec.txt, 2020."},{"key":"2022062314365133570_j_popets-2022-0005_ref_028","unstructured":"[28] \u2014\u2014, \u201cTor metrics: Servers,\u201d https:\/\/metrics.torproject.org\/networksize.html, 2020."},{"key":"2022062314365133570_j_popets-2022-0005_ref_029","unstructured":"[29] \u2014\u2014, \u201cTor metrics: Users,\u201d https:\/\/metrics.torproject.org\/userstats-relay-country.html, 2020."},{"key":"2022062314365133570_j_popets-2022-0005_ref_030","unstructured":"[30] F. Thill, \u201cHidden service tracking detection and bandwidth cheating in Tor anonymity network,\u201d Ph.D. dissertation, University of Luxembourg, 2014."},{"key":"2022062314365133570_j_popets-2022-0005_ref_031","doi-asserted-by":"crossref","unstructured":"[31] M. Traudt, R. Jansen, and A. Johnson, \u201cFlashflow: A secure speed test for tor,\u201d 2020.10.1109\/ICDCS51616.2021.00044","DOI":"10.1109\/ICDCS51616.2021.00044"},{"key":"2022062314365133570_j_popets-2022-0005_ref_032","doi-asserted-by":"crossref","unstructured":"[32] T. Wang, K. Bauer, C. Forero, and I. Goldberg, \u201cCongestion-aware path selection for Tor,\u201d in International Conference on Financial Cryptography and Data Security, 2012, pp. 98\u2013113.10.1007\/978-3-642-32946-3_9","DOI":"10.1007\/978-3-642-32946-3_9"},{"key":"2022062314365133570_j_popets-2022-0005_ref_033","unstructured":"[33] P. Winter, R. Ensafi, K. Loesing, and N. Feamster, \u201cIdentifying and characterizing sybils in the tor network,\u201d in 25th USENIX Security Symposium, 2016, pp. 1169\u20131185."},{"key":"2022062314365133570_j_popets-2022-0005_ref_034","doi-asserted-by":"crossref","unstructured":"[34] M. K. Wright, M. Adler, B. N. Levine, and C. Shields, \u201cThe predecessor attack: An analysis of a threat to anonymous communications systems,\u201d ACM Transactions on Information and System Security (TISSEC), vol. 7, no. 4, pp. 489\u2013522, 2004.10.1145\/1042031.1042032","DOI":"10.1145\/1042031.1042032"}],"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.sciendo.com\/pdf\/10.2478\/popets-2022-0005","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T16:31:50Z","timestamp":1658334710000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2022\/popets-2022-0005.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,20]]},"references-count":34,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,11,20]]},"published-print":{"date-parts":[[2022,1,1]]}},"alternative-id":["10.2478\/popets-2022-0005"],"URL":"https:\/\/doi.org\/10.2478\/popets-2022-0005","relation":{},"ISSN":["2299-0984"],"issn-type":[{"value":"2299-0984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,20]]}}}