Understanding Integer Overflow in C/C++

1 Appeared inProceedings of the 34th International Conference on Software Engineering (ICSE), Zurich, Switzerland, June Integer Overflow in C/C++ Will Dietz, Peng Li, John Regehr, and Vikram Adve Department of Computer ScienceUniversity of Illinois at School of ComputingUniversity of Integer overflow bugs in C and C++ programsare difficult to track down and may lead to fatal errors orexploitable vulnerabilities. Although a number of tools forfinding these bugs exist, the situation is complicated becausenot all overflows are bugs. Better tools need to be constructed but a thorough Understanding of the issues behind these errorsdoes not yet exist. We developed IOC, a dynamic checking toolfor Integer overflows, and used it to conduct the first detailedempirical study of the prevalence and patterns of occurrenceof Integer overflows in C and C++ code.

2 Our results show thatintentional uses of wraparound behaviors are more commonthan is widely believed; for example, there are over 200distinct locations in the SPEC CINT2000 benchmarks whereoverflow occurs. Although many overflows are intentional, alarge number of accidental overflows also occur. Orthogonalto programmers intent, overflows are found in both well-defined and undefined flavors. Applications executing undefinedoperations can be, and have been, broken by improvements incompiler optimizations. Looking beyond SPEC, we found andreported undefined Integer overflows in SQLite, PostgreSQL,SafeInt, GNU MPC and GMP, Firefox, GCC, LLVM, Python,BIND, and OpenSSL; many of these have since been results show that Integer overflow issues in C and C++are subtle and complex, that they are common even in mature,widely used programs, and that they are widely misunderstoodby overflow; Integer wraparound; undefinedbehaviorI.

3 INTRODUCTIONI nteger numerical errors in software applications canbe insidious, costly, and exploitable. These errors includeoverflows, underflows, lossy truncations ( , a cast of anintto ashortin C++ that results in the value beingchanged), and illegal uses of operations such as shifts ( ,shifting a value in C by at least as many positions as itsbitwidth). These errors can lead to serious software failures, , a truncation error on a cast of a floating point value toa 16-bit Integer played a crucial role in the destruction ofAriane 5 flight 501 in 1996. These errors are also a sourceof serious vulnerabilities, such as Integer overflow errors inOpenSSH [1] and Firefox [2], both of which allow attackersto execute arbitrary code.

4 In their 2011 report MITRE placesinteger overflows in the Top 25 Most Dangerous SoftwareErrors [3].Detecting Integer overflows is relatively straightforwardby using a modified compiler to insert runtime , reliable detection of overflowerrorsis surprisinglydifficult because overflow behaviors are not always low-level nature of C and C++ means that bit- andbyte-level manipulation of objects is commonplace; the linebetween mathematical and bit-level operations can often bequite blurry. Wraparound behavior using unsigned integersis legal and well-defined, and there are code idioms thatdeliberately use it. On the other hand, C and C++ haveundefined semantics for signed overflow and shift pastbitwidth: operations that are perfectly well-defined in otherlanguages such as Java.

5 C/C++ programmers are not alwaysaware of the distinct rules for signed vs. unsigned types in C,and may na vely use signed types in intentional such uses were rare, compiler-based overflowdetection would be a reasonable way to perform Integer errordetection. If it is not rare, however, such an approach wouldbe impractical and more sophisticated techniques would beneeded to distinguishintentionaluses it is commonly known that C and C++ programscontain numerical errors and also benign, deliberate useof wraparound, it is unclear how common these behaviorsare and in what patterns they occur. In particular, there islittle data available in the literature to answer the followingquestions:1) How common are numericalerrorsin widely-usedC/C++ programs?

6 2) How common is use of intentional wraparound op-erations with signed types which has undefinedbehavior relying on the fact that today s compilersmay compile these overflows intocorrectcode? Werefer to these overflows as time bombs because theyremain latent until a compiler upgrade turns them intoobservable ) How common isintentionaluse of well-defined1In fact, in the course of our work, we have found that even expertswritingsafe Integer librariesortools to detect Integer errorsare not alwaysfully aware of the subtleties of C/C++ semantics for numerical 2012 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposesor for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works mustbe obtained from the operations on unsigned Integer types?

7 Although there have been a number of papers on toolsto detect numerical errors in C/C++ programs,no previouswork we know of has explicitly addressed these questions, orcontains sufficient data to answer any of closest isBrumley et al. s work [4], which presents data to motivate thegoals of the tool and also to evaluate false positives (invaliderror reports) due to intentional wraparound discussed in Section V, that paper only tangentiallyaddresses the third point above. We study all of thesequestions paper makes the following primary , we developed Integer Overflow Checker (IOC), anopen-source tool that detects both undefined Integer behav-iors as well as well-defined wraparound behaviors in C/C++ is an extension of the Clang compiler forC/C++ [5].

8 Second, we present the first detailed, empiricalstudy based on SPEC 2000, SPEC 2006, and a numberof popular open-source applications of the prevalence andpatterns of occurrence of numerical overflows in C/C++ programs. Part of this study includes a manual analysis of alarge number ofintentionaluses of wraparound in a subsetof the programs. Third, we used IOC to discover previouslyunknown overflow errors in widely- used applications andlibraries, including SQLite, PostgreSQL, BIND, Firefox,OpenSSL, GCC, LLVM, the SafeInt library, the GNU MPCand GMP libraries, Python, and PHP. A number of thesehave been acknowledged and fixed by the maintainers (seeSection IV).The key findings from our study of overflows are asfollows: First, all four combinations of intentional andunintentional, well-defined and undefined Integer overflowsoccur frequently in real codes.

9 For example, the SPECCINT2000 benchmarks had over 200 distinct occurrencesof intentional wraparound behavior, for a wide range ofdifferent purposes. Some uses for intentional overflows arewell-known, such as hashing, cryptography, random numbergeneration, and finding the largest representable value fora type. Others are less obvious, , inexpensive floatingpoint emulation, signed negation ofINT_MIN, and evenordinary multiplication and addition. We present a detailedanalysis of examples of each of the four major categoriesof overflow. Second, overflow-related issues in C/C++ arevery subtle and we find that even experts get them example, the latest revision of Firefox (as of Sep 1,2011) contained Integer overflowsin the library that wasdesigned to handle untrusted integers safelyin addition tooverflows in its own code.

10 More generally, we found veryfew mature applications that were completely free of integernumerical errors. This implies that there is probably littlehope of eliminating overflow errors in large code baseswithout sophisticated tool support. However, these tools2 IOC is available at IEXAMPLES OFC/C++ Integer OPERATIONS AND THEIR RESULTSE xpressionResultUINT_MAX+10 LONG_MAX+1undefinedINT_MAX+1undefinedSHR T_MAX+1 SHRT_MAX+1ifINT_MAX>SHRT_MAX,otherwise undefinedchar c = CHAR_MAX; c++varies1-INT_MINundefined2(char)INT_MA Xcommonly-11<<-1undefined1<<011<<31commo nlyINT_MINin ANSI C andC++98; undefined in C99 and C++112,31<<32undefined31/0undefinedINT_M IN%-1undefined in C11,otherwise undefined in practice1 The question is: Doescget promoted tointbefore being incre-mented?