∗ Supported by the Israeli Ministry of Science.

The Internet has become a fertile ground for hostile activity. One of the simplest yet most effective attacks that can be launched over the network is a denial of service (DoS) attack. The most trivial form of a DoS attack floods the target with packets, causing congestion and consuming all available network resources. In order to employ massive attack power, the attacker usually launches a distributed denial of service (DDoS) attack, in which several subordinate hosts flood the target in concert. Traditionally, DoS attacks were performed at the network level. As a result, various network-level solutions have emerged. One type of readily available and cheap solution uses an existing firewall or router to perform ratelimiting of traffic and filtering of packets according to header fields like address and port number. Since most reasonabl