The Domain Name System (DNS) is a critical element of the Internet infrastructure. Even a small part of the DNS infrastructure being unavailable for a very short period of time could potentially upset the entire Internet and is thus totally unacceptable. Unfortunately, because DNS queries and responses are mostly UDP-based, it is vulnerable to spoofing-based denial of service (DoS) attacks, which are difficult to defeat without incurring significant collateral damage. The key to thwart this type of DoS attacks is spoof detection, which enables selective discarding of spoofed DNS requests without jeopardizing the quality of service to legitimate requests. This paper presents spoof detection strategies for protecting DNS servers from DoS attacks. These strategies create some form of cookies for a DNS server to check if each incoming request is indeed from where the request packet says it is from. We have implemented them as a firewall module called DNS guard. Measurements on the current DNS guard prototype show that it can deliver up to 80K requests/sec to legitimate users in the presence of DoS attacks at the rate of 250K requests/sec.