DIVINE: DIscovering Variables IN Executables
Gogul Balakrishnan and Thomas Reps
This paper addresses the problem of recovering variable-like entities
when analyzing executables in the absence of debugging information. We
show that variable-like entities can be recovered by iterating
Value-Set Analysis (VSA), a combined numeric-analysis and
pointer-analysis algorithm, and Aggregate Structure Identification, an
algorithm to identify the structure of aggregates. Our initial
experiments show that the technique is successful in correctly
identifying 88% of the local variables and 89% of the fields of
heap-allocated objects. Previous techniques recovered 83% of the local
variables, but 0% of the fields of heap-allocated objects. Moreover,
the values computed by VSA using the variables recovered by our
algorithm would allow any subsequent analysis to do a better job of
interpreting instructions that use indirect addressing to access
arrays and heap-allocated data objects: indirect operands can be
resolved better at 4% to 39% of the sites of writes and up to 8% of
the sites of reads. (These are the memory-access operations for which
it is the most difficult for an analyzer to obtain useful results.)
(Click here to access the paper:
PDF;
(c) Springer-Verlag.)
University of Wisconsin