Research On Statement Recovery And Algorithm Recognition In Code Reverse Analysis

During code reverse analysis, analyst can easily gain structural and functional information of binary code by improving abstract representation and recognizing algorithms of the given code. This thesis focuses on Approximate High Level (AHL) statement recovery and algorithm recognition based on AHL, which are technical favors for code analysis.Firstly, on the basis of analyzing grammar of the intermediate language (IL), the data flow analysis method of IL is proposed. Data flow analysis puts emphasis upon building used and defined collections of each intermediate statement, meanwhile the effect of register overlapping to definition is also solved. Secondly, according to the data flow information of IL collected by data flow analysis, register retrospection is proposed to recovery statements. Statement recovery stresses on problems of overlapped definitions and multiple definitions of registers. Besides, this dissertation provides a method to recover register parameters by dint of statement recovery. Thirdly, after analyzing typical algorithms, characteristic expressions are picked up as the distinguishable characteristics described by XML for later recognition. Fourthly, operator precedence analysis is used for constructing abstract syntax trees of expressions, and characteristic expressions are automatically recognized by determining the consistence between abstract syntax trees using two policies. Finally, the dissertation implements a prototype system of statement recovery and algorithm recognition.In the end, the prototype system is tested and the results are presented. According to the results, 95 percent of the recovered statements are correct, and more than ten kinds of algorithms are recognized successfully by recognizing characteristic expressions of them.