A Static Buffer Overrun Detector for C

Motivation

Robert Morris, a former Cornell graduate student, wrote and released the original Internet worm in 1988. One method of transmission for his worm was a buffer overrun in fingerd. More recent worms spread by buffer overruns include blaster, nimda, slammer, and code red. Buffer overrun exploits typically enable an attacker to execute arbitrary code (i.e., do anything they want if it's a root process). Overruns continue to show up in both open and closed source software.

Objective

To create a static buffer overrun detection system for C source code with three goals:

1. Safety. Be conservative within reason. We want a low false negative rate where a false negative is defined as a real buffer overrun that we did not flag as a possible buffer overrun. The buffer overrun detector is already safe.
2. Low False Positive Rate. We want to reduce the time spent by developers checking their code. A false positive is defined as something that we flag as a possible buffer overrun which was actually safe. False positives are our biggest problem at present.
3. Automation. The user does not need to annotate their code in order to achieve useful results. The tool should also assist the user in determining whether a warning is a genuine buffer overrun or a false positive.

Static vs Dynamic Methods

Static methods analyze the source code without running it wheras dynamic methods watch the code as it runs or insert additional instructions into the code. Each strategy has its drawbacks and advantages.

Statically detecting where buffer overruns can occur in C code without any possibility of false positives or false negatives is computationally intractable. Therefore, most static methods attempt to make a safe and/or useful approximation. A safe approximation produces very few (ideally 0, but that is difficult with some languages) false negatives. False positives are common with static methods that are safe. More precise static methods are usually more computationally expensive.

More popular static methods include tools like (s)lint and even grep. These tools can catch some problems with only a lexical analysis--for instance, calls to gets. However, lint and grep are far from safe. There are many more sophisticated algorithms out there, but they are beyond the scope of this document.

Dynamic methods use extra checks at run-time to either prevent overruns from occurring or to detect them after the fact. Usually, the offending program is terminated (and the incident may be logged) for lack of anything better to do. Sometimes, an exception may be thrown. The primary weakness of dynamic methods is their inability to check all possible executions of the program for problems. Dynamic methods only detect problems in the current execution. Java and StackGuard both qualify as dynamic methods for detecting buffer overruns (only StackGuard will help with C code, of course). Languages like Java are safe (in theory), but tools like StackGuard are not foolproof.

The Tool

The tool is a result of a series of incremental improvements over David Wagner's approach to detecting buffer overruns [3]. The two largest differences are:

1. We make use of pointer analysis results.
2. We are (partially) flow sensitive.

Architecture

1. Build the project using CodeSurfer [5]. CodeSurfer provides an intermediate representation including flow and context insensitive pointer analysis results and an interprocedural mod analysis.
2. Create a linear program (LP) by generating constraints from the intermediate representation of the entire program. Variables in the LP describe the following at various program points:
   • How many bytes are read/written/allocated in arrays and heap variables
   • The location of a terminating null character in a character array or heap variable
   • Values of integral type variables
   • Offsets in bytes from the beginning of arrays or heap variables to which pointers point. That is, if the pointer p points to A[10] where A is an array of chars, then p has an offset of 10.
3. Use an LP solver to solve for the tightest solution to the LP. The LP is constructed using the language accepted by David Wagner's LP solver [3]. We use a modified version of this solver to find the solution.
4. Examine the results from the solver and classify reads and/or writes as dangerous where it may be possible to read or write past the end of an array or heap variable.
5. Present the results in a GUI prioritized and grouped using various heuristics. Double clicking on a warning navigates to the offending source code. From there, the user can use CodeSurfer [5] to help them understand whether the code can infact generate a buffer overrun. Suggestions for improving the functionality of the interface are welcome.

Sources of Precision and Imprecision

Pointer Analysis

A pointer analysis determines where pointers may point. It is an asymmetric binary relation between variables. At present, the tool is using a flow-insensitive and context-insensitive pointer analysis. This means that the pointer analysis treats all possible orderings of statements equally and essentially does not distinguish between different invocations of the same procedure (this is an oversimplification). Why not use something better? We're thinking about it--but it can be computationally expensive.

• Pointer analysis is required for safety. In order to eliminate false negatives, we must know the sets of variables that pointers may point to.

  /* This program produces a false negative without pointer analysis */
  main()
  {
     int i = 0, *p;
     int A[10];
     p = &i;
     *p = 20;
     A[ i ] = 42; /* buffer overrun */
  }
  

• Pointer analysis results can be imprecise. This leads to false positives.

  /* This program produces a false positive with a flow-insensitive
     pointer analysis */
  main()
  {
     int i = 0, j = 20, *p;
     int A[10];
     p = &j;
     p = &i;
     A[ *p ] = 42; /* not an overrun, but the tool would flag it */
  }
  
  /* This program produces a false positive with a context-insensitive
     pointer analysis */
  int *id( int *a )
  {
     return a;
  }
  
  main()
  {
     int i = 0, j = 20, *p, *q;
     int A[10];
     q = id(&j);
     p = id(&i); /* the PA thinks this may return &j or &i */
     A[ *p ] = 42; /* not an overrun, but the tool would flag it */
  }
          

• A context or flow sensitive pointer analysis could certainly eliminate the false positives above. However, there are many different degrees of flow sensitivity and context sensitivity. Some of these are prohibitively expensive--we require a balance between precision and efficiency.

Flow Sensitivity in the Buffer Overrun Analysis

• The buffer overrun detector is partially flow-sensitive. It pays attention to the ordering of statements, and restricts some variables that appear in conditionals accordingly. For example, it detects that the following program is safe:

  /* Nothing is flagged in this program (there is a true negative) */
  main()
  {
     int i;
     int A[10];
     i = 15;
     for( i = 0; i < 10; i++ )
        A[i] = 42;
  }
          

• There are many variables that are not appropriately restricted and this leads to false positives. The solver's constraint language is not expressive enough to encode some conditionals. Also, we do not restrict variables with correlations to other variables appearing in conditionals (consider multiple induction variables in a loop). For example, the following produces a false positive:

  main()
  {
     int i,j;
     int A[10];
     for( i = 0, j = 0; i < 10; i++, j++ )
       A[j] = 42; /* the tool thinks the value of j is unbounded */
  }
          

Context Sensitivity in the Buffer Overrun Analysis

• We get some context sensitivity from inlining constraints for calls to many functions in libc. For instance, every call to strcpy is treated independently as should be the case. Inlining more functions could be an effective method for reducing false positives.
• Most of the constraints we generate are context insensitive. The following example shows a false positive due to this:

  int id(int a)
  {
     return a;
  }
  
  main()
  {
     int A[10];
     id(13);
     A[id(7)] = 42; /* false positive here because the tool thinks id(7)
                       might return 13 */
  }
          

• Other than inlining, we don't have any concrete ideas about how to make the buffer overrun detector context-sensitive and reasonably efficient with an incremental change.

Some other sources of imprecision include dead code, infeasible paths, and non-linear integer computations.

Results

The tool (in various stages of development) has been used to detect about 20 low-risk buffer overruns in wu-ftpd. We have also confirmed that the tool finds known buffer overruns in applications including: sendmail, talkd, CLIPS, and strace.

Note: As far as we know, there are no false negatives in any of the benchmarks. However, it is possible to engineer a false negative in the C language. So there may be false negatives we do not know about.

References

• [1] Buffer Overrun Detection using Linear Programming and Static Analysis, by Vinod Ganapathy, Somesh Jha, David Chandler, David Melski and David Vitek. [ PS | PDF ]
  Note: The tool has changed significantly since this paper was written.
• [2] Slides written by Vinod Ganapathy about related work
• [3] Static analysis and computer security: New techniques for software assurance, David Wagner. Ph.D. dissertation, Dec. 2000, University of California at Berkeley.
• [4] This tool as a product (it has been coined the "ASA Security Analyzer")
• [5] CodeSurfer

Parties Presently Involved