Denial of Service

Lecturer: Professor Fred B. Schneider

Lecture notes by Michael Frei

Denial of Service Attacks

This week, several well-known and widely used web sites suffered at the hands of "cyber attackers". Yahoo!, Amazon.com, and CNN among them---overloaded with bogus traffic---each became inaccessible to the majority of the internet's users for several hours. Such assaults are known as denial of service attacks.

To understand the situation, let's start with a non-technical example. You and your date go to an exclusive restaurant. This restaurant only seats customers with reservations, which you did not know (and did not make). When you and your date are turned away, you leave the restaurant angry and embarassed. Determined to get revenge, you call the restaurant and book as many tables as you can for a whole night. When that night arrives, you go to the movies instead. Many would-be real customers are unable to get reservations due to your monopoly of the reservations schedule; the restaurant suffers a night of low profits from the lack of real business. That will teach them!

It is likely that a restaurant would catch-on if the same person makes lots of reservations for the same night. For example, they might recognize your voice and might refuse further reservations from you. But this defense is easily overcome---you can get a bunch of your friends each to call and try to make as many reservations as possible. This is a distributed attack, because the aggregate load is originating from a set of sources. What could the restaurant do to protect against this? Maybe they could start a rule that reservations require a (significant) non-refundable deposit. This non-refundable deposit could be a deterrent for you and your friends (Revenge at what price?), but not a deterrent for real customers with intentions on eating there.

Availability of Networked Systems

To put things in more technical terms, a Denial of Service attack is usually based on the following principle:

To illustrate, consider an online service, named Cycles-R-Us, and suppose the service we provide to customers is computation time, say 2 minutes (see figure below).

Our server(s) take in requests for computation and then respond with the result. How could we build our system to ensure service to all our customers at all times? Here are a couple approaches we might consider:
or

It is easy to see why the second choice is more practical. Even though our system might get 1000 requests a day, statistics could show that the largest concurrent set of requests has been size 10. However, assuming that this upper bound will continue creates a vulnerability. The attacker causes the assumption to be violated (and the system no longer is obligated to satisfy its specification.)

Let's look at the two types of Denial of Service attacks and examine corresponding defense mechanisms.

Single Machine Attack

A single attacker sends a continuous, heavy stream of requests to Cycles-R-Us, hoping to bog it down with bogus computation requests, preventing real users from having their requests processed. There are a couple ways we can defend against this.

Notice Attack and Block Requests

We might have a basis for recognizing attacks. For example, we might have some notion of what "normal" behavior for a single user is. Including that rule in a firewall or router at the entrance to Cycles-R-Us would allow the router to discard (seemingly) bogus requests. (see figure below). If, for example, we suspect an attack coming from a particular place, we could use a rule based on sender location (assuming it hasn't been forged) and block all requests from that location.

However, an attack can keep switching machines so that all bogus requests do not come from a single location.

Make Attackers Expand Effort

A second approach to defense would be to require requestors to expend some resources, analogous to the deposit in the restaurant reservation example above. For example, upon receiving a request, Cycles-R-Us could choose 2 numbers, x and y, such that z := x * y. The server could then reply to the requestor with a message saying "Factor z, then I'll do your computation". Since choosing the two numbers and multiplying them is cheap for Cycles-R-Us, but factoring is expensive for the requestor, the server has succeeded in making requestors expend resources of their own before the server does any processing. (see figure below)

But in the protocol just given, the requestor could "cheat" by simply coming up with it's own x and y, computing z, then sending these back to the server. To prevent such cheating, Cycles-R-Us would have to store which x, y, and z it chose for each request, and then check requestor responses against this saved information. But the scheme consumes memory (a resource) and consuming that resource could then be the basis of another form of denial of service attack. So, we instead modify the above protocol by having the server encrypt the two numbers it came up with and including them in the message it sends to each requestor. When the requestor has finished factoring, as proof that it did not cheat, the requestor must also send back to Cycles-R-Us the two encrypted numbers along with the factors.

Distributed Attack

If machines scattered through a network direct attacks at a victim, then the cost to each individual attacking machine might not be prohibative (even though the aggregate cost might be high enough to rule out using a single machine to launch the attack). Consider the figure below.

A router or firewall might succeed in blocking requests from specific sources, but that only works if there is a (small and) fixed set of sources. With a distributed attack, the set of sources could be large and constantly changing. Attackers might break into machines and co-opt them for use in the attack. If machines on the internet were more secure, attackers would be unable to exploit them in such attacks.

How can we defend a distributed attack? Not very well, as this week's events showed. Even though an attacker might fake IP addresses, attack packets will still pass through hardware attached to true IP address. So packets can be traced and approximate origins found. And attacks coming from multiple machines on the same subnetworks can be determined and blocked.