A bandwidth attack is an attempt to disrupt an online service by generating a traffic overload that clogs links or causes routers near the victim to crash. This can have serious consequences for Web companies which rely on their online availability to do business. This paper introduces a data-structure that routers and network monitors can use to collect packet rate statistics for subnet prefixes at different aggregation levels. These statistics can be used to detect bandwidth attacks using a simple heuristic: a significant, disproportional difference between the packet rate going to and coming from a host or subnet. This heuristic is based on the assumption that, during normal operations on the Internet, the packet rate of traffic going in one direction is proportional to the packet rate of traffic going in the opposite direction. Although this assumption does not hold in some cases, it is a close approximation to reality.
Bandwidth attacks are typically distributed attacks. An attacker uses tools to gain root access to machines on the Internet [Pac00,Spi00]. Once a machine is cracked, it is turned into a ``zombie.'' The attacker instructs the zombies to send bogus data to one particular destination [Dit00]. The resulting traffic can clog links, cause routers near the victim or the victim itself to fail under the load.
One major reason underlies the absence of a simple solution against bandwidth attacks: attackers can release high volumes of normal-looking packets on the Internet without being conspicuous or easily traceable. It is the mass of all packets together directed at one victim that poses a threat, rather than any characteristics of the individual packets. A dropping policy in routers based on per-packet characteristics will, therefore, not work.
It is relatively easy, but rather useless, to detect a bandwidth attack in the vicinity of the victim: by measuring the traffic load on a link or in a router, the exceptionally high volume of packets can be detected. Unfortunately for the victim, determining that it is under attack will not make the packets go away. Harm has already been done by the time the malicious packets reach (the vicinity of) the victim. A bandwidth attack should, therefore, be detected close to the attacker rather than close to the victim so that malicious packets can be stopped before they can cause any harm.
This paper proposes a MUlti-Level Tree for Online Packet Statistics (MULTOPS). MULTOPS enables routers or network monitors to detect ongoing bandwidth attacks. A handful of attackers that blast packets to a victim without any (or disproportionally fewer) packets coming back will be identified as malicious by MULTOPS. Large attacks that occurred in February 2000 [CNN00a,CNN00b,Net00] displayed these disproportional packet flows. Routers (or network monitors) using MULTOPS could have been used to stop (or detect) those attacks.
MULTOPS is a tree of nodes that contains packet rate statistics for subnet prefixes at different aggregation levels. It dynamically adapts its shape to (1) reflect changes in packet rates, and (2) avoid (maliciously intended) memory exhaustion.
Depending on their setup and depending on their location on the network, MULTOPS-equipped routers or network monitors may fail to detect a bandwidth attack that is mounted by attackers that randomize IP source addresses on malicious packets. In a different setup, MULTOPS-equipped routers may cause ``collateral damage'' by dropping legitimate packets with an IP destination address that MULTOPS identified as being under attack.
MULTOPS fails to detect attacks that deploy a large number of proportional flows to cripple a victim. (Proportional flows are flows in which the packet rate in one direction is proportional to the packet rate in the opposite direction.) For example, many attackers could open FTP or HTTP connections to one victim and download--preferably large--files over these connections, thereby overloading the victim. Even though the packet rates between the attackers and the victim are relatively low (because the victim cannot handle all the parallel downloads), they are proportional and, therefore, undetectable by MULTOPS. However, to successfully mount such an undetectable bandwidth attack, attackers need to be numerous, geographically distributed, and well organized. This makes it more difficult to mount an undetectable attack.
MULTOPS has been implemented in a software router and was tested with simulated attacks. Results are encouraging: attacks are stopped and legitimate traffic continues in a normal fashion, even with a large number of participating attackers. An off-the-shelf 700 Mhz Pentium III PC, running MULTOPS-equipped routing software, routes between 240,000 to 340,000 packets per second, depending primarily on the resources available to MULTOPS.
The rest of this paper is organized as follows. Section 2 takes a look at related work, Section 3 looks at different types of bandwidth attacks, Section 4 explains the design of MULTOPS, Section 5 looks at the details of the MULTOPS implementation, Section 6 deals with measurements, Section 7 discusses the details of some (unresolved) issues, and Section 8 concludes this paper.