1. bookVolume 2022 (2022): Issue 1 (January 2022)
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

MLEFlow: Learning from History to Improve Load Balancing in Tor

Published Online: 20 Nov 2021
Page range: 75 - 104
Received: 31 May 2021
Accepted: 16 Sep 2021
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
Abstract

Tor has millions of daily users seeking privacy while browsing the Internet. It has thousands of relays to route users’ packets while anonymizing their sources and destinations. Users choose relays to forward their traffic according to probability distributions published by the Tor authorities. 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’ paths. We present MLEFlow, a maximum likelihood approach for estimating relay capacities for optimal load balancing in Tor. We show that MLEFlow generalizes a version of Tor capacity estimation, TorFlow-P, 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 MLEFlow: MLEFlow-CF, a closed-form approximation of the MLE and MLEFlow-Q, a discretization and iterative approximation of the MLE which can account for noisy observations. We demonstrate the practical benefits of MLEFlow 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 MLEFlow provides significantly more accurate estimates, which result in improved user performance, with median download speeds increasing by 30%.

Keywords

[1] M. AlSabah and I. Goldberg, “Performance and security improvements for Tor: A survey,” ACM Computing Surveys (CSUR), vol. 49, no. 2, p. 32, 2016. Search in Google Scholar

[2] R. Annessi and M. Schmiedecker, “Navigator: Finding faster paths to anonymity,” in 2016 IEEE European Symposium on Security and Privacy (EuroS P), 2016, pp. 214–226. Search in Google Scholar

[3] K. Bauer, D. McCoy, D. Grunwald, T. Kohno, and D. Sicker, “Low-resource routing attacks against Tor,” in Proceedings of the 2007 ACM Workshop on Privacy in Electronic Society (WPES), 2007, pp. 11–20. Search in Google Scholar

[4] H. Darir, “mleflow,” 2021. [Online]. Available: https://github.com/hdarir2/mleflow Search in Google Scholar

[5] H. Darir, H. Sibai, N. Borisov, G. Dullerud, and S. Mitra, “Tightrope: Towards optimal load-balancing of paths in anonymous networks,” in Proceedings of the 2018 Workshop on Privacy in the Electronic Society, 2018, pp. 76–85. Search in Google Scholar

[6] R. Dingledine, “The lifecycle of a new relay,” The Tor Project Blog, https://blog.torproject.org/lifecycle-new-relay, Sep. 2013. Search in Google Scholar

[7] ——, “Tor security advisory: “relay early” traffic confirmation attack,” https://blog.torproject.org/tor-security-advisory-relay-early-traffic-confirmation-attack, Jul. 2014, tor Blog. Search in Google Scholar

[8] R. Dingledine and N. Mathewson, “Anonymity loves company: Usability and the network effect.” in WEIS, 2006. Search in Google Scholar

[9] R. Dingledine, N. Mathewson, and P. F. Syverson, “Tor: The second-generation onion router,” in USENIX Security Symposium. USENIX, 2004, pp. 303–320. Search in Google Scholar

[10] M. Edman and P. Syverson, “As-awareness in tor path selection,” in Proceedings of the 16th ACM conference on Computer and communications security, 2009, pp. 380–389. Search in Google Scholar

[11] D. Goulet and M. Perry, “Make relays report when they are overloaded,” Tor Proposal 328, https://gitlab.torproject.org/tpo/core/torspec/-/blob/master/proposals/328-relay-overload-report.md, Nov. 2020. Search in Google Scholar

[12] A. Greubel, A. Dmitrienko, and S. Kounev, “Smartor: Smarter tor with smart contracts: Improving resilience of topology distribution in the tor network,” in Proceedings of the 34th Annual Computer Security Applications Conference, ACSAC 2018, San Juan, PR, USA, December 03-07, 2018. ACM, 2018, pp. 677–691. [Online]. Available: https://doi.org/10.1145/3274694.3274722 Search in Google Scholar

[13] S. Herbert, S. J. Murdoch, and E. Punskaya, “Optimising node selection probabilities in multi-hop m/d/1 queuing networks to reduce latency of tor,” Electronics letters, vol. 50, no. 17, pp. 1205–1207, 2014. Search in Google Scholar

[14] R. Jansen, K. Bauer, N. Hopper, and R. Dingledine, “Methodically modeling the tor network,” in 5th Workshop on Cyber Security Experimentation and Test (CSET’12). Bellevue, WA: USENIX Association, Aug. 2012. [Online]. Available: https://www.usenix.org/conference/cset12/workshop-program/presentation/Jansen Search in Google Scholar

[15] R. Jansen and N. Hopper, “Shadow: Running Tor in a box for accurate and efficient experimentation,” in Proceedings of the 19th Symposium on Network and Distributed System Security (NDSS), 2012. Search in Google Scholar

[16] R. Jansen and A. Johnson, “On the accuracy of Tor bandwidth estimation,” in Passive and Active Measurement Conference (PAM), 2021. Search in Google Scholar

[17] R. Jansen, T. Vaidya, and M. Sherr, “Point break: a study of bandwidth denial-of-service attacks against Tor,” in 28th USENIX Security Symposium, 2019, pp. 1823–1840. Search in Google Scholar

[18] A. Johnson, R. Jansen, N. Hopper, A. Segal, and P. Syverson, “PeerFlow: Secure load balancing in Tor,” Proceedings on Privacy Enhancing Technologies, vol. 2017, no. 2, pp. 74–94, 2017. Search in Google Scholar

[19] juga, “How bandwidth scanners monitor the Tor network,” Tor Project Blog, https://blog.torproject.org/aggregation-feed-types/sbws, Apr. 2019. Search in Google Scholar

[20] M. G. Kendall, A. Stuart, and J. K. Ord, Kendall’s Advanced Theory of Statistics. USA: Oxford University Press, Inc., 1987. Search in Google Scholar

[21] K. Loesing, M. Perry, and A. Gibson, “Bandwidth scanner specification,” https://gitweb.torproject.org/torflow.git/tree/NetworkScanners/BwAuthority/README.spec.txt, 2011. Search in Google Scholar

[22] M. Perry, “TorFlow: Tor network analysis,” in Proceedings of the 2nd Workshop on Hot Topics in Privacy Enhancing Technologies (HotPETs), 2009, pp. 1–14. Search in Google Scholar

[23] R. Snader and N. Borisov, “EigenSpeed: Secure peer-to-peer bandwidth evaluation,” in 8th International Workshop on Peer-To-Peer Systems, R. Rodrigues and K. Ross, Eds. Berkeley, CA, USA: USENIX Association, Apr. 2009. Search in Google Scholar

[24] ——, “Improving security and performance in the Tor network through tunable path selection,” IEEE Transactions on Dependable and Secure Computing, vol. 8, no. 5, pp. 728–741, 2011. Search in Google Scholar

[25] The Tor Project, “Deploying the simple bandwidth scanner,” https://sbws.readthedocs.io/en/latest/DEPLOY.html, 2018. Search in Google Scholar

[26] ——, “Differences between Torflow and sbws,” https://tpo.pages.torproject.net/network-health/sbws/differences.html, 2020. Search in Google Scholar

[27] ——, “Tor directory protocol, version 3,” https://gitweb.torproject.org/torspec.git/tree/dir-spec.txt, 2020. Search in Google Scholar

[28] ——, “Tor metrics: Servers,” https://metrics.torproject.org/networksize.html, 2020. Search in Google Scholar

[29] ——, “Tor metrics: Users,” https://metrics.torproject.org/userstats-relay-country.html, 2020. Search in Google Scholar

[30] F. Thill, “Hidden service tracking detection and bandwidth cheating in Tor anonymity network,” Ph.D. dissertation, University of Luxembourg, 2014. Search in Google Scholar

[31] M. Traudt, R. Jansen, and A. Johnson, “Flashflow: A secure speed test for tor,” 2020. Search in Google Scholar

[32] T. Wang, K. Bauer, C. Forero, and I. Goldberg, “Congestion-aware path selection for Tor,” in International Conference on Financial Cryptography and Data Security, 2012, pp. 98–113. Search in Google Scholar

[33] P. Winter, R. Ensafi, K. Loesing, and N. Feamster, “Identifying and characterizing sybils in the tor network,” in 25th USENIX Security Symposium, 2016, pp. 1169–1185. Search in Google Scholar

[34] M. K. Wright, M. Adler, B. N. Levine, and C. Shields, “The predecessor attack: An analysis of a threat to anonymous communications systems,” ACM Transactions on Information and System Security (TISSEC), vol. 7, no. 4, pp. 489–522, 2004. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo