Abstract

The Internet is afflicted by unwelcome “requests”, defined broadly as claims on a scarce resource, such as a server’s CPU (in the case of spurious traffic whose purpose is to deny service) or a human’s attention (in the case of spam). Traditional responses to these problems apply heuristics: they try to identify “bad” requests based on their content (e.g., in the way that spam filters analyze an email’s text). This talk argues that heuristics are inherently gameable and that defenses should instead aim to allocate resources proportionally to all clients (so if, say, 10% of the requesters of some scarce resource are “bad”, those clients should be limited to 10% of the resources).

To meet this goal, this talk presents two systems. The first is a denial-of-service mitigation in which clients are encouraged to automatically send more traffic to a besieged server. The “good” clients can thereby compete equally with the “bad” ones. The second is a distributed system for enforcing per-sender email quotas to control spam. This system scales to a workload of millions of requests per second, tolerates arbitrary faults in its constituent hosts, and resists a variety of attacks. It achieves this fault-tolerance despite storing only one copy (roughly) of any given datum and, ultimately, does a fairly large job with fairly little mechanism.