Valgrind: A Framework for Heavyweight Dynamic Binary ...

1 Valgrind: A Framework for Heavyweight Dynamic BinaryInstrumentationNicholas NethercoteNational ICT Australia, Melbourne, SewardOpenWorks LLP, Cambridge, Binary instrumentation (DBI) frameworks make it easyto build Dynamic Binary analysis (DBA) tools such as checkersand profilers. Much of the focus on DBI frameworks has been onperformance; little attention has been paid to their capabilities. As aresult, we believe the potential of DBI has not been fully this paper we describe Valgrind, a DBI Framework designedfor building Heavyweight DBA tools. We focus on its unique sup-port forshadow values a powerful but previously little-studiedand difficult-to-implement DBA technique, which requires a toolto shadow every register and memory value with another value thatdescribes it.

2 This support accounts for several crucial design fea-tures that distinguish Valgrind from other DBI frameworks. Be-cause of these features, lightweight tools built with Valgrind runcomparatively slowly, but Valgrind can be used to build more in-teresting, Heavyweight tools that are difficult or impossible to buildwith other DBI frameworks such as Pin and and Subject [Software Engineer-ing]: Testing and Debugging debugging aids, monitors; [Programming Languages]: Processors incremental compilersGeneral TermsDesign, Performance, ExperimentationKeywordsValgrind, Memcheck, Dynamic Binary instrumentation , Dynamic Binary analysis, shadow values1.

3 IntroductionValgrind is a Dynamic Binary instrumentation (DBI) frameworkthat occupies a unique part of the DBI Framework design paper describes how it works, and how it differs from Dynamic Binary Analysis and InstrumentationMany programmers use program analysis tools, such as errorcheckers and profilers, to improve the quality of their Binary analysis(DBA) tools are one such class of tools;they analyse programs at run-time at the level of machine tools are often implemented usingdynamic Binary instru-mentation(DBI), whereby theanalysis codeis added to the originalcode of theclient programat run-time.

4 This is convenient for users,Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. To copy otherwise, to republish, to post on servers or to redistributeto lists, requires prior specific permission and/or a 07 June 11 13, 2007, San Diego, California, 2007 ACM 978-1-59593-633-2/07/0006.. $ no preparation (such as recompiling or relinking) is , it gives 100% instrumentation coverage of user-mode code,without requiring source code.

5 Several genericDBI frameworksex-ist, such as Pin [11], DynamoRIO [3], and Valgrind [18, 15]. Theyprovide a base system that can instrument and run code, plus anenvironment for writing tools that plug into the base performance of DBI frameworks has been studied closely [1,2, 9]. Less attention has been paid to their instrumentation capabil-ities, and the tools built with them. This is a shame, as it is the toolsthat make DBI frameworks useful, and complex tools are more in-teresting than simple tools. As a result, we believe the potential ofDBI has not been fully Shadow Value Tools and Heavyweight DBAOne interesting group of DBA tools are those that useshadowvalues.

6 These tools shadow, purely in software, every register andmemory value with another value that says something about it. Wecall theseshadow value tools. Consider the following motivatinglist of shadow value tools; the descriptions are brief but demonstratethat shadow values (a) can be used in a wide variety of ways, and(b) are powerful and [25] uses shadow values to track which bit valuesare undefined ( uninitialised, or derived from undefined values)and can thus detect dangerous uses of undefined values. It is usedby thousands of C and C++ programmers, and is probably the mostwidely-used DBA tool in [20] tracks which byte values are tainted ( froman untrusted source, or derived from tainted values) and canthus detect dangerous uses of tainted [6] andLIFT[23] are similar and Ernst s secret-tracking tool [13] tracks whichbit values are secret ( passwords), and determines how muchinformation about secret inputs is revealed by public [4] tracks each value s type (determined from opera-tions performed on the value)

7 And can thus detect subsequent oper-ations inappropriate for a value of that [7] similarly determines abstract types of byte val-ues, for program comprehension and invariant detection [16] tracks which word values are array pointers, andfrom this can detect bounds [17] creates adynamic dataflow graph, a visualisation ofa program s entire computation; from the graph one can see all theprior operations that contributed to the each value s these tools each shadow value records a simple approxi-mation of each value s history one shadow bit per bit, one1 Purify [8] is a memory-checking tool similar to Memcheck.

8 However,Purify is not a shadow value tool as it does not does not track definednessof values through registers. As a result, it detects undefined value errors lessaccurately than byte per byte, or one shadow word per word which thetool uses in a useful way; in four of the above seven cases, the tooldetects operations on values that indicate a likely program value tools are a perfect example of what we call Heavyweight DBA tools. They involve large amounts of analysisdata that is accessed and updated in irregular patterns. They instru-ment many operations (instructions and system calls) in a varietyof ways for example, loads, adds, shifts, integer and FP opera-tions, and allocations and deallocations are all handled Heavyweight tools,the structure and maintenance of the tool sanalysis data is comparably complex to that of the client program soriginal data.

9 In other words, a Heavyweight tool s execution is ascomplex as the client program s. In comparison, more lightweighttools such as trace collectors and profilers add a lot of highly uni-form analysis code that updates analysis data in much simpler ways( appending events to a trace, or incrementing counters).Shadow value tools are powerful, but difficult to existing ones have slow-down factors of 10x 100x or evenmore, which is high but bearable if they are sufficiently are faster, but applicable in more limited circumstances, aswe will ContributionsThis paper makes the following contributions.

10 Characterises shadow value using shadow valuesare not new, but the similarities they share have received littleattention. This introduction has identified these similarities, andSection 2 formalises them by specifying the requirements ofshadow value tools in detail. Shows how to support shadow values in a DBI 3 describes how Valgrind works, emphasising its fea-tures that support robust Heavyweight tools, such as its coderepresentation, its first-class shadow registers, its events sys-tem, and its handling of threaded programs. This section doesnot delve deeply into well-studied topics, such as code cachemanagement and trace formation, that do not relate to shadowvalues and instrumentation capabilities.