Practical Comprehensive Bounds on Surreptitious Communication over DNS

TitlePractical Comprehensive Bounds on Surreptitious Communication over DNS
Publication TypeConference Paper
Year of Publication2013
AuthorsPaxson, V., Christodorescu M., Javed M., Rao J., Sailer R., Schales D., Stoecklin M. Ph., Thomas K., Venema W., & Weaver N.
Other Numbers3469

DNS queries represent one of the most common forms of network traffic, and likely the least blocked by sites. As such, DNS provides a highly attractive channel for attackers who wish to communicate surreptitiously across a network perimeter, and indeed a variety of tunneling toolkits exist. We develop a novel measurement procedure that fundamentally limits the amount of information that a domain can receive surreptitiously through DNS queries to an upper bound specified by a site’s security policy, with the exact setting representing a tradeoff between the scope of potential leakage versus the quantity of possible detections that a site’s analysts must investigate.

Rooted in lossless compression, our measurement procedure is free from false negatives. For example, we address conventional tunnels that embed the payload in the query names, tunnels that repeatedly query a fixed alphabet of domain names or varying query types, tunnels that embed information in query timing, and communication that employs combinations of these. In an analysis of 230 billion lookups from real production networks, our procedure detected 59 confirmed tunnels. For the enterprise datasets with lookups by individual clients, detecting surreptitious communication that exceeds 4 kB/day imposes an average analyst burden of 1–2 investigations/week.


Our thanks to Partha Bannerjee, Scott Campbell, HaixinDuan, Robin Sommer, and JamesWelcher for facilitatingsome of the data and processing required for this work.Our thanks too to Christian Rossow and the anonymousreviewers for their valuable comments.This work would not have been possible without thesupport of IBM’s Open Collaboration Research awardsprogram. In addition, elements of this work were supportedby the U.S. Army Research Office under MURIgrant W911NF-09-1-0553, and by the National ScienceFoundation under grants 1161799, 1223717, and1237265. Any opinions, findings, and conclusions orrecommendations expressed in this material are those ofthe authors and do not necessarily reflect the views of thesponsors. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors or originators and do not necessarily reflect the views of the National Science Foundation.

Bibliographic Notes

Proceedings of the 22nd USENIX Security Symposium, Washington, D.C.

Abbreviated Authors

V. Paxson, M. Christodorescu, M. Javed, J. Rao, R. Sailer, D. L. Schales, M. Ph. Stoecklin, K. Thomas, W. Venema, and N. Weaver

ICSI Research Group

Networking and Security

ICSI Publication Type

Article in conference proceedings