Research And Improvements On Data Structure Recovery

Software vulnerabilities make the system easily vulnerable to be attacked,and affect the effectiveness of system.Among the software vulnerabilities,composite types related vulnerabilities accounted for a larger proportion.The key to effective detection of such vulnerabilities in an executable program is the recovery of composite types.Since the program accessing such variables through a pointer,we use pointer analysis to restore the composite types.However,due to the lack of pointer connectivity analysis and other defects,the existing pointer analysis can't get the base address properly,thus affect the accuracy of complex data types recovery.This thesis makes four major contributions.(1)From the demand of binary analysis to data types,we researched and summarized the three major problem of data structure recovery.We presented an overview of this techniques and summarized the basic classification of the recovery algorithms and compared the advantages and disadvantages of the algorithms in the current works.(2)We investigated the existing vulnerability database,and found that some vulnerabilities are related to the embedded structure,which are important to the detection of such vulnerabilities.And by the investigation we show the necessity of the reverse to the embedded structure.(3)In this thesis,we proposed the two improvements to the pointer analysis.For the base address analysis,we improved it by decomposing the instructions to get the address modes;For the pointer connectivity analysis,we improved it by creating the pointer sets to collect the type information of the same pointer type.(4)Based on the above methods,we implemented the data structure recovery tool dataStuRec.To evaluate the accuracy of dataStuRec,we presented detailed experiments with nine Linux binary programs,and the evaluation results showed that dataStuRec could effectively reverse the data structure of programs.