We improve the state of the art of behavior-based tracking, an unobtrusive technique that allows observers on the Internet to monitor user activities over long periods of time – in spite of changing IP addresses. Our technique uses semi-supervised machine learning, which allows observers to track users without the need for multiple labeled training sessions. We present evaluation results obtained on a realistic dataset that contains the DNS traffic of 3,800 users. Given the traffic of one week, our simulated observers can link the sessions of up to 87% of the users with surprisingly little effort. Our results indicate that observers can leverage unlabeled sessions to increase the robustness of existing tracking techniques. This makes it more difficult for users to protect their privacy on the Internet.