gPath: A game-theoretic path selection algorithm to protect Tor's anonymity

In this paper, we address the problem of defending against entry-exit linking attacks in Tor, a popular anonymous communication system. We formalize the problem as a repeated non-cooperative game between the defender and the adversary (i.e., controller of the compromised Tor nodes to carry out entry-exit linking attacks). Given the current path selection algorithm of Tor, we derive an optimal attack strategy for the adversary according to its utility function, followed by an optimal defensive strategy against this attack. We then repeat such interactions for three additional times, leading to three design principles, namely stratified path selection, bandwidth order selection, and adaptive exit selection. We further develop gPath, a path selection algorithm that integrates all three principles to significantly reduce the success probability of linking attacks. Using a combination of theoretical analysis and experimental studies on real-world Tor data, we demonstrate the superiority of our algorithm over the existing ones.