Prev: Object File Formats
Identifying Code and Data
Since non-code can be present in an executable section, we need some way to identify
which sequences of bytes are actually code and which are not.
The decompiler knows where the program starts executing from the object file format
(the program's entry point).
A simple and safe algorithm for identifying code regions is to analyze which
instructions can be reached from the program's entry point. The following pseudo-code
would produce a list of function entry points (as well as some additional useful
callList = entry_address
while callList not empty
address = pop from callList
functionList += new function starting at address
if instr at address is jump
workList += jump destination
if instr at address is call
callList += call destination
if instr at address is ret
if workList empty
if instr is not conditional
address = pop from workList
address += instr length
The same algorithm can be applied to any function entry point. If the binary
file has a symbol table (whether a low-level list of labels or high-level
debugging information), we can call the algorithm for all known function entry
Unfortunately the previous algorithm has a few shortcomings:
- it does not recognize functions accessed via function pointers;
- it does not follow indirect jumps, such as those used in switch
- it does not identify functions that are present in the binary file
but never called.
Functions accessed via function pointers are found in the following cases:
- straight function pointers stored in memory. In this case the decompiler
should report that the call is through a user variable. It is not possible
for the decompiler to know which functions can be called from that
- virtual functions accessed through a C++ virtual table.
- functions accessed through dynamic library trampoline code. Since the
trampoline code has to be exported to the dynamic linker for the dynamic
linker to be able to patch it with the address of the entry point to the
dynamic linbrary function, these can usually be safely converted into direct
calls to the trampoline code, and mark the trampoline code as the entry
point of the library function.
- functions that are accessed through a register which has been
initialized with the destination address of a global function. This is a
difficult case, which requires data flow analysis to compute which value is
contained in the register at the call point. But since we don't know which
bytes are code and which are data, yet, we cannot perform such analysis
until much later.
Since we have established that the previous algorithm will not find all
functions, we need to apply further analyses to identify the missing functions.
The following heuristics can be applied:
- use a library signature module to identify sequences of bytes that might
be the entry point of a function. Using a database of function byte
sequences also allows the identification of the function name, of any global
variables that may be used by the function, and the types of both the
function and its input parameters. If the function's behavior is known, we
can mark so that we don't decompile it, thus reducing the output only to
user functions and not to library functions.
- ask the processor module to provide a short sequence of bytes that is
typically used by a compiler to set up the stack frame at the beginning of a
function. Instruction sequences such as PUSH EBP + MOV EBP, ESP + SUB ESP,#
are typically found at the beginning of functions in x86 programs.
- assume that the first non-noop instructions after a RET instruction that
is not the destination of a jump is the entry point of a function. This is a
risky assumption to make, and it may consider as code bytes that are instead
data. One possibility is to give the user a list of such entry point and let
the user decide whether to use such addresses as function entry points.
The output of the algorithm is a list of function entry points, and a list of
jump and ret instructions, which will be used in constructing the basic blocks
of each function.
For each function, we also record the function that it calls.
Next : Basic Blocks