Tracking Dynamic Sources of Malicious Activity at Internet-Scale
journal contributionposted on 01.12.2005 by Shoba Venkataraman, Avrim Blum, Dawn Song, Subhabrata Sen, Oliver Spatscheck
Any type of content formally published in an academic journal, usually following a peer-review process.
We formulate and address the problem of discovering dynamic malicious regions on the Internet. We model this problem as one of adaptively pruning a known decision tree, but with additional challenges: (1) severe space requirements, since the underlying decision tree has over 4 billion leaves, and (2) a changing target function, since malicious activity on the Internet is dynamic. We present a novel algorithm that addresses this problem, by putting together a number of different “experts” algorithms and online paging algorithms. We prove guarantees on our algorithm’s performance as a function of the best possible pruning of a similar size, and our experiments show that our algorithm achieves high accuracy on large real-world data sets, with significant improvements over existing approaches.