DoS attacks that result in application failure are almost always code quality issues. Some of the most well known of these have worked against networking stacks. An early example of this was the User Datagram Protocol (UDP) bomb that would bring down certain SunOS 4.x systems. If you built a UDP packet so that the length specified in the UDP header exceeded the actual packet size, the kernel would cause a memory access violation and panic—UNIX systems panic, Windows systems blue screen or bugcheck—followed by a reboot.

A more recent example is the "Ping of Death," which has an interesting cause that has to do with some problems in how IP headers are constructed. Here’s what an IPv4 header looks like:

struct ip_hdr
{
    unsigned char  ip_version:4,
                   ip_header_len:4;
    unsigned char  ip_type_of_service;
    unsigned short ip_len;
    unsigned short ip_id;
    unsigned short ip_offset;
    unsigned char  ip_time_to_live;
    unsigned char  ip_protocol;
    unsigned short ip_checksum;
    struct in_addr ip_source, ip_destination;
};

The ip_len member yields the number of bytes that the whole packet contains. An unsigned short can be at most 65,535, so the whole packet can contain 65,535 bytes at maximum. The ip_offset field is a little strange—it uses three bits to specify the fragmentation behavior. One bit is used to determine whether the packet is allowed to be fragmented, and another specifies whether more fragments follow. If none of the bits are set, either the packet is the last of a set of fragmented packets or there isn’t any fragmentation. We have 13 bits left over to specify the offset for the fragment. Because the offset is in units of eight bytes, the maximum offset occurs at 65,535 bytes. What’s wrong with this? The problem is that the last fragment can be added to the whole packet at the last possible byte that the whole packet should contain. Thus, if you write more bytes at that point, the total length of the reassembled packet will exceed 2^16.

How do you protect yourself from this type of mistake? The first rule is to never ever trust anything that comes across the network. Writing solid code, and thoroughly testing your code is the only way to defeat application crashes. Also remember that many DoS attacks that cause crashes are really cases in which arbitrary code might have been executed if the attacker had spent a little more time. Here’s a code snippet that illustrates this problem:

/*
  Example of a fragment reassembler that can detect
  packets that are too long
*/

#include <winsock2.h>
#include <list>
using namespace std;

//Most fragment reassemblers work from a linked list.
//Fragments aren’t always delivered in order.
//Real code that does packet reassembly is even more complicated.

struct ip_hdr
{
    unsigned char  ip_version:4,
                   ip_header_len:4;
    unsigned char  ip_type_of_service;
    unsigned short ip_len;
    unsigned short ip_id;
    unsigned short ip_offset;
    unsigned char  ip_time_to_live;
    unsigned char  ip_protocol;
    unsigned short ip_checksum;
    struct in_addr ip_source, ip_destination;
};

typedef list<ip_hdr> FragList;

bool ReassemblePacket(FragList& frags, char** outbuf)
{
    //Assume our reassembler has passed us a list ordered by offset.

    //First thing to do is find out how much to allocate 
    //for the whole packet.
    unsigned long  packetlen = 0;

    //Check for evil packets and find out maximum size.
    unsigned short last_offset;
    unsigned short datalen;
    ip_hdr Packet;

    //I’m also going to ignore byte-ordering issues - this is 
    //just an example.

    //Get the last packet.
    Packet = frags.back();

    //Remember offset is in 32-bit multiples.
    //Be sure and mask out the flags.
    last_offset = (Packet.ip_offset & 0x1FFF) * 8;

    //We should really check to be sure the packet claims to be longer
    //than the header!
    datalen = Packet.ip_len - Packet.ip_header_len * 4;

    //Casting everything to an unsigned long prevents an overflow.
    packetlen = (unsigned long)last_offset + (unsigned long)datalen;

    //If packetlen were defined as an unsigned short, we could be
    //faced with a calculation like this:

    //offset =  0xfff0;
    //datalen = 0x0020;
    //total =  0x10010
   
    //which then gets shortened to make total = 0x0010
    //and the following check always returns true, as an unsigned
    //short can never be > 0xffff.

    if(packetlen > 0xffff)
    {
        //Yech! Bad packet!
        return false;
    }

    //Allocate the memory and start reassembling the packet.
    //...
    return true;

}

Following is another code snippet that illustrates another type of problem: inconsistencies between what your structure tells you to expect and what you’ve really been handed. I’ve seen this particular bug cause lots of mayhem in everything from Microsoft Office applications to the core operating system.

/*Second example*/
struct UNICODE_STRING
{
    WCHAR* buf;
    unsigned short len;
    unsigned short max_len;
};

void CopyString(UNICODE_STRING* pStr)
{
    WCHAR buf[20];

    //What’s wrong with THIS picture?
    if(pStr->len < 20)
    {
        memcpy(buf, pStr->buf, pStr- >len * sizeof(WCHAR));
    }

    //Do more stuff.
}

The most obvious bug you might notice is that the function isn’t checking for a null pointer. The second is that the function just believes what the structure is telling it. If you’re writing secure code, you need to validate everything you can. If this string were passing in by a remote procedure call (RPC), the RPC unmarshalling code should check to see that the length that was declared for the string is consistent with the size of the buffer. This function should at least verify that pStr->buf isn’t null. Never assume that you have a well-behaved client.

The object of a CPU starvation attack is to get your application to get stuck in a tight loop doing expensive calculations, preferably forever. As you might imagine, your system isn’t going to be much good once you’ve been hit with a CPU starvation attack. One way an attacker might find a problem in your application is to send a request for c:\foo.txt and observe that the error message says that c:foo.txt was not found. Ah, your application is stripping out duplicate backslashes—how efficiently will it handle lots of duplicates? Let’s take a look at a sample application:

/*
  CPU_DoS_Example.cpp
  This application shows the effects of two
  different methods of removing duplicate backslash
  characters.

  There are many, many ways to accomplish this task. These 
  are meant as examples only.
*/

#include <windows.h>
#include <stdio.h>
#include <assert.h>

/*
  This method reuses the same buffer but is inefficient.
  The work done will vary with the square of the size of the input.

  It returns true if it removed a backslash.
*/

//We’re going to assume that buf is null-terminated.
bool StripBackslash1(char* buf)
{
    char* tmp = buf;
    bool ret = false;

    for(tmp = buf; *tmp != ’’; tmp++)
    {
        if(tmp[0] == ’\’ && tmp[1] == ’\’)
        {
            //Move all the characters down one
            //using a strcpy where source and destination
            //overlap is BAD! 
            //This is an example of how NOT to do things.
            //This is a professional stunt application -  
            //don’t try this at home.
            strcpy(tmp, tmp+1);
            ret = true;
        }
   }

    return ret;
}

/*
  This is a less CPU-intensive way of doing the same thing.
  It will have slightly higher overhead for shorter strings due to
  the memory allocation, but we have to go through the string 
  only once.
*/

bool StripBackslash2(char* buf)
{
    unsigned long len, written;
    char* tmpbuf = NULL;
    char* tmp;
    bool foundone = false;

    len = strlen(buf) + 1;

    if(len == 1)
        return false;

    tmpbuf = (char*)malloc(len);
   
    //This is less than ideal -  we should really return an error.
    if(tmpbuf == NULL)
    {
        assert(false);
        return false;
    }

    written = 0;
    for(tmp = buf; *tmp != ’’; tmp++)
    {
        if(tmp[0] == ’\’ && tmp[1] == ’\’)
        {
            //Just don’t copy this one into the other buffer.
            foundone = true;
        }
        else
        {
            tmpbuf[written] = *tmp;
            written++;
        }
    }

    if(foundone)
    {
        //Copying the temporary buffer over the input
        //using strncpy allows us to work with a buffer 
        //that isn’t null-terminated.
        //tmp was incremented one last time as it fell 
        //out of the loop.
        strncpy(buf, tmpbuf, written);
        buf[written] = ’’;
    }

    if(tmpbuf != NULL)
        free(tmpbuf);

    return foundone;
}

int main(int argc, char* argv[])
{
    char* input;
    char* end = "foo";
    DWORD tickcount;
    int i, j;

    //Now we have to build the string.

    for(i = 10; i < 10000001; i *= 10)
    {
        input = (char*)malloc(i);

        if(input == NULL)
        {
            assert(false);
            break;
        }

        //Now populate the string.
        //Account for the trailing "foo" on the end.
        //We’re going to write 2 bytes past input[j], 
        //then append "foo".
        for(j = 0; j < i - 5; j += 3)
        {
            input[j] = ’\’;
            input[j+1] = ’\’;
            input[j+2] = ’Z’;
        }

        //Remember that j was incremented before the conditional 
        //was checked.
        strncpy(input + j, end, 4);

        tickcount = GetTickCount();
        StripBackslash1(input);
        printf("StripBackslash1: input = %d chars, time = %d ms
", 
               i, GetTickCount() - tickcount);

        //Reset the string - this test is destructive.
        for(j = 0; j < i - 5; j += 3)
        {
            input[j] = ’\’;
            input[j+1] = ’\’;
            input[j+2] = ’Z’;
        }

        //Remember that j was incremented before the conditional
        //was checked.
        strncpy(input + j, end, 4);

        tickcount = GetTickCount();
        StripBackslash2(input);
        printf("StripBackslash2: input = %d chars, time = %d ms
", 
               i, GetTickCount() - tickcount);

        free(input);
    }

    return 0;
}

CPU_DoS_Example.cpp is a good example of a function-level test to determine how well a function stands up to abusive input. This code is also available with the book’s sample files in the folder Secureco2Chapter17CPUDoS. The main function is dedicated to creating a test string and printing performance information. The StripBackslash1 function eliminates the need to allocate an additional buffer, but it does so at the expense of making the number of instructions executed proportional to the square of the number of duplicates found. The StripBackslash2 function uses a second buffer and trades off a memory allocation for making the number of instructions proportional to the length of the string. Take a look at Table 17-1 for some results.

As you can see in the table, the differences between the two functions don’t show up until the length of the string is up around 10,000 bytes. At 1 million bytes, it takes 36 minutes on my 800 MHz Pentium III system. If an attacker can deliver only a few of these requests, your server is going to be out of service for quite a while.

Several readers of the first edition pointed out to me that StripBackslash2 is itself inefficient—the memory allocation is not absolutely required. I’ve written a third version that does everything in place. This version isn’t measurable using GetTickCount and shows 0 ms all the way to a 1-MB string. The reason I didn’t write the examples this way the first time is that I wanted to demonstrate a situation where a solution might be initially discarded due to performance reasons under optimal conditions when another solution was available. StripBackslash1 outperforms StripBackslash2 with very small strings, but the performance difference could well be negligible when dealing with your overall application. StripBackslash2 has some additional overhead but has the advantage of stable performance as the load grows. I’ve seen people make the mistake of leaving themselves open to denial of service attacks by considering performance only under ordinary conditions. It’s possible that you may want to take a small performance hit under ordinary loads in order to be much more resistant to denial of service. Unfortunately, this particular example wasn’t the best because there was a third alternative available that outperforms both of the original solutions and that also resists DoS attacks. Here’s StripBackslash3:

bool StripBackslash3(char* str)
{
    char* read;
    char* write;

    //Always check assumptions.
    assert(str != NULL);

    if(strlen(str) < 2)
    {
        //No possible duplicates.
        return false;
    }

    //Initialize both pointers.
    for(read = write = str + 1; *read != ’’; read++)
    {
        //If this character and last character are both
        //backslashes,don’t write -
        //only read gets incremented.

        if(*read == ’\’ && *(read - 1) == ’\’)
        {
            continue;
        }
        else
        {
            *write = *read;
            write++;
        }
    }

    //Write trailing null.
    *write = ’’;

    return true;

}

A complete discussion of algorithmic complexity is beyond the scope of this book, and we’ll cover security testing in more detail in Chapter 19, but let’s take a look at some handy tools that Microsoft Visual Studio provides that can help with this problem.

I was once sitting in a meeting with two of my programmers discussing how we could improve the performance of a large subsystem. The junior of the two suggested, "Why don’t we calculate the algorithmic complexity?" He was a recent graduate and tended to take a theoretical approach. The senior programmer replied, "That’s ridiculous. We’ll be here all week trying to figure out the algorithmic complexity of a system that large. Let’s just profile it, see where the expensive functions are, and then optimize those." I found on several occasions that when I asked Tim (the senior programmer) to make something run faster, I’d end up asking him to inject wait states so that we didn’t cause network equipment to fail. His empirical approach was always effective, and one of his favorite tools was the Profiler.

To profile your application in Visual Studio 6, click the Project menu, select Settings, and then click the Link tab. In the Category drop-down list box, click General. Select Enable Profiling and click OK. Now run your application, and the results will be printed on the Profile tab of your output window. I changed this application to run up to only 1000 characters—I had taken a shower and eaten lunch waiting for it last time—and here’s what the results were:

Profile: Function timing, sorted by time
Date:    Sat May 26 15:12:43 2001


Program Statistics
------------------
    Command line at 2001 May 26 15:12: 
    "D:DevStudioMyProjectsCPU_DoS_ExampleReleaseCPU_DoS_Example"
    Total time: 7.822 millisecond
    Time outside of functions: 6.305 millisecond
    Call depth: 2
    Total functions: 3
    Total hits: 7
    Function coverage: 100.0%
    Overhead Calculated 4
    Overhead Average 4

Module Statistics for cpu_dos_example.exe
-----------------------------------------
    Time in module: 1.517 millisecond
    Percent of time in module: 100.0%
    Functions in module: 3
    Hits in module: 7
    Module function coverage: 100.0%

        Func          Func+Child           Hit
        Time   %         Time      %      Count  Function
---------------------------------------------------------
       1.162  76.6        1.162  76.6        3 StripBackslash1(char *)
(cpu_dos_example.obj)
       0.336  22.2        1.517 100.0        1 _main 
(cpu_dos_example.obj)
       0.019   1.3        0.019   1.3        3 StripBackslash2(char *)
(cpu_dos_example.obj)

The timer used by the Profiler has a better resolution than GetTickCount, so even though our initial test didn’t show a difference, the Profiler was able to find a fairly drastic performance difference between StripBackslash1 and StripBackslash2. If you tinker with the code a little, fix the string length, and run it through the loop 100 times, you can even see how the two functions perform at various input lengths. For example, at 10 characters, StripBackslash2 takes twice as long as StripBackslash1 does. Once you go to only 100 characters, StripBackslash2 is five times more efficient than StripBackslash1. Programmers often spend a lot of time optimizing functions that weren’t that bad to begin with, and sometimes they use performance concerns to justify using insecure functions. You should spend your time profiling the parts of your application that can really hurt performance. Coupling profiling with thorough function-level testing can substantially reduce your chances of having to deal with a DoS bug. Now that I’ve added StripBackslash3 at the behest of people concerned with performance, let’s take a look at how StripBackslash2 and StripBackslash3 compare using the profiler, which is described in Table 17-2.

These results are interesting. The first interesting thing to note is that StripBackslash2 really wasn’t all that bad. The reason the ratio varies across the length of the string is that the operating system and heap manager allocates memory more efficiently for some sizes than others. I haven’t managed to upgrade my home system since writing the first edition, so the results are consistent. One note is that this system has plenty of available RAM, and a system that was RAM-constrained would show very different results, because large memory allocations would get very expensive. Despite the fact that there are currently processors shipping with three times the performance of this system, something to remember is that older systems are often much better at revealing performance and CPU DoS issues.

A memory starvation attack is designed to force your system to consume excess memory. Once system memory is depleted, the best that you can hope for is that the system will merely page to disk. Programmers all too often forget to check whether an allocation or new succeeded and just assume that memory is always plentiful. Additionally, some function calls can throw exceptions under low-memory conditions—InitializeCriticalSection and EnterCriticalSection are two commonly found examples, although EnterCriticalSection won’t throw exceptions if you’re running Windows XP or Windows .NET Server. If you’re dealing with device drivers, nonpaged pool memory is a much more limited resource than regular memory.

One good example of this was found by David Meltzer when he was working at Internet Security Systems. He discovered that for every connection accepted by a computer running Windows NT 4 Terminal Server Edition, it would allocate approximately one megabyte of memory. The Microsoft Knowledge Base article describing the problem is http://support.microsoft.com/support/kb/articles/Q238/6/00.ASP. On the underpowered system David was testing, this quickly brought the machine to a near halt. If your Terminal Server computer is configured with a reasonable amount of RAM per expected user, the problem becomes a resource starvation issue—see the next section—in which available sessions are difficult to obtain. The obvious fix for this type of problem is to not allocate expensive structures until you’re sure that a real client is on the other end of the connection. You never want a situation in which it’s cheap for an attacker to cause you to do expensive operations.

A resource starvation attack is one in which an attacker is able to consume a particular resource until it’s exhausted. You can employ a number of strategies to address resource starvation attacks, and it’s up to you to determine the response appropriate to your threat scenario. For illustration purposes, I’ll use one resource starvation attack I found: systems running Windows NT use an object called an LSA_HANDLE when querying the Local Security Authority (LSA). I was looking for ways to cause trouble, so I wrote an application that requested LSA handles and never closed them. After the system under attack had given me 2048 handles, it wouldn’t give me any more but it also wouldn’t allow anyone to log on or perform several other essential functions.

The fix for the LSA handle starvation problem was an elegant solution, and it’s worth considering in some detail. We can allocate a pool of handles for each authenticated user; this allows each user to open as many handles as he needs. Any single user cannot cause a denial of service to anyone except himself, and the anonymous user has a pool to himself as well. The lesson to learn here is to never allow anonymous users to consume large amounts of critical resources, whether handles, memory, disk space, or even network bandwidth.

One approach that can mitigate the problem is to enforce quotas. In some respects, a quota can be the cause of a resource starvation attack, so this needs to be done with care. For example, say I had an application that spawned a new worker thread every time it received a new connection to a socket. If I didn’t place a limit on the number of worker threads, an ambitious attacker could easily have me running thousands of threads, causing CPU starvation and memory starvation problems. If I then limit the number of worker threads in response to this condition, the attacker simply consumes all my worker threads—the system itself withstands the attack, but my application does not.

Darn those pesky attackers! What now? How about keeping a table for the source addresses of my clients and establishing a limit based on the requesting host? How many sessions could any given host possibly want? Now I discover that one of my most active client systems is a server running Terminal Services with 100 users, and I’ve set my limit to 10. You might have the same type of problem if you have a lot of clients coming from behind a proxy server. It’s a good idea to think about the usage patterns for your application before devising a plan to handle resource starvation attacks. With the advent of IPv6, it is possible for a single system to have a large number of IP addresses. In fact, there is a provision for anonymous IP addresses built into the protocol. As we leave the IPv4 world behind, keeping a table of source addresses will become much less practical and more expensive due to the fact an address takes up to four times more memory.

A more advanced approach would be to set quotas on the distinct users who are accessing my application. Of course, this assumes that I know who certain users are, and it requires that I’ve gotten to the point in the transaction where I can identify them. If you do take a quota-based approach to resource starvation attacks, remember that your limits need to be configurable. As soon as you hard-code a limit, you’ll find a customer who needs just a little more.

One of the most advanced ways to deal with resource starvation is to code your application to change behavior based on whether it is under attack. Microsoft’s SYN flood protection works this way: if you have plenty of resources available, the system behaves normally. If resources are running low, it will start dropping clients who aren’t active. The Microsoft file and print services—the Server Message Block (SMB) protocol and NetBIOS—use the same strategy. This approach requires that you keep a table of which clients are progressing through a session normally. You can use some fairly sophisticated logic—for example, an attack that doesn’t require authentication is cheap to the attacker. You can be more ruthless about dropping sessions that have failed to authenticate than those that have supplied appropriate credentials. An interesting approach to overcoming CPU starvation attacks on the Transport Layer Security (TLS) protocol was presented at the 2001 USENIX Security Conference. The paper dealing with this approach is titled "Using Client Puzzles to Protect TLS" (Drew Dean, Xerox PARC, and Adam Stubblefield, Rice University). This technique also varies the behavior of the protocol when under attack. If you’re a USENIX member, you can download a full version of the paper from http://www.usenix.org/publications/library/proceedings/sec01/dean.html.

You can also use combinations of quotas and intelligently applied timeouts to address the risks to your own application. For all these approaches, I can give you only general advice. The best strategy for you depends on the specific details of your application and your users.

Perhaps one of the most classic network bandwidth attacks involved the echo and chargen (character generator) services. Echo simply replies with the input it was given, and chargen spews an endless stream of characters to any client. These two applications are typically used to diagnose network problems and to get an estimate of the available bandwidth between two points. Both services are also normally available on both UDP and TCP. What if some evil person spoofed a packet originating from the chargen port of a system with that service running and sent it to the echo service at the broadcast address? We’d quickly have several systems madly exchanging packets between the echo port and the chargen port. If you had spectacularly poorly written services, you could even spoof the broadcast address as the source, and the amount of bandwidth consumed would grow geometrically with the number of servers participating in what a friend of mine terms a "network food fight." Before you get the idea that I’m just coming up with a ridiculous example, many older chargen and echo services, including those shipped by Microsoft in Windows NT 4 and earlier, were vulnerable to just that kind of attack. The fix for this is to use a little sense when deciding just who to spew an endless stream of packets to. Most current chargen and echo services won’t respond to source ports in the reserved range (port number less than 1024), and they also won’t respond to packets sent to the broadcast address.

A variation on this type of attack that was also discovered by David Meltzer involved spoofing a UDP packet from port 135 of a system running Windows NT to another system at the same port. Port 135 is the RPC endpoint mapping service. The endpoint mapper would take a look at the incoming packet, decide it was junk, and respond with a packet indicating an error. The second system would get the error, check to see whether it was in response to a known request, and reply to the first server with another error. The first server would then reply with an error, and so on. The CPUs of both systems would spike, and available network bandwidth would drop drastically. A similar attack against a different service was patched very recently.

The fix for these types of DoS attacks is to validate the request before sending an error response. If the packet arriving at your service doesn’t look like something that you ought to be processing, the best policy is to just drop it and not respond. Only reply to requests that conform to your protocol, and even then you might want to use some extra logic to rule out packets originating to or from the broadcast address or reserved ports. The services most vulnerable to network bandwidth attacks are those using connectionless protocols, such as Internet Control Message Protocol (ICMP) and UDP. As in real life, some inputs are best not replied to at all.

Protecting against denial of service attacks is very difficult, and sometimes there’s no good answer to the overall problem. However, protecting against denial of service must be part of your overall security design. Protecting against some types of attacks, especially resource starvation attacks, can cause substantial design changes, so putting off DoS attacks until last could cause serious schedule risk.

Application failure is almost always a code quality issue. Protect against this with code reviews and fuzz testing. CPU starvation attacks are a performance issue and can be detected by profiling the code while subjecting it to abusive inputs. Memory starvation and resource starvation are both design issues and often require protective mechanisms to detect attack conditions and change behavior. Protect against network bandwidth attacks by considering how your application reacts to improper network requests.