Proceedings of ISP RAS


Raising the level of abstraction of program’s execution trace.

Nazarov A.G., Klimushenkova M.A., Dovgalyuk P.M., Makarov V.A.

Abstract

This paper presents a method for raising the level of abstraction of a program execution trace by building of an algorithm model.

Dynamic analysis of executable files is often used to understand the logic of a program in the absence of source code. One of dynamic analysis methods is analysis of program execution traces containing register values and sequence of instructions executed by the processor.

Traces are difficult for understanding because of the large amount of information. First stage of building an algorithm model is identification of function calls in the trace. Input and output parameters are determined for each call. If the trace has got several calls for the same function, the information about them is combined, defining low-level parameters, return value, and dependencies between inputs and outputs.

Second stage is variable recovery. Low-level data elements are mapped on variables. Each processor has a fixed set of registers and limited memory and the number of higher-level variables in the program is not limited. Variable lifetime is evaluated for mapping variables to their locations. Lifetime is a range of trace step indexes from variable creation to its last usage. Return value and parameters of the function are recovered using its calling convention. Third stage is examination of library calls that are used in the trace. Symbolic information can be extracted from binary libraries and added to the corresponding functions in the trace. Header files are available for some libraries. Full high level function prototypes can be found from them and mapped to the trace.

This allows us to get high level types of parameters that are propagated along the trace through global variables and function calls.

Function models are combined into a high level model algorithm that can be used to restore or analyse it.

Keywords

dynamic analysis, variables recovery, interfaces recovery, decompilation

Edition

Proceedings of the Institute for System Programming, vol. 23, 2012, pp. 93-106.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2012-23-6

Full text of the paper in pdf (in Russian) Back to the contents of the volume