Behavior-based tracking: Exploiting characteristic patterns in DNS traffic

We review and evaluate three techniques that allow a passive adversary to track users who have dynamic IP addresses based on characteristic behavioral patterns, i.e., without cookies or similar techniques. For this purpose we consider 1-Nearest-Neighbor classifiers, a Multinomial Naïve Bayes classifier and pattern mining techniques based on the criteria support and lift.For evaluation we focus on the case of a curious DNS resolver. Therefore, we analyze the effectiveness of the techniques using a common, large-scale dataset that contains the DNS queries issued by more than 3600 users over the course of two months. We find that behavior-based tracking is feasible: The best technique can link up to 85.4% of the surfing sessions of all users on a day-to-day basis. Moreover, for tracking to be effective only the most significant features or the most popular hostnames have to be considered.Our results indicate that users can degrade accuracy by changing their IP addresses more frequently, e.g., every few minutes. On the other hand, we find that the previously proposed DNS “range query” obfuscation techniques cannot prevent tracking reliably.Our findings are not limited to DNS traffic. Behavior-based tracking can be implemented by any adversary that has access to the web requests issued by users or their machines.