Defending Networked Resources Against Floods of Unwelcome Requests

Michael Walfish
Massachusetts Institute of Technology, Cambridge, MA,

The Internet is afflicted by "unwelcome requests", defined broadly as spurious claims on scarce resources. For example, the CPU and other resources at a server are targets of denial-of-service (DoS) attacks. Another example is spam (i.e., unsolicited bulk email); here, the resource is human attention. Absent any defense, a very small number of attackers can claim a very large fraction of the scarce resources.

Traditional responses identify "bad" requests based on content (for example, spam filters analyze email text and embedded URLs). We argue that such approaches are inherently gameable because motivated attackers can make "bad" requests look "good". Instead, defenses should aim to allocate resources proportionally (so if 10% of the requesters are "bad", they should be limited to 10% of the scarce resources).

To meet this goal, we present the design, implementation, analysis, and experimental evaluation of two systems. The first, speak-up, defends servers against application-level denial-of-service by encouraging all clients to automatically send more traffic. The "good" clients can thereby compete equally with the "bad" ones. Experiments with an implementation of speak-up indicate that it allocates a server's resources in rough proportion to clients' upload bandwidths, which is the intended result.

The second system, DQE, controls spam with per-sender email quotas. Under DQE, senders attach stamps to emails. Receivers communicate with a well-known, untrusted enforcer to verify that stamps are fresh and to cancel stamps to prevent reuse. The enforcer is distributed over multiple hosts and is designed to tolerate arbitrary faults in these hosts, resist various attacks, and handle hundreds of billions of messages daily (two or three million stamp checks per second). Our experimental results suggest that our implementation can meet these goals with only a few thousand PCs. The enforcer occupies a novel design point: a set of hosts implement a simple storage abstraction but avoid neighbor maintenance, replica maintenance, and mutual trust.

One connection between these systems is that DQE needs a DoS defense -- and can use speak-up. We reflect on this connection, on why we apply speak-up to DoS and DQE to spam, and, more generally, on what problems call for which solutions.

[PDF (1559KB)]