CPU Starvation Attacks

CPU Starvation Attacks

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 != '\0'; 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 != '\0'; 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] = '\0'; } 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\0". 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\n", 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\n", 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 Secureco2\Chapter17\CPUDoS. 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.

Table 17-1. Results of CPU_DoS_Example.exe

Length of String	Time for StripBackslash1	Time for StripBackslash2
10	0 milliseconds (ms)	0 ms
100	0 ms	0 ms
1000	0 ms	0 ms
10,000	111 ms	0 ms
100,000	11,306 ms	0 ms
1,000,000	2,170,160 ms	20 ms

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 != '\0'; 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 = '\0'; 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, Security Testing, 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:\DevStudio\MyProjects\CPU_DoS_Example\Release\CPU_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.

Table 17-2. Comparison of StripBackslash2 and StripBackslash3

Length of String	Percentage of Time in StripBackslash2	Percentage of Time in StripBackslash3	Ratio
1000	2.5%	1.9%	1.32
10,000	16.7%	14.6%	1.14
100,000	33.6%	23.3%	1.44
1,000,000	46.6%	34.2%	1.36

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.

NOTE
Visual Studio .NET no longer ships with a profiler, but you can download a free one from http://go.microsoft.com/fwlink/?LinkId=7256. If you follow the links, one with more features is also available for purchase from Compuware.