John Jenkins – M.S. Final Exam

About the event

Advisor:  Dr. Haipeng Cai

Degree:  M.S. Computer Science

Abstract: Over the past decade, Android applications have become one of the principal interfaces by which consumers interact with technology. To date, there are reportedly 2.5 billion Android devices in circulation. Due to the global pervasiveness of the Android Operating System, Android Applications are subject to pervasive attack and thus require effective, efficient methods of detecting data leaks.

 A robust security analysis technique known as Taint Analysis performs an analysis of the sources (user inputs) and sinks (destinations for user input, such as a database) within an application to discover points in the dataflow where sensitive information may be leaking out (taints). However, performing taint analysis can be prohibitively expensive in terms of time and computational resources.

This paper refines Incremental Taint Analysis, a taint analysis technique that provides efficiency advantages over traditional taint analysis. Since changes between two versions of an Android application are typically small, Incremental Taint Analysis performs a change impact analysis between two application versions prior to running a Taint Analysis. The addition of this step allows for re-analyzing only the impacted portions of the program, thus saving considerable resources during analysis.

This thesis provides an open-source tool to the academic community that can perform Incremental Taint Analysis automatically by performing an automated change impact analysis between two versions and using the analysis results to perform Incremental Taint Analysis on any set of versioned Android applications.

 After performing Incremental Taint Analysis using this tool on 615 Android Applications, or otherwise 205 base-pair versions, the results demonstrate that Incremental Taint Analysis increases the efficiency of analyzing any random pair of Android applications by 42.2% when not considering any other factors. Furthermore, the average efficiency of the analysis increases by 73.8% when the overhead of analyzing small differences between two versions crosses a specific threshold.