In this paper we study the structure of criminal networks, groups of related malicious infrastructures that work in concert to provide hosting for criminal activities. We develop a method to construct a graph of relationships between malicious hosts and identify the underlying criminal networks, using historic assignments in the DNS. We also develop methods to analyze these networks to identify general structural trends and devise strategies for effective remediation through takedowns. We then apply these graph construction and analysis algorithms to study the general threat landscape, as well as four cases of sophisticated criminal networks. Our results indicate that in many cases, criminal networks can be taken down by de-registering as few as five domain names, removing critical communication links. In cases of sophisticated criminal networks, we show that our analysis techniques can identify hosts that are critical to the network’s functionality and estimate the impact of performing network takedowns in remediating the threats. In one case, disabling 20% of a criminal network’s hosts would reduce the overall volume of successful DNS lookups to the criminal network by as much as 70%. This measure can be interpreted as an estimate of the decrease in the number of potential victims reaching the criminal network that would be caused by such a takedown strategy.