Tradeoffs between anonymity and quality of services in data networking and signaling games
Abhishek Mishra · 2015
Timing analysis has long been used to compromise users’ anonymity in networks. Even when data is encrypted, an adversary can track flows from sources to the corresponding destinations by merely using the correlation between the inter-packet timing on incoming and outgoing streams at intermediate routers. Anonymous network systems, where users communicate without revealing their identities, rely on the idea of Chaum mixing to hide ‘networking information’. Chaum mixes are routers or proxy servers that randomly reorder the outgoing packets to prevent an eavesdropper from tracking the flow of packets. The effectiveness of such mixing strategies is, however, diminished under constraints on network Quality of Services (QoS)s such as memory, bandwidth, and fairness. In this work, two models for studying anonymity, packet based anonymity and flow based anonymity, are proposed to address these issues quantitatively and a trade-off between network constraints and achieved anonymity is studied. Packet based anonymity model is proposed to study the short burst traffic arrival models of users such as in web browsing. For packet based anonymity, an information theoretic investigation of mixes under memory constraint and fairness constraint is established. Specifically, for memory constrained mixes, the first single letter characterization of the maximum achievable anonymity for a mix serving two users with equal arrival rates is provided. Further, for two users with unequal arrival rates the anonymity is expressed as a solution to a series of finite recursive equations. In addition, for more than two users and arbitrary arrival rates, a lower bound on the convergence rate of anonymity is derived as buffer size increases and it is shown that under certain arrival configurations the lower bound is tight. The adverse effects of requirement of fairness in data networking on anonymous networking is also studied using the packet based anonymity model and a novel temporal fairness index is proposed to compare the tradeoff between fairness and achieved anonymity of three diverse and popular fairness paradigms: First Come First Serve, Fair Queuing and Proportional Method. It is shown that FCFS and Fair Queuing algorithms have little inherent anonymity. A significant improvement in anonymity is therefore achieved by relaxing the fairness paradigms. The analysis of the relaxed FCFS criterion, in particular, is accomplished by modeling the problem as a Markov Decision Process (MDP). The proportional method of scheduling, while avoided in networks today, is shown to significantly outperform the other fair scheduling algorithms in anonymity, and is proven to be asymptotically optimal as the buffer size of the scheduler is increased. Flow based anonymity model is proposed to study long streams traffic models of users such as inmedia streaming. A detection theoretic measure of anonymity is proposed to study the optimization