A First Step Towards Automated Detection of Buffer Overrun Vulnerabilities∗David Wagner Jeffrey S. Foster Eric A. Brewer Alexander AikenUniversity of California, BerkeleyAbstractWe describe a new technique for finding potential bufferoverrun vulnerabilities in security-critical C code. The keyto success is to use static analysis: we formulate detec-tion of buffer overruns as an integer range analysis prob-lem. One major advantage of static analysis is that secu-rity bugs can be eliminated before code is deployed. Wehave implemented our design and used our prototype to findnew remotely-exploitable vulnerabilities in a large, widelydeployed software package. An earlier hand audit missedthese bugs.1. IntroductionBuffer overrun vulnerabilities have plagued security ar-chitects for at least a decade. In November 1988, the in-famous Internet worm infected thousands or tens of thou-sands of network-connected hosts and fragmented much ofthe known net [17]. One of the primary replication mecha-nisms was exploitation of a buffer overrun vulnerability inthe fingerd daemon.Since then, buffer overruns have been a serious, continu-ing menace to system security. If anything, the incidence ofbuffer overrun attacks has been increasing. See Figure 1 fordata extracted from CERT advisories over the last decade.Figure 1 shows that buffer overruns account for up to 50%of today’s vulnerabilities, and this ratio seems to be increas-ing over time. A partial examination of other sources sug-gests that this estimate is probably not too far off: bufferoverruns account for 27% (55 of 207) of the entries in onevulnerability database [29] and for 23% (43 of 189) in an-other database [33]. Finally, a detailed examination of threemonths of the bugtraq archives (January to March, 1998)shows that 29% (34 of 117) of the vulnerabilities reportedare due to buffer overrun bugs [7].Buffer overruns are so common because C is inherentlyunsafe. Array and pointer references are not automaticallybounds-checked, so it is up to the programmer to do the∗This research was supported in part by the National Science Founda-tion Young Investigator Award No. CCR-9457812, NASA Contract No.NAG2-1210, and an NDSEG fellowship.checks herself. More importantly, many of the string op-erations supported by the standard C library—strcpy(),strcat(), sprintf(), gets(), and so on—are un-safe. The programmeris responsible for checking that theseoperations cannot overflow buffers, and programmers oftenget those checks wrong or omit them altogether.As a result, we are left with many legacy applications thatuse the unsafe string primitives unsafely. Programs writtentoday still use unsafe operations such as strcpy() be-cause they are familiar. Even sophisticated programmerssometimes combine the unsafe primitives with some ad-hoc checks, or use unsafe primitives when they somehow“know” that the operation is safe or that the source stringcannot come under adversarial control.Unfortunately, programs that use just the “safe” subset ofthe C string API are not necessarily safe, because the “safe”string primitives have their own pitfalls [43]:• The strn*() calls behave dissimilarly. For instance,strncpy(dst, src, sizeof dst) is correctbut strncat(dst, src, sizeof dst) iswrong. Inconsistency makes it harder for the program-mer to remember how to use the “safe” primitivessafely.• strncpy() may leave the target bufferunterminated.In comparison, strncat() and snprintf() al-ways append a terminating ’\0’ byte, which is an-other example of dissimilarity.• Using strncpy() has performanceimplications, be-cause it zero-fills all the available space in the tar-get buffer after the ’\0’ terminator. For example,a strncpy() of a 13-byte buffer into a 2048-bytebuffer overwrites the entire 2048-byte buffer.• strncpy() and strncat() encourage off-by-one bugs. For example, strncat(dst, src,sizeof dst - strlen(dst) - 1) is correct,but don’t forget the -1!• snprintf() is perhaps the best of the “safe” primi-tives: it has intuitive rules, and it is very general. How-ever, until recently it was not available on many sys-tems, so portable programs could not rely on it.0510152025301988199019921994199619980%10%20%30%40%50%60%198819901992199419961998Figure 1. Frequency of buffer overrun vulnerabilities, derived from a classification of CERT advisories. Theleft-hand chart shows, for each year, the total number of CERT-reported vulnerabilities and the number thatcan be blamed primarily on buffer overruns. The right-hand chart graphs the percentage of CERT-reportedvulnerabilities that were due to buffer overruns for each year.In all cases, the programmer must still keep track of bufferlengths accurately, which introduces another opportunityfor mistakes.In short, today’s C environments make it easy to do thewrong thing, and, worse still, hard to do the right thing withbuffers. This suggests that an automated tool to help de-tect this class of security-relevant coding errors may be ofconsiderable benefit.1.1. OverviewThis paper describes a tool we developed to detect bufferoverruns in C source code. Though this is only a firstprototype, early results look promising. For example, thetool found several serious new vulnerabilities in one largesecurity-critical application, even though it had been hand-audited previously.This work involves a synthesis of ideas from severalfields, including program analysis, theory, and systems se-curity. The main idea is to apply standard static analy-sis techniques from the programming languages literatureto the task of detecting potential security holes. We focusspecifically on static analysis so that vulnerabilities can beproactively identified and fixed before they are exploited.We formulate the buffer overrun detection problem as aninteger constraint problem, and we use some simple graph-theoretic techniques to construct an efficient algorithm forsolving the integer constraints. Finally, security knowl-edge is used to formulate heuristics that capture the class ofsecurity-relevant bugs that tend to occur in real programs.Others have applied runtime code-testing techniques tothe problem, using, e.g., black-box testing [41, 42] or soft-ware fault injection [21] to find buffer overrunsin real-worldapplications. However, runtime testing seems likely to missmany vulnerabilities. Consider the following example:if (strlen(src) > sizeof dst)break;strcpy(dst, src);Note that off-by-one errors in buffer