Nasim Vafai – 97300 4015
Roozbeh Ghafary – 20001 6974
Percy Shroff – 20001 6131
May 2002.


Introduction

 

he exploitation of buffer overflow vulnerabilities is an important and persistent security problem.  With the widespread growth of the Internet, efforts to forcibly gain access to remote systems have increased. Many security assaults, such as the 1988 Internet Worm [ER89], will be remembered in Internet history. Some of these attacks, such as the Internet Worm, purely frustrate or occupy system resources.  However, other attacks may be more menacing as they are capable of seizing root privileges and modifying, corrupting, or stealing data. Buffer overflow problems have been and are still liable for a large number of security breaches.  Of the 44 CERT advisories published between 1997 and 1999, 24 were related to buffer overflow issues [Thomas].

 

Figure I1: Number of Reported CERT Security Advisories Attributable to Buffer Overflow [WFBA00].

 

Figure I1 illustrates the noticeable increase in the number of reported CERT [CERT] security advisories that are based on buffer overflow security breaches.  Recently, approximately half of all reported CERT advisories include attacks that exploit buffer overflow bugs

 

Programs created in the C programming language have been notoriously plagued with buffer overflow bugs. There are two main reasons that cause this. Firstly, C does not perform automatic bounds checking for arrays and pointer references. Secondly, and more importantly, many functions that are offered by the standard C library, such as those given below in Table I1, are insecure.

 

Table I1: Partial List of Unsafe Functions in the Standard C Library [BTS99].

 

Hence, the effort is passed to the programmers to explicitly ensure that the uses of such functions do not overflow the buffer. Nevertheless, most often, programmers omit to perform such checks.  Subsequently, a significant number of programs are plagued with buffer overflow bugs, which makes them extremely vulnerable to security attacks.  Thus, passing the effort to programmers to verify against such vulnerabilities has largely been unsuccessful.  In order to guard against this many tools have been developed and implemented in order to automatically safeguard programs against buffer overflow vulnerabilities. 

 

This paper is a survey based research project concerning tools that automate buffer overflow checks particularly for the C programming language.  We have endeavoured to provide an in-depth analysis of a few tools that are being widely used.  These tools have different designs and implementations, which we have attempted to analyse in detail.  Hence, for each tool we have provided our findings regarding their various design and implementation issues, which also include their limitations.  Through our research we discovered that many tools had significant disparities between their theoretical design and features versus their practical usage, which we also endeavoured to ascertain.  However, before introducing the tools we feel that a good understanding regarding the issues of the buffer overflow problem would be fitting.

 

What Does Overflowing the Buffer Mean?

 

 

The simplest forms of attacks are buffer overflow assaults. Although buffer overflow attacks do not require a great effort to implement, they may be prevented. A buffer overflow is the result of careless programming and the C language and its features [Farrow99]. A buffer overflow occurs when a function writes beyond the boundaries of the destination buffer and hence overwrites the content immediately after or before it [FX01].  Below are summarized descriptions of the two most popular classes of buffer overflow attacks:

  1. Stack smashing
  2. Heap smashing

 

1.      Stack Smashing

 

Undoubtedly, the most popular form of buffer overflow abuse is attacking buffers on the stack, which is referred to as the stack smashing attack. Processes are divided into three regions: Text, Data and Stack (See Figure B1). The text region is generally marked read-only and corresponds to the text code of the executable file. The size of this region is fixed. The data region contains statically defined data and corresponds to the data-bss section of the executable file. Its size can be changed by the ‘brk (2)’ system call in Linux. If this system-call expands the memory so much that the allocated memory space is surpassed, the process will be blocked and it will be scheduled to run with a more memory allocated to it. [One]

 

Text
- lower memory addresses

(Initialized) 

Data

(Uninitialized) 
Stack
- higher memory addresses

Fig. B1 Process Memory Regions [copied from One]

 

The stack is a first-in-first-out data storage system. The very last thing that is stored on the memory stack is the very first thing that will be picked up. The idea of storing something on the stack is called pushing and retrieving data from the stack is called popping. A stack pointer always points to the head of the stack where data can be pushed onto or popped out from the stack. The stack pointer is implemented as a register in most processors. A program counter, PC, keeps track of the memory address of the next instruction to be executed by the CPU.

 

When a function is called, the return address as well as all the function parameters is pushed onto the stack. Apart from this, any variables defined within the function are also stored in an allotted space on the stack. For example, if a string is defined in the function, a number of bytes will be assigned on the stack. The function may then use this piece of memory, which will be automatically unallocated subsequently after the function returns. However, the C programming language does not provide any bounds checking when data is stored in this area.  This opens a potential security breach that may be compromised by an attacker, as it is easy for programmers to write past the end of the buffer. The following code illustrates this point:

 

void foo() {

            int z[100];

            z[200] = 7;

}

 

Generally, writing past the end of the buffer causes the program to crash with a segmentation fault error, and does not necessarily result in a security breach. In order for a security susceptibility to transpire, two conditions must be satisfied:

i)                    The attacker should be able to have power over data written into the buffer.

ii)                   In memory there should be security sensitive variables stored after the buffer.

 

There are a number of C functions that do not provide any bound checking to ensure that the data being passed into the function fits inside the buffer, which has been allocated to that function for its local use.  Some of these functions are: strcat(), strcpy(), sprintf(), vsprintf(), bcopy(), gets(), and scanf() [Farrow99]. Thus hacker may provide a long string that causes the buffer to overflow over previously stored security sensitive variables. Then the hacker may put his own code to be executed on the stack, which gives him control over the data written on the buffer.  In this class of buffer overflow attacks, attackers compromise the integrity and control of the return address.  Figure B2 provides a visual explanation of how exactly such buffer overflows occur.

Figure B2 [Farrow99].

 

2.      Heap Smashing

 

Heap smashing attacks, or variable attacks, are another class of less likely occurring buffer overflow attacks.  These attacks are not aimed at the return address, but target overwriting other sensitive variables of a process.

 

Heap smashing attacks overrun a heap buffer to change the control flow of a program. For example, such an overflow could overwrite function pointers stored on the heap to redirect the control flow of a program [FX01].  Figure B3 illustrates a network service, which runs in root mode. Function f is stored after an allocated buffer p on the heap. Legitimate clients use the network service by sending packets of size 28 bytes (the size of the buffer). An attacker could send a larger packet. As illustrated in figure B4 b), once the unsafe C function call to strcpy() is performed, f[0] is overwritten as no boundary check is provided by strcpy(). Consequently once this function is called, the attacker will gain root access to the computer by hijacking the control of the root-privileged service.

 

Figure B3: Program With Heap Smashing Attack [FX01].

 

 

Figure B4: Heap Smashing Attack As Implemented Above [FX01].

 

 

The following section of our research paper consists of tools that automate buffer overflow checks particularly for the C programming language.  Even though there is no single tool that is able to completely solve the buffer overflow security problem, there are currently many tools that can increase the probability of detecting buffer overflows and reducing an attacker's chance of successfully exploiting such vulnerabilities.


Software Security Tools

 

1.      Libsafe

 

Overview

 

Libsafe uses an original method for effectively detecting and handling buffer overflow attacks. Without requiring any source code, it transparently protects processes against stack smashing attacks, even on a system-wide basis. It does this by intercepting all calls to library functions that are recognised as vulnerable. Then an alternate version of the corresponding function is used to implement the original functionality, but in a secure manner, that ensures any buffer overflows are restrained within the current stack frame.  Libsafe has been implemented on Linux as a dynamically ‘loadable’ library.  It has been shown to successfully detect many known attacks and can potentially prevent even unknown attacks.

 

Implementation

 

The key idea behind Libsafe is the ability to automatically assess a safe upper limit on the size of buffers. Since the size of the buffer may not be known at compile time this cannot be performed then.  Hence the calculation of the buffer size is made after the start of the function in which the buffer has been accessed. This tool is able to determine the maximum buffer size by understanding that such local buffers cannot possibly extend beyond the end of the current stack frame. This awareness allows the substitute version of the function, which is used to implement the original functionality, to confine buffer writes within the estimated buffer size. Hence, the return address from that function, which is located on the stack, cannot be overwritten (stack smashing) and control of the process cannot be seized.

 

Libsafe does not need any alterations to the operating system, and works with existing binary programs. It does not require access to the source code of defective programs, nor does it require recompilation or off-line processing of binaries  [Avaya01]. Furthermore, it can be transparently implemented on a system-wide basis. It is based on an intermediate software layer that intercepts all function calls made to library functions that are known to be unsafe.

 

Libsafe is built around the following essential observations:

·        Overflowing a stack variable, i.e. inserting the attack code into a running process may not lead to a triumphant stack smashing attack. This is because the attack must also avert the execution sequence of a process to run the attack code.

·        Although buffer overflows cannot be terminated in general, automatic and transparent run-time mechanisms may prevent the overflow from corrupting a return address and diverting the control flow of a process.

 

Below (Figure L1) is an implementation of strcpy() which is as an example to explain Libsafe’s implementation technique.

 

 

Figure L1: A Process Undergoing a Stack Smashing Attack [BTS00]

 

In figure L1(a), at the time strcpy() is called, the frame pointer is pointing to a memory location that contains the preceding frame's frame pointer. Furthermore, the frame pointer divides the stack variables, which are local to the current function, from the parameters that are passed to the function. As in the above example the size of buffer and all other stack variables residing on the top frame cannot extend beyond the frame pointer.  Thus this is a safe upper limit. Also a correct C program should never explicitly change any stored frame pointers, nor should it explicitly alter any return addresses that are located near the frame pointers. This information is used to detect and confine stack buffer overflows. Thus, the attack executed by calling the strcpy() may be discovered and completed before the return address is corrupted (as in Figure L1(b)). In the case when a local buffer, that is on one of the previous stack frames is used, frame pointers are traversed up the stack until the right stack frame is found.  Then Libsafe computes the upper bound of the stack.

 

The above is implemented as a dynamically loadable library that is preloaded with every process it needs to protect. The preloading injects the Libsafe library between the program code and the dynamically loadable standard C library functions. [BTS99]  The library may then intercept and perform a bound checking for the arguments before allowing the standard C library functions to execute. In particular, it intercepts the unsafe functions in order to provide:

·        Correct programs will execute accurately, i.e. no occurrences of false positives.

·        The frame pointers and return addresses may never be overwritten by an intercepted function.  Thus an overflow leading to overwriting the return address is ceaselessly detected.

 

Figure L2: Libsafe Containment of Buffer Overflow [BTS99]

 

Figure L2 portrays the memory of a process linked with the Libsafe library, and also shows the new (substitute) implementation of strcpy() in the Libsafe library. Once the program calls strcpy(), this substitute version contained in the Libsafe library is executed.  This occurs due to the order in which the libraries were loaded. The Libsafe implementation of the strcpy() function firstly determines the length of the source string and the upper bound on the size of the destination buffer, as previously explained. It then confirms that the length of the source string is less than the bound on the destination buffer. If the inspection succeeds, then the strcpy() function calls the memcpy() method, which is implemented in the standard C library, in order to perform the operation. But if the verification fails, strcpy() creates an entry in syslog and ends the program. The same technique is used for other unsafe functions within the standard C library.

 

Performance

 

Libsafe requires extra code to detect stack-smashing attacks.  That supplementary code comes with a cost - a performance overhead.

 

Libsafe Tests

 

Figure L3: Performance of Libsafe Functions[1] [BTS99]

 

The execution times of five unsafe C library functions have been measured and compared with their corresponding ‘safe’ versions in Figure L3.  This was done in order to quantify the performance overhead of the Libsafe library.  The reported times are ‘wall clock’ elapsed times as reported by gettimeofday()[BTS99]. From the above, an interesting observation is that the Libsafe versions of many functions outperform the primary versions. This behaviour was consistently repeatedly found and observed on different machines and operating system versions. This consequence is because of both low-level optimizations, and the fact that Libsafe's execution of most functions is unlike those of the standard C library. For example, consider the performance of the getwd() and sprintf() functions. The Libsafe library replaces these functions with corresponding safe versions. getwd() is replaced with getcwd() and sprintf() is replaced with snprintf().  These safe substitute versions were found to execute faster on the Linux platform. 

 

The figure also indicates that the Libsafe library may slow down the string operations strcpy() and strcat() by approximately 0.5 ms per function call. Nevertheless, as the string size grows, the absolute overhead shrinks because the execution time of the safe versions increases more slowly than that for the unsafe versions. Moreover, the safe version of strcat() used with strings that are longer than 256 bytes is actually quicker than the unsafe version.  This is an example that shows how using a different implementation (e.g., using memcpy() to copy a string) can outperform the standard implementation for particular cases. 

 

Theoretical Design Versus Practical Implementation

 

An interesting positive attribute is Libsafe’s performance.  It has a low performance overhead even in practice. This is due to low-level optimizations, and because Libsafe’s execution of most functions is different than those of the standard C library.  For some applications there is an actual observed speedup. 

 

Libsafe does nothing for applications, which are statically linked, as it is implemented as a dynamically loadable library that is preloaded with every process it needs to protect.  Thus in such a situation it would neither provide any benefits nor any harm.  Also Libsafe does not work for applications that have been compiled with the old Linux C library version 5 (run-time libraries). 

 

For software developers, Libsafe seems to appear as a useful mechanism to support defence-in-depth.  However, below are some reasons why Libsafe may not be completely depended upon during code development:

 

The Libsafe developers themselves acknowledge that software developers should not just depend on Libsafe. In their words:

“It is generally accepted that the best solution to buffer overflow attacks is to fix the defective programs. However, fixing defective programs requires knowing that a particular program is defective. The true benefit of using libsafe and other alternative security measures is protection against future attacks on programs that are not yet known to be vulnerable.” [Wheeler02]

 

Libsafe’s greatest benefit appears to be its ability to prevent yet unknown attacks.  It is generally accepted that the best solution to buffer overflow (and format string attacks) is to fix the actual defective programs. However, fixing these defective programs require first knowing that a particular program is defective. This may not always be possible.  Thus Libsafe’s protection against future attacks on programs that are not yet known to be vulnerable is a very useful trait.

 

Conclusion

Experiments indicate that the performance overhead of Libsafe is negligible.  The stability, minimal performance overhead, and ease of implementation (through no amendment or recompilation of source code) of Libsafe make it an attractive defence against stack smashing attacks.  Not many systems use Libsafe today, which adds to its effective security.  Although it might be possible to still exploit these bugs with Libsafe installed, few people actually run it so the attackers are not targeting Libsafe protected computers. In the future that might change and Libsafe may become less of a benefit.

 

2.      ITS4 - It's The Software Stupid! Security Scanner

 

Overview

 

ITS4 is a tool for statically scanning security-critical C source code for vulnerabilities [VBKM01]. This tool is able to recognize potentially unsafe function calls, which may lead to buffer overflow conditions and warns the programmer suitably.  ITS4 examines C or C++ source code, and its output contains a list of potential security holes in the source.  The tool suggests alternative methods for resolving these potential problems.  Both the problems and suggested solutions are read from a database file.  This file may be easily updated or customized by the user.

 

ITS4 runs on UNIX, but was written in such a way that it can be easily ported to Windows. It can also be easily integrated into other development environments and is already available for the development environment Emacs. [BST01]

 

Implementation

 

Initial Scanning and Assessment

 

ITS4 takes one or more C or C++ source files as input and breaks each one into a stream of tokens. After scanning a file ITS4 examines the resultant token stream, comparing identifiers against a database of “suspects.” [VBKM01]

 

Examining every identifier is a heuristic that may not be entirely precise - security-neutral identifiers may be flagged.  A common example would be variable names. Consider the following C code:

int main()

{

int strcpy;

return 0;

}

 

Running ITS4 on the above code would produce the following results:

[viega@lima c]$ its4 test1.c

test1.c:3:(Very Risky) strcpy

This function is high risk for buffer overflows.

Use strncpy instead.

[VBKM00]

 

A false positive in the case of the declaration of strcpy should be avoided. However, without any form of ‘real’ parsing it would not be possible to accurately determine all identifiers that are lexically used as variables. This is mainly because the pre-processor could arbitrarily modify the identifiers.  In the above code, both the type ‘int’ and the variable ‘strcpy’ may be replaced with arbitrary code. To handle this a full pre-processor is needed to be implemented, as the programmer may perform arbitrarily complex tasks. ITS4 combats this problem by restricting checks to those identifiers followed by a left parenthesis, as programmers do not usually distort the pre-processor in this manner.  This is because a simpler analysis usually is sufficient for most practical applications. For example, programmers do not generally use ‘strcpy’ as a variable name. ITS4 has an option to flag all suspect identifiers if the examiner is anxious about possible false negatives.

 

The Vulnerability Database

 

Upon start-up ITS4 reads a vulnerability database from a text file and keeps the whole content in memory for the tool’s lifetime. Vulnerabilities may be added, removed, and changed from this database with ease thereby enabling ITS4 to guard against a large range of vulnerabilities.  Currently ITS4’s vulnerability database contains a large number of entries of which functions susceptible to buffer overflows account for many.  Thus developers may use these functions to shuffle cards or generate cryptographic keys in situations where security is important [VBKM01].

 

The following information is stored in the database:

NO RISK, LOW RISK, MODERATE RISK, RISKY, VERY RISKY, MOST RISKY.

 

Upon flagging a function name, ITS4 searches the vulnerability database for a ‘handler’ for that function. This handler is responsible for reporting the flagged problem. If no such handler is present in the vulnerability database then a default handler is used.  This default handler simply adds the problem to the results database.

 

ITS4 Commands

 

It is possible for ITS4 to disregard specific occurrences of a particular function. Even though such a feature may be detrimental, as misappropriate use could cause ITS4 to ignore real vulnerabilities, it is useful for trimming the output. This is because individual vulnerabilities can be manually inspected and eliminated.  For example, a developer could add a strcpy method to a work-in-progress. Then after executing ITS4, they discover the potential problem and resolve it by adding an explicit bounds-check prior to the call.  Currently ITS4 cannot perform a complicated enough analysis to verify that such a check is there. Thus, it will always flag that instance of strcpy. There should be a technique to solve this error.

 

This problem may be amended two ways:

The developer may insert in-place comments along with embedded commands to the scanner. For example -

strcpy(buf, dst); // ITS4: ignore

This will cause the above to be ignored. Since it deals with the line of code it affects, the comment is usually placed on the same line as that code.  If there is no code on the same line, it will affect the following line (not the one prior to it). The case-insensitive text “ITS4:” must be present in the comment, followed by an optional list of function calls. The elements in the list may be separated by commas. Other than this only white spaces may appear in the comment. If no calls are specified, ITS4 will pay no attention to any function call on the affected line.  When there is no option to alter the source code, it is possible for the user to keep a list of ITS4 commands in a file.  The file name and line number to which the command applies are also held.  The location of this file is specified by the user on the command line. To allow inspection of code that already has ITS4 commands set in it, the tool offers a command line option to allow disregarding all commands.  It also provides options to minimize the output and to display the output in a more useful manner. For example, the user may choose between many different available sorting methods, and vulnerabilities may be filtered based on their levels of risk.

 

Theoretical Design Versus Practical Implementation

 

ITS4 breaks a non-preprocessed file into a series of lexical tokens, and then matches patterns in that stream of tokens [VBKM01]. Matching code is manually added; so non-regular patterns may be discovered. When performing more complex static analysis, it would be simpler to use a fairly comprehensive, easy-to-navigate depiction of a program, such as a parse tree generated with a context-free parser.  However, the developers chose not to use a “real parser” for the following reasons:

  1. They wanted to have a false negative rate as close to 0 as possible.
  2. In order to support interactive programming, “real” context-free parsing is not used in ITS4.  Thus interactive programming environments such as Emacs and Microsoft Visual C++ may be supported in real time. In order to support compatibility with already existing applications the ITS4 developers have highlighted errors in the same manner that misspelled words are highlighted by Microsoft Office applications. Thus as the programmer enters code, the programming environment recognizes the possibility that a specific piece of code may contain certain vulnerabilities and acts suitably.

 

ITS4 has the following current limitations (of advanced static analysis) for C and C++ programming languages:

 

The following are the limitations of the vulnerability database:

  1. Measures of severity should be refined based on feedback from the security community.
  2. The descriptions and recommendations should be expanded.
  3. Several additional fields would be desirable, such as a detailed code example on how to mitigate the problem.
  4. The database currently contains primarily Unix vulnerabilities; Windows vulnerabilities should be added.

[VBKM01]

 

Practical experiences using ITS4

 

·        ITS4 requires a high level of expert knowledge.  Even though it does encode a large amount of information on vulnerabilities that developers do not need to memorize, an expert would still perform better than a novice.  Experts would tend to be far more efficient and accurate at taking a potential vulnerability location and manually performing the static analysis necessary to determine whether an exploit is possible, than a novice.

·        Analysis is time consuming, even for experts. ITS4 only eliminates approximately one quarter to one third of the time it takes to perform such analyses, since the manual analysis is quite time consuming.

·        ITS4 can help discover real bugs. Using ITS4, buffer overflow vulnerabilities were successfully discovered. 

 

Future directions for ITS4

 

The following consist of practical improvements that may be made to ITS4:

 

Conclusion

 

ITS4’s scanning technique stakes out a new middle ground between accuracy and efficiency [VBKM01].  Even though its parsing model makes it not suitable for high precision static analysis, the equivalent model makes the tool quite useful for real-world use.  This is because ITS4 can scan large programs efficiently, and achieve sufficient results. The tool is well suited for integrating into programming environments with little alterations. On the other hand, its current limitations would cause it to take some more time before producing a more robust, accurate and practical tool. 

 

 

3.      Splint - Secure Programming Lint

 

Overview

 

Splint was previously known as LCLint[2].  It is a lightweight static analysis tool for ANSI C [LE02].  It was designed to enable minimal programmer effort without requiring significant changes to conventional development processes, and was developed as a tool that would not require any user interaction.  It was intended to be fast and as easy to use as a typical compiler.  It does not currently support C++.

 

The developers believed it reasonable to make compromises that increase the class of properties that may be checked while sacrificing soundness and completeness.  While this would not be acceptable in many environments, it is a desirable trade-off in a typical industrial development environment where cost-effective detection of program bugs is the overriding goal [Evans00].  Splint is capable of performing checking that no compiler can do by utilizing annotations that have been added to libraries and source code in programs. 

 

The degree of better results depends upon the effort put into annotating programs. A representational effort-benefit curve for using Splint is shown in Figure SP1 [Evans01].  Splint was made to allow programmers to choose appropriate points on the effort-benefit curve for particular objects.  Thus it enables a degree of flexibility.  As different checks are enabled more information would be provided in annotations within source code, and the number of bugs that would be detected would also increase dramatically.

 

Figure SP1.  Typical Effort-Benefit Curve [Evans01]

 

Splint is able to detect the following problems in programs (however our paper will cover only those associated with buffer overflows):

·        Dereferencing a possibly null pointer

·        Using possibly undefined storage or returning storage that is not properly defined

·        Type mismatches, with greater precision and flexibility than provided by C compilers

·        Violations of information hiding

·        Memory management errors including uses of dangling references and memory leaks

·        Dangerous aliasing

·        Modifications and global variable uses that are inconsistent with specified interfaces

·        Problematic control flow such as likely infinite loops, fall through cases or incomplete switches, and suspicious statements

·        Buffer overflow vulnerabilities

·        Dangerous macro implementations or invocations and

·        Violations of customized naming conventions.

[Evans01]

 

Annotations

 

Annotations are semantic comments that are added to program source code and libraries.  They document programmer assumptions and intents.  Users are also able to define new annotations and associated checks to extend Splint’s checking or to enforce application specific properties [Evans01]. They exist as stylized comments that follow a definite syntax.  Although they are comments, they may only be used in fixed grammatical contexts e.g., like a type qualifier.

 

Annotations are denoted using stylized C comments identified by an @ character following the /* comment marker [LE02].  They are associated syntactically with function parameters, function return values, global variables and structure fields.  For example, the annotation /*@notnull*/ can be used syntactically like a type qualifier.  In a parameter declaration, it indicates that the value passed for this parameter may not be NULL [LE01].

 

Annotations limit the values a parameter may contain before or after a function call.  It also constrains the return value of the function.  For example, the annotation /*@notnull*/ may place a constraint on the parameter value before the function body is entered.  When Splint verifies the function body it assumes that the initial parameter value is not NULL.  Similarly for function return values, it checks that the value returned is not NULL.  In a global variable declaration, a not NULL annotation would show that the value of the variable will not be NULL at an interface point, i.e. it might be NULL within the body of a function but would not be NULL at the location from which it was called or the return point.  Failure to handle possible NULL return values may not be noticed in regular testing, but is often exploited by denial of service attacks.

 

Annotations may also record assumptions over an object’s lifetime. For example, the ‘only’ annotation on a pointer reference is used to indicate that the reference is the only long-lived reference to its target storage [LE02].  An ‘only’ annotation implies a compulsion to release storage. This is performed by the system either by passing the object as a parameter annotated with ‘only’ and returning the object as a result annotated with ‘only’, or by assigning the object to an external reference annotated with ‘only’ [LE02].  Both these options transfer the obligation to another reference. Splint would report a warning for any code path that falls short of fulfilling this storage-release obligation, because that would cause a memory leak.

 

In order to do useful checking of buffer overflow vulnerabilities, Splint has extended LCLint to support more expressive annotations that are not limited to classifying references as being in one of a small number of possible states.  This is because, with regards to buffer overflows, a greater concern would be the amount of memory that had been allocated for a buffer, which is something that cannot be adequately modeled using only a fixed number of states.  These expressive annotations allow programmers to openly state function preconditions and postconditions using ‘requires’ and ‘ensures’ clauses.  These clauses may then be used to describe assumptions about buffers that are passed to functions, and also limit the state of buffers when the function returns.

 

Splint’s Implementation

 

Four main kinds of assumptions and constraints are currently being used in Splint: minSet, maxSet, minRead and maxRead.  Constraints may even contain constants and variables, and allow the following arithmetic operations: + and -.  The full constraint grammar is:

constraint Þ (requires | ensures)

constraintExpression relOp constraintExpression

relationalOp Þ == | > | >= | < | <=

constraintExpression Þ

    constraintExpression binaryOp constraintExpresion

  | unaryOp ( constraintExpression )

  | term

binaryOp Þ + | -

unaryOp Þ maxSet | maxRead | minSet | minRead

term Þ variable | C expression | literal | result

[LE01]

 

Annotations inserted in program source code allow arbitrary constraints, as defined in the above constraint grammar, to be specified as the preconditions and postconditions of functions.  Constraints may be conjoined (using /\), but there is no current support for disjunction.  Also every variable used in the constraints has a corresponding location.  Since the value stored by a variable may change in the function body, it is imperative that the constraint resolver may differentiate the value at different points within program execution.

 

Splint’s Use Warnings

 

Splint will produce a warning whenever the source code uses library functions that are susceptible to buffer overflow vulnerabilities. The ‘gets’ function is continually vulnerable, so it reports all uses of ‘gets’. Other library functions, such as ‘strcpy’, may be securely used but are also often the cause of buffer overflow vulnerabilities. Splint provides an annotation warn flag-specifier message, which precedes a declaration.  It indicates that the use of such a declarator would produce a warning. For example, the Splint library declares ‘gets’ with:

/*@warn bufferoverflowhigh

 “Use of gets leads to … “@*/

This specifies that Splint should provide a warning message every time ‘gets’ is used and the ‘bufferoverflowhigh’ flag is set.

 

How Splint Describes Functions

 

Suppose we consider the strcpy function: it takes two char * parameters (q1 and q2) and copies the string that the second parameter (q2) points to into the buffer pointed to by the first parameter (q1). A call to strcpy will overflow the buffer pointed to by the first parameter (q1) if that buffer’s capacity is not large enough to hold the string pointed to by the second parameter (q2).  This property can be enabled by adding a ‘requires’ clause to the declaration of strcpy such as: /*@requires maxSet(q1)>=maxRead(q2) @*/.

This precondition uses two buffer attribute annotations, maxSet and maxRead. When used in a ‘requires’ clause, the minSet and maxSet annotations describe assumptions about the lowest and highest indices of a buffer that may be safely used as an lvalue [LE01], i.e. a value on the left side of an assignment expression.  In the same way, the minRead and maxRead constraints indicate the minimum and maximum indices of a buffer that may be read securely.  The value of maxRead for a given buffer is always less than or equal to the value of maxSet [LE01].  The value of maxSet(buff1) is the highest integer ‘i’ such that buff1[i] can be securely used as an lvalue.    The value of maxRead(buff2) is the highest integer ‘i’ such that buff2[i] can be safely used as an rvalue, i.e. a value on the right side of an assignment expression. Also consider that the q2 parameter has a null-terminated annotation that indicates that it is a null-terminated character string.  This implies that q2[i] must be a NULL character for some i<= maxRead(q2). 

 

At the calling location, Splint produces a warning if a precondition is not satisfied. Thus, a call for strcpy (s, t) would produce a warning if Splint could not determine that MaxSet(s)>=maxRead(t). That warning would indicate that the buffer allocated for s may be overrun by the call to strcpy.

 

How Splint Conducts its Analysis

 

Splint examines a function body from the annotated preconditions and verifies that the function implementation ensures the stated post-conditions. It generates preconditions and postconditions at the expression level in the parse tree using internal rules or, in the case of function calls, annotated descriptions. For example, the declaration char buf[MAXSIZE] generates the postconditions maxSet(buf) = MAXSIZE – 1 and minSet(buf) = 0. [LE02]

 

Where the expression buf[i] is used as an lvalue, Splint produces the precondition maxSet(buf)>= i. All constraint variables associate specific code locations. Because a variable’s value may change, Splint distinguishes between values at different code points.

 

Splint determines preconditions using postconditions from previous statements, and any annotated preconditions for the given function.  If it is not able to resolve a generated precondition at the beginning of a function or satisfy a given postcondition at the end, Splint issues a explanatory warning about the unfulfilled condition. Hence, for the above buf[i] example, Splint will issue a warning if it is unable to resolve the value of i between 0 and MAXSIZE – 1. 

 

Splint propagates constraints across statements using an axiomatic semantics and simplifies constraints using constraint-specific algebraic rules, such as maxSet(ptr + i) = maxSet(ptr) – i [LE02].

 

In order to analyse loops, Splint uses heuristics, which recognize common loop forms.  This is possible because a few heuristics may match many loops in actual programs. This enables effective analysis of loops without any need for loop invariants or costly analyses.

 

Extensible Checking

 

Apart from built-in checks, Splint contains mechanisms to define new checks and annotations.  This enables it to detect new vulnerabilities or security breaches of application specific properties.  A sizeable class of practical checks may be portrayed as constraints on attributes related to program objects or the global execution state. However, unlike types, the values of these attributes may alter along an execution path. 

 

Splint provides a general language that lets users define attributes associated with different kinds of program objects as well as rules that both constrain the values of attributes at interface points and specify how attributes change [LE02]. Due to the limited expressiveness of user attributes, Splint may check user-defined properties effectively.  This enables detecting new vulnerabilities using something called a ‘taintedness’ attribute to detect format bugs.  This attribute may be used to detect potentially dangerous operations with tainted values at compile time. Splint accomplishes this by defining a ‘taintedness’ attribute associated with char* objects and introducing the annotations ‘tainted’ and ‘untainted’ which point out assumptions about the ‘taintedness’ of a reference.

 

Theoretical Design Versus Practical Implementation

 

Some of the important theoretical design goals behind developing Splint are:

·        Efficiency - Since Splint should be run whenever the source code or specification is changed, the time needed to run Splint should be comparable to that for compilation.  This limits the checking to simple checks that do not require global analysis.

·        Flexibility - Splint is not intended to impose a specific style of coding. Hence, its checking must be customizable to support different programming styles.

·        Incremental effort and gain - Splint should provide significant benefits without programmers expending much effort on writing specifications. Benefits should increase as further effort is put into the specifications.

·        Ease of use - Splint should be as easy to run as a compiler, and its output should be easy to understand.

·        Ease of learning - Splint is intended to be an entry into writing formal specifications for programmers who would not otherwise write them, so the knowledge of formal specifications needed to start realizing the benefits of Splint should be minimal.

[EGHT94]

 

Splint is used in an iterative manner.  It is first run in order to generate warnings and then to either change the code or annotations accordingly.  Subsequently it is run again to verify the changes and publicize the newly documented assumptions. This is continued no further warnings are issued.  Since Splint checks approximately 1,000 lines per second, running Splint repetitively is not cumbersome. However, there are both theoretical and practical limits to what Splint can analyze statically. Since the goal of Splint’s development was to perform as much useful checking as possible, checking that is both unsound and incomplete is allowed. Splint thus constructs both false positives and false negatives. Theoretically the warnings were developed to be as useful as possible to programmers, however they offer no guarantee that all messages indicate real bugs or that all bugs will be found.  Thus Splint appears to run efficiently but some of its warning may prove to be inadequate.

 

With regards to the theoretical flexibility issue, simple ways are provided for programmers to customize verification behaviour locally and repress false warnings that result from imprecise analysis.

 

Annotating programs do require a large degree of effort.  This limits the scope of widely using these techniques in the near future.  This may be partly solved by providing an annotated standard library.  But this does not eliminate the need to add annotations to user functions where accuracy depends on documenting assumptions that cross interface borders.  Also most of the effort involved in annotating legacy programs is usually fairly tedious and mechanical.  However, an informal sampling of tens of thousands of emails received from LCLint users indicates that about one quarter of LCLint users add the annotations supported by previously released versions of LCLint to their programs.  Perhaps half of those use annotations in sophisticated ways (and occasionally in ways the authors never imagined) [LE01].  Even though the annotations required for effectively detecting buffer overflow vulnerabilities are to some extent more complex, they are only one incremental step beyond previous annotations.  In most cases, especially for security-sensitive programs, the benefits of providing such security greatly outweighs the effort required.  Thus the theoretical issue of incremental effort and gain does stand as a tradeoff.  It would depend on the level of security that certain security-sensitive applications require.

 

The process of adding annotations is a constructive and useful step for understanding of a program and improving its maintainability [LE01].  Also its output is easy to read and expressive enough to understand.  Thus Splint does have a good degree of ease of use.

 

Splint’s annotations are both expressive and have a sense of standardisation.  They do not require any formal programming training.  Also we could realistically (and optimistically) assume that programmers would be willing to add annotations to their programs if they understand the importance of preventing security breaches such as buffer overflows.  Thus the theoretical issue regarding ease of learning seems to be well met.

 

Apart from the above some further observations have been recorded regarding Splint:

 

Conclusion

 

Lightweight static analysis tools, such as Splint, seem to be a promising technique for detecting likely software vulnerabilities.  They assist programmers to fix vulnerabilities before software is deployed rather than patch them after these problems have been utilized by attackers.  Even though no single tool will eliminate all security risks, lightweight static analysis tools should be an integral part of the software development method for security-sensitive applications.

 

4.      StackGuard

 

Overview

 

StackGuard is a simple compiler technique that produces programs secured against stack-smashing attacks while virtually eliminating buffer overflow vulnerabilities with only modest performance penalties.  However, this protection is only provided for programs and libraries that are re-compiled with StackGuard [CBFDPWW99]. These programs no longer surrender control to the attacker, but instead they enter a fail-safe state. Since it is a compiler-based software engineering security tool, this protection does not require any source code modifications and are binary-compatible with existing operating systems and libraries.  When a vulnerable program is attacked, StackGuard detects the attack in progress, raises an intrusion alert, and halts the victim program [SG98].

 

Stack smashing attacks exploit a lack of bounds checking on the size of input being stored in a buffer array.  By writing data past the end of an allocated array, the attacker can make arbitrary changes to program state stored adjacent to the array. 

 

The continued success of buffer overflow attacks is largely due to the “patchy” nature by which solutions are provided against them.  Usually a malicious user discovers the vulnerability in a program and then someone else implements a patch to that particular attack, for that program. Fixes to buffer overflow attacks attempt to solve the problem at the source (the vulnerable program) instead of at the destination (the stack that is being overflowed) [CPMHBBGWZ98].  StackGuard strives to defend that which the attacker wishes to alter. Programs compiled with StackGuard are safe from buffer overflow attack, regardless of the software engineering quality of the program. 

 

Implementation

 

StackGuard is a compiler extension that enhances the executable code produced by the compiler so that it detects and thwarts buffer-overflow attacks against the stack [CPMHBBGWZ98]. This creates a degree of transparency to the normal functioning of programs. The only way to observe that a program is StackGuard-enhanced is to make it execute C statements with undefined performance – such enhanced programs describe the behaviour of writing to the return address of a function while it is still active.

 

StackGuard averts modifications to active return addresses by either perceiving the change of the return address before the function returns, or by completely disallowing a write to the return address. Thus StackGuard supports both techniques: detecting changes to the return address which is more efficient and portable, and actually preventing the change which is more secure.  StackGuard is also able to adaptively switch from one mode to the other.

 

Detecting a Return Address Change before Returning

 

In order to be effective, detection of an altered return address must occur before a function returns.  StackGuard performs this by inserting a “canary” word next to the return address on the stack, as shown in Figure SG1.  

Figure SG1.  Canary Word Next to Return Address [CPMHBBGWZ98]

 

When the function returns, it initially verifies that the “canary” word is unaltered before jumping to the address pointed to by the return address word.  This technique presumes that the return address is unaltered if and only if the “canary” word is intact. Even though this assumption is not always true generally, as stray pointers may modify any word, it is true for buffer overflow attacks.  The buffer overflow attack method takes advantage of the return address word being located very close to a byte array with weak bounds checking.  Thus the only tool the attacker has is a linear, sequential write of bytes to memory, usually in ascending order [CPMHBBGWZ98]. Therefore under these rigid circumstances, it would require a very complex task to over-write the return address word without disturbing the “canary” word.  If the canary word has been altered when the function returns, then a stack smashing attack has been attempted, and the program responds by emitting an intruder alert into syslog, and then halts [SG98].

 

[Frykholm00]

 

The StackGuard implement this by a simple patch to gcc. The gcc function_prologue() and function_epilogue() methods have been modified to emit code to place and verify “canary” words. function_prolog() lays down canaries on the stack when functions start, and function_epilog() checks the integrity of the canary word when the function exits.  Thus an attempt to corrupt the return address would be detected before the function returns.

 

This form of canary defence is usually sufficient to prevent most buffer overflow attacks that are unaware of the canary.  However it is possible to create attacks specifically designed to conquer StackGuard. Two ways to do this are:

 

  1. By skipping over the canary word.  If the attacker can locate a poorly checked copy of an array of structs, which have alignment requirements, and are not big enough to fulfill the alignment requirements while densely packing the array, then it is possible that the copy could occur such that the canary word is in one of the holes left in the array [CPMHBBGWZ98]. This form of vulnerability is rare and difficult to utilize.

 

  1. By simulating the canary word. If a malicious user may guess the canary value then the attack string could include the canary word in the right place and the check at the end of the function. Thus if a completely static canary word is used it would be easy to deduce.  This form of attack is typically problematic.

 

In order to handle the case of easily guessable canary words, randomly chosen canary values are used.  When the program starts a set of random canary words are selected. Then these random words are used as distinct random canary words, one for each function within the object code. Even though it is not impossible to still guess such a canary value, it would be very difficult.  This is because the attacker must be able to examine the memory image of the running process to get the randomly selected word [CPMHBBGWZ98].

 

Preventing Return Address Changes with MemGuard

 

MemGuard is a tool developed to locate code statements, which change quasi-invariant[3] values.  Individual words of memory, i.e. quasi-invariant terms, may be designated as read-only, except when explicitly written via the MemGuard API.  For e.g., the function’s return address could be read-only while the function is active thus preventing buffer overflow attacks against the stack.  Thus MemGuard is used to avert buffer overflow attacks by shielding a return address when a function is called, and then ‘un-protecting’ the return address when the function returns. This protection and un-protection occur in exactly the same locations as the canary placement and checks the function_prologue() and function_epilogue() methods.  Figure SG2 [CPMHBBGWZ98] shows the prologue code sequence forMemGuard.

 

push a

push b

move 164 into a

move arg[0] into b

trap 0x80

pop b

pop a

Figure SG2: Function Prologue Code: Protecting the Return AddressWith MemGuard [CPMHBBGWZ98]

 

The sequence of the function_epilogue() code would be identical to Figure SG2, but uses system call 165 instead of 164.

 

MemGuard is applied by firstly marking virtual memory pages containing quasi-invariant terms as read-only.  Then a trap handler is also installed that catches writes to protected pages, and copies writes to non-protected words on protected pages. This cost of a write to a non-protected word on a protected page is approximately 1800 times the cost of an ordinary write [CPMHBBGWZ98].  This cost would be acceptable when quasi-invariant terms are in ‘quiet’ portions of the kernel’s address space, and when MemGuard is principally used for debugging purposes. 

 

However this cost would not be tolerable when the protected words are located near the top of the stack, that is, next to several of the most repeatedly written words within the program. Previously MemGuard had been originally designed to protect variables within the kernel only. Consequently, to protect the stack, MemGuard was extended in the following ways:

 

An Adaptive Defence Strategy

 

One of StackGuard’s focuses is to provide adaptive responses to security threats.  Thus an adaptive response to intrusions was developed to allow switching between the better performing Canary version, and the more robust MemGuard techniques.  When a buffer overflow is identified, either by the Canary or by MemGuard technique, the process is terminated. The process must exit.  This is because an indefinite amount of state had already been corrupted at the time the attack was detected.  Consequently it is impossible to safely recover the state of the process. Thus the process exits, using only static data and code, so as to avoid any potential corruption from the aggressor. Then replacing the dead process is context-dependent.  It is also possible for these mechanisms to adaptively choose which type of protection to next use.

 

The Canary and MemGuard techniques offer different perspectives in the trade-off between security and performance. The Canary version is more offers a better performance, while the MemGuard version offers a higher degree of security. More precisely, the important security breach in the Canary technique is that it may be subject to guessing of the canary value. This technique may defend itself against such guesses by exiting, and replacing the attacked Canary-guarded daemon with aMemGuardguarded daemon. Such adaptive responses allow systems to usually run in a moderately high-performance state, and adaptively switch to a lower-performance but higher-security state when under attack. In the worst case, the intruder may carry out a degradation-of-service attack by regularly attacking daemons and forcing them to run in the lower performance MemGuard mode most of the time. However, in this case service is not completely denied, because the daemons still continue to operate, and the attacker is no longer able to obtain illicit privileges via buffer overflow attacks.

 

Theoretical Design Versus Practical Implementation

 

StackGuard does not get rid of the need to fix buffer overflow vulnerabilities.  However by converting root vulnerabilities into mild degradation-of-service attacks, it eliminates the rush to fix them. This provides software developers with enough time to fix buffer over-flows conveniently rather than having to hurry. Apart from this StackGuard relieves security administration by alleviating system administrators of the need to apply these patches as soon as they are released.

 

StackGuard may alert the user to potentially dangerous code, but it does not provide any assistance in determining whether a particular use of a possibly dangerous function is safe or dangerous, unlike source-code based software engineering security tools.

 

StackGuard has a performance price making it possible to be perceived as an ‘insurance policy’. Thus if one is very certain that a particular program is correct, i.e. does not contain possible buffer overflow vulnerabilities because it has been verified using formal methods, or a validation tool, then the  program may be re-compiled and installed without using StackGuard.

 

Conclusion

 

StackGuard is an effectively transparent replacement for gcc that offers protection from the pervasive problem of stack smashing vulnerabilities [CBFDPWW99]. Essentially, StackGuard prevents against attacks that are security faults, which arise due to trivial programming errors.  Nonetheless StackGuard not only patches a broad set of existing faults, but also patches a broad collection of future faults that have yet to be exposed.  In its most fundamental form, the tool requires only recompilation to make a program secure against possible buffer overflow attacks. In its more elaborate forms, it also does provide adaptive responses to buffer overflow attacks, allowing systems to trade performance for survivability. [Please see Appendix A that describes a significant security vulnerability that allows attackers to commit successful attacks against StackGuard programs under specific circumstances.]

 

5.      TAXYS: A Tool for the Development and Verification of Real-Time Embedded Systems

 

Overview

 

The right performances of real-time applications do not simply depend on the accuracy of the results of the calculations, but also on the instance when these results were formed. In fact, violations of real-time constraints in embedded systems are of the most complex errors to identify because they are exceptionally receptive to both the configurations of external actions stimulating the system, and also to the timing behaviour of the actual system itself. Undoubtedly, the development of real-time systems requires precise methods and tools to reduce development costs and ‘time-to-market’ while assuring superiority of the produced code.

 

The development of the Taxys tool was motivated by the above requirements.  Taxys is dedicated to the design and validation of real-time telecommunications software.  One of the major goals of the Taxys tool is to create a proper model that captures the sequential behaviour of the entire application, which comprises of the embedded computer and its external environment.  For this purpose the formal model of timed automata was used [AD94].  The choice of this model allows the use of results, algorithms and tools that are available. At this time, the KRONOS model checker [DOTY96] is being used for model analysis.

 

From the source code of the application, i.e. an Esterel[4] program annotated with temporal constraints, the Taxys tool creates a sequential executable code and a timed model of the application. This model is again created with a timed model of the external environment so that a global model may be obtained, which is statically analyzed to validate the timing restrictions. Thus, the application is decomposed into a control part, written in Esterel and a functional part written in C, and it is compiled with the Esterel compiler Saxo-rt [WBCPVP00].

Implementation

 

The use of synchronous languages for the development of real-time reactive applications relies on a ‘synchrony assumption’ meaning that the application reacts infinitely fast with respect to its environment [CPPSVWY01]. This assumption, which is suitable in practice, is required to be validated for a given implementation on a target machine. In practice, validating the synchrony assumption shows that the environment does not take much lead over the application. This needs the use of a so-called ‘realistic’ synchrony assumption absolutely depending on the application, that is on the speed of the machine and on its exchanges with the environment. To amalgamate the real-time system with its environment, an external event-handler H is used, which is generated by Saxo-rt from an ad-hoc requirement [BPPS00].  It accurately takes into consideration how the external events are being captured by the interrupt mechanisms and sent to the application.

 

The behaviour of such systems may be represented by the composition of three systems represented as: the application automaton A, the external event handler H which abstracts the behaviour of the interrupt routine and buffers external events prior to being taken into account by the next synchronous reaction, and the environment model E which states the situations in which the application must run [BPPS00].  The environment of a real-time embedded system may display unrelated behaviours that must be captured by some non-deterministic model. As Esterel programs are deterministic, a non-deterministic instruction npause was added to the Esterel language. The environment may therefore be written in the same language as that of the application (the timing constraints are described directly by pragmas in the Esterel code of A and E).

 

Taxys’ design flow is shown in Fig. T1. Saxo-rt produces three C-modules, which calculate A, H and E transition functions: the model of the application contains the embedded code itself. Kronos [DOTY96] investigates the system state’s space by composing A, H and E on the fly. Thus, no intermediate state explosion may arise previous to the composition and only reachable states may be calculated. If any timing constraint is dishonoured, a trace leading to this error is then produced. This trace is then re-executed step by step on the Saxo-rt graphical debugger to provide to the user more accurate diagnostics.

 

Figure T1: Taxys Design Flow [CPPSVWY01].

 

Timing Analysis

 

The C code is structured as a reactive machine whose transitions are triggered by signals provided by an external environment. A transition occurrence changes atomically control state and data state by executing an associated C function. [SIFAKIS01]

 

It is significant to observe that while, according to Esterel semantics, the communication between an Esterel program and its environment is immediate, the composition among the timed application software and the timed environment requires the use of memory. Undeniably, immediate actions of the un-timed model take time when executed and during this time environment changes should be recorded. Global timed models of the real-time system are analyzed using the Kronos timing analysis tool.

 

Experimental Results

 

Taxys was used for validating Esterel code for the communication mode of a GSM terminal developed by Alcatel (815 Esterel lines and 48000 C lines) [BPP01]. Four scenarios were discovered that lead to deadline violations caused by erroneous scheduling between two C functions.   The results were obtained on a digital phone prototype carrying simultaneous voice and data produced by a graphic tablet, implemented on a 32 MIPS Digital Signal Processor. Graphic tablet data were compressed by a vectorization algorithm, which used between 15000 and 20000 CPU cycles. There were six experiments carried out with the same Esterel code for the application but with different environment models and handler buffer sizes. For all of the cases, the application A consisted of 3000 C lines and 258 Esterel lines, and the environment E - of 120 Esterel lines.  The results obtained have are shown in Table T2.  From this table it may be seen that a buffer size of at least six was required for absorbing the irregular task (ISDN2). It also shows that the number of symbolic states examined by Kronos would increase exponentially with the ‘degree’ of non-determinism of the environment. Consequently, to manage the state explosion due to environment non-determinism, it was essential to find suitable environment model approximations conserving the confirmed properties.

 

Table T2: Taxys Experimental Results

 

Theoretical Design Versus Practical Implementation

 

Taxys is part of a more general project that aims towards automatic low level code generation from high level specifications of an embedded real-time application.  However below are the following areas that contain certain practical limitations: -

 

Conclusion

 

Taxys presents a unique method for specifying, designing and validating real-time embedded systems. This method is implemented in a completely automated tool, which is relevant to industrial size examples. Specifications are written in a user friendly and compositional formalism, which does not need the user to have any previous experience with timed automata or temporal logic. Any progress in these techniques may be considered transparently for the user. Moreover, since the embedded code is successfully executed during validation, the validation appears to be reliable and is consequently mainly suitable for safety critical applications.

 

Conclusion

 

In order to prevent buffer overflows there are several possible levels where a defence mechanism may be inserted. At the language level, modifications can be made to the C language itself to reduce the risk of buffer overflows. At the source code level, static or dynamic source code analyzers may be used to verify code against buffer overflow vulnerabilities. At the compiler level, alterations to the compiler may be undertaken so that the operating system itself performs bounds checking or protects certain addresses from being overwritten. .  In real-time, formal models may be developed that capture the temporal behaviour of the entire application, which is made of the embedded computer and its external environment. At the operating system level change may be made to the rules that ascertain which memory pages should be allowed to hold executable content.  These approaches all reduce the risk of security vulnerabilities while requiring only minimal extra work from application developers.  Our analysis mainly consisted of tools that checked against buffer overflow vulnerabilities related to the C programming language.  Thus they covered all the above levels except for Operating System tools.  This was also because there are not many successful Operating System tools currently available.  Below is a brief summary of the various levels and their corresponding tools that we have analysed:

 

 

At this level the simplest solution would be to switch to a language that provides automatic bounds checking of buffers, such as Java, Perl or Python. Nevertheless, in most realistic tasks this is not usually an option.

 

The Libsafe library replaces the implementation of the dangerous functions in the shared libc library with safe versions.  Thus in order to make every buffer access safe, only those specific functions in C which are known to be dangerous (e. g. strcpy, strcat, gets and sprintf) are targeted. However this does not handle buffer overflows caused by other code, such as user-defined functions.

 

 

Such tools analyze the source code of a program and attempt to determine whether the application contains any vulnerabilities that may lead to buffer overflows.  However, source code tools that are currently available perform only a local analysis of the source code, and are consequently restricted in the types of buffer overflow problems that they can detect. 

 

ITS4 is such a source code tool that verifies usage of unsafe functions. Some of its features include the ability to rule out certain cases where the use of an insecure function should not pose a problem.

 

Splint is another such tool that utilizes annotations that have been added to libraries and programs.  These annotations describe assumptions and intents.  Splint is able to find potential problems by performing checks to test whether the source code is coherent with the properties implied by annotations.

 

 

Compiler level tools modify how a program is compiled.  Thus protection against buffer overflows is automatically compiled with the program. It is not necessary to make any further modifications to the program's source code.

 

StackGuard is a compiler level tool that can only protect against stack attacks.  It is not capable of detecting and preventing variable attacks, but there is work being undertaken to append canary values to function pointers too, since they are also vulnerable targets.

 

A significant disadvantage of such runtime level checking is that performance overhead is increased. If the program contains many small function calls the total overhead could be large.  Consequently if the program does not contain as many function calls, the overhead will be less.

 

 

Real-time computing is such where the correctness of the system depends not only on the logical result of the computation but also on the time at which the results are produced [Stallings92]. Tools that perform such validation notably shorten design time by limiting tedious test and simulation sessions.  Furthermore, because the embedded code is effectively executed during validation, the validation is trustworthy and is therefore particularly suited to safety critical applications [CPPSVWY01].  However such tools (e.g. TAXYS) posses those limitations associated with model-checking techniques.

 

 

There has been research into solving the buffer overflow problem at the operating system level itself.   Thus the operating system would impose program independent restrictions, making buffer overflow attacks harder to perform.  However there has not been any notable success with regards to preventing buffer overflow breaches at this level.  Solar Designer has created a patch for Linux that makes the stack non-executable [SD]. This implies that an attacker may no longer be able to inject code into the stack and execute it. However, it does not prevent attackers from calling random functions in the program with arbitrary arguments.

 

It seems unlikely that the C and C++ languages will become inherently more secure soon. To make up for this inadequacy it would be beneficial to make programming environments ease the burden of writing secure software for the end programmer.  Hence, the ideal tool would be one that detects and prevents buffer overflows from the Language level and from the Operating System level.  This would enable preventing such attacks even if the language did provide any such measures, and would remove the responsibility of creating secure code from the programmers.  Every flaw the software security tool finds can potentially spare the programmer an additional check when building and testing a program. 

 

Newly exposed security vulnerabilities should not be prevented by just a patch for a specific program’s problem, but should also include checking protocols that detect similar problems in other programs and ensure that the same mistake is not made in future programs.  From our analysis we suggest that the security community should design and implement a tool suite that assembles knowledge about security vulnerabilities in a manner that makes it accessible to all programmers. 

 

Through our analysis we were surprised to discover the extent of the problem of software security vulnerabilities.  The further we researched, the more issues seemed to slowly surface.  We discovered that the problem of buffer overflows is extremely prevalent in the current world of software security.  Not having any past experience creating secure software we were pleased to learn the vital importance of safeguarding our programs from potential vulnerabilities.  Being programmers ourselves we understood the importance of removing this burden from the programmers and having tools that would automate detecting and eliminating security defects.  Currently there are several tools available, each having their own significant features and limitations.  However these tools seem to be easily available and their precision is iteratively being enhanced.  We were glad to have studied this topic during this course as it has helped us gain considerable insight towards the issues of secure software engineering and their corresponding tools especially with regards to the extensive problem of buffer overflows.

 

References
 

1.      [Thomas]

Evan Thomas. Attack Class: Buffer Overflows. Hello World! April, 1999.

<http://www.cosc.brocku.ca/~cspress/HelloWorld/1999/04-apr/attack_class.html>

 

2.      [ER89]

Mark W. Eichin and Jon A. Rochlis. With microscope and tweezers: An analysis of the Internet virus of November 1988. In Proceedings of the 1989 IEEE Computer Society Symposium on Security and Privacy (SSP '89), 1989.

 

3.      [Frykholm00]

Niklas Frykholm.  Countermeasures against Buffer Overflow Attacks. 30 November, 2000.

 

4.      [WFBA00]

David Wagner, Jeffrey S. Foster, Eric A. Brewer, and Alexander Aiken. A first step towards automated detection of buffer overrun vulnerabilities. In Proceedings 7th Network and Distributed System Security Symposium (to appear), February 2000.

 

5.      [CERT]

CERT Coordination Center. <http://www.cert.org>

 

6.      [EGHT94] 

David Evans, John Guttag, Jim Horning, and Yang Meng Tan.  LCLint: A Tool for Using Specifications to Check Code.  In SIGSOFT Symposium on the Foundations of Software Engineering.  December 1994.

 

7.      [Evans00]

David Evans. Annotation-Assisted Lightweight Static Checking.  Position Paper for The First International Workshop on Automated Program Analysis, Testing and Verification.  University of Virginia, Department of Computer Science. Feb 25, 2000.

 

8.      [Evans01]

David Evans.  Splint Manual. Version 3.0.6.  11 February 2001

 

9.      [LE01]

David Larochelle and David Evans.  Statically Detecting Likely Buffer Overflow Vulnerabilities.  In 2001 USENIX Security Symposium, Washington, D. C., August 13-17, 2001.

 

10.  [LE02]

David Larochelle and David Evans.  Improving Security Using Extensible Lightweight Static Analysis.  In IEEE Software, Jan/Feb 2002.

 

11.  [Avaya01]

Avaya Labs Research: Projects.  Libsafe: Protecting Critical Elements of Stacks. November 9, 2001

<http://www.research.avayalabs.com/project/libsafe/>

 

12.  [BTS99]

Arash Baratloo, Timothy Tsai, and Navjot Singh.  Libsafe: Protecting Critical Elements of Stack.  Bell Labs, Lucent Technologies.  December 25, 1999.

 

13.  [BTS00]

Arash Baratloo, Timothy Tsai, and Navjot Singh. Transparent Run-Time Defense Against Stack Smashing Attacks.  In Proceedings of the USENIX Annual Technical Conference. June 2000.

 

14.  [BTS01]

Arash Baratloo, Timothy Tsai, and Navjot Singh. LIBSAFE. Section: LIBSAFE (8). Updated: 9-JAN-2001.

<http://www.research.avayalabs.com/project/libsafe/doc/libsafe.8.html>

 

15.  [Baratloo00]

The Arash Baratloo interview - June 7th, 2000.  Open Source Development Network.

 

16.  [Wheeler02]

David A. Wheeler. Secure Programming for Linux and Unix HOWTO.  Prev Chapter 5. Avoid Buffer Overflow. v2.962. 12 March 2002.

< http://www.linuxdoc.org/HOWTO/Secure-Programs-HOWTO/library-c.html>

 

17.  [CPMHBBGWZ98]

Crispin Cowan, Calton Pu, David Maier, Heather Hinton, Peat Bakke, Steve Beattie, Aaron Grier, Perry Wagle, and Qian Zhang.

Automatic Detection and Prevention of Buffer-Overflow Attacks, in the 7th USENIX Security Symposium, San Antonio, TX. January 1998.

 

18.  [CBFDPWW99]

Crispin Cowan, Steve Beattie, Ryan Finnin Day, Calton Pu, Perry Wagle, and Erik Walthinsen.  Protecting Systems from Stack Smashing Attacks with StackGuard, in the Linux Expo. Raleigh, NC. May 1999. 

 

19.  [SG98]

Immunix – Adaptive System Viability.  Stackguard.

<http://www.immunix.org/stackguard.html>

 

20.  [Woloszyn98]

Mariusz Woloszyn. StackGuard Mechanism: Emsi's Vulnerability.

<http://www.immunix.org/stackguard/emsi_vuln.html>

 

21.  [VBKM01]

John Viega, J.T. Bloch, Yoshi Kohno, Gary McGraw.  ITS4: A Static Vulnerability Scanner for C and C++ Code. Pages 1-11.  Reliable Software Technologies.

 

22.  [VBKM00]

John Viega, J.T. Bloch, Tadayoshi Kohno, Gary McGraw.  ITS4: A Static Vulnerability Scanner for C and C++ Code.  Pages 1-15. <http://www.rstcorp.com>

 

23.  [BST01]

Beyond-Security's SecuriTeam.com.  Beyond Security Ltd. 2001

<http://www.securiteam.com/tools/5WP0A000JA.html>

 

24.  [LR92]

W. Landi and B. Ryder. A Safe Approximation Algorithm For Interprocedural Pointer Aliasing. In Proceedings of Programming Language Design and Implementation.  1992.

 

25.  [BPP01]

Valérie BERTIN, Michel POIZE, Jacques PULOU. Towards Validated Real-Time Software. 2001.

<http://www-verimag.imag.fr/~sifakis/RECH/euromicro00.htm>

 

26.  [CPPSVWY01]

Etienne CLOSSE, Michel POIZE, Jacques PULOU, Joseph SIFAKIS, Patrick VENIER, Daniel Weil, and Sergio YOVINE. TAXYS: a Tool for the Development and Verification of Real-Time Embedded Systems. 2001.

<http://www.dess-itea.org/publications/CAV2001-France_Telecom.pdf>

 

27.  [SIFAKIS01]

Joseph Sifakis.  Modeling Real-time Systems --Challenges and Work Directions. October 8, 2001.

<http://www-cad.eecs.berkeley.edu/~fresco/embedded-software/talks/sifakis/sifakis.pdf>

 

28.  [AD94]

R. Alur, D. Dill, A theory of timed automata, Theoretical Computer Science. 126:183–235, 1994.

 

29.  [DOTY96]

C. Daws, A. Olivero, S. Tripakis and S.Yovine. The tool Kronos. In Hybrid Systems

III, Verification and Control, Lecture Notes in Computer Science 1066, Springer-

Verlag, 1996.

 

30.  [BG92]

G. Berry, G. Gonthier, The Esterel Synchronous Programming Language : Design,

Semantics, Implementation, Science of Computer Programming, vol. 19-2, pp. 87-

152, 1992.

 

31.  [WBCPVP00]

D. Weil, V. Bertin, E. Closse, M. Poize, P. Venier, J. Pulou, Efficient Compilation

of Esterel for Real-Time Embedded Systems, Proceeding of CASES’2000, pp. 2-8,

San Jose, November 2000.

 

32.  [BPPS00]

V. Bertin, M. Poize, J. Pulou, J. Sifakis, Towards Validated Real-Time Software,

12th Euromicro Conference on Real-Time Systems, Stockholm, Sweden, June 2000

 

33.  [SD]

Solar Designer. Linux kernel patch from the Openwall project.

<http://www.openwall.com/linux/>

 

34.  [Stallings92]

William Stallings. ISDN and Broadband ISDN. New York: Macmillan Publishing Company. 1992.

 

35.  [Farrow99]

Rik Farrow. Blocking Buffer Overflow Attacks.  An easily avoided attack takes advantage

of programming errors.  1999. <http://www.networkmagazine.com/article/NMG20000511S0015>

 

36.  [Graham01]

Paul Graham.  Hijacking Is Buffer Overflow. September 2001.  <http://www.paulgraham.com/hijack.html>

 

37.  [One]

Aleph One.  Smashing The Stack For Fun And Profit.  Volume Seven, Issue Forty-Nine.  File 14 of 16.

<http://destroy.net/machines/security/P49-14-Aleph-One>

 

38.  [Frykholm00]

Niklas Frykholm.  Countermeasures against Buffer Overflow Attacks. 30 November, 2000. <http://www.rsasecurity.com/rsalabs/technotes/buffer/buffer_overflow.html>

 

39.  [FX01]

Christof Fetzer, Zhen Xiao.  Detecting Heap Smashing Attacks Through Fault Containment Wrappers.  2001. <http://www.research.att.com/~christof/papers/srds2001-preprint.pdf>

 


Appendix A
 

StackGuard Mechanism: Emsi's Vulnerability

[Woloszyn98]

 

A significant security vulnerability was discovered which permits attackers to commit successful attacks against StackGuard programs under specific circumstances.  StackGuard 1.21 has protection against this vulnerability. 

 

The Problem - Consider this vulnerable code:

 

foo(char * arg) {

    char *    p = arg;    // a vulnerable pointer

    char a[25];    // the buffer that makes the pointer vulnerable

 

    gets(a);    // using gets() makes you vulnerable

    gets(p);    // this is the good part

}

 

In attacking this code, the attacker first overflows the buffer a[] with a goal of changing the value of the char * p pointer.  Specifically, the attacker can cause the p pointer to point anywhere in memory, but especially at a return address record in an activation record.  When the program then takes input and stores it where p points, the input data is stored where the attacker said to store it.

 

The above attack is effective against the Random and Terminator Canary mechanisms because those methods assume that the attack is linear, i.e. that an attacker seeking to corrupt the return address must necessarily use a string operation that overflows an automatic buffer on the stack, moving up memory through the canary word, and only then reach the return address entry.  The above attack form, however, allows the attacker to synthesize a pointer to arbitrary space, including pointing directly at the return address, bypassing canary protection.

 

The Solution:  The XOR Random Canary

 

StackGuard 1.21 introduces a new canary defense mechanism: the XOR Random canary.  Like the random canary mechanism, we choose a vector of 128 random canary words at exec() time, but we also XOR the canary with the return address word, so that the return address is bound to the random canary value.  The exact procedure is as follows:

 

·        Setting up an activation record: when calling a function

§         push the return address

§         look up the random canary word for the current function

§         XOR the random canary word with the return address

§         store the result immediately below the return address in the activation record.

 

·        Tearing down an activation record: when returning from a function

§         fetch the canary word from memory

§         XOR the memory canary word with the return address on the stack

§         compare the result with the random canary word associated with the current function

 

The result of this method is that we have the same protection as with the classic Random canary, and also the property that the attacker cannot modify the return address without invalidating the canary word.

 


[1] All experiments were conducted on a 400 MHz Pentium II machine with 128 MB of memory running RedHat Linux version 6.0. Libsafe and all programs in Sections 6.1 and 6.2 were compiled (and optimized using -O2) with GCC compiler version 2.91.66 [BTS99].

 

[2] LCLint was the predecessor of Splint.  It was used as an efficient and flexible tool that accepts input programs written in ANSI C, and various levels of formal specification [EGHT94].

[3] “Quasi-invariants” are state properties that could true for some time, but may change without any notice.  

[4] Esterel programs run in a single thread on a single processor with a non-preemptive interrupt routine and can refer to external data and routines written in C for complex (numerical) computations and provides powerful constructs for management of parallelism and exceptions and has rigorously defined semantics [BG92].