Dynamic Binary Analysis And Instrumentation - Valgrind
Dynamic Binary Analysis and InstrumentationorBuilding Tools is EasyNicholas NethercoteTrinity CollegeA dissertation submitted for the degree ofDoctor of Philosophy at the University of CambridgeCopyright c 2004 Nicholas Nethercote
ii
Statement of OriginalityMost of the work described in this dissertation is my own, but some of the work described was donein collaboration with others.Chapters 1, 6 and 7 are entirely my own work.Chapter 2 describes a software system that I implemented large parts of, but which is partly thework of others. Without my contributions to this system, the work described in chapters 3, 4, 5 and 6would not have been possible. The contributions of others to this system are described within the textin Sections 1.2.3, 2.1.3 and 2.4.1. Chapter 2 is partly based on a publication [82] that I co-authoredwith Julian Seward.Chapters 3, 4 and 5 describe software tools that I designed and implemented. Chapter 3 containsone section (Section 3.4) that is derived from a publication [80] that I co-authored with Alan Mycroft.Chapter 4 is based on a publication [79] that I co-authored with Jeremy Fitzhardinge. Chapter 5 isbased on a publication [81] that I co-authored with Alan Mycroft.The section “Author Publications” below lists all these publications. They are also listed in thebibliography.All the words, tables and figures within are my own.No part of this dissertation has been submitted, or is being concurrently submitted, for a degree ordiploma or any other qualification at this or any other university.This dissertation does not exceed 60,000 words, including tables and footnotes, but excluding diagrams and the bibliography.Nicholas Nethercote,11th November 2004.
iv
Author PublicationsParts of the research presented in this dissertation have been previously published or presented in thefollowing papers.Nicholas Nethercote and Alan Mycroft.The cache behaviour of large lazy functional programson stock hardware. In Proceedings of the ACM SIGPLAN Workshop on Memory System Performance(MSP 2002), pages 44–55, Berlin, Germany, July 2002.Nicholas Nethercote and Alan Mycroft.Redux: A dynamic dataflow tracer.In Proceedings ofthe Third Workshop on Runtime Verification (RV’03), Boulder, Colorado, USA, July 2003.Nicholas Nethercote and Julian Seward.Valgrind: A program supervision framework.In Pro-ceedings of the Third Workshop on Runtime Verification (RV’03), Boulder, Colorado, USA, July 2003.Nicholas Nethercote and Jeremy Fitzhardinge.Bounds-checking entire programs without recom-piling. In Informal Proceedings of the Second Workshop on Semantics, Program Analysis, and Computing Environments for Memory Management (SPACE 2004), Venice, Italy, January 2004.
vi
AbstractDynamic binary analysis (DBA) tools such as profilers and checkers help programmers create bettersoftware. Dynamic binary instrumentation (DBI) frameworks make it easy to build new DBA tools.This dissertation advances the theory and practice of dynamic binary analysis and instrumentation,with an emphasis on the importance of the use and support of metadata.The dissertation has three main parts.The first part describes a DBI framework called Valgrind which provides novel features to supportheavyweight DBA tools that maintain rich metadata, especially location metadata—the shadowing ofevery register and memory location with a metavalue. Location metadata is used in shadow computation, a kind of DBA where every normal operation is shadowed by an abstract operation.The second part describes three powerful DBA tools. The first tool performs detailed cache profiling. The second tool does an old kind of dynamic analysis—bounds-checking—in a new way.The third tool produces dynamic data flow graphs, a novel visualisation that cuts to the essence ofa program’s execution. All three tools were built with Valgrind, and rely on Valgrind’s support forheavyweight DBA and rich metadata, and the latter two perform shadow computation.The third part describes a novel system of semi-formal descriptions of DBA tools. It gives manyexample descriptions, and also considers in detail exactly what dynamic analysis is.The dissertation makes six main contributions.First, the descriptions show that metadata is the key component of dynamic analysis; in particular,whereas static analysis predicts approximations of a program’s future, dynamic analysis remembersapproximations of a program’s past, and these approximations are exactly what metadata is.Second, the example tools show that rich metadata and shadow computation make for powerfuland novel DBA tools that do more than the traditional tracing and profiling.Third, Valgrind and the example tools show that a DBI framework can make it easy to buildheavyweight DBA tools, by providing good support for rich metadata and shadow computation.Fourth, the descriptions are a precise and concise way of characterising tools, provide a directedway of thinking about tools that can lead to better implementations, and indicate the theoretical upperlimit of the power of DBA tools in general.Fifth, the three example tools are interesting in their own right, and the latter two are novel.Finally, the entire dissertation provides many details, and represents a great deal of condensedexperience, about implementing DBI frameworks and DBA tools.
viii
AcknowledgementsI must thank many people. Without their help and support, this work would not have been possible.Julian Seward, for having the audacity and ability to create Valgrind; for letting me rip it to pieces;and for answering a million questions.Alan Mycroft, for his experience; for stimulating discussions; for boundless optimism during theslow patches; and for telling me when to stop hacking.Jeremy Fitzhardinge, Tom Hughes, Josef Weidendorfer, Dirk M üller, Robert Walsh, Paul Mackerras, Donna Robinson, and all the others who have contributed to Valgrind.Jeremy Singer, Tom Stuart, and the other members of the Cambridge Programming ResearchGroup, for their fine company.Trinity College, Cambridge, for supporting me financially and providing a home and community.And finally, my family and Christine Vogel, for their love and support, and doing their best tounderstand what it is that I study.
x
Contents1 Introduction1.11.21Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.1.1Static Analysis vs. Dynamic Analysis . . . . . . . . . . . . . . . . . . . . .11.1.2Source Analysis vs. Binary Analysis . . . . . . . . . . . . . . . . . . . . . .21.1.3Four Kinds of Program Analysis . . . . . . . . . . . . . . . . . . . . . . . .31.1.4Static Binary Instrumentation vs. Dynamic Binary Instrumentation . . . . .3This Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41.2.1Dissertation Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41.2.2Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41.2.3A Note About Implementations . . . . . . . . . . . . . . . . . . . . . . . .52 A Framework for Building Tools2.17Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.1.1Dynamic Binary Instrumentation Frameworks . . . . . . . . . . . . . . . . .72.1.2Overview of Valgrind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.1.3Chapter Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .82.2Using Valgrind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .82.3How Valgrind Works: The Core . . . . . . . . . . . . . . . . . . . . . . . . . . . .102.3.1Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .102.3.2Definition of a Basic Block . . . . . . . . . . . . . . . . . . . . . . . . . . .112.3.3Resource Conflicts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112.3.4Starting Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .122.3.5Making Translations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .132.3.6Executing Translations . . . . . . . . . . . . . . . . . . . . . . . . . . . . .162.3.7Floating Point, MMX and SSE Instructions . . . . . . . . . . . . . . . . . .172.3.8Segment Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .182.3.9Pthreads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .182.3.10 System Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .192.3.11 Signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20
xiiCONTENTS2.3.12 Client Requests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .202.3.13 Self-modifying Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .212.3.14 Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . .212.3.15 Ensuring Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .212.3.16 Termination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .222.3.17 Self-hosting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22How Valgrind Works: Tool Plug-ins . . . . . . . . . . . . . . . . . . . . . . . . . .222.4.1An Example Tool: Memcheck . . . . . . . . . . . . . . . . . . . . . . . . .222.4.2Execution Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .232.4.3Tool Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .242.4.4Shadow Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .252.4.5Crucial Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .272.5Size of Core and Tool Plug-ins . . . . . . . . . . . . . . . . . . . . . . . . . . . . .302.6Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .312.7Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .322.7.1Not Quite Dynamic Binary Analysis . . . . . . . . . . . . . . . . . . . . . .322.7.2Not Quite Dynamic Binary Instrumentation . . . . . . . . . . . . . . . . . .332.7.3Dynamic Binary Instrumentation Frameworks . . . . . . . . . . . . . . . . .35Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .452.42.83 A Profiling Tool3.147Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .473.1.1Profiling Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .473.1.2Cache Effects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .483.1.3Cache Profiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .493.1.4Overview of Cachegrind . . . . . . . . . . . . . . . . . . . . . . . . . . . .493.1.5Chapter Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .503.2Using Cachegrind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .503.3How Cachegrind Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .513.3.1Metadata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .513.3.2Instrumentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .553.3.3Code Unloading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .573.3.4Output and Source Annotation . . . . . . . . . . . . . . . . . . . . . . . . .573.3.5Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .583.3.6Useful Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .593.3.7Simulation Shortcomings . . . . . . . . . . . . . . . . . . . . . . . . . . . .603.3.8Usability Shortcomings . . . . . . . . . . . . . . . . . . . . . . . . . . . . .61In Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .623.4.1Language and Implementation . . . . . . . . . . . . . . . . . . . . . . . . .623.4.2Benchmark Suite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .633.4.3Motivating Measurements . . . . . . . . . . . . . . . . . . . . . . . . . . .633.4
CONTENTSxiii3.4.4Quantifying Cachegrind’s Accuracy . . . . . . . . . . . . . . . . . . . . . .643.4.5Use of Cachegrind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .643.4.6Avoiding Data Write Misses . . . . . . . . . . . . . . . . . . . . . . . . . .653.5Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .663.6Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .674 A Checking Tool4.169Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .694.1.1Checking Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .694.1.2Bounds Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .704.1.3Bounds-Checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .704.1.4Overview of Annelid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .704.1.5Chapter Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .714.2Using Annelid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .714.3How Annelid Works: Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .724.3.1Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .724.3.2Metadata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .734.3.3Checking Accesses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .734.3.4Life-cycle of a Segment . . . . . . . . . . . . . . . . . . . . . . . . . . . .744.3.5Heap Segments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .744.3.6Static Segments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .754.3.7Stack Segments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .774.3.8Shadow Computation Operations . . . . . . . . . . . . . . . . . . . . . . .78How Annelid Works: Implementation . . . . . . . . . . . . . . . . . . . . . . . . .814.4.1Metadata Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . .814.4.2Segment Structure Management . . . . . . . . . . . . . . . . . . . . . . . .824.4.3Static Segments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .834.4.4Stack Segments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .834.4.5Range Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .844.4.6Pointer Differences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .844.4.7System Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .844.4.8Custom Allocators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .854.4.9Leniency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .854.4.10 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .854.4.11 Real World Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .854.4.12 Crucial Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .86Shortcomings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .864.5.1Optimal Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .864.5.2Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .874.5.3No Debug Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . .874.5.4No Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .874.44.5
xivCONTENTS4.5.54.64.7Avoiding Shortcomings . . . . . . . . . . . . . . . . . . . . . . . . . . . . .88Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .884.6.1Red-zones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .884.6.2Fat Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .904.6.3Mixed Static and Dynamic Analysis . . . . . . . . . . . . . . . . . . . . . .914.6.4Static Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .914.6.5Runtime Type Checking . . . . . . . . . . . . . . . . . . . . . . . . . . . .92Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .925 A Visualisation Tool5.15.25.35.45.55.693Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .935.1.1Program Comprehension Tools . . . . . . . . . . . . . . . . . . . . . . . . .935.1.2Visualising Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .935.1.3Overview of Redux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .935.1.4Chapter Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .94Using Redux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .945.2.1Dynamic Data Flow Graphs . . . . . . . . . . . . . . . . . . . . . . . . . .955.2.2Factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .955.2.3Hello World . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .95How Redux Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .985.3.1Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .985.3.2Metadata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .985.3.3System Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .995.3.4Sub-word Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1005.3.5Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1015.3.6Lazy Node Building . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1015.3.7Rewriting and Printing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1015.3.8Crucial Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102Essences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1025.4.1Program Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1025.4.2Factorial in C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1035.4.3Factorial on a Stack Machine . . . . . . . . . . . . . . . . . . . . . . . . . . 1035.4.4Factorial in Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103Possible Uses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1045.5.1Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1045.5.2Dynamic Program Slicing . . . . . . . . . . . . . . . . . . . . . . . . . . . 1065.5.3Other Uses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107Difficulties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1085.6.1Normalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1095.6.2Loop Rolling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1095.6.3Conditional Branches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
CONTENTSxv5.6.4Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1105.6.5Limitations of the Implementation . . . . . . . . . . . . . . . . . . . . . . . 1115.7Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1115.8Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1126 Describing Tools6.16.26.3Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1136.1.1Tool Differences and Similarities . . . . . . . . . . . . . . . . . . . . . . . 1136.1.2Tool Descriptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1146.1.3Chapter Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114The Big Picture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1156.2.1Description Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1156.2.2A First Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1186.3.16.46.56.66.7113M-hooks and Built-in I-hooks . . . . . . . . . . . . . . . . . . . . . . . . . 118Descriptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1216.4.1Basic Ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1216.4.2Formal Description of Metadata . . . . . . . . . . . . . . . . . . . . . . . . 1226.4.3Informal Description of Metadata . . . . . . . . . . . . . . . . . . . . . . . 1226.4.4Formal Description of Analysis Code . . . . . . . . . . . . . . . . . . . . . 1236.4.5Informal Description of Analysis Code . . . . . . . . . . . . . . . . . . . . 124Descriptions of Simple Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1246.5.1Tools Using No Metadata . . . . . . . . . . . . . . . . . . . . . . . . . . . 1246.5.2Tools Using Global Metadata . . . . . . . . . . . . . . . . . . . . . . . . . 1266.5.3Tools Using Per-Location Metadata . . . . . . . . . . . . . . . . . . . . . . 1276.5.4Tools Using Per-Value Metadata . . . . . . . . . . . . . . . . . . . . . . . . 128Custom I-hooks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1286.6.1A Simple Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1296.6.2System Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1306.6.3Function Replacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1316.6.4Memory Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132Descriptions of Valgrind Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1356.7.1Memcheck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1356.7.2Addrcheck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1386.7.3Cachegrind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1386.7.4Annelid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1396.7.5Redux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1406.8Limits of Dynamic Binary Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 1416.9What is Dynamic Analysis? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1426.10 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1446.10.1 Benefits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
xviCONTENTS6.10.2 Shortcomings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1466.10.3 Ideality vs. Reality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1476.10.4 Executable Descriptions? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1476.11 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1486.11.1 Classifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1486.11.2 Specification Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1496.12 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1517 Conclusion1537.1What Just Happened . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1537.2Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1547.37.2.1New Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1547.2.2New Operating Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1557.2.3New Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1557.2.4Avoiding Code Blow-up . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156Final Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156A Glossary157Bibliography161
List of Figures2.1Conceptual view of program execution . . . . . . . . . . . . . . . . . . . . . . . . .102.2Disassembly: x86 code UCode . . . . . . . . . . . . . . . . . . . . . . . . . . .142.3Code generation: Register-allocated UCode x86 . . . . . . . . . . . . . . . . . .153.1Fast and slow array traversal: fast.c and slow.c . . . . . . . . . . . . . . . . . .483.2Global cache statistics for fast.c and slow.c . . . . . . . . . . . . . . . . . . . .513.3Line-by-line cache statistics for fast.c and slow.c . . . . . . . . . . . . . . . . .523.4Cost centre types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .543.5Instr-info nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .543.6Example basic block, instrumented . . . . . . . . . . . . . . . . . . . . . . . . . . .563.7Cachegrind output file example . . . . . . . . . . . . . . . . . . . . . . . . . . . . .584.1Program with bounds errors: bad.c . . . . . . . . . . . . . . . . . . . . . . . . . .724.2Bounds errors detected for bad.c . . . . . . . . . . . . . . . . . . . . . . . . . . .734.3Hard-wired static array accesses . . . . . . . . . . . . . . . . . . . . . . . . . . . .765.1DDFGs for iterative and recursive fac(5) in C . . . . . . . . . . . . . . . . . . . .965.2DDFGs for Hello World . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .975.3Building a DDFG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1005.4Accumulator recursive fac(5) in C . . . . . . . . . . . . . . . . . . . . . . . . . . 1035.5DDFG for iterative fac(5) on an interpreted stack machine . . . . . . . . . . . . . 1045.6DDFGs for iterative and recursive fac(5) in Haskell . . . . . . . . . . . . . . . . . 1055.7Slices for the return value of factorial programs . . . . . . . . . . . . . . . . . . . . 1075.8A program with a complex condition . . . . . . . . . . . . . . . . . . . . . . . . . . 1095.9DDFGs for bzip2 when compressing a two-byte file and a ten-byte file . . . . . . . . 1106.1Example DTrace probes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
xviiiLIST OF FIGURES
List of Tables1.1Four kinds of program analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32.1Five steps to translate a basic block . . . . . . . . . . . . . . . . . . . . . . . . . . .132.2Lines of code in core and tool plug-ins . . . . . . . . . . . . . . . . . . . . . . . . .302.3Slow-down factor of five tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . .322.4Code expansion factor of five tools . . . . . . . . . . . . . . . . . . . . . . . . . . .332.5Eleven dynamic binary instrumentation frameworks . . . . . . . . . . . . . . . . . .363.1Model 4 Athlon characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . .483.2Haskell program descriptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .633.3Ratios between hardware counter and software simulation event counts . . . . . . . .643.4Effect of prefetching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .654.1Basic shadow operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .796.1M-hooks, I-hooks, and their attributes . . . . . . . . . . . . . . . . . . . . . . . . . 119
xxLIST OF TABLES
CHAPTER1IntroductionThis dissertation advances the theory and practice of dynamic binary analysis and instrumentation,with an emphasis on the importance of the use and support of metadata.1.1BackgroundProgramming is difficult, especially in languages like C and C that are low-level and provide little protection against common programming errors. As both software and hardware systems growincreasingly complex, programmers need more help than ever. Tools that can be used to improve program quality, particularly correctness and speed, are therefore invaluable. Many such tools use somekind of program analysis to determine interesting information about programs.This dissertation is largely about two things: dynamic binary analysis (DBA), a particular kind ofprogram analysis; and dynamic binary instrumentation (DBI), a particular implementation techniquefor DBA. This section shows how these two things fit into the wide world of program analysis.1.1.1 Static Analysis vs. Dynamic AnalysisProgram analyses can be categorised into two groups according to when the analysis occurs.1. Static analysis involves analysing a program’s source code or machine code without runningit. Many tools perform static analysis, in particular compilers; examples of static analysesused by compilers include analyses for correctness, such as type checking, and analyses foroptimisation, which identify valid performance-improving transformations. Also, some standalone static analysis tools can identify bugs or help visualise code. Tools performing staticanalysis only need to read a program in order to analyse it.2. Dynamic analysis involves analysing a client program as it executes. Many tools perform dynamic analysis, for example, profilers, checkers and execution visualisers. Tools performing
2Chapter 1. Introductiondynamic analysis must instrument 1 the client program with analysis code. The analysis codemay be inserted entirely inline; it may also include external routines called from the inline analysis code. The analysis code runs as part of the program’s normal execution, not disturbing theexecution (other than probably slowing it down), but doing extra work “on the side”, such asmeasuring performance, or identifying bugs.2 The analysis code must maintain some kind ofanalysis state, which I call metadata (and individual pieces of metadata are metavalues). Metadata is absolutely crucial, and at the very heart of dynamic analysis, as this dissertation willshow.The two approaches are complementary. Static analysis can be sound, as it can consider all executionpaths in a program, whereas dynamic analysis is unsound in general, as it only considers a singleexecution path [41]. However, dynamic analysis is typically more precise than static an
example descriptions, and also considers in detail exactly what dynamic analysis is. The dissertation makes six main contributions. First, the descriptions show that metadata is the key component of dynamic analysis; in particular, whereas static analysis predicts approximations of a program's future, dynamic analysis remembers
Binary prices Binary prices rautmann (2013 Binary no price Epstein (2002 Binary prices al. (2014 Binary maximis- seek- er- t al. (2010 Binary individ- price al. 2014 Binary prices Binary sset prices Halevy (2019 Auction y Binary diffi- sig- nals Liang (2019 sm y Binary erreac- news al. (2012 Auction y Binary under- signals et y Gaussian erreac .
Lecture #1: Bits, Bytes, and Binary CS106E Spring 2018, Young The binary number system underlies all modern computers. In this lecture we'll take a look at the binary number system and some of the implications of using binary numbers. Having a solid grounding in binary will set us up to explore digital images and digital music in the next two .
Binary compounds are those that are composed of only two elements. There are three types of binary compounds: binary covalent compounds, binary ionic compounds and binary acids. Examples of binary covalent compounds include water (H 2O), carbon monoxide (CO), and carbon dioxide CO 2. The naming convention for bina
And there are also only two options of the outcome that is: right or wrong. Hence, Binary Options are also known as Binary Bets or Binary Transactions. This simplicity, the simple two-way choice, is one of the main reasons why Binary Options have been so successful since their beginning. Binary Options exist since 2008 and in 2012 it became .
dynamic analysis runs an instrumented program in a controlled manner to collect information which can be analyzedto learn about a property of interest. Computing test coverage is a dynamic analysis. Instrumentation can take the form of source code or binary rewriting. Dynamic analysis limitations include efficiency, false positives and
encoded with 0 and the others with 1; A binary number is ob-tained by concatenating all these binary codes in a clockwise direction starting from the top-left one and its corresponding decimal value is used for labeling. The derived binary numbers are referred to as Local Binary Patterns or LBP codes. Fig. 1. An example of the basic LBP operator.
Lab 6: Instrumentation Amplifier . INTRODUCTION: A fundamental building block for electrical measurements of biological signals is an instrumentation amplifier. In this lab, you will explore the operation of instrumentation amplifiers by designing, building, and characterizing the most basic instrumentation amplifier structure.
Health in Care Homes service provides a clear framework for delivering healthcare through the support of a multi-disciplinary team including primary care, specialists, community-based care services and care home staff. The Care Provider Alliance looks forward to continuing to work with our members and our health colleagues to ensure all care homes have access to this support.” Kathy Roberts .
