Data Type Recovery Problem Of Decompilation

Decompilation can help us creat equivalent high level language code from machine/assembly language code. It helps a lot in transportation, comprehension, maintenance, development of software.At present, the data type recovery problem is the hot problem of decompilation, and relatively ripe and satisfactory data type recovery techniques have not been proposed. In this article, we discussed this problem in principle. A hypothesis of locality principle is proposed. Based on this hypothesis, a data type recovery algorithm is proposed. A concrete implementation is also given, which make use of two tools of compiler design: Lex and Yacc. The experiment shows that the effect of our algorithm is pretty well.The following are features of our algorithm: strict and sound theory basis, relatively complete discussion of data type recovery problem, easy implementation, good application and expansion.Further discussion of class type recovery problem of Object Orient language is given, and we get conclusion that this problem is not easily a data type recovery problem but a program structured problem in itself.For studying data type recovery problem in principle, we establish two formed and simplified language model: source language model C-Sub and object language model Assembly-Sub. By studying the data transformation between this two language, we propose locality principle which helps build up a type system for Assembly-Sub. In this system, every instruction has its corresponding strict type rule. According to these rules, the instructions of Assembly-Sub program is analyzed one by one to collect the type information of base type variables. Through analyzing these information synthetically, we try to find the complex type variables which are maybe in the program. By this way, we implement our data type recovery algorithm.We also expand our algorithm to the situation that the source language is C, complier is Turbo C v2.0. and object language is Intel 8086 assembly language. Lex and Yacc are used which simplify our implementation a lot.