WYSINWYX: What You See Is Not What You eXecute
Gogul Balakrishnan and Thomas Reps
Over the last seven years, we have developed static-analysis methods
to recover a good approximation to the variables and
dynamically-allocated memory objects of a stripped executable, and to
track the flow of values through them. The paper presents the
algorithms that we developed, explains how they are used to recover
intermediate representations (IRs) from executables that are similar
to the IRs that would be available if one started from source code,
and describes their application in the context of program
understanding and automated bug hunting.
Unlike algorithms for analyzing executables that existed prior to our
work, the ones presented in this paper provide useful information
about memory accesses, even in the absence of debugging information.
The ideas described in the paper are incorporated in a tool for
analyzing Intel x86 executables, called CodeSurfer/x86.
CodeSurfer/x86 builds a system dependence graph for the program, and
provides a GUI for exploring the graph by (i) navigating its edges, and
(ii) invoking operations, such as forward slicing, backward slicing,
and chopping, to discover how parts of the program can impact other
parts.
To assess the usefulness of the IRs recovered by CodeSurfer/x86 in the
context of automated bug hunting, we built a tool on top of
CodeSurfer/x86, called Device-Driver Analyzer for x86 (DDA/x86), which
analyzes device-driver executables for bugs. Without the benefit of
either source code or symbol-table/debugging information, DDA/x86 was
able to find known bugs (that had been discovered previously by
source-code-analysis tools), along with useful error traces, while
having a low false-positive rate. DDA/x86 is the first known
application of program analysis/verification techniques to industrial
executables.
(Click here to access the paper:
PDF.)