Dynamic Binary Analysis and Instrumentation
University of Cambridge, A dissertation submitted for the degree of Doctor of Philosophy, (November 2004)It's related with Valgrind framework.
fulltitle:
Dynamic Binary Analysis and Instrumentation
or
Building Tools is Easy
Parts of the research presented in this dissertation have been previously published or presented in the
following papers.
Nicholas Nethercote and Alan Mycroft.
The cache behaviour of large lazy functional programs
on 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 of
the 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 Com-
puting Environments for Memory Management (SPACE 2004), Venice, Italy, January 2004..Abstract
Dynamic binary analysis (DBA) tools such as profilers and checkers help programmers create better
software. 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 support
heavyweight DBA tools that maintain rich metadata, especially location metadata—the shadowing of
every register and memory location with a metavalue. Location metadata is used in shadow computa-
tion, 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 pro-
filing. 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 of
a program’s execution. All three tools were built with Valgrind, and rely on Valgrind’s support for
heavyweight 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 many
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
approximations 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 powerful
and 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 build
heavyweight 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 directed
way of thinking about tools that can lead to better implementations, and indicate the theoretical upper
limit 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 condensed
experience, about implementing DBI frameworks and DBA tools.