Networks of Hosts Implementing DNS are NP-Complete

Mak Kolybabi defends his MSc thesis on September 12 at the University of Manitoba, and will present it here in advance.

The Internet core protocols are the networking protocols that the Internet is built on, a subset of which are implemented on every device connected to the Internet. The specifications of these protocols can span dozens of documents, making accurately understanding and implementing them difficult. The Domain Name System is one of the Internet’s core protocols, providing a distributed, hierarchical database primarily intended to map between the names and addresses of hosts. Modern DNS contains a plethora of complex and interacting features, defined across a number of documents, evolving over the course of over thirty years. We show that a network of specially-configured hosts implementing a subset of DNS operate as logic gates. We then describe how such gates can communicate to form Boolean circuits. Finally, we discuss CSAT and NP-completeness and what our results mean for network security.

Mak Kolybabi is the founder of several community organizations and works in information security. Mak has a healthy interest in accessibility and an unhealthy interest in Emacs, neither of which he’ll cover in this talk. He is desperate to finish his Master’s degree.