The Research On Android Privacy Leak Detection Technology Based On Static Single Assignment Form

In recent years,with the development of Android operating system and applications,the privacy information security of mobile phone is more and more concerned by users.In order to solve the problem of privacy leakage,static detection technology has gradually become the focus of domestic and foreign researchers.Static detection technology will not actually run the application,but directly analyze the source code,and track the direction of tainted data by constructing control flow graph,so as to find the privacy leak path.Compared with dynamic detection,static detection technology has the advantages of high detection coverage and accuracy because of its direct effect on the source code.However,there is a problem that the static detection time is too long,so it is of great significance to study how to improve the efficiency of data flow analysis in the field of static detection.In essence,static analysis transforms abstract code into graph structure in mathematical form,which makes solving graph accessibility problem the core of taint analysis process.Therefore,in the process of static detection,the efficiency of data flow analysis is affected by the scale of control flow graph including the number of nodes and edges.However,due to the increasing amount of code in Android applications,the scale of control flow graph is too large.In order to improve the time efficiency of static detection,a sparse optimization scheme for control flow graph based on static single assignment form is proposed in this thesis.In the optimization scheme of this thesis,the control flow graph is converted to static single assignment form,so as to reduce some redundant nodes and edges without loss of control flow graph information,and eliminate the propagation process that does not affect the data flow analysis in the control flow graph.Finally,the sparse optimization of the control flow graph is realized,and the time cost of subsequent data flow analysis is reduced.The optimization scheme in this thesis is divided into the following steps: firstly,the immediate dominator array is used to save the ordered dominator set of nodes,and fast iterative algorithm based by Cooper is used to calculate the immediate dominator information;Then an abstract dominator tree is constructed according to the structural characteristics of the immediate dominator array.According to the dominator information in the dominator tree,the algorithm including the idea of dynamic programming is used to repeatedly use the dominance frontier,and the dominance frontier of the node is obtained along the opposite direction of the dominator tree;Finally,according to the information of the dominance frontier,Φ functions are inserted to convert the graph to static single assignment form,so as to realize sparse optimization of control flow graph,and finally improve the time efficiency of taint analysis in static detection.In this thesis,the proposed optimization scheme based on static single assignment form is implemented and verified by experiments.Firstly,the static detection tool Flow Droid is improved.In short,after Flow Droid constructs ICFG object and before data flow analysis,the optimization code is added to optimize the information in ICFG object.Then,the Droid Bench malicious application set and random real application set are used to test and analyze its performance.The test results show that the designed sparse optimization scheme can reduce the time cost of data flow analysis,which is of great significance for the research and application of Android privacy leak static detection technology.