Domain name system (“DNS”) resolvers are typically used to translate domain names meaningful to humans into Internet protocol (“IP”) addresses meaningful to computers in order to locate a particular device worldwide. DNS resolvers typically query a DNS server to translate the full domain name into an IP address. Domain names contain one or more segments (“labels”) delimited by periods that are translated from right (“top level domain”) to left (“low level domain” or “sub domain”). For example, in a full domain name of google.co.uk, the top level domain is “.uk,” the sub domain is “.co.uk”, and the full domain name is “google.co.uk.” When a DNS resolver attempts to resolve a full domain name, it typically queries a root server first. If the root server is authoritative for the top level domain (e.g., “.uk”), the root server will return the IP address of a server capable of resolving the next sub domain (e.g., “.co.uk”). However, if the root server is not authoritative for that particular domain, the root server will refer the query to other authoritative name servers that should be capable of providing a reference or even capable of resolving the entire domain name. In turn, the name server delegated by the root server will also refer the query to yet another name server authoritative for the next sub domain level. This course continues until the full domain name is resolved (e.g., “google.co.uk”). Thus, queries are often forwarded to multiple authoritative DNS servers. However, it is also possible to resolve the full domain name by querying only one authoritative server.
The open and distributed architecture of DNS and its employment of the user datagram protocol (“UDP”) make DNS susceptible to various forms of attacks from hackers. Recursive DNS resolvers are especially at risk, since they do not restrict incoming packets to a set of allowed source IP addresses. “Spoofing” is a known hacking technique that aims to redirect users from legitimate websites and domain names to malicious ones. A “Kaminsky attack” is one kind of spoofing tactic that occurs by transmitting a series of queries to the recursive DNS resolver. If the answers are not in the resolver's cache, the resolver will send the queries to other authoritative name servers. Attackers then flood spoofing answers to the resolver that lead to entry of invalid records in the resolver's cache. If a spoofing packet matching the resolver's query arrives at the resolver earlier than valid answers from authoritative name servers, the resolver will direct the query to hacker controlled name servers.
Various solutions for averting spoofing attacks have been tried in the past including prepending nonce labels to DNS queries. One solution attempts to gather DNS resolver logs that include as many hostnames as possible over a period of time (e.g., one month). DNS logs traditionally contain queries and responses to most hostnames. Once the logs are gathered, the following steps are followed: A root DNS server is queried to provide the name servers for a particular zone of interest (e.g., .org, .uk, .jp, .us, .com, etc.). Once the root DNS server replies with a list of name servers, the DNS logs are scanned to find all responses from the list of name servers that returned “authoritative” answers, excluding wildcard responses and bogus responses. For each name server returned, it is determined whether nonce labels are prepended for queries sent to this name server and what queries should not be prepended with nonce labels. Unfortunately, nonce labels cannot be prepended to every query. Rather, nonce labels are prepended to queries that result in a referral to another name server.