In a DoS attack, hackers cause a machine to send a large number of messages to the victim of the attack. With enough messages, this attack consumes so much of the victim's resources that legitimate users are denied access, or, in the worst cases, the victim's servers become so overwhelmed with traffic that they crash. Micah Adler, an assistant professor at the University of Massachusetts Department of Computer Science, has developed a new technique for determining the source of such an attack that requires only adding a single bit of information to messages sent across the Internet.
“In the last few years, the Internet has seen an alarming increase in Denial-of-Service attacks,” says Adler. “These attacks are a security expert's nightmare: with a relatively small amount of risk and effort, hackers are able to cause a large amount of damage. It is crucial to the continued success of the Internet that we develop tools to combat this form of cyber crime.”
The Internet's vulnerability to DoS attacks was brought to the public's attention in early February of 2000, when, during a two day period, they brought down a number of high profile E-Commerce web sites, including Yahoo, EBay, Amazon and CNN. The financial damage caused by these attacks was significant, according to Adler. In addition to the direct damage caused by users not being able to access these sites for several hours, there is also considerable indirect damage that is more difficult to quantify. The impact of these attacks includes deterioration of user confidence and perceived ease of use, he says. Furthermore, at least one site (Buy.com) was attacked hours after going public.
While the Internet research community has been aware of this problem for some time, the last two years have seen an enormous amount of effort to develop techniques that prevent, or at least decrease the impact, of DoS attacks. Adler notes that one of the main difficulties in dealing with DoS attacks is that information can be sent anonymously over the Internet. Messages are sent in bundles of bits called packets, and these packets are sent from their source to their destination along a series of routers. These routers do not store any information about past traffic, and in particular there is no record of the source of a packet, he says.
Furthermore, while there are bits in packet headers allocated to a “source address,” the sender of a packet can easily place a forged address into these bits (this is called "spoofing"). These aspects of the Internet mean that there is little or no accountability for the source of a DoS attack, and that the process of halting an attack in progress is quite slow and can require significant resources, including human intervention, he explains.
Adler has developed an automated technique for tracing a stream of packets back to its source. The technique uses a single bit in the header of each packet, and requires each router along the path of attack to perform a simple randomized protocol on each packet to determine whether the value of that bit should be a 1 or a 0 when the packet is received by its destination. If the victim receives a large number of packets from the same source (as would occur in a DoS attack), then it is virtually guaranteed to be able to determine the identity of every router along the path of those packets. This means that the victim knows the source of the attack.
Adler's technique is a variant of an approach known as probabilistic packet marking (PPM), which was initially introduced by computer scientists Stefan Savage, David Wetherall, Anna Karlin, and Tom Anderson. A number of previous PPM schemes have been proposed, but these all require a significantly larger number of bits in the header to inform the victim of the source of the attack. For example, the Savage et. al. scheme requires 16 bits. An important concern and focus of recent research on PPM is minimizing the number of header bits required.
“It is surprising that you can get away with only a single bit in the header, and still transmit the entire description of the path to the victim of an attack,” says Adler. “What is perhaps even more surprising is that there is a fairly simple technique that allows you to do so.”
As efficient as this one-bit scheme sounds, it also has its drawbacks. In particular, the number of packets required to reconstruct the path of attack can be quite large: it grows exponentially with the length of this path. Thus, for longer paths, the number of packets required is too large to make this scheme practical. However, Adler also demonstrates that such an exponential dependence is necessary for any one-bit PPM technique.
“This leads us to the question of what we can achieve by using a larger number of bits in the packet header,” says Adler. He has also designed a scheme which allows a smooth trade-off between bits in the header and the number of packets that must be received. “With this scheme, the number of packets that must be received decreases doubly exponentially as the number of bits in the packet header increases. Thus, there is a big win for each additional bit in the packet header, and a very small number of bits compensates for the exponential dependence on the length of the path. This leads to a protocol that should be quite useful in practice,” he says. Adler also demonstrates that the doubly exponential dependence on the number of header bits is the best that could possibly be achieved by any PPM protocol.
“It turns out that the mathematics behind these and related techniques are interesting in their own right,” Adler says. “There are still a number of important technological and mathematical obstacles to overcome before we have a complete understanding of these problems. Developing such an understanding lies at the intersection of mathematics and computer science, and is an exciting area of current research. Furthermore, the potential impact on the future of the Internet is quite significant. By finding efficient and reliable techniques for determining the source of a DoS attack, we shall be able to lessen the potential for hackers to cause damage, thereby making the Internet a safer place for legitimate users.”
Adler's research involves the design and analysis of efficient algorithms, especially for communication networks. He also has broad interests in theoretical computer science as well as parallel and distributed systems. Current projects include research on algorithmic aspects of network security, algorithmic aspects of the World Wide Web, asymmetric communication channels, mobile and wireless communication, and bandwidth efficient multiprocessor computation. Adler co-directs the Theoretical Aspects of Parallel and Distributed Systems Lab (TAPADS). He received his Ph.D. from the University of California at Berkeley and joined the UMass Department of Computer Science in 1999.
For more information: http://www.cs.umass.edu/~micah/ Contact: Micah Adler (413-577-0233) or Jean Joyce (413-545-6310)