A Comparative Analysis of Methods of Defense against = Buffer Overflow Attacks

From: Subject: A Comparative Analysis of Methods of Defense against Buffer Overflow Attacks Date: Mon, 5 Nov 2001 23:13:33 +0900 MIME-Version: 1.0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Content-Location: http://www.mcs.csuhayward.edu/~simon/security/boflo.html X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4522.1200 A Comparative Analysis of Methods of Defense against = Buffer Overflow Attacks

A Comparative Analysis of Methods of Defense against Buffer Overflow = Attacks

Istvan Simon
California State = University,=20 Hayward
Hayward, CA 94542
simon@csuhayward.edu
http://= www.mcs.csuhayward.edu/~simon/security/boflo.html
January,=20 31 2001
=20

Abstract

For = the past=20 several years Buffer Overflow attacks have been the main method of = compromising a computing system's security. Many of these = attacks=20 have been devastatingly effective, allowing the attacker to attain = administrator privileges on the attacked system. We review the = anatomy of=20 these attacks and the reasons why conventional methods of defense have = been=20 ineffective, and likely to remain so in the foreseeable future. = Recently,=20 however, several promising methods of defense have been proposed. We = compare the=20 strengths and weaknesses of these defense methods.
=
=20

1. Introduction

Buffer Overflows have been successfully used as a method of=20 penetrating systems' security for over 12 years. One of the=20 first buffer overflow attacks which attracted widespread = attention=20 due to its spectacular success was Robert Morris's Internet Worm. In = 1988 Morris=20 released a program which succeeded in infecting thousands of = Unix=20 hosts on the Internet. One of the methods Morris used to = gain access=20 to a vulnerable system was a buffer overflow bug in the fingerd = daemon [ 9, 29 ]. Once it gained access to a vulnerable = system,=20 Morris's program installed itself on the machine, and used several = methods to=20 attempt to spread itself to other machines. The original intent of = Morris=20 was to spread to other systems relatively slowly and undetected, = without =20 causing a significant disruption on any of the affected=20 machines. However, his attack failed completely in = this.=20 Morris made a programming error which caused his worm to spread at a = much higher=20 rate than originally intended. Because of this error, machines = were=20 infected and reinfected so rapidly that the worm = ended up overwhelming the attacked systems. Of course = this=20 caused his program to be detected immediately, and = transformed =20 it into the most devastating denial of service attack = until=20 that time. Morris's program usually did not gain administrative = root=20 access, and did not destroy any information on the = penetrated=20 system, nor leave time bombs or other malicious code behind [9].=20

From 1988 to 1996 the number of buffer overflow attacks = remained=20 relatively low [ 2, 30 ]. The known vulnerabilities were fixed, = and=20 because the attack method was little known and thought to = be =20 difficult to execute few new vulnerabilities were = discovered. =20 This changed dramatically in 1996 when Levy published a very well = written=20 paper [ 17 ] which simultaneously showed that it was very likely = that many=20 programs harbored buffer overflow vulnerabilities, and also=20 demonstrated techniques of constructing buffer overflow attacks = which were=20 likely to succeed against a target program suspected of being = vulnerable, =20 even if the attacker had no access to the actual source code of the = target=20 program. The combination of these two factors = stimulated =20 attackers to a flurry of research activity which lead to many = discoveries=20 of new vulnerabilities. In addition, many of the attacks = were=20 automated, which permitted the attack to be carried out = even =20 by people with little or no knowledge. People who are=20 relatively unsophisticated but interested in such attacks are often = called=20 Script Kiddies. Unfortunately, there are far = too many=20 script kiddies, who seem to have plenty of time on their hands, = and also=20 the energy, patience and persistence to keep hacking systems this = way. The=20 unhappy result is that these automated attacks have become a = serious=20 nuisance to the overworked system administrators responsible for=20 maintaining the integrity of their systems under = continuous =20 attack.=20

In this paper we review the anatomy of buffer overflow = attacks=20 and discuss the reasons why they are so prevalent and = deadly. We=20 then examine the traditional methods of defense and show why they are = unlikely=20 to succeed in stopping these attacks effectively in the near = future. We=20 also discuss more recent approaches of defense, and discuss = their=20 relative weaknesses and strengths. While no method of defense is = 100%=20 effective, we show why these newer methods are more likely = succeed=20 than their predecessors.
=20

2. What is a Buffer Overflow Attack?

A buffer overflow occurs in a program when the program stores = more=20 information in an array, the buffer, than the space = reserved=20 for it. This causes the areas adjacent to the buffer to be=20 overwritten, corrupting the values previously stored there. Buffer = overflows are=20 always programming errors which are typically introduced into a program=20 because the programmer failed to anticipate that the = information=20 copied into the buffer by the program may exceed its size. =20 Unfortunately, as we shall soon see, buffer overflow programming = errors=20 are quite common because of certain widely used and dangerous C=20 programming practices. Once a buffer overflow vulnerability = is=20 present in a program inadequate testing may not uncover it, so = that the=20 vulnerability may lurk in the program hidden , undiscovered and silent = for=20 years. This potentially opens up the program to be the target=20 of a sudden attack which exploits the vulnerability to gain=20 unauthorized access to a system.=20

A buffer overflow may happen accidentally during the execution of a=20 program. When this happens, however, it is very = unlikely that=20 it will lead to a security compromise of the system. Most often = the=20 clobbering of information in areas adjacent to the buffer will cause the = program=20 to crash or produce obviously incorrect results. In a buffer = overflow=20 attack, on the other hand, the objective of the attacker is to use the=20 vulnerability to corrupt information in a carefully designed way = in=20 order to execute attack code previously planted by = the=20 attacker. If this succeeds, the attacker effectively hijacked the = control of the=20 program. Once control is transferred to the attack code, it grants = unauthorized access to the attacker. Typically the attack = code just=20 spawns a shell, which allows the attacker to execute arbitrary = commands on=20 the system.=20

When a new shell is spawned in a Unix system, it = inherits=20 the access privileges of the process that spawned it. = Consequently,=20 if the attacked process containing the buffer overflow = vulnerability runs=20 with root privileges, the attacker will also get a root = shell. =20 We remark that though we limited our discussion to UNIX systems, = buffer=20 overflows are applicable to most Operating Systems . = In=20 particular, many attacks have been successful against = Windows NT and=20 Windows 2000 systems [ 8, 12, 13, 21, 22, 26 ]. Axelsson [ 1 ] compared = the=20 security of Windows NT and UNIX systems against known types of attack, = and found=20 them to be roughly equally vulnerable.=20

A buffer overflow attack may be local or remote. In a = local=20 attack the attacker already has access to the system and may be = interested in=20 escalating his/her access privilege. A remote = attack =20 is delivered through a network port, and may achieve = simultaneously=20 both gaining unauthorized access and maximum access = privilege.=20

Summarizing , we see that a buffer overflow attack = usually=20 consists of three parts:=20

1. The planting of the attack code into the target program;=20

2. The actual copying into the buffer which overflows = it =20 and corrupts adjacent data structures;=20

3. The hijacking of control to execute the attack code;=20

We now examine in more detail the main type of buffer overflow = attacks.=20

3. Smashing the Stack

One classification of buffer overflow attacks depends on where = the buffer=20 is allocated. If the buffer is a local variable of a function, the = buffer=20 resides on the run-time stack. This is the type of attack examined = in=20 Levy's article [ 17 ], and it is by far the most prevalent form of = buffer=20 overflow attack.=20

When a function is called in a C program, before the execution = jumps to=20 the actual code of the called function , the activation = record=20 of the function must be pushed on the run-time stack. In = a C=20 program the activation record consists of the following fields: =
=20

space allocated for each parameter of the function;=20
the return address;=20
the dynamic link;=20
space allocated to each local variable of the function. =

For=20 convenience we will consider the address of the dynamic link field to be = the=20 base address of the activation record. The function = must be=20 able to access it's parameters and local variables. This requires=20 that during the execution of the function a register hold = the base=20 address of the activation record of the function., i.e. the address of = the=20 dynamic link field. Parameters are below this address on the = stack, and=20 local variables above. When the function returns, this register = must be=20 restored to its previous value, to point to the activation record of the = calling=20 function. To be able to do this, when the function is called the value = of this=20 register is saved in the dynamic link field. Thus the = dynamic=20 link field of each activation record points to the dynamic link field of = the=20 previous activation record on the stack, which in turn points to = the=20 dynamic link field of the previous activation record, and so on, all the = way to=20 the bottom of the stack. The first activation record on the stack is = that of=20 main(). This chain of pointers is called the dynamic = chain.=20

In many C compilers the buffer grows towards the bottom of the stack. = Thus=20 if the buffer overflows and the overflow is long enough the return = address=20 will be corrupted, (as well as everything else in = between, =20 including the dynamic link.) If the return address is = overwritten by=20 the buffer overflow so as to point to the attack code, this will be = executed=20 when the function returns. Thus, in this type of attack, the return = address on=20 the stack is used to hijack the control of the program.=20

Overwriting the return address, as explained above, gives the = attacker the=20 means of hijacking the control of the program, but where should the = attack code=20 be stored? Most commonly it is stored in the buffer itself. Thus = the =20 payload string which is copied into the buffer will contain both = the=20 binary machine language attack code as well as the address = of this=20 code which will overwrite the return address.=20

There are a few difficulties that the attacker must overcome to carry = out=20 this plan. If the attacker has the source code of the = attacked=20 program it may be possible to determine exactly how big the buffer = is=20 and how far it is from the return address, determining how big the = payload=20 string must be. Also, the payload string cannot contain the = null=20 character since this would abort the copying of the payload into the=20 buffer. Some copying routines of the C library use carriage = returns and=20 new lines as a delimiter instead, so these characters should also be = similarly=20 avoided in the payload string. =20

Access to the source code is nowadays quite common = for many=20 Operating Systems, e.g. Linux, OpenBSD, Free BSD, and even = Solaris. =20 Levy [ 17 ] shows, however, that there is no need to have access = to the=20 source, or even knowledge of the exact details of how the attacked = program=20 works. The address of the attack code can be guessed, =20 and through various techniques an approximate guess will do. = For=20 example, the attack code could start with a long list of no=20 operation instructions, so that control could be passed to any of = these in=20 order to correctly execute the crucial part of the attack code = which=20 spawns the shell and comes after the no ops. This technique was already = used in=20 the Morris worm. Similarly, the tail of the payload=20 string could consist of a repeated list of the guessed address of = the=20 attack code that we want to overwrite the return address = with. These=20 techniques increase considerably the chances of guessing the address of = the=20 attack code close enough for the attack to work. For more details check = Levy's=20 article [ 17 ].=20

We now examine why buffer overflows are so common. = Suppose that=20 the buffer is a character array used to store strings. Most programs = have string=20 inputs or environment variables which can be used by the attacker to = deliver the=20 attack. The program must read this input and parse it in order to = make the=20 appropriate response to the input. Often, to parse the input,the program = will=20 first copy it into a local variable of a function and then parse it. To = do this=20 the programmer reserves a large enough buffer for any reasonable=20 input. To copy the input into the buffer the program = will=20 typically use a string copying function of the standard C library such = as=20 strcpy(). If done carelessly, this introduces a buffer = overflow=20 vulnerability. This pattern is so well = established in=20 the C programmer's repertoire that it makes very = likely=20 that many programs will contain buffer overflow vulnerabilities.=20

The problem arises partly because C represents strings in a = dangerous=20 way. The length of a string is determined by terminating the = sequence of characters by a null character. This representation = is =20 convenient, because strings can have arbitrary length and yet it = allows=20 for efficient processing of strings. But at the same time it is also = dangerous,=20 because the scheme breaks down if a string is not null = terminated, =20 and because there is no way of knowing the length of the string = prior to=20 processing all its characters. The typical C = culture=20 emphasizes efficiency over correctness, prudence or safety, = which=20 compounds the problem. It would require a massive amount of=20 education to change this well entrenched programming practice. A=20 consequence of this is that it is unlikely that buffer overflow = vulnerabilities=20 can be eradicated at the source by not introducing them into = a=20 program in the first place. Not only it will be = difficult to=20 eliminate the vulnerability from the enormous quantity of software = already=20 deployed, but it seems likely that programmers will continue to write = new=20 vulnerable software.=20

Miller [ 20 ] studied the behavior of UNIX utilities when given = random input=20 in many distributions, both commercial and open source. His study is = important=20 and relevant to our discussion, because while unexpected input is not=20 necessarily directly related to buffer overflows, the inability of = programs to=20 handle unexpected input comes from the same tendency of programmers to=20 concentrate only on reasonable input that leads also to buffer = overflow=20 flaws. Attackers are not reasonable. On the contrary, they wish to = exploit this=20 blind spot of programmers for unreasonableness, to find a hole in the = program's=20 logic that they can use for their own purposes. So Miller's study = provides some=20 evidence on how common buffer overflow problems are likely to be. = Unfortunately,=20 in almost all distributions more than half of the utilities crashed = under=20 Miller's experiment.=20

Miller also gives us some insight into the speed with which vendors = are=20 making progress in improving the quality of their software, if at all, = because=20 he repeated the study five years later. Indeed, his results show that = progress=20 is being made. But progress has been very modest.=20

Another interesting result of Miller is the confirmation of the = widely held=20 anecdotal belief that Open Source provides significantly higher quality = software=20 than commercial offerings. This seems to suggest the power of somewhat = chaotic=20 large-scale parallelism over better organization of small-scale = parallelism. The=20 former is prevalent in the Open Source model, in which many pairs of = eyes=20 scrutinize the software but relatively uncoordinated. The latter is=20 characteristic of commercial organizations, with fewer pairs of eyes=20 scrutinizing the software but in a much more systematic and organized = fashion.=20
=20

4. Traditional defenses

We now examine some traditional defenses against buffer = overflow=20 vulnerabilities such as the ones discussed in the last section. We = already=20 mentioned the first and most obvious of these which is eliminating = the=20 error from the target program. We have seen briefly at the end of = the last=20 section that unfortunately this approach is unlikely to = succeed. =20 Here we elaborate on further obstacles to this defense.=20

First, there is the magnitude of the problem. To eliminate the=20 bug a very large number of programs must be examined. = The=20 number of potential targets already deployed is very = large. =20 There are some tools that one can use to automate the search for the=20 vulnerability [ 11, 12, 30 ]. For example, a very = simple=20 scheme would be to search for the use of the unsafe = functions in the=20 C library, which like strcpy() have been identified, and replace = them=20 with safe functions which takes the size of the buffer into account, = like=20 strncpy(). Still, manual auditing of the code must be = used =20 for each program which makes this a massive and very = expensive=20 approach. This is not to say that this work should not be=20 undertaken, and indeed there are efforts under way to systematically = audit the=20 code of at least two free versions of Unix , OpenBSD and Linux [ = 19, 23=20 ]. In the case of the former this effort seems to have = already =20 achieved considerable success, accounting for the reputation of OpenBSD = among=20 the security community as being the most secure Unix distribution = currently=20 available. One wonders why similar efforts are not under way by = the=20 commercial vendors of Operating Systems, which one would suppose = could =20 better afford the cost. While the value of such = systematic=20 auditing of code has been successfully demonstrated, the = approach is=20 not guaranteed to produce buffer-overflow-free code. Some = buffer=20 overflows have been found even in already audited code [ 10 ].=20

Not surprisingly, most installations must rely on the vendor to = provide=20 them with reliable code. Even if the source code is = available, they=20 must deploy code which they can't hope to fully understand = themselves. =20 Unfortunately this reliance on the vendor seems misplaced in = many=20 cases, as vulnerabilities seem to be all too common. with most=20 vendors. This rather discouraging state of affairs is very=20 frustrating, yet seems to be the main approach traditionally=20 recommended. Security specialists [ 22, 26 ] recommend that = the=20 administrator of a system follow closely the release of security patches = by the=20 vendor, so that as soon as they are released they can install them. = This =20 presumably makes their systems more secure. However, this = approach =20 has serious shortcomings. The first problem is that it is costly = in terms=20 of the administrator's time and effort. Many systems are=20 administered not by professional system administrators but by = people whose=20 primary job is something else. For these systems this approach is simply = too=20 impractical and untenable. The cure is worse than the disease. = Thus the=20 high cost of this method of defense guarantees that many systems will = fail to=20 install the patches in a timely manner, which in turn provides attackers = with=20 plenty of vulnerable systems, even for vulnerabilities which have = already been=20 fixed. Furthermore, as we remarked in the last section, = programmers=20 keep introducing new vulnerabilities with every new release of the = operating=20 system.
=20

5. Recent defenses

Recently new defenses have been discovered that are more promising = than the=20 traditional approaches discussed above. We examine three = methods and=20 discuss their strengths and weaknesses. One of the attractive = features of=20 all these three methods is that they are all relatively low cost = measures that=20 can be easily implemented by any system administrator = independently of the=20 vendor and they are all effective to some degree against = buffer=20 overflow vulnerabilities not yet discovered. So one of the = common=20 characteristics of these three methods is that they offer valuable=20 protection with current code which is = vulnerable. The=20 other most significant advantage of these methods is that they are = proactive=20 methods of defense rather than the reactive methods discussed in the = previous=20 section. They allow a significant measure of protection without = forcing=20 the administrator to have to wait for the vendor to do something to = secure his=20 system.
=20

5.1 Disabling Stack Execution

Several vendors now offer this method of defense. [ = 7, 18 ]=20 Most systems do not need code to be ever executed on the = stack.=20 Since the most common buffer overflows, as seen in Section 3, rely on = code to be=20 injected into the buffer and then executed, a simple = solution is the=20 option to install the operating system with stack execution = disabled. The=20 idea is simple, inexpensive to install, and relatively effective against = the current crop of attacks.=20

There are some serious weaknesses to this approach. = First, though=20 rare, some programs do rely on the stack to be executable. More=20 importantly, the defense is weak. Though the code in the = current=20 crop of stack based buffer overflows is often stored into the = buffer, a=20 little reflection will immediately reveal that this is not really = essential. The=20 attacker does not care where the attack code is. All the attacker needs = is that=20 this code be somewhere in memory and that it's address or=20 approximate address be known to the attacker so he can overflow the = return=20 address with it to hijack control. We think that it is only a matter of = time=20 before a new crop of buffer overflow attacks will appear that do not = store the=20 code on the stack and which will become immune to this = defense. =20 Wojtczuk explores methods to bypass the non executable = stack=20 defense in [ 31 ]
=20

5.2 Safer C library support

A much more robust alternative would be if we could provide a safe = version to=20 the C library functions on which the attack relies to overwrite the = return=20 address. This idea seems to have occurred independently to = several=20 people. Alexander Snarskii seems to have been the first one to = think of it=20 [ 28 ]. He implemented it for the FreeBSD version of Unix and = offered it=20 to the development group of FreeBSD. His explanation of the = method =20 was unfortunately a little obscure, and either he may not have = fully=20 realized the true power of his method, or if he did, he certainly did = not=20 elaborate on it in his note. Thus Snarskii's = idea had=20 less impact than it should have had. Baratloo, Tsai , and = Singh=20 from Bell Labs independently rediscovered the idea , = and wrote=20 a much more substantial white paper about it [ 2 ]. = This=20 author also rediscovered this defense independently. The = Bell Labs=20 group implemented the vulnerable functions in a library called = LibSafe,=20 which can be freely downloaded from their site.=20

Can we replace a vulnerable function in the C library by a safer=20 version? We will discuss the idea in terms of strcpy(), but = it will=20 become readily apparent that the method generalizes to any of the other=20 vulnerable string manipulation functions. At first = sight a=20 safer version of strcpy() appears impossible because = strcpy() does=20 not know the size of the buffer that it is copying into. So complete = avoidance=20 of overflowing the buffer is not possible. Nonetheless, = strcpy()=20 has access to the dynamic chain on the stack, and successive dynamic = links are=20 like bright markers delimiting the activation records of all the = currently=20 active functions. The idea is to use this information to prevent=20 strcpy() from corrupting the return address or the dynamic link = fields.=20

Using these markers and the address of the buffer itself =20 strcpy() can first determine which activation record = contains=20 the buffer, or else that the buffer is not on the stack at = all. To=20 do this strcpy() finds the interval [a,b] of=20 consecutive dynamic links which contains the buffer. The = cases in=20 which the buffer is either below the first activation record on = the stack,=20 or above the last activation record can be handled as special cases with = appropriate values of either a or b. = Once=20 the values of a and b are determined, we can compute = an=20 upper bound on the size of buffer. For example, if the = buffer grows=20 towards the bottom of the stack then |buffer = -a | =20 is an upper bound on the size of the buffer. This can be = used=20 by strcpy() to limit the length of the copied = string so=20 that neither the dynamic link nor the return address are=20 overwritten. Furthermore, strcpy() can detect = an=20 attempt to do so, report the problem to syslog, and safely = terminate the=20 application.=20

LibSafe does not replace the standard C library. The method = relies=20 instead on the loader searching LibSafe before the standard C = library, so=20 that the safe functions are used instead of the standard library=20 functions. This scheme is more flexible than replacing the = functions=20 in the C library itself. For example, it is possible to have one = program=20 use the C library functions and another use the LibSafe = versions. =20 By setting appropriate environment variables LibSafe can be = installed as=20 the default library. But from a security perspective, there seems = to be=20 little reason to keep the vulnerable functions installed on = the=20 system, so the usefulness of this extra flexibility is somewhat = questionable.=20

This defense has several advantages. It is effective against all = buffer=20 overflow attacks that attempt to smash the stack in which the target = program=20 uses one of the vulnerable C library functions to copy into the = buffer. =20 The method does not totally prevent buffer overflows. It can't, = because it=20 does not know the true size of the buffer. It is still possible to = overflow=20 areas between the buffer and the dynamic link. But the critical return = address=20 and the dynamic link fields are protected from being overwritten.=20

The method fails to provide any protection against heap based buffer = overflow=20 attacks (see below), or attacks which do not need to hijack = control by=20 overwriting the return address. Both of these kinds of = attack,=20 however, are much harder to pull off, and consequently much rarer. = The=20 method would also fail to protect a program that does not use the = standard C=20 library functions to copy into the buffer. For example, if = the =20 target program contains custom code to copy the string into the=20 buffer it will not be protected. However, it seems clear = that few=20 programs will have such custom code. Generally speaking it is = considered=20 to be bad programming practice to "reinvent the wheel", so programmers = are=20 encouraged to use the standard libraries. =20

Though programs that rely on custom code may contain buffer overflow=20 vulnerabilities just as much as those that use the standard C library, = they will=20 be less likely to be detected. Because of this they will enjoy some = immunity=20 from attack. This is security through obscurity, which in general is not = a good=20 way to secure a system. Nonetheless it is of some security value.=20

The overhead of the safe functions is negligible, and the cost of = installing=20 the library and configure the system to use it is very low. = Another=20 advantage is that it works with the binaries of the target program, and = does not=20 require access to their source code. Finally, it can be deployed = without=20 having to wait for the vendor to react to security threats, which is a = very=20 desirable feature. It is a much more robust defense than disabling = stack=20 execution. Though we have discussed variants of attacks against which it = will=20 offer no protection, it is very effective against the class of = attacks=20 that it is designed for, and it cannot be easily circumvented. The = attacker has no way of interfering with the detection of the buffer = overflow=20 attack, because this occurs before the attacker has a chance to hijack=20 control. We conclude that overall, this defense offers a = very=20 significant improvement of the security of a system at very low cost. In = our=20 opinion it is a sure winner.=20

We also mention Andrey Kolishak's BOWall protection [ 16 ]. This is = available=20 for Windows NT systems, with full source. This solution has some = similarities to=20 both the safer Library approach, and to the methods to be presented in = the next=20 Section.=20

Kolishak's approach is similar to the others in this Section, because = it=20 works by replacing the DLL's that contain the vulnerable library = functions with=20 a safer library version. However, unlike LibSafe or Snarskii's = method, it=20 seems to be a buffer overflow detection system, which is more similar to = the=20 methods of the next Section. It works by saving the return address when = the=20 function enters, and checking it before actually returning. If = corruption of the=20 return address is detected it does not return, so hijacking of control = is=20 prevented. Kolishak also has a second component of BOWall which relies = on some=20 specific Windows NT security features.
=20

5.3 Compiler Techniques

Range checking of indices is a defense that is 100% effective=20 against buffer overflow attacks. For example, buffer = overflow=20 attacks are impossible in a Java program, because Java = automatically=20 checks that an array index is within the proper bounds. =20 Unfortunately, full-blown range checking in C is impossible, = because=20 of the dichotomy between arrays and pointers. Some compilers will = offer=20 protection if the array is accessed with an indexing = operation, like=20 in the expression buffer[i] but not in = an=20 expression like buffer + i . When = the=20 compiler compiles a function like strcpy(char* dest , = char*=20 src) the two arguments are just pointers, and it is=20 impossible for the compiler to know the lengths of the corresponding=20 arrays. So the compiler cannot generate code to do range = checking=20 inside of the function. Jones and Kelly implemented some = range=20 checking techniques in C [ 14, 15 ].=20

C programmers do not always appreciate range checking because of the=20 associated overhead, but this excessive preoccupation with=20 performance is often only justified in the most demanding=20 applications. Snappy performance is always a desirable feature, = but for=20 most applications it is much less of a critical issue than programmers = tend to=20 assume. For example, the calendar manager daemon in Solaris has been = shown =20 to be vulnerable to a buffer overflow attack which compromises = root, yet=20 there seems to be no reason why such an application could not have = been=20 written in Java, which would have rendered the attack impossible. = We=20 believe that performance would not have been a critical issue in this = case. Some=20 security flaws have been uncovered in Java and quickly fixed. These = flaws did=20 not invalidate Java's security model, which appears to be sound, but = usually=20 were implementation problems of the Java Virtual Machine, which of = course is=20 just another C program, so subject to the same programmer errors as any = other=20 program [ 6 ].
=20

Cowan, Wagle, Pu, Beattie and Walpole [ 4 ] devised a = fresh =20 approach to the problem. Their method does not = prevent =20 the corruption of the return address and dynamic link, but instead = prevents the hijacking of control by detecting that an attack took = place=20 before the control is hijacked. Just as was the case with the safe = library=20 approach, the key idea is simple and elegant. It is based on the = assumption that=20 if a buffer overflow attack took place then everything between the = buffer and=20 the return address is likely to be corrupted. They propose to = modify the=20 compiler so that it protects the critical return address and dynamic = link part=20 of the activation record by allocating an extra field aptly called = the =20 canary after the dynamic link and before the local = variables=20 in the activation record. When the activation record is pushed on = the=20 stack a value is stored in the canary field. Before the function returns = the=20 integrity of the canary is checked. If it was corrupted the canary sings = and the=20 attack is detected. (Equivalently, another possible metaphor, is to say = that the=20 attack makes the canary die. This is analogous to the use of canaries in = mines.)=20 In this case, the program is gracefully terminated with an syslog = error=20 message alerting about the buffer overflow thus thwarting the = attack. =20 These ideas were implemented in the StackGuard = project and=20 used in some experiments to protect an entire Linux distribution = recompiled with=20 this technique.=20

To avoid the possibility of the attacker forging = the value=20 stored in the canary they propose either storing terminator = symbols, like=20 the null character, carriage return , line feed, and eof, whose = inclusion=20 in the payload string would stop the copying operation by the various = vulnerable=20 functions of the C library, or to choose a random canary value, = chosen=20 independently each time the program is started, which would make = its=20 forging very difficult for the attacker.=20

"Bulba" and "Kil3r" explored ways that StackGuard could = be=20 circumvented [ 3 ]. For example, they reasoned that if a pointer = variable=20 were between the buffer and the return address, then a first buffer = overflow=20 could corrupt this pointer variable, without corrupting anything else, = so as to=20 make it point to the return address field. A second copying operation = then could=20 overwrite the return address without corrupting the canary. = This=20 would defeat the StackGuard protection by avoiding the = basic=20 assumption that everything between the buffer and the return = address must=20 have been corrupted by a buffer overflow. To deal with such an=20 attack Cowan proposed an even better choice to be stored in = the=20 canary, namely he proposed to store a value that depended both on = a random=20 value and the correct return address. Specifically, he proposed to = compute=20 the XOR of these two values. This countermeasure was easy to = implement,=20 and it would detect the attack even if the canary was not changed. =
=20

"Bulba" and "Kil3r" demonstrate that their techniques work with = examples of=20 vulnerable code. But in our opinion these attacks are = somewhat=20 optimistic about the conditions that must be present in the target = program=20 for the attack to work, so that their techniques currently seem more a = proof of=20 concept than a serious and immediate threat to defeat the = StackGuard=20 defense. It is quite possible that such target programs exist and = are=20 deployed widely enough for their techniques to become a serious breach = of the=20 defense, but that has not been demonstrated yet. Of = course, =20 one must be always vigilant when dealing with security, and the = prudent =20 approach is always to assume that no defense is foolproof. =
=20

The performance overhead of StackGuard is worse than = that of the=20 LibSafe defense, in part because = StackGuard =20 imposes an overhead on every function called, but = better than=20 the overhead of range checking which incurs a small extra cost on every = array=20 access. In any event, this overhead is still = small. =20 StackGuard is effective even against custom code, since=20 StackGuard is a buffer overflow detection method, so it does not = care how=20 the buffer overflow happened. However we noted that custom code = attacks=20 seem to be less likely than those that rely on the standard = library=20 functions. On the other hand, assuming that an = administrator=20 has access to the modified compiler, the cost of protection is = much larger=20 than that of the LibSafe approach, because it requires = recompilation of=20 every target program to be protected. This also means that one has = to have=20 access to the source code of the target program, or put another = way,=20 StackGuard cannot protect a program for which we have no source = code,=20 whereas LibSafe can.=20

In some ways the three methods discussed in this section are = complementary,=20 so they can be applied independently and simultaneously. By doing so = the =20 robustness against future attacks circumventing the defenses is also=20 enhanced. Given the very low cost of deployment and = overhead=20 of the first two methods, and moderate cost of deployment and low = overhead =20 for the last one, deploying these methods should be recommended.=20
=20

6. Buffer Overflow Variants

We mentioned earlier that the Morris worm used several methods to try = to=20 infect a machine, one of which was essentially a stack=20 smashing attack on fingerd. This part of the=20 worm sent a TCP/IP packet to port 79, the = finger port .=20 The packet consisted of 400 VAX nop instructions, = followed by=20 code that exec'd a shell, followed by a part = that would=20 overflow the return address to point to this code. The worm also = attacked=20 Sun machines with a similarly constructed packet, but there = was an=20 error in the part that was supposed to overwrite the return = address in the=20 Sun version, which caused it to fail, even though the Suns were also=20 vulnerable. fingerd parsed its input by reading = it=20 into a local buffer of 512 bytes with gets(). The = above=20 packet had 536 bytes, so this caused it to overflow and corrupt the = return=20 address. Once the control was hijacked, the shell would read its = input=20 from the network connection and write it's output to the network = connection. The=20 client side that had sent this packet would then send over a = C=20 program of the worm, which was compiled and then run on the newly = infected=20 machine [ 9 ].=20

Though the fingerd attack was a straightforward stack = smashing=20 attack, exactly as described in Section 3, initially it found few = imitators.=20 Perhaps it was not realized for a while how widespread the vulnerability = was in=20 other targets as well. Another factor may have been that the worm was = fairly=20 complex, and the fingerd attack was just one of several methods = used by=20 it. Because of this it may have been understood by a relatively small = number of=20 people. It was not until the publication of Levy's paper in Phrack that = the=20 hacker community seem to have realized that many programs were = likely to=20 harbor a stack smashing vulnerability.=20

Once the stack smashing attack was well understood variants started = to=20 appear. We discuss some of these variants in this section. Looking = at=20 the general steps of a buffer overflow attack that we=20 discussed in Section 2, we may see the possible variants. In = some=20 programs there is no need for Step 1 (planting the attack code) = because=20 the code might be already present in the target program. In such=20 cases Step 2 (overflowing the buffer) might seek to corrupt not = the return=20 address but another resource. For example, the string that the code = would=20 exec. In this case the hijacking of control works=20 differently.=20

In the stack smashing examples, Step 1 (planting the attack = code) might=20 be accomplished in several ways: through an input to the = target=20 program, or an environment variable, or a network port on which the = target=20 program listens (as in fingerd, basically just another form of = input).=20 The buffer overflow of Step 2 copies the planted code into the = buffer and=20 overwrites the return address on the stack. The hijacking of control = occurs when=20 the function returns to the wrong return address, and executes the = attack code=20 instead.
=20

While the stack is convenient for Steps 2 and 3 of the attack, = we may=20 look at other ways that a program may hijack control not involving the = stack.=20 These will then lead to a different class of potential=20 attacks. Any structure in which function pointers are = stored, or=20 addresses to which the program will jump are potential targets for Step = 3. =20 If these structures can be corrupted by a buffer=20 overflow, we have a potential new technique for an attack. = If the=20 pattern necessary to carry this out is also sufficiently widespread we = have=20 another dangerous variant.=20

For example, heap based attacks are possible in C++ targets[ 24=20 ]. Each object has a virtual function table = where each=20 entry points to the corresponding member function of the=20 object. By corrupting the virtual function table of an = object ,=20 control can be hijacked when any of the object's operations is invoked. = Instead=20 of executing the object's intended operation, the attack code will be=20 executed. Every object-oriented program will have this pattern, so = in=20 theory this looks quite promising. But the difficulty here = is=20 finding an application in which an adjacent object has a buffer that can = be=20 overflown. The order in which objects are allocated on the heap = depends on=20 the particular run-time conditions present, so might be frequently = difficult or=20 impossible to predict. Consequently, the chances of a successful attack = through=20 heap based buffer overflows that corrupt the virtual function table are = much=20 more difficult to carry out than the stack smashing attack.
=20

7. Conclusions

We have analyzed the characteristics of several buffer = overflow=20 attacks, the reasons for their popularity, and the effectiveness and = costs of=20 various defenses against them. Until recently the attackers seemed = to have=20 the upper hand, and the traditional defenses seemed largely impotent to = stop=20 these attacks. We analyzed the reasons for this. Among the reasons we = cited are=20 the cost of deployment of the traditional defenses, the reactive = nature of=20 the methods of defense, and the dependence of the average installation = on=20 the operating system vendor to provide the solutions to the=20 attacks. The recent appearance of effective defenses = that=20 break some of these obstacles give reason for hope that finally the = defenders=20 might have a chance to gain the upper hand against this type = of=20 attack.

=20

8. References

Stefan Axelsson, A Comparison of the Security of Windows NT and = UNIX, 1998=20
http://www.securityfocus.com/data/library/nt-vs-un= ix.pdf=20
Arash Baratloo, Timothy Tsai, and Navjot Singh, Libsafe: = Protecting=20 Critical Elements of Stacks
http://www.securityfocus.com/library/2267=20
http://www.bell-labs.com/org/11356/libsafe.html =
Bulba and Kil3r, Bypassing StackGuard and Stackshield, Phrack = Magazine=20 56 No 5, 1999.
http://phrack.infonexus.com/search.phtml?view&= article=3Dp56-5=20
Crispin Cowan, Perry Wagle, Calton Pu, Steve Beattie, and Jonathan = Walpole, Buffer Overflows: Attacks and Defenses for the Vulnerability = of the=20 Decade, in DARPA Information Survivability Conference and Expo = 2000.=20
<= FONT=20 = face=3DArial,Helvetica>http://www.cse.ogi.edu/DISC/projects/immunix/publi= cations.html=20
http://www.securityfocus.com/library/1674=20
David Curry, Improving the Security of your Unix System, 1990 =
http://www.securityfocus.com/library/1913=20
Drew Dean, Edward W. Felten, and Dan S. Wallach, Java Security: = From=20 HotJava to Netscape and Beyond, in Proc. of the IEEE Symp. on = Security and=20 Privacy, 1996
http://www.cs.princeton.edu/sip/pub/secure96.html =
Casper Dik, Non-Executable Stack for Solaris, posted to=20 comp.security.unix January 2, 1997.
http://x10.dejanews.com/
DilDog, The TAO of Windows Buffer Overflow, 1998
http://www.cultdeadcow.com/cDc_files/cDc-351/=20
Mark W. Eichin and Jon A. Rochlis, With Microscope and Tweezers: = An=20 Analysis of the Internet Virus of November 1988, 1988.
http://www.mit.edu:8001/people/eichin/www/virus/ma= in.html=20
Chris Evans, Nasty Security Hole in lprm, posted in = BugTraq,=20 April 18, 1998
http://www.securityfocus.com/archive/1/9023=20
HalVar Flake, Auditing Binaries for Security Vulnerabilities, in = Black=20 Hat Europe Conference, 2000.
http://www.blackhat.com/html/bh-europe-00/bh-europ= e-00-speakers.html=20
Nishad Herath, (Joey_) Advanced Windows NT Security, in Black = Hat Asia=20 Conference, 2000.
http://www.blackhat.com/html/bh-asia-00/bh-europe-= 00-speakers.html#Joey=20
Barnaby Jack, (dark spyrit), Win32 Buffer Overflows (Location,=20 Exploitation, and Prevention), Phrack Magazine 55,(15), 1999. =
http://phrack.infonexus.com/search.phtml?view&= article=3Dp55-15=20
Richard Jones, Bounds Checking Patches for gcc.
http://web.inter.NL.net/hcc/Haj.Ten.Brugge=20
Richard Jones and Paul Kelly, Bounds Checking for C, 1995
http://www-ala.doc.ic.ac.uk/phjk/BoundsChecking.ht= ml=20
Andrey Kolishak, BOWall, (Buffer Overflow Protection for Windows = NT), 2000=20
http://developer.nizhny.ru/bo/eng/BOWall=20
Elias Levy (alpha1), Smashing the Stack for Fun and Profit, = Phrack=20 Magazine 49 (14), 1996.
http://phrack.infonexus.com/search.phtml?view&= article=3Dp49-14=20
The Linux OpenWall Project, Nonexecutable Stack Patch for Linux =
http://www.openwall.com/linux/ =
The Linux Security Audit Project,
http://lsap.org/
Barton P. Miller, Fuzz Revisited: A Re-examination of the = Reliability of=20 Unix Utilities and Services, 1998
http://www.securityfocus.com/library/2087=20
Mudge, How to Write Buffer Overflows, 1997
http://l0pht.com/advisories/buffero.html=20
Ryan Russel, Rain Forest Puppy, Elias Levy, Blue Boar, Dan = Kaminsky,=20 Oliver Friedrichs, Riley Eller, Greg Hoglund, Jeremy Rauch, and Georgi = Guninski, Hack Proofing Your Network Internet Tradecraft, = Syngress,=20 2000.
Theo Raadt, OpenBSD Security
http://openbsd.org/security.html =
rix, Smashing C++ VPTRS, Phrack Magazine 56 (8), 2000. =
http://phrack.infonexus.com/search.phtml?view&= article=3Dp56-8=20
W. Olin Sibert, Malicious Data and Computer Security, 1996.
http://www.securityfocus.com/library/2168=20
Joel Scambray, Stuart McClure, George Kurtz, Hacking Exposed, = Network=20 Security Secrets & Solutions , Second Edition, = Osborne/McGrawHill ,=20 2001
Nathan P. Smith, Stack Smashing Vulnerabilities in the UNIX = Operating=20 System, 1997.
http://millcomm.com/nate/machines/security/stack-s= mashing/nate-buffer.ps=20
Alexander Snarskii, FreeBSD Stack Integrity Patch, 1997
ftp.lucky.net/pub/unix/local/libc-letter=20
Eugene Spafford, The Internet Worm Program: Analysis, Computer=20 Communications Review, 1989
David Wagner, Jeffrey S Foster, Eric A. Brewer, and Alexander = Aiken, A=20 First Step towards Automated Detection of Buffer Overrun = Vulnerabilities, in=20 Proc. 7th Network and Distributed System Security Symposium = 2000.=20
http://www.cs.berkeley.edu/~daw/papers/overruns-nd= ss00.ps=20
Rafel Wojtczuk, Defeating Solar Designer's Non-Executable Stack = Patch, in=20 Bugtraq, January 30 1998
http://www.securityfocus.com/templates/archive.pik= e?list=3D1&mid=3D8470&fromthread=3D0&date=3D1998-01-30=20