top of page

Support Group

Public·88 members
Adrian Wright
Adrian Wright

Parasoft.C .Test.v2.2.1.2-AGAiN Fix Full Version


  • AbstractWe present Memcheck, a tool that has been implemented with thedynamic binary instrumentation framework Valgrind. Memcheck detects awide range of memory errors in programs as they run. This paperfocuses on one kind of error that Memcheck detects: undefined value errors.Such errors are common, and often cause bugs that are hard to find in programswritten in languages such as C, C++ and Fortran. Memcheck's definednesschecking improves on that of previous tools by being accurate to the level ofindividual bits. This accuracy gives Memcheck a low false positive and falsenegative rate.The definedness checking involves shadowing every bit of data inregisters and memory with a second bit that indicates if the bit has adefined value. Every value-creating operation is instrumented with ashadow operation that propagates shadow bits appropriately. Memcheckuses these shadow bits to detect uses of undefined values that couldadversely affect a program's behaviour.Under Memcheck, programs typically run 20-30 times slower thannormal. This is fast enough to use with large programs. Memcheckfinds many errors in real programs, and has been used during thepast two years by thousands of programmers on a wide range of systems,including OpenOffice, Mozilla, Opera, KDE, GNOME, MySQL, Perl, Samba,The GIMP, and Unreal Tournament.1 IntroductionThe accidental use of undefined values is a notorious source of bugsin programs written in imperative languages such as C, C++ andFortran. Such undefined value errors are easy to make, but canbe extremely difficult to track down manually, sometimes lurkingunfound for years.In this paper we describe Memcheck, a practical tool which detects awide range of memory errors, including undefined value errors.Memcheck is implemented using the dynamic binary instrumentationframework Valgrind [10,9]. 1.1 Basic operation and featuresMemcheck is a dynamic analysis tool, and so checks programs for errorsas they run. Memcheck performs four kinds of memory error checking. First, it tracks the addressability of every byte of memory, updating theinformation as memory is allocated and freed. With this information, it candetect all accesses to unaddressable memory.Second, it tracks all heap blocks allocated with malloc(), new andnew[]. With this information it can detect bad or repeated frees ofheap blocks, and can detect memory leaks at program termination.Third, it checks that memory blocks supplied as arguments tofunctions like strcpy() and memcpy() do not overlap. This does notrequire any additional state to be tracked.Fourth, it performs definedness checking: it tracks the definedness ofevery bit of data in registers and memory. With this information it can detectundefined value errors with bit-precision.All four kinds of checking are useful. However, of the four,definedness checking is easily the most sophisticated, and it isthis checking that this paper focuses on.Memcheck uses dynamic binary instrumentationto instrument the program to be checked (the client)on-the-fly at run-time. Execution of the added instrumentation code isinterleaved with the program's normal execution, not disturbing normal programbehaviour (other than slowing it down), but doing extra work ``on the side'' todetect memory errors. Because it instruments and analyses executable machinecode, rather than source code or object code, it has the following niceproperties.Wide applicability: it works with programs written in any language.1

  • Total coverage: all parts of the client are executed under Memcheck's control, including dynamically linked libraries and the dynamic linker, even if the source code is not available on the system. Indeed, it is only by doing this that Memcheck can be accurate--partial coverage leads either to lots of missed errors (false negatives) or lots of invalid errors (false positives).

  • Ease of use: unlike many similar tools, it does not require programs to be prepared (e.g. recompiled or relinked) in any way.

  • Memcheck is part of the Valgrind suite, which is free (GPL) software,and is available for download from the Valgrind website[14]. It currently runs only on the x86/Linuxplatform, although work is currently underway to port it to otherplatforms such as AMD64/Linux, PowerPC/Linux, x86/FreeBSD, andPowerPC/MacOSX.1.2 Using MemcheckFigure 1:Example program badprog.c Memcheck is easy to use. As an example, consider the (contrived) programbadprog.c in Figure 1. It contains three undefinedvalue errors. To check the compiled program badprog the user only hasto type: valgrind --tool=memcheck badprogThe --tool= option specifies which tool in theValgrind suite is used. The program runs under Memcheck's control,typically 20-30 times slower than usual. This slow-down is partlydue to Memcheck's definedness checking, partly due to its otherchecking, and partly due to Valgrind's inherent overhead. The program'soutput is augmented by Memcheck's output, which goes by default to standarderror, although it can be redirected to a file, file descriptor, or socket witha command line option.Figure 2:Example output for badprog.c Figure 2 shows the resulting output. The first three linesare printed by Memcheck on startup. The middle section shows threeerror messages issued by Memcheck. The final three lines are printed attermination, and summarise Memcheck's findings. Each line of Memcheck's outputis prefixed with the client's process ID, 27607 in this case.The three error messages are quite precise. The first indicates thatthe memory passed to the system call write() via the buf argumentcontains undefined values; its last line indicates that the undefinedvalue is on the stack of thread 1 (the main thread). The secondindicates that a conditional jump depends on an undefined value.The third indicates that an undefined value is used as a pointer.All three error messages include a stack trace that indicate preciselywhere the error is occurring. In order to get exact line numbers inthe stack traces, the client must be compiled with debugginginformation. If this is missing, the code locations are less precise,as can be seen with the location within the write() function(not to be confused with the write() system call)--GNU libc onthis system was not compiled with debugging information.Attentive readers may note that the final line of badprog.c could cause a segmentation fault due to the use of the uninitialisedvariable p as an address. On one system we tried this test on,exactly that happened, and so Memcheck issued an additional``Invalid read of size 4'' warning immediately before the memoryaccess, thanks to its addressability checking. For the run presented,the memory access (un)luckily hit addressable memory, so noaddressability error message was issued.1.3 Bit-level precisionFigure 3:Unsafe use of a bit-arrayMemcheck is the first tool we are aware of that tracks definednessdown to the level of bits. Other tools track definedness at bytegranularity (Purify) or word granularity (Third Degree).This means Memcheck correctly handles code which deals withpartially-defined bytes. In C and C++, two common idiomsgive rise to such bytes: use of bit arrays and use of bitfields instructures. Tools which track definedness at byte or wordgranularities necessarily give inaccurate results in suchsituations - either they fail to report genuine errors resulting fromuses of uninitialised bits, or they falsely flag errors resulting fromcorrect uses of partially defined bytes.The program shown in Figure 3 uses anuninitialised bit in a bit-array. Memcheck reports this, but Purifydoes not2. Memcheck is known to have found previously-undetected usesof single uninitialised bits in C++ structure bitfields, in at leastone large, widely used C++ code base.1.4 ContributionsOur main contribution is a detailed description of Memcheck's definednesschecking, which has only been briefly touched upon in previous publicationsabout Valgrind [10,9]. Memcheck's definednesschecking improves on that performed by previous tools by being accurate to thelevel of individual bits. Its falsepositive and false negative rates are very low. Finally, the run-time overheadof the definedness checking is reasonable enough that it is practical to use onvery large programs.1.5 Paper structureThe rest of this paper is structured as follows. Section 2 describes how Memcheck works, in particular thedetails of shadow bit operations, which are crucial in ensuringMemcheck's accuracy and speed. Section 3 evaluatesMemcheck by considering the cost of its use--in terms of how easy itis to obtain and run, the ease of using its results, and its impact onperformance--and the benefits provided by its bug-finding abilities.Section 4 discusses related work.Section 5 concludes. 2 How Memcheck works2.1 ValgrindMemcheck is implemented as a plug-in toValgrind [10,9]. Valgrind is aframework for creating tools that use dynamic binary instrumentation;it does all the hard work of inserting instrumentation intomachine code at run-time. Tools are created asplug-ins, written in C, to Valgrind'score.The basic view is:Valgrind core tool plug-in Valgrind tool.The resulting tool loads the client at start-up, grafting itself ontothe process as it does so. It then starts executing the client, by(re)compiling the client's code, one basic block at a time, in ajust-in-time, execution-driven fashion. The compilation processinvolves disassembling the machine code into an intermediaterepresentation called UCode. UCode is instrumented by the toolplug-in, and the instrumented UCode is then converted back into x86code. The resulting code is stored in Valgrind's code cache, to bererun as necessary.The core spends most of its execution time making, finding, andrunning translations. None of the client's original code is run. Thecore also provides many services to tools, to ease common tasks suchas recording errors and reading debug information. Only one tool canbe used at a time.The Valgrind distribution contains the core, plus five tools:Memcheck, Addrcheck (a lightweight version of Memcheck that omitsdefinedness checking), a cache profiler, a memory space-use (heap)profiler, and a data race detector for POSIX pthread-ed programs.2.2 OverviewThe basic idea underlying the definedness checking is straightforward. Every single bit of data, , maintained by a program, in both registers and memory, is shadowed by a piece of metadata, called a definedness bit. For historical reasons these are often also referred to as V bits (V being short for ``validity''). Each V bit indicates whether or not the bit it shadows is regarded as currently having a properly defined value.

  • Every single operation that creates a value is shadowed by a shadow operation that computes the V bits of any outputs, based on the V bits of all inputs and the operation. The exact operations performed by this shadow computation are important, as they must be sufficiently fast to be practical, and sufficiently accurate to not cause many false positives.

  • Every operation that uses a value in such a way that it could affect the observable behaviour of a program is checked. If the V bits indicate that any of the operation's inputs are undefined, an error message is issued. The V bits are used to detect if any of the following depend on undefined values: control flow transfers, conditional moves, addresses used in memory accesses, and data passed to system calls.Most operations do not directly affect the program's observable behaviour. In such cases, the V bits are not checked. Instead, V bits for the result of the operation are computed. Hence, for the most part, Memcheck silently tracks the flow of undefined values, and only issues an error message when use of such a value is potentially dangerous. This scheme is required because undefined values are often copied around without any problem, due to the common practice, used by both programmers and compilers, of padding structures to ensure fields are word-aligned.

  • From this overview, the main overheads of definedness checking areapparent. First, the use of V bits doubles the amount of memory inuse. Second, most instructions compute new values, and thus require ashadow operation itself consisting of one or more instructions.2.3 Details of V bitsA V bit of zero indicates thatthe corresponding data bit has a properly defined value, and a V bit of oneindicates that it does not. This is counterintuitive, but makes some of theshadow operations more efficient than they would be if the bit values wereinverted.Every 32-bit general purpose register is shadowed by a 32-bit shadow register,and every byte of memory has a shadow V byte. After that, there are some exceptions to the basic rule of ``one V bit per databit''.The x86 condition code register (%eflags) is approximated witha single V bit, since tracking all 6 condition codes individually isexpensive and mostly unnecessary.

  • The program counter is not shadowed. Instead, we regard it asalways defined, and emit an error message whenever a conditional jumpdepends on undefined condition codes. One way to interpret such ajump is as an attempt to assign an undefined value to the programcounter, but since we are not tracking the program counter'sdefinedness state, we regard it as always-defined, and so mustimmediately report any attempt to ``assign'' it an undefinedvalue.

  • Floating point, MMX and SSE registers are not shadowed.Memcheck can still perform definedness checkingon code using these registers, but such checks may produce a higher false positive rate than would have occurred had theregisters been shadowed.

  • 2.4 Instrumentation basicsIn principle it is possible to directly state the V bit transformationsrequired to shadow each x86 instruction. In practice, the x86instruction set is so complex and irregular that this would bedifficult and fragile. Fortunately, UCode (Valgrind's intermediaterepresentation) is RISC-like and clearly exposes all memory and arithmeticoperations, which makes Memcheck's instrumentation task much easier.Another important aspect of UCode is that it supports the use of aninfinite supply of virtual registers. The initial translation fromx86 is expressed in terms of such registers. Memcheckinterleaves its own instrumentation UCode with it, using asmany new virtual registers as required. Valgrind's core has the job ofperforming instruction selection and register allocation toconvert this sequence back to executable x86 code.2.5 Abstract operations on V bitsThe V bit instrumentation scheme is best described in terms of a family of simple abstract operations on V bits. We will use d1 andd2 to denote virtual registers holding real values, and v1 and v2 denote virtual shadow registers holding V bits. Also, some operations below use X and Y indicate the operand andresult widths in bytes (and 0 represents an operand with a width of asingle bit). Those operations for which the width is not specified arewidth-independent.Memcheck uses the following binary operations.DifD(v1,v2) (``defined if either defined'') returns a V bit vector the same width as v1 and v2. Each bit of the result indicates definedness if either corresponding operand bit indicates definedness. Since our encoding is zero for defined and one for undefined, DifD can be implemented using a bitwise-AND operation.

  • UifU(v1,v2) (``undefined if either undefined'') dually propagates undefinedness from either operand, again at a bitwise level, and can be implemented using a bitwise-OR operation.

  • ImproveAND(d,v) and ImproveOR(d,v) are helpers for dealing with AND and OR operations. These have the interesting property that the resulting V bits depend not only on the operand V bits, but also on the operand data values. ImproveAND takes a data value (d) and a V bit value (v), and produces an ``improvement value'' bitwise as follows:ImproveAND(0, undefined) = undefinedImproveAND(0, defined) = definedImproveAND(1, undefined) = undefinedImproveAND(1, defined) = undefined The second case is the interesting one. If one of the arguments is a defined zero bit, we don't care that the other argument might be undefined, since the result will be zero anyway. Hence ImproveAND creates a ``defined'' V-bit, which, as described in Section 2.6, is merged into the final result for AND using DifD. This has the effect of forcing that bit of the result to be regarded as defined. ``undefined'' is the identity value for DifD, so the other three cases have no effect on the final outcome.For exactly analogous reasons, ImproveOR behaves similarly, with the interesting case being ImproveOR(1, defined) = defined.

  • The following unary operations are also needed.Left(v) simulates the worst-case propagation of undefinedness upwards (leftwards) through a carry chain during integer add or subtract. Left(v) is the same as v, except that all bits to the left of the rightmost 1-bit in v are set. For example, using 8-bit values, Left(00010100) = 11111100. Left can be implemented in two x86 instructions, a negation followed by an OR operation.

  • PCastXY(v) are a family of size-changing operations which can be interpreted as ``pessimising casts''. If all bits of the operand are zero (defined), PCast produces a V bit vector at the new width in which all bits are zero (defined), else it produces a value with all bits one (undefined). For example, PCast12(00010100) = 1111111111111111, and PCast12(00000000) = 0000000000000000.These casts are used in various approximations in which the definedness checking needs to consider the worst-case across a whole word of bits. It is important to appreciate that the narrowing casts (where ) do not simply discard the high bits of the operand. Similarly, the case where is not the identity function. In all cases, each result bit depends on all operand bits, regardless of their relative sizes. PCast can be implemented in at most three x86 instructions: for narrowing casts, negation followed by subtract-with-borrow; for widening casts, a shift, a negation, and a subtract-with-borrow.

  • ZWidenXY(v) are a family of widening operations which mimic unsigned (zero-extend) widening of data values. As with PCast, X and Y denote argument and result widths, with the additional requirement that . Zero-widening a data value produces zeroes in the new positions, and so ZWiden needs to indicate these new positions are defined. Since defined values are encoded as zero bits, ZWiden can itself be implemented using a zero-widen instruction. This is the first of several cases where choosing zero (rather than one) to mean ``defined'' simplifies the implementation.

  • SWidenXY(v) is the dual family of signed widening operations. A signed widening copies the top argument bit into all new positions. Therefore SWiden has to copy the top definedness bit into all new positions and so can itself be implemented using a signed-widen instruction.

2.6 The instrumentation scheme properEvery operation (instruction or system call) that creates a value mustbe instrumented with a shadow operation that computes thecorresponding V bits. This section describes these shadow operationsin detail.Recall that for each virtual register in the incoming UCode, Memcheck allocates ashadow virtual register to carry the corresponding V bits.2.6.0.1 Register and memory initialisationAt startup, all registers have their V bits set to one,i.e. undefined. The exception is the stack pointer, which has itsV bits set to zero, i.e. defined.All memory bytes mapped at startup (i.e. code and data segments, andany shared objects) have their V bits set to zero (defined).2.6.0.2 Memory allocation and deallocationThe Valgrind framework intercepts function and system calls whichcause usable address ranges


About

Welcome to the group! You can connect with other members, ge...

Members

bottom of page