UMass computer scientist offers a new way to track internet vandals

[InfoSec News <isn () c4i org>]

Forwarded from: Elyn Wollensky <elyn () consect com>

Contact: Elizabeth Luciano
luciano () journ umass edu
413-545-0444
University of Massachusetts at Amherst

UMass computer scientist offers a new way to track internet vandals

http://www.eurekalert.org/pub_releases/2002-04/uoma-ucs040402.php

AMHERST, Mass. - A computer scientist at the University of
Massachusetts has developed a powerful new technique for combating a
form of cyber crime known as Denial-of-Service (DoS) attacks.

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.



-
ISN is currently hosted by Attrition.org

To unsubscribe email majordomo () attrition org with 'unsubscribe isn' in the BODY
of the mail.