Static Program Slicing Method Research Based On LLVM

Program slicing is one of the important methods for program analysis and understanding.It has been widely applied in practical production and research.Currently the best known slicing method is based on reachability over dependence graphs such as program dependence graphs(PDGs)or system dependence graphs(SDGs).The fastest now known SDG-based algorithm is based on the Interprocedural Finite Distributive Subset(IFDS)analysis.However,IFDS algorithm requires the whole exploded supergraph to be constructed ahead of time for computing summary edges.In certain situations,precise inter-procedural analysis methods such as IFDS are necessary.In addition to the dependence graph based method,Bergeretti and Carre propose information-flow analysis method,using information-flow relations to define slices.The information-flow method can analyze intra-procedures precisely,but not inter-procedures.Therefore,inter-procedural slicing method based on information-flow should be further studied.To solve the above problems,the major studies of this thesis include:(1)improving the static program slicing method based on SDG.(2)proposing a new inter-procedural program slicing method based on information-flow analysis.The object language of this thesis is LLVM IR,which can better meet full development of the applications when compared with other front-end languages.In summary,this thesis makes the following main contributions:(1)A new algorithm is presented to calculate summary edges.This new one makes full use of intra-procedural slicing results,without the need to construct any other intermediate structures such as supergraph,thus avoiding complicated calculation to a large extent.Based on this new algorithm,a LLVM IR slicer is implemented,noted as SDGSlicer.(2)In order to further improve the information-flow method,an inter-procedural slicing algorithm based on information-flow analysis is proposed in this thesis.Based on this,an information-flow slicer is implemented,named as InfoSlicer.(3)For comparison with SDGSlicer,IFDS method is first adapted to slice programs in LLVM IR form,noted as IFDSSlicer.Experimental results illustrate that(1)SDGSlicer enhances the efficiency of slicing without losing accuracy.(2)InfoSlicer can slice inter-procedures with the same slicing accuracy as SDGSlicer's.