Despite considerable attention from both the academic and commercial communities, denial-of-service (DoS) attacks represent a growing threat to network administrators and service providers. A large number of proposed DoS countermeasures attempt to detect an attack in-progress and filter out the DoS attack packets. These techniques often depend on the instantiation of sophisticated routing mechanisms and the ability to differentiate between normal and malicious messages. Unfortunately, neither of the se prerequisites may be practical or possible. We propose and evaluate a defense against DoS attacks which we call selective bin verification. The technique shows promise against large DoS attacks, even when attack packets are able to permeate the network and reach the target of their attack. We explore the effectiveness of our technique by implementing an experimental testbed in which selective bin verification is successfully used to protect against DoS attacks. We formally describe the mathematical properties of our approach and delineate "tuning" parameters for defending against various attacks.