  Anonymous communication systems are subject to selective denial-of-service
(DoS) attacks. Selective DoS attacks lower anonymity as they force paths to be
rebuilt multiple times to ensure delivery which increases the opportunity for
more attack. In this paper we present a detection algorithm that filters out
compromised communication channels for one of the most widely used anonymity
networks, Tor. Our detection algorithm uses two levels of probing to filter out
potentially compromised tunnels. We perform probabilistic analysis and
extensive simulation to show the robustness of our detection algorithm. We also
analyze the overhead of our detection algorithm and show that we can achieve
satisfactory security guarantee for reasonable communication overhead (5% of
the total available Tor bandwidth in the worst case). Real world experiments
reveal that our detection algorithm provides good defense against selective DoS
attack.
