Abstract: Worms are becoming more virulent at the same time as operating system improvements try to contain them.Recent research demonstrates several effective methods to detect and prevent randomly scanning worms from spreading [2, 13]. As a result, worm authors are looking for new ways to acquire vulnerable targets without relying on randomly scanning for them. It is often possible to find vulnerable web servers by sending carefully crafted queries to search engines. Search worms1 automate this approach and spread by using popular search engines to find new attack vectors. These worms not only put significant load on search engines, they also evade detection mechanisms that assume random scanning. From the point of view of a search engine, signatures against search queries are only a temporary measure as many different search queries lead to the same results. In this paper, we present our experience with search worms and a framework that allows search engines to quickly detect new worms and take automatic countermeasures. We argue that signature-based filtering of search queries is ill-suited for protecting against search worms and show how we prevent worm propagation without relying on query signatures. We illustrate our approach with measurements and numeric simulations.